4 ms·
Why Data Structures Matter
- spacemanaki 15y agoPreviously, http://news.ycombinator.com/item?id=2294202 http://news.ycombinator.com/item?id=2294202 More specifically, someone hunted down what I think is the Guy Steele talk mentioned in the OP: http://www.infoq.com/presentations/Thinking-Parallel-Programming http://www.infoq.com/presentations/Thinking-Parallel-Program...
- peregrine 15y agoGreat 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.
- durandal1 15y agoWho said they didn't?
- orborde 15y agoWhat is the word splitting task mentioned here?
- lurker14 15y agoNot 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) ).