List vs Array

25, Nov, 2018
I was searching about performance differences of array vs list. I have found only some very populistic measurements - like removal of random element in list with random access (using linear search each time). This is somehow unrealistic usage for that structure. My need would be to frequently iterate over elements, and when something happen during the inspection of the item it will be deleted. Something like per frame game update. So, to compare more realistic usages, I have made simple
implementation and tests.

I made two implementations of list - one with custom allocator, one with malloc. I wanted to test simple unordered insertion (so at the end), iteration and deletion time (at any place). For deletion I have made additional optimized version for array which first marks elements to be removed and then remove them in one batch. Also I have tested cache coherent order vs cache unfriendly memory arrangement for the list nodes. So here are results:

List with malloc/free; time spend in list compared to array:

OP/#    4K      64K     256K      Items count
ADD     14.8    14.4    14.4      Simple insertion at the end.
ITER    3.42    3.54    2.56      Simple iteration over the items.
DEL     0.13    0.0091  0.0011    Delete each 8th element.
DEL*    2.67    1.77    1.62      Defered delete - mark each 8th element and delete at once.

List with custom allocator; time spend in list compared to array:

OP/#    4K      64K     256K        Items count
ADD     1.97    1.98    2.28        Simple insertion at the end.
ITER    5.46    3.96    1.76        Simple iteration over the items.
ITER*   27.87   39.69   38.26       Cache missed iteration over the items.
DEL     0.017   0.0022  0.00028     Delete each 8th element.
DEL*    0.36    0.365   0.49        Defered delete - mark each 8th element and delete at once.
So, it can be surely seen that list is slower for all except deletion. However, arrays may be faster in deletion if you use std allocator. Call to free() is significant. Insertion with malloc was about 14x time slower than array insertion at the end. However, with custom allocator it is not a case, and other times are not so bigger than array implementation. Then lists rocks at deletion. The iteration and insertion times are higher roughly 2x - as the memory consumption also is 2x higher. But it is crucial for iteration over list is to maintain good cache coherency in the allocator (the penalty is 20x compared to cache friendly access).

Another tests would be needed in concurrent environment. Maybe I will do it in future. There list may win as locks may be local not global (or even lock free or persistent approaches may be used). Also, one may test insertion in the middle - but this clearly changes nothing for list and for array will drop performance to deletion case.