Timeline for Why is processing a sorted array faster than processing an unsorted array?
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Nov 15, 2021 at 5:31 | comment | added | MuhammadAliDEV | @GManNickG this ans explains in an easy and understandable way. | |
| Oct 31, 2021 at 20:03 | comment | added | GManNickG | What does this answer add that is missing from the existing answers? | |
| Oct 27, 2021 at 1:41 | comment | added | MuhammadAliDEV | @PeterCordes check now. fixed the issuse. | |
| Oct 27, 2021 at 1:40 | history | edited | MuhammadAliDEV | CC BY-SA 4.0 |
fixed the error part of the question.
|
| Oct 26, 2021 at 9:45 | comment | added | Peter Cordes | What does Example 2 have to do with branch prediction? You're comparing linear search against binary search and similar algorithms. Human searching of huge sorted lists isn't normally done by scanning each entry in order. You would do that once you got to the right page, in which case yeah you'd scan down a column until you either found it or saw you'd gone past, e.g. to Johnston, and yes you can scan quickly in a way that's similar to linear search. But really you're not fully looking at every entry, so even that isn't a perfect analogy. | |
| Oct 26, 2021 at 9:40 | history | edited | Peter Cordes | CC BY-SA 4.0 |
This isn't Javascript. Also, the compiler has nothing to do with this effect, other than having created branchy asm in the first place instead of using branchless count += (arr[i] < N/2); with x86 setcc/add, or ARM64 cinc. (Or SIMD vectorization.)
|
| Oct 26, 2021 at 9:35 | history | edited | Peter Cordes | CC BY-SA 4.0 |
This isn't Javascript
|
| Oct 26, 2021 at 9:33 | comment | added | Peter Cordes | compiler optimizes the code here and skips the if condition. No, branch prediction (and branch mispredictions) are a run-time effect. If the compiler knew it was sorted, it could do a loop-fission optimization and make two loops, one that just searches for the first false case, then the other that just runs the rest of the array. (Or I guess optimize away that 2nd loop since it's empty.) | |
| Oct 26, 2021 at 9:30 | history | edited | Dharman | CC BY-SA 4.0 |
Stack Overflow is like an encyclopedia, so we prefer to omit these types of phrases. It is assumed that everyone here is trying to be helpful.
|
| Oct 26, 2021 at 9:25 | history | answered | MuhammadAliDEV | CC BY-SA 4.0 |