3 ms·

> What unsafe APIs would you like to see? Well, here’s a simple example I’ve wrote above: “Some container that keeps some items + a linked list to track and ev

> What unsafe APIs would you like to see? Well, here’s a simple example I’ve wrote above: “Some container that keeps some items + a linked list to track and evict the least recently used item from that container”. You know, LRU caches are everywhere. I remember in C++, I recently wrote something similar in three completely unrelated projects. Well, a linked list alone isn’t usually enough, but a linked list + unordered map that maps elements to list iterators do the job very well. To update the LRU order, I query the hashmap and get a list position, then I move that element to the list’s tail. And when I need to evict an element, I grab the list’s head and evict those. Note the following good things about this C++ solution: (1) All those operations (hashmap lookup, linked list reorder, linked list remove head) are O(1), i.e. I can have millions items in my cache, and still update my LRU order for practically no cost (a few pointer writes). (2) I didn’t wrote much code, only creatively combined what was already here in the C++ standard library. Now Rust. The safety means pointers to list nodes aren’t part of the list’s API. And without raw pointers, linked lists are nearly useless, because we can’t split or reorder them efficiently. If you’ll read the documentation for LinkedList<T>::split_off, you’ll find the complexity is O(n), while for most other languages, linked lists are famous for being able to do that for O(1). I’m not sure any efficient linked list API is possible within Rust memory management model, safe or unsafe.

