Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

When Big O Fools You

jackmott.github.io

Post reply on HN
Print view View original

81–90 of 134 posts

Re: When Big O Fools You

#81

Post by qwertyuiop924 »

yxhuvud wrote: post #74
qwertyuiop924 wrote: post #63

Earlier quoted context omitted.

No, I don't deny it's important to know that cache misses exist, and what they can do: to the contrary, it's vital. However, in 90% of applications, it's not going to matter, because those applications are spending hundreds of cycles waiting anyways: Disk or network IO, user input, all that stuff is way slower than a cache miss. If you're writing a video game, or a database, or other software with very high soft-real…

Considering the Ruby object and memory models, you probably will get cache miss after cache miss. You just won't have the tools to do anything about them.

You're probably right. I was just thinking, "It can't possibly be THAT bad," especially seeing as there are so many objects that are referenced frequently.

Re: When Big O Fools You

#82

Post by qwertyuiop924 »

Koromix wrote: post #76
qwertyuiop924 wrote: post #63

Earlier quoted context omitted.

No, I don't deny it's important to know that cache misses exist, and what they can do: to the contrary, it's vital. However, in 90% of applications, it's not going to matter, because those applications are spending hundreds of cycles waiting anyways: Disk or network IO, user input, all that stuff is way slower than a cache miss. If you're writing a video game, or a database, or other software with very high soft-real…

You're looking at this problem backward. For example, you mention user input. Users may need a second to click or touch a button, but when they do the software should react instantly , and that does not leave you that many cycles. My smartphone's lock screen is my go-to example: most times it fails to follow my finger, and I barely have anything running on it. Most of the dynamic languages are data and instruction ca…

>My smartphone's lock screen is my go-to example: most times it fails to follow my finger, and I barely have anything running on it.

...That doesn't sound like a cache miss. Knowing Android, A cache miss is probably the least of your worries.

>Users may need a second to click or touch a button, but when they do the software should react instantly, and that does not leave you that many cycles.

You raise a good point...

>Most of the dynamic languages are data and instruction cache-miss machines. They chase objects and pointers all around the memory.

...and this is part of my point. If you look at a problem and think, "A high-level language is fast enough," then you are implicitly saying that the latency of a cache miss is acceptable. And IME, in most cases that's true. I mean, heck, I'm using Scheme, so while I may have pointer chases like the Amazon has trees, but I CAN optimize them into array lookups, and my code is compiled: not great, but better than most HLLs.

It's the same argument as always: perf vs. development speed. You can be in the C and FP loop, or the Lisp and JS loop.

Re: When Big O Fools You

#83

Post by Const-me »

ric129 wrote: post #79
Const-me wrote: post #75

Ported to C++, added two ATL collections, also added 100M elements data point: https://github.com/Const-me/CollectionMicrobench Arrays are still generally faster than lists. The funny thing is Microsoft’s linked lists are faster than C++ standard vectors.

>The funny thing is Microsoft’s linked lists are faster than C++ standard vectors. If I had to guess, it's because the std::vector is more conservative in memory use and it causes more malloc/array copy calls.

I think the main reason is CAtlList class encapsulates its own memory pool. It allocates RAM in batches. The default batch size for CAtlList is 10 elements/batch, user-adjustable in constructor, but I kept the default value 10.

The elements are created directly adjacent to each other. This makes iteration faster because RAM locality despite the pointer-based data structure.

Re: When Big O Fools You

#84

Post by qwertyuiop924 »

TillE wrote: post #73
qwertyuiop924 wrote: post #64

Earlier quoted context omitted.

That I could guess. My point is that most code isn't in high traffic backend systems and games.

There are a million things that a person writing a boring CRUD web app doesn't need to know. But if you want to be a good programmer, you should probably understand how a computer works.

I didn't say you shouldn't. I just asked how often that kind of performance optimization mattered. The world is not comprised only of CRUD and situations where that kind of perf matters.

But I do agree that even if you don't have to worry about cache latency for every single thing you write, it is something you should know about.

Re: When Big O Fools You

#85

Post by nayuki »

Arrays are fast for getting random elements and inserting/deleting at the end (amortized), but slow for inserting/deleting in the middle.

Linked lists are fast for inserting/deleting/getting at the beginning and end, but slow for random access for anything in the middle.

