Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Allocgate: Restructuring how allocators work in Zig

pithlessly.github.io

Post reply on HN
Print view View original

31–40 of 52 posts

Re: Allocgate: Restructuring how allocators work in Zig

#31

Post by twmb »

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

Re: Allocgate: Restructuring how allocators work in Zig

#32

Post by steveklabnik »

Spex_guy wrote: post #30
steveklabnik wrote: post #25

Earlier quoted context omitted.

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

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

Re: Allocgate: Restructuring how allocators work in Zig

#33

Post by Spex_guy »

AndyKelley wrote: post #8
levzettelin wrote: post #2

Does anyone know if RAII types will ever be a thing in Zig?

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

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

Re: Allocgate: Restructuring how allocators work in Zig

#34

Post by jasonhansel »

twmb wrote: post #31

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

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.

Re: Allocgate: Restructuring how allocators work in Zig

#35

Post by celeritascelery »

Spex_guy wrote: post #23
celeritascelery wrote: post #17

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 "temp…

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.

Re: Allocgate: Restructuring how allocators work in Zig

#36

Post by pcwalton »

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.

Re: Allocgate: Restructuring how allocators work in Zig

#37

Post by Spex_guy »

celeritascelery wrote: post #35
Spex_guy wrote: post #23

Earlier quoted context omitted.

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 "temp…

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.

Re: Allocgate: Restructuring how allocators work in Zig

#38

Post by tialaramex »

nikki93 wrote: post #13
AndyKelley wrote: post #8

Earlier quoted context omitted.

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

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

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.

Re: Allocgate: Restructuring how allocators work in Zig

#39

Post by spacechild1 »

jcelerier wrote: post #11
initplus wrote: post #6

Earlier quoted context omitted.

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

> 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")}; }

That's what I do as well. Many people are not aware that std::unique_ptr can do more than just manage heap memory.

Re: Allocgate: Restructuring how allocators work in Zig

#40

Post by Spex_guy »

pcwalton wrote: post #36

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.
Post reply on HN