<story><title>Why is processing a sorted array faster than an unsorted array?</title><url>http://stackoverflow.com/q/11227809/399268</url></story><parent_chain></parent_chain><comment><author>rayiner</author><text>Modern architectures really are quite complex, and it&apos;s important to keep your internal machine model up to date with what&apos;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&apos;s didn&apos;t try to predict the target address of the branch. Today, CPU&apos;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.&lt;p&gt;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&apos;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.</text></comment>
<story><title>Why is processing a sorted array faster than an unsorted array?</title><url>http://stackoverflow.com/q/11227809/399268</url></story><parent_chain></parent_chain><comment><author>Bakkot</author><text>Several months old, but still worth a read - especially for the end of Mystical&apos;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.</text></comment>