5 ms·

> Rustaceans usually opt for continuous data layout (known in C/C++ lingua as array-of-struct or struct-of-array depending on priorities), which is more cache-f

> Rustaceans usually opt for continuous data layout (known in C/C++ lingua as array-of-struct or struct-of-array depending on priorities), which is more cache-friendly than reference-heavy data structures anyway. Yes! This is a point that I try to hammer home that's missed by many people who write C/C++ on a daily basis. Everyone wants to use the fanciest data structures when most of the times arrays will be faster and simpler to use.

nilved 10y ago
They are also opaque to the type system.
jstimpfle 10y ago
SOA is the widely accepted approach to performance design. Not an argument vs C/C++, though.
- vvanders 10y ago
  Sure, but maybe 10% of C/C++ developers I've worked with over my career was actually aware of it :). I wasn't putting it out there as a dig against C/C++ but more a general comment on how rarely it's understood/appreciated in native code.
  - jstimpfle 10y ago
    > I wasn't putting it out there as a dig against C/C++ It very much sounded like that.
lomnakkus 10y ago
Isn't this a bit of a weird formulation? What matters isn't actually layout... what matters is access patterns. If you lay out a 32G array and access it randomly you're not much better of that just doing loads of pointer chasing. (Alright, prefetching might help a little bit, but...)
charles-salvia 10y ago
C++ programmers usually prefer contiguous data layout as well. I mean std::vector is just a contiguous array that dynamically reallocates and copies/move-constructs everything as needed. But many interesting data structures are hard to write in a memory-efficient manner without resorting to non-contiguous nodes. Even a hashtable often will use linked lists within each bucket for collision resolution. You can argue that an open-addressing scheme is more cache-friendly, but it also has downsides, i.e. performance degrades faster as the load factor gets higher. Many other interesting data structures, especially some lock-free structures, are simply impractical to implement as single contiguous arrays. Of course, any node-based structure can make use of a memory pool that allocates blocks from one or more larger contiguous buffers, but there will still be pointers interleaved throughout the structure. All in all, it remains true that Rust doesn't really provide any safety above C++ in regard to writing these kinds of node-based data structures, and saying "don't ever write node-based data structures" is just pointless. Yes, Rust has some downsides and tradeoffs. Is it so bad to just say that out loud?
- msbarnett 10y ago
  > All in all, it remains true that Rust doesn't really provide any safety above C++ in regard to writing these kinds of node-based data structures Debatable. It certainly does for the consumers of these structures, and data structures are consumed a lot more often than they are rewritten. > Yes, Rust has some downsides and tradeoffs. Is it so bad to just say that out loud? Of course not. But that doesn't mean you shouldn't expect some pushback if you're incorrectly describing those tradeoffs. Is it really so bad to say "at the end of the day, the difficulty of complex graphs in safe Rust is symptomatic not of a flaw in Rust but of how hard it is to build these things without memory errors even in C or C++" out loud?
- ekidd 10y ago
  > All in all, it remains true that Rust doesn't really provide any safety above C++ in regard to writing these kinds of node-based data structures, Yup! Rust does not fix all your problems, sadly. Maybe some of them. :-) If you're working with graph-like structures in Rust, then you have two choices: 1. You can work with pointers using 'unsafe' blocks, and then wrap everything inside a nice, safe API. This is a good tradeoff if your data structure is only a tiny portion of your code, or if it's reusable. (Most of the data structures in Rust's 'std' crate are written like this.) 2. You can work with indices instead of pointers. This is the approach taken by petgraph (https://docs.rs/petgraph/0.4.3/petgraph/ https://docs.rs/petgraph/0.4.3/petgraph/), which is currently one of the best graph libraries for Rust. Not all Rust code needs to be safe. It's OK to write "unsafe" code and put it behind a "safe" API. If I can eliminate 98% of the opportunities for pointer bugs, I'm happy to eyeball the remaining 2% manually.
ThatGeoGuy 10y ago
> Everyone wants to use the fanciest data structures when most of the times arrays will be faster and simpler to use. I'm not sure I comprehend this, since I don't often encounter code where people use advanced data structures to do simple things. For most collections, you're typically talking about an array of some kind, since you just want to iterate through many objects doing the same thing. However, there is a reason for more complex data structures to exist. KDTrees, for example, are great for performing nearest-neighbour search, and I can't see any situation where I'd want to use a straight array if I knew I was doing nearest-neighbour searches. In the most broad, general case I agree: array-of-struct or struct-of-arrays is probably the way to go. You can even see this in the data science world where data frames (effectively struct-of-arrays) are the tool of the trade. However, there are algorithms where if you want an advanced data structure, you really want it (e.g. KDTree). Is it really so common in systems programming to see people trying to incorporate all sorts of magic from The Art of Computer Programming into their programs? I can't say I've ever seen it myself (obvious disclaimer that while I'm a programmer by trade I don't read too many large Rust / C++ projects).
- vvanders 10y ago
  Guess how every Quad/KDTree I've seen has been implemented(I've seen 3 in high-perf domains)? SoA + indices, because locality of the search is critical and you want explicit control over the layout.

