[Cython] Hash-based vtables

[Dag Sverre Seljebotn]

On 06/10/2012 11:53 AM, Robert Bradshaw wrote:
> On Sun, Jun 10, 2012 at 1:43 AM, Dag Sverre Seljebotn
>> About signatures, a problem I see with following the C typing is that the
>> signature "ill" wouldn't hash the same as "iii" on 32-bit Windows and "iqq"
>> on 32-bit Linux, and so on. I think that would be really bad.
>
> This is why I suggested promotion for scalars (divide ints into
> <=sizeof(long) and sizeof(long)<  x<= sizeof(long long)), checked at
> C compile time, though I guess you consider that evil. I don't
> consider not matching really bad, just kind of bad.

Right. At least a convention for promotion of scalars would be good anyway.

Even MSVC supports stdint.h these days; basing ourselves on the random 
behaviour of "long" seems a bit outdated to me. "ssize_t" would be 
better motivated I feel.

Many linear algebra libraries use 32-bit matrix indices by default, but 
can be swapped to 64-bit indices (this holds for many LAPACK 
implementations and most sparse linear algebra). So often there will at 
least be one typedef that is either 32 bits or 64 bits without the 
Cython compiler knowing.

Promoting to a single type "[u]int64" is the only one that removes 
possible combinatorial explosion if you have multiple external typedefs 
that you don't know the size of (although I guess that's rather 
theoretical).

Anyway, runtime table generation is quite fast, see below.

>
>> "l" must be banished -- but then one might as well do "i4i8i8".
>>
>> Designing a signature hash where you select between these at compile-time is
>> perhaps doable but does generate a lot of code and makes everything
>> complicated.
>
> It especially gets messy when you're trying to pre-compute tables.
>
>> I think we should just start off with hashing at module load
>> time when sizes are known, and then work with heuristics and/or build system
>> integration to improve on that afterwards.
>
> Finding 10,000 optimal tables at runtime better be really cheap than
> for Sage's sake :).

The code is highly unpolished as I write this, but it works so here's 
some preliminary benchmarks.

Assuming the 64-bit pre-hashes are already computed, hashing a 64-slot 
table varies between 5 and 10 us (microseconds) depending on the set of 
hashes.

Computing md5's with C code from ulib (not hashlib/OpenSSL) takes ~400ns 
per hash, so 26 us for the 64-slot table => it dominates!

The crapwow64 hash takes ~10-20 ns, for ~1 us per 64-slot table. 
Admittedly, that's with hand-written non-portable assembly for the 
crapwow64.

Assuming 10 000 64-slot tables we're looking at something like 0.3-0.4 
seconds for loading Sage using md5, or 0.1 seconds using crapwow64.

https://github.com/dagss/pyextensibletype/blob/master/include/perfecthash.h

http://www.team5150.com/~andrew/noncryptohashzoo/CrapWow64.html

Dag