Hacker News new | past | comments | ask | show | jobs | submit login
Why Data Structures Matter (joelneely.wordpress.com)
72 points by gnosis on Jan 7, 2012 | hide | past | favorite | 8 comments



Previously, 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-Program...


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.


Is Fortress dead?


Sorry for jumping on this late, it is not dead. http://projectfortress.java.net/


No, as far as I know its just not funded any more, there is still open source development on the way.


What is the word splitting task mentioned here?


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) ).


Who said they didn't?




Consider applying for YC's Spring batch! Applications are open till Feb 11.

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: