Timeline for Why is processing a sorted array faster than processing an unsorted array?
Current License: CC BY-SA 4.0
15 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Feb 27, 2019 at 10:58 | history | edited | Neuron | CC BY-SA 4.0 |
fixed column indentation
|
| Mar 16, 2018 at 12:51 | history | edited | Peter Mortensen | CC BY-SA 3.0 |
Active reading [<https://en.wiktionary.org/wiki/let%27s#Contraction>]
|
| Dec 23, 2016 at 22:32 | comment | added | Warren K | @MooingDuck : The diagram in Surt's answer below I think explains why TTFFTTFF is in fact the "pathological case" in Saqlain's example. | |
| Jul 26, 2016 at 4:33 | comment | added | Mooing Duck | @steveha: The Two-level adaptive predictor could lock onto the TTFFTTFF pattern with no issue whatsoever. "Variants of this prediction method are used in most modern microprocessors". Local branch prediction and Global branch prediction are based on a two level adaptive predictor, they can as well. "Global branch prediction is used in AMD processors, and in Intel Pentium M, Core, Core 2, and Silvermont-based Atom processors" Also add Agree predictor, Hybrid predictor, Prediction of indirect jumps, to that list. Loop predictor wont lock on, but hits 75%. That leaves only 2 that can't lock on | |
| Jul 26, 2016 at 3:49 | comment | added | steveha | @MooingDuck It is true that I am not an expert in processor design. But I invite you to read the Wikipedia page about branch predictors. Not one of the discussed designs could lock on to the pattern TTFFTTFF... and predict correctly. (Except maybe for the neural net one, with a sufficiently advanced neural net, and I'll bet you cash money that you don't own a computing device that has such a branch predictor in its processor.) en.wikipedia.org/wiki/Branch_predictor | |
| Jul 20, 2016 at 21:10 | comment | added | Mooing Duck | @steveha: I think you're making assumptions about how the CPU branch predictor works, and I disagree with that methodology. I don't know how advanced that branch predictor is, but I seem to think it's far more advanced than you do. You're probably right, but measurements would definitely be good. | |
| Jul 20, 2016 at 21:07 | comment | added | steveha | @MooingDuck To a human eye, "TTFFTTFFTTFF" is a predictable sequence, but what we are talking about here is the behavior of the branch predictor built into a CPU. The branch predictor is not AI-level pattern recognition; it's very simple. When you just alternate branches it doesn't predict well. In most code, branches go the same way almost all the time; consider a loop that executes a thousand times. The branch at the end of the loop goes back to the start of the loop 999 times, and then the thousandth time does something different. A very simple branch predictor works well, usually. | |
| Mar 28, 2016 at 18:27 | comment | added | Mooing Duck | @cst1992: Right now his slowest timing is TTFFTTFFTTFF, which seems, to my human eye, quite predictable. Random is inherently unpredictable, so it's entirely possible it would be slower still, and thus outside the limits shown here. OTOH, it could be that TTFFTTFF perfectly hits the pathological case. Can't tell, since he didn't show the timings for random. | |
| Mar 28, 2016 at 12:58 | comment | added | cst1992 | @MooingDuck 'Cause it won't make a difference - that value can be anything, but it still will be in the bounds of these thresholds. So why show a random value when you already know the limits? Although I agree that you could show one for the sake of completeness, and 'just for the heck of it'. | |
| 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 | ||
| Mar 22, 2013 at 12:20 | history | edited | Saqlain | CC BY-SA 3.0 |
added 711 characters in body
|
| S Feb 23, 2013 at 2:45 | history | suggested | Rathakrishnan | CC BY-SA 3.0 |
I just improved formatting
|
| Feb 23, 2013 at 2:34 | review | Suggested edits | |||
| S Feb 23, 2013 at 2:45 | |||||
| Feb 15, 2013 at 7:24 | history | answered | Saqlain | CC BY-SA 3.0 |