[Cython] CEP1000: Native dispatch through callables

[Robert Bradshaw]

On Fri, Apr 13, 2012 at 2:24 PM, Nathaniel Smith <njs at pobox.com> wrote:
> On Fri, Apr 13, 2012 at 9:27 PM, Dag Sverre Seljebotn
> <d.s.seljebotn at astro.uio.no> wrote:
>> Ah, I didn't think about 6-bit or huffman. Certainly helps.
>>
>> I'm almost +1 on your proposal now, but a couple of more ideas:
>>
>> 1) Let the key (the size_t) spill over to the next specialization entry if
>> it is too large; and prepend that key with a continuation code (two size-ts
>> could together say "iii)-d\0\0" on 32 bit systems with 8bit encoding, using
>> - as continuation). The key-based caller will expect a continuation if it
>> knows about the specialization, and the prepended char will prevent spurios
>> matches against the overspilled slot.
>>
>> We could even use the pointers for part of the continuation...
>
> I am really lost here. Why is any of this complicated encoding stuff
> better than interning? Interning takes one line of code, is incredibly
> cheap (one dict lookup per call site and function definition), and it
> lets you check any possible signature (even complicated ones involving
> memoryviews) by doing a single-word comparison. And best of all, you
> don't have to think hard to make sure you got the encoding right. ;-)
>
> On a 32-bit system, pointers are smaller than a size_t, but more
> expressive! You can still do binary search if you want, etc. Is the
> problem just that interning requires a runtime calculation? Because I
> feel like C users (like numpy) will want to compute these compressed
> codes at module-init anyway, and those of us with a fancy compiler
> capable of computing them ahead of time (like Cython) can instruct
> that fancy compiler to compute them at module-init time just as
> easily?

Good question.

The primary disadvantage of interning that I see is memory locality. I
suppose if all the C-level caches of interned values were co-located,
this may not be as big of an issue. Not being able to compare against
compile-time constants may thwart some optimization opportunities, but
that's less clear.

It also requires coordination common repository, but I suppose one
would just stick a set in some standard module (or leverage Python's
interning).

- Robert