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

Current License: CC BY-SA 4.0

97 events
when toggle format what by license comment
Sep 22 at 8:12 comment added I Love Coding voted just because its the most upvoted answer on Stackoverflow.
Sep 13 at 14:58 comment added Sajeel Hassan voted just because its the most upvoted answer on StackOverflow
Sep 13 at 14:11 review Suggested edits
Sep 13 at 16:17
Aug 20 at 16:47 history edited T.Todua CC BY-SA 4.0
I know this edit might seem weird, but if you take a bit precise look, that fits best to the example, as admitted by author itself a bit down below.
Aug 12 at 15:44 review Suggested edits
Aug 12 at 18:36
Jul 3 at 13:50 review Suggested edits
Jul 3 at 16:22
Apr 1 at 11:59 review Suggested edits
Apr 1 at 12:25
Mar 10 at 6:20 review Suggested edits
Mar 10 at 17:33
Jan 21 at 2:37 history bounty ended CommunityBot
Dec 30, 2021 at 9:38 review Suggested edits
Dec 30, 2021 at 9:58
Aug 21, 2021 at 4:24 comment added Kuba hasn't forgotten Monica @C.Binair The prediction is made at runtime, and it costs millions of transistors per core to implement it. And multiple Ph.D. dissertations worth of work :) Modern branch predictors are marvels of engineering, to the point that the Eiffel Tower starts looking minuscule. They are hidden from the view, but they are largely responsible for the performance of modern processors. Turn branch prediction off (e.g. by writing code that slams the predictor and makes it useless), and an i7 3GHz core is like a cheap ARM Arduino...
Aug 1, 2021 at 13:19 review Suggested edits
Aug 2, 2021 at 6:48
Jul 25, 2021 at 22:06 history edited Zoe stands with Ukraine♦ CC BY-SA 4.0
added 7 characters in body
Jun 12, 2021 at 0:53 comment added Peter Cordes @Tom: Not exactly. Most ISAs don't have any mechanism for the compiler to actually provide branch hints to the CPU. likely/unlikely macros mostly just affect decision to use cmov (branchless) vs. actually branching, and to lay out the asm so the expected case has fewer taken branches. (i.e. the fast path can get fetched contiguously in wide chunks by the pipeline.) Is there a compiler hint for GCC to force branch prediction to always go a certain way?, and this is an example of actual x86 code-gen.
Jun 12, 2021 at 0:43 history edited Peter Cordes CC BY-SA 4.0
"the branch predictors". No, we're not talking about any specific branch predictors in that sentence, just roll that back and remove the extra word instead of changing it. And although warm-up is normally good, it clashes with "slow down".
S Jun 11, 2021 at 16:00 history edited Pawel Veselov CC BY-SA 4.0
Some grammatical, spelling and punctuation mistakes corrected.
S Jun 11, 2021 at 16:00 history suggested Kashif Iftikhar CC BY-SA 4.0
Some Grammatical Mistakes corrected.
Jun 11, 2021 at 10:44 review Suggested edits
S Jun 11, 2021 at 16:00
Jun 3, 2021 at 21:18 review Suggested edits
Jun 4, 2021 at 4:55
May 11, 2021 at 21:58 history edited Erwin Brandstetter CC BY-SA 4.0
Don't use protocol-relative URLs. See: https://nickcraver.com/blog/2017/05/22/https-on-stack-overflow/#mistakes-protocol-relative-urls
Mar 10, 2021 at 14:47 comment added Tom @C.Binair Primarily it's runtime, i.e. processor predicts branches while executing the code. The processor also remembers previous results and use that to predict next jump. However, compiler can provide some initial hints for branch prediction while compiling - search for "likely" and "unlikely" attributes. So you could say the answer is kinda both, but runtime is when it actually happens.
Mar 3, 2021 at 16:21 comment added C. Binair I hope this question is simple, but I'm confused. The prediction is that made during runtime or already when compiling?
Jan 10, 2021 at 15:35 history edited Deduplicator CC BY-SA 4.0
copy-edited
Jan 8, 2021 at 2:03 comment added WhozCraig @Mycotina It's easier to understand when you think of the instruction pipeline cache as tracks, the train (with cars) as the instructions, and the indicator of whether you go left or right by some dude at the END of the train; not the beginning. By the time you see him to know you've guessed right, not only is it too late to switch things, the pipeline ahead is already populated, but in the wrong direction. If you guessed wrong the predicted pipeline needs to be thrown out (derail the train; drag it back before the switch house, put it back on the tracks, and send it the other way).
Jan 5, 2021 at 15:51 comment added Raphael @Mycotina, I'm no expert, but what I understand is: the processor needs multiple steps to execute a single instruction (fetching, decoding, etc) -- this is called "instruction pipelining" -- so, as an optimization, it will fetch multiple instructions at once and "warm up" the next instructions while executing the current one. If the wrong branch is chosen, the instructions being "warmed up" in the pipeline must be discarded, so that the instructions on the right branch can be put into the pipeline instead.
Dec 8, 2020 at 9:26 comment added Mycotina I have a hard time understanding the explanation. Because, even with branch predictor, isn't the computer still need to know if it guessed right or wrong in the end? Because if not, how will it know if it should do the rollback? And for knowing if it is right or wrong, isn't we need to compute the result of the if condition nonetheless? Which in the end, will consume the same resource without branch prediction, or even slower because we need to correct mistakes?
Oct 16, 2020 at 14:04 comment added mins Incidently branch prediction failure can also be exploited by a program to obtain crypto keys being used by another program on the same CPU core.
Oct 6, 2020 at 8:37 comment added Agoston Horvath @MatiasChara it's really hidden, see en.wikipedia.org/wiki/… ; "however most compilers will perform an arithmetic shift, causing the blank to be filled with the sign bit of the left operand". I guess it's a de-facto standard by now.
Jul 22, 2020 at 13:59 history rollback Ryan Lundy
Rollback to Revision 41
Jul 14, 2020 at 19:01 history edited Abhishek Bhagate CC BY-SA 4.0
fixed grammar
Jul 12, 2020 at 23:52 comment added Matias Chara wait a second, doesnt shifting negative values to the right yield implementation-defined values? int t = (data[c] - 128) >> 31; sum += ~t & data[c];
Jun 20, 2020 at 9:12 history edited CommunityBot
Commonmark migration
Mar 26, 2020 at 10:57 history rollback Peter Cordes
Rollback to Revision 38 - None of the previous edit was an improvement. Removing "on" was not necessary, but not harmful. Some of the other changes were harmful, like introducing a "but" between two things that are both positive, and a "the" before branch predictors. "Is able to" also suits that context better than "can".
Mar 26, 2020 at 10:31 history edited Arsen Khachaturyan CC BY-SA 4.0
deleted 12 characters in body
Jan 29, 2020 at 21:34 history bounty ended CommunityBot
Dec 28, 2019 at 2:46 history edited Peter Cordes CC BY-SA 4.0
cmov can be slower than branchy, especially when GCC does it wrong. Link a followup Q&A
Dec 28, 2019 at 1:25 history edited Cœur CC BY-SA 4.0
added 3 characters in body
Nov 15, 2019 at 18:07 history bounty ended Meraj al Maksud
Sep 10, 2019 at 18:02 review Suggested edits
Sep 10, 2019 at 18:15
May 27, 2019 at 12:42 history edited Peter Mortensen CC BY-SA 4.0
Second iteration.
May 27, 2019 at 12:36 history edited Peter Mortensen CC BY-SA 4.0
Active reading [<http://en.wikipedia.org/wiki/NetBeans> <https://en.wikipedia.org/wiki/Intel_C%2B%2B_Compiler>]. Introduced abbr. "ICC" - "Intel C++ Compiler" is a proper noun.
May 4, 2019 at 19:55 history rollback Cody Gray♦
Rollback to Revision 30
May 2, 2019 at 18:43 history edited Alec CC BY-SA 4.0
added 2 characters in body
Apr 10, 2019 at 4:49 history rollback royhowie
Rollback to Revision 30
Apr 8, 2019 at 3:26 history edited BSMP CC BY-SA 4.0
In each case the image is described by the text above it, thus the alt text is redundant. Testing an edit re: https://meta.stackoverflow.com/questions/382581/i-couldnt-submit-my-edit-on-an-answer-due-to-unformatted-code-yet-i-didnt-edi
Feb 27, 2019 at 10:45 history edited Neuron CC BY-SA 4.0
added meaningful texts as image alts
Jan 27, 2019 at 19:44 review Suggested edits
Jan 27, 2019 at 23:40
Sep 20, 2018 at 19:44 review Suggested edits
Sep 20, 2018 at 20:44
Sep 15, 2018 at 9:05 review Suggested edits
Sep 15, 2018 at 9:34
May 18, 2018 at 7:06 history rollback cs95
Rollback to Revision 27
May 13, 2018 at 3:21 history rollback ashleedawg
Rollback to Revision 12
Mar 24, 2018 at 0:13 history rollback cs95
Rollback to Revision 25
Feb 21, 2018 at 4:24 history edited whackamadoodle3000 CC BY-SA 3.0
added 1 character in body
Nov 2, 2017 at 14:15 history rollback cs95
Rollback to Revision 23
Oct 3, 2017 at 11:50 history bounty ended CommunityBot
Sep 21, 2017 at 3:31 review Suggested edits
Sep 21, 2017 at 7:03
Jul 26, 2017 at 17:39 history edited Johnny Bones CC BY-SA 3.0
added 6 characters in body
May 29, 2017 at 1:15 history bounty ended Baum mit Augen♦
Mar 8, 2017 at 0:55 history edited tbodt CC BY-SA 3.0
Add missing [
Feb 22, 2017 at 7:36 history edited Vikrant CC BY-SA 3.0
deleted 14 characters in body
Dec 20, 2016 at 3:59 history bounty ended RamenChef
Nov 2, 2016 at 1:14 history rollback duplode
Rollback to Revision 19
Oct 12, 2016 at 6:23 history edited Vikrant CC BY-SA 3.0
deleted 2 characters in body
Apr 25, 2016 at 0:31 history bounty ended TwoStraws
Mar 21, 2016 at 7:49 history edited gsamaras CC BY-SA 3.0
rolled back the edit.
Jan 31, 2016 at 3:12 review Suggested edits
Jan 31, 2016 at 5:25
Jan 28, 2016 at 20:56 history made wiki Post Made Community Wiki by George Stocker
Dec 30, 2015 at 4:15 history edited GAMITG CC BY-SA 3.0
added 4 characters in body
Dec 7, 2015 at 6:07 history edited TFD CC BY-SA 3.0
edited body
Jul 28, 2015 at 14:50 history bounty ended Oleksandr Pyrohov
Jun 20, 2015 at 5:18 history edited candied_orange CC BY-SA 3.0
Switch operator knows exactly where it will go. Doesn't yet know where it should go.
May 29, 2015 at 11:14 history edited gsamaras CC BY-SA 3.0
deleted 2 characters in body
Oct 9, 2014 at 18:18 history rollback Mysticial
Rollback to Revision 12
Oct 9, 2014 at 18:12 history edited Luke Willis CC BY-SA 3.0
The correct form of the word is Failure.
Jul 30, 2014 at 7:02 history bounty ended zessx
Jun 25, 2014 at 14:02 history bounty ended nicael
Apr 26, 2014 at 8:39 review Suggested edits
Apr 26, 2014 at 8:39
Mar 16, 2014 at 20:54 history edited Ilmari Karonen CC BY-SA 3.0
bare links are still kind of ugly, let's do it right this time; also, protocol-relative links FTW
Mar 15, 2014 at 4:37 history wiki removed BoltClock
Mar 15, 2014 at 4:09 history rollback BoltClock
Rollback to Revision 9
Dec 21, 2013 at 22:58 history bounty ended TLama
Dec 20, 2013 at 10:05 history edited Code Lღver CC BY-SA 3.0
added 30 characters in body
Nov 11, 2013 at 23:29 review Suggested edits
Nov 11, 2013 at 23:34
Oct 5, 2013 at 19:52 history bounty ended rebeliagamer
Sep 25, 2013 at 20:10 history edited canon CC BY-SA 3.0
deleted 1 characters in body
Jul 11, 2013 at 19:32 history bounty ended Ry-♦
Jun 26, 2013 at 0:34 review Suggested edits
Jun 26, 2013 at 0:45
Mar 18, 2013 at 8:42 history rollback Mysticial
Rollback to Revision 6
Mar 18, 2013 at 7:42 history edited Derek 朕會功夫 CC BY-SA 3.0
added 1 characters in body
Oct 10, 2012 at 18:48 review Suggested edits
Oct 10, 2012 at 18:49
Jul 31, 2012 at 10:11 review Suggested edits
Jul 31, 2012 at 10:12
Jul 1, 2012 at 22:16 history edited Mysticial CC BY-SA 3.0
Reduce the size of the image to 640 x 480. It was obnoxiously large before.
Jun 28, 2012 at 15:25 history edited Robert Harvey CC BY-SA 3.0
added 2 characters in body
Jun 28, 2012 at 12:20 history edited Matthew Flaschen CC BY-SA 3.0
better attribution
Jun 27, 2012 at 15:47 history edited Mysticial CC BY-SA 3.0
added 4048 characters in body; added 2 characters in body
Jun 27, 2012 at 14:07 history edited Mysticial CC BY-SA 3.0
added 1413 characters in body; added 109 characters in body
Jun 27, 2012 at 13:56 history answered Mysticial CC BY-SA 3.0
toggle format

Your privacy

By clicking “Accept all cookies”, you agree Stack Exchange can store cookies on your device and disclose information in accordance with our Cookie Policy.