3 ms·
I know nothing about erlang, but if performance matters and you won't be deleting from the middle, an array-based implementation will usually be better than a l
by robmccoll 12y ago
I know nothing about erlang, but if performance matters and you won't be deleting from the middle, an array-based implementation will usually be better than a linked structure. Better alignment, less pointer chasing, fewer allocations and reallocations. Also the synchronization cost can be lower in a multi threaded context. Cost might be more memory allocated in some cases (but less in others and less fragmentation in your memory allocator's pool).
- JoeAltmaier 12y agoAn array would work, most of the time. The rest of the time, it'd be reallocating to extend the array, then copying. Which also has undesirable performance at unexpected times. Don't see it as any better.
- robmccoll 12y agoThat's almost true under the assumption that you are using the most elementary implementation possible with only a single array (insert at end of array, reallocate as needed to increase array length, copy elements down during dequeue, etc.) - you would still be avoiding the garbage collector relocating your array elements and generally get better performance due to nice alignment within cache lines in memory. With a more advanced implementation using multiple arrays, you can do even better (basically a blocked linked list), and you can cache the blocks as you dequeue and free up blocks to avoid hitting the memory allocator more than necessary. If you want to get really crazy with it, you can start doing blocks of multiple sizes that grow and shrink dynamically with the usage behavior of the list, but at that point what you have done is implement a memory allocator.