fused types as parts of structures

[shaunc]

I'm trying to create a "max-heap" that works with longs and floats.


ctypedef fused element_t:
long
double

cdef struct heap:
ulong capacity
element_t *data


cdef heap_init( ulong capacity, heap_t heap ) nogil:
heap.capacity = capacity
heap.data = <element_t>malloc( capacity *
sizeof( heap.data[ 0 ] ) )
for i in range( capacity ):
if heap.data[ 0 ] is long:
heap.data[ i ] = LONG_MIN
else:
heap.data[ i ] = DBL_MIN

However, I get "Type is not specialized" on the cast from malloc. I
have gotten this to compile by changing type of "data" to void *, and
declaring a dummy element_t:

cdef void heap_init( ulong capacity, heap_t heap, element_t element )
nogil:
heap.capacity = capacity
heap.data = malloc( capacity * sizeof( element ) )
if element_t is long:
for i in range( capacity ):
(<element_t *>heap.data)[ i ] = LONG_MIN
elif element_t is double:
for i in range( capacity ):
(<element_t *>heap.data)[ i ] = DBL_MIN
else:
with gil:
raise TypeError( "Unsupported heap type" )

However, this is (IMHO) an ugly hack... is there any way to refer to
the type of the specialized element in "heap_t"?

(NB, my favority syntax would be:

heap.data = <heap_t.element_t *>malloc( capacity *
sizeof( heap_t.element_t ) )

But that doesn't work...)

Thanks!

[mark florisson]

You can fuse the structs themselves, which is admittedly less elegant
than fusing a single element of a struct. i.e.

ctypedef struct heap_long:
ulong capacity
long *data

ctypedef struct heap_double:
ulong capacity
double *data

cdef fused heap_t:
heap_long
heap_double

[shaunc]

>
> You can fuse the structs themselves, which is admittedly less elegant
> than fusing a single element of a struct. i.e.
>
> ctypedef struct heap_long:
>     ulong capacity
>     long *data
>
> ctypedef struct heap_double:
>     ulong capacity
>     double *data
>
> cdef fused heap_t:
>     heap_long
>     heap_double

Thanks, Mark!

... now I'm also getting:


@cython.boundscheck( False )
def get_elements( N.ndarray[ element_t, ndim = 1 ] elements ):
^
------------------------------------------------------------

/Users/shauncutts/src/python/factfiber/stat/pmodel/c/max_heap.pyx:
128:4: Compiler crash in AnalyseDeclarationsTransform

I presume I should also fuse the ndarray types? Or is this "just a
bug" :)?

[shaunc]

update:

In fact, you can't fuse different ndarrays:

ctypedef N.ndarray[ N.long_t, ndim = 1 ] vector_long_t 

ctypedef N.ndarray[ N.float64_t, ndim = 1 ] vector_float_t

cdef fused vector_t:

    vector_long_t

    vector_float_t

on the first ctypedef, I get: "Buffer types only allowed as function local variables"

so "fusing structure" doesn't seem to be an option for ndarrays...

[shaunc]

update #2:

using info from another post I was able to fuse the ndarray

cdef fused vector_t:

    N.ndarray[ N.long_t, ndim = 1 ]

    N.ndarray[ N.float64_t, ndim = 1 ]

however, I still get a compiler crash:

cdef class MaxHeap( object ):

    cdef heap_t heap

# ...

    def get_elements( vector_t elements ):

   ^

------------------------------------------------------------

/Users/shauncutts/src/python/factfiber/stat/pmodel/c/max_heap.pyx:164:4: Compiler crash in AnalyseDeclarationsTransform

ModuleNode.body = StatListNode(max_heap.pyx:24:0)

StatListNode.stats[20] = StatListNode(max_heap.pyx:144:5)

StatListNode.stats[0] = CClassDefNode(max_heap.pyx:144:5,

    as_name = u'MaxHeap',

    class_name = u'MaxHeap',

    module_name = u'',

    visibility = u'private')

CClassDefNode.body = StatListNode(max_heap.pyx:145:4)

StatListNode.stats[4] = CompilerDirectivesNode(max_heap.pyx:164:4)

CompilerDirectivesNode.body = StatListNode(max_heap.pyx:164:4)

StatListNode.stats[0] = DefNode(max_heap.pyx:164:4,

    has_fused_arguments = True,

    modifiers = [...]/0,

    name = u'get_elements',

    num_required_args = 1,

    py_wrapper_required = True,

    reqd_kw_flags_cname = '0')

File 'Nodes.py', line 2265, in __init__: FusedCFuncDefNode(max_heap.pyx:164:4,

    nodes = [...]/0)

File 'Nodes.py', line 2305, in copy_def: FusedCFuncDefNode(max_heap.pyx:164:4,

    nodes = [...]/0)

Compiler crash traceback from this point on:

  File "/Library/Python/2.7/site-packages/Cython/Compiler/Nodes.py", line 2305, in copy_def

    permutations = PyrexTypes.get_all_specialized_permutations(fused_compound_types)

  File "/Library/Python/2.7/site-packages/Cython/Compiler/PyrexTypes.py", line 2644, in get_all_specialized_permutations

    return _get_all_specialized_permutations(unique(fused_types))

  File "/Library/Python/2.7/site-packages/Cython/Compiler/PyrexTypes.py", line 2647, in _get_all_specialized_permutations

    fused_type, = fused_types[0].get_fused_types()

IndexError: list index out of range

[mark florisson]

Hm, could you post the full code (or a full minimal working example)?

[shaunc]

Ok ... well given:

cdef struct heap_long_t:

    ulong capacity

    long *data

cdef struct heap_double_t:

    ulong capacity

    double *data

cdef fused heap_t:

    heap_long_t

    heap_double_t

Then the following two "work" -- the question is how to fuse the ndarray types, so I can have just one routine?

@cython.boundscheck( False )

cdef void heap_copy_to_long_vector( 

        heap_long_t heap, N.ndarray[ N.long_t, ndim = 1 ] vector 

        ):

    '''

    copy elements from long heap to vector

    

    .. note: problem with fused version because of ndarray

    '''

    for i in range( heap.capacity ):

        vector[ i ] = heap.data[ i ]

        

@cython.boundscheck( False )

cdef void heap_copy_to_double_vector( 

        heap_double_t heap, N.ndarray[ N.float64_t, ndim = 1 ] vector 

        ):

    '''

    copy elements from long heap to vector

    

    .. note: problem with fused version because of ndarray

    '''

    for i in range( heap.capacity ):

        vector[ i ] = heap.data[ i ]

[mark florisson]

The problem is the typedef that doesn't work here, you can fuse
ndarrays like this:

cimport numpy as N

cdef fused vector_t:

N.ndarray[ N.long_t, ndim = 1 ]

N.ndarray[ N.float64_t, ndim = 1 ]

You can combine it with the fused structs as another fused type, but
that would give you some specializations that are invalid (you could
match for that and raise an exception though...).

[Stefan Behnel]

mark florisson, 30.04.2012 10:22:

Sounds like this should go into the NumPy documentation page for now.

Stefan

[mark florisson]

Ah, you made two mistakes. The first is that you forgot to declare
'self' in your method, which leads to the compiler crash. The second
is that you use a fused type as a class attribute, which is not
supported.

[mark florisson]

Perhaps that's a good idea. It's briefly hinted at here though:
http://docs.cython.org/src/userguide/fusedtypes.html#fused-types-and-arrays

[mark florisson]

At some point we discussed allowing fused types as part of fused
types, e.g. struct attributes, dtypes, etc. Only in the case of
structs and unions would this be really useful, as you can't specify
the fused part in an argument declaration itself. It's really not
different from e.g.

cdef func(cython.floating (*f)(cython.floating, cython.integral)):
...

except it happens up-front. The semantics here are:

1) if a compound type has one elementary type as a fused type,
specialize on the elementary type
-> example: cython.floating[:] -> specialize on float, double, ...

