Why is processing a sorted array faster than an unsorted array?

http://stackoverflow.com/q/11227809/399268

by ashishgandhi • 14 years ago

590 119 14 years ago

Bakkot• 14 years ago

Several months old, but still worth a read - especially for the end of Mystical's comment, where he discusses the different optimizations performed by different compilers. Particularly interesting is the Intel Compiler, which effectively optimizes out the benchmark itself: something to keep in mind when testing your own code, if you want your results to make sense.

lazydon• 14 years ago

Ah this.. the highest voted Q on SO. Not again plz - http://www.hnsearch.com/search#request/all&q=Why+is+proc... (interesting case of same page diff urls bypassing HN duplicate url check though)

Go to http://stackoverflow.com/questions sort by votes and read from top if you like.

m0th87• 14 years ago

I'm a regular HN reader and I've never seen this before. I don't think it's so bad to re-post, especially since it's actually HN-quality content.

mck-2• 14 years ago

I'd second that -- the fact that it jumped to the top means there are enough people who haven't seen it before

JepZ• 14 years ago

I also saw it a few weeks ago here on HN and was wondering why it is here again... At least I wasn't the only one who thought so ;-)

Sometimes I wonder how old 'news' can be and still climb up to the top of HN. Is there somewhere a search engine which can tell the author if something was on HN already? Or if it is about good websites an not about news, why nobody posted a link to google.com during the last weeks? ;-)

msbarnett• 14 years ago

> Sometimes I wonder how old 'news' can be and still climb up to the top of HN. Is there somewhere a search engine which can tell the author if something was on HN already?

What value is there to the people who are finding this content interesting today in rejecting it because some other subset of the HN community saw it at some arbitrarily distant time in the past?

Reposted interesting technical content beats the hell out of Boring industry naval-gazing news story #82795 and Android vs Apple "news" intended to provoke a fanbo flamewar thread #762483101.

If you're spending so much time on HN that you not only recognize reposts but that you see them so often it bothers you enough to complain in the comments, consider doing something more productive with your time.

dllthomas• 14 years ago

Wasn't there something from the 80's recently?

Jun8• 14 years ago

This is totally missing the point of a major part of HN's (and other communities') value: The actual links may or may not be important, it's the community discussion that has the more value. In many cases, I find myself not even clicking on the links on HN (either the topic is too mundane or I've already seen it from another source) but go straight for comments.

This particular post is a good example: I have seen this interesting SO tidbit before but learned a few things from the HN discussion.

sondh• 14 years ago

The results show that the 4 other links receive very low attention (3 links with 2 points, 1 with 21 points, all of them with no comments). Given the HN audience is spread across the globe with consistent interest in programming articles, I think there must be inference of posting time. Poster karma is not a big factor here because ColinWright has 33711 karma. Anyone wants to conduct such a research?

mck-2• 14 years ago

This is actually quite interesting. What it tells me is that "luck" (not timing, nor karma) is the most significant determinant whether something goes viral or not. Content comes second.

fakeer• 14 years ago

It's certainly better than those countless why you should be 'hacking' stuff with XYZ or why you shouldn't.

raverbashing• 14 years ago

Interesting test, but it's not news if you know something about code optimization.

Caching of the data may also play a part on similar cases (but not this one - or better, the effect is negligible)

Here's a little test that can be tried. Make the test result (inside the if) be true or false alternately (for example, sum only if the index is even), see how long it takes.

Spoiler: modern branch predictors can detect and predict cyclic conditions

fleitz• 14 years ago

Sorted arrays make it easy for a simple branch predictor guess correctly, if the branch predictor guesses correctly then you avoid a pipeline stall.

Assuming the median value in the array is 128 then for the sorted case the first half of the array will have one cache miss and the second half will have one cache miss.

If the OP optimized their code, sorted/filtered the array and then summed only those values greater than 128 it would be obvious why sorting is faster.

prophetjohn4• 14 years ago

Branch prediction is not the only reason this is faster and probably not even the biggest reason.

Since the array is sorted,

    if (data[c] >= 128)

will evaluate to true consecutively. When the cache requests something from memory, it will request blocks containing multiple words at a time. Since every data[c] that needs to be added to sum is in a contiguous piece of memory, the code is minimizing the number of times a block is transferred from memory to the cache. This is the concept of spatial locality[1].

