Timeline for Why is processing a sorted array faster than processing an unsorted array?
Current License: CC BY-SA 3.0
24 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 23, 2022 at 12:45 | comment | added | puppydrum64 | @Omer The branch predictions are purely at a processor level. Even in assembly there's no syntax to help the CPU branch predict. It boils down to the way the hardware works. There's just no way to know whether a branch will be taken ahead of time. While it's obvious to you and me, a computer really isn't as smart. It's not aware of anything that exists outside of a few instructions ahead and the caches. | |
| Apr 21, 2022 at 5:36 | comment | added | Peter Cordes |
@AgrimPathak: No, unless you can sort once but iterate over the array many times, the time to sort an array is much larger than one pass with this loop. Comparison-based sorting also involves many data-dependent branches. (O(N) sorts like Counting Sort or Radix Sort may avoid mispredicts depending on implementation choice, but still have enough overhead to make it not worth it.) What you should actually do is encourage the compiler to make branchless asm, like sum += (v >= 128 ? v : 0); or similar, or to vectorize with SIMD.
|
|
| Jun 27, 2020 at 5:57 | comment | added | Omer | Is the branch predictions mostly happen at compiler level or it is handled by processor? And why java or c++ can not handled it? I mean why is not complicated to predict it right? | |
| Jun 20, 2020 at 9:12 | history | edited | CommunityBot |
Commonmark migration
|
|
| Nov 9, 2018 at 5:34 | review | Suggested edits | |||
| Nov 9, 2018 at 6:03 | |||||
| Jul 6, 2018 at 20:13 | review | Low quality answers | |||
| Jul 6, 2018 at 20:47 | |||||
| Oct 13, 2017 at 21:43 | comment | added | knickum | @AnandTyagi As Peter Wone noted, it's not that the compiler knows which array is sorted or not. Imagine an extremely simple branch predictor that takes the same path as the previous iteration, e.g. a train taking a left if it took a left last time, and vice versa. For a sorted array of 256 ints, (ignoring the undefined first iteration), the prediction would be correct from 2-128, wrong at 129, and then correct from 130-256. Now, that's a terrible branch predictor that would only work in this specific situation, but a really good predictor should still handle this capably. | |
| Sep 30, 2017 at 7:35 | review | Suggested edits | |||
| Sep 30, 2017 at 9:35 | |||||
| Sep 15, 2017 at 14:16 | comment | added | आनंद | @DanielFischer does compiler knows which array is sorted and which one is not? | |
| May 25, 2017 at 17:51 | comment | added | Dr t | I would recommend a look at: en.wikibooks.org/wiki/Optimizing_C%2B%2B/Writing_efficient_code/… which provides a good discussion with examples of this topic including some that are not mentioned in any comments that i have seen regarding this question. | |
| S Aug 5, 2016 at 7:53 | history | suggested | Shankar | CC BY-SA 3.0 |
grammar fix
|
| Aug 5, 2016 at 7:28 | review | Suggested edits | |||
| S Aug 5, 2016 at 7:53 | |||||
| Jul 1, 2016 at 23:34 | history | edited | dippas | CC BY-SA 3.0 |
added 8 characters in body
|
| Jan 29, 2016 at 1:24 | history | wiki removed | Shog9 | ||
| Jan 28, 2016 at 20:56 | history | made wiki | Post Made Community Wiki by George Stocker | ||
| May 1, 2015 at 4:02 | comment | added | Peter Wone | @AdamFreeman - Sorting is relevant here only inasmuch as in this code it increases branch prediction to 100% success. | |
| Nov 9, 2014 at 13:49 | comment | added | Daniel Fischer | @FilipBartuzi Branch prediction takes place in the processor, below the language level (but the language may offer ways to tell the compiler what's likely, so the compiler can emit code suited to that). In your example, the out-of-order 3 will lead to a branch-misprediction (for appropriate conditions, where 3 gives a different result than 1000), and thus processing that array will likely take a couple dozen or hundred nanoseconds longer than a sorted array would, hardly ever noticeable. What costs time is i high rate of mispredictions, one misprediction per 1000 isn't much. | |
| Nov 9, 2014 at 13:37 | comment | added | Filip Bartuzi | When does branch prediction takes place? When does language will know that array is sorted? I'm thinking of situation of array that looks like: [1,2,3,4,5,...998,999,1000, 3, 10001, 10002] ? will this obscure 3 increase running time? Will it be as long as unsorted array? | |
| Oct 30, 2014 at 10:14 | comment | added | Daniel Fischer | @AgrimPathak That depends. For not too large input, an algorithm with higher complexity is faster than an algorithm with lower complexity when the constants are smaller for the algorithm with higher complexity. Where the break-even point is can be hard to predict. Also, compare this, locality is important. Big-O is important, but it is not the sole criterion for performance. | |
| Oct 30, 2014 at 7:51 | comment | added | Agrim Pathak | So basically everything I conventionally learned about big-O is out of the window? Better to incur a sorting cost than a branching cost? | |
| Sep 23, 2014 at 18:58 | comment | added | Adam Freeman | Does branch prediction work better on sorted arrays vs. arrays with different patterns? For example, for the array --> { 10, 5, 20, 10, 40, 20, ... } the next element in the array from the pattern is 80. Would this kind of array be sped up by branch prediction in which the next element is 80 here if the pattern is followed? Or does it usually only help with sorted arrays? | |
| Oct 9, 2013 at 4:51 | history | edited | 웃웃웃웃웃 | CC BY-SA 3.0 |
[Edit removed during grace period]
|
| Jun 28, 2012 at 6:23 | history | edited | Tim Pietzcker | CC BY-SA 3.0 |
typo
|
| Jun 27, 2012 at 13:54 | history | answered | Daniel Fischer | CC BY-SA 3.0 |