Also, I highly encourage people who worry about pointer management all the time to checkout modern C++.
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.
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.
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->.
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).
Taking the reference would be "auto foo = ptr.operator->()". This could be forbidden by not providing op->, and instead having an apply function which takes a method name and the parameters. That would be safer, but probably too much effort for little gain.
It could be a null unique_ptr of course, but I don't see how this is anything worse than a denial-of-service.
Keep in mind that you are at this point arguing against the existence of actual zero-days that have occurred in Firefox (and lots of other software). This is not a theoretical concern.
My point is all Rust does is force you stop and think, and while C++ lets you do dumb shit, it's hardly fair to blame the language when almost-safe C++ is actually cleaner and easier to read and write than dumb C++.
Build your own handle types with well-defined ownership semantics, use explicit move() sparingly, pass objects by value, use references, utilize the stack and temporaries. Only put pointers inside the guts of classes and your data structure implementations. These techniques go quite far.
And Firefox as an appeal to authority is hardly compelling. As another, I've seen bug fixes in Chromium where the original code quality is so poor it was hard to believe it came out of Google. Of course, since then i've learned most C++ out of Google is total crap.
Yes, it's possible, however references should only ever have local scope so, unless you're dealing with threads or asynchrony it's hard to write sane code where this happens, and if you have those things, and you're passing refs or ptrs, then I don't have to tell you that things are bad.
> as opposed to in C where an explicit call to free is required, this makes C++ more prone to UAF than C.
I don't see this. C++ destructors run after the last line of your code block, if something uses a destructed object then it can only be because you passed a pointer or reference to it to something else that wasn't yet destroyed.
Mentioning free() just implies that you're willing to accept resource leaks to avoid UAF bugs, which is nuts because UAFs can be a lot easier to debug.
If you're focused on security, it goes in the opposite direction: a resource leak can lead to a denial of service, but an use-after-free can lead to remote code execution, which is much worse. From that point of view, it's worth it risking a resource leak if by doing that you prevented a potential instance of remote code execution.
By the way,
> C++ destructors run after the last line of your code block
Aren't there many situations where the C++ destructor runs at the end of the current statement? IIRC, if you call a function which returns a temporary, then call a method on that temporary which returns a reference to within the temporary, and assign the result to a variable, all in a single statement, the temporary will be destructed while the reference to its contents is still live.
The obvious answer to this would be never to return references to members (or anything tied to the objects lifefime), but if you really must then you can always use a qualifier to prevent this pattern from compiling.
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
> 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
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.
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.
Compose a hash map + linked list into an LRU cache. Rust how has that in standard library, but they had to implement their own linked list for that. In C++ it’s just a few lines of code, because standard maps+lists compose just fine.
Or (more generic example and thus harder to put in the standard library), add an index to existing collection. I have a large collection of some values. I want to build an index allowing to lookup values by some key. Values are not small, can’t afford duplicating them. If you’ll tell “just move values into a hashmap”, my response is “and I also want another, different index of the same set of values by different key”. Again, very easy in C++, encapsulate both the original collection, and a hashmap from key to value pointer.
> use after free is still far too common in C++ code.
In my experience, use after free = instant crash in debug build. Quite easy to detect and fix.
The security track records of major network-facing C++ apps disagree with you.
Even if I manage to extract an unsafe pointer from that Rust collection, I don’t know for how long will it work. For C++ collections, iterator invalidation rules tell me that.
It's easy, just get the & or &mut to the value (as if you were acessing it), and cast it to respectively * const or * mut.
> I don’t know for how long will it work. For C++ collections, iterator invalidation rules tell me that.
It's the same in Rust. Whenever the iterator would be invalidated in C++, the pointer you stashed above might point to the wrong place. This is not usually documented in Rust, because its borrow rules prevent you from stashing a reference while the collection mutates, but once you start playing with raw pointers, the borrow checker gets out of the way (references have a lifetime, pointers don't).
You just have to be careful when casting the pointer back to a mutable ref ("unsafe { &mut *ptr }" is the trick, see the documentation for std::mem::transmute): mutable references are like C99's "restrict", so you should make sure to only ever have one live for each pointer at every moment, otherwise you're in undefined behavior land.
----
Anyway, going back to the parent comment, you said "Values are not small, can’t afford duplicating them". Might I suggest keeping the values in a Box<T> then, and making both collections point to the box? That way, you don't have to worry about a mutation in one of the collections invalidating the pointer, since the contents of a Box won't move in memory.
And in fact, the usual Rust style for keeping a value in more than one collection would be to use a Rc<T>, which is basically a Box with a reference counter. That way, you don't need to play with raw pointers, and have no risk of a misstep. You pay the cost of incrementing/decrementing the reference counter only when adding/removing from the collection, and the reference counter is small.
Indeed, both methods are simple and elegant ways to approach the problems.
The bad thing with both of them is performance.
Box<T> means when I need to iterate through all values in a collection, I’ll get random memory access for each item. Rc<T> is even worse, not only it’s RAM read latency per item, also ref.counting overhead per item (AFAIK even when reading stuff).
That's the beauty of the borrow checker: no, there's no reference counting overhead when reading stuff. The borrow checker guarantees that the reference you used to access the value won't go away until you're done with it, so it doesn't have to increment the reference counter.
The iterator invalidation rules in Rust are straightforward, more straightforward than those in C++. They have to be, because the compiler actually checks them.
> I need these two lower-level structures to expose unsafe stuff at the API boundary
Two thoughts: 1) I think you can always use unsafe to get access to a raw pointer (I honestly don't use unsafe often) 2) you need someway to express ownership between both data structures, this can be annoying, no doubt.
> C++, with these iterators and smart pointers
Does that make it safer than unsafe Rust? Maybe, but there's a lot less unsafe Rust even in these graphs...
I’m not sure about that. Also I don’t know for how long will it work, C++ has iterator invalidation rules.
> you need someway to express ownership between both data structures
Not every relation is ownership. Graph modes don’t own each other, an external index doesn’t own the indexed items, etc.
So, I need to do both. And also, I need to know when these pointer expire so I can rebuild my index when it happens.
What's the benefit of doing that, compared to making both the HashMaps store pointers to independently allocated objects on the heap, such that insertions into one map never invalidate the other map? Is the hope to avoid paying the cost of an extra pointer dereference when we're using the first map? Or does independently allocating each object hurt cache locality or something like that?
Both.
In practice, I probably wouldn’t use a hashmap for the first container that actually owns these items. When I do expect gigabytes of data, in C++ I use something like vector<vector<tValue>>, where the inner vectors are of the same fixed size (except for the last one), e.g. 2-16MB RAM / each. If I need to erase elements, I include a free list such as this one: https://github.com/Const-me/CollectionMicrobench/blob/master...
But the exact container is not that important here. If you don’t have that many values, it can as well be a standard vector.
The point is, C++ allows composing these containers making higher-level ones, such as this indexed array example, using pointers to link individual items across them. This feature allows building sophisticated and efficient data structures that are still possible to reason about.
The technique of giving stable addresses to things by stuffing them into vectors isn't unique to C++. People do it in Rust too: https://github.com/SimonSapin/rust-typed-arena/blob/master/s...
They can be standard, third-party, my own, I still can compose them.
About my particular example, I’m not sure you can easily implement a free list in rust, to reuse space from de-allocated items. Especially if these items have non-empty constructor and destructor.
What I---and others---are trying to tell you is that it's perfectly possible in Rust too. I don't think you've pointed out anything that isn't possible in Rust. My previous comment was exactly about composing containers to make higher-level ones.
Have you tried building such things? Did you get stuck? Maybe someone can help.
> About my particular example, I’m not sure you can easily implement a free list in rust, to reuse space from de-allocated items. Especially if these items have non-empty constructor and destructor.
I don't see any reason why implementing a free list in Rust wouldn't be possible either.
While vectors are comparable, C++ also guarantees a lot about the rest of the containers. E.g. unordered associative containers never expire pointers to keys or values. Linked lists never expire pointers nor iterators.
In C++ I can create an efficient LRU cache in a dozen lines of code, combining list<const tKey* > with unordered_map<tKey, struct{tValue, list<const tKey* >::iterator}> (this implies tKey is not an int, otherwise list<tKey> is more efficient). Rust’s built-in LinkedHashMap had to reimplement a linked list instead.
Is placement new available in rust stable?
Could you give a specific example please? I compose data structures in Rust all the time.
> CRT debug heap / MALLOC_CHECK_ / libefence, depending on the platform/compiler
None of these are effective at preventing use after free problems in production.
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.
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.
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.
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).
- Some OT code. This went ok, but I still have no idea which of the 6 string types I should use for a library like that. I think I ended up settling for Rc<Cow<String>> or something, but it still wasn't ideal. Swift, Go and C all each have a canonical string type.
- First I tried to make a skip list with performance matching the performance of my C implementation. I discovered that even with unsafe there was no way to make a struct with a dynamically sized array at the end, like I can easily do in C.
- Then I tried to make a networked server using tokio. Despite all the hype, adding a dynamic item to the event bus didn't work because it wasn't 'static didn't work. After spending a few hours fighting the borrow checker, I went online and was told that this would get better with impl trait or something.
I'd really like to use rust, but as far as I can tell its not mature enough for what I want. I've started a new server project recently and I'm writing it in straight C, as none of the newcomer C-replacement languages I tried seem good enough to replace C.
There are two string types: a string that owns its contents and a string that references its contents. This is the same as in any language that uses smart pointers for resource management.
Can you name a string type that you think should be removed, and explain why?
> First I tried to make a skip list with performance matching the performance of my C implementation. I discovered that even with unsafe there was no way to make a struct with a dynamically sized array at the end, like I can easily do in C.
Yes, you can. You can make a one element array and allocate and deallocate manually, just as you do in C. The offset method on pointers allows for arbitrary pointer arithmetic.
> Despite all the hype, adding a dynamic item to the event bus didn't work because it wasn't 'static didn't work.
I haven't used Tokio, but couldn't you use a boxed trait?
There's String, &str, Cow<?>, Rc<?> and other variants. None is canonical. I spent about 2 hours reading documentation trying to pick the right type to use and I think I ended up with Rc<Cow<String>>. But in this instance my strings represent character edits in a document. 90% of the time they're < 5 bytes long. So in 90+% of cases I should be able to avoid allocations and memory dereferencing entirely, and store the string inside the pointer. What I actually want is an efficient version of enum Str { ShortStr(char[X]), Ref(Rc<Cow<String>>) }, but encapsulated behind a common string interface. Coincidentally, this is exactly how the canonical string implementation works in obj-c and (I think) swift. Despite having 6 different options maybe the string type I actually want is buried in Cargo. I'm not sure - at this point I was tired and I stopped trying.
To me this is a classic symptom of a language trying to do too much. Having all this choice is great for systems development, but for application-level development I don't want X different string options. You want 1. And I want it to be good. Having lots of options would be fine if the language was more opinionated - "Unless you know what you're doing you should just use String, which is efficient, immutable, copy-on-write and ref counted. Click here (link to advanced section of book) to read about your other options if you want more control over allocations."
> Yes, you can. You can make a one element array and allocate and deallocate manually, just as you do in C. The offset method on pointers allows for arbitrary pointer arithmetic.
Does it? At the time even with unsafe there was no way to directly call malloc. Maybe I just couldn't find it in the docs, or maybe thats changed now. I spent weeks on and off trying to get it working, including reading the rust unsafe nomicon and writing dozens of linked list implementations. I tried out all sorts of weird ways to allocate and initialize the array. I kept thinking of new ideas, only to find out a critical piece of syntax was missing. In the end I could allocate the struct I wanted but discovered it was syntactically impossible to initialize, or something silly like that. And at that point I gave up. Maybe this problem has been fixed since. And maybe if I spent even more time trying I would have figured it out. But I was tired and I had work to do.
> I haven't used Tokio, but couldn't you use a boxed trait?
I don't know what that is. Frankly I'm still confused why Rc<> didn't work. I got about 6 different answers when I asked the rust subreddit how to fix this. Some people suggested things that also didn't compile. Some people said I should make my object 'static (no thanks). And others said the problem would be fixed when trait impl lands (whatever that is - is that what you're talking about?). This use case is literally the 'hello world' of nodejs code - attach an event handler to an object, interact with local variables each time the event fires. At least as of a year ago the tokio devs clearly thought all network servers only did request/response style interaction. All the examples on their website were either an echo server or an http server. I need streams.
I really want to be able to use rust. But so far my only experience with it has been one of frustration. It seems too immature to replace C as a systems language, and tokio seems too immature to replace Nodejs for network services. Maybe I'll revisit it in a few years, but at this point I'm more hopeful either someone will bolt decent syntax on top of Go a la coffeescript, or that Swift will add language level support for concurrency. (I'd be happy with either async or go's actor model.)
To be fair, that's like saying std::string and std::shared_ptr<std::string> are two different string types in C++, and that neither is canonical.
In Rust, String/&str are the canonical string types. String is an owned growable buffer, &str is an immutable slice. That's it. Adding Cow<_>, Rc<_> or Arc<_> to the mix is orthogonal to the specific string type you're using. They are smart pointers and can work with various types other than strings.
> What I actually want is an efficient version of enum Str { ShortStr(char[X]), Ref(Rc<Cow<String>>) }, but encapsulated behind a common string interface.
We couldn't get away with adding this as the standard library string type because it would impose non-zero costs on every use of a string. The use of Rc is particularly grating because it's not thread safe, which means you wouldn't even be able to send strings across threads. That would suck. So then you might want to say to use an Arc---atomic ref counting, thread safe---but that's even more costly.
I'm honestly kind of confused at your feedback here. At first it just sounded like you were bewildered by the various string types---which is a fair criticism, getting strings right is hard and everyone has opinions on what they should look like---but it actually sounds like you knew exactly what you wanted, and were frustrated that the standard library didn't have it. Instead, the standard library gives you a fundamental string type that one could use to build other more advanced string types when you need them.
The typical solution to problems like that is to go out and build what you need and put it on crates.io. Or, use one that already exists. :-) https://docs.rs/inlinable_string/0.1.8/inlinable_string/
Not long ago, they open sourced the compiler and a subset of runtime, making it cross-platform: https://github.com/dotnet/core It’s a but tricky to install on Linux, but for me it works OK, at least so far (an embedded TCP/UDP server app).
But if I'm going to move further away from the hardware in exchange for some language comforts & quality of life improvements, Elixir is the next language I want to try. I think both its concurrency primitives and immutability rules might be the right language-level defaults.
C# has descent native interop, i.e. [DllImport]. On Linux it imports from .so dynamic libraries. When you want to be closer to the hardware, because SIMD, or system calls not exposed to .NET, or integration with third-party C code, it usually works OK.
Oh and Fortran of course.
But yeah, I also find it sad having to go down to Assembly to make use of them.
SIMD in Rust: http://huonw.github.io/blog/2015/08/simd-in-rust/ (yes, still in nightly)
Thousands lines of code. Large amount of that is unsafe rust, even C++ is safer than that :-)
> SIMD in Rust: http://huonw.github.io/blog/2015/08/simd-in-rust/ (yes, still in nightly)
It was already “still in nightly” a year ago. Also it’s harder to do integer math with it, because type safety: very often, even consecutive instructions interpret these __m128i registers as different datatypes, u8x16 / i32x4 / u64x2 / etc.
Have you taken a look at petgraph? It does quite a lot of things. The same functionality in C would be thousands of lines as well.
> It was already “still in nightly” a year ago.
SIMD is in Rust nightly not because it's immature, but because the Rust developers would rather design a portable interface than quickly standardize a nonportable one. Given that AFAIK neither the C nor C++ specifications include provisions for SIMD and all support is compiler-specific, the only difference between C/C++ and Rust here is that Rust follows a release model that features a nightly channel.
The support is portable across compilers. You #include <[xepsiz]mmintrin.h>, and you’ll get these SIMD intrinsics as documented on intel.com.
BTW, OpenMP isn’t in the C++ language spec either, doesn’t prevents it from working on most compilers and platforms.