Comment by twawaaay | Hacker News Reader

Comment by twawaaay | Hacker News Reader

Parent Full thread

Honestly, for a single threaded processing potentially the largest improvement come from:

* Exploiting cache locality (related data in same cache line, operations hit the data before it leaves cache, etc.)

* Exploiting cache prefetching (understanding how to lay out your data and operations so that CPU prefetches data from memory into cache BEFORE it is needed)

* Ensuring high density of data being accessed (make sure you only access what you need and the cache lines you access contain only data you need and not random other things that are not involved in the operation)

... at least in my own experience.

These can be so powerful that may make a dumb algorithm perform like an absolute superstar.

A lot of developers overthink algorithms. They try to create something that is super efficient on paper forgetting that the algorithm is not being executed on paper but by a real CPU. Sometimes it is better to sacrifice "paper efficiency" and just ensure cache locality, prefetching, data density and the result is speedup so large it more than covers for a little bit of inefficiency.

The article is about the same thing essentially? Decreasing number of memory accesses is the same thing as exploiting cache locality. Registers are the just more local more high-speed level of cache. Given on modern superscalar CPUs registers are virtual anyway.

> The article is about the same thing essentially? Decreasing number of memory accesses is the same thing as exploiting cache locality.

No, it is not. For example, you can have an application that is doing a lot of memory accesses, but the working set is controlled to fit the cache except for couple of things that need to be fetched into the cache but you make sure those things fit predictable pattern that the CPU prefetcher can recognise and supply in advance of you needing it.

Now, having less memory accesses usually helps, but it is kinda newb way of looking at the problem. What if you have to make a lot of accesses because your application is memory heavy (say it is a database)? Does it mean there is nothing you can do to improve it? Of course there are things you can do to improve it -- but you need a bit more in depth knowledge.

I think this article is about cache locality, but temporal cache locality. Which is just as important albeit orthogonal to what you are describing.

> These can be so powerful that may make a dumb algorithm perform like an absolute superstar.

That's an over-generalization that is only valid for small input sizes. Consider:

- an O(N*log N) heap-sort implemented by a decent programmer in idiomatic high-level code.

- a dumb O(N^2) bubble-sort coded by an absolute assembly optimization wizard.

Your O(N^2) sort will probably be much faster for small input sizes, but it won't take a large input size for it to become dog-crap slow. You can improve constant factors all day, but that won't obviate the need for doing millions or billions of comparisons.

You can only take a dumb algorithm so far before it breaks down completely in practice.

This is not a theoretical thing either - in unoptimized codebases, I've often seen people finding low-hanging fruit by looking for inadvertent O(N^2) or even O(N^3) behaviour (usually it's not obvious nested loops, but looping hidden by indirection i.e. function calls) and replacing it with an O(N*log N) or O(N) alternative.

> That's an over-generalization

I think most people here will interpret the word "can" in the sentence you're quoting as a caveat emptor; and I would add the same applies to TFA. Loop fusion can etc. but measure if it actually does in your exact context.

> You can improve constant factors all day, but that won't obviate the need for doing millions comparisons. > You can only take a dumb algorithm so far before it breaks down completely in practice.

If the dumb algorithm relies entirely on arithmetic while the better algorithm has conditional jumps, branch prediction misses can play against it for unexpectedly large input sizes.

Micro-optimizations may fall short quickly, but big-O() approved algorithms don't always win either, in practice.

People usually underestimate where that line is. In my past experience, I ended up benchmarking binary search vs linear search on a collection of small objects. The breakeven point on a modern CPU was at 10 megabytes of data. Although this is a particularly extreme example, most people assume that collections of a few thousand items are where you should switch to big-O-optimal algorithms, but the breakeven is usually several orders of magnitude higher.

That’s very surprising to me. My intuition screams that surely a binary search is competitive with a linear search even at small sizes. I would love to see benchmarks and code for this if you have them handy.

If your problem domain never expands to more than a couple of thousand elements that needs to be ordered, but really often (which is very often the case) the the bubble sort is the way to go (Especially if you have almost-sorted data making bubble sort the ideal choice).

> That's an over-generalization

I think this is exactly the problem with these types of comparisons. As the original commenter also hinted: You can not generalize best choice about the algorithm.

I am pretty used to people defending their blind trust in big-O notation.

As I mentioned, the idea is to be open to alternative ways of thinking.

Performance is incredibly difficult or impossible to generalise. I have many times worked on a project where people said confidently it is not possible to speed something up and then I speeded it up by multiple orders of magnitude.

I worked for one of largest banks in the world and we had a batch task on MongoDB that took 12 hours to complete. The previous team, before I joined, took it down to 4 hours but then said it is not possible to improve it anymore. The consultants from MongoDB confirmed it. This was a huge problem because there was a delay of 4 hours between end of trading day and the report being finished which was unacceptable.

I took it down to ~15 seconds. Without changing data structure or the database or the application technology. The only significant thing I did is I made both the data suppliers to stream it to our app and the consumers to stream the results during the data. So the data was being processed during trading day and partial results were already being pushed to the client. The only thing that needed to be done was to sync between the sources and the clients and it took about 15 s to do it (and I could probably take it even further but it was not worth the effort).

So you see, it is all about being open minded.

bubble sort is never as good as insertion sort, not even for almost-sorted data or for six elements

bubble sort is never the way to go

generally in the case you're describing, where you have a few thousand elements that need to stay sorted in the face of insertions, a b-tree would be a better choice, or failing that, merge in a batch of updates whenever the update file gets big enough

either of these can beat bubble sort or insertion sort in this situation by more than an order of magnitude

I'm sure it's possible to conceive of a pathological hardware architecture where bubble sort is faster than insertion sort on small inputs.

I mean sure, you can always come up with a processor that tries to detect insertion sort and makes it slow while it has hardware acceleration for bubble sort. That doesn't make it a very useful model, though.

Also using big-O notation turns the "1/2" of the post title into a discarded constant.

My algorithms class discussed the importance of not forgetting the constants. We talked about an algorithm for recursively taking averages of a list of numbers (or whatever that's not important) that was O(n^2) but only in worst case, while there was a version that is guaranteed O(nlogn) or something but the constant factor was 27. This meant the growth only mattered in extreme cases.

That math doesn't seem to check out. Say with base-2 log and a 27 factor difference, for 1000 it would be 1000^2 = 1,000,000 vs 27 * 1000 x log 1000 = 270,000. I wouldn't call n=1000 an extreme case for most problems. Just because practical counterexamples exist, don't think that it applies to your problem unless demonstratably so, an then still worry about N being larger than originally designed for.

Reply on news.ycombinator.com