[Cython] CEP1000: Native dispatch through callables

[mark florisson]

On 14 April 2012 22:02, Stefan Behnel <stefan_ml at behnel.de> wrote:
> Hi,
>
> thanks for writing this up. Comments inline as I read through it.
>
> Dag Sverre Seljebotn, 14.04.2012 21:08:
>> === GIL-less accesss ===
>>
>> It is OK to access the native-call table without holding the GIL. This
>> should of course only be used to call functions that state in their
>> signature that they don't need the GIL.
>>
>> This is important for JITted callables who would like to rewrite their
>> table as more specializations gets added; if one needs to reallocate
>> the table, the old table must linger along long enough that all
>> threads that are currently accessing it are done with it.
>
> The problem here is that changing the table in the face of threaded access
> is very likely to introduce race conditions, and the average library out
> there won't know when all threads are done with it. I don't think later
> modification is a good idea.
>
>
>> == Native dispatch descriptor ==
>>
>> The final format for the descriptor is not agreed upon yet; this sums
>> up the major alternatives.
>>
>> The descriptor should be a list of specializations/overload
>
> While overloaded signatures are great for the callee, they make things much
> more complicated for the caller. It's no longer just one signature that
> either matches or not. Especially when we allow more than one expected
> signature, then each of them has to be compared against all exported
> signatures.
>
> We'll have to see what the runtime impact and the impact on the code
> complexity is, I guess.
>
>
>> each described by a function pointer and a signature specification
>> string, such as "id)i" for {{{int f(int, double)}}}.
>
> How do we deal with object argument types? Do we care on the caller side?
> Functions might have alternative signatures that differ in the type of
> their object parameters. Or should we handle this inside of the caller and
> expect that it's something like a fused function with internal dispatch in
> that case?
>
> Personally, I think there is not enough to gain from object parameters that
> we should handle it on the caller side. The callee can dispatch those if
> necessary.
>
> What about signatures that require an object when we have a C typed value?
>
> What about signatures that require a C typed argument when we have an
> arbitrary object value in our call parameters?
>
> We should also strip the "self" argument from the parameter list of
> methods. That's handled by the attribute lookup before even getting at the
> callable.
>
>
>> === Approach 1: Interning/run-time allocated IDs ===
>>
>>
>> 1A: Let each overload have a struct
>> {{{
>> struct {
>>     size_t signature_id;
>>     char *signature;
>>     void *func_ptr;
>> };
>> }}}
>> Within each process run, there is a 1:1
>
> mapping/relation
>
>> between {{{signature}}} and
>> {{{signature_id}}}. {{{signature_id}}} is allocated by some central
>> registry.
>>
>> 1B: Intern the string instead:
>> {{{
>> struct {
>>     char *signature; /* pointer must come from the central registry */
>>     void *func_ptr;
>> };
>> }}}
>> However this is '''not'' trivial, since signature strings can
>> be allocated on the heap (e.g., a JIT would do this), so interned strings
>> must be memory managed and reference counted.
>
> Not necessarily, they are really short strings that could just live
> forever, stored efficiently by the registry in a series of larger memory
> blocks. It would take a while to fill up enough memory with those to become
> problematic. Finding an efficiently lookup scheme for them might become
> interesting at some point, but that would also take a while.
>
> I don't expect real-world systems to have to deal with thousands of
> different runtime(!) discovered signatures during one interpreter lifetime.
>
>
>> ==== Discussion ====
>>
>> '''The cost of comparing a signature''': Comparing a global variable (needle)
>> to a value that is guaranteed to already be in cache (candidate match)
>>
>> '''Pros:'''
>>
>>  * Conceptually simple struct format.
>>
>> '''Cons:'''
>>
>>  * Requires a registry for interning strings. This must be
>>    "handshaked" between the implementors of this CEP (probably by
>>    "first to get at {{{sys.modules["_nativecall"}}} sticks it there),
>>    as we can't ship a common dependency library for this CEP.
>
> ... which would eventually end up in the stdlib, but could equally well
> come from PyPI for now. I don't see a problem with that.
>
> Using sys.modules (or another global store) instead of an explicit import
> allows for dependency injection, that's good.
>
>
>> === Approach 2: Efficient strcmp of verbatim signatures ===
>>
>> The idea is to store the full signatures and the function pointers together
>> in the same memory area, but still have some structure to allow for quick
>> scanning through the list.
>>
>> Each entry has the structure {{{[signature_string, funcptr]}}}
>> where:
>>
>>  * The signature string has variable length, but the length is
>>    divisible by 8 bytes on all platforms. The {{{funcptr}}} is always
>>    8 bytes (it is padded on 32-bit systems).
>>
>>  * The total size of the entry should be divisible by 16 bytes (= the
>>    signature data should be 8 bytes, or 24 bytes, or...)
>>
>>  * All but the first chunk of signature data should start with a
>>    continuation character "-", i.e. a really long signature string
>>    could be {{{"iiiidddd-iiidddd-iiidddd-)d"}}}. That is, a "-" is
>>    inserted on all positions in the string divisible by 8, except the
>>    first.
>>
>> The point is that if you know a signature, you can quickly scan
>> through the binary blob for the signature in 128 bit increments,
>> without worrying about the variable size nature of each entry.  The
>> rules above protects against spurious matches.
>
> Sounds pretty fast to me. Absolutely worth trying. And if we store the
> signature we compare against in the same format, we won't have to parse the
> signature string as such, we can really just compare the numeric values.
> Assuming that's really fast, that would allow the callee to optimistically
> export additional signatures, e.g. with compatible subtypes or easily
> coercible types, ordered by the expected overhead of processing the
> arguments (and the expected probability of being called), so that the
> caller would automatically hit the fastest call path first when traversing
> the list from start to end. The number of possible signatures would
> obviously explode at some point...
>
> Note that JITs could still be smart enough to avoid the traversal after a
> few loop iterations.
>
> One problem: if any of the call parameters is a plain object type, identity
> matches may not work anymore because we won't know what signature to expect.
>
>
>> ==== Optional: Encoding ====
>>
>> The strcmp approach can be made efficient for larger signatures by
>> using a more efficient encoding than ASCII. E.g., an encoding could
>> use 4 bits for the 12 most common symbols and 8 bits
>> for 64 symbols (for a total of 78 symbols), of which some could be
>> letter combinations ("Zd", "T{"). This should be reasonably simple
>> to encode and decode.
>>
>> The CEP should provide C routines in a header file to work with the
>> signatures. Callers that wish to parse the format string and build a
>> call stack on the fly should probably work with the encoded
>> representation.
>
> Huffman codes can be processed bitwise from start to end, that would work.
>
> However, this would quickly die when we start adding arbitrary object
> types. That would require a global registry for user types again. A reason
> not to care about object types at the caller.
>
> Also, how do we encode struct/union argument types?
>
>
>> ==== Discussion ====
>>
>> '''The cost of comparing a signature''': For the vast majority of
>> functions, the cost is comparing a 64-bit number stored in the CPU
>> instruction stream (needle) to a value that is guaranteed to already
>> be in cache (candidate match).
>>
>> '''Pros:'''
>>
>>  * Readability-wise, one can use the C switch statement to dispatch
>>
>>  * "Stateless data", for compiled code it does not require any
>>    run-time initialization like interning does
>>
>>  * One less pointer-dereference in the common case of a short
>>    signature
>>
>> '''Cons:'''
>>
>>  * Long signatures will require more than 8 bytes to store and could
>>    thus be more expensive than interned strings
>
> We could also ignore trailing arguments and only dispatch based on a fixed
> number of first arguments. Callees with more arguments would then simply
> not export native signatures.
>
>
>>  * Format looks uglier in the form of literals in C source code
>
> They are not meant for reading, and we can always generate a comment with a
> spelled-out readable signature next to it.
>
>
>> == Signature strings ==
>>
>> Example: The function
>> {{{
>> int f(double x, float y);
>> }}}
>> would have the signature string {{{"df)i"}}} (or, to save space, {{{"idf"}}}).
>>
>> Fields would follow the PEP3118 extensions of the struct-module format
>> string, but with some modifications:
>>
>>  * The format should be canonical and fit for {{{strcmp}}}-like
>>    comparison: No whitespace, no field names (TBD: what else?)
>>
>>  * TBD: Information about GIL requirements (nogil, with gil?), how
>>    exceptions are reported
>
> What about C++, including C++ exceptions?
>
>
>>  * TBD: Support for Cython-specific constructs like memoryview slices
>>    (so that arrays with strides and shape can be passed faster than
>>    passing an {{{"O"}}}).
>
> Is this really Cython specific or would a generic Py_buffer struct work?

That could work through simple unboxing wrapper functions, but it
would add some overhead, specifically because it would have to check
the buffer's object, and if it didn't exist or was not a memoryview
object, it would have to create one (checking whether something is a
memoryview object would also be a pain, as each module has a different
memoryview type). That could still be feasible for interaction with
Cython functions from non-Cython code.

> Stefan
> _______________________________________________
> cython-devel mailing list
> cython-devel at python.org
> http://mail.python.org/mailman/listinfo/cython-devel