4 ms·

There's some exciting work already going on in this space, in fact! * Andrew Kelley is looking into combining escape analysis with allocators to assist in Zig'

There's some exciting work already going on in this space, in fact! * Andrew Kelley is looking into combining escape analysis with allocators to assist in Zig's memory safety. [0] It could be quite a step forward! * D is adding a borrow checker! [1] * Cone is adding a borrow checker on top of user-definable allocators. [2] * We're currently prototyping a region-based borrow checker [3] for Vale, which should get us most of the benefit of Rust's borrow checker with only a fraction of the complexity. It's opt-in, not upwardly infectious, and can stay near the "computational leaves" of one's program. [0] https://news.ycombinator.com/item?id=31853964 https://news.ycombinator.com/item?id=31853964 [1] https://dlang.org/changelog/2.092.0.html#ob https://dlang.org/changelog/2.092.0.html#ob [2] https://cone.jondgoodwin.com/memory.html https://cone.jondgoodwin.com/memory.html [3] https://verdagon.dev/blog/zero-cost-refs-regions https://verdagon.dev/blog/zero-cost-refs-regions

pcwalton 4y ago
It sounds like the "region borrow checker" is fundamentally based on reference counting, which makes it a garbage collected system. Also, statically eliminating reference count traffic from the stack isn't new; it goes back to Deutsch and Bobrow 1976. Actually, I suggest reading the paper; it seems like a quite similar system [1]. [1]: https://www.memorymanagement.org/bib.html#db76 https://www.memorymanagement.org/bib.html#db76
- verdagon 4y ago
  The region borrow checker was originally designed for a reference-counted system, but not any more. We later discovered generational references, a method for memory-safe single ownership with no borrow checker, reference counting, nor garbage collection. To our delight, the region borrow checker works even better with generational references than with reference counting =)
  - deleted 4y ago
    [deleted]
  - zozbot234 4y ago
    Generational references are best seen as an alternative to RC that makes different tradeoffs. They add overhead to reads/writes thru the managed reference, as opposed to the overhead for changes in ownership you see wrt. RC/ARC in something like Rust. (Note that other languages like C++ or Swift cannot cleanly separate ownership changes to the same extent as Rust, so their overhead is ultimately a lot higher. Especially Swift, with its ARC-for-everything approach.) They look like they might be good complementary approaches.
    - Nomentatus 4y ago
      I'd be curious as to whether my comment here hypothesizing an AI wizard stikes you as "just nuts", or not.
  - glowcoil 4y ago
    Frankly it seems strange to me to be comparing Vale's generational reference system and Rust's borrow checker directly. They have completely different characteristics and are not direct substitutes for one another. First, Rust's borrow checker incurs zero runtime overhead for any pointer operations (whether dereferencing, copying, or dropping a pointer) and requires no extra storage at runtime (no reference counts or generation numbers); it's entirely a set of compile-time checks. Generational references, on the other hand, require storing an extra piece of data alongside both every heap allocation and every non-owning reference, and they incur an extra operation at every dereference. Second, since Rust's borrow checker exists entirely at compile time, it doesn't introduce any runtime failures. If a program violates the rules of the borrow checker, it won't compile; if a program compiles successfully, the borrow checker does not insert any conditional runtime panics or aborts. Generational references, in comparison, consist entirely of a set of runtime checks; you won't found out if you violated the rules of generational references until it happens at runtime during a particular execution and your program crashes. Finally, Rust's borrow checker applies to references of all kinds, whether they point to a heap-allocated object, a stack-allocated object, an inline field inside a larger allocation, a single entry in an array, or even an object allocated on a different heap and passed over FFI. Its checks still apply even in scenarios where there is no heap. Generational references, on the other hand, are entirely specific to heap-allocated objects. They don't work for stack-allocated objects, they don't work for foreign objects allocated on a different heap, and they don't work in a scenario with no heap at all. All of these are fundamental differences which mean that Vale's generational reference system is not at all a replacement for Rust's borrow checker. It's not zero-overhead, it doesn't catch errors at compile time, and it's fundamentally specific to heap-allocated objects. In these ways it's more comparable to Rust's Rc, which introduces runtime overhead and is specific to heap-allocated objects, or RefCell, which performs checks at runtime that can result in aborting the program.