2) if a compound type has multiple elementary fused types,
specialize on the entire type
-> example: the function as above, a struct with multiple
fused attributes -> specialize on the entire type (this may mean the
user has to define those entire types if they want to explicitly
specialize)

What do you think?

[Stefan Behnel]

mark florisson, 30.04.2012 10:29:

> On 29 April 2012 15:56, shaunc wrote:
>> File "/Library/Python/2.7/site-packages/Cython/Compiler/PyrexTypes.py",
>> line 2647, in _get_all_specialized_permutations
>> fused_type, = fused_types[0].get_fused_types()
>> IndexError: list index out of range
>>
>
> Ah, you made two mistakes. The first is that you forgot to declare
> 'self' in your method, which leads to the compiler crash.

It's still a bug that it crashes, though. Should raise an error instead
when the type declared for the first argument of an extension type method
is not compatible with "self". And the above traceback looks like the fused
types code should check if there really is a matching permutation.

> The second
> is that you use a fused type as a class attribute, which is not
> supported.

That's unfortunate, though understandable. It would mean that the class
itself gets multiplied, I guess, so this could end up being quite involved.
And I don't think it could be done without user visible quirks, e.g. when
typing variables as that class or type checking against it. Sounds like it
would take some major effort.

Another error case for now, I guess.