[1]http://en.wikipedia.org/wiki/Locality_of_reference#Locality_...

alexkus2• 14 years ago

Eh, what new item is it requesting from memory inside the branch?

  if (data[c] >= 128)
    sum += data[c];

Whether the condition evaluates to true or false it has already retreived the value from the data array in order to test it against the condition.

prophetjohn4• 14 years ago

You're right, that's a pretty careless mistake. Considering that, the only way to stretch this into locality would be to assume that sum would be used in rapid enough succession so as to be able to live in a register instead of go back to a cache or even memory. That difference seems negligible, though.

plorkyeran• 14 years ago

In an optimized build data[c] is read from memory only once per loop iteration, so the memory read patterns are identical in the sorted and unsorted cases.

tptacek7• 14 years ago

No. The "true" or "false" value of a simple expression isn't stored in memory. It's stored as a bit in the status register as a side effect of the "cmp" instruction†. It is no faster for "cmp" to set "true" than it is to set "false".

† (CMP is actually setting carry, overflow, sign, zero, &c; "truth" or "falsity" is decided by the specific conditional jump, here JL, which checks if sign != overflow).

prophetjohn4• 14 years ago

That's not what I was saying. I was indicating that more memory accesses would be required in unsorted data for the `sum += data[c]` computation, obviously overlooking that data[c] is already in a cache, and probably in a register as a result of the comparison with 128.

w0utert• 14 years ago

I don't think this is true. The loop that sums the values always fetches the array items linearly. Whether they are sorted or not does not make any difference. Since the accumulator ('sum') can be kept in a register there should be no store operations in the inner loop, which means it reduces to simply reading consecutive memory, inspecting the values, and adding some of them to a register.

Branch mispredictions are the only likely cause for the runtime difference. It would be interesting to see whether using multiplexing (sum += data[c] > 128 ? data[c] : 0) or conditional assignments would make any difference. Some CPU's have opcodes for these that don't require branching, but I'm not sure whether they use the branch prediction logic.

mrich• 14 years ago

Not to hate on the great top-voted answer, but isn't it a bit strange that it was posted a mere five minutes after the question?

asdfs• 14 years ago

It's become common on stackexchange sites to post a brief answer immediately, follow by a much longer edit.

d0m• 14 years ago

Seems like the answer has been edited after lots of upvote to give a more detailed explanation.

dkersten• 14 years ago

I often do this. There is one answer which I've been quite literally editing for about three years. Every few months I add a bit more information or a few more references or links to it. Its become a kind of personal (but public) repository of information on the topic.

jrockway• 14 years ago

Doesn't matter. You can answer your own question immediately after posting it if you want. It's designed to be a collections of questions and answers, not a forum, and so it doesn't matter who answers what question.

bduerst2• 14 years ago

Although Stackexchange puts in some mild game dynamics to make it a competition. At least for some, if you're into that kind of thing.

nuclear_eclipse• 14 years ago

If you read the post author's comment on his own post, he went back and added all the explanation/analogy after making the initial post that just said it was down to branch prediction.

masklinn• 14 years ago

Not really, a very common pattern on SO is to jump on a question to which you know you have a good answer, put something very short (but correct) and then edit in a better, longer response. This avoids "losing" initial votes from people looking at responses while you're fleshing out the description, adding benchmarks, etc...

It's definitely gaming the system, but it's not really suspicious (in the sense of "guy asks a question and immediately puts a response he had pre-written in a text editor" suspicious)

m_myers• 14 years ago

The "suspicious" case you mention is explicitly supported by the system; you can actually write the question and answer at the same time if you want. The normal content rules still apply, of course; if the question isn't about an actual problem, you're more likely to win a bundle of downvotes.

chousuke• 14 years ago

I think without this ability to "game" the system SO wouldn't be half as good as it is now. You end up with brilliant and above all complete answers that can be kept up to date, and the moderation policy reduces duplication and clutter, keeping the SNR high.

Sure, some people might be motivated only by receiving high scores, but it seems that the benefits outweigh the potential for abuse

rayiner7• 14 years ago

