If you have a dynamic type that you can attach arbitrary new fields to, then, capability-wise, you have exactly what's needed to make game entities: to do a lookup by entity type, just traverse the list of all entities looking for a magic pattern in the data. To look up a specific one, assign each one a unique ID and search by ID.
The problem is that game developers get anxious about this kind of lackadaisical structure(for good reason, if there's any aim at serious performance) and want to put more things in their own index, and allocate things with a more compact representation and less fragmentation.
And the alternatives are...god object with every possible behavior crammed into an oversized record type, and ECS bookkeeping, in its various flavors, some more compilation-heavy and others more reflective with more runtime editing functionality.
But regardless of what approach you take, every time you introduce dynamism into your entities and enable more flexibility in asset assignment, you convert more of your bugs into data bugs. There are a huge number of bugs in games that are configuration problems with the entity and not a flow control or algorithms issue.
Of course you still have restrictions on aliasing, so you're not going to get data races. But you'll still get bugs that are essentially equivalent to ones you'd get with raw pointers.
In the process you avoid use-after-free, double-free, and accessing unallocated memory because the borrowers always live shorter lives than the owners, and can only access borrowed and thus allocated memory that is deallocated once the owner dies, and there is nobody else who can use it or free it once more.
You don't really avoid those things, though. In the process you end up with index-use-after-index-free, double-index-free, and accessing index-unallocated array entries.
These are the exact same bugs the borrow checker prevents in main memory, just hidden from the borrow checker by adding a layer of abstraction.
These are memory-unsafety bugs. You still get the same wrong answers caused by coding errors. Random junk values and behaviours, when dereferencing use-after-free invalid pointers that point to memory reused for a new object. It's just that pointers are now called indexes, and the borrow checker doesn't check these pointers.
It's like turning the borrow checker off for this set of objects. Those long-lived entities you mentioned act as a mechanism to enable that. That's useful to do, but nobody should be under the impression use-after-free, pointers to the wrong objects and other memory-unsafety bugs don't happen in the array index model.
A compiler can only prevent bad things from happening within a system, typically just one process. The world around it doesn’t work that way. A system is often a cache, not an owner, and caches go out of date because the world changed without notice. You want to update on what notices you get that the world changed. You can’t prevent inconsistency, only detect it and react by updating or removing outdated information.
This probably isn’t relevant within a batch compiler, but it would be for a language service in an IDE.
Games often simulate worlds where references shouldn’t own things. It would be a weird form of power to remotely prevent something from getting destroyed because you remember it. Even though both objects are within the same process, they’re modeled as independent systems where pointer ownership doesn’t happen.
It also checks that the slot you are trying to get is occupied, and if it's not it won't let you access it. It actually is forced to check that the slot is occupied because the slot is an enum with vacant and occupied variants, and the vacant variant doesn't have a value to get in the first place. In rust you can't read a data out of an enum without checking the variant first.
With these two restrictions, you can't use stale keys, you can't UAF, and you can't read junk data at all, it's enforced by the type system and the runtime checks.
You can still have keys that are invalid, but the slotmap's "get" method returns an option type, and invalid keys cause it to return "None".
So in practice, you will end up panicking if your keys become invalid (the index operator panics when the return value is "None"), or you will explicitly handle the "None" case and do whatever you want to do.
All of this only applies to this specific data structure though, and the checks do have some performance cost.
It seems that these are memory-unsafety bugs with the caveat that they have nothing to do with the memory allocator. Maybe a sort of sandboxed memory unsafety? I don’t know.
It's an application-specific memory allocator.
AFAICT, a language would need something like higher RAII [0] or linear types [1] for that. I'd love to see Rust adopt these features too one day, though it may be difficult to do backwards compatibly.
A reference is a new object that references an existing memory value. You can not store a reference unless the borrow-checker can prove that the object that stores it has a shorter lifetime than the referenced object.
That is also why you can't just pass that reference around willy-nilly, because the reference is consumed due to affine types.
I may be misunderstanding something though so feel free to correct me.
And also weird claims that arenas solve memory safety problems in C, when it's equally likely (depending on the program) that they CAUSE dangling pointers, use-after-free, etc.
The same issue comes up in slightly different ways in both C/C++ and Rust
---
My comment on this post from 2 months ago:
https://old.reddit.com/r/ProgrammingLanguages/comments/1350d...
Summary: the upsides are very real, but we should mention the downsides too:
- Arenas punt on memory safety; Ownership can be nontrivial (a bunch of examples)
- Mutation, and appending to list/vectors are complications
- Pointer representations are more friendly to debuggers
My wiki page is linked at the bottom of this article (which I appreciate because it actually has code and measurements!)
https://github.com/oilshell/oil/wiki/Compact-AST-Representat...
Packing your objects into their own tight heap not only doesn't solve memory allocation issues, but makes them harder to debug. The tools for fighting these problems in C don't work as well.
In TXR Lisp, I have to have a number of strategies in place for debugging GC issues.
One is Valgrind integration. If you want to use Valgrind, but have implemented your own bump allocation within packed heaps, Valgrind won't be as helpful.
For example, what is a semantic use-after-free in your world (something accessing an object that has been garbage collected) looks fine to the C library; you're just dereferencing a pointer into a large object that you allocated just fine.
With Valgrind integration, you can use the API mark free objects inaccessible. But: that only means Valgrind will detect the wrong use of a reclaimed object (quite swiftly, thank you very much). It will not tell you who allocated that object. The diagnostic will be something like "invalid read, 15300 bytes into a 262164 object, allocated at <call stack>". That is not very useful! It gives you the call stack when that entire heap was allocated, not when that misused object within that heap was allocated.
I have some debug support which takes advantage of reproducible repro test cases where we can count on addresses of bad objects being the same. Once I know the address of the offending object, I can put it into a debug variable called break_obj. When the object is allocated or reclaimed, there is a VALGRIND_PRINTF which will dump a trace. I can also get a breakpoint in gdb (that's why it's the break_obj).
There is also an option to run the GC in a kind of torture mode where garbage collection is invoked on every allocation. Newly allocated objects that are not properly retained by the caller (made visible to gc) will be scavenged immediately, revealing those kinds of bugs by bringing the allocation and misuse contexts close together. A substantial portion of the test suite runs in this GC torture mode. Not everything, because it's quite slow.
https://news.ycombinator.com/item?id=36427264
In response to a claim about arena-based allocators and memory safety
I see this in the current manual:
VALGRIND_MALLOCLIKE_BLOCK:
If your program manages its own memory instead of using the standard malloc / new / new[], tools that track information about heap blocks will not do nearly as good a job. For example, Memcheck won't detect nearly as many errors, and the error messages won't be as informative. To improve this situation, use this macro just after your custom allocator allocates some new memory. See the comments in valgrind.h for information on how to use it.
I can't remember whether I saw this before; i.e. is this something existing that had not been useful, or is it something new. I will look into it.
It does look like it should be attacking the same problem: that the errors aren't detected well or nearly as informative in blocks carved out of larger block by custom allocators.
When I go through the hoops of registering each heap as a memory pool, which supports malloc-like allocations doled out of it, problems happen.
When cell [0] of a heap becomes garbage and is indicated as freed (reclaimed by GC), Valgrind throws an invalid free/delete/delete[] error, saying there is a conflict between that and the entire block. I think this is because there is no offset between the block and the start of the heap. Valgrind assumes there will be some header or red zone between the entire memory zone and the pool area. It seems to be saying, whoa, you can't do VALGRIND_FREELIKE_BLOCK at that address; you allocated that address from malloc. Well no shit, and I told you that block was a heap, from which I'm getting VALGRIND_MALLOCLIKE_BLOCK blocks.
Secondly, after the first GC cycles, errors go haywire, like "invalid read of 2 bytes: 0 bytes after 16 byte block allocated at ... blah blah". Basically, it thinks that various accesses are overruns, possibly due to there being no red zones between the blocks. Its quite baffling.
Maybe current Valgrind has fixes for some of this; I just use what distros package.