46 ms·

> That it has no sane ways to implement a graph structure. Sure it does. I work with graphs in Rust all the time. They may not be "sane" in your view because

> That it has no sane ways to implement a graph structure. Sure it does. I work with graphs in Rust all the time. They may not be "sane" in your view because they're different from the way you implement them in C++, but I could equally well say that there's no "sane" way to implement a safe owning pointer in C++ (since there's no memory-safe way to do so). > Also, I highly encourage people who worry about pointer management all the time to checkout modern C++. Modern C++ has no protection against the most pernicious memory management errors, particularly use-after-free.

Const-me 9y ago
> 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).
- 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.
nly 9y ago
> I could equally well say that there's no "sane" way to implement a safe owning pointer in C++ unique_ptr + std::move gives you that semantically. Sure it won't stop you from dereferencing a null pointer but, in all the years i've been writing C++, finding and fixing null pointer dereferences wouldn't rank very high on my list of things to worry about. They always kill your program and are easy to spot in an IDE or debugger. Rusts choice to make pointers either mutable and owning, or shared and immutable and garbage-collected, is no doubt the right one, but there are code-styles in C++ where this can be achieved with a very low fuck-up rate. The modern C++ way is not to use pointers, except as an implementation detail. A pointer (raw or smart) of any type, other than perhaps char*, as a function parameter is a sure sign of code smell, and raw pointers as data members have very limited use.
- pcwalton 9y ago
  Unique pointers provide no protection against use after free, because you can take a reference to their contents and that reference can become dangling. Because the destructor of a unique pointer is invoked automatically per the language rules, as opposed to in C where an explicit call to free is required, this makes C++ more prone to UAF than C.
  - blub 9y ago
    It's unusual to take references to the contents of a unique pointer. There is one idiom which says that if one has a smart ptr and a function taking a ref, the raw ptr should be passed, but that's it. It's frowned upon... nay scoffed at to store references one receives as parameters, so that temporary ref will go away after the function call, leaving the smart ptr as unique owner. This should not be a problem and it certainly doesn't make C++ more prone to use after free. Null pointers are the problem. Both can be solved though by creating e.g. a safe smart ptr which does null checks and only exposes operator->.
    - pcwalton 9y ago
      > It's unusual to take references to the contents of a unique pointer. No, it's not. It happens every time you call a method on the referent (well, OK, this is technically not a reference, but it doesn't matter to the argument).

Const-me 9y ago

> 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).
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.

nly 9y ago

> I could equally well say that there's no "sane" way to implement a safe owning pointer in C++ unique_ptr + std::move gives you that semantically. Sure it won't stop you from dereferencing a null pointer but, in all the years i've been writing C++, finding and fixing null pointer dereferences wouldn't rank very high on my list of things to worry about. They always kill your program and are easy to spot in an IDE or debugger. Rusts choice to make pointers either mutable and owning, or shared and immutable and garbage-collected, is no doubt the right one, but there are code-styles in C++ where this can be achieved with a very low fuck-up rate. The modern C++ way is not to use pointers, except as an implementation detail. A pointer (raw or smart) of any type, other than perhaps char*, as a function parameter is a sure sign of code smell, and raw pointers as data members have very limited use.

pcwalton 9y ago
Unique pointers provide no protection against use after free, because you can take a reference to their contents and that reference can become dangling. Because the destructor of a unique pointer is invoked automatically per the language rules, as opposed to in C where an explicit call to free is required, this makes C++ more prone to UAF than C.
- blub 9y ago
  It's unusual to take references to the contents of a unique pointer. There is one idiom which says that if one has a smart ptr and a function taking a ref, the raw ptr should be passed, but that's it. It's frowned upon... nay scoffed at to store references one receives as parameters, so that temporary ref will go away after the function call, leaving the smart ptr as unique owner. This should not be a problem and it certainly doesn't make C++ more prone to use after free. Null pointers are the problem. Both can be solved though by creating e.g. a safe smart ptr which does null checks and only exposes operator->.
  - pcwalton 9y ago
    > It's unusual to take references to the contents of a unique pointer. No, it's not. It happens every time you call a method on the referent (well, OK, this is technically not a reference, but it doesn't matter to the argument).