List vs Array
25, Nov, 2018implementation 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.
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.
- Posted by michal in
- Add a comment