Why Data Structures Matter

Great talk. I feel like he spent the first 18 minutes talking about his crappy ASM code just because he did all that work and wanted to present it.

Not sure, but for the article's sake, "word splitting" is only relevant as it involves (singly-linked) list concatenation as a performance bottleneck. List concatentation is efficient when the first list is short (ideally length=1), which is to say, a right fold that builds a list by a series of prepend operations.

Of course, that analysis is a little weird, because if our goal is to accumulate a large sequence (O(1) to get head, O(n) full traversal) as fast as possible, you shouldn't use a linked list at all. You should use something like a Finger Tree, whose construction is parallelizable (that is merging two size-n sublists is O(log n), not linked list's O(n) ).