While writing `alloc` should require `T: !Drop` or be `unsafe` · Issue #251 · fitzgen/bumpalo · GitHub, it occurred to me that the LinkedList<*mut dyn Any> droppables I was describing would sometimes contain millions of entries, and that since it really only needs to be iterated in LIFO order, using a singly-linked rather than doubly-linked list of n allocated objects would reduce the space needed from 3 * n * size_of::<usize>() to 2 * n * size_of::<usize>() + O(1). Having to iterate in only one direction would also make it easier to reduce the amortized overhead further by creating a type that wrapped a LinkedStack<[NonNull<*mut dyn Any>; N]> instead; then it would only be (1 + 1/N) * n * size_of::<usize>() + O(1). (Using a Vec or VecDeque would mean we couldn't use the Bump's own space for allocation once the slab size was exceeded.) Could we please have singly-linked implementations of LinkedStack and LinkedQueue?
One thing I'm missing is, why should those go into stdlib, rather than a crate? It's an approach that works well for e.g. dashmap, which is another datastructure crate.
Aside from that, linked lists are relatively rare these days, as they tend to not be too CPU cache friendly. That makes the case for putting them in a crate stronger, and the case for putting them in stdlib weaker, I'd say.
As a side note I don't get the linked issue. Leaking memory and not running the destructor is perfectly safe in Rust (see std::mem::forget for example).
it is safe in the rust sense, yes, but that doesn't mean it is a good idea, especially for generic datastructures.
std::fs::remove_dir_all("/") is also "safe", but it is definitely not a good idea.
And more to the point, so is calling it on one thread and launching std::process::exit() on another thread. But I think it fits Rust's general philosophy better if it's, in general, easier to prevent resource leaks and unfinished external operations whenever possible than not to.
I would be very surprised to see such types in alloc, since even LinkedList is generally discouraged and probably only exists out of pre-1.0 inertia.
Especially since if all you need is a linked stack, then doing that yourself works fine in safe code in a couple dozen lines: https://rust-unofficial.github.io/too-many-lists/first-final.html.
This topic was automatically closed 90 days after the last reply. New replies are no longer allowed.