Stefan

[Stefan Behnel]

mark florisson, 30.04.2012 10:44:

> At some point we discussed allowing fused types as part of fused
> types, e.g. struct attributes, dtypes, etc. Only in the case of
> structs and unions would this be really useful, as you can't specify
> the fused part in an argument declaration itself. It's really not
> different from e.g.
>
> cdef func(cython.floating (*f)(cython.floating, cython.integral)):
> ...
>
> except it happens up-front. The semantics here are:
>
> 1) if a compound type has one elementary type as a fused type,
> specialize on the elementary type
> -> example: cython.floating[:] -> specialize on float, double, ...
>
> 2) if a compound type has multiple elementary fused types,
> specialize on the entire type
> -> example: the function as above, a struct with multiple
> fused attributes -> specialize on the entire type (this may mean the
> user has to define those entire types if they want to explicitly
> specialize)
>
> What do you think?

Is this really all that useful? Wouldn't you just use a union in C instead
if you want to store multiple types in the same field of a struct?

I think we might run into the same quirks as for fused extension type
attributes at some point.

The use case at hand (as far as I understand it) was building up an entire
heap implementation based on a struct with a fused item type. That would
mean that the entire implementation gets specialised for each item type.
That's potentially a huge amount of struct data types and associated code
that we generate there, without a serious benefit.

I think, if fused types are to be used here, it would be much better to
make the heap items array a void* and store the heap item type (maybe as an
enum) as part of the heap struct. The rest can be done with fused types
already, simply by casting to the proper item array type before passing it
into the fused heap implementation. And as an additional bonus, it would be
trivial to hide all of it behind an extension type façade.

Personally, I wouldn't invest too much time into fused structs for now and
just make them an error with a clearly understandable message, until we
have a valid use case that we can build this feature around.

Stefan

[mark florisson]

Yeah, they should give proper errors. I guess there's so many
different possible cases to not use them correctly, that I haven't had
them all handled.

[mark florisson]