Modern architectures really are quite complex, and it's important to keep your internal machine model up to date with what's happening. Examples: It used to be on a 486 even correctly-predicted taken branches had a two-cycle penalty. It used to be important whether you arranged your code so the most commonly taken code was on the fall through path or not. Today, correctly predicted branches are free--the processor stitches together the current path and the new path so there are no bubbles in the pipeline. Virtual function calls also used to be more expensive back in the day, because CPU's didn't try to predict the target address of the branch. Today, CPU's have a buffer that maps from a program counter to a target address, so if your virtual function call predictably hits the same target each time, the only overhead will be the extra memory accesses to indirect through the v-table.

At the same time, things that are expensive today may not be so in the near future. Haswell is supposed to make uncontended synchronization operations almost free. It'll make a lot of algorithms, particularly lock-free algorithms, much more practical than they are today. For example, C++ smart pointers are slow in multi-threaded situations because the reference count manipulation needs to be done under a lock. But the lock is almost never needed (except when it is). Cheap synchronization should make it much more practical to use reference counting more pervasively in C++ programs.

dan002• 14 years ago

"For example, C++ smart pointers are slow in multi-threaded situations because the reference count manipulation needs to be done under a lock."

Several architectures support atomic increment and decrement operations, so there's no need for any lock. Libaries like OpenSceneGraph use them for their reference counting.

Also Haskell isn't magical in this regard. Their lock free implementations will also presumably just use safe atomic operations.

jrajav• 14 years ago

I think s/he meant the upcoming Haswell processor architectures, not Haskell the language.

rayiner7• 14 years ago

Atomic increment/decrement operations still generate a locked memory transaction of some form or the other at the processor level. Haswell is Intel's new CPU that is supposed to implement some level of hardware transactional memory, leveraging the infrastructure used for cache coherency. In theory, this will make transactional operations (atomic increment/decrement is just a tiny transaction) as cheap as a regular memory operation so long as there is no contention.

cube132• 14 years ago

It's important to note that even at the hardware level(for intel x64, at least), atomic increments and decrements are, in fact, just the operations with locks around them.

So relying heavily on them in multithreaded cases with heavy contention can actually reduce performance over a more complex lockless scheme.

grannyg00se• 14 years ago

What about the time taken to do the sorting? Is there some rule of thumb that hints at whether taking the time to sort the data is going to be a net win?

Tichy• 14 years ago

I would expect sorting to take a lot longer than just summing.

chiph• 14 years ago

Unless you have external information, you will need to take at least one pass through the data to determine if its sorted or not.

saraid216• 14 years ago

The time it takes to sort an array is a rather well-understood problem. If you can reason about how much performance gain you'll get from looping through a sorted versus unsorted array, you can probably estimate the additional cost of the sort itself.

propercoil• 14 years ago

sorting an array of integers that you know the max value of (like in the question in SO) will take you O(n) with count sort, so this will be pretty damn fast

Lagged2Death5• 14 years ago

You are the victim of branch prediction fail.

"Failure" is a perfectly serviceable word and the cutesy "fail" is just annoying in a technical discussion like this.

dclusin3• 14 years ago

When I see colloquialisms used in technical discussions I generally assume that the author is attempting to convey the topic of conversation in a more casual and approachable way so as to maximize the amount of of people who read and think about what is being said. You may not be aware of this but pretentiousness does turn a lot of people off. This stops said people from inquiring further about things they may actually discover they care about. The downside of all this pretentiousness is that the world is as a whole less educated because the people who possess the knowledge and know-how refuse to accommodate their audiences with simple word changes such as this.

Lagged2Death5• 14 years ago

There's nothing pretentious about the word "failure."

I do not believe the people who plod through a huge multi-page, multi-code-sample question at StackOverflow are just casual dabblers who are likely to leap away from the discussion when they discover the top-rated answer features the word "failure."

peterwwillis2• 14 years ago

That anyone would grok less word salad resulting from cutesyhood is dubious, bro.

kahawe3• 14 years ago

> "fail" is just annoying in a technical discussion

I am sorry but you know what is REALLY annoying? Nit-picking at what must be the atomic level considering the depth and detail of this perfectly brilliant reply.

