5 ms·

This reminds me of a GDC talk where rust was praised because it forces you to either go mad because of the borrow checker or structure code using an entity comp

This reminds me of a GDC talk where rust was praised because it forces you to either go mad because of the borrow checker or structure code using an entity component system. I find it funny that the value of the borrow checker in all these real world scenarios with complicated lifetimes is to find a way to avoid it entirely by putting stuff in arrays and reference them by their index.

PartiallyTyped 3y ago
You could say that it forces you to define long living entities that own memory and lend it to short-lived objects. 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.
- eyelidlessness 3y ago
  It’s almost as if immutability writ large is vindicated, but with a whole lot of complicated rules to let mutation infect everything everywhere even if you’ll never use it. At least that was my takeaway trying to learn Rust.
  - Flow 3y ago
    Do you think a purely functional language without GC would be much simpler than Rust and Rust's borrow checker? I don't think the mutation part of Rust is what makes it complicated.
    - eyelidlessness 3y ago
      It’s very possible there’s something I’m missing, but my instinct is: yes, it very probably would. If data can be presumed immutable, a whole lot of ownership rules could be relaxed to scope and cycle counts which could be verified at compile time with no runtime penalty. The whole premise that data needs to be borrowed is explicitly to guard against conflicting views of shared state. Such conflicts can only arise by mutability of shared state. Rust’s solution to that is to limit mutability to only one part of a procedure at a given time. If nothing can mutate state at any point in a program’s lifecycle, that tradeoff can be expanded to basically whatever facilities the hardware/compile target affords.
  - c_crank 3y ago
    Ada has better tools for the task if mutability is allowed.
- verdagon 3y ago
  Ironically, we could say that we're losing the true ownership relationships between the objects, and we're making medium-term memory leaks more likely; drop() can free a Box pointing to a child, but can't free an index. In other words, we lose the guarantee that an element is released for reuse. 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. [0] https://verdagon.dev/blog/higher-raii-7drl https://verdagon.dev/blog/higher-raii-7drl [1] https://austral-lang.org/linear-types https://austral-lang.org/linear-types
  - PartiallyTyped 3y ago
    Re linear types, Rust actually has an affine typesystem, and the compiler complains when you move a variable and try to access it, so instead you need to provide a reference if you intend to do that multiple times. 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.
- jlokier 3y ago
  > In the process you avoid use-after-free, double-free, and accessing unallocated memory 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.
  - avgcorrection 3y ago
    > These are memory-unsafety bugs. 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.
    - kmstout 3y ago
      > nothing to do with the memory allocator It's an application-specific memory allocator.
      - avgcorrection 3y ago
        That’s in effect what I’m saying. You’ve implemented a memory allocator using the “system” one.
  - PartiallyTyped 3y ago
    That's the specific case of (mis)using an arena, no? Could this be extended to the general model of ownership?
  - 3y ago
dist1ll 3y ago
Correct. Rust lifetimes become less powerful in certain niches of high-performance programming where you're avoiding the heap or don't have one in the first place. Games, databases, embedded, HPC-style batch workloads, and even compilers. 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.
- pornel 3y ago
  Note that you still have implicit/elided lifetimes for basically every function argument and every local variable. They’re everywhere, even if you’re not typing 'a.
