3 ms·
> 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
by 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!
- staticassertion 6y agoOr a Vec<T> for storage and a Vec<usize> for tombstoning. Lots of ways to solve this, and my experience is that you can beat a linked list approach with the 'Vec plus Vec' approach for a lot of data sizes/ operations. Or a custom Vec that has a lower maximum bound, at which point you can start doing things like integer encoding/ pointer swizzling.