Allocgate: Restructuring how allocators work in Zig(pithlessly.github.io)
pithlessly.github.io
Allocgate: Restructuring how allocators work in Zig
https://pithlessly.github.io/allocgate.html
51 comments
This was a fantastic, thorough explanation, thank you for putting in the effort!
This is an example of how certain optimizations (specifically, making vtables immutable) are hard in LLVM, because of how low-level it is. Language-specific high-level IRs, such as Swift SIL, can allow compilers to perform these kinds of optimizations more easily. Of course, they're a lot of work to implement.
It's true that language specific IRs are more powerful, but that isn't the problem in this example. Interfaces aren't part of Zig at the language level, nor are object lifetimes over which to make the vtables immutable. Having a memory model where memory is not innately typed is what makes this problem difficult to optimize, the IR has very little to do with it.
> a memory model where memory is not innately typed
This is intriguing. Do you have examples of systems where memory is typed? Or some ideas?
This is intriguing. Do you have examples of systems where memory is typed? Or some ideas?
Memory is typed in C++. You must use placement new to imbue memory with a non-POD type, and that memory continues to have that type until its destructor is invoked. This is what allows the optimizer to assume that vtable pointers don't change while an object is alive.
Effects of the typedness of memory can also be seen in the strict aliasing rules. Once a piece of memory has taken on a type, it may no longer be aliased by pointers of different types, until the memory is relinquished back into typelessness by a destructor.
Effects of the typedness of memory can also be seen in the strict aliasing rules. Once a piece of memory has taken on a type, it may no longer be aliased by pointers of different types, until the memory is relinquished back into typelessness by a destructor.
thanks!
BitC used a strictly typed memory model.
Are there performance worries about passing around two pointers for anything that needs to allocate, as well as storing these pointers in a struct? AFAICT this basically means two registers are eaten, and a lot of types have effectively 16 bytes of overhead. It seems like this could quickly change the calculus on what fits within cache lines and what doesn't, which people often care about for very high performance code.
I wonder if it's possible to change the compiler to detect that, if what is being used in arguments is the global default allocator, the first argument can be stripped and all references inside the function can be replaced with the global pointer. Potentially the same concept could apply to allocators that use thread local storage. (perhaps these optimizations already exist?)
I wonder if it's possible to change the compiler to detect that, if what is being used in arguments is the global default allocator, the first argument can be stripped and all references inside the function can be replaced with the global pointer. Potentially the same concept could apply to allocators that use thread local storage. (perhaps these optimizations already exist?)
This is a worry, but it's not as bad as you might initially think. The first thing to notice is that even though the "interface pointer" got fatter, the implementation got much leaner, as it no longer contains the vtable. Vtables are now shared between instances of the same type, so total memory use has gone down, and implementations can be packed more densely. If you're worried about overall cache usage, this is a net positive. The first load, from the fat pointer, is very likely to be in cache. The second load, from the vtable, will be in cache if you have used the same type recently. Which is likely if you have thousands of objects, you probably do not have thousands of implementations.
There is some additional latency because the virtual function load is now two pointer dereferences instead of one. However, C++ and Go both use double-dereference models like this, and it seems to be working fine for them. Additionally, if virtual calls like this are on your critical fast path, you have bigger problems :P
There is some additional latency because the virtual function load is now two pointer dereferences instead of one. However, C++ and Go both use double-dereference models like this, and it seems to be working fine for them. Additionally, if virtual calls like this are on your critical fast path, you have bigger problems :P
I believe that "devirtualization"--the optimization mentioned in the OP--will do exactly what you're describing, by rewriting the virtual function call as a static call to the allocator when the vtable can be determined from the callsite at compile-time.
Does anyone know if RAII types will ever be a thing in Zig?
It's unlikely. RAII comes with a surprising amount of complexity. In order to have a reasonably complete language that has RAII and value types, you must also have:
- constructors
- destructors
- overloadable copy assignment operators
- placement new
- move semantics and rvalue references
These features come together or not at all. If you lose any of them, the language becomes less complete. I think Rust and C++ are doing a fine job of exploring the design space of languages that have this feature set, but it's too much complexity for Zig.
Edit: As commenters have pointed out, this exact manifestation of these features is not required. A more correct set of requirements is:
- a notion of beginning and ending object lifetimes in existing memory
- a notion of move semantics to relocate an existing RAII object
- a notion of non-copyability for certain types, or an ability to override copy behavior
- constructors
- destructors
- overloadable copy assignment operators
- placement new
- move semantics and rvalue references
These features come together or not at all. If you lose any of them, the language becomes less complete. I think Rust and C++ are doing a fine job of exploring the design space of languages that have this feature set, but it's too much complexity for Zig.
Edit: As commenters have pointed out, this exact manifestation of these features is not required. A more correct set of requirements is:
- a notion of beginning and ending object lifetimes in existing memory
- a notion of move semantics to relocate an existing RAII object
- a notion of non-copyability for certain types, or an ability to override copy behavior
Rust doesn't end up with an overloadable copy assignment operator, it does something else which I would argue is cleverer (although you can't just add it to an existing language)
Because Rust knows the lifetime of everything in your program (in Rust the lifetime of things is part of their type) the effect of the assignment operator = is to dispose of whatever was in the variable before, and move the assigned item into the variable.
Rust's Copy trait does not alter the semantics of the assignment operators - you can't overload that. You promise that your type's in-memory representation is all that matters, and then if you move from a variable the value in that variable is still live even though there was a copy made, usually that value would be dead because it was moved from.
Rust's Clone trait behaves a little like a C++ copy constructor, except, it's an explicit trait, the only way to get a clone of x is to x.clone() or various moral equivalents e.g. Clone::clone(&x); so you're not getting one without explicitly asking for it.
Rust doesn't formally have Constructors, or from another perspective, any Rust code anywhere which wants to make a Thing, is a "Constructor" for that Thing. (safe) Rust won't let you do any of the shenanigans which is common in C++ like having two separate pieces of code share responsibility for initialising a data structure, in Rust when you make a Thing you need to explicitly set all the values in the Thing at once, if the easy way to write that involves temporaries, no matter the compiler does have an optimiser and knows how to use it.
It is idiomatic in Rust to provide a function named new() in the implementation of a structure which will make you one of that structure if doing so makes sense, but that function and its name aren't magic, it's just a convention. Rust's vector type Vec has a new() function but it also has a with_capacity(n) function, they're both "Constructors" in the C++ sense if you want to think about it that way, with_capacity() isn't calling new() to make the vector, that would be crazy.
Because Rust knows the lifetime of everything in your program (in Rust the lifetime of things is part of their type) the effect of the assignment operator = is to dispose of whatever was in the variable before, and move the assigned item into the variable.
Rust's Copy trait does not alter the semantics of the assignment operators - you can't overload that. You promise that your type's in-memory representation is all that matters, and then if you move from a variable the value in that variable is still live even though there was a copy made, usually that value would be dead because it was moved from.
Rust's Clone trait behaves a little like a C++ copy constructor, except, it's an explicit trait, the only way to get a clone of x is to x.clone() or various moral equivalents e.g. Clone::clone(&x); so you're not getting one without explicitly asking for it.
Rust doesn't formally have Constructors, or from another perspective, any Rust code anywhere which wants to make a Thing, is a "Constructor" for that Thing. (safe) Rust won't let you do any of the shenanigans which is common in C++ like having two separate pieces of code share responsibility for initialising a data structure, in Rust when you make a Thing you need to explicitly set all the values in the Thing at once, if the easy way to write that involves temporaries, no matter the compiler does have an optimiser and knows how to use it.
It is idiomatic in Rust to provide a function named new() in the implementation of a structure which will make you one of that structure if doing so makes sense, but that function and its name aren't magic, it's just a convention. Rust's vector type Vec has a new() function but it also has a with_capacity(n) function, they're both "Constructors" in the C++ sense if you want to think about it that way, with_capacity() isn't calling new() to make the vector, that would be crazy.
Worth noting that even though Rust doesn't let you have two separate pieces of code share responsibility for actually initializing a data structure, in practice that doesn't lead to much, if any, code duplication: a Foo::new() can usually be written as a wrapper around a call to Foo::new_with_options(x, y, z).
> In order to have a reasonably complete language that has RAII and value types, you must also have: - constructors - destructors - overloadable copy assignment operators - placement new - move semantics and rvalue references
Rust has RAII and value types, and does not have constructors, overloadable copy assignment operators, placement new, or rvalue references (though we do of course have a very similar notion to rvalue/lvalue in general, but that's not the same thing as "rvalue references" with relation to all of this). While it has move semantics, they're significantly different.
Rust has RAII and value types, and does not have constructors, overloadable copy assignment operators, placement new, or rvalue references (though we do of course have a very similar notion to rvalue/lvalue in general, but that's not the same thing as "rvalue references" with relation to all of this). While it has move semantics, they're significantly different.
I don't mean that these things need to manifest in exactly the same way as they do in C++, but analagous features are needed. You're right that rvalue references are not necessary, but some form of move semantics are. When I say constructors and destructors, I am really referring to having a concept of object lifetimes as part of the language. Zig does not have this, and is much simpler because of it.
Edit: to clarify, the thing that makes a constructor/destructor useful in this case is the property that it begins/ends an object lifetime according to the language. This lifetime reasoning certainly has benefits, like the ability to have const fields in C++ and the ability to do static checking of lifetimes in Rust. However it also comes with significant complexity, because move semantics are needed throughout the language, and begin/end lifetime tags are needed when implementing data structures that use preallocated backing arrays.
Edit: to clarify, the thing that makes a constructor/destructor useful in this case is the property that it begins/ends an object lifetime according to the language. This lifetime reasoning certainly has benefits, like the ability to have const fields in C++ and the ability to do static checking of lifetimes in Rust. However it also comes with significant complexity, because move semantics are needed throughout the language, and begin/end lifetime tags are needed when implementing data structures that use preallocated backing arrays.
Hm, personally I consider "object lifetimes exist" to be completely different than "constructors", which are a hook into a specific point in some sort of object lifetime cycle. Rust doesn't have the hook, so it doesn't have the feature. Note that I didn't put destructors on my list; the Drop trait does exist in Rust and is the same general idea as destructors.
I guess that basically, to me at least, if you've stretched the definitions of these features far enough to include what Rust does, you don't really have a meaningful definition any more.
I guess that basically, to me at least, if you've stretched the definitions of these features far enough to include what Rust does, you don't really have a meaningful definition any more.
However the Drop trait still has some safety issues, right?
It appears to be more like Ada's Unchecked_Deallocation as it comes with some "use with care" footnotes.
I remember reading something about it.
It appears to be more like Ada's Unchecked_Deallocation as it comes with some "use with care" footnotes.
I remember reading something about it.
Not exactly, or at least, not in the same way as Unchecked_Deallocation. There are no memory safety issues with Drop. There are a few times when you need to be a little careful so that you don't get bad behavior: recursive Drop can stack overflow (which is caught and aborts), Drop while Dropping aborts which may not be what you want, if you've written unsafe code, you need to be careful with Drop because what is valid and what isn't may be a bit more tricky since it's effectively a callback.
I see, then I misunderstood whatever was related to Drop and not being fully stable.
Yeah stack overflow can also be an issue on other RAII approaches.
Yeah stack overflow can also be an issue on other RAII approaches.
Hm yeah, on the "not fully stable" angle, there's also some talk about "async drop," which doesn't exist just yet, and would be useful in async contexts. Maybe that's what it was.
That's a fair criticism, I think C++ blurs a lot of lines that make these things difficult to talk about in isolation, and I'm still working on being more rigorous about picking them apart correctly. The very specific complexity at the core of it all is the fact that you need something like placement new to begin a lifetime in memory that is already allocated. Copying the object representation of an initialization template is insufficient in general, you have to use a specific tag to say "the life of a new object starts here", which has no direct analogy to anything the hardware does. It's not necessarily important that the programmer can hook into this like a C++ constructor, but the tag needs to be there. This is something that can be very difficult for programmers to get right in languages that aren't Rust, because the compiler does no verification of it. If you do it wrong, everything works in debug, but then things may break in release because the optimizer performed incorrect alias analysis or detected unconditional UB. But they might work correctly, you may not notice for years until a more powerful optimizer comes along. Since we don't plan to validate lifetimes (Rust is a great language that already does that if it's important to your goals), we would like to avoid this sort of strict object model as much as possible.
When you add RAII on top of lifetimes as a language feature, it creates the need for language support for moves and specialized copies. Or a need to say that types cannot be copied. But you need some sort of tag that says "memcpy doesn't cut it anymore", which is what I mean by overridable copy behavior.
When you add RAII on top of lifetimes as a language feature, it creates the need for language support for moves and specialized copies. Or a need to say that types cannot be copied. But you need some sort of tag that says "memcpy doesn't cut it anymore", which is what I mean by overridable copy behavior.
> That's a fair criticism, I think...
Totally, and I wouldn't be so pedantic here myself if I didn't think it was on-topic: Zig, Rust, and C++ all choose different amounts of complexity on these axes. I think that Rust's RAII is closer to Zig's lack of it than C++'s implementation of it in terms of overall complexity, but that the feature exists at all in Rust is significant. All of that should come as no surprise. :)
> The very specific complexity at the core of it all is the fact that you need something like placement new to begin a lifetime in memory that is already allocated.
By this definition, Rust doesn't have RAII. Placement new does not currently exist in the language. This is possible because we do not have constructors, and therefore don't need (on the language level, I'll come back to this momentarily) the need to do this. It does mean that, as you've noted, copying it is possible, and this is what happens in Rust. Optimizers can elide this copy but aren't guaranteed to. But the need to eliminate this single copy hasn't been big enough to actually get placement new over the finish line in Rust, even though at one point it felt critical to even shipping 1.0.
Totally, and I wouldn't be so pedantic here myself if I didn't think it was on-topic: Zig, Rust, and C++ all choose different amounts of complexity on these axes. I think that Rust's RAII is closer to Zig's lack of it than C++'s implementation of it in terms of overall complexity, but that the feature exists at all in Rust is significant. All of that should come as no surprise. :)
> The very specific complexity at the core of it all is the fact that you need something like placement new to begin a lifetime in memory that is already allocated.
By this definition, Rust doesn't have RAII. Placement new does not currently exist in the language. This is possible because we do not have constructors, and therefore don't need (on the language level, I'll come back to this momentarily) the need to do this. It does mean that, as you've noted, copying it is possible, and this is what happens in Rust. Optimizers can elide this copy but aren't guaranteed to. But the need to eliminate this single copy hasn't been big enough to actually get placement new over the finish line in Rust, even though at one point it felt critical to even shipping 1.0.
Ah interesting, yeah I suppose if we define "RAII" as just "automatically invoked configurable cleanup", there's no actual need to mark the beginning of the lifetime. All you need is to mark the end of the lifetime. This needs to be possible both from the language (for stack variables) and from user code (for ArrayList implementations). So you need something like a placement delete or explicit destructor invocation, but not necessarily a placement new or explicit creation.
I think I mix these up because placement new is necessary to have a concept of const fields that is meaningful to the optimizer. This would have been an alternate solution to the original vtable problem, but requires lifetimes over which the field is const. I had RAII categorized as another feature that required lifetimes, but I suppose it requires a less strict definition of lifetimes than is needed for const fields.
I think I mix these up because placement new is necessary to have a concept of const fields that is meaningful to the optimizer. This would have been an alternate solution to the original vtable problem, but requires lifetimes over which the field is const. I had RAII categorized as another feature that required lifetimes, but I suppose it requires a less strict definition of lifetimes than is needed for const fields.
> In order to have a reasonably complete language that has RAII and value types, you must also have: - constructors - destructors - overloadable copy assignment operators - placement new - move semantics and rvalue references
C++ didn't have move semantics at all until several decades after it had RAII.
C++ didn't have move semantics at all until several decades after it had RAII.
Yes, move semantics were added because the language was considered incomplete without them. In particular, because RAII based resources like std::vector could not be relocated without very expensive value copy operations.
Only C++ has all of what you mention. Plenty of languages provide RAII without introducing all that complexity such as Ada, Rust, Vale. D has RAII but unfortunately it too carries much (but not all) of the complexity of C++.
`defer` and `errdefer` give you 90% of what destructors & co give you for 0% of the complexity.
For now the the closest thing to RAII is this proposal, but there is no guarantee that it will be accepted.
https://github.com/ziglang/zig/issues/782
For now the the closest thing to RAII is this proposal, but there is no guarantee that it will be accepted.
https://github.com/ziglang/zig/issues/782
I find in C++ at least reasoning about RAII is always surprisingly complex. The second you have to write a custom destructor you get into the weeds of reasoning about copy/move/copy-assignment etc.
https://en.cppreference.com/w/cpp/language/rule_of_three
C++ RAII also rubs up painfully against handle based APIs (looking at you Windows) in my experience. There is a lack of standardized RAII wrappers for handle types like there is for pointers. Yes you can pull in a custom handle RAII wrapper but at that point it's simpler to just manage manually.
Defer on the other hand is simple. Anyone can understand it in five minutes.
https://en.cppreference.com/w/cpp/language/rule_of_three
C++ RAII also rubs up painfully against handle based APIs (looking at you Windows) in my experience. There is a lack of standardized RAII wrappers for handle types like there is for pointers. Yes you can pull in a custom handle RAII wrapper but at that point it's simpler to just manage manually.
Defer on the other hand is simple. Anyone can understand it in five minutes.
> There is a lack of standardized RAII wrappers for handle types like there is for pointers.
.. what's wrong with
.. what's wrong with
#include <memory>
template<typename T, auto Free>
using safe_handle_t = std::unique_ptr<T, decltype([] (auto p) { Free(p); })>;
using file_handle = safe_handle_t<FILE, fclose>;
void file_example() {
file_handle f{fopen("foo", "r")};
}That's what I do as well. Many people are not aware that std::unique_ptr can do more than just manage heap memory.
Now you have a double indirection. Worse, the handle probably already references dynamically allocated memory. So that’s two dynamic memory allocations per “safe” handle. Which might be perfectly acceptable for non-critical programs, but it is certainly going to tank your memory usage efficiency and thrash your CPU cache if scaled up to millions of handles.
This is entirely wrong.
This produces exactly the same code than
auto f = fopen("foo", "r");
if(f)
fclose(f);
There is no double indirection and allocation here, it stores the FILE* directly, not as a pointer to a FILE*.
I'm pinning my hopes that certain types can be marked as "shared resources", either in-lang, or through a minimalistic helper tool - and analyzed at a lower level (ZIR or AIR) for lifetime analysis.
When people talk about RAII in relation to Zig I think they mean something slightly different than RAII, but then the conversation starts to become about what is the definition of RAII rather than whether the Zig language is lacking a certain kind of useful abstraction.
Examples:
[1]: https://news.ycombinator.com/item?id=29506814
[2]: https://gist.github.com/andrewrk/190170bc1441839644c3f15725a...
Examples:
[1]: https://news.ycombinator.com/item?id=29506814
[2]: https://gist.github.com/andrewrk/190170bc1441839644c3f15725a...
Haha yeah this is a good insight. "Resource Acquisition Is Initialization" actually has nothing to do with resource acquisition or initialization in most peoples' minds, instead people (including me) tend to think of it as "Resource Release Is Implicit Object Lifetime Termination". RRIIOLT doesn't really have the same ring to it though xD
Not saying this means you actually need to add constructors and destructors, but I think the main tricky bit is when you have eg. a grow / shrinkable array and want to call something on it that removes elements and it should be calling destructors on those. AFAICT there's no clear place to add a `defer` that makes it happen at the right time at the lexical site those elements are originally added. I think this is where the main RAII complexity comes from vs. the lexical scope local variable scenario which is definitely handled by `defer`.
All that said, not an argument for having that, just wanted to nuance it. I think not having it and keeping the language focused on its priorities can be good, for example.
All that said, not an argument for having that, just wanted to nuance it. I think not having it and keeping the language focused on its priorities can be good, for example.
Surely the only part you need for this scenario is a way to dispose of whatever resources are behind the elements?
So if you have interfaces a Disposable interface is enough, the code can determine that these elements are Disposable and dispose of them when they're removed.
That's quite a lot less intense than needing a language-level concept of destructors. If you're writing a low-level language it might well be better to hook this in explicitly like Rust's Drop trait (the Drop trait is a langitem in Rust, it must exist), but in high-level languages I think you'd get almost all the value from a Disposable interface even if there is no actual language support provided.
So if you have interfaces a Disposable interface is enough, the code can determine that these elements are Disposable and dispose of them when they're removed.
That's quite a lot less intense than needing a language-level concept of destructors. If you're writing a low-level language it might well be better to hook this in explicitly like Rust's Drop trait (the Drop trait is a langitem in Rust, it must exist), but in high-level languages I think you'd get almost all the value from a Disposable interface even if there is no actual language support provided.
maybe since Zig still is making breaking changes, they can call it IIRA
I am not fully understanding how fat-pointers allow LLVM to devirtualize the function calls. If the allocators are polymorphic then a particular piece of code doesn't know which vtable it will get at run time correct?
It depends a lot, but in practice in Zig devirtualization is effectively constant propagation. The compiler needs to see the place where the vtable is created, and follow that to the place where virtual functions are called, ensuring along the way that nothing modifies the vtable. This is not possible for all uses of interfaces, but it is possible for many of them, especially ones where the interface is sort of "temporary" and you are usually passing around the implementation. These are the cases targeted by this change.
The difference in results has to do with pointer provenance tracking and aliasing. With both approaches, the first call to an interface function will almost definitely be devirtualized. The problem is that that first call will also modify implementation state. If the implementation function is not inlined (which is common), this is tracked as a modification to the memory region containing the implementation state. But with the fieldParentPtr model, that's the same memory region containing the vtable! So this breaks constant propagation on the vtable and any later calls must always be fully virtual, even if the optimizer can see the whole way from vtable creation to virtual call.
The difference in results has to do with pointer provenance tracking and aliasing. With both approaches, the first call to an interface function will almost definitely be devirtualized. The problem is that that first call will also modify implementation state. If the implementation function is not inlined (which is common), this is tracked as a modification to the memory region containing the implementation state. But with the fieldParentPtr model, that's the same memory region containing the vtable! So this breaks constant propagation on the vtable and any later calls must always be fully virtual, even if the optimizer can see the whole way from vtable creation to virtual call.
So does this optimization only work when the declaration of the allocator and its uses are in the same codegen unit? Otherwise the vtable of the allocator can’t be known at compile time.
Zig's build model is mostly to combine everything into one compilation unit (from multiple files). Since Zig doesn't have a preprocessor, the compiler can reason about incremental compilation and avoid rebuilding everything for every change. Incremental optimization is an open question that we will need to tackle at some point, but the focus for now is on getting the language to a point where it can be stable first.
You can introduce intentional graph cuts if you want, and build multiple objects, but you are limited to the C ABI at these boundaries.
You can introduce intentional graph cuts if you want, and build multiple objects, but you are limited to the C ABI at these boundaries.
You aren't modifying the same object
When you have a fat pointer, llvm can tell you are modifying the ptr, bot the vtable
You can then cache the function call
When your vtable is in the object you are mutating, it needs to read each time
You can then cache the function call
When your vtable is in the object you are mutating, it needs to read each time
Does LLVM do the inline caching itself? Or does it just enable zig to do this optimization?
What happens is likely that the code gen can do the virtual lookup once, instead on each loop iteration
This is llvm, bit zig
This is llvm, bit zig
why not just an an interface type instead of this giant mess?
"allocgate" is actually a meme name that we purposely gave to this API change. In reality it's not a big deal and that's the superpower that a language v0 has: you can make breaking changes.
As for the builtin interface type, why get locked into one particular implementation when you can have all of them by leaving the choice to the programmer.
As for the builtin interface type, why get locked into one particular implementation when you can have all of them by leaving the choice to the programmer.
I agree that it's not a big deal. I am not a Zig developer, but I've written a few thousand lines of Zig code in the last few months that extensively uses allocators all over the place, and it only took me a few minutes to update my code to work with this API change. Also, having seriously played around in Zig for a few months writing high performance pure mathematics and number theory code for fun, I *really, really* like it. Zig is a fantastic language for certain application domains.
> As for the builtin interface type, why get locked into one particular implementation when you can have all of them by leaving the choice to the programmer.
that's a very good point!
that's a very good point!