[Cython] Hash-based vtables

[Robert Bradshaw]

On Sun, Jun 10, 2012 at 1:43 AM, Dag Sverre Seljebotn
<d.s.seljebotn at astro.uio.no> wrote:
> On 06/10/2012 10:23 AM, Robert Bradshaw wrote:
>>
>> On Sun, Jun 10, 2012 at 1:00 AM, Dag Sverre Seljebotn
>> <d.s.seljebotn at astro.uio.no>  wrote:
>>>
>>> On 06/10/2012 09:34 AM, Robert Bradshaw wrote:
>>>>
>>>>
>>>> On Sun, Jun 10, 2012 at 12:14 AM, Dag Sverre Seljebotn
>>>> <d.s.seljebotn at astro.uio.no>    wrote:
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> Robert Bradshaw<robertwb at gmail.com>    wrote:
>>>>>
>>>>>> On Fri, Jun 8, 2012 at 10:45 PM, Dag Sverre Seljebotn
>>>>>> <d.s.seljebotn at astro.uio.no>    wrote:
>>>>>>>
>>>>>>>
>>>>>>> I'd love to not do interning, but I see no way around it.
>>>>>>
>>>>>>
>>>>>>
>>>>>> No, I want to use the lower 64 bits by default, but always have the
>>>>>> top 96 bits around to allow using this mechanism in "secure" mode at a
>>>>>> slight penalty. md5 is out because there are known collisions. (Yes,
>>>>>> sha-1 may succumb sooner rather than later, theoretical weaknesses
>>>>>> have been shown, so we could look to using something else (hopefully
>>>>>> still shipped with Python).
>>>>>
>>>>>
>>>>>
>>>>> But very few users are going to know about this. What's the odds that
>>>>> the
>>>>> user who decide to trigger JIT-compilation with function signatures
>>>>> that
>>>>> varies based on the input will know about the option and turn it on and
>>>>> also
>>>>> recompile all his/her C extension modules?
>>>>>
>>>>> In practice, such an option would always stay at its default value. If
>>>>> we
>>>>> leave it to secure by default and start teaching it to users from the
>>>>> start...but that's a big price to pay.
>>>>
>>>>
>>>>
>>>> Yes, it's not ideal from this perspective.
>>>>
>>>>> And if you *do* want to run in secure mode, it will be a lot slower
>>>>> than
>>>>> interning.
>>>>
>>>>
>>>>
>>>> Are you thinking that the 64-bit interned pointer would be used as the
>>>> hash? In this case all hashtables would have to be constructed at
>>>> runtime, which means it needs to be really, really cheap (well under a
>>>> milisecond, I'm sure Sage has>1000 classes,>10000 methods it imports
>>>> at startup). Also I'm not sure how the very-uneven distribution would
>>>> play out for constructing perfect hastables (perhaps it won't hurt,
>>>> there's likely to be long runs of consecutive values in some cases.
>>>
>>>
>>>
>>> No, I'm thinking that callsites need both the 64-bit interned char* and
>>> the
>>> 64-bit hash of the *contents*. They use the hash to figure out the
>>> position,
>>> then compare by ID.
>>
>>
>> Ah, I missed that bit. OK, yes, that could work well.
>
>
> Ah, we've been talking past one another for some time then. OK, let's settle
> on that.
>
>
>>
>>> The hash is not stored in callees, it's discarded after figuring out the
>>> table layout.
>>>
>>> (There was this idea that if the char* has least significant bit set,
>>> we'd
>>> hash it directly rather than dereference it, but let's ignore that for
>>> now.)
>>
>>
>> (For the purpose of this discussion, it's part of the "interning" step.)
>>
>>> I don't think under a millisecond is unfeasible to hash smallish tables
>>> --
>>> we could put the pointer through a cheap hash to create more entropy (for
>>> the perfect hashing, being able to select a hash function through the>>r
>>> is
>>> important, so you can't just use the pointer directly -- but there are
>>> functions cheaper than md5, e.g, in here: http://code.google.com/p/ulib/)
>>
>>
>> Just a sec, we're not hashing pointers, but the full signature itself,
>> right? For our hash function we need
>>
>> (1) Collision free on 64-bits (for non-malicious use).
>> (2) Good distribution (including for short strings, which is harder to
>> come by).
>> (2b) Any small subset of bits should have property (2).
>> (3) Ideally easy to reference (e.g. "md5" is better than "these 100
>> lines of C code").
>>
>> Cheap runtime construction is still ideal, but much less of an issue
>> if hashes (and perfect tables) can be constructed at compile time,
>> which I think this scheme allows.
>
>
> Yes, 64 bits of md5 then?

+1 for me.

> ulib contains "100 lines of C code" for md5
> anyway, if one doesn't want to go through Python hashlib (I imagine e.g.
> hashlib might be unavailable somewhere as it relies on openssl and there's
> license war going on vs. gnutls and so on. And the md5 module is
> deprecated.).

Just the interface, right? (hashlib should be used instead...)

>>> That would save us a register and make the instructions shorter in some
>>> places I guess...I think it's really miniscule, it's not like the effect
>>> of
>>> load of a global variable. But if you like this approach I can benchmark
>>> C-written hashtable creation and see.
>>
>>
>> This will have value in and of itself (both the implementation and the
>> benchmarks).
>
>
> Will do (eventually, less spare time in coming week).
>
> 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.

> "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 :).

- Robert