3 ms·

> They may not be "sane" in your view because they're different from the way you implement them in C++ I saw two kinds of Rust graphs. One is safe, easy to un

> They may not be "sane" in your view because they're different from the way you implement them in C++ I saw two kinds of Rust graphs. One is safe, easy to understand, but slow (e.g. reference counting). Another one (unsafe Rust) is very hard to implement, thousands lines of code. Also, modern C++ is much safer than unsafe rust. > C++ has no protection against the most pernicious memory management errors, particularly use-after-free CRT debug heap / MALLOC_CHECK_ / libefence, depending on the platform/compiler

cesarb 9y ago
> I saw two kinds of Rust graphs. There's a third kind, which uses indexes into arrays containing the nodes and edges, instead of direct pointers to the node/edge. > CRT debug heap / MALLOC_CHECK_ / libefence, depending on the platform/compiler Can any of these protect against the scenario where a block of memory is freed, allocated again for another purpose, but still accessed through the old dangling pointer? Also, are they always present at runtime, or are they used only on debug builds and turned off on production? The use-after-free might happen only after a specific sequence of uncommon operations confuses the code enough that it either frees something before its time, or keeps and uses a stale pointer.
- Const-me 9y ago
  > There's a third kind, which uses indexes into arrays containing the nodes and edges Pointers are still faster. Also with arrays it’s expensive to reduce RAM usage after a lot of nodes were removed. > Can any of these protect against the scenario where a block of memory is freed, allocated again for another purpose, but still accessed through the old dangling pointer? No 100% guarantee, but AFAIR CRT debug heap takes measures to reduce RAM reuse when it can. > are they always present at runtime, or are they used only on debug builds Not present. Yes, only on debug builds. Still, these early debug traps are quite helpful while development.
  - cesarb 9y ago
    > Pointers are still faster. Depending on cache effects, indexes might or might not be faster than pointers. With indexes into an array, the nodes or edges will be sequential in memory, which depending on their size and access patterns might increase the cache hit rate. Furthermore, while pointers will always be 8 or 4 bytes, indexes can be as small as 2 or even 1 byte for smaller graphs (reducing structure sizes and potentially leading again to a higher cache hit rate). As for the costs of indexing, on x86 a single instruction can add the array base, the index, and a constant offset, and do a load or store from/to the resulting address. Other architectures might need a few more instructions, but that is dwarfed by the cost of a cache miss, which can be hundreds of instructions. Another cost is the bounds check for every indexing into the array, which the compiler can't elide because it can't easily prove that the index is within the array bounds. That is the main reason you saw "unsafe" code on the petgraph crate; there are places where the programmer knows the indexes are within the bounds, since they came from a trusted place (the graph itself), but the compiler isn't smart enough to prove it, so the programmer manually bypasses the array bound checks in these cases. All in all, I wouldn't know a priori which would be faster for a particular use case, pointers or array indices. I'd have to benchmark first. > Also with arrays it’s expensive to reduce RAM usage after a lot of nodes were removed. True, the "array indexes" approach is not as good for algorithms which need to remove many nodes (or edges, depending on how they're represented) from the graph. As long as you don't need the indexes to be stable across deletions, you can use a simple trick to make deletions cheaper (move the last element of the array into the newly freed place, so all empty places are at the end of the array), but that trick can't be used if you need the indexes to be stable (because they're referenced from outside the graph).
    - Const-me 9y ago
      https://news.ycombinator.com/item?id=15180649 https://news.ycombinator.com/item?id=15180649
    - deleted 9y ago
      [deleted]
    - benlorenzetti 9y ago
      Your point about reducing pointer size if the size of allocation pool is smaller makes sense. But I think it is not fair or realistic to imply that simply using an array the size of all RAM starting at zero leads to more fragmentation than referencing all of RAM relative to some other point. Assuming same algorithms working on same sized data sets. The relative locations of objects is not dependent on where the coordinate origin is, although choosing a good zero may make the engineer's life easier.
bluejekyll 9y ago
I can't reply directly to your other comment, so I'll do it here. In the case of pet-graph, I wouldn't say it has large amounts of unsafe (I reviewed it recently b/c I might start using it), but it does use unsafe. Most data structures in Rust require unsafe for performance or memory access patterns. In these cases the developer is the one responsible for guaranteeing that it is safe (no loss over an unsafe language). > modern C++ is much safer than unsafe rust This is an interesting comment. I can't say if you are right or wrong, but it's thought provoking. So I'll quote the rustinomicon here: Unsafe Rust is exactly like Safe Rust with all the same rules and semantics. However Unsafe Rust lets you do some extra things that are Definitely Not Safe. The only things that are different in Unsafe Rust are that you can: -Dereference raw pointers -Call unsafe functions (including C functions, intrinsics, and the raw allocator) -Implement unsafe traits -Mutate statics Point being Rust doesn't just throw out all the rules. But it's a very interesting assertion. https://doc.rust-lang.org/nomicon/meet-safe-and-unsafe.html https://doc.rust-lang.org/nomicon/meet-safe-and-unsafe.html
- Const-me 9y ago
  > I can't reply directly to your other comment Next time just wait 5-10 minutes. > Most data structures in Rust require unsafe for performance or memory access patterns. And when I want to compose 2 data structures into my own higher-level one, for performance and memory access patterns I need these two lower-level structures to expose unsafe stuff at their API boundaries. The data structures I saw don’t do that, they’re designed to be consumed from safe Rust instead. > Rust doesn't just throw out all the rules I think in modern C++, with these iterators and smart pointers, you’re less likely to screw up dereferencing a wrong pointer.
  - pcwalton 9y ago
    > And when I want to compose 2 data structures into my own higher-level one, for performance and memory access patterns I need these two lower-level structures to expose unsafe stuff at their API boundaries. The data structures I saw don’t do that, they’re designed to be consumed from safe Rust instead. Can you give a specific example of something you want to do that you can't? > I think in modern C++, with these iterators and smart pointers, you’re less likely to screw up dereferencing a wrong pointer. I don't think this is empirically true relative to C, but even if it is, use after free is still far too common in C++ code.
pcwalton 9y ago
There is another kind of Rust graph that uses indices. Indices are just bounds checked addresses, so this is a natural fit. The most popular graph crate, petgraph, is of this type. > CRT debug heap / MALLOC_CHECK_ / libefence, depending on the platform/compiler None of these are effective at preventing use after free problems in production.
- Const-me 9y ago
  There’s another problem with arrays: they can’t be too large. First reason is address space fragmentation, esp. on 32-bit platforms. Second reason is insert time can be very high. Sure, the average is usually amortized using exponential growth. The worst case however is horrible, you copy 1GB RAM just to insert another 16-byte item.

cesarb 9y ago

> I saw two kinds of Rust graphs. There's a third kind, which uses indexes into arrays containing the nodes and edges, instead of direct pointers to the node/edge. > CRT debug heap / MALLOC_CHECK_ / libefence, depending on the platform/compiler Can any of these protect against the scenario where a block of memory is freed, allocated again for another purpose, but still accessed through the old dangling pointer? Also, are they always present at runtime, or are they used only on debug builds and turned off on production? The use-after-free might happen only after a specific sequence of uncommon operations confuses the code enough that it either frees something before its time, or keeps and uses a stale pointer.

Const-me 9y ago
> There's a third kind, which uses indexes into arrays containing the nodes and edges Pointers are still faster. Also with arrays it’s expensive to reduce RAM usage after a lot of nodes were removed. > Can any of these protect against the scenario where a block of memory is freed, allocated again for another purpose, but still accessed through the old dangling pointer? No 100% guarantee, but AFAIR CRT debug heap takes measures to reduce RAM reuse when it can. > are they always present at runtime, or are they used only on debug builds Not present. Yes, only on debug builds. Still, these early debug traps are quite helpful while development.
- cesarb 9y ago
  > Pointers are still faster. Depending on cache effects, indexes might or might not be faster than pointers. With indexes into an array, the nodes or edges will be sequential in memory, which depending on their size and access patterns might increase the cache hit rate. Furthermore, while pointers will always be 8 or 4 bytes, indexes can be as small as 2 or even 1 byte for smaller graphs (reducing structure sizes and potentially leading again to a higher cache hit rate). As for the costs of indexing, on x86 a single instruction can add the array base, the index, and a constant offset, and do a load or store from/to the resulting address. Other architectures might need a few more instructions, but that is dwarfed by the cost of a cache miss, which can be hundreds of instructions. Another cost is the bounds check for every indexing into the array, which the compiler can't elide because it can't easily prove that the index is within the array bounds. That is the main reason you saw "unsafe" code on the petgraph crate; there are places where the programmer knows the indexes are within the bounds, since they came from a trusted place (the graph itself), but the compiler isn't smart enough to prove it, so the programmer manually bypasses the array bound checks in these cases. All in all, I wouldn't know a priori which would be faster for a particular use case, pointers or array indices. I'd have to benchmark first. > Also with arrays it’s expensive to reduce RAM usage after a lot of nodes were removed. True, the "array indexes" approach is not as good for algorithms which need to remove many nodes (or edges, depending on how they're represented) from the graph. As long as you don't need the indexes to be stable across deletions, you can use a simple trick to make deletions cheaper (move the last element of the array into the newly freed place, so all empty places are at the end of the array), but that trick can't be used if you need the indexes to be stable (because they're referenced from outside the graph).
  - Const-me 9y ago
    https://news.ycombinator.com/item?id=15180649 https://news.ycombinator.com/item?id=15180649
  - deleted 9y ago
    [deleted]
  - benlorenzetti 9y ago
    Your point about reducing pointer size if the size of allocation pool is smaller makes sense. But I think it is not fair or realistic to imply that simply using an array the size of all RAM starting at zero leads to more fragmentation than referencing all of RAM relative to some other point. Assuming same algorithms working on same sized data sets. The relative locations of objects is not dependent on where the coordinate origin is, although choosing a good zero may make the engineer's life easier.

bluejekyll 9y ago

I can't reply directly to your other comment, so I'll do it here. In the case of pet-graph, I wouldn't say it has large amounts of unsafe (I reviewed it recently b/c I might start using it), but it does use unsafe. Most data structures in Rust require unsafe for performance or memory access patterns. In these cases the developer is the one responsible for guaranteeing that it is safe (no loss over an unsafe language). > modern C++ is much safer than unsafe rust This is an interesting comment. I can't say if you are right or wrong, but it's thought provoking. So I'll quote the rustinomicon here: Unsafe Rust is exactly like Safe Rust with all the same rules and semantics. However Unsafe Rust lets you do some extra things that are Definitely Not Safe. The only things that are different in Unsafe Rust are that you can: -Dereference raw pointers -Call unsafe functions (including C functions, intrinsics, and the raw allocator) -Implement unsafe traits -Mutate statics Point being Rust doesn't just throw out all the rules. But it's a very interesting assertion. https://doc.rust-lang.org/nomicon/meet-safe-and-unsafe.html https://doc.rust-lang.org/nomicon/meet-safe-and-unsafe.html

Const-me 9y ago
> I can't reply directly to your other comment Next time just wait 5-10 minutes. > Most data structures in Rust require unsafe for performance or memory access patterns. And when I want to compose 2 data structures into my own higher-level one, for performance and memory access patterns I need these two lower-level structures to expose unsafe stuff at their API boundaries. The data structures I saw don’t do that, they’re designed to be consumed from safe Rust instead. > Rust doesn't just throw out all the rules I think in modern C++, with these iterators and smart pointers, you’re less likely to screw up dereferencing a wrong pointer.
- pcwalton 9y ago
  > And when I want to compose 2 data structures into my own higher-level one, for performance and memory access patterns I need these two lower-level structures to expose unsafe stuff at their API boundaries. The data structures I saw don’t do that, they’re designed to be consumed from safe Rust instead. Can you give a specific example of something you want to do that you can't? > I think in modern C++, with these iterators and smart pointers, you’re less likely to screw up dereferencing a wrong pointer. I don't think this is empirically true relative to C, but even if it is, use after free is still far too common in C++ code.

pcwalton 9y ago

There is another kind of Rust graph that uses indices. Indices are just bounds checked addresses, so this is a natural fit. The most popular graph crate, petgraph, is of this type. > CRT debug heap / MALLOC_CHECK_ / libefence, depending on the platform/compiler None of these are effective at preventing use after free problems in production.

Const-me 9y ago
There’s another problem with arrays: they can’t be too large. First reason is address space fragmentation, esp. on 32-bit platforms. Second reason is insert time can be very high. Sure, the average is usually amortized using exponential growth. The worst case however is horrible, you copy 1GB RAM just to insert another 16-byte item.