4 ms·

There are certain styles of programming and data structure implementations that end up requiring you to fight Rust at almost every step. Things like intrusive d

by biorach 10mo ago

There are certain styles of programming and data structure implementations that end up requiring you to fight Rust at almost every step. Things like intrusive data structures, pointer manipulation and so on. Famously there is an entire book online on how to write a performant linked list in idiomatic Rust - something that is considered straightforward in C. For these cases you could always use Zig instead of C

ViewTrick1002 10mo ago
Or just build a tested unsafe implementation as a library. For example the Linked List in the standard library. https://doc.rust-lang.org/src/alloc/collections/linked_list.rs.html#481 https://doc.rust-lang.org/src/alloc/collections/linked_list....
- mjlawson 10mo ago
  I think that misses the point though. C trusts you to design your own linked list. It also trusts your neighbor, your kid, your LLM, you, your dog, another linked list...
- biorach 10mo ago
  Yeah, if you need a linked list (you probably don't) use that. If however you are one of the very small number of people who need fine-grained control over a tailored data-structure with internal cross-references or whatnot then you may find yourself in a world where Rust really does not believe that you know what you are doing and fights you every step of the way. If you actually do know what you are doing, then Zig is probably the best modern choice. The TigerBeetle people chose Zig for these reasons, various resources on the net explain their motivations.
  - ViewTrick1002 10mo ago
    The point with the linked list is that it is perfectly valid to use unsafe to design said ”tailored data structure with internal cross-reference or what not” library and then expose a safe interface. If you’re having trouble designing a safe interface for your collection then that should be a signal that maybe what you are doing will result in UB when looked at the wrong way. That is how all standard library collections in Rust works. They’ve just gone to the length of formally verifying parts of the code to ensure performance and safety.
    - eru 10mo ago
      > If you’re having trouble designing a safe interface for your collection then that should be a signal that maybe what you are doing will result in UB when looked at the wrong way. Rust is great, but there are some things that are safe (and you could prove them safe in the abstract), but that you can't easily express in Rust's type system. More specifically, there are some some things and usage pattern of these things that are safe when taken together. But the library can't force the safe usage pattern on the client, with the tools that Rust provides.
      - ViewTrick1002 10mo ago
        If you can't create a safe interface and must have the function then create an unsafe function and clearly document the invariants and then rely on the user to uphold them? Take a look at the unsafe functions for the standard library Vec type to see examples of this: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.from_raw_parts https://doc.rust-lang.org/std/vec/struct.Vec.html#method.fro...
        eru 10mo ago
        > If you can't create a safe interface and must have the function then create an unsafe function and clearly document the invariants and then rely on the user to uphold them? Yes, that's what you do in practice. But it's no different--in principle--from the approach C programmers have to use.
    - bluecalm 10mo ago
      >>That is how all standard library collections in Rust works Yeah and that's what not going to work for high performance data structures because you need to embed hooks into the objects - not just put objects into a bigger collection object. Once you think in terms of a collection that contains things you have already lost that specific battle. Another thing that doesn't work very well in Rust (from my understanding, I tried it very briefly) is using multiple memory allocators which is also needed in high performance code. Zig takes care to make it easy and explicit.
arbitrandomuser 10mo ago
what is an intrusive data structure?
- ajuc 10mo ago
  A data structure that requires you to change the data to use it. Like a linked list that forces you to add a next pointer to the record you want to store in it.
- ahartmetz 10mo ago
  A container class that needs cooperation from the contained items, usually with special data fields. For example, a doubly linked list where the forward and back pointers are regular member variables of the contained items. Intrusive containers can avoid memory allocations (which can be a correctness issue in a kernel) and go well with C's lack of built-in container classes. They are somewhat common in C and very rare in C++ and Rust.
  - eru 10mo ago
    At least for a double linked list you can probably get pretty far in terms of performance in the non-intrusive case, if your compiler unboxes the contained item into your nodes? Or are there benefits left in intrusive data structures that this doesn't capture?
    - dzaima 10mo ago
      Storing the data in nodes doesn't work if the given structure may need to be in multiple linked lists, which iirc was a concern for the kernel? And generally I'd imagine it's quite a weird form for data structures for which being in a linked list isn't a core aspect (no clue what specifically the kernel uses, but I could imagine situations where where objects aren't in any linked list for 99% of time, but must be able to be chained in even if there are 0 bytes of free RAM ("Error: cannot free memory because memory is full" is probably not a thing you'd ever want to see)).
      - 10mo ago
