Live data from Hacker News

When Big O Fools You

jackmott.github.io

61–70 of 134 posts

Re: When Big O Fools You

#61

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.

Memory access time is a constant multiplier, whether it hits or misses the cache. There can be a big difference in that constant depending on the access pattern, but it is still considered a constant factor.

Yes, random access (missing the cache every time) may be 100x slower than sequential (hitting the cache almost always), but if you're iterating through an array twice as large, it will still be 100x slower.

Re: When Big O Fools You

#62
The benefits of the list abstraction are small---because it's a clumsy, blub-like list abstraction with a container object and iterators.

Look at the code; termination of the loop is even based on an integer count pulled from the container.

A True Scotsman's linked list has no such thing. It's either an empty indicator (like NIL in Lisp) or a binary cell consisting of an item and a pointer to the next one.

The benefit of that abstraction is that you can recurse over it directly without clumsy additional parameters having to be passed.

Another benefit is substructure sharing. We can insert at the front of a list not only in O(1) time and that is great. But perhaps more importantly, existing copies of the list before the insertion do not change. And it is the same way if we delete from the front: we just move the local head pointer to the previous node, which doesn't affect anyone else who is still holding on to the pointer to the original front node.

These lists also allow lock-free operation, unlike "heavy weight" containers. Suppose we have a list that acts purely as a container, but is shared by multiple threads. We can insert into it by consing a new node onto the head of the current snapshot of the list, and then doing an atomic-compare-swap to install that head in place of the old head. If it fails, it means the list changed behind our back; we cons the node onto the new list (or rewrite the cons to point to the new one as its "rest" pointer) and try again.

Some of the caching benefits of the array will disappear if the array holds only references/pointers to items. In this example, the containers are typed. The List actually can allocate the int objects in an array that packs them together in memory. Whereas the LinkedList has individual separately allocated nodes which hold the int. Suppose the List and LinkedList hold pointers to heaped objects. Then the impact of caching is softened. It's still the case that multiple pointers in the array can be cached together; but these have to be traversed to access the items themselves. In the case of the LinkedList, we have to traverse a pointer to get to the next node and traverse a pointer to get to the heaped object. But two pointer traversals versus one is not as bad as one traversal versus zero. If the objects being traversed are fairly complex, and have pointers to additional objects that have to be examined during the traversal, it matters even less what kind of list they are accessed from. If I have a list of File objects, for each of which a stream is opened and a regex scan performed, why would I care whether it's an array list or a linked list.

