10 ms·

Crossbeam makes lock-free data structures easier to write than in any other mainstream language I know of. Regarding graphs, just use indices and vectors. It's

Crossbeam makes lock-free data structures easier to write than in any other mainstream language I know of. Regarding graphs, just use indices and vectors. It's often better to use indices for graph nodes anyway, for example in games, where an ECS design using IDs is generally preferable to direct references to objects. For a while, I was kind of obsessed with showing that Rust could do doubly linked trees and graphs just as well as C++ could. I now realize that this was a mistake, and I made a big mess of a lot of code in the process. Having a single owner and using IDs for "secondary" references is often preferable even in languages that easily allow multiple strong references to objects. In the small, direct references and an OO style can be convenient, but in the large, you often want to break up your graph code into components and systems anyway, and it's kind of nice to have the language push you to front loading that kind of design.

ecnahc515 8y ago
Crossbeam is awesome. That said; I think his point is more on the "how hard is it to write a crossbeam-like library in Rust compared to a language with a GC".
- ridiculous_fish 8y ago
  From crossbeam docs [1]: "Programming languages that come with garbage collectors solve this problem trivially." [1]: https://docs.rs/crossbeam-epoch/0.6.0/crossbeam_epoch/ https://docs.rs/crossbeam-epoch/0.6.0/crossbeam_epoch/
  - pcwalton 8y ago
    It's not just the core mechanism of crossbeam-epoch that I'm talking about: it's the entire ecosystem that surrounds it. Crossbeam-epoch adds some syntactic overhead compared to GC, but it comes with a whole bunch of tools that most GC'd languages don't have, including a compiler that ensures that you take locks when you're supposed to.
chc 8y ago
I know this works, but whenever I hear this advice, I can't help thinking: Aren't indexes and vectors basically just a way of smuggling pointers past the borrow checker?
- steveklabnik 8y ago
  It depends on what you mean by “smuggling.” This implies something bad; I don’t think this pattern is inherently bad. It’s just different. It’s another example of moving a compile-time check to a runtime check, and depending on what you’re doing, can have better cache locality and better performance.
  - vvanders 8y ago
    Yeah, that's a pattern we used all over the place in games where we also abused the hell out of pointers(some in-place loaders I've seen would turn your hair white) because the pattern has other merits.
  - comex 8y ago
    It has worse ergonomics, though. Most obviously, every time you want to access data through an index ‘reference’, you need to name two things: the array and the index. With a pointer you only have to name one thing. Thus, you might have to write `self.widgets[widget].foo` instead of `widget.foo`: not the end of the world, but annoying if you have a lot of references floating around. Further, even if Rust guarantees memory safety, the approach is still less safe in the broader sense of guaranteeing program correctness. For one thing, if you just use raw integers for your indices, you basically have the equivalent of a C void pointer, a pointer to some unknown type. The compiler doesn’t know what the index is for and can’t catch you if you accidentally index into the wrong array. You can partially solve this by making a newtype wrapper for indices into each type of array, but even that can’t differentiate between multiple arrays of the same type. Also, if you have a system for ‘freeing’ array indices and reusing those array slots for new data, you run the risk of keeping an index around too long and causing a semantic use-after-free: not as bad as a traditional memory use-after-free, usually, but certainly a source of incorrect and unpredictable behavior. And whereas tools like ASan let you ‘flip a switch’ to catch traditional use-after-frees if they happen in development builds, with arrays you have to add the extra checking manually. (On the other hand, if you do design extra checks, they might be cheap enough to run in production, where ASan is probably not. And yes, I know, when it comes to security, “if they happen in development builds” is quite meager comfort.) But I’m not saying all this just to be negative. Personally, it’s my hope that someday in the future, Niko and co. will find ways to make the borrow checker more expressive when it comes to parent-child relationships, and in other situations where it currently struggles. If so, it won’t just help with pointers, but with array-based designs as well: it’ll become a more viable approach to have the borrow checker check array indices, by adding lifetimes to those array index newtypes. That would remove all of the aforementioned safety issues, while keeping the performance benefit of arrays – indeed, increasing it, since with the right design you would be able to safely disable the bounds check when indexing.
