4 ms·
Re 1. (memory fragmentation): I'm sort of on board with this (although you probably make it worse for the next person if you use linked lists). But it'll be a v
by MauranKilom 6y ago
Re 1. (memory fragmentation): I'm sort of on board with this (although you probably make it worse for the next person if you use linked lists). But it'll be a very special case where the performance hit from working with a huge list will be acceptable.
Re 2. (threading): What happens when the list becomes empty? How do you keep track of the size to determine whether the list is empty? How do you know the size is still up-to-date when you go on to make a modification? I don't think this is as easy (even "in theory") as you make it sound.
Re 3. (merging overhead): You say "takes no extra memory", but you use significant extra memory already: You incur an additional two pointers of (and possibly per-allocation) overhead. For the entire lifetime of the list, not just when you do some operations.
If your elements are small, then your list might have double memory consumption the entire time instead of only when merging. And if they are large, you could store unique_ptrs to those elements in a vector. In which case the total memory overhead of merging two vectors (2 x total number of elements x pointer size) is exactly the same as a linked list has the entire time. And all the operations then turn into shuffling around pointers too, but probably fewer: You just have to move the unique_ptrs around, which is one pointer each instead of constantly unlinking and relinking lists.
Sure, sometimes iterator invalidation is a thing, and maybe keeping pointers to (separately allocated) elements doesn't cut it. But even then you wouldn't want to use a list if performance is even remotely a concern.
- gpderetta 6y agoTo fight fragmentation, a deque-like container is probably better anyway. Very good point on 3.
- MauranKilom 6y agoIndeed. I recently looked at using std::deque because I was exactly trying to avoid allocating too much contiguous memory, fearing fragmentation. Sadly, std::deque is pretty much useless. It uses something like page-sized blocks in one implementation, a few cachelines in another one (forgot which is gcc/clang), and on MSVC it allocates every single item separately (!!!) for element size > 1 word. And this will not be changed due to ABI compatibility. It might as well not exist in the standard.
- gpderetta 6y agoyes, I never use std::deque for the same reason. I believe that the deque in boost these days has a compile time configurable block size.
- lelanthran 6y ago> Re 2. (threading): What happens when the list becomes empty? How do you keep track of the size to determine whether the list is empty? How do you know the size is still up-to-date when you go on to make a modification? I don't think this is as easy (even "in theory") as you make it sound. No, it isn't easy. I used a single lock to lock both head and tail pointers, and did the pointer-swapping and pointer-comparisons for the pathological cases in that lock[1]. However, that being said, locking for the comparison and head/tail reassignment is *still* preferable to locking while reallocating your array. For counting items in the list, I post to a semaphore when an item is inserted, wait on the semaphore when an item is removed and simply return the semaphore count when a count of items is required. Because it is a linked list, there is no problem with having the count change in between retrieving it and adding/removing items - that'd only be a problem in array-like structures. If you want to code-review my implementation then be my guest (it's on github, under my name, a repo called libcmq). I welcome criticism :-) In any case, I've been considering reimplementing that library as a resizable array precisely because of the downsides of lists. I'm keeping it as it is (for now) because there are other things I want to do that aren't boring. [1] Empty list and list of exactly one element are problematic.