The results shown in this test case tell me that the performances of the two containers are not that far off! Here they are subject to a test case that is designed to highlight the difference between them by making the container content, and its processing, almost as trivial as possible. That 38 seconds versus 51 difference is almost purely in the container-related operations. That is as bad as it gets: from there, the more actual real work you do per container node, the smaller the actual difference. (What is 51 versus 38 in "orders of magnitude"? Why 0.12 orders. It's 0.42 "binary orders of magnitude" (where 1 binary order is a doubling; terminology mine). So in terms of classic Moore's Law (speed doubling every 18 months), that's a 7.6 month advance. "My arrays are 7.6 months ahead of your linked list container, in Moore's Law, in a pure benchmark; eat my dust!"

Re: When Big O Fools You

#63

Here's a question: How often does this matter ? No, not that big O can fool you. That always matters. How often does it matter that non-contigouous memory access is slow? Really. How much do those few useconds really matter? In most apps, I would guess that a CPU cache miss isn't noticable by humans. Yes, non-contiguous structures are significantly slower, but if you don't need to be as fast as possible, eliminating…

A cache miss isn't noticeable by a human. Code that cache misses a lot runs 10-100x slower than code that takes into consideration that it's running on a physical machine and not an abstraction. That is very noticeable by humans. Even when your data structures and algos are designed with a nice O(logN), it's very noticeable when one program bogs down with 1/6 the data compared to another. I work in games, so the stor…

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-realtime speed requirements, or heavy data access, by all means, optimize to avoid cache miss.

But if you're writing a company-internal Rails app, nobody's going to notice, even if you're getting cache miss after cache miss. Which you probably won't.

Actually, if your language isn't compiled, a cache miss is the least of your worries, perf-wise.

And now I've got to see if I can optimize my code to avoid cache misses. But the code's in Scheme, so unless the initial access cost is amortized, I'm already doomed...

Re: When Big O Fools You

#64

Here's a question: How often does this matter ? No, not that big O can fool you. That always matters. How often does it matter that non-contigouous memory access is slow? Really. How much do those few useconds really matter? In most apps, I would guess that a CPU cache miss isn't noticable by humans. Yes, non-contiguous structures are significantly slower, but if you don't need to be as fast as possible, eliminating…

In games, critical systems and high traffic backend systems it means a lot.

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

Re: When Big O Fools You

#65
post #29

Here's a question: How often does this matter ? No, not that big O can fool you. That always matters. How often does it matter that non-contigouous memory access is slow? Really. How much do those few useconds really matter? In most apps, I would guess that a CPU cache miss isn't noticable by humans. Yes, non-contiguous structures are significantly slower, but if you don't need to be as fast as possible, eliminating…

Memory contiguity may be the most fundamental thing to keep in mind when doing numerical computing, for example.

Okay, so now I know.

Re: When Big O Fools You

#66

Here's a question: How often does this matter ? No, not that big O can fool you. That always matters. How often does it matter that non-contigouous memory access is slow? Really. How much do those few useconds really matter? In most apps, I would guess that a CPU cache miss isn't noticable by humans. Yes, non-contiguous structures are significantly slower, but if you don't need to be as fast as possible, eliminating…

This advice applies a ton to databases. At my job, our application is heavily disk i/o bound, with a database query typically taking several seconds. I benchmarked how different sorting the rows in our db by time would be compared to our current layout (partially sorted by user, partially sorted by time, which was completely accidental). Sorting by time benchmarked ~10x faster, which is absolutely huge.

Yeah, heavy data access is where this matters.

Re: When Big O Fools You

#67
post #61

Earlier quoted context omitted.

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.

Memory access time is a constant multiplier, whether it hits or misses the cache. There can be a big difference in that constant depending on the access pattern, but it is still considered a constant factor. Yes, random access (missing the cache every time) may be 100x slower than sequential (hitting the cache almost always), but if you're iterating through an array twice as large, it will still be 100x slower.

I agree, on the same machine, the slow-downs are constant for each level of cache and for ram access.

Re: When Big O Fools You

#68
post #57
post #46

Earlier quoted context omitted.

The nuance you're missing here is that the author is always inserting at the front of the arraylist. So even though the list grows dynamically, it still needs to move every value one spot over. e.g. arraylist: [0][1][2][3][ ] Even though there is space left in the array, we still need to move all the values one index to the right to be able to insert at the front, which takes O(n) time. In contrast, inserting at the…

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 require moving some fraction of the data.

The OP is discussing inserts at the start just because it is the worst-case scenario for arrays, then a positive result will still be true if some of the inserts are in the midddle or even near the end.

Re: When Big O Fools You

#69
There's a simpler and broader point: don't use Big O as the sole means of analysis of a high level language's data structures. The theoretical time/space complexity of a data structure may or may not accurately reflect how it's actually implemented in that language.

Re: When Big O Fools You

#70

Here's a question: How often does this matter ? No, not that big O can fool you. That always matters. How often does it matter that non-contigouous memory access is slow? Really. How much do those few useconds really matter? In most apps, I would guess that a CPU cache miss isn't noticable by humans. Yes, non-contiguous structures are significantly slower, but if you don't need to be as fast as possible, eliminating…

> How much do those few useconds really matter

There is at least one area where even a split micro will cost you millions.

P.S.: and even in consumer apps there microseconds here and there add up and then user will have overall sluggish experience.

Post reply on HN