dilap 8y ago
non-ruster question: does rust let you easily define a new type to use for the index, so you're not just using ints everywhere (with all the lack of type safety and clarity that implies)?
- Inityx 8y ago
  Absolutely https://doc.rust-lang.org/std/ops/trait.Index.html https://doc.rust-lang.org/std/ops/trait.Index.html https://github.com/rust-unofficial/patterns/blob/master/patterns/newtype.md https://github.com/rust-unofficial/patterns/blob/master/patt...
  - jonathanstrange 8y ago
    Or they could just implement integer subtypes like Ada has since 1983, but it seems that Rustaceans prefer to write boilerplate instead.
    - kibwen 8y ago
      Ada's integer subtypes are newtypes, but you don't need integer subtypes to have newtypes. Furthermore, newtypes are applicable to more than just integers; e.g. one might newtype String to represent an HTTP header.
      - jonathanstrange 8y ago
        That's incorrect. Ada has subtypes and new types for scalars and they behave differently. For example, a new integer type is: type MyInteger is integer; declares a new integer type that needs to be explicitly converted to any other integer type. You can also declare a new range integer type as in type MyPositive is integer range 1 .. Integer'Last; But you can also delcare integer and float subtypes: subtype Day_Number is integer range 1 .. 31; or (a bit pointless) subtype MyInt is integer; The difference between new types and subtypes is that no operations of the base type are defined for the new type since it's an entirely new type. A subtype on the other hand allows the operations of the base type, and their range is checked at compile time if possible and runtime if necessary. In addition to this, Ada also has modular integer types, real types, floating point types, fixed point types, and decimal types in the numeric type system and all of them can be subtyped. Of course, you can create a new type for any other type in Ada as well, but that's not what I meant when I was talking about integer subtypes.
seanmcdirmid 8y ago
Using an index/ID rather than a direct object reference basically excludes the object from any kind of automatic memory management. Aren’t you just arguing that they should all be managed manually?
- Retra 8y ago
  The object will still be freed when its owner is dropped... It's just the accesses to the object that are manually managed, not memory.
  - seanmcdirmid 8y ago
    There is no way to tell if there is an index to the object or not, so obviously it’s lifetime has to be managed manually.
    - Retra 8y ago
      Indexes aren't references to objects, they're references to slots. The lifetimes of the objects are determined by whoever puts them into and out of those slots. That doesn't have to be determined manually. Sure, objects aren't deallocated when the index is dropped, but that doesn't mean it isn't being automatically deallocated somewhere else for some other reason.
      - seanmcdirmid 8y ago
        Wherever the object is deallocted, it can’t be done safely via the language or languages runtime because those indices are completely opaque. I’m not saying this is a bad thing, it definitely has a use case, but just that it isn’t really showing off a viable alternative to GC, it is very weird to be states as such. All manual memory management schemes work as you describe, they aren’t classes as automatic because the language runtime (or standard libs) can’t provide it for free.