nilved 10y ago

They are also opaque to the type system.

jstimpfle 10y ago

SOA is the widely accepted approach to performance design. Not an argument vs C/C++, though.

vvanders 10y ago
Sure, but maybe 10% of C/C++ developers I've worked with over my career was actually aware of it :). I wasn't putting it out there as a dig against C/C++ but more a general comment on how rarely it's understood/appreciated in native code.
- jstimpfle 10y ago
  > I wasn't putting it out there as a dig against C/C++ It very much sounded like that.

lomnakkus 10y ago

Isn't this a bit of a weird formulation? What matters isn't actually layout... what matters is access patterns. If you lay out a 32G array and access it randomly you're not much better of that just doing loads of pointer chasing. (Alright, prefetching might help a little bit, but...)

charles-salvia 10y ago

C++ programmers usually prefer contiguous data layout as well. I mean std::vector is just a contiguous array that dynamically reallocates and copies/move-constructs everything as needed. But many interesting data structures are hard to write in a memory-efficient manner without resorting to non-contiguous nodes. Even a hashtable often will use linked lists within each bucket for collision resolution. You can argue that an open-addressing scheme is more cache-friendly, but it also has downsides, i.e. performance degrades faster as the load factor gets higher. Many other interesting data structures, especially some lock-free structures, are simply impractical to implement as single contiguous arrays. Of course, any node-based structure can make use of a memory pool that allocates blocks from one or more larger contiguous buffers, but there will still be pointers interleaved throughout the structure. All in all, it remains true that Rust doesn't really provide any safety above C++ in regard to writing these kinds of node-based data structures, and saying "don't ever write node-based data structures" is just pointless. Yes, Rust has some downsides and tradeoffs. Is it so bad to just say that out loud?

msbarnett 10y ago
> All in all, it remains true that Rust doesn't really provide any safety above C++ in regard to writing these kinds of node-based data structures Debatable. It certainly does for the consumers of these structures, and data structures are consumed a lot more often than they are rewritten. > Yes, Rust has some downsides and tradeoffs. Is it so bad to just say that out loud? Of course not. But that doesn't mean you shouldn't expect some pushback if you're incorrectly describing those tradeoffs. Is it really so bad to say "at the end of the day, the difficulty of complex graphs in safe Rust is symptomatic not of a flaw in Rust but of how hard it is to build these things without memory errors even in C or C++" out loud?
ekidd 10y ago
> All in all, it remains true that Rust doesn't really provide any safety above C++ in regard to writing these kinds of node-based data structures, Yup! Rust does not fix all your problems, sadly. Maybe some of them. :-) If you're working with graph-like structures in Rust, then you have two choices: 1. You can work with pointers using 'unsafe' blocks, and then wrap everything inside a nice, safe API. This is a good tradeoff if your data structure is only a tiny portion of your code, or if it's reusable. (Most of the data structures in Rust's 'std' crate are written like this.) 2. You can work with indices instead of pointers. This is the approach taken by petgraph (https://docs.rs/petgraph/0.4.3/petgraph/ https://docs.rs/petgraph/0.4.3/petgraph/), which is currently one of the best graph libraries for Rust. Not all Rust code needs to be safe. It's OK to write "unsafe" code and put it behind a "safe" API. If I can eliminate 98% of the opportunities for pointer bugs, I'm happy to eyeball the remaining 2% manually.

ThatGeoGuy 10y ago

> Everyone wants to use the fanciest data structures when most of the times arrays will be faster and simpler to use. I'm not sure I comprehend this, since I don't often encounter code where people use advanced data structures to do simple things. For most collections, you're typically talking about an array of some kind, since you just want to iterate through many objects doing the same thing. However, there is a reason for more complex data structures to exist. KDTrees, for example, are great for performing nearest-neighbour search, and I can't see any situation where I'd want to use a straight array if I knew I was doing nearest-neighbour searches. In the most broad, general case I agree: array-of-struct or struct-of-arrays is probably the way to go. You can even see this in the data science world where data frames (effectively struct-of-arrays) are the tool of the trade. However, there are algorithms where if you want an advanced data structure, you really want it (e.g. KDTree). Is it really so common in systems programming to see people trying to incorporate all sorts of magic from The Art of Computer Programming into their programs? I can't say I've ever seen it myself (obvious disclaimer that while I'm a programmer by trade I don't read too many large Rust / C++ projects).

vvanders 10y ago
Guess how every Quad/KDTree I've seen has been implemented(I've seen 3 in high-perf domains)? SoA + indices, because locality of the search is critical and you want explicit control over the layout.