My name is Thomas. I work at Rattard. I'm going to be really horse after this. So, this talk
is sort of a side show to the project Lily Put. Oh, my talk about that earlier. When we
were working on project Lily Put in the last couple of years, we saw, we had to shrink the
network class or the down to 22 bits as Roman has explained. And in the course of that work,
we saw that we may hit at some point in time limits in the class based model we have
now. So, last summer, I set out to explore some alternative avenues. And that's the talk basically.
So, you have to remember that class based has been with us since it's inception,
basically since I'm going to move it. And it's freeing around the corners, it's showing us age.
And sometimes it's good to step back and look what you are doing, whether you should be
continue doing it, or whether there are alternatives, and whether they treat off still makes sense.
Even if you end up doing the same in the end. So, a small recap in class based objects
lift in the heat, obviously. And if the GVM wants to do something with an object, it needs to
know things about that object. And many of these things are recorded in the class structure.
The class structure written with Captain K is a native data structure. And in letters based,
or class based, it's two sides of the same coin, really. And contain things like IT,
the detail, the detail, and so on. So, every object contains a reference to the class of its class.
And the shape of this reference matters, because it has to be small, it goes into a real object.
So, everybody matters. And decoding has to be fast, because we do this all the time, especially
during you see. Now, we could just put the point into the header, we don't do that, because
it's a bit silly, and it based its memory, at least on 64 bit, on 32 bit we do that. So,
what you do instead, there is a mode actually in the GVM. You can enable this. If you switch
off, you need to deliberately switch off compressed class pointers. And then you have this mode,
but I actually think this mode shouldn't exist anymore, we should deprecate it. And what we
instead do, by default, is a trait of between size and decoding speed. We have the so-called
narrow class ID or narrow class pointer. The narrow class pointer is 32 bit offset of the
address of the class structure, which refers to a common base, which we add, and then you have the
class pointer. There is also an optional shift of three, which I will ignore for now, because it's
basically not used anymore, at least not in practical concerns, because it doesn't work with CDS
and everyone wants to CDS. So, using this technique means that you have four gigabyte range,
so you have to confine the location of our class structures to a four gigabyte range or the offset
with lower over. And we do that, that starts at the encoding base, and in this encoding range,
we place CDS and class base, and all class is live in that thing, and the distance, the
pointer difference between the class structure and the encoding base is the narrow class ID,
we put into the object. And this technique allows us, this is actually a pretty smart, because
this technique allows us to translate the narrow class ID into the real class pointer without any
additional loads. We can just, it's one load to load the narrow class ID. Everything else can
happen on the CPU, because at least from the point of the JIT. The encoding base is a constant,
so we can encode it directly in the instructions stream as some form of, of, of immediate,
which we do. With Lily put things change a bit, so the narrow class ID shrunk down to 22 bits,
and moved into the Margaret, as Roman has explained. You can see advantage of Lily put right here,
because now we can load both Margaret and the narrow class ID in a single 64 bit load, and that
actually shows in metrics. That's one of the advantages of the many advantages. And 22 bit
give you only a coverage of form megabyte, and that would be a small class base, so what we do
instead is we now have an obligatory shift of 10. The reality is a bit more complex, so the shift
can be smaller, but let's go with 10. And every narrow class ID now shift the button,
in effect this means that every class structure has to be located at an address that is
in one kilobyte aligned, so we have an alignment should of 10 bits, which we then don't just don't
save. And that works, so we should Lily put, we will should Lily put for JIT 21 networks.
The only problem is now there are two disadvantages. The first to what you can see is we impose
a cadence of sort, like one kilobyte cadence, on the encoding range, every class structure lifts
there and only there unless you don't want to decode the pointer. And first thing is obvious,
you now have alignment based. Every class structure is followed by a block of memory of varying
size, class structures there are a size, and we cannot use this memory for class structures. So
we solve this problem, by using recycling this memory for data that would otherwise be
lift somewhere else, so the net footprint is not 0, net footprint plus 0. And that data is also
metadata, it belongs, it has the same lifetime scope as a class, so it's fine, this really works,
so that problem is solved. The other problem or the problem of hyperlining and I will come to that.
So why should we change? There are several reasons, the apart from the hyperlining issue,
we have a class limit, we are sneaking up on every further step, for instance, for Lily put,
we reduce the narrow class ID, and the size of the narrow class ID is really the class limit,
it's not the size of the class base, but it's the size of the bit size of the narrow class ID.
So with Lily put, we are now at 4Mg, at 4Mg, and it goes down, and we may, I don't know,
it gets tight, it's not the problem yet, so it's not really urgent problem, what we need to have
a plan, and we have a plan, and I will present that plan at the end. The other problem is that
no class ID set up in CDS, and a class BSD coding set up is really complex, and it's not fun
complex, it's annoying complex, it's brittle, and maintenance heavy, so we have lived with this
problem for quite some while, this code exists for 15 years, we can continue to live with it,
but if the opportunity arises to not have a class base, this would be good, we could reduce a lot
of complexity, honestly. The set-ups complex for a number of reasons, and unfortunately, when I was
preparing this, I had like six, six slides, and I don't have time for that for them talks
are short, so suffers to see there is a basic problem behind all of them, and the basic problem
is that the numerical shape of the narrow class ID, and of the encoding base is tightly
coupled with allocator mechanics, because the narrow class ID is in part of an address, and that
address is the product of an allocator, the metaspace allocator, and that one does allocator things,
like it has a body allocator in the middle, it does free list management, and so on, so it's already
kind of part to predict and influence the shape of the narrow class ID, if you want to do that,
and we maybe want to do that. Next thing is, below the allocator, there's a virtual memory layer,
and below that as an operating system, so in the end eventually, we have M map calls to the
operating system, and the operating system, and we are subject to the winds of the operating
system, like address-based population, and ASLR, and whatnot, and so if you want to do things
like like you went to have a certain bit shape of the encoding base, maybe because your
particular digit, or your particular ISA, straggled, representing arbitrary 64 bit, and 64 bit,
immediate, then you need to fight this out with the allocator, and with the underlying OS, and
it's important to remember that this is a performance to it, we do things the way we do,
because they are fast. There is a simpler way, and I will present one.
So the hyperlining problem. Class structures are aligned to tendons, it's fine, so it works,
but the problem is now with a typical cashline size of 64 by it, we lose four bit for selecting a cashline,
and that means we have more cashline now. If you work the heap and you touch different
class structures, you have a higher chance of evicting the outer class structure. We did no
Roman and I, we knew that this effect existed, we didn't really have time to focus on it,
because Lily put a really needed power or attention elsewhere, and clearly, it's actually
if you Roman didn't really touch on that topic, but Lily put brings a lot of positive effects also
in terms of memory bandwidth, very much so. So clearly, whatever effects the hyperlining
has is much more than an outrated by the positive effects of Lily put, because things in the heap
are no smaller, and you can basically use your memory bandwidth much more efficiently.
So question is, how much better could we be? And now last summer I said aside some time to
look at this, and first I tried a couple of general purpose benchmarks. The problem here is that
general purpose benchmarks are not always, but most of the time they tend to drawn out whatever you
want to measure with general mutator and VM noise, and so this was getting me nowhere, and then I was
at a junction of some sort, I could say, okay, you don't see anything in general purpose benchmark,
you can just throw away the class base, and I wasn't really daring to do that. There were actually
people who said this, but the problem here is always you as a GBM vendor, you never know who's
using your stuff. I mean, you never can be sure whether a significant portion of the user base will
be heard by a change, and there are existing optimizations in the GBM, which seem to indicate that
this is kind of important. So what I did was, I wrote a small micro benchmark in order to mimic
the situations in which these optimizations are important. The thing is rather simple, you
populate the heap with a ton of objects, the objects try to mimic the distribution of object features
in a realistic population in a way like distribution object sizes, distribution of
root map sizes, and so on. But they belong to a randomly selected class of a set of enclosures,
and clearly when you have the larger the set, this is the benchmark parameter, the larger the set,
the more adverse the catch effect, when you trace the heap, because you touch different classes.
And also clearly the higher the number of classes, the more unrealistic it gets, because
the heap population is really like this. But it really exposes like bad catch behavior really
great. So I tried the first thing I tried was, I tried the non-power tool alignment. This is a
very simple idea. So you make the class alignment not a power tool value, but a non-power tool value,
more specifically you take an uneven number of catch line sizes. In my case I just
hard-coded 11, 7 or 4 bytes. That means if you touch different classes, you touch different catch lines.
Eventually every catch line is so nice, the distributed. The decode is not an add and shift anymore,
it's an add and an integral multiplication, but this is only like three more cycles depending on the
CPU. But I have to say, while I was writing it, I was already kind of hating this patch,
because the length is non-power tool alignment is no fun. It's really awkward. So the results are
interesting. So the level one misses the rise, similarly steeply blue is the prototype black
is stock. The level one misses the rise, similarly steeply, but they start at a state,
is the later stage. Then I thought, okay, I can work with this. Now I have numbers. Now I know
how much hyperlining costs, and this because everything else was the same. I didn't really like this
patch, though. It has a second problem, which is that deep within metaspace, we have a power tool based
body style allocator, and that doesn't, if you throw allocation sizes at that large,
because class is large, and with alignment requirements that are not power tool based, it starts
choking. So your fragmentation, this can be solved. I know I can solve this, but the problem
at that point I was kind of, I have something, I can do it, and it's fine, you know,
if nothing else works. So the next alternative is a class-bound interaction table.
The very quickly the idea comes up over and over again, Colleen Phillymore, from all what
the brings this up, and the idea here is that we, instead, we don't have a class-based. What we do
is we just place a point as into a look-up table, and every night, narrow-class idea is the slot,
is the slot of the look-up table. Two advantages, first, no class-based, lots of fewer complexities,
this is really good. It's solved, cyber-aligning, as an excellent almost, because now the
class-structure can look wherever, so they can be a line-werver, whatever. Big disadvantage is now you
have one more load in a hot decode path, and this shows. So steeper-wise, we can clearly see with
a little depot that first we have a benefit because our hyper-alignment is avoided, and then it goes
into pivots into negative territory, and then it just goes progressively, progressively worse.
So, this was already not good. Obviously, so, on this point, the costs for the load-out rate,
the benefits of the avoided hyper-aligning. And for non-leli-pot, of course, you don't have a benefit.
You only have the costs, so it's bad, it's worse from the beginning, and the thing is,
this, this approach only makes sense if you do it for lili-pot or non-leli-pot, because otherwise
you don't have a complexity benefit. It's just only more complicated than what we already do.
You can, a number of lili-one loads goes up flat by 5%, this is the load. So, okay,
I didn't like this video. I actually like this a lot, I would love to get rid of the class days,
but it's, I think, it's too expensive, at least for now. So, and then I, I was getting impatient,
I didn't have time anymore, and so I tried something different. I looked at how we
actually access metadata during arbitration. So, arbitration is when the GC traces heap. Here,
he looks at an object, tries to figure out where the referents are, and then traces these,
and maybe that's things with the object. So, it goes, it loads in our class,
I think, then it decodes, now we have the class pointer, now we know where the class structure is.
Now it loads a ton of data from the class structures, it's distributed, all over the class structure,
and so we hit, we don't always always load everything, but we load at least,
though, and that one is at the end of a while of size section, so we need to figure out where that one is.
And it's a ton of loads from different cache lines, up to 7 different cache lines,
I can't, if I can't directly. And as an edit, more loads, the class structure is large, so
you will never hit the same cache line from one class to the other. So, that is kind of,
can we do this better, to answer what we can? So, the new approach I played around with was,
you, when you load a class, you pre-compute a little token, I started a bit token, and that token
contains all the information I need for, for, for arbitration, and that seems weird, because that's
a lot of information, that's like 70 bytes, how do you get into four bytes, but we get.
The point here is that this compression doesn't have to always work, it's an optimization,
if it doesn't work, it's in the class structure, you look, in the class space. So,
but it has to work for most cases to make it worthwhile, and but in Java, most objects are small
and simple, so they have a small instance size, and very few map entries really.
So, the patch works, this particular thing, if the instance size can be statically computed,
which is always always the case, unless it's a yellow, yellow and class instance, or something like that,
instance size more than 512 bytes, and the number of loop map entries is less than 3,
and if we were loaded by one of the three loaders, then we get bonus.
And turns out this works for like 96 to 99% of all objects in a given heap of relation,
and I did a ton of different tests, various different applications, like SPAC, BGBB, and
and Jack Brains, and so on. So, this actually turns out to work well.
There's a little trick involved for those who wonder what to loop map thing.
So, loop maps describe where and the objects are, reference to our objects. And if you load a normal object,
then you have the GBM class as the object reference. So, for normal, simple objects, you only have a single loop map entry.
You only get multiple loop map entries, when you now have a child of this parent class, because he cannot, the part of the parent class is now immutable.
But what you can do is, like for every hierarchy level, in this, in this hierarchy, when you build up the class,
in the field layout, we can just alternate the order between loops and non-oops, and now you have,
this is like 10 lines of code. And now you have the higher chance of oopsections ending up nearing nearby,
you're nearing each other, and then the GBM will just create a single loop map entry.
That's how we get the average number of loop maps done.
With map entries. So, that's the simple. We store this thing into a side table. That side table, I call it Clute,
a class look up table, and the index into that thing is the narrow class ID.
And iteration now looks like this. We load the narrow class ID from the object,
and we don't need to decode. Now decode needed. So, what we do, we load the, the, the,
token from the, from the group, and then we are done. The token contains all information,
I need for iteration. I need some bit fit link to to get it out, but it can happen all in CPU,
no, no second, no third memory load. If you disregard the memory load of the, of the
clube base. And that's just two loads from two different cache lines. And there's actually a very good
chance of, of different loads. Yeah, of different loads sitting the same cache line because 16,
16 tokens fit into a single cache line. If the, yeah. So, results. The matrix look a lot better.
The red line down there is, is Clute. So, you can see that the response to rising number of classes,
the level one is, is a lot flatter. And not only that, we also have a ton of, we, we have much
lower number of level three loads. And both of them together means that you do a lot of,
a fewer loads, a much fewer loads than before. And it's like in 50 to 60% fewer loads. And of those
loads that actually hadn't, most of them are satisfied by the level one cache. A lot more than with
the other approaches. So, I think this, this handily, um, and solves the hyper-aligning issue, we had,
and um, and, um, oversolves, that's really. So, this was very good. Uh, DC pours is good down,
in the micro, um, they went down for all of them, but in Clute the best. And I was happy to see that
I even, if you're squint wheeled hard, you can actually see some metrics and, uh, expected to be
be the go down. Um, there's a grain of salt rules, since the standard deviation is 5% to 7%. The,
the standard deviation further for the micro was like 1%. So, here, this has definitely to be confirmed
and more measurements, but at least gives me hope. So, for me, the conclusion, this is the best
performance of all by far. Um, it doesn't really, it's not that complex. So, because it, it
just replaces the oil iteration. So, so, it's fine, um, and the, the important part here is that
actually, of course, on compliments, Colleen's idea was like, in the vacuum table, very good,
because that idea was the interaction table, suffers from poor decoding speed because of the load.
But if you don't decode too care, so, so, um, of course, this is only for iteration,
up iteration, then, in C++. But, um, maybe we can adjust this for other things. Um,
so, Clute cursed, I would, I would love to bring Clute in, I think there is no argument against it,
and then maybe the interaction table thing, at least at least it's interesting. And then,
maybe in the end, we don't have a class-based, then, goodbye class-based, after 15 years.
Okay, very quick, um, running out of time, completely different topic, of course.
The number of classes is limited by the, by the narrow class, I think.
Um, we, today, stocked JBN, 5 to 6 million limit, little input brings us down to four,
uh, hypothetical, little input 2 with, with 90 bit class, uh, we, we are now at 525k.
Things get tied, even if you don't have little input 2, you may at some point in time, there's always
the, the, the thing that you may want to repurpose narrow class point a bit for something else,
because the market gets smaller. And there is, there is a plan, we have a plan for this,
and this is actually very cool. The plan is from, not from me, but from John Rose, Edward Orkel.
And it's the near-class far-class idea. Basically, the idea here is that you, you have near-classes,
which are normally classes, and you have the narrow class idea as described. But if you hit the limit,
you, you, over, the limit of a, what a narrow class idea can represent, you have some way to do this by,
by offloading, injecting the, the class pointer into the middle of the object. And the specific
of that idea on, on this mailing list, and you can read it up. And I, I kind of hope, maybe if I get time to
implement a prototype next year, because at least so that we know it works, and that we also can measure
how much the cost. Lastly, things, things of all month, and things, colleagues, and stuff
on an absence, and working on a little bit of a test being really fun. And, yeah, I'm actually done.
Thank you.
Thank you very much.