Introduce Hash trait, immutable flag on Class and runtime magic to cache hashcodes about dora HOT 7 CLOSED

@dinfuehr What do you think? While I think there is a concern regarding predictability, I think it would be a cool way for the runtime to opportunistically cache hashcodes, speeding up every data-structure that uses it, because things are never computed more than once (modulo harmless race conditions).

from dora.

I am not a fan of adding such magic in general: A class can always cache the hash itself and have some behavior that fits for its use case (e.g. recomputing the hash when setting a field).

I am also not sure whether it makes sense to steal bits from the vtable pointer. This requires us to mask out the low 3-bits when loading something from the vtable ptr, this introduces some overhead. Although not sure how much. However we could steal a bit from the header word - the word right after the vtable pointer in an object (used by the GC for the forwarding pointer and marking bit).

from dora.

I agree with you regarding magic in general.

In this case my experience is that people rarely cache hashcodes, because often they are fine with caching it when it's free (in terms of instance size), but don't want to pay the overhead if it added to the instance size. Usually the concern is that the next person might add another field without considering the instance size, turning their "free" hashcode into one with cost attached.

So I'm not sure it is worth it, but I thought that the hashcode magic in the runtime alleviated some of these concerns, by automatically using the wasted bytes to provide a "free" cached hash, without introducing fears that the next user might add an additional field.

In addition to that, there are some hashmap implementations which cache the hashcodes externally. With this feature, this could be elided for classes which already cache it internally. The benefit compared to manually caching the hashcode is that in this case the position of the cached hashcode is guaranteed, so instead of calling the hash method, it could read the field directly.

However we could steal a bit from the header word - the word right after the vtable pointer in an object (used by the GC for the forwarding pointer and marking bit).

True, this would make more sense.

from dora.

In addition to that, there are some hashmap implementations which cache the hashcodes externally. With this feature, this could be elided for classes which already cache it internally. The benefit compared to manually caching the hashcode is that in this case the position of the cached hashcode is guaranteed, so instead of calling the hash method, it could read the field directly.

Not sure this makes much of a difference: A HashMap has to be specialized for each key/value combination anyway, inlining hash() should then give the same result.

I am not opposed to this, but this seems to require a lot of language features to work properly. Let's postpone this discussion to a later date for now.

from dora.

Agreed. Shall I close this issue or do we want to create a few of these issue tags Github offers and start tagging issues with it (e. g. this one with "postponed" or something)?

from dora.

I am fine with whatever you prefer!

from dora.

I just checked https://github.com/dinfuehr/dora/labels and there seem to exist some tags, but nothing like "postponed". Could you create such a tag and tag this issue with it (I can do neither of those things) and close it?

(I would keep open tickets only for those issues we agree that they should/could be done and can be completed in a reasonable time frame, and distinguish between closed ones we have rejected and ones we might reconsider with tags like "postponed", "rejected", etc.)

from dora.