Live data from Hacker News

Allocgate: Restructuring how allocators work in Zig

pithlessly.github.io

21–30 of 52 posts

Re: Allocgate: Restructuring how allocators work in Zig

#21
post #19

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?

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

Does LLVM do the inline caching itself? Or does it just enable zig to do this optimization?

Re: Allocgate: Restructuring how allocators work in Zig

#22
post #19

Earlier quoted context omitted.

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

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

Re: Allocgate: Restructuring how allocators work in Zig

#23

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.

Re: Allocgate: Restructuring how allocators work in Zig

#24

Earlier quoted context omitted.

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…

> 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 r…

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.

Re: Allocgate: Restructuring how allocators work in Zig

#25

Earlier quoted context omitted.

> 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 r…

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 clarif…

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.

Re: Allocgate: Restructuring how allocators work in Zig

#26

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.

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.

Re: Allocgate: Restructuring how allocators work in Zig

#27

Earlier quoted context omitted.

> There is a lack of standardized RAII wrappers for handle types like there is for pointers. .. what's wrong with #include template using safe_handle_t = std::unique_ptr ; using file_handle = safe_handle_t ; void file_example() { file_handle f{fopen("foo", "r")}; }

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.

There is no double indirection and allocation here, it stores the FILE* directly, not as a pointer to a FILE*.

Re: Allocgate: Restructuring how allocators work in Zig

#28

Earlier quoted context omitted.

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…

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 int…

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).

Re: Allocgate: Restructuring how allocators work in Zig

#29

Earlier quoted context omitted.

> There is a lack of standardized RAII wrappers for handle types like there is for pointers. .. what's wrong with #include template using safe_handle_t = std::unique_ptr ; using file_handle = safe_handle_t ; void file_example() { file_handle f{fopen("foo", "r")}; }

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);
check for yourself: https://gcc.godbolt.org/z/YxaPqYGez

Re: Allocgate: Restructuring how allocators work in Zig

#30

Earlier quoted context omitted.

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 clarif…

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 stretch…

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.

Post reply on HN