So far, that's what the article covered. Now if you want fast random insertions/deletions and fast random access, this is possible with balanced trees. A tree-based list can support all single-element operations in O(log n) time. Sample code: https://www.nayuki.io/page/avl-tree-list

Re: When Big O Fools You

#86

Post by edejong »

nayuki wrote: post #85

Arrays are fast for getting random elements and inserting/deleting at the end (amortized), but slow for inserting/deleting in the middle. Linked lists are fast for inserting/deleting/getting at the beginning and end, but slow for random access for anything in the middle. So far, that's what the article covered. Now if you want fast random insertions/deletions and fast random access, this is possible with balanced tre…

That's not what the article is about nayuki. The author of the article makes and proves a claim that arrays are faster than linked lists regardless of the insertion point. The metrics presented clearly show this.

The reason for this abnormality is cache locality (there are other reasons, which I will not go into right here).

Balanced trees can be pretty slow in fact. After some operations, a tree structure can become quite fragmented in memory, leading to many cache misses. In my experience, it is often faster to work with arrays instead of trees when processing in memory. However, using external storage, a b-tree often introduces quite some performance gain.

Re: When Big O Fools You

#87

Post by edejong »

JohnLeTigre wrote: post #59
tillytal wrote: post #33

Earlier quoted context omitted.

Surely the main point is that O(n) + O(n) = O(2n) = O(n) = O(n + 1) = O(n) + O(1) and the constant factors left out of O() often dominate execution time. Cache performance is just one example of a constant factor, right?

Cache performance is not constant, if it was, we wouldn't even consider it when optimizing. The point is to use data that was recently fetched into the (faster) cache memory as much as possible instead of incuring the penalty of a cache miss Cache performance really depends on memory access patterns. Anyways :) I'm being pedantic here, I should probably go back to work.

Not necessarily. You might want to create an algorithm that iterates in a sequential fashion through memory, since your memory controller will see the iteration and prefetch the next block of memory. This is a huge performance win on larger data structures.

Re: When Big O Fools You

#89

Post by Koromix »

qwertyuiop924 wrote: post #82
Koromix wrote: post #76

Earlier quoted context omitted.

You're looking at this problem backward. For example, you mention user input. Users may need a second to click or touch a button, but when they do the software should react instantly , and that does not leave you that many cycles. My smartphone's lock screen is my go-to example: most times it fails to follow my finger, and I barely have anything running on it. Most of the dynamic languages are data and instruction ca…

>My smartphone's lock screen is my go-to example: most times it fails to follow my finger, and I barely have anything running on it. ...That doesn't sound like a cache miss. Knowing Android, A cache miss is probably the least of your worries. >Users may need a second to click or touch a button, but when they do the software should react instantly, and that does not leave you that many cycles. You raise a good point..…

> That doesn't sound like a cache miss. Knowing Android, A cache miss is probably the least of your worries.

My example was meant to illustrate the user input problem. From what I know about Android, the absymal performance is very much a case of "death from a thousand cuts".

> It's the same argument as always: perf vs. development speed. You can be in the C and FP loop, or the Lisp and JS loop.

The fast(er) languages we have are old and full of warts, and that makes them slow to develop in. The heavily used HLLs such as Python and Ruby were made by people who did not care much (at all?) about performance, and it shows in many design decisions. But here's the thing: we could have both at the same time. I don't buy this dichotomy.

Re: When Big O Fools You

#90

Post by thaumasiotes »

DougBTX wrote: post #68
gens wrote: post #57

Earlier quoted context omitted.

Can't you just imagine it is reversed, where the_array[num_things-1] is the first ?

Yes, then it would be a discussion about append performance instead of insert performance. Might be handy to do if you know that all the changes to an array will be inserts at the front, then you can just write the array in reverse and also read in reverse. But it is helpful to keep the terminology clear, because an insert in the middle of a linked list is still O(1), but inserting into the middle of an array will re…

> But it is helpful to keep the terminology clear, because an insert in the middle of a linked list is still O(1), but inserting into the middle of an array will require moving some fraction of the data.

This is true if you already have a reference to the middle of the list. If you don't (say, because you want to insert while preserving the fact that the list is sorted), then inserting into a linked list is O(n) just like the array is.

Post reply on HN