<story><title>Drop millions of allocations by using a linked list (2015)</title><url>https://github.com/rubygems/rubygems/pull/1188</url></story><parent_chain></parent_chain><comment><author>rsp1984</author><text>Lessons from high-performance &amp;#x2F; embedded development: If you know the size of your data beforehand, or can at least put a bound on it, it&amp;#x27;s best to pre-allocate your memory and then hand out bits as needed through a custom allocator working on the pre-allocated set. That way you have only a single allocation and all your data is contiguous in memory (huge deal for cache coherency and therefore speed of access). Very easy to put a vector&amp;#x2F;ArrayList -type interface on top of this.&lt;p&gt;If you don&amp;#x27;t know the size or bound, then do the next best thing and pre-allocate in chunks and use a slightly more sophisticated allocator that manages the chunks to hand out bits.&lt;p&gt;Not sure what mechanisms high-level languages use these days and whether there&amp;#x27;s any pre-allocation involved under the hood, but plain unoptimized linked lists can fragment your memory pretty badly and they also aren&amp;#x27;t cache coherent. Use them to store small #s of large objects, instead of large #s of small objects.</text></comment>
<story><title>Drop millions of allocations by using a linked list (2015)</title><url>https://github.com/rubygems/rubygems/pull/1188</url></story><parent_chain></parent_chain><comment><author>naranha</author><text>Unrelated to the article, but perhaps an interesting fact: as a Java programmer you perhaps know that using the class java.util.LinkedList is almost always worse in than using plain arrays or ArrayList. Even though there are much less allocations, the overhead for maintaining the linked list data structures is immense. And it turns out that computers are pretty fast at allocating memory.&lt;p&gt;But there more optimized implementations of linked lists of course (probably using arrays as well internally (?)).</text></comment>