2 ms·
Next week: linked lists? Linked lists have performance problems on computers. You need contiguous memory arrays for performance, since Direct Memory Access eng
by n00b101 13y ago
Next week: linked lists?
Linked lists have performance problems on computers. You need contiguous memory arrays for performance, since Direct Memory Access engines, caches, and pipelining all achieve peak performance only when memory is strictly accessed in contiguous chunks. How do functional language implementations deal with that problem?
- Fixnum 13y agoFor one thing, you generate as few as possible by aggressively fusing away intermediate lists (at least if your language is pure). Also, the garbage collector will often move lists into contiguous region(s) of memory. More to the point, though, sometimes a list is the appropriate data structure for a problem (like returning all intermediate results from the Collatz call, where you don't know how many there will be). Sure, you could use an array and double its size every now and then, but you're doing an awful lot of violence to your program just to handle something the runtime could take care of for you :) And yes, I know there will be a slight performance penalty under many circumstances.