Technical discussions need a LOT more people like Alexander Yee aka "Mysticial" - and technical discussions sure as hell do not need ANY people like you complaining about the choice of words or slang as long as it is perfectly clear and understandable for the target audience and on that account he more than delivered.

mrtriangle• 14 years ago

word, kahawe, you just said what I was thinking.

Lagged2Death5• 14 years ago

Nit-picking at what must be the atomic level considering the depth and detail of this perfectly brilliant reply.

Can't have it both ways. The more depth and detail a discussion tries to present, the more important it is to get the details right. The medium (StackExchange) even recognizes this and has editing, correcting, and collaborative fixing built into its DNA, for that very reason.

The more famous this response becomes, the more ESL readers there will be. Why trip them up this way? There's just no reason to use "fail" like this here.

"Branch prediction fail" is not actually a very clear or precise phrase. It could mean the failure of a single branch prediction attempt; it could mean the failure of the technique in a particular case, and it could refer to an author's opinion that it was a failure in general. Why muddy the waters?

glhaynes• 14 years ago

I didn't read "fail" there as being cutesy/meme-y. I [think I] heard people use the term "branch prediction fail" many years before "FAIL!" became "a thing".

soup10• 14 years ago

One take away point from this for non-c coders is that higher level languages will always be significantly slower than C because it's far easier to make these kinds of fiddly pipeline optimizations when you don't have another abstraction layer in between mucking things up. There's few java programmers for instance that both intuitevly understand how both the machine architecture, and the JVM compiler will affect the code they write. There's too many quirks. While in theory it's possible to write comparably fast java code(assuming your willing to do sketchy things for memory manipulation related tasks). In practice it's significantly more difficult to get all the juice out with higher level languages.

jwilliams2• 14 years ago

And assembly would be faster again?

Both the C compiler and the JVM JIT target machine code. I don't buy that one is automatically & universally superior to the other. You can equally argue that the JIT will always be superior because it's run-time aware.

krakensden• 14 years ago

In the counterfactual world where the JVM's JIT commonly won bechmarks against C, that would be a great point.

Retric• 14 years ago

It's a question of degrees of freedom.

Lower level languages like C can include ASM code with little overhead, they can also swap code around at run time just like the JIT. Granted, the vast majority of CRUD code has no need for such capability's, but as JVM languages have more constraints and absolutely no new capability's when it comes to the ASM they produce they fall behind when performance is most critical.

That said, the vast majority of programmers are never get any where near these limits.

a-priori• 14 years ago

Yes, it's always possible to write assembly code that is at least as fast as C code, if not faster.

But it's entirely another question whether you, as a mere mortal human, are able to do a better job at producing assembly code in practice, for non-trivial programs, than a compiler.

juiceandjuice• 14 years ago

Yes, there are some critical algorithms which will be always be faster in C.

In practice it's significantly more difficult to optimize all your code based on deep knowledge of architectures, compilers, and even compiler versions than it is to just let a JIT compiler optimize at runtime.

rayiner7• 14 years ago

What the JVM compiler does to your code isn't really that much harder to understand than what GCC or LLVM does to your code. Assuming equally skilled programmers, I think it's often easier to write fast code in a higher level language. The primary bottleneck for performance is usually developer time. If you can get the non-performance critical parts written in half the time, you have way more time to optimize. Higher level languages also generally have much better profiling and introspection tools, which make debugging much easier. Debugging tightly optimized code is, of course, one of the big time sucks in optimizing code.

gus_massa• 14 years ago