wiz21c 10mo ago
it is not straightforward in rust because the linked list is inherently tricky to implement correctly. Rust makes that very apparent (and, yeah, a bit too apparent). I know, a linked list is not exactly super complex and rust makes that a bit tough. But the realisation one must have is this: building a linked list will break some key assumptions about memory safety, so trying to force that into rust is just not gonna make it. Problem is I guess that for several of us, we have forgotten about memory safety and it's a bit painful to have that remembered to us by a compiler :-)
- delamon 10mo ago
  Can you elaborate, what key assumptions about memory safety linked lists break? Sure, double linked lists may have non-trivial ownership, but that doesn't compromise safety.
  - estebank 10mo ago
    Rust wants all memory to be modeled as an ownership tree: the same bit of memory can't be owned by more than one data structure. A doubly linked list breaks that requirement so it can't be modeled in safe Rust directly. The options are using unsafe, or using one of the pointer wrapper types that have runtime checks that ensure correct behavior and own the underlying memory as far Rust is concerned.
    - zozbot234 10mo ago
      You can do it by combining ghostcell/qcell along with some bespoke "static/compile-time reference counting" for the double links part. But ghostcell/qcell is quite difficult to use with Rust's current feature set (it has to use lifetime hacks to place a safe "brand" on type instantiations, a kind of quasi-capability construct), so it hasn't become a part of standard rust so far.
    - delamon 10mo ago
      Right. So it is not that double-linked lists are inherently unsafe, it is (just) Rust ownership model cannot represent them (any other cyclic structures).
pjmlp 10mo ago
Given Zig's approach to safety, you can get the same in C with static and runtime analysis tools, that many devs keep ignoring. Already setting the proper defaults on a Makefile would get many people half way there, without changing to language yet to be 1.0, and no use-after-free story.
- metaltyphoon 10mo ago
  > many devs keep ignoring And thats why Zig don’t offer much. Devs will just ignore it.
yencabulator 10mo ago
Sure. Now import a useful performant B+tree in C from a reusable library, while enforcing type safety for your keys and values. Lots of things C chose to use intrusive pointers and custom data structures for, you would program very differently in a different language. I'm an old C neckbeard and I find Rust a great experience. Some of the arguments against it sound like people are complaining about how hard it is to run pushing a bicycle.

by biorach 10mo ago

ViewTrick1002 10mo ago

Or just build a tested unsafe implementation as a library. For example the Linked List in the standard library. https://doc.rust-lang.org/src/alloc/collections/linked_list.rs.html#481 https://doc.rust-lang.org/src/alloc/collections/linked_list....

