Generics can make your Go code slower • Hacker News Board

Re: Generics can make your Go code slower

#371

Post by [deleted] » Thu, Mar 31, 2022, 1:24 PM UTC

chrisseaton wrote: post #369

coder543 wrote: post #368

Earlier quoted context omitted.

I edited my comment before you posted yours. Making heap allocations super complicated just to avoid the stack is a confusing idea. Generational GCs surely do not do a single bump allocate for all local variables. How could the GC possibly know where each object starts and ends if it did it as a single allocation? Instead, it treats them all as individual allocations within an allocation buffer, which means bumping f…

When you allocate objects individually it looks like this: object_a = tlab tlab += 8 check tlab limit object_b = tlab tlab += 8 check tlab limit When you allocate as a single allocation it looks like this: object_a = tlab object_b = tlab + 8 tlab += 16 check tlab limit What about that do you see as impossible? > How could the GC possibly know where each object starts and ends if it did it as a single allocation? As a…

[deleted]

Re: Generics can make your Go code slower

#372

Post by coder543 » Thu, Mar 31, 2022, 1:31 PM UTC

chrisseaton wrote: post #369

coder543 wrote: post #368

Earlier quoted context omitted.

I edited my comment before you posted yours. Making heap allocations super complicated just to avoid the stack is a confusing idea. Generational GCs surely do not do a single bump allocate for all local variables. How could the GC possibly know where each object starts and ends if it did it as a single allocation? Instead, it treats them all as individual allocations within an allocation buffer, which means bumping f…

When you allocate objects individually it looks like this: object_a = tlab tlab += 8 check tlab limit object_b = tlab tlab += 8 check tlab limit When you allocate as a single allocation it looks like this: object_a = tlab object_b = tlab + 8 tlab += 16 check tlab limit What about that do you see as impossible? > How could the GC possibly know where each object starts and ends if it did it as a single allocation? As a…

In your example, the objects are all the same size. That would certainly be easy.

If you have three local objects that are 8 bytes, 16 bytes, and 32 bytes… if you do a single 48 byte allocation on the TLAB, how can the GC possibly know that there are three distinct objects, when it comes time to collect the garbage? I can think of a few ways to kind of make it work in a single buffer, but they would all require more than the 48 bytes that the objects themselves need. Separate TLAB arenas per size class seem like the best approach, but it would still require three allocations because each object is a different size.

I understand you’re some researcher related to Truffle… this is just the first I’m hearing of multiple object allocation being done in a single block with GC expected to do something useful.

Re: Generics can make your Go code slower

#373

Post by chrisseaton » Thu, Mar 31, 2022, 1:31 PM UTC

coder543 wrote: post #368

chrisseaton wrote: post #365

Earlier quoted context omitted.

> If you allocate them all as a single allocation, then the entire allocation would be required to live as long as the longest lived object. No, you can copy objects out if they live longer than others. That's how a generational GC works.

I edited my comment before you posted yours. Making heap allocations super complicated just to avoid the stack is a confusing idea. Generational GCs surely do not do a single bump allocate for all local variables. How could the GC possibly know where each object starts and ends if it did it as a single allocation? Instead, it treats them all as individual allocations within an allocation buffer, which means bumping f…

> at a minimum it seems like you would need arenas for each size class

But TLABs are heterogenous by size. Objects of all sizes go in one linear allocation space. So allocating two objects next to each other is the same as allocating them both at the same time.

Re: Generics can make your Go code slower

#374

Post by coder543 » Thu, Mar 31, 2022, 1:34 PM UTC

chrisseaton wrote: post #373

coder543 wrote: post #368

Earlier quoted context omitted.

I edited my comment before you posted yours. Making heap allocations super complicated just to avoid the stack is a confusing idea. Generational GCs surely do not do a single bump allocate for all local variables. How could the GC possibly know where each object starts and ends if it did it as a single allocation? Instead, it treats them all as individual allocations within an allocation buffer, which means bumping f…

> at a minimum it seems like you would need arenas for each size class But TLABs are heterogenous by size. Objects of all sizes go in one linear allocation space. So allocating two objects next to each other is the same as allocating them both at the same time.

That doesn’t answer how the GC knows where the boundaries of each object are.

Re: Generics can make your Go code slower

#375

Post by chrisseaton » Thu, Mar 31, 2022, 1:39 PM UTC

coder543 wrote: post #372

chrisseaton wrote: post #369

Earlier quoted context omitted.

When you allocate objects individually it looks like this: object_a = tlab tlab += 8 check tlab limit object_b = tlab tlab += 8 check tlab limit When you allocate as a single allocation it looks like this: object_a = tlab object_b = tlab + 8 tlab += 16 check tlab limit What about that do you see as impossible? > How could the GC possibly know where each object starts and ends if it did it as a single allocation? As a…

In your example, the objects are all the same size. That would certainly be easy. If you have three local objects that are 8 bytes, 16 bytes, and 32 bytes… if you do a single 48 byte allocation on the TLAB, how can the GC possibly know that there are three distinct objects, when it comes time to collect the garbage? I can think of a few ways to kind of make it work in a single buffer, but they would all require more…

> If you have three local objects that are 8 bytes, 16 bytes, and 32 bytes… if you do a single 48 byte allocation on the TLAB, how can the GC possibly know that there are three distinct objects, when it comes time to collect the garbage?

Because the objects are self-describing - they have a class which tells you their size.

    object_a = tlab
    object_a.class = ClassA
    object_b = tlab + 8
    object_b.class = ClassB
    object_c = tlab + 16
    object_c.class = ClassC
    tlab += 48
    check tlab limit

Re: Generics can make your Go code slower

#376

Post by coder543 » Thu, Mar 31, 2022, 1:47 PM UTC

