Far classes

[Thomas Stüfe]

Hi John,

Sorry for the late response, I have been busy with other Lilliput aspects.

Thanks again for your great ideas!

Let's see if I get this right. The base idea is to use joint encoding to
take the sting out of losing half of the whole nKlass value range for near
classes with the "is-far-class" signal bit; and the fact (obvious now but
it did not occur to me) that we can just insert the Klass* into *every*
large class, near or far, since the overhead paid depends on instance size.

Let's say I have 16-bit nKlass - (I need a different name now for the datum
in the mark word since in case of a far class, this is not a nKlass ID.
klassWord?) - a 16-bit klassWord, and reserve 8 bits for the
offset-into-klass.

In that model:
a) the largest offset I can represent is 0xFF; counting in words and adding
1 since I don't need offset 0 (its the header), the farthest I can point at
is word offset 256
a) any (near and far) class that is larger than 256 words will have an
empty Klass* slot injected at word offset 256
b) a far class with a small instance size will have a Klass* slot injected
and populated at the end end of the object
c) a far class whose instance size is > 256 will populate the Klass* slot
prepared by (a)
d) all far classes will set their klassWord to: lower 8 bits zero, higher 8
bits the capped-at-256 Klass* slot offset
e) all near classes will set their klassWord to their nKlass ID as we do
today
f) No near class can have a nKlass ID with all eight lower bits zero -
aligned to 8 bit - which reduces the number of valid nKlass IDs to (64k -
256)

The challenges to the allocator alignment-wise would be manageable.

IIUC, the knob to tweak would be offset size. Larger offsets reduce the
number of encodable near classes and increase the threshold instance size
at which an object needs a Klass* slot injected. The latter defines how
many objects carry the 8-byte size overhead. In the above example, a
cut-off point of 256 words (2KB) is very generous, and the number of
objects actually affected super rare. There is also a diminishing return
for reducing the offset too much: the delta between (64k - 256) or (64k -
128/64/32) is not that significant. 8 bit for the offset may turn out to be
a good spot.

As for memory overhead, if an app runs into the situation that it needs
many far classes, the size overhead of small-sized-far-class-objects with
their appended Klass* slot will matter a lot more.

Thanks & Cheers, Thomas


On Wed, Jun 26, 2024 at 10:54 AM John Rose <john.r.rose at oracle.com> wrote:

>
>
> On 18 Jun 2024, at 5:23, Thomas Stüfe wrote:
>
> > We dedicate one bit in the nKlass for "is-far-class". For far classes, we
> > store the Klass* at the end of the object. Then we encode the offset of
> the
> > Klass* slot in the remaining nKlass bits.
>
> You could also use a joint encoding [1] on more than one bit,
> so as have encode more near classes in the same number of
> bits.  What’s the trade-off?  The bits other than the
> joint encoding would encode the offset, so the offsets
> would be shorter.  In fact, you don’t need long offsets
> at all; there’s no sense in tying the max offset to
> the max number of near classes, which is what the naive
> selector bit does: 2^15 near classes AND 2^15 max offset,
> if you have 16 bits and burn one bit for the far class
> indicator.
>
> Instead, use (say) 6 joint bits out of 16 total, and
> then you get 2^16-2^10 near classes, and a maximum far
> class offset of 2^10.
>
> [1] https://cr.openjdk.org/~jrose/jvm/joint-bit-encodings.html
>
> > That depends on max. object size. How large does an object get? I found
> no
> > limit in specs. However, the size of an object depends on its members,
> and
> > we have an utf-8 CP-entry per member, and the number of CP entries is
> > limited to 2^16. So, an object cannot have more than 65535 members (a bit
> > less, actually). Therefore, I think it cannot be larger than 64k heap
> words.
>
> Objects can get pathologically large because there is no limit
> to the depth of the superclass chain, and each superclass can
> contribute tens of thousands of fields.
>
> But this should not be understood as a constraint on the
> size of the nClass field, or the number of near classes.
>
> > …
> > We could even get down to 16 bits for the MW-stored nKlass, if we agree
> on
> > aligning the Klass* slot trailing the object to 16 bytes. In that case,
> we
> > can encode the Klass* slot offset with 15 bits and have the
> "is-far-class"
> > as the 16th bit. Then, we could extract the nKlass from the MW with a
> > 16-bit move. This would cost us: On average, another four bytes of
> overhead
> > per far-class object, and a halved value range for near class IDs.
>
> You are getting closer here to a better design:  The key move
> is to constrain where the far-class Klass* can occur in the
> object layout.  As long as there are enough bits in the header
> (minus the far-class selector bit or bits), as long as those
> bits can distinguish all the possible locations of the
> far class (Klass*) field in the object layout, you are good.
>
> So the problem boils down to what is the best way to constrain
> the location of the Klass* field.  Obviously it is aligned
> word-wise, so it’s not just any char offset.  More importantly,
> we can simply demand that it is less than some fixed constant,
> such as 2^10 words (taking the above example again, the one
> with 16 nClass bits and 6 joint encoded far-class selector
> bits).
>
> Can we meet this demand?  Yes.  The key is to allocate
> a far class pointer in any class whose layout is large
> enough to overflow the offset limit. This is done even
> if the class itself does not need a far class slot.
> The slot is wasted in that case, but it is just one
> word out of 2^10, so the max waste is 0.1%.
>
> Jumbo classes are super-rare, anyway.
>
> That way, if a subclass of the jumbo class ever needs
> a far class word, there’s a spot prepared for it,
> within the maximum offset.
>
> If the class is jumbo and final, there is no need
> to allocate a far class slot for subclasses.  But
> if it is jumbo and non-final then it will require
> a far class slot EVEN IF it is lucky enough to
> acquire a near class ID.  The far class slot is
> for the subclasses that are not so lucky and
> cannot get a near class ID.  They will need that
> far class slot, and they won’t be able to allocate
> it for themselves.
>
> BTW, if the class is abstract there is no need to allocate
> a near class ID: Only concrete classes need near class
> IDs.  But abstract jumbo classes WILL need far class
> slots, again for their subclasses that are unlucky,
> and cannot get a near class ID.
>
> For testing make the max offset of the far class word
> very small, like 10.  That way many classes will be
> burdened with the extra field, and you will get a
> stress test of the mechanism.  Don’t just assume
> that there are enough jumbo classes in the world
> to test this contraption without a stress mode.
>
> The trick of preallocating a far class slot even
> before you need it allows you to constrain the
> offset of the far class slot.
>
> The other independent trick of using a joint
> encoding (of the far class selector pattern)
> allows you to have very small far class offsets,
> and therefore use almost all of the encoding
> power of the nKlass in the header to represent
> near classes, which is as it should be.
>
> Continuing the above concrete example, if the 16-bit
> nKlass has all zero bits in the top 6 bits, that
> selects the far class mode, while one or more
> non-zero bits in the top 6 would select the near
> class, and all 16 bits would encode the ID of that
> near class.
>
> Klass* get_klass(uint16_t nKlass) {
>   if ((nKlass & (-1<<10)) == 0) {
>     return ((Klass**)this)[nKlass];
>   } else {
>     return NEAR_CLASSES[nKlass - (1<<10)];
>   }
> }
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <https://mail.openjdk.org/pipermail/lilliput-dev/attachments/20240712/15314f4d/attachment-0001.htm>