On 30 April 2012 10:21, Stefan Behnel <stef...@behnel.de> wrote:
> mark florisson, 30.04.2012 10:44:
>> At some point we discussed allowing fused types as part of fused
>> types, e.g. struct attributes, dtypes, etc. Only in the case of
>> structs and unions would this be really useful, as you can't specify
>> the fused part in an argument declaration itself. It's really not
>> different from e.g.
>>
>> cdef func(cython.floating (*f)(cython.floating, cython.integral)):
>>     ...
>>
>> except it happens up-front. The semantics here are:
>>
>>     1) if a compound type has one elementary type as a fused type,
>> specialize on the elementary type
>>         -> example: cython.floating[:] -> specialize on float, double, ...
>>
>>     2) if a compound type has multiple elementary fused types,
>> specialize on the entire type
>>         -> example: the function as above, a struct with multiple
>> fused attributes -> specialize on the entire type (this may mean the
>> user has to define those entire types if they want to explicitly
>> specialize)
>>
>> What do you think?
>
> Is this really all that useful? Wouldn't you just use a union in C instead
> if you want to store multiple types in the same field of a struct?
>
> I think we might run into the same quirks as for fused extension type
> attributes at some point.

Indeed. So maybe it would be better to for structs also list the
specializations as part of the struct type. For things like function
pointers you simply list the entire thing.

So specializing structs/ext classes: StructOrClass[float, int]
Function pointers: int (*)(float, int)

> The use case at hand (as far as I understand it) was building up an entire
> heap implementation based on a struct with a fused item type. That would
> mean that the entire implementation gets specialised for each item type.
> That's potentially a huge amount of struct data types and associated code
> that we generate there, without a serious benefit.

And that's exactly what you want, as you want to keep a list of items
of a specific type. If you want to support many types, you're going to
have to duplicate the code, or do a lot of checks on the dtype. In
case of a union, you're going to have to specialcase which attribute
you're going to access, which you want to be automatic. I don't think
this use case is very common, but not supporting it is also a
limitation. That said, it's also not very high on my priority list,
but I think it'd be nice to support if and when extension classes are
also supported.

[Stefan Behnel]

mark florisson, 30.04.2012 12:02:

> On 30 April 2012 10:21, Stefan Behnel wrote:
>> The use case at hand (as far as I understand it) was building up an entire
>> heap implementation based on a struct with a fused item type. That would
>> mean that the entire implementation gets specialised for each item type.
>> That's potentially a huge amount of struct data types and associated code
>> that we generate there, without a serious benefit.
>
> And that's exactly what you want, as you want to keep a list of items
> of a specific type. If you want to support many types, you're going to
> have to duplicate the code, or do a lot of checks on the dtype. In
> case of a union, you're going to have to specialcase which attribute
> you're going to access, which you want to be automatic. I don't think
> this use case is very common, but not supporting it is also a
> limitation.

I do not consider it a limitation that we do not support an uncommon use
case in the syntactically easiest(?) possible way. See below for a straight
forward way to deal with the specific use case at hand without having to
duplicate any code on the user side.

>> I think, if fused types are to be used here, it would be much better to
>> make the heap items array a void* and store the heap item type (maybe as an
>> enum) as part of the heap struct. The rest can be done with fused types
>> already, simply by casting to the proper item array type before passing it
>> into the fused heap implementation. And as an additional bonus, it would be
>> trivial to hide all of it behind an extension type façade.
>>
>> Personally, I wouldn't invest too much time into fused structs for now and
>> just make them an error with a clearly understandable message, until we
>> have a valid use case that we can build this feature around.

I consider fused types a way to optimise code by trading code complexity
and size for speed. If users have to deal with non-performance critical
code (such as what I describe above) in a more generic way without help by
fused types, I'm totally ok with that. After all, we wanted something
that's simpler than C++ templates and we should keep it that way.

Stefan

[Stefan Behnel]

mark florisson, 30.04.2012 11:57:

