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

41–50 of 134 posts

Re: When Big O Fools You

#41

Post by timmytokyo »

qwertyuiop924 wrote: post #26

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 game dev, it often matters a lot. The difference between code that takes cache performance into account and code that does not is often measured in frames per second.

Re: When Big O Fools You

#42

Post by Kenji »

ncw33 wrote: post #10
Kenji wrote: post #8

This is a great point and I'll probably have to do some performance measurements and change parts of my code now. I should be more careful with sacrificing contiguous storage for O(1) insertions. It is also worth noting that some manuals say that appending to an array list is O(1) amortized. Which is true, if you make an amortized analysis (which essentially distributes the workload of copying the array into a larger…

Insertion into an array list at a uniformly-distributed location is always O(n): you can't avoid moving half the list. Appending is amortized O(1).

You are right, my bad. I meant appending.

Re: When Big O Fools You

#43

Post by khedoros »

ctvo wrote: post #2

If the author sees this: please consider changing your color choices. It'd make reading the content you put so much work into producing easier for everyone. I couldn't finish the post. The 90s hacker's lair colors were that offensive.

I didn't find it offensive. The color scheme isn't that far off from what I prefer for my terminal settings.

What would you have preferred the author do differently?

Re: When Big O Fools You

#44

Post by stcredzero »

_benedict wrote: post #36
stcredzero wrote: post #31

Earlier quoted context omitted.

I would say, "If your software engineering begins and ends with [jargon] you're likely doing a terrible job. Measure, and test. Always." As a field, do we measure and test the effect of using various programming paradigms, patterns, and coding standards? I don't think most companies do this. Most developer decisions are made by "gut." As a field, we are still more like the "before" of Moneyball than the after.

There's a third option: analysis and understanding. This seems to be entirely forgotten by the "measure, test" crowd - the scientific method requires a hypothesis to test for measurements to be meaningful, and separately not all things that are produced are "tested" in every aspect, since many things are well established, and the application of that existing theoretical framework makes measurement and testing a waste…

The programming field isn't lacking in typical programmers with hypotheses. What it's lacking are typical programmers who are checking their hypotheses.

Re: When Big O Fools You

#45

Post by TylerE »

pc86 wrote: post #9
ctvo wrote: post #2

If the author sees this: please consider changing your color choices. It'd make reading the content you put so much work into producing easier for everyone. I couldn't finish the post. The 90s hacker's lair colors were that offensive.

This is not what "offensive" means.

That's exactly what offensive means.

adjective 1. causing resentful displeasure; highly irritating, angering, or annoying: offensive television commercials. 2. unpleasant or disagreeable to the sense: an offensive odor. 3. repugnant to the moral sense, good taste, or the like; insulting:

Re: When Big O Fools You

#46

Post by bfstein »

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…

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 front of a linked list is simply a matter of moving pointers and therefore constant time.

Re: When Big O Fools You

#47

Post by acbabis »

k__ wrote: post #21
acbabis wrote: post #6

Earlier quoted context omitted.

Why would you select against people with poor vision?

The green seems a bit harsh, yes. But all in all it is a good page for people with poor vision. No low-contrast and no white background, which are both considered bad on screens.

Yes, the white on black is fine. I checked the #8a7ae2 purple (http://webaim.org/resources/contrastchecker/) and, surprisingly, it passes WCAG AAA guidelines. I say "surprisingly" because it hurts my eyes. I think jumping between the alternating white and purple is what does it.

Re: When Big O Fools You

#48

Post by corysama »

qwertyuiop924 wrote: post #26

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 story I tell new kids is: The PlayStation2 ran at 300Mhz and a cache miss would cost you 50 cycles. The PlayStation3 ran at 3200Mhz and a cache miss would cost you 500 cycles. So, if you are cache missing a lot, your PS3 game will run as if it were on a PS2.

In other words, not paying attention to cache make your computer run like it's 10 years older than it is. You paid for a modern machine, but you are getting the results of a Craigslist junker. This is true outside of games. It's the reason 4x2Ghz cellphones struggle to run seemingly simple apps. It's a big part of the reason people struggle to orchestrate armies of servers (distributed computing is easier when it's 90% less distributed).

Is it really harder to work with the cache system instead of ignoring it? Yeah, it requires a tiny bit of study an a little bit of planning. In contrast, the theme I see a lot online is to completely dismiss physical reality in favor or theory. And, the theme I see almost universally in the students (and many senior engineers) I interview is complete ignorance of the very existence of cache and it's effects on the code they write. It's very concerning...

Re: When Big O Fools You

#49

Post by lziest »

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.

Re: When Big O Fools You

#50

Post by SamReidHughes »

geophile wrote: post #18
sn41 wrote: post #14

I agree with the fundamental point in the article, but isn't it well known that when you consider multiple levels of the memory hierarchy as a whole, big O notation needs to be modified to take into account the relative cost of access? I think the problem is not so much the big-O notation, but that the underlying assumption that the data access is from an "all main memory" model with no cache or secondary storage is…

Big O notation is typically counting comparisons, and ignores constant factors. It isn't that memory hierarchy is ignored so much as the equating of comparison growth (in n) with performance. The field of cache oblivious algorithms is focused explicitly on memory hierarchy, and accounts for cache misses.

It's typically not counting comparisons, there are none when inserting elements. But sometimes it pretends that comparisons are O(1).
Post reply on HN