I've gone back and forth on this, myself.
I wrote a custom b-tree implementation in rust for a project I've been working on. I use my own implementation because I need it to be an order-statistic tree, and I need internal run length encoding. The original version of my b-tree works just like how you'd implement it in C. Each internal node / leaf is a raw allocations on the heap.
Because leaves need to point back up the tree, there's unsafe everywhere, and a lot of raw pointers. I ended up with separate Cursor and CursorMut structs which held different kinds of references to the tree itself. Trying to avoid duplicating code for those two cursor types added a lot of complex types and trait magic. The implementation works, and its fast. But its horrible to work with, and it never passed MIRI's strict checks. Also, rust has really bad syntax for interacting with raw pointers.
Recently I rewrote the b-tree to simply use a vec of internal nodes, and a vec of leaves. References became array indexes (integers). The resulting code is completely safe rust. Its significantly simpler to read and work with - there's way less abstraction going on. I think its about 40% less code. Benchmarks show its about 25% faster than the raw pointer version. (I don't know why - but I suspect the reason is due to better cache locality.)
I think this is indeed peak rust.
It doesn't feel like it, but using an array-index style still preserves many of rust's memory safety guarantees because all array lookups are bounds checked. What it doesn't protect you from is use-after-free bugs.
Interestingly, I think this style would also be significantly more performant in GC languages like javascript and C#, because a single array-of-objects is much simpler for the garbage collector to keep track of than a graph of nodes & leaves which all reference one another. Food for thought!
Static analysis could potentially check for those potential panics at compile time. If that was implemented, the run time check, and the potential for a panic, would go away. It's not hard to check, provided that all borrows have limited scope. You just have to determine, conservatively, that no two borrow scopes for the same thing overlap.
If you had that check, it would be possible to have something that behaves like RefCell, but is checked entirely at compile time. Then you know you're free of potential double-borrow panics.
I started a discussion on this on a Rust forum. A problem is that you have to perform that check after template expansion, and the Rust compiler is not set up to do global analysis after template expansion. This idea needs further development.
This check belongs to the same set of checks which prevent deadlocking a mutex against itself. There's been some work on Rust static deadlock analysis, but it's still a research topic.
However, I'm not sure what the implications are around mutability. I use a Cursor struct which stores a reference to a specific leaf node in the tree. Cursors can walk forward in the tree (cursor.next_entry()). The tree can also be modified at the cursor location (cursor.insert(item)). Modifying the tree via the cursor also updates some metadata all the way up from the leaf to the root.
If the cursor stored a Rc<Leaf> or Weak<Leaf>, I couldn't mutate the leaf item because rc.get_mut() returns None if there are other strong or weak pointers pointing to the node. (And that will always be the case!). Maybe I could use a Rc<Cell<Leaf>>? But then my pointers down the tree would need the same, and pointers up would be Weak<Cell<Leaf>> I guess? I have a headache just thinking about it.
Using Rc + Weak would mean less unsafe code, worse performance and code thats even harder to read and reason about. I don't have an intuitive sense of what the performance hit would be. And it might not be possible to implement this at all, because of mutability rules.
Switching to an array improved performance, removed all unsafe code and reduced complexity across the board. Cursors got significantly simpler - because they just store an array index. (And inserting becomes cursor.insert(item, &mut tree) - which is simple and easy to reason about.)
I really think the Vec<Node> / Vec<Leaf> approach is the best choice here. If I were writing this again, this is how I'd approach it from the start.
I have done this before with stdlib stuff like io::Cursor and was pretty happy with the result.
Doesn't this also require you to correctly and efficiently implement (equivalents of C's) malloc() and free()? IIUC your requirements are more constrained, in that malloc() will only ever be called with a single block size, meaning you could just maintain a stack of free indices -- though if tree nodes are comparable in size to integers this increases memory usage by a significant fraction.
(I just checked and Rust has unions, but they require unsafe. So, on pain of unsafe, you could implement a "traditional" freelist-based allocator that stores the index of the next free block in-place inside the node.)
In my case, inserts and read operations vastly outnumber deletes. So much so that in all of my testing, I never saw a leaf node which could be freed anyway. (Leaves store ~32 values, and there were no cases where all of a leaf's values actually get deleted). I decided to just leak nodes if it ever happens in real life.
The algorithm processes data in batches then frees everything. So worst case, it just has slightly higher peak memory usage while processing. A fine trade in this case given it let me remove ~200 lines of code - and any bugs that might have been lurking in them.
How about using hash maps/hash tables/dictionaries/however it's called in Rust? You could generate unique IDs for the elements rather than using vector indices.
Cache locality matters, but so does having less allocator pressure. Use 32-bit unsigned ints as indices, and you get improvements on that as well.
>The original version of my b-tree works just like how you'd implement it in C. Each internal node / leaf is a raw allocations on the heap.
I'd always try to avoid that type of allocation pattern in C++, FWIW :-).
I probably say this because I still have to main 32-bit binaries (only 2G of address space), but it can potentially be problematic even on 64-bit machines (typically 256 TB of address space), especially if the data structure should be a reusable container with unknown number of instances. If you don't know a reasonable upper bound of elements beforehand, you have to reallocate later, or drastically over-reserve from the start. The former removes a pointer stability guarantee, the later is uneconomical, it may even be uneconomical on 64-bit depending on how many instances of the data structures you plan to have. And having to reallocate when overflowing the preallocated space makes operations less deterministic with regards to execution time.
That makes sense. If my btree was gigabytes in size, I might rethink the approach for a number of reasons. But in my case, even for quite large input, the data structure never gets more than a few megabytes in size. Thats small enough that resizing the vec has a negligible performance impact.
It helps that my btree stores its contents using lossless internal run-length encoding. Eg, if I have values like this:
{key: 5, value: 'a'}
{key: 6, value: 'a'}
{key: 7, value: 'a'}
{key: [5..8), value: 'a'}
Yes. I've found that problem in index-allocated code.
Also, when you do this, you need an allocator for the indexes. I've found bugs in those.
These are all solvable problems, but in reality, it's very hard to write a good business case for being the one to solve them. Most of the cost accrues to you and most of the benefit to the commons. Unless a corporate actor decides to write a major new engine in Rust or use Bevy as the base for the same, or unless a whole lot of indie devs and part-time hackers arduously work all this out, it's not worth the trouble if you're approaching it from the perspective of a studio with severe limitations on both funding and time.
The difference is that I'm writing a metaverse client, not a game. A metaverse client is a rare beast about halfway between an MMO client and a web browser. It has to do most of the the graphical things a 3D MMO client does. But it gets all its assets and gameplay instructions from a server.
From a dev perspective, this means you're not making changes to gameplay by recompiling the client. You make changes to objects in the live world while you're connected to the server. So client compile times (I'm currently at about 1 minute 20 seconds for a recompile in release mode) aren't a big issue.
Most of the level and content building machinery of Bevy or Unity or Unreal Engine is thus irrelevant. The important parts needed for performance are down at the graphics level. Those all exist for Rust, but they're all at the My First Renderer level. They don't utilize the concurrency of Vulkan or multiple CPUs. When you get to a non-trivial world, you need that. Tiny Glade is nice, but it works because it's tiny.
What does matter is high performance and reliability while content is coming in at a high rate and changing. Anything can change at any time, but usually doesn't. So cache type optimizations are important, as is multithreading to handle the content flood. Content is constantly coming in, being displayed, and then discarded as the user moves around the big world. All that dynamism requires more complex data structures than a game that loads everything at startup.
Rust's "fearless multiprogramming" is a huge win for performance. I have about 20 threads running, and many are doing quite different things. That would be a horror to debug in C++. In Rust, it's not hard.
(There's a school of thought that says that fast, general purpose renderers are impossible. Each game should have its own renderer. Or you go all the way to a full game engine and integrate gameplay control and the scene graph with the renderer. Once the scene graph gets big enough that (lights x objects) becomes too large to do by brute force, the renderer level needs to cull based on position and size, which means at least a minimal scene graph with a spatial data structure. So now there's an abstraction layering problem - the rendering level needs to see the scene graph. No one in Rust land has solved this problem efficiently. Thus, none of the four available low-level renderers scale well.
I don't think it's impossible, just moderately difficult. I'm currently looking at how to do this efficiently, with some combination of lambdas which access the scene graph passed into the renderer, and caches. I really wish someone else had solved this generic problem, though. I'm a user of renderers, not a rendering expert.)
Meta blew $40 billion dollars on this problem and produced a dud virtual world, but some nice headsets. Improbable blew upwards of $400 million and produced a limited, expensive to run system. Metaverses are hard, but not that hard. If you blow some of the basic architectural decisions, though, you never recover.
The only challenge is not having an ecosystem with ready made everything like you do in "batteries included" frameworks. You are basically building a game engine and a game at the same time.
We need a commercial engine in Rust or a decade of OSS work. But what features will be considered standard in Unreal Engine 2035?
(For the record software development has nothing to do now with how it looked when I started in 2003, plenty of things have revolutionized the way we write code (especially Github) and made us an order of magnitude more productive at least. Yet the number of developer has skyrocketed. I don't expect this trend to stop, AI is yet another productivity boost in an industry that already faced a lot of them in recent time.
I see this and I am reminded when I had to fight the 0 indexing, when I was cutting my teeth in C, for class.
I wonder why no one complains about 0 indexing anymore. Isn't it weird how you have to go 0 to length - 1, and implement algorithm differently than in a math book?
Am I the only person that remembers how hard it was to wrap your head around numbers starting at 0, rather than 1?
So the reason why you don't see many people fighting 0-indexing is because they actually prefer it.
Maybe you had the luck of learning 0 based language first. Then most of them were a smooth ride.
My point is you forgot how hard it is because it's now muscle memory (if you need a recap of the difficulty learn a program with arbitrary array indexing and set you first array index to something exciting like 5 or -6). It also means if you are "fighting the borrow checker" you are still at pre-"muscle memory" stage of learning Rust.
Given most languages since at least C have 0-based indexing... I would think most engineers picked it up early? I recall reading The C Programming Language 20 years ago, reading the reason and just following what it says. I don't think it's as complex as the descriptions people put forward of "fighting the borrow checker." One is "mentally add/subtract 1" and another is "gain a deep understanding of how memory management works in Rust." I know which one I'm going to find more challenging when I get round to trying to learn Rust...
As I mentioned I started Basic on C64, and schools curriculum was in Pascal. I didn't learn about C until I got to college.
> One is "mentally add/subtract 1" and another is "gain a deep understanding of how memory management works in Rust."
In practice they are, you start writing code. At first you trip on your feet, read stuff carefully, then try again until you succeed.
Then one day, you wake up and realize I know 0 indices and/or borrow checker. You don't know how you know, you just know you don't make those mistakes anymore.
Also, there’s a huge difference between beginners not understanding 0-based indexing and experienced C++ engineers describing the challenges understanding Rust’s unique features. I mean, Jesus Christ, we’re commenting on a thread here of experienced engineers commenting on how challenging it can be! I really don’t know what else to say.
Keep in mind I wasn't new to programming at that point. I was programming in C64 basic for 3 years and Pascal for 3 as well. For hobby of course, and not fully.
Zero indexes aren't simple, they are intertwined everywhere but they are easy - as in familiar.
What experienced C++ devs in Rust are not much different than experienced Pascal devs in C. Lost. And having to rethread semi-familiar grounds.
---
And I described you my own. I don't fight the borrow checker. I just intuitively know how it works and what to avoid.
If you think just subtracting one or adding one is enough, there should be an easy enough way to test if it is. In Veritasium video they mention that having glasses that turn your vision upside down will cause confusion at first, but you will get used to them quickly.
What you could do is take a language that has arbitrary starting index value and set it to something weird. Like 42 or -5. Then rewrite your programs. See how many off by 41 errors you make. Then once you no longer make mistakes with it. Go back to 0 indexes.
Do you need me to comment on the difference between 0 and 42?
But you need to see with eyes of a newbie. I mean what is the problem here, you did say it's just adding or subtracting a number whether it's 0, 1, -1 or 42? Should be trivial, right?
My guess while the change of indices is simple (altering ranges by a constant), it's going to be hard (requiring constant mental effort until it's internalized).
Apparently I do need to comment but I don't think any human on earth has the words to convince you that, as a human, adding/subtracting by 1 is a billion times easier to understand than adding/subtracting 42.
Ok, then add start your indices with something else 1 or 2, -1 would be best but probably not well supported. Whatever you aren't used to.
Also why is substracting a small number such a problem? I never found adding/substracting 1, much more difficult than 42. It's just math.
If the answer to your question is not self-evident, then I don't know of any words that will convince you.
for (i=0; i<length; i++)
The borrow checks feels similar but different. It feels like it has more "levels" to it. Initially, it came naturally to me and I wondered what all the fuss was about. I was fighting iterators and into, not the borrow checker. I just had to mentally keep track of what owned my data and it all felt pretty obvious.
Then I started working on things that didn't fit into my naive mental model, and it became a constant fight.
So overall, a similar experience to 0-based indexing, yes. (Except I still don't "just know" the trickier bits of the borrow checker yet, so I don't know what comes next.)
I started out with BASIC and Fortran, which use 1 based indices. Going to C was a small bump in the road getting used to that, and then it's Fortran which is the oddball.
DIM a(10)
I believe it was QBASIC that first borrowed the ability to define ranges explicitly from Pascal, so that we could do:
DIM a(1 TO 10)
Most languages have abstractions for iterating over an array so that you don’t need to use 0 or length-1 these days
element_position = start + index*element_sizeSure. But from most general to least general, it goes:
Counting on fingers >>>> Math Equations >> Computer algorithms
The more general ones influence the less general ones because that's where most people start.
(defvar names (Vector String)
#("Alex" "Kim" "Robin" "Sam"))
(elt names 1)
(defvar names (Vector String)
#("Alex" "Kim" "Robin" "Sam"))
(first names)
(defvar names (Vector String)
#("Alex" "Kim" "Robin" "Sam"))
(elt names (lowbound names))
To say it's the same as using array indices is just not true.
Bevy entity IDs are opaque and you have to try really hard to do arithmetic on them. You can technically do math on instance IDs in Unity too; you might say "well, nobody does that", which is my point exactly.
> You don't need to deal with the game life cycle AND the memory life cycle with a GC.
I don't know what this means. The memory for a `GameObject` is freed once you call `Destroy`, which is also how you despawn an object. That's managing the memory lifecycle.
> In Unity they free the native memory when a game object calls Destroy() but the C# data is handled by the GC. Same with any plain C# objects.
Is there a use for storing data on a dead `GameObject`? I've never had any reason to do so. In any case, if you really wanted to do that in Bevy you could always use an `EntityHashMap`.
The live C# but dead Unity object trick is mostly only useful for dangling handles and IDs and such. It's more that memory won't be ripped out from under you for none Unity data and the usual GC rules apply.
And again the difference between using the GC and rolling your own implementation is pretty big. In your hash map example you still have to solve the issue of how long you keep entries in that map. The GC answers that question.