- fancl20 4y ago
  It doesn’t have to. If your allocator is the first-class citizen in the language, simply check the allocated memory when allocator itself is manually destroyed (exit its region) is enough for detecting memory leak.
- hayley-patton 4y ago
  Borrowing, in a way, looks a bit like the anchored pointers suggested by Henry Baker in [1]. I recall reading someone did a static analysis to detect what pointers could be anchored, but forgot which someone. However the "deferral" suggested is very different to the Deutsch-Bobrow deferral; what makes me think it is more like borrowing is that anchoring avoids destruction due to linear types, like borrowing avoids moving or copying. (Regions in Cyclone would be somewhere in between, too.) [1] https://plover.com/~mjd/misc/hbaker-archive/LRefCounts.html https://plover.com/~mjd/misc/hbaker-archive/LRefCounts.html
dunefox 4y ago
D is adding everything, it seems.
- Matl 4y ago
  I wonder if that could actually be hindering its adoption. I think the 'kitchen sink' C++ style is not so popular anymore.
  - Tozen 4y ago
    When it comes to language popularity, we have to keep in mind that D is way more popular than so-called up and coming languages (where it's oddly ignored they came out many years ago) such as Zig, Nim, Crystal, etc... Dlang often floats around the top #30 in the TIOBE rankings. It really is a very tough hill to climb to crack the top 10 among languages. Relatively speaking, D has done well for itself, and arguably is in the position to climb further up and possibly be in the top 20 of language rankings. Have seen a lot of talk and theories about why D didn't or hasn't become more popular. Some of them have to do with circumstances, not just about the number of features. For instance, Dlang's DMD reference compiler was under license restrictions by Symantec, which wasn't changed until 2017 (now it's under the commercial friendly Boost license). A lot of companies and corporate sponsors get leery about licensing issues. There were also early squabbles about API design, like Tango versus Phobos, which are mostly resolved these days. But, years ago, it was less clear about the direction or how it would get sorted out. D, as a contender to climb even higher up the language ranking charts, is still a strong possibility. D might even remain and always be more popular than Zig will ever be (especially if it wants to fight and die on the more syntactically complex "better C" hill), despite this view on D adding so much. Which could even be more of a selling point (kitchen sink included), than an hindrance, and particularity as an already established and developed older language.
    - dunefox 4y ago
      If D is in the top 30 of languages according to these rankings that just shows how flawed they are.
Nomentatus 4y ago
Fascinating (and heartening.) I wonder whether this work takes us any way toward an AI wizard "in between" Rust and Zig (say) as I've described in a longer comment here. Am I nuts to hope for such a thing?

pcwalton 4y ago

It sounds like the "region borrow checker" is fundamentally based on reference counting, which makes it a garbage collected system. Also, statically eliminating reference count traffic from the stack isn't new; it goes back to Deutsch and Bobrow 1976. Actually, I suggest reading the paper; it seems like a quite similar system [1]. [1]: https://www.memorymanagement.org/bib.html#db76 https://www.memorymanagement.org/bib.html#db76

verdagon 4y ago
The region borrow checker was originally designed for a reference-counted system, but not any more. We later discovered generational references, a method for memory-safe single ownership with no borrow checker, reference counting, nor garbage collection. To our delight, the region borrow checker works even better with generational references than with reference counting =)
- deleted 4y ago
  [deleted]
- zozbot234 4y ago
  Generational references are best seen as an alternative to RC that makes different tradeoffs. They add overhead to reads/writes thru the managed reference, as opposed to the overhead for changes in ownership you see wrt. RC/ARC in something like Rust. (Note that other languages like C++ or Swift cannot cleanly separate ownership changes to the same extent as Rust, so their overhead is ultimately a lot higher. Especially Swift, with its ARC-for-everything approach.) They look like they might be good complementary approaches.
  - Nomentatus 4y ago
    I'd be curious as to whether my comment here hypothesizing an AI wizard stikes you as "just nuts", or not.