mjlawson 10mo ago
I think that misses the point though. C trusts you to design your own linked list. It also trusts your neighbor, your kid, your LLM, you, your dog, another linked list...
biorach 10mo ago
Yeah, if you need a linked list (you probably don't) use that. If however you are one of the very small number of people who need fine-grained control over a tailored data-structure with internal cross-references or whatnot then you may find yourself in a world where Rust really does not believe that you know what you are doing and fights you every step of the way. If you actually do know what you are doing, then Zig is probably the best modern choice. The TigerBeetle people chose Zig for these reasons, various resources on the net explain their motivations.
- ViewTrick1002 10mo ago
  The point with the linked list is that it is perfectly valid to use unsafe to design said ”tailored data structure with internal cross-reference or what not” library and then expose a safe interface. If you’re having trouble designing a safe interface for your collection then that should be a signal that maybe what you are doing will result in UB when looked at the wrong way. That is how all standard library collections in Rust works. They’ve just gone to the length of formally verifying parts of the code to ensure performance and safety.
  - eru 10mo ago
    > If you’re having trouble designing a safe interface for your collection then that should be a signal that maybe what you are doing will result in UB when looked at the wrong way. Rust is great, but there are some things that are safe (and you could prove them safe in the abstract), but that you can't easily express in Rust's type system. More specifically, there are some some things and usage pattern of these things that are safe when taken together. But the library can't force the safe usage pattern on the client, with the tools that Rust provides.
    - ViewTrick1002 10mo ago
      If you can't create a safe interface and must have the function then create an unsafe function and clearly document the invariants and then rely on the user to uphold them? Take a look at the unsafe functions for the standard library Vec type to see examples of this: https://doc.rust-lang.org/std/vec/struct.Vec.html#method.from_raw_parts https://doc.rust-lang.org/std/vec/struct.Vec.html#method.fro...
      - eru 10mo ago
        > If you can't create a safe interface and must have the function then create an unsafe function and clearly document the invariants and then rely on the user to uphold them? Yes, that's what you do in practice. But it's no different--in principle--from the approach C programmers have to use.
  - bluecalm 10mo ago
    >>That is how all standard library collections in Rust works Yeah and that's what not going to work for high performance data structures because you need to embed hooks into the objects - not just put objects into a bigger collection object. Once you think in terms of a collection that contains things you have already lost that specific battle. Another thing that doesn't work very well in Rust (from my understanding, I tried it very briefly) is using multiple memory allocators which is also needed in high performance code. Zig takes care to make it easy and explicit.

arbitrandomuser 10mo ago

what is an intrusive data structure?

ajuc 10mo ago
A data structure that requires you to change the data to use it. Like a linked list that forces you to add a next pointer to the record you want to store in it.
ahartmetz 10mo ago
A container class that needs cooperation from the contained items, usually with special data fields. For example, a doubly linked list where the forward and back pointers are regular member variables of the contained items. Intrusive containers can avoid memory allocations (which can be a correctness issue in a kernel) and go well with C's lack of built-in container classes. They are somewhat common in C and very rare in C++ and Rust.
- eru 10mo ago
  At least for a double linked list you can probably get pretty far in terms of performance in the non-intrusive case, if your compiler unboxes the contained item into your nodes? Or are there benefits left in intrusive data structures that this doesn't capture?
  - dzaima 10mo ago
    Storing the data in nodes doesn't work if the given structure may need to be in multiple linked lists, which iirc was a concern for the kernel? And generally I'd imagine it's quite a weird form for data structures for which being in a linked list isn't a core aspect (no clue what specifically the kernel uses, but I could imagine situations where where objects aren't in any linked list for 99% of time, but must be able to be chained in even if there are 0 bytes of free RAM ("Error: cannot free memory because memory is full" is probably not a thing you'd ever want to see)).
    - 10mo ago

wiz21c 10mo ago

it is not straightforward in rust because the linked list is inherently tricky to implement correctly. Rust makes that very apparent (and, yeah, a bit too apparent). I know, a linked list is not exactly super complex and rust makes that a bit tough. But the realisation one must have is this: building a linked list will break some key assumptions about memory safety, so trying to force that into rust is just not gonna make it. Problem is I guess that for several of us, we have forgotten about memory safety and it's a bit painful to have that remembered to us by a compiler :-)

delamon 10mo ago
Can you elaborate, what key assumptions about memory safety linked lists break? Sure, double linked lists may have non-trivial ownership, but that doesn't compromise safety.
- estebank 10mo ago
  Rust wants all memory to be modeled as an ownership tree: the same bit of memory can't be owned by more than one data structure. A doubly linked list breaks that requirement so it can't be modeled in safe Rust directly. The options are using unsafe, or using one of the pointer wrapper types that have runtime checks that ensure correct behavior and own the underlying memory as far Rust is concerned.
  - zozbot234 10mo ago
    You can do it by combining ghostcell/qcell along with some bespoke "static/compile-time reference counting" for the double links part. But ghostcell/qcell is quite difficult to use with Rust's current feature set (it has to use lifetime hacks to place a safe "brand" on type instantiations, a kind of quasi-capability construct), so it hasn't become a part of standard rust so far.
  - delamon 10mo ago
    Right. So it is not that double-linked lists are inherently unsafe, it is (just) Rust ownership model cannot represent them (any other cyclic structures).

pjmlp 10mo ago

Given Zig's approach to safety, you can get the same in C with static and runtime analysis tools, that many devs keep ignoring. Already setting the proper defaults on a Makefile would get many people half way there, without changing to language yet to be 1.0, and no use-after-free story.

metaltyphoon 10mo ago
> many devs keep ignoring And thats why Zig don’t offer much. Devs will just ignore it.

yencabulator 10mo ago

Sure. Now import a useful performant B+tree in C from a reusable library, while enforcing type safety for your keys and values. Lots of things C chose to use intrusive pointers and custom data structures for, you would program very differently in a different language. I'm an old C neckbeard and I find Rust a great experience. Some of the arguments against it sound like people are complaining about how hard it is to run pushing a bicycle.