chrisseaton wrote: post #375

coder543 wrote: post #372

Earlier quoted context omitted.

In your example, the objects are all the same size. That would certainly be easy. If you have three local objects that are 8 bytes, 16 bytes, and 32 bytes… if you do a single 48 byte allocation on the TLAB, how can the GC possibly know that there are three distinct objects, when it comes time to collect the garbage? I can think of a few ways to kind of make it work in a single buffer, but they would all require more…

> If you have three local objects that are 8 bytes, 16 bytes, and 32 bytes… if you do a single 48 byte allocation on the TLAB, how can the GC possibly know that there are three distinct objects, when it comes time to collect the garbage? Because the objects are self-describing - they have a class which tells you their size. object_a = tlab object_a.class = ClassA object_b = tlab + 8 object_b.class = ClassB object_c =…

Ok, so it’s not as simple as bumping the TLAB pointer by 48. Which was my point. You see how that’s multiple times as expensive as stack allocating that many variables? Even something as simple as assigning the class to each object still costs something per object. The stack doesn’t need self describing values because the compiler knows ahead of time exactly what every chunk means. Then the garbage collector has to scan each object’s self description… which way more expensive than stack deallocation, by definition.

You’re extremely knowledgeable on all this, so I’m sure that nothing I’m saying is surprising to you. I don’t understand why you seem to be arguing that heap allocating everything is a good thing. It is certainly more expensive than stack allocation, even if it is impressively optimized. Heap allocating as little as necessary is still beneficial.

Re: Generics can make your Go code slower

#377

Post by chrisseaton » Thu, Mar 31, 2022, 1:48 PM UTC

coder543 wrote: post #376

chrisseaton wrote: post #375

Earlier quoted context omitted.

> If you have three local objects that are 8 bytes, 16 bytes, and 32 bytes… if you do a single 48 byte allocation on the TLAB, how can the GC possibly know that there are three distinct objects, when it comes time to collect the garbage? Because the objects are self-describing - they have a class which tells you their size. object_a = tlab object_a.class = ClassA object_b = tlab + 8 object_b.class = ClassB object_c =…

Ok, so it’s not as simple as bumping the TLAB pointer by 48. Which was my point. You see how that’s multiple times as expensive as stack allocating that many variables? Even something as simple as assigning the class to each object still costs something per object. The stack doesn’t need self describing values because the compiler knows ahead of time exactly what every chunk means. Then the garbage collector has to s…

Every stack allocation scheme I've seen creates a fully reified object though, with a class pointer as normal.

You may be confusing with scalar replacement of aggregates, which is a separate concept.

https://chrisseaton.com/truffleruby/seeing-escape-analysis/

Re: Generics can make your Go code slower

#378

Post by jbjohns » Thu, Mar 31, 2022, 1:53 PM UTC

svnpenn wrote: post #276

TheDong wrote: post #274

Earlier quoted context omitted.

As I said above: > In this case, the abstraction available in rust is cleaner and requires less code for me, the user of the package, so I don't think the lines of code used to build that abstraction matter. > Why do you see this as something that matters? It's true that the abstraction in rust has more code underlying it, but why does that matter? If you de-facto never have to implement the rust error trait by hand…

Thats a good outlook. Dont worry about any problem, just import something an its fixed! More imports the better! Hopefully we can do away with all code, and just import everything.

The Rust code is doing much more than what the Go code is doing, it's making more incorrect cases impossible. I really don't understand the complaint about imports. Anything that's not built into the standard library is not valid somehow? I'm struggling to imagine what would make someone think this.

Re: Generics can make your Go code slower

#379

Post by coder543 » Thu, Mar 31, 2022, 2:00 PM UTC

chrisseaton wrote: post #377

coder543 wrote: post #376

Earlier quoted context omitted.

Ok, so it’s not as simple as bumping the TLAB pointer by 48. Which was my point. You see how that’s multiple times as expensive as stack allocating that many variables? Even something as simple as assigning the class to each object still costs something per object. The stack doesn’t need self describing values because the compiler knows ahead of time exactly what every chunk means. Then the garbage collector has to s…

Every stack allocation scheme I've seen creates a fully reified object though, with a class pointer as normal. You may be confusing with scalar replacement of aggregates, which is a separate concept. https://chrisseaton.com/truffleruby/seeing-escape-analysis/

Go does not put class pointers on stack variables. Neither does Rust or C. The objects are the objects on the stack. No additional metadata is needed.

The only time Go has anything like a class pointer for any object on the stack is in the case of something cast to an interface, because interface objects carry metadata around with them.

These days, Go doesn’t even stack allocate all non-escaping local variables… sometimes they will exist only within registers! Even better than the stack.

Re: Generics can make your Go code slower

#380

Post by chrisseaton » Thu, Mar 31, 2022, 2:01 PM UTC

coder543 wrote: post #379

chrisseaton wrote: post #377

Earlier quoted context omitted.

Every stack allocation scheme I've seen creates a fully reified object though, with a class pointer as normal. You may be confusing with scalar replacement of aggregates, which is a separate concept. https://chrisseaton.com/truffleruby/seeing-escape-analysis/

Go does not put class pointers on stack variables. Neither does Rust or C. The objects are the objects on the stack. No additional metadata is needed. The only time Go has anything like a class pointer for any object on the stack is in the case of something cast to an interface, because interface objects carry metadata around with them. These days, Go doesn’t even stack allocate all non-escaping local variables… some…

> These days, Go doesn’t even stack allocate all non-escaping local variables… sometimes they will exist only within registers!

Did you read the article I linked? That's what it says - and this isn't stack allocation, it's SRA. Even 'registers' is overly constrained - they're dataflow edges.