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

71–80 of 134 posts

Re: When Big O Fools You

#71

Post by firethief »

mezuzza wrote: post #32
justusw wrote: post #25

This article points out a few right things, but also skips over the wrong parts. Namely, the amortised time complexity of dynamic lists. Amortised analysis treats operations not as single events but looks at the time complexity over the span of many operations (through something called "Accounting"). An initial "investment" of array over-allocation will be amortised by inserting, but only over time. Inserting into an…

This point should be understood very clearly: The article isn't wrong that an ArrayList has O(n) for a single insertion. However, the article misses that amortized analysis shows that the same structure can be made to have O(n) for n insertions as well. In effect, ArrayLists can be thought to have O(1) insertion time in practice meaning that all you are comparing are the differences in constants between the two struc…

Isn't that an argument for average case performance being a better predictor of average cases than worst case performance?

Re: When Big O Fools You

#72

Post by Guvante »

lziest wrote: post #49

Big O notation is asymptotic. Using only 5 insertions to understand Big O is definitely the wrong way. For example, insertion sort works better when the array is small, but insertion sort is definitely O(n^2), worse than qsort. Don't let Big O notation fool you, don't misunderstand Big O.

Inserts in that chart is the ratio of inserts to reads.

5 means "write five times then read once per iteration" not "write five times".

Re: When Big O Fools You

#73

Post by TillE »

qwertyuiop924 wrote: post #64
pmelendez wrote: post #56

Earlier quoted context omitted.

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.

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.

Re: When Big O Fools You

#74

Post by yxhuvud »

qwertyuiop924 wrote: post #63
corysama wrote: post #48

Earlier quoted context omitted.

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-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.

Re: When Big O Fools You

#76

Post by Koromix »

qwertyuiop924 wrote: post #63
corysama wrote: post #48

Earlier quoted context omitted.

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-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 cache-miss machines. They chase objects and pointers all around the memory.

Re: When Big O Fools You

#78

Post by fixerfrasse »

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…

Afaik, if you read in reverse, then you will miss cache optimization since it only works forward.

Re: When Big O Fools You

#79

Post by ric129 »

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.

Re: When Big O Fools You

#80

Post by gingerrr »

justusw wrote: post #25

This article points out a few right things, but also skips over the wrong parts. Namely, the amortised time complexity of dynamic lists. Amortised analysis treats operations not as single events but looks at the time complexity over the span of many operations (through something called "Accounting"). An initial "investment" of array over-allocation will be amortised by inserting, but only over time. Inserting into an…

Would be interesting to see the performance of Python's overallocation algo compared to a simpler one like Lua's, which just overallocates to the next power of 2 (so if you have a list with 4 items and want to add, it jumps to 8, then 16, then 32). I can't imagine the bitwise operations adding up to that much time added in Python, but Lua needs to increase size much less the larger the list (after 7 iterations Lua has room for 64 items, Python only 46 according to that link). Interesting choices, wonder which optimizes for what.

Would love to get Ierusalimschy and van Rossum in a room together and let them talk it out.

Post reply on HN