> On 30 April 2012 09:45, Stefan Behnel wrote:
>> mark florisson, 30.04.2012 10:29:
>>> On 29 April 2012 15:56, shaunc wrote:
>>>> File "/Library/Python/2.7/site-packages/Cython/Compiler/PyrexTypes.py",
>>>> line 2647, in _get_all_specialized_permutations
>>>> fused_type, = fused_types[0].get_fused_types()
>>>> IndexError: list index out of range
>>>>
>>>
>>> Ah, you made two mistakes. The first is that you forgot to declare
>>> 'self' in your method, which leads to the compiler crash.
>>
>> It's still a bug that it crashes, though. Should raise an error instead
>> when the type declared for the first argument of an extension type method
>> is not compatible with "self". And the above traceback looks like the fused
>> types code should check if there really is a matching permutation.
>>
>>
>>> The second
>>> is that you use a fused type as a class attribute, which is not
>>> supported.
>>
>> That's unfortunate, though understandable. It would mean that the class
>> itself gets multiplied, I guess, so this could end up being quite involved.
>> And I don't think it could be done without user visible quirks, e.g. when
>> typing variables as that class or type checking against it. Sounds like it
>> would take some major effort.
>>
>> Another error case for now, I guess.
>

> Yeah, they should give proper errors. I guess there's so many
> different possible cases to not use them correctly, that I haven't had
> them all handled.

Understandable again. This was a rather large addition to the language. It
doesn't come unexpected that it takes some time for the compiler to mature.

Stefan

[mark florisson]

This only works if you pass in the element type as an extra or dummy
argument (e.g. when inserting into the heap, or searching for some
value in the heap). Otherwise, you'll need a dummy scalar argument,
and what you lose is type safety. If I pass in a float to my heap of
doubles, it will suddenly cast a double pointer stored as a void
pointer to a float pointer and clobber my data. I can only avoid this
by checking the kind and the sizeof of the data type before casting.
This also means that conversion to objects and returning primitive
values get harder, e.g. "get the maximum element". You now have to do
a memcpy for the primitive case copying to a passed in pointer from
the user, or manually hard-code all the different conversions. This is
exactly what fused types are there to avoid.

[Stefan Behnel]

mark florisson, 30.04.2012 15:32:

What I meant was this:

cdef enum:
INT_TYPE
LONG_TYPE
DOUBLE_TYPE

struct heap:
Py_ssize_t mem_length
Py_ssize_t length
void* items
int type

cdef class Heap:
cdef heap _heap

def push(self, item):
if self._heap.type == INT_TYPE:
_push_item(<int>item, <int*>self._heap.items,
self._heap.length, self._heap.mem_length)
elif self._heap.type == LONG_TYPE:
_push_item(<long>item, <long*>self._heap.items,
self._heap.length, self._heap.mem_length)
elif self._heap.type == DOUBLE_TYPE:
_push_item(<double>item, <double*>self._heap.items,
self._heap.length, self._heap.mem_length)

cdef _push_item(cython.numeric item, cython.numeric* items,
Py_ssize_t length, Py_ssize_t mem_length):
# do stuff

I find that acceptable and it keeps the generated C code way below what a
fused struct and cdef class would give you. I would even use separate API
classes for different low-level types, might make things more accessible
for users on the Python side.

Stefan

[mark florisson]

Maybe C++ templates aren't that bad, they are certainly much more
powerful. It is sometimes useful to allow code to operate on any type,
as you go, rather than have the API designed decide what is best for
you (and export all possible specializations).

In this case I would personally prefer to use fused types as it makes
the compiler deal with all the boring things like dispatching, but
also guarantee type safety in an easy way (this code because
unmanageable for a more complicated algorithm or more data types).

[Stefan Behnel]

mark florisson, 30.04.2012 17:15:

> Maybe C++ templates aren't that bad, they are certainly much more
> powerful. It is sometimes useful to allow code to operate on any type,
> as you go, rather than have the API designed decide what is best for
> you (and export all possible specializations).

You have to know all possible specialisations statically at compile time,
though.

> In this case I would personally prefer to use fused types as it makes
> the compiler deal with all the boring things like dispatching, but
> also guarantee type safety in an easy way (this code because
> unmanageable for a more complicated algorithm or more data types).

That's why I leave the (algorithmically) complicated stuff to fused types
in the code above and keep the boring stuff simple.

Stefan

[shaunc]

