Re: [Cython] CEP1000: Native dispatch through callables
I'm afraid I'm going to try to kick this thread alive again. I want us to have something that Travis can implement in numba and "his" portion of SciPy, and also that could be used by NumPy devs. Since the decisions are rather arbitrary, perhaps we can try to quickly get to the "+1" stage (or, depending on how things turn out, a tournament starting with at most one proposal per person). On 04/20/2012 09:30 AM, Robert Bradshaw wrote: On Thu, Apr 19, 2012 at 6:18 AM, Dag Sverre Seljebotn wrote: On 04/19/2012 01:20 PM, Nathaniel Smith wrote: On Thu, Apr 19, 2012 at 11:56 AM, Dag Sverre Seljebotn wrote: I thought of some drawbacks of getfuncptr: - Important: Doesn't allow you to actually inspect the supported signatures, which is needed (or at least convenient) if you want to use an FFI library or do some JIT-ing. So an iteration mechanism is still needed in addition, meaning the number of things for the object to implement grows a bit large. Default implementations help -- OTOH there really wasn't a major drawback with the table approach as long as JIT's can just replace it? But this is orthogonal to the table vs. getfuncptr discussion. We're assuming that the table might be extended at runtime, which means you can't use it to determine which signatures are supported. So we need some sort of extra interface for the caller and callee to negotiate a type anyway. (I'm intentionally agnostic about whether it makes more sense for the caller or the callee to be doing the iterating... in general type negotiation could be quite complicated, and I don't think we know enough to get that interface right yet.) Hmm. Right. Let's define an explicit goal for the CEP then. What I care about at is getting the spec right enough such that, e.g., NumPy and SciPy, and other (mostly manually written) C extensions with slow development pace, can be forward-compatible with whatever crazy things Cython or Numba does. There's 4 cases: 1) JIT calls JIT (ruled out straight away) 2) JIT calls static: Say that Numba wants to optimize calls to np.sin etc. without special-casing; this seem to require reading a table of static signatures 3) Static calls JIT: This is the case when scipy.integrate routines calls a Numba callback and Numba generates a specialization for the dtype they explicitly needs. This calls for getfuncptr (but perhaps in a form which we can't quite determine yet?). 4) Static calls static: Either table or getfuncptr works. My gut feeling is go for 2) and 4) in this round => table. getfuncptr is really simple and flexible, but I'm with you on both of these to points, and the overhead was not trivial. It's interesting to hear you say the overhead was not trivial (that was my hunch too but I sort of yielded to peer pressure). I think SAGE has some history with this -- isn't one of the reasons for the "cpdef" vs. "cdef" split that "cpdef" has the cost of a single lookup for the presence of a __dict__ on the object, which was an unacceptable penalty for parts of Sage? That can't have been much more than a 1ns penalty per instance. Of course we could offer both, i.e. look at the table first, if it's not there call getfuncptr if it's non-null, then fall back to "slow" call or error. These are all opt-in depending on how hard you want to try to optimize things. That's actually exactly what I was envisioning -- in time (with JITs on both ends) the table could act sort of as a cache for commonly used overloads, and getfuncptr would access the others more slowly. As far as keys vs. interning, I'm also tempted to try to have my cake and eat it too. Define a space-friendly encoding for signatures and require interning for anything that doesn't fit into a single sizeof(void*). The fact that this cutoff would vary for 32 vs 64-bit would require some care, but could be done with macros in C. If the signatures produce non-aligned "pointer" values there won't be any collisions, and this way libraries only have to share in the global (Python-level?) interning scheme iff they want to expose/use "large" signatures. That was the approach I described to Nathaniel as having the "worst features of both" -- lack of readable gdb dumps of the keys, and having to define an interning mechanism for use by the 5% cases that don't fit. To sum up hat's been said earlier: The only thing that would blow the key size above 64 bits except very many arguments would be things like classes/interfaces/vtables. But in that case, reasonable-sized keys for the vtables can be computed (whether by interning, cryptographic hashing, or a GUID like Microsoft COM). So I'm still +1 on my proposal; but I would be happy with an intern-based proposal if somebody bothers to flesh it out a bit (I don't quite know how I'd do it and would get lost in PyObject* vs. char* and cross-language state sharing...). My proposal in summary: - Table with variable-sized entries (not getfuncptr, not interning)
Re: [Cython] CEP1000: Native dispatch through callables
On Thu, May 3, 2012 at 5:24 AM, Dag Sverre Seljebotn wrote: > I'm afraid I'm going to try to kick this thread alive again. I want us to > have something that Travis can implement in numba and "his" portion of > SciPy, and also that could be used by NumPy devs. That's great, I'd like to get things moving forward on this. > Since the decisions are rather arbitrary, perhaps we can try to quickly get > to the "+1" stage (or, depending on how things turn out, a tournament > starting with at most one proposal per person). > > > On 04/20/2012 09:30 AM, Robert Bradshaw wrote: >> >> On Thu, Apr 19, 2012 at 6:18 AM, Dag Sverre Seljebotn >> wrote: >>> >>> On 04/19/2012 01:20 PM, Nathaniel Smith wrote: On Thu, Apr 19, 2012 at 11:56 AM, Dag Sverre Seljebotn wrote: > > > I thought of some drawbacks of getfuncptr: > > - Important: Doesn't allow you to actually inspect the supported > signatures, which is needed (or at least convenient) if you want to use > an > FFI library or do some JIT-ing. So an iteration mechanism is still > needed > in > addition, meaning the number of things for the object to implement > grows > a > bit large. Default implementations help -- OTOH there really wasn't a > major > drawback with the table approach as long as JIT's can just replace it? But this is orthogonal to the table vs. getfuncptr discussion. We're assuming that the table might be extended at runtime, which means you can't use it to determine which signatures are supported. So we need some sort of extra interface for the caller and callee to negotiate a type anyway. (I'm intentionally agnostic about whether it makes more sense for the caller or the callee to be doing the iterating... in general type negotiation could be quite complicated, and I don't think we know enough to get that interface right yet.) >>> >>> >>> >>> Hmm. Right. Let's define an explicit goal for the CEP then. >>> >>> What I care about at is getting the spec right enough such that, e.g., >>> NumPy >>> and SciPy, and other (mostly manually written) C extensions with slow >>> development pace, can be forward-compatible with whatever crazy things >>> Cython or Numba does. >>> >>> There's 4 cases: >>> >>> 1) JIT calls JIT (ruled out straight away) >>> >>> 2) JIT calls static: Say that Numba wants to optimize calls to np.sin >>> etc. >>> without special-casing; this seem to require reading a table of static >>> signatures >>> >>> 3) Static calls JIT: This is the case when scipy.integrate routines >>> calls a >>> Numba callback and Numba generates a specialization for the dtype they >>> explicitly needs. This calls for getfuncptr (but perhaps in a form which >>> we >>> can't quite determine yet?). >>> >>> 4) Static calls static: Either table or getfuncptr works. >>> >>> My gut feeling is go for 2) and 4) in this round => table. >> >> >> getfuncptr is really simple and flexible, but I'm with you on both of >> these to points, and the overhead was not trivial. > > > It's interesting to hear you say the overhead was not trivial (that was my > hunch too but I sort of yielded to peer pressure). I think SAGE has some > history with this -- isn't one of the reasons for the "cpdef" vs. "cdef" > split that "cpdef" has the cost of a single lookup for the presence of a > __dict__ on the object, which was an unacceptable penalty for parts of Sage? > That can't have been much more than a 1ns penalty per instance. It's mostly historical, as a lot of Sage was written before cpdef existed (and people following this pattern after the fact). There are also some cases where cdef is used because the "leaf" classes are often in Python but have no need to override the given method, and an actual dictionary lookup would be required otherwise (e.g. in the coercion model). >> Of course we could offer both, i.e. look at the table first, if it's >> not there call getfuncptr if it's non-null, then fall back to "slow" >> call or error. These are all opt-in depending on how hard you want to >> try to optimize things. > > > That's actually exactly what I was envisioning -- in time (with JITs on both > ends) the table could act sort of as a cache for commonly used overloads, > and getfuncptr would access the others more slowly. OK, then +1 >> As far as keys vs. interning, I'm also tempted to try to have my cake >> and eat it too. Define a space-friendly encoding for signatures and >> require interning for anything that doesn't fit into a single >> sizeof(void*). The fact that this cutoff would vary for 32 vs 64-bit >> would require some care, but could be done with macros in C. If the >> signatures produce non-aligned "pointer" values there won't be any >> collisions, and this way libraries only have to share in the global >> (Python-level?) interning scheme iff they want to expose/use "large" >> signatures. > > > That was the approach I descri
