8 ms·

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

590 points by ashishgandhi 14y ago

Bakkot 14y 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 14y ago
Ah this.. the highest voted Q on SO. Not again plz - http://www.hnsearch.com/search#request/all&q=Why+is+processing+a+sorted+array+faster+than+an+unsorted+array 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 http://stackoverflow.com/questions sort by votes and read from top if you like.
- m0th87 14y 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- 14y ago
    I'd second that -- the fact that it jumped to the top means there are enough people who haven't seen it before
- deleted 14y ago
  [deleted]
- JepZ 14y 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 14y 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 14y ago
    Wasn't there something from the 80's recently?
    - TeMPOraL 14y ago
      A week or two ago we had a text from 70's about diamonds, AFAIR. :).
- Jun8 14y 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 14y 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- 14y 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 14y ago
  It's certainly better than those countless why you should be 'hacking' stuff with XYZ or why you shouldn't.
raverbashing 14y 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 14y 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.
prophetjohn 14y 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_of_reference http://en.wikipedia.org/wiki/Locality_of_reference#Locality_...
- alexkus 14y 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.
  - prophetjohn 14y 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.
    - tptacek 14y ago
      You can just compile the code and look at it; yes, the sum gets a register.
- plorkyeran 14y 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.
- tptacek 14y 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).
mrich 14y 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 14y ago
  It's become common on stackexchange sites to post a brief answer immediately, follow by a much longer edit.
- d0m 14y ago
  Seems like the answer has been edited after lots of upvote to give a more detailed explanation.
  - dkersten 14y 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.
    - gmaslov 14y ago
      I hope you keep a backup of it yourself.
- jrockway 14y 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.
  - bduerst 14y 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.
rayiner 14y 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.
- dan00 14y 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 14y ago
    I think s/he meant the upcoming Haswell processor architectures, not Haskell the language.
  - rayiner 14y 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.
grannyg00se 14y 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 14y ago
  I would expect sorting to take a lot longer than just summing.
- chiph 14y 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 14y 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 14y 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
Lagged2Death 14y 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.
- dclusin 14y 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.
  - Lagged2Death 14y 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."
    - dclusin 14y ago
      I suspect that you also believe that you are not being pretentious and pedantic by raising this point. I emphatically disagree. The latter half of the criticism raised in my comment was directed towards your initial comment and comments or explanations like yours that are prevalent in advanced fields. I apologize for not being clear.
      - Lagged2Death 14y ago
        I'm sorry, but I got turned off from reading the rest of your comment when I got to "emphatically." Maybe you should change it to "like totally." To accommodate me.
deleted 14y ago
[deleted]
soup10 14y 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.
- jwilliams 14y 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 14y ago
    In the counterfactual world where the JVM's JIT commonly won bechmarks against C, that would be a great point.
    - rayiner 14y ago
      What kind of benchmarks? The benchmarks C folks always want to use are the ones that favor static compilation (matrix multiplication, etc). The best any language can do in that situation is tie--it's basically just an exercise of how much money has gone into the compiler's low-level optimizer. Consider a benchmark implementing a common situation in real programs--a performance intensive loop calling some code located in a plugin that isn't known until runtime. The JVM will wipe the floor with a C compiler in that situation--since the JVM can do inlining at runtime between module boundaries, while a C compiler cannot do inlining at runtime at all. Or, when memory management is involved, they always want to test situations where everything can be easily pool-allocated, instead of complex situations involving lots of dynamic allocation. But in situations where code is really allocating lots of short-lived objects (e.g. functional code for optimizing compiler trees), the GC in a JVM is going to wipe the floor with any malloc() implementation.
deleted 14y ago
[deleted]
cvursache 14y 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-fall/id461056991 http://itunes.apple.com/de/itunes-u/computer-science-61c-001...
juddlyon 14y 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.
- kahawe 14y 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...
  - Evbn 14y 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 14y 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 http://stackoverflow.com/a/11303693/300908
- DannyBee 14y ago
  Meh, GCC can do the interchange as well, it just isn't on by default.
deleted 14y ago
[deleted]
zippie 14y 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-per-hardware-sample 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 14y 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.
ColinWright 14y 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=4185226 * http://news.ycombinator.com/item?id=4170972 http://news.ycombinator.com/item?id=4170972 * http://news.ycombinator.com/item?id=4355548 http://news.ycombinator.com/item?id=4355548 * http://news.ycombinator.com/item?id=4167834 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.
- dfc 14y 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?
  - tptacek 14y 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?
    - dfc 14y ago
      I realize that your comment was mainly rhetorical but... I don't have a problem with duplicates. I think a lot of things are worth reading/seeing/doing multiple times. Moreover I do no think or expect anyone to be perfect. I do have a problem with Colin's crusade against duplicates. I don't think it sets the right tone for HN and it is a disincentive for people to submit things. I would rather have people feel free/comfortable submitting things and then let the up voting system separate the chaff. If you go through Colin's comments you can see hundreds of discussion ending comments about duplicate stories. Given his distaste for duplicates I found it disingenuous that he would bring up the problem of duplicates given his was the third duplicate in the list. If its a recent exact duplicate the submission is merely another upvote and which is a neat function of the system (this happened to me recently with a story I submitted about correlation/causation that you had already submitted) If its a duplicate and boring it will be flagged or at the very least not up voted. If its a duplicate and people find it interesting it will be up voted. If a duplicate is up voted that I have read before I can choose to ignore it or read the discussion to see if there are new opinions. Duplicates are not a problem for me, reducing the likelihood of people contributing to HN is a problem.