Thanks for all the discussion, guys!

I reworked using memoryviews rather than buffers, but now get another compiler crash:

cdef struct pair_double_ulong_t:

    double key

    ulong value

ctypedef N.long_t[ : ] h_vector_long_t

ctypedef N.float64_t[ : ] h_vector_double_t

ctypedef pair_double_ulong_t[ : ] h_vector_pair_double_ulong_t

cdef fused h_vector_t:

    h_vector_long_t

    h_vector_double_t

    h_vector_pair_double_ulong_t

cdef struct heap_long_t:

    ulong capacity

    long *data

cdef struct heap_double_t:

    ulong capacity

    double *data

cdef struct heap_pair_double_ulong_t:

    ulong capacity

    pair_double_ulong_t *data

cdef fused heap_t:

    heap_long_t

    heap_double_t

    heap_pair_double_ulong_t

@cython.boundscheck( False )

cdef void heap_copy_to_vector( heap_t heap, h_vector_t vector ) nogil:

    cdef unsigned long i

    if ( heap_t is heap_long_t and h_vector_t is not h_vector_long_t

            or heap_t is heap_double_t and h_vector_t is not h_vector_double_t

            or heap_t is heap_pair_double_ulong_t and h_vector_t is not h_vector_pair_double_ulong_t ):

        with gil:

            raise TypeError( 'element must be same type as heap' )

    else:

        for i in range( heap.capacity ):

            vector[ i ] = heap.data[ i ]

-----

gives:

Error compiling Cython file:

------------------------------------------------------------

...

@cython.boundscheck( False )

cdef void heap_copy_to_vector( heap_t heap, h_vector_t vector ) nogil:

    cdef unsigned long i

    if ( heap_t is heap_long_t and h_vector_t is not h_vector_long_t

            or heap_t is heap_double_t and h_vector_t is not h_vector_double_t

            or heap_t is heap_pair_double_ulong_t and h_vector_t is not h_vector_pair_double_ulong_t ):

                                                                ^

------------------------------------------------------------

/Users/shauncutts/src/python/factfiber/stat/pmodel/c/max_heap.pyx:134:65: Compiler crash in ReplaceFusedTypeChecks

CFuncDefNode.body = StatListNode(max_heap.pyx:131:4)

StatListNode.stats[1] = IfStatNode(max_heap.pyx:132:4)

IfStatNode.if_clauses[0] = IfClauseNode(max_heap.pyx:132:7)

IfClauseNode.condition = BoolBinopNode(max_heap.pyx:133:12,

    operator = u'or',

    result_is_used = True,

    use_managed_ref = True)

BoolBinopNode.operand2 = BoolBinopNode(max_heap.pyx:134:12,

    operator = u'or',

    result_is_used = True,

    use_managed_ref = True)

BoolBinopNode.operand2 = BoolBinopNode(max_heap.pyx:134:50,

    operator = u'and',

    result_is_used = True,

    use_managed_ref = True)

BoolBinopNode.operand2 = PrimaryCmpNode(max_heap.pyx:134:65,

    operator = u'is_not',

    result_is_used = True,

    use_managed_ref = True)

Compiler crash traceback from this point on:

  File "Visitor.py", line 176, in Cython.Compiler.Visitor.TreeVisitor._visitchild (/Users/x/src/entropy-git/src/entropy/analyze/monitor/build/cython/Cython/Compiler/Visitor.c:3766)

  File "/Library/Python/2.7/site-packages/Cython/Compiler/ParseTreeTransforms.py", line 2580, in visit_PrimaryCmpNode

    is_same = type1.same_as(type2)

  File "/Library/Python/2.7/site-packages/Cython/Compiler/PyrexTypes.py", line 214, in same_as

    return self.same_as_resolved_type(other_type.resolve(), **kwds)

AttributeError: 'NoneType' object has no attribute 'resolve'

[mark florisson]

Thanks for the report, fixed in cython's master branch on github.