- pcwalton 8y ago
  I don't see any reason why you couldn't have a Rust ECS that keeps track of the number of outstanding references to each entity and doesn't free them while there are any references left. You'd have an opaque "reference" object instead of an index. (Care would have to be taken to make sure the references can't go dangling when the vector is resized, but it should be possible.) But usually programmers intend to destroy entities in one place; for example, in UI code, a programmer typically expects a widget to be destroyed once it's removed from the window. It can be beneficial to have the runtime system diagnose if a reference to an object thought to be destroyed is actually used. So I haven't seen anyone actually go to the trouble…
Const-me 8y ago
> for example in games, where an ECS design using IDs is generally preferable to direct references In scripting/gameplay parts of games maybe. In rendering or other performance-critical components, pointers are just faster. They are single RAM reference, IDs are 2 RAM references (and in case of languages like C# or Rust, plus bounds checking).
- kibwen 8y ago
  Sure, and fortunately ECSes are usually for managing world state, leaving one free to use references for graphics, physics, AI, etc. An ECS-esque design for one component of the system does not preclude using pointers elsewhere.
  - Const-me 8y ago
    > An ECS-esque design for one component of the system does not preclude using pointers elsewhere. I know how ECS work, but GP was advocating Rust's way i.e. not using pointers at all.
    - eddyb 8y ago
      Not using pointers at all for graphs. I suspect a lot of the data where you want to use pointers for efficiency, is already in stricter shapes than graphs.
      - Const-me 8y ago
        > Not using pointers at all for graphs. And trees. > I suspect a lot of the data where you want to use pointers for efficiency, is already in stricter shapes than graphs. In games, graphs are used for pathfinding and other AI, for skeletal animation incl. IK. Trees are everywhere: scene graph, bounding volumes, space partitioning, many others.
        kibwen 8y ago
        If you have a tree then your data necessarily isn't cyclic or self-referential, in which case you likely won't have any problem using references.

ecnahc515 8y ago

Crossbeam is awesome. That said; I think his point is more on the "how hard is it to write a crossbeam-like library in Rust compared to a language with a GC".

ridiculous_fish 8y ago
From crossbeam docs [1]: "Programming languages that come with garbage collectors solve this problem trivially." [1]: https://docs.rs/crossbeam-epoch/0.6.0/crossbeam_epoch/ https://docs.rs/crossbeam-epoch/0.6.0/crossbeam_epoch/
- pcwalton 8y ago
  It's not just the core mechanism of crossbeam-epoch that I'm talking about: it's the entire ecosystem that surrounds it. Crossbeam-epoch adds some syntactic overhead compared to GC, but it comes with a whole bunch of tools that most GC'd languages don't have, including a compiler that ensures that you take locks when you're supposed to.

chc 8y ago

I know this works, but whenever I hear this advice, I can't help thinking: Aren't indexes and vectors basically just a way of smuggling pointers past the borrow checker?

steveklabnik 8y ago
It depends on what you mean by “smuggling.” This implies something bad; I don’t think this pattern is inherently bad. It’s just different. It’s another example of moving a compile-time check to a runtime check, and depending on what you’re doing, can have better cache locality and better performance.
- vvanders 8y ago
  Yeah, that's a pattern we used all over the place in games where we also abused the hell out of pointers(some in-place loaders I've seen would turn your hair white) because the pattern has other merits.
- comex 8y ago
  It has worse ergonomics, though. Most obviously, every time you want to access data through an index ‘reference’, you need to name two things: the array and the index. With a pointer you only have to name one thing. Thus, you might have to write `self.widgets[widget].foo` instead of `widget.foo`: not the end of the world, but annoying if you have a lot of references floating around. Further, even if Rust guarantees memory safety, the approach is still less safe in the broader sense of guaranteeing program correctness. For one thing, if you just use raw integers for your indices, you basically have the equivalent of a C void pointer, a pointer to some unknown type. The compiler doesn’t know what the index is for and can’t catch you if you accidentally index into the wrong array. You can partially solve this by making a newtype wrapper for indices into each type of array, but even that can’t differentiate between multiple arrays of the same type. Also, if you have a system for ‘freeing’ array indices and reusing those array slots for new data, you run the risk of keeping an index around too long and causing a semantic use-after-free: not as bad as a traditional memory use-after-free, usually, but certainly a source of incorrect and unpredictable behavior. And whereas tools like ASan let you ‘flip a switch’ to catch traditional use-after-frees if they happen in development builds, with arrays you have to add the extra checking manually. (On the other hand, if you do design extra checks, they might be cheap enough to run in production, where ASan is probably not. And yes, I know, when it comes to security, “if they happen in development builds” is quite meager comfort.) But I’m not saying all this just to be negative. Personally, it’s my hope that someday in the future, Niko and co. will find ways to make the borrow checker more expressive when it comes to parent-child relationships, and in other situations where it currently struggles. If so, it won’t just help with pointers, but with array-based designs as well: it’ll become a more viable approach to have the borrow checker check array indices, by adding lifetimes to those array index newtypes. That would remove all of the aforementioned safety issues, while keeping the performance benefit of arrays – indeed, increasing it, since with the right design you would be able to safely disable the bounds check when indexing.

dilap 8y ago

non-ruster question: does rust let you easily define a new type to use for the index, so you're not just using ints everywhere (with all the lack of type safety and clarity that implies)?

Inityx 8y ago
Absolutely https://doc.rust-lang.org/std/ops/trait.Index.html https://doc.rust-lang.org/std/ops/trait.Index.html https://github.com/rust-unofficial/patterns/blob/master/patterns/newtype.md https://github.com/rust-unofficial/patterns/blob/master/patt...
- jonathanstrange 8y ago
  Or they could just implement integer subtypes like Ada has since 1983, but it seems that Rustaceans prefer to write boilerplate instead.
  - kibwen 8y ago
    Ada's integer subtypes are newtypes, but you don't need integer subtypes to have newtypes. Furthermore, newtypes are applicable to more than just integers; e.g. one might newtype String to represent an HTTP header.
    - jonathanstrange 8y ago
      That's incorrect. Ada has subtypes and new types for scalars and they behave differently. For example, a new integer type is: type MyInteger is integer; declares a new integer type that needs to be explicitly converted to any other integer type. You can also declare a new range integer type as in type MyPositive is integer range 1 .. Integer'Last; But you can also delcare integer and float subtypes: subtype Day_Number is integer range 1 .. 31; or (a bit pointless) subtype MyInt is integer; The difference between new types and subtypes is that no operations of the base type are defined for the new type since it's an entirely new type. A subtype on the other hand allows the operations of the base type, and their range is checked at compile time if possible and runtime if necessary. In addition to this, Ada also has modular integer types, real types, floating point types, fixed point types, and decimal types in the numeric type system and all of them can be subtyped. Of course, you can create a new type for any other type in Ada as well, but that's not what I meant when I was talking about integer subtypes.

seanmcdirmid 8y ago

Using an index/ID rather than a direct object reference basically excludes the object from any kind of automatic memory management. Aren’t you just arguing that they should all be managed manually?

Retra 8y ago
The object will still be freed when its owner is dropped... It's just the accesses to the object that are manually managed, not memory.
- seanmcdirmid 8y ago
  There is no way to tell if there is an index to the object or not, so obviously it’s lifetime has to be managed manually.
  - Retra 8y ago
    Indexes aren't references to objects, they're references to slots. The lifetimes of the objects are determined by whoever puts them into and out of those slots. That doesn't have to be determined manually. Sure, objects aren't deallocated when the index is dropped, but that doesn't mean it isn't being automatically deallocated somewhere else for some other reason.
    - seanmcdirmid 8y ago
      Wherever the object is deallocted, it can’t be done safely via the language or languages runtime because those indices are completely opaque. I’m not saying this is a bad thing, it definitely has a use case, but just that it isn’t really showing off a viable alternative to GC, it is very weird to be states as such. All manual memory management schemes work as you describe, they aren’t classes as automatic because the language runtime (or standard libs) can’t provide it for free.
pcwalton 8y ago
I don't see any reason why you couldn't have a Rust ECS that keeps track of the number of outstanding references to each entity and doesn't free them while there are any references left. You'd have an opaque "reference" object instead of an index. (Care would have to be taken to make sure the references can't go dangling when the vector is resized, but it should be possible.) But usually programmers intend to destroy entities in one place; for example, in UI code, a programmer typically expects a widget to be destroyed once it's removed from the window. It can be beneficial to have the runtime system diagnose if a reference to an object thought to be destroyed is actually used. So I haven't seen anyone actually go to the trouble…

Const-me 8y ago

> for example in games, where an ECS design using IDs is generally preferable to direct references In scripting/gameplay parts of games maybe. In rendering or other performance-critical components, pointers are just faster. They are single RAM reference, IDs are 2 RAM references (and in case of languages like C# or Rust, plus bounds checking).

kibwen 8y ago
Sure, and fortunately ECSes are usually for managing world state, leaving one free to use references for graphics, physics, AI, etc. An ECS-esque design for one component of the system does not preclude using pointers elsewhere.
- Const-me 8y ago
  > An ECS-esque design for one component of the system does not preclude using pointers elsewhere. I know how ECS work, but GP was advocating Rust's way i.e. not using pointers at all.
  - eddyb 8y ago
    Not using pointers at all for graphs. I suspect a lot of the data where you want to use pointers for efficiency, is already in stricter shapes than graphs.
    - Const-me 8y ago
      > Not using pointers at all for graphs. And trees. > I suspect a lot of the data where you want to use pointers for efficiency, is already in stricter shapes than graphs. In games, graphs are used for pathfinding and other AI, for skeletal animation incl. IK. Trees are everywhere: scene graph, bounding volumes, space partitioning, many others.
      - kibwen 8y ago
        If you have a tree then your data necessarily isn't cyclic or self-referential, in which case you likely won't have any problem using references.