dennisgorelik 14y 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-yee-shigeru-kondo/ 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 14y ago
Where can I learn more about this?
hm8 14y 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 14y ago
a very broad intuition is that less entropy in the input, more predictability in executing algorithms on that input, more regularities to exploit

590 points by ashishgandhi 14y 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 14y ago

Ah this.. the highest voted Q on SO. Not again plz - http://www.hnsearch.com/search#request/all&q=Why+is+processing+a+sorted+array+faster+than+an+unsorted+array 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 http://stackoverflow.com/questions sort by votes and read from top if you like.

m0th87 14y 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- 14y ago
  I'd second that -- the fact that it jumped to the top means there are enough people who haven't seen it before
deleted 14y ago
[deleted]
JepZ 14y 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 14y 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 14y ago
  Wasn't there something from the 80's recently?
  - TeMPOraL 14y ago
    A week or two ago we had a text from 70's about diamonds, AFAIR. :).
Jun8 14y 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 14y 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- 14y 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 14y ago
It's certainly better than those countless why you should be 'hacking' stuff with XYZ or why you shouldn't.

raverbashing 14y 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 14y 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.

prophetjohn 14y 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_of_reference http://en.wikipedia.org/wiki/Locality_of_reference#Locality_...

alexkus 14y 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.
- prophetjohn 14y 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.
  - tptacek 14y ago
    You can just compile the code and look at it; yes, the sum gets a register.
plorkyeran 14y 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.
tptacek 14y 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).

mrich 14y 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 14y ago
It's become common on stackexchange sites to post a brief answer immediately, follow by a much longer edit.
d0m 14y ago
Seems like the answer has been edited after lots of upvote to give a more detailed explanation.
- dkersten 14y 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.
  - gmaslov 14y ago
    I hope you keep a backup of it yourself.
jrockway 14y 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.
- bduerst 14y 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.

rayiner 14y 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.

dan00 14y 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 14y ago
  I think s/he meant the upcoming Haswell processor architectures, not Haskell the language.
- rayiner 14y 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.

grannyg00se 14y 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 14y ago
I would expect sorting to take a lot longer than just summing.
chiph 14y 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 14y 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 14y 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

Lagged2Death 14y 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.

dclusin 14y 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.
- Lagged2Death 14y 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."
  - dclusin 14y ago
    I suspect that you also believe that you are not being pretentious and pedantic by raising this point. I emphatically disagree. The latter half of the criticism raised in my comment was directed towards your initial comment and comments or explanations like yours that are prevalent in advanced fields. I apologize for not being clear.
    - Lagged2Death 14y ago
      I'm sorry, but I got turned off from reading the rest of your comment when I got to "emphatically." Maybe you should change it to "like totally." To accommodate me.

deleted 14y ago

[deleted]

soup10 14y 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.

jwilliams 14y 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 14y ago
  In the counterfactual world where the JVM's JIT commonly won bechmarks against C, that would be a great point.
  - rayiner 14y ago
    What kind of benchmarks? The benchmarks C folks always want to use are the ones that favor static compilation (matrix multiplication, etc). The best any language can do in that situation is tie--it's basically just an exercise of how much money has gone into the compiler's low-level optimizer. Consider a benchmark implementing a common situation in real programs--a performance intensive loop calling some code located in a plugin that isn't known until runtime. The JVM will wipe the floor with a C compiler in that situation--since the JVM can do inlining at runtime between module boundaries, while a C compiler cannot do inlining at runtime at all. Or, when memory management is involved, they always want to test situations where everything can be easily pool-allocated, instead of complex situations involving lots of dynamic allocation. But in situations where code is really allocating lots of short-lived objects (e.g. functional code for optimizing compiler trees), the GC in a JVM is going to wipe the floor with any malloc() implementation.

deleted 14y ago

[deleted]

cvursache 14y 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-fall/id461056991 http://itunes.apple.com/de/itunes-u/computer-science-61c-001...

juddlyon 14y 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.

kahawe 14y 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...
- Evbn 14y 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 14y 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 http://stackoverflow.com/a/11303693/300908

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

deleted 14y ago

[deleted]

zippie 14y 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-per-hardware-sample 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 14y 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.

ColinWright 14y 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=4185226 * http://news.ycombinator.com/item?id=4170972 http://news.ycombinator.com/item?id=4170972 * http://news.ycombinator.com/item?id=4355548 http://news.ycombinator.com/item?id=4355548 * http://news.ycombinator.com/item?id=4167834 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.

dfc 14y 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?
- tptacek 14y 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?
  - dfc 14y ago
    I realize that your comment was mainly rhetorical but... I don't have a problem with duplicates. I think a lot of things are worth reading/seeing/doing multiple times. Moreover I do no think or expect anyone to be perfect. I do have a problem with Colin's crusade against duplicates. I don't think it sets the right tone for HN and it is a disincentive for people to submit things. I would rather have people feel free/comfortable submitting things and then let the up voting system separate the chaff. If you go through Colin's comments you can see hundreds of discussion ending comments about duplicate stories. Given his distaste for duplicates I found it disingenuous that he would bring up the problem of duplicates given his was the third duplicate in the list. If its a recent exact duplicate the submission is merely another upvote and which is a neat function of the system (this happened to me recently with a story I submitted about correlation/causation that you had already submitted) If its a duplicate and boring it will be flagged or at the very least not up voted. If its a duplicate and people find it interesting it will be up voted. If a duplicate is up voted that I have read before I can choose to ignore it or read the discussion to see if there are new opinions. Duplicates are not a problem for me, reducing the likelihood of people contributing to HN is a problem.

dennisgorelik 14y 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-yee-shigeru-kondo/ 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 14y ago

Where can I learn more about this?

hm8 14y 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 14y ago

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