noelwelsh 3y ago
Using an entity component system felt like writing very fancy spaghetti code in my limited experience with the Bevy game engine in Rust. No longer having direct references between objects means the type system isn't nearly as useful and I found it very hard to reason about the code. I can believe it becomes useful in very large systems but it was just a hinderance in the small program I was writing.
- logicchains 3y ago
  You can use phantom-typed index types (a wrapper type per container) to recover type safety. Or at least you can when using an ECS in C++; I'm not sure how easy it is to write the wrapper types generically in Rust.
  - pornel 3y ago
    You can have typed indices (https://lib.rs/crates/typed-index-collections https://lib.rs/crates/typed-index-collections), but unless you force the collection to be a singleton, there's no way to prevent mixing of indices between different instances (clones) of the same collection type.
- syntheweave 3y ago
  A lot of the mangling produced by ECS is an outcome of representing dynamic behaviors through static optimizations. 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.
bregma 3y ago
Pointers are just indexes into memory space. Seems to me that if Rust is trying to solve a general programming problem the borrow checker needs to handle all indexes, not just those specialized for memory space.
- dist1ll 3y ago
  I feel that for this to be really viable, Rust would have to allow references that consume less memory (like 8-bit or 16-bit pointers).
chubot 3y ago
Yes totally, I keep seeing people mention these arena / flattened tree and graph structures, without mentioning memory safety. 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/1350dfw/flattening_asts_and_other_compiler_data_structures/jiid1mb/ 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-Representation https://github.com/oilshell/oil/wiki/Compact-AST-Representat...
- kazinator 3y ago
  > when it's equally likely (depending on the program) that they CAUSE dangling pointers 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.

PartiallyTyped 3y ago

You could say that it forces you to define long living entities that own memory and lend it to short-lived objects. 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.

eyelidlessness 3y ago
It’s almost as if immutability writ large is vindicated, but with a whole lot of complicated rules to let mutation infect everything everywhere even if you’ll never use it. At least that was my takeaway trying to learn Rust.
- Flow 3y ago
  Do you think a purely functional language without GC would be much simpler than Rust and Rust's borrow checker? I don't think the mutation part of Rust is what makes it complicated.
  - eyelidlessness 3y ago
    It’s very possible there’s something I’m missing, but my instinct is: yes, it very probably would. If data can be presumed immutable, a whole lot of ownership rules could be relaxed to scope and cycle counts which could be verified at compile time with no runtime penalty. The whole premise that data needs to be borrowed is explicitly to guard against conflicting views of shared state. Such conflicts can only arise by mutability of shared state. Rust’s solution to that is to limit mutability to only one part of a procedure at a given time. If nothing can mutate state at any point in a program’s lifecycle, that tradeoff can be expanded to basically whatever facilities the hardware/compile target affords.
- c_crank 3y ago
  Ada has better tools for the task if mutability is allowed.
verdagon 3y ago
Ironically, we could say that we're losing the true ownership relationships between the objects, and we're making medium-term memory leaks more likely; drop() can free a Box pointing to a child, but can't free an index. In other words, we lose the guarantee that an element is released for reuse. 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. [0] https://verdagon.dev/blog/higher-raii-7drl https://verdagon.dev/blog/higher-raii-7drl [1] https://austral-lang.org/linear-types https://austral-lang.org/linear-types
- PartiallyTyped 3y ago
  Re linear types, Rust actually has an affine typesystem, and the compiler complains when you move a variable and try to access it, so instead you need to provide a reference if you intend to do that multiple times. 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.
jlokier 3y ago
> In the process you avoid use-after-free, double-free, and accessing unallocated memory 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.
- avgcorrection 3y ago
  > These are memory-unsafety bugs. 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.
  - kmstout 3y ago
    > nothing to do with the memory allocator It's an application-specific memory allocator.
    - avgcorrection 3y ago
      That’s in effect what I’m saying. You’ve implemented a memory allocator using the “system” one.
- PartiallyTyped 3y ago
  That's the specific case of (mis)using an arena, no? Could this be extended to the general model of ownership?
- 3y ago

dist1ll 3y ago

Correct. Rust lifetimes become less powerful in certain niches of high-performance programming where you're avoiding the heap or don't have one in the first place. Games, databases, embedded, HPC-style batch workloads, and even compilers. 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.

pornel 3y ago
Note that you still have implicit/elided lifetimes for basically every function argument and every local variable. They’re everywhere, even if you’re not typing 'a.

noelwelsh 3y ago

Using an entity component system felt like writing very fancy spaghetti code in my limited experience with the Bevy game engine in Rust. No longer having direct references between objects means the type system isn't nearly as useful and I found it very hard to reason about the code. I can believe it becomes useful in very large systems but it was just a hinderance in the small program I was writing.

logicchains 3y ago
You can use phantom-typed index types (a wrapper type per container) to recover type safety. Or at least you can when using an ECS in C++; I'm not sure how easy it is to write the wrapper types generically in Rust.
- pornel 3y ago
  You can have typed indices (https://lib.rs/crates/typed-index-collections https://lib.rs/crates/typed-index-collections), but unless you force the collection to be a singleton, there's no way to prevent mixing of indices between different instances (clones) of the same collection type.
syntheweave 3y ago
A lot of the mangling produced by ECS is an outcome of representing dynamic behaviors through static optimizations. 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.

bregma 3y ago

Pointers are just indexes into memory space. Seems to me that if Rust is trying to solve a general programming problem the borrow checker needs to handle all indexes, not just those specialized for memory space.

dist1ll 3y ago
I feel that for this to be really viable, Rust would have to allow references that consume less memory (like 8-bit or 16-bit pointers).

chubot 3y ago

Yes totally, I keep seeing people mention these arena / flattened tree and graph structures, without mentioning memory safety. 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/1350dfw/flattening_asts_and_other_compiler_data_structures/jiid1mb/ 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-Representation https://github.com/oilshell/oil/wiki/Compact-AST-Representat...

kazinator 3y ago
> when it's equally likely (depending on the program) that they CAUSE dangling pointers 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.