- glowcoil 4y ago
  Frankly it seems strange to me to be comparing Vale's generational reference system and Rust's borrow checker directly. They have completely different characteristics and are not direct substitutes for one another. First, Rust's borrow checker incurs zero runtime overhead for any pointer operations (whether dereferencing, copying, or dropping a pointer) and requires no extra storage at runtime (no reference counts or generation numbers); it's entirely a set of compile-time checks. Generational references, on the other hand, require storing an extra piece of data alongside both every heap allocation and every non-owning reference, and they incur an extra operation at every dereference. Second, since Rust's borrow checker exists entirely at compile time, it doesn't introduce any runtime failures. If a program violates the rules of the borrow checker, it won't compile; if a program compiles successfully, the borrow checker does not insert any conditional runtime panics or aborts. Generational references, in comparison, consist entirely of a set of runtime checks; you won't found out if you violated the rules of generational references until it happens at runtime during a particular execution and your program crashes. Finally, Rust's borrow checker applies to references of all kinds, whether they point to a heap-allocated object, a stack-allocated object, an inline field inside a larger allocation, a single entry in an array, or even an object allocated on a different heap and passed over FFI. Its checks still apply even in scenarios where there is no heap. Generational references, on the other hand, are entirely specific to heap-allocated objects. They don't work for stack-allocated objects, they don't work for foreign objects allocated on a different heap, and they don't work in a scenario with no heap at all. All of these are fundamental differences which mean that Vale's generational reference system is not at all a replacement for Rust's borrow checker. It's not zero-overhead, it doesn't catch errors at compile time, and it's fundamentally specific to heap-allocated objects. In these ways it's more comparable to Rust's Rc, which introduces runtime overhead and is specific to heap-allocated objects, or RefCell, which performs checks at runtime that can result in aborting the program.
fancl20 4y ago
It doesn’t have to. If your allocator is the first-class citizen in the language, simply check the allocated memory when allocator itself is manually destroyed (exit its region) is enough for detecting memory leak.
hayley-patton 4y ago
Borrowing, in a way, looks a bit like the anchored pointers suggested by Henry Baker in [1]. I recall reading someone did a static analysis to detect what pointers could be anchored, but forgot which someone. However the "deferral" suggested is very different to the Deutsch-Bobrow deferral; what makes me think it is more like borrowing is that anchoring avoids destruction due to linear types, like borrowing avoids moving or copying. (Regions in Cyclone would be somewhere in between, too.) [1] https://plover.com/~mjd/misc/hbaker-archive/LRefCounts.html https://plover.com/~mjd/misc/hbaker-archive/LRefCounts.html

dunefox 4y ago

D is adding everything, it seems.

Matl 4y ago
I wonder if that could actually be hindering its adoption. I think the 'kitchen sink' C++ style is not so popular anymore.
- Tozen 4y ago
  When it comes to language popularity, we have to keep in mind that D is way more popular than so-called up and coming languages (where it's oddly ignored they came out many years ago) such as Zig, Nim, Crystal, etc... Dlang often floats around the top #30 in the TIOBE rankings. It really is a very tough hill to climb to crack the top 10 among languages. Relatively speaking, D has done well for itself, and arguably is in the position to climb further up and possibly be in the top 20 of language rankings. Have seen a lot of talk and theories about why D didn't or hasn't become more popular. Some of them have to do with circumstances, not just about the number of features. For instance, Dlang's DMD reference compiler was under license restrictions by Symantec, which wasn't changed until 2017 (now it's under the commercial friendly Boost license). A lot of companies and corporate sponsors get leery about licensing issues. There were also early squabbles about API design, like Tango versus Phobos, which are mostly resolved these days. But, years ago, it was less clear about the direction or how it would get sorted out. D, as a contender to climb even higher up the language ranking charts, is still a strong possibility. D might even remain and always be more popular than Zig will ever be (especially if it wants to fight and die on the more syntactically complex "better C" hill), despite this view on D adding so much. Which could even be more of a selling point (kitchen sink included), than an hindrance, and particularity as an already established and developed older language.
  - dunefox 4y ago
    If D is in the top 30 of languages according to these rankings that just shows how flawed they are.

Nomentatus 4y ago

Fascinating (and heartening.) I wonder whether this work takes us any way toward an AI wizard "in between" Rust and Zig (say) as I've described in a longer comment here. Am I nuts to hope for such a thing?