7 ms·
Yeah, the article is weird about "But even this becomes cumbersome quickly, not to mention the overhead from reference counts." You pick the linked list becaus
by imtringued 6y ago
Yeah, the article is weird about "But even this becomes cumbersome quickly, not to mention the overhead from reference counts."
You pick the linked list because of better scalability as the data size grows bigger, you choose them precisely because you think the constant overhead vs contiguous lists is worth it.
The most common example is an object that wants to remove itself from a big list.
E.g. you have a OS with 10000 processes. 1000 processes die per second and they already know their position in the linked list so they remove themselves in O(1). An array would require leaving the slot empty and swapping in the last element (unordered list) O(1) or shifting entries to fill the gap (ordered list) O(n). The former breaks ordering, the latter leads to O(nm) removal costs where n is the number of live processes and m the number of dying processes. Paying reference counting costs is not a problem.
- IshKebab 6y agoA linked list is still a pretty terrible choice. You'd probably be better off with a Vec with tombstones and some kind of free list.
- titzer 6y agoIt really depends on what you are doing. If inserts into the middle are common, readjusting a vector gets really expensive.
- rmdashrfstar 6y agoTheoretically expensive, but modern hardware is optimized for this case. Random access lookups and cache misses from the linked list will tank performance, even in most cases where a linked list is theoretically equivalent or preferred.
- titzer 6y agoIf you have a long vector, say, 1000 elements, and you need to copy 500 of them to shift them over for an insert, you are going to be very slow compared to a linked list. Besides, linked lists aren't that bad if the nodes are close enough in memory (read: consecutive), or they are hot enough to be in already in cache. But as always, measure instead of guessing.
- masklinn 6y ago> If you have a long vector, say, 1000 elements, and you need to copy 500 of them to shift them over for an insert, you are going to be very slow compared to a linked list. FWIW the original suggestion mentioned tombstoning so you'd have a Vec<Option<T>> instead of a `Vec<T>`, and "removing" an item would just set the `Option` to `None`. Of course this would increase iteration cost (as you'd have to skip the `None`), and you'd probably want to compact the vec once in a while.
- mousepilot 6y agoI probably shouldn't even be in this thread but isn't that creeping back toward garbage collection?
- staticassertion 6y agoSure, it's just a mark and sweep, but manually implemented (which is fine).
- masklinn 6y agoIt’s completely normal to have this sort of things in low-level code bases. Both C++ and Rust have refcounting smart pointers in their standard libraries, and bespoke refcounting schemes are regular occurrences in C codebases (the Linux kernel has tons of refcounting, so much so that it has a utility file for reference counters: https://github.com/torvalds/linux/blob/master/include/linux/refcount.h https://github.com/torvalds/linux/blob/master/include/linux/...)
- mousepilot 6y agothanks for the response! I'm a big fan of doubly linked lists, so it was interesting to see that there was extra work to get them going. I'm certainly going to read up on this "ownership" thing. I get the impression that its there for really good reasons, and I'm not going to argue with experts who are protecting users. I have a question for you, would you say that the increase of difficulties with doubly linked lists are incidental in nature, or is there something inherent with doubly linked lists that impact security? Like I said, I like the doubly linked lists for certain things, and the more I know about the impact of using them the better! I certainly will be reading up on this!
- volta83 6y agoNobody here is talking about vectors of integers. From the first post, this is all assuming that the objects in the vector are "big". A modern CPU has 200Gb/s of bandwidth. If the objects in your array are 200 Gb in size each, then swapping the position of two elements in a vector is going to take O(seconds) at memcpy speeds, while doing this with a linked list is going to take ~1 * 10^(-11) seconds. That's a performance difference of 11 orders of magnitude... You can make the objects in the array smaller (e.g. 200Mb each instead of 200Gb each) and your two-element swap would still be 10^8 times faster with a doubly linked list. --- In the parallel threads, people seem to just be arguing that a vector is always faster than a list, without understanding "why" this is the case, and making claims about "what the hardware does" without doing basic rule-of-thumb calculations to verify their claims.
- myrrlyn 6y agothe good news is that a vector of any object can be reduced to a vector of integers by `Box`ing, and then you only incur a miss when you access the data, but not during every step you take to find the data
- kd5bjo 6y ago> A modern CPU has 200Gb/s of bandwidth. If the objects in your array are 200 Gb in size each, then swapping the position of two elements in a vector is going to take O(seconds) at memcpy speeds, Not necessarily. If those items are aligned to a memory-page boundary, memcpy will probably do a page table update instead of actually moving the values in RAM.
- kllrnohj 6y agoIf objects know where they are, why do you need sorted ordering? If you need sorted ordering, it sounds like you're (regularly!) iterating over it. But iterating over a linked list is incredibly slow. This is where Big-O just really doesn't have a strong relationship with performance. Iterating over a linked-list is O(N), same as a vec. But in the real world it's nowhere close to as fast. So then if you're not regularly iterating over it a bag implemented with a vec is likely a better option. Then just have a bool that tracks if it's sorted or not, and in the (relatively) rare case you need sorted traversal just sort() it first.
- xigoi 6y agoOrdered is not the same thing as sorted. If you do swap-removals, there's no way to sort the array back into the original order unless you also keep track of insertion time, which adds memory overhead.
- kllrnohj 6y agoStoring pointers in a linked list also adds memory overhead, too. Insertion time in nanoseconds is only 8 bytes - same as a single pointer on 64-bits. So half the memory usage as a doubly linked list.
- josephg 6y agoYou can get the best of both worlds - fast iteration and fast insert speed - by using a tree. Essentially use a b-tree as a list, and in internal nodes count the number of items contained in each child. Inserts traverse down the tree to find the insert position, insert there and then traverse back up the tree updating indexes. Each leaf should contain a small array of items, and when inserting you can memmove the existing items to to make space. Tuning the size of that array lets you balance the cost of memcpy vs the cost of pointer indirection & allocations on insert. The whole construction ends up extremely efficient in practice for this kind of thing, since you get log(n) indexed lookup and log(n) insert time. I don’t know why they aren’t used more.
- kllrnohj 6y ago