I have mixed feelings about this.<p>In principle, I applaud the initiative to put the sacred theories given from above to the test. We need more of this and much earlier. Every CS 101 course should be presenting something similar.<p>On the other hand, what where this guys expecting? They are testing a LinkedList(TM) for goodness sake!!! Even if you assume hardware that follows the abstract theoretical machine of the C standard to the letter, all the toying around with pointers should be a good predictor that things are going to be <i>slow</i> regardless of what Complexity Theory says. <i>And</i>, speaking of Complexity Theory, with the samples sizes they were using, all the Big Oh analysis does not apply. The limits of the equations are irrelevant, the one with the lowest fixed cost wins!<p>So, I find extremelly annoying all that mumbo-jumbo about how the so called complexity of software and the processor caches, etc, make analysis impossible. It is not that difficult; the guy who does not overthink stuff and packs everything close enough to cause the least cache misses wins (and the idiot that needlessly spreads data around and uses indirection everywhere looses).<p>I follow up article that compares slight variants of the same data structure to take advantage of modern hardware would provide great insights!!!