[Numpy-discussion] moving forward around ABI/API compatibilities (was numpy 1.7.x branch)

[Dag Sverre Seljebotn]

On 06/26/2012 01:48 PM, David Cournapeau wrote:
> Hi,
>
> I am just continuing the discussion around ABI/API, the technical side
> of things that is, as this is unrelated to 1.7.x. release.
>
> On Tue, Jun 26, 2012 at 11:41 AM, Dag Sverre Seljebotn
> <d.s.seljebotn at astro.uio.no>  wrote:
>> On 06/26/2012 11:58 AM, David Cournapeau wrote:
>>> On Tue, Jun 26, 2012 at 10:27 AM, Dag Sverre Seljebotn
>>> <d.s.seljebotn at astro.uio.no>    wrote:
>>>> On 06/26/2012 05:35 AM, David Cournapeau wrote:
>>>>> On Tue, Jun 26, 2012 at 4:10 AM, Ondřej Čertík<ondrej.certik at gmail.com>      wrote:
>>>>>
>>>>>>
>>>>>> My understanding is that Travis is simply trying to stress "We have to
>>>>>> think about the implications of our changes on existing users." and
>>>>>> also that little changes (with the best intentions!) that however mean
>>>>>> either a breakage or confusion for users (due to historical reasons)
>>>>>> should be avoided if possible. And I very strongly feel the same way.
>>>>>> And I think that most people on this list do as well.
>>>>>
>>>>> I think Travis is more concerned about API than ABI changes (in that
>>>>> example for 1.4, the ABI breakage was caused by a change that was
>>>>> pushed by Travis IIRC).
>>>>>
>>>>> The relative importance of API vs ABI is a tough one: I think ABI
>>>>> breakage is as bad as API breakage (but matter in different
>>>>> circumstances), but it is hard to improve the situation around our ABI
>>>>> without changing the API (especially everything around macros and
>>>>> publicly accessible structures). Changing this is politically
>>>>
>>>> But I think it is *possible* to get to a situation where ABI isn't
>>>> broken without changing API. I have posted such a proposal.
>>>> If one uses the kind of C-level duck typing I describe in the link
>>>> below, one would do
>>>>
>>>> typedef PyObject PyArrayObject;
>>>>
>>>> typedef struct {
>>>>      ...
>>>> } NumPyArray; /* used to be PyArrayObject */
>>>
>>> Maybe we're just in violent agreement, but whatever ends up being used
>>> would require to change the *current* C API, right ? If one wants to
>>
>> Accessing arr->dims[i] directly would need to change. But that's been
>> discouraged for a long time. By "API" I meant access through the macros.
>>
>> One of the changes under discussion here is to change PyArray_SHAPE from
>> a macro that accepts both PyObject* and PyArrayObject* to a function
>> that only accepts PyArrayObject* (hence breakage). I'm saying that under
>> my proposal, assuming I or somebody else can find the time to implement
>> it under, you can both make it a function and have it accept both
>> PyObject* and PyArrayObject* (since they are the same), undoing the
>> breakage but allowing to hide the ABI.
>>
>> (It doesn't give you full flexibility in ABI, it does require that you
>> somewhere have an "npy_intp dims[nd]" with the same lifetime as your
>> object, etc., but I don't consider that a big disadvantage).
>>
>>> allow for changes in our structures more freely, we have to hide them
>>> from the headers, which means breaking the code that depends on the
>>> structure binary layout. Any code that access those directly will need
>>> to be changed.
>>>
>>> There is the particular issue of iterator, which seem quite difficult
>>> to make "ABI-safe" without losing significant performance.
>>
>> I don't agree (for some meanings of "ABI-safe"). You can export the data
>> (dataptr/shape/strides) through the ABI, then the iterator uses these in
>> whatever way it wishes consumer-side. Sort of like PEP 3118 without the
>> performance degradation. The only sane way IMO of doing iteration is
>> building it into the consumer anyway.
>
> (I have not read the whole cython discussion yet)

So here's the summary. It's rather complicated but also incredibly neat 
:-) And technical details can be hidden behind a tight API.

  - We introduce a C-level metaclass, "extensibletype", which to each 
type adds a branch-miss-free string->pointer hash table. The ndarray 
type is made an instance of this metaclass, so that you can do

PyCustomSlots_GetTable(array_object->ob_type)

  - The hash table uses a perfect hashing scheme:

   a) We take the lower 64 bits of md5 of the lookup string (this can be 
done compile-time or module-load-time) as a pre-hash "h".

   b) When looking up the table for a key with pre-hash "h", the index 
in the table is given by

((h >> table->r) & table->m1) ^ table->d[r & table->m2]

Then, *if* the element is present, it will always be found on the first 
try; the table is guaranteed collisionless. This means that an expensive 
branch-miss can be avoided. It is really incredibly fast in practice, 
with a 0.5 ns penalty on my 1.8 GHz laptop.

The magic is in finding the right table->r and table->d. For a 64-slot 
table, parameters r and d[0]..d[63] can be found in 10us on my machine 
(it's an O(n) operation). (table->d[i] has type uint16_t)

(This algorithm was found in an academic paper which I'm too lazy to dig 
up from that thread right now; perfect hashing is an active research field.)

The result? You can use this table to store function pointers in the 
type, like C++ virtual tables or like the built-in slots like 
tp_get_buffer, but *without* having to agree on everything at 
compile-time like in C++. And the only penalty is ~0.5 ns per call and 
some cache usage.

Cython would use this to replace the current custom "cdef class" vtable 
with something more tools could agree on, e.g. store function pointers 
in the table with keys like

"method:foo:i4i8->f4"

But NumPy could easily store entries relating to its C API in the same 
hash table,

"numpy:SHAPE"

Then, the C API functions would all take PyObject*, look up the fast 
hash table on the ob_type.

This allows for incredibly flexible duck typing on the C level.

PyArray_Check would just check for the presence of the C API but not 
care about the actual Python type, i.e., no PyObject_TypeCheck.

Me and Robert have talked a lot about this and will move forward with it 
for Cython. Obviously I don't expect others than me to pick it up for 
NumPy so we'll see... I'll write up a specification document sometimes 
over the next couple of weeks as we need that even if only for Cython.

Dag