Yeah, we should teach this to undergrads. If you want high performance for a dynamic list, you end up making a lot of tradeoffs with tricks like: - Use blocks

Yeah, we should teach this to undergrads. If you want high performance for a dynamic list, you end up making a lot of tradeoffs with tricks like: - Use blocks of multiple elements per actual list element that fit your cache line size. Blocks also have the benefit of potentially allowing SIMD processing of your data. - Allocate blocks out of a vector or some other structure that reduces your actual number of allocation calls. Maintain a free list threaded through this vector. - Tombstone list elements in their blocks on removal instead of repacking the entire list. This allows for fast deletions and fast insertions at specific locations (in that you can always insert a new block between existing blocks containing only a single element or get lucky and re-use a tombstoned slot). Note that most of these optimizations trade some memory efficiency for speed. This is a common theme in optimization. Using more memory, but using it more intelligently such that you are potentially accessing less of it and accessing it sequentially where possible.