kibwen 10y ago
> The safety means pointers to list nodes aren’t part of the list’s > API. A quick glance at LinkedList leads me to believe that there's no technical reason why we couldn't support a `split_at_node` function that takes a raw pointer to a list node (along with additional APIs that actually return raw pointers to list nodes, which themselves wouldn't need to be unsafe). And even if my intuition is wrong and there's some reason why the implementation of LinkedList in the standard library can't do this for some reason, I see no additional reason why some other implementation of linked lists couldn't do this. (The standard library implementation likely optimizes for convenience rather than power, given that our data structures guru has a complicated relationship with linked lists: http://cglab.ca/~abeinges/blah/too-many-lists/book/README.html#an-obligatory-public-service-announcement http://cglab.ca/~abeinges/blah/too-many-lists/book/README.ht... ). The fact that Rust doesn't favor these sorts of things hasn't stopped others from going ahead and writing implementations anyway: https://crates.io/search?q=intrusive https://crates.io/search?q=intrusive > I didn’t wrote much code, only creatively combined what > was already here in the C++ standard library. Rust definitely enjoys supporting this use case (heck, the stdlib even does it: http://doc.rust-lang.org/src/std/up/src/libstd/collections/hash/set.rs.html#105-107 http://doc.rust-lang.org/src/std/up/src/libstd/collections/h... ), but when it falls down please feel free to check to see if others have preceded you in scratching your itch: https://crates.io/search?q=lru https://crates.io/search?q=lru > I’m not sure any efficient linked list API is possible > within Rust memory management model, safe or unsafe. I'm still unsure what you're implying here, given that, again, unsafe code can use raw pointers willy-nilly (though as we've established, using the stdlib to compose data structures via raw pointers isn't always convenient).
- Const-me 10y ago
  > there's no technical reason why we couldn't support a `split_at_node` function that takes a raw pointer to a list node How about rust memory management model? When I split linked list in two, the new list must somehow become the owner of the newly detached elements. For both unmanaged and garbage-collected languages there’s a heap (garbage collected or not) that’s shared across all threads of the process. List nodes are freed either explicitly with delete/free, or implicitly with GC. Rust memory managed model forces to transfer the ownership when the list is split. AFAIK that’s exactly what happens inside split_off, and that operation is O(n). > unsafe code can use raw pointers willy-nilly If so, why the implementation of LinkedList<T> doesn’t? You know, O(1) and O(n) is a big difference.
  - Manishearth 10y ago
    > If so, why the implementation of LinkedList<T> doesn’t? Because the stdlib doesn't want to expose too many unsafe APIs on its datastructures, giving it freedom to evolve the internals. And LinkedLists are considered a niche type anyway, not for general use. As kibwen mentioned, you are free to create your own linkedlist implementation that exposes this API. Rust has a heap, and you can free things directly if you need.
    - Const-me 10y ago
      Let’s summarize. I want to implement efficient LRU cache data structure. In C++, I don’t need to spend time implementing and debugging my own linked lists, because standard library implementation already good enough for the task. I only need to encapsulate two standard containers together, and write a pair of methods to add/remove stuff. In Rust, I need to roll out my own lists, because stdlib doesn't want to expose too many unsafe APIs on its data structures. You agree with all of the above? If yes, hope now you see how Rust isn’t good enough for creating complex specialized data structures.
      - Manishearth 10y ago
        That's a non sequitur. The choice made by thee stdlib to not support many linked list operations (there probably are crates in the ecosystem for this anyway) does not imply Rust is unsuitable for complex specialized datastructures. It implies that Rust has opinions about what should and shouldn't be in the stdlib. In fact, you said it yourself, "specialized". Since linkedlists are generally used in specific cases with different required ergonomics, you do not want to expose a catch-all.

kibwen 10y ago

> The safety means pointers to list nodes aren’t part of the list’s > API. A quick glance at LinkedList leads me to believe that there's no technical reason why we couldn't support a `split_at_node` function that takes a raw pointer to a list node (along with additional APIs that actually return raw pointers to list nodes, which themselves wouldn't need to be unsafe). And even if my intuition is wrong and there's some reason why the implementation of LinkedList in the standard library can't do this for some reason, I see no additional reason why some other implementation of linked lists couldn't do this. (The standard library implementation likely optimizes for convenience rather than power, given that our data structures guru has a complicated relationship with linked lists: http://cglab.ca/~abeinges/blah/too-many-lists/book/README.html#an-obligatory-public-service-announcement http://cglab.ca/~abeinges/blah/too-many-lists/book/README.ht... ). The fact that Rust doesn't favor these sorts of things hasn't stopped others from going ahead and writing implementations anyway: https://crates.io/search?q=intrusive https://crates.io/search?q=intrusive > I didn’t wrote much code, only creatively combined what > was already here in the C++ standard library. Rust definitely enjoys supporting this use case (heck, the stdlib even does it: http://doc.rust-lang.org/src/std/up/src/libstd/collections/hash/set.rs.html#105-107 http://doc.rust-lang.org/src/std/up/src/libstd/collections/h... ), but when it falls down please feel free to check to see if others have preceded you in scratching your itch: https://crates.io/search?q=lru https://crates.io/search?q=lru > I’m not sure any efficient linked list API is possible > within Rust memory management model, safe or unsafe. I'm still unsure what you're implying here, given that, again, unsafe code can use raw pointers willy-nilly (though as we've established, using the stdlib to compose data structures via raw pointers isn't always convenient).

Const-me 10y ago
> there's no technical reason why we couldn't support a `split_at_node` function that takes a raw pointer to a list node How about rust memory management model? When I split linked list in two, the new list must somehow become the owner of the newly detached elements. For both unmanaged and garbage-collected languages there’s a heap (garbage collected or not) that’s shared across all threads of the process. List nodes are freed either explicitly with delete/free, or implicitly with GC. Rust memory managed model forces to transfer the ownership when the list is split. AFAIK that’s exactly what happens inside split_off, and that operation is O(n). > unsafe code can use raw pointers willy-nilly If so, why the implementation of LinkedList<T> doesn’t? You know, O(1) and O(n) is a big difference.
- Manishearth 10y ago
  > If so, why the implementation of LinkedList<T> doesn’t? Because the stdlib doesn't want to expose too many unsafe APIs on its datastructures, giving it freedom to evolve the internals. And LinkedLists are considered a niche type anyway, not for general use. As kibwen mentioned, you are free to create your own linkedlist implementation that exposes this API. Rust has a heap, and you can free things directly if you need.
  - Const-me 10y ago
    Let’s summarize. I want to implement efficient LRU cache data structure. In C++, I don’t need to spend time implementing and debugging my own linked lists, because standard library implementation already good enough for the task. I only need to encapsulate two standard containers together, and write a pair of methods to add/remove stuff. In Rust, I need to roll out my own lists, because stdlib doesn't want to expose too many unsafe APIs on its data structures. You agree with all of the above? If yes, hope now you see how Rust isn’t good enough for creating complex specialized data structures.
    - Manishearth 10y ago
      That's a non sequitur. The choice made by thee stdlib to not support many linked list operations (there probably are crates in the ecosystem for this anyway) does not imply Rust is unsuitable for complex specialized datastructures. It implies that Rust has opinions about what should and shouldn't be in the stdlib. In fact, you said it yourself, "specialized". Since linkedlists are generally used in specific cases with different required ergonomics, you do not want to expose a catch-all.