[Cython] Hash-based vtables

[Dag Sverre Seljebotn]

On 06/30/2012 01:01 PM, Dag Sverre Seljebotn wrote:
> On 06/30/2012 12:57 PM, Dag Sverre Seljebotn wrote:
>> My time is rather limited but I'm slowly trying to get another SEP 200
>> in place.
>>
>> Something that hit me, when I tried to make up my mind about whether to
>> have (key, ptr) entries or (key, flags, ptr), is that the fast hash
>> table entries can actually be arbitrary size. So we could make the table
>> itself
>>
>> void *table[n]
>>
>> and then n would be a power of 2 (TBD: benchmark cost of allowing other
>> sizes). Since we have the d[i] displacements, it's no problem at all to
>> construct displacements to account for variable-size entries.
>>
>> Proposal:
>>
>> C-source for an un-initialized table (signature string is placeholder
>> and not up for discussion now):
>>
>> { "3:method:foo:i4i4->i4", (void*)EXCEPT_STAR_FLAG, &foo_method,
>> "2:numpy:SHAPE", &get_shape_method,
>> "2:fieldoffset:barfield", (void*)5, 0 /*padding to n=2^k*/ }
>>
>> I.e. all keys are prepended by the number of slots they use. So methods
>> get to use 3 sizeof(void*) slots since they need the flags, but entries
>> that don't need flags use only 2 slots. (In this case, "numpy:SHAPE" is
>> a protocol defined by NumPy and so doesn't need any flags; or the flags
>> are stored under "numpy:FLAGS" by that protocol.)
>>
>> Then, PyExtensibleType_Ready parses this and rearranges the table to a
>> perfect hash-table. As part of that, it parses the string literal keys
>> and interns them, so that the number of slots becomes available in a
>> more coder-friendly manner:
>>
>> typedef {
>> uint64_t hash; /* lower-64 bit of md5 */
>> uint32_t strlen; /* we allow \0 in key */
>> uint8_t nslots; /* set to 3 for first example */
>> char *key; /* set to "method:foo:i4i4->i4" */
>> } fasttable_key_t;

An idea that could be entertained is make the hash e.g. sha-256, and 
store the entire 256 bits here, so that the interning procedure didn't 
need to strcmp the entire key string on hash collisions.

I imagine that interface definitions etc. could make for rather large 
string keys, and one would also want to use the sha-256 to point to 
other interfaces.

OTOH, one needs to run through the entire key to construct the cheaper 
hash needed to go from char* to fasttable_key_t* anyway, so perhaps 
there's not much point in this, it's only a factor 2x or 3x.

Dag

>>
>> Then, the interned keys for the table is the fasttable_key_t*.
>>
>> Storing the hash inside the key has two pros:
>> - Caching the md5 work (provided the interner uses a faster hash
>> function to go from string to
>
> Sorry.
>
> Storing the hash inside the key has two pros:
>
> - Caching the md5 work (provided the interner uses a faster hash
> function to go from string to key "object")
>
> - You don't always have to store both key and hash in global variables
> (see below), you can dereference the key for the hash if you want to.
>
> Dag
>
>>
>> Lookup would happen like this:
>>
>> typedef {
>> fasttable_key_t *key;
>> uintptr_t flags;
>> void *funcptr
>> } method_t;
>>
>> (method_t*)PyCustomSlots_Find(mykey, mykey->hash);
>> /* or, faster: */
>> (method_t*)PyCustomSlots_Find(mykey, 0x45343453453fabaULL);
>>
>> If you want to scan the table linearly (to avoid having to bother with
>> getting an interned key), you would scan a table of void*, and for every
>> entry cast the key to fasttable_key_t* and check nslots for how much to
>> skip to get to the next entry.
>>
>> Too complicated?
>>
>> Dag
>
> _______________________________________________
> cython-devel mailing list
> cython-devel at python.org
> http://mail.python.org/mailman/listinfo/cython-devel