On the other hand, sometime in higher level languages the compiler could prove more constrains and then apply more aggressive optimizations. (I don't remember a specific case now, perhaps we still need a few years for an interesting example.)

Another possibility is that using a higher level language it is possible to write more complicated code, with smarter optimizations, because the programmer doesn't have to take care of all the details. For example, the Pypy project they has a Phyton interpreter written in a combination of RPhyton an C that is faster than the standard Phyton interpreter that is written directly in C.

wmf2• 14 years ago

Fortran defaults to strict aliasing and C defaults to loose aliasing, leading to naive Fortran programs sometimes being optimized better than equivalent naive C programs. Or as some people say, "Fortran is faster than C".

Dylan168072• 14 years ago

You can carefully design an interpreter to mitigate these issues.

You can also have a JIT compiler remove branches altogether based on experimental data, something completely impossible in C.

Don't point at one thing and claim it makes a language class faster or slower.

alexkus2• 14 years ago

Indeed, a JIT compiler will always be able to take advantage of something that isn't possible for something that is compiled once and set in stone.

However, that's not to say that upfront compilation is doomed never to compete.

Profiling C compilers can mimic this behaviour to an extent, although they can only profile for the situtations they experience during their training phase so they can't adapt to unforeseen scenarios or dramatic shifts in the input stream.

C compilers could be extended to implement several/many variants of each function based on different possible code paths and, using information gained from on the fly timings it could switch between different variants in order to optimise execution. Combinatorics would place a low limit on the number of percentage of possible variants implemented though.

Finally, no-one ever said that C has to be a compiled language. There's nothing stopping someone writing a JIT C interpreter and getting the best of both worlds. (Ugh!)

DannyBee2• 14 years ago

It's not impossible in C. It's impossible statically.

There is nothing that stops you from JIT'ing C/C++. LLVM includes a JIT that functions just fine on C/C++ programs.

cdavid• 14 years ago

This is not correct: there are things that can be faster than C because of the compilation aspect (the compiler can only optimize with the information it has, some of them can only be known at runtime).

A good example is iteration over non trivial, multi-dimensional structures: if you iterate over a single dimension, then some variables become actual constant, but this can only be known once you know the iterator parameters (i.e. even profile-guided optimization would not work).

You could obviously implement a runtime-based optimizer in C, but then the assertion that you can never beat C is a tautology.

ChuckMcM• 14 years ago

The counter argument is that if you've compiled into a semantic description (bytecodes for a virtual machine) then the underlying VM implementation can optimize a semantically correct pipeline based on features available to it. Thus programmer time is saved (they wrote their code once) at the expense of a higher burden on the VM to do the right thing.

This argument (that the VM new best) was put forward by Bill Joy early on in the development of Java as the reason Java would eventually be faster than compiled C code. We discovered that in practice 'friction' [1] between hot spot compilation and instruction set architectures nearly always dominated this equation (leaving Java code slower).

Architectures where the friction was reduced (like the Jazelle instruction set on ARM) could swing the balance the other way.

[1] Friction in this case is the cost to performance of the difference of expressibility between a byte coded instruction and the actual processor architecture.

derleth• 14 years ago

> higher level languages will always be significantly slower than C

Looking at benchmarks, I can see this is factually incorrect.

Also... show me where C allows you to see the pipeline directly. It's hard to optimize something you can't see.

C is an abstraction layer. So is assembly. Both are relatively thick when you're talking about things like branch prediction and pipelining.

peterwwillis2• 14 years ago

If you need to super-optimize execution you can build C or ASM code and call it via a library or inline it into your high-level language. Java can call functions in shared libraries (or use JNI) and Perl can inline straight C or ASM.

I'm not sure why you'd want to get "all the juice" out of higher level languages, though. I thought the whole point was to abstract away from machine optimization? For example, to learn to write more efficient Perl I picked up "Mastering Algorithms with Perl" and it had loads of helpful tips.

gizzlon• 14 years ago

On the other hand, using a higher lever language and ready-made code can mean than someone else has already implemented all those optimizations you would never implement yourself.

cvursache• 14 years ago

If you're looking for a good online course on how computer systems work from AND gate scale - up to data center size, the iTunesU course <<"Computer Science 61C", UC Berkeley, w/ Daniel Garcia>> is really informative and fun to watch.

http://itunes.apple.com/de/itunes-u/computer-science-61c-001...

juddlyon• 14 years ago

The fact that someone would take the time to help someone in such depth restores my faith in humanity. With a picture to boot.

kahawe3• 14 years ago

The fact that someone would complain about the use of the word "fail", on HN no less, should nicely even out whatever faith was restored, unfortunately...

Evbn3• 14 years ago

Nope, you can look away from the troll and focus your attention on the good stuff. You have the power to weigh good stuff more heavily.

Permit• 14 years ago

Mystical mentions that Intel's compiler uses loop interchange to gain an extraordinary speedup. There's actually a great answer further down the page that details this and was great as I wasn't aware of how it worked: http://stackoverflow.com/a/11303693/300908

DannyBee2• 14 years ago

Meh, GCC can do the interchange as well, it just isn't on by default.

zippie• 14 years ago

The answer focuses on branch misprediction but there is also another factor - CPU data prefetch.

In order to offset increasing CAS latencies (largely due to the increasing number of channels) modern CPU's are greedy (in a good sense) and fetch more pages per memory controller read request than are necessary.

If your data is laid out continuously (in this case - sorted), chances of the pages you need next being primed via prefetch are greatly increased and further read requests to the memory controller may be reduced or avoided.

I benchmarked the effect of data prefetching on modern processors with large data structures (usually limited to L1d cache lines):

https://github.com/johnj/llds#l1-data-prefetch-misses-200000...

A plausible analogy for CPU prefetching would be "readahead" mechanisms implemented by modern filesystems and operating systems.

ww520• 14 years ago

While prefetch is an important factor, it is not the case here since the data array is accessed sequentially in both the sorted or unsorted scenarios. Also the initial number generation loop already primes the data in the memory for either scenario.

ColinWright2• 14 years ago

Isn't HN amazing? Here is the same article submitted on no less than four previous occasions:

* http://news.ycombinator.com/item?id=4185226

* http://news.ycombinator.com/item?id=4170972

* http://news.ycombinator.com/item?id=4355548

* http://news.ycombinator.com/item?id=4167834

Total upvotes: 29.

Total discussion: 0.

No wonder people try to game the system and find optimal times to submit things.

No wonder people think HN is broken.

dfc2• 14 years ago

Colin, I find it amazing that you did not confess that you were one of the people who submitted a duplicate of this story, your duplicate being the most recent:

4167834: zmanji 105 days ago

4170972: VeXocide 104 days ago

4185226: moobirubi 101 days ago

4355548: ColinWright 63 days ago

Especially given your fight against duplicated stories:

"My intention in doing what I did was always to try to create value by reducing duplication (and thereby reducing wasted effort)"

Glass houses?

tptacek7• 14 years ago

Who the hell cares, you two? We're talking about it now. The system worked fine for this story. Can we move on from this sideshow?

This whole story generated a pretty great thread; why look for reasons to have a problem with that?

ColinWright2• 14 years ago

I was going to reply privately, but could find no contact details. I see you espouse HN Notify, so I'm hoping you'll see this response.

My duplicate detector found the initial pair almost immediately. I did nothing, because there was no discussion, so I didn't know which one to point to. Then the third came. Still no discussion. I watched in considerable dismay as a submission that I thought was absolutely excellent, and deserving of significant discussion, sank without trace.

Was it just unlucky? Did no one read it? There were a few desultory upvotes - a few had read it. But was I so completely wrong about what HN would find interesting?

I couldn't believe it, so I submitted it again over a month later. Still no upvotes, still no discussion. It seemed I was wrong about the audience here.

And now I can see that I was right about HN being interested in deeply technical issues like this, and I'm happy. I'm less happy that a brilliant item like this took four submissions, sorry, five submissions before it got noticed.

That's why now I generally try to point out duplicates in two circumstances. One is when they come close together, and that's to help stop a split discussion. The other is when there was a significant discussion on an earlier occasion, and I want people to benefit from previous comments.

So no, I don't think it's a case of glass houses.

dennisgorelik• 14 years ago

Alexander J. Yee, who answered the question is a student who calculated Pi to 5 trillion digits:

http://www.geekosystem.com/pi-five-trillion-digits-alexander... The main challenge for a computation of such a size, is that both software and hardware are pushed beyond their limits. For such a long computation and with so much hardware, failure is not just a probability. It is a given.

marblar• 14 years ago

Where can I learn more about this?

hm8• 14 years ago

TL;DR Would it not be great that we change the branch prediction implementation to switch on/off automatically(with every new process)? This would be difficult to trace or even implement but I'm just guessing. The CPU stops using branch prediction if a lot of it's predictions are failing but starts again after some time.

keefe• 14 years ago

a very broad intuition is that less entropy in the input, more predictability in executing algorithms on that input, more regularities to exploit

Why is processing a sorted array faster than an unsorted array?

Related Stories