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

101–110 of 134 posts

Re: When Big O Fools You

#101

Post by readams »

A cache miss can be a slowdown of ~200x on modern CPU architectures. Lets say you have a choice of a O(n) algorithm that always misses the cache and a O(n lg n) algorithm that never misses the cache.

The crossover point where it makes sense to use the O(n) algorithm will occur when:

200 * n = n lg n

which occurs for n > 2^200. Most of us are not dealing with problems larger than can be represented in our universe, so cache efficiency matters, kids.

Note that this changes for other comparisons. Going from n maximally cache inefficient vs n^2 cache efficient is only worth it for n up to 200, and n lg n --> n^2 up to n about 2223.

Of course, in practice your algorithm won't be missing the cache on every access, so reality is somewhere between these values.

Re: When Big O Fools You

#102

Post by hinkley »

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.

One of my favorite ACM papers was an analysis on how the asymptotic runtime behaviors of various sort algorithms didn't tell the full story, and that the faster algorithms took a pretty big data set before they even broke even with some of the other sort algorithms. In fact I think at even 10,000 records it was still about 30% slower than a 'worse' algorithm and you had to get up to sorting a considerable amount of data before it was 'best'.

I don't know about you, but I don't sort 100k records in a single batch, and if I am it's because I messed up. But I might sort different batches of 100 records 1000 times a minute.

Re: When Big O Fools You

#103

Post by caf »

The result is that when you iterate over contiguous memory, you can access it about as fast as the CPU can operate, because you will be streaming chunks of data into the L1 cache.

This is not true at all. You'll be able to access it about as fast as the memory can operate - it'll still be much faster than randomly chasing pointers all over the place - but the maximum processing speed of the CPU is an order of magnitude greater than that again.

Re: When Big O Fools You

#104

Post by hinkley »

stcredzero wrote: post #31
valarauca1 wrote: post #27

Earlier quoted context omitted.

Furthermore amortization isn't always accounted for in Big-O. Inserting into into the head of a linked list is O(1), and for a vector it is O(n). But on modern hardware vector inserts are much faster. If your software engineering begins and ends with Big-O notation, your likely doing a terrible job. Measure, and test. Always.

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.

Hell, let's go a step farther. If your software engineering begins and ends with jargon, you're likely doing a terrible job.

(the business people always pick the worse solution that sounds better unless you can explain why they should care, in english, meant for normal human beings, without sounding condescending about it)

Re: When Big O Fools You

#105

Post by [deleted] »

Koromix wrote: post #89
qwertyuiop924 wrote: post #82

Earlier quoted context omitted.

>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) language…

[deleted]

Re: When Big O Fools You

#106

Post by johncolanduoni »

stcredzero wrote: post #28

Make Sure the Abstraction is Worth It Yes! All abstraction has a price. This is what people really mean when "all abstractions leak." Basically, all code and runtime features have a cost in terms of developer resources, cpu, memory, etc. The "inner game" of development isn't being able to muster huge amounts of "cleverness" power. The "inner game" is being able to put whatever resources you have to the best possible…

This isn't true at all. What's the cost in developer resources, cpu, or memory of making a complex number class in C++ a template over floats and doubles? How about the cost of using Rust's generics to make a parser that can parse from any linear source of bytes (e.g. both files and in memory byte arrays)?

There's plenty of abstractions which don't actually cost anything, and there's room for even more.

Re: When Big O Fools You

#107

Post by mannykannot »

vonmoltke wrote: post #58
_benedict wrote: post #36

Earlier quoted context omitted.

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 scientific method requires a hypothesis to test for measurements to be meaningful That's the simplistic grade school version. In practice, characterization and measurement is part of a feedback cycle that is used to develop and refine hypotheses. Experiments need a hypothesis to test, but measurements do not require experiments. Where the "measure, test" crowd usually goes off the rails is in not entering that…

I am not buying your distinction between measurements and experiments - experiments are measurements with a purpose.

You don't have to start with measurements. You can often do some analysis before you have anything to test, and that may save you a lot of time measuring, testing and tinkering with something that doesn't have a prayer of working. If you are measuring the environment that the system will interact with, you have already done some analysis in determining what to measure, and developed some theories about what is going to matter; that is hard to do without some causal reasoning. If your tests show you have a problem, you need to think about what is going on in order to find a solution.

There's a curious anti-intellectualism in software development that is opposed to any suggestion that thinking about problems is useful. It seems to go hand-in-hand with a simplistic world view that only sees dichotomies, together with the assumption that there can only be one answer.

Re: When Big O Fools You

#108

Post by qwertyuiop924 »

Koromix wrote: post #89
qwertyuiop924 wrote: post #82

Earlier quoted context omitted.

>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) language…

>But here's the thing: we could have both at the same time. I don't buy this dichotomy.

That's actually not true: OO, dynamism, late binding, and a lot of the other things that HLLs have to offer require a lot of pointer chasing and non-consecutive datastructures. I'm mostly a Schemer, and Scheme and Lisp have had decades of research put into making them compile and run fast. Most dynamic languages aren't so lucky. But the required pointer chasing and garbage collection mean they'll never be as fast as C.

Functional programming languages, however, are rarely late-binding, and don't expose as much about their implementation, so some of the pointer chasing can be avoided.

Rust doesn't need a GC, and is fairly C-like - or rather, ALGOL-like and BLISS-like - with added memory safety. So with a programmer who knows what they're doing, it can be pretty fast. But here's the rub: the faster a language is, the closer it has to be to the metal, and the less it can do with high-level features.

So yes, you can make HLLs faster, but you can't take the cache misses out of an HLL, and you can't make a systems language wearing an HLL's clothing - although Rust is making an admirable attempt.

Re: When Big O Fools You

#109

Post by Moto7451 »

yandrypozo wrote: post #94

The author is doing less than 10 insertions per benchmark, that's practically a constant O(1), even if you have to copy the entire array 5 or 10 times don't affect the Big O analysis

But he's inserting at the front of an array, which requires the rest of the elements to be copied into a new array. DotNetPerls has a clearer example: http://www.dotnetperls.com/list-insert

Re: When Big O Fools You

#110

Post by Danieru »

fixerfrasse wrote: post #78
DougBTX wrote: post #68

Earlier quoted context omitted.

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.

Intel cache prediction will detect both forward, backward, and some odd movement patterns. It has not been only forward prediction for a very long time.
Post reply on HN