Live data from Hacker News

Allocgate: Restructuring how allocators work in Zig

pithlessly.github.io

41–50 of 52 posts

Re: Allocgate: Restructuring how allocators work in Zig

#41
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…

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

Re: Allocgate: Restructuring how allocators work in Zig

#42

Earlier quoted context omitted.

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

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.

Re: Allocgate: Restructuring how allocators work in Zig

#43

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?

Re: Allocgate: Restructuring how allocators work in Zig

#44

Earlier quoted context omitted.

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?

BitC used a strictly typed memory model.

Re: Allocgate: Restructuring how allocators work in Zig

#45

Earlier quoted context omitted.

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?

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.

Re: Allocgate: Restructuring how allocators work in Zig

#46

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…

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

Re: Allocgate: Restructuring how allocators work in Zig

#47

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

Re: Allocgate: Restructuring how allocators work in Zig

#48

Earlier quoted context omitted.

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

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

thanks!

Re: Allocgate: Restructuring how allocators work in Zig

#49

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…

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.

Re: Allocgate: Restructuring how allocators work in Zig

#50
post #49

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…

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.

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