On 06/26/2012 04:08 PM, Dag Sverre Seljebotn wrote:
> 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.seljeb...@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.seljeb...@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.cer...@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]Sorry, typo. Should be ((h >> table->r) & table->m1) ^ table->d[h & table->m2] What happens is that "h & table->m2" sorts the keys of the table into n buckets. Then "r" is selected (among 64 possible choices) so that there's no intra-bucket collisions. Finally, d is chosen so that none of the buckets collide, starting with the largest one. Dag > > 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 _______________________________________________ NumPy-Discussion mailing list NumPy-Discussion@scipy.org http://mail.scipy.org/mailman/listinfo/numpy-discussion
