develooper Front page | perl.perl5.porters | Postings from September 2021

Re: Robin Hood Hashing for the perl core

Thread Previous | Thread Next
Dave Mitchell
September 1, 2021 14:10
Re: Robin Hood Hashing for the perl core
Message ID:
On Wed, Sep 01, 2021 at 01:50:29PM +0000, Nicholas Clark wrote:
> On Mon, Aug 30, 2021 at 01:53:20PM +0100, Dave Mitchell wrote:
> > Just a general observation here about proposals to change or improve hash
> > semantics. I've been meaning for many years (but lacked tuits) to introduce
> > hash vtables, which would allow for differing hash implementations to be
> > called on a per-hash basis (so you could declare a hash as being of a
> > key-order-preserving or ref-as-key-preserving type for example).
> Yes. At least, "yes" is what I thought at first.
> But I think for this case, it won't help most of the time.
> "I don't want hash entries to move underneath me" is a constraint wanted by
> the call site (the third party XS code)
> "This hash can move about"/"This hash does not" would be a property of the
> vtable, and you couldn't "turn it on/off" for any hash passed into the XS
> code.

Er, I was suggesting vtables would help with ref-preserving key semantics,
not that they would help with HE lifetimes!

> I'm also not convinced about the efficiency. At the lowest level, it's a call
> through a function pointer, which I thought that CPUs didn't totally enjoy.

My "vision" such as it was, is that vtable functions are only called for
the special cases. I.e. whereas hv_common() etc currently have a whole
bunch of code along the lines of:

    if (has %ENV magic)
        do something special;
    if (has tie magic)
        do something special;
    if (is stash)
        do something special;

It would now look like:

    if (hv->sv_flags & SVf_HV_VTABLE) { the relevant chain of vtable fn pointers ...
        return if vtable function indicated a return was appropriate;
    ... handle a plain perl hash ...

So most special-case code is now hidden behind a single conditional.

> But one level up, I can see (and in that branch) have made code and structure
> assumptions based on how the parts of the hash fit together.

I confess I haven't given much thought to the API, especially in terms of
what should be the collection of vtable methods, and especially as to
whether they should be a small collection of low-level functions, mimicing
hv_common() etc, or lots of higher-level ones, mimicing all the
hv_fetch(), hv_fetch_ent() etc functions.

In England there is a special word which means the last sunshine
of the summer. That word is "spring".

Thread Previous | Thread Next Perl Programming lists via nntp and http.
Comments to Ask Bjørn Hansen at | Group listing | About