a MemoryAllocator object for easier Cython memory management

[ncohen]

This is a re-implementation of an example appearing in Cython's documentation (see bottom of [1]).

The idea is simple: an object has a .malloc method, and returns arrays of memory. When that object is garbage-collected, the memory it allocated is automatically freed.

This makes it much easier to deal with C pointers in Cython code, which must be freed before any 'return' and whenever an exception can be raised.

As an illustration of how useful this can be, I removed a *lot* of graph code.

Nathann

[1] ​http://docs.cython.org/src/tutorial/memory_allocation.html

[ncohen]

New commits:

​2723175

trac #18868: a MemoryAllocator object for easier Cython memory management

[jdemeyer]

This

include 'sage/ext/interrupt.pxi'

should be in the .pyx file.

[jdemeyer]

For performance, replace

cdef MemoryAllocator mem = MemoryAllocator()

by

cdef MemoryAllocator mem = <MemoryAllocator>MemoryAllocator.__new__(MemoryAllocator)

[jdemeyer]

Can you please support all memory-allocation functions, like calloc, realloc, (re)allocarray and replace the dangerous(*) calls like

mem.malloc( n * sizeof(unsigned short *))

by

mem.allocarray(n, sizeof(unsigned short *))

(*) the multiplication can overflow.

[jdemeyer]

Also for performance: keep calloc, do not replace it with malloc + memset.

[jdemeyer]

I guess that realloc(array) might not be so easy to support, so you can forget about that. But I would certainly support allocarray and calloc.

And I don't understand why you use

cdef void * val = malloc(size)
if val == NULL:
    raise MemoryError()

instead of

cdef void * val = check_malloc(size)

[dimpase]

[1] recommends PyMem_Malloc, PyMem_Realloc, PyMem_Free over the system functions. Why do you stick with malloc etc?

[jdemeyer]

More about performance: note that your use of MemoryAllocator needs at least 2 extra memory allocation calls compared to not using MemoryAllocator: one to allocate the MemoryAllocator object and one to allocate the pointers member. If you allocate several pointers, it's worse because you again need more additional realloc() calls for pointers.

To solve some of these problems, I propose the following: add a small fixed array

cdef void* local_pointers[16]

in the MemoryAllocator class and initialize

self.max_size = 16
self.pointers = self.local_pointers

such that you avoid any allocations for pointers if you need to store at most 16 pointers (which is the usual case I guess).

[jdemeyer]

Replying to dimpase:

Why do you stick with malloc etc?

In Sage, you should use absolutely use sage_malloc (or check_malloc) because it behaves well w.r.t. interrupts!

[jdemeyer]

More for performance: replace

cdef enlarge_if_needed(self):

by

cdef int enlarge_if_needed(self) except -1:

[jdemeyer]

One more detail: replace

cdef int n
cdef int max_size

by

cdef size_t n
cdef size_t max_size

(and adjust the loop index in __dealloc__) in case I ever need more than 2³¹ pointers :-)

[dimpase]

Replying to jdemeyer:

Replying to dimpase:

Why do you stick with malloc etc?

In Sage, you should use absolutely use sage_malloc (or check_malloc) because it behaves well w.r.t. interrupts!

And why does sage_malloc use malloc, and not PyMem_Malloc?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​bf39672	trac #18868: back to calloc
​9597eec	trac #18868: Changes to MemoryAllocator

[ncohen]

This include 'sage/ext/interrupt.pxi' should be in the .pyx file.

Done

For performance, replace cdef MemoryAllocator mem = MemoryAllocator() by cdef MemoryAllocator mem = <MemoryAllocator>MemoryAllocator.__new__(MemoryAllocator)

Makes no difference in any of the functions I touched, so I did not do it. Less readable.

Can you please support all memory-allocation functions, like calloc, realloc, (re)allocarray and replace the dangerous(*) calls like

I added support for calloc. I do not need realloc (you can add a commit if you need it).

About realloc:

I guess that realloc(array) might not be so easy to support, so you can forget about that.

+1

But I would certainly support allocarray

Add a commit if you like. My problem with 'allocarray' is that it is Sage's terminology (as far as I know), and that I prefer to stick to more widely understood terms like 'malloc/calloc'. I was just saying to David that we may eventually move some C graph code away from sage and make it an independent C library.

And I don't understand why you use

cdef void * val = malloc(size)
if val == NULL:
    raise MemoryError()

instead of

cdef void * val = check_malloc(size)

Done

[1] recommends PyMem_Malloc, PyMem_Realloc, PyMem_Free over the system functions. Why do you stick with malloc etc?

Personally, for a simple reason: I trust C functions. Officially, it is for the reason Jeroen mentionned. Note that we can satisfy everybody: it is possible to have sage_malloc (which behaves properly with respect to interrupts) call your functions instead of C ones.

More about performance: note that your use of MemoryAllocator? needs at least 2 extra memory allocation calls compared to not using MemoryAllocator?

This is not a problem for the codes I touched, for malloc is never a dominant cost in any of them. You can add a commit if you like, though please keep the code simple and understandable if you do.

More for performance: replace cdef enlarge_if_needed(self): by cdef int enlarge_if_needed(self) except -1:

Done.

One more detail: replace int with size_t

Done.

Jeroen, could you send reviews as one big comment rather than adding one every time you notice something? Everybody in Cc receives an email for each comments, and it is also a bit harder to address your points:

• One never knows if you are done reading the code or if we can expect a new comment in the next seconds

• Answering your points like I do now is a bit harder: instead of clicking on 'reply' (to your comment), I copy/paste all your individual messages into a text file, then start answering them.

Thaaaaaaaaanks,

Nathann

[jdemeyer]

Replying to dimpase:

[1] recommends PyMem_Malloc, PyMem_Realloc, PyMem_Free over the system functions.

What is [1]?

[jdemeyer]

Replying to ncohen:

My problem with 'allocarray' is that it is Sage's terminology (as far as I know)

It actually comes from BSD, where it was added for security reasons (like I said, the multiplication in malloc(n * sizeof(foo)) can overflow, a potential security issue). For Sage, it's not so much the "security" aspect which is important, but the reliability.

[jdemeyer]

Replying to ncohen:

You can add a commit if you like, though please keep the code simple and understandable if you do.

I thought that speed was an important reason to invent this new class. If you don't care so much about speed, there are several already-existing alternatives, such as ​Cython arrays.

If speed is not so much a concern, then why are you reinventing the wheel?

[ncohen]

I thought that speed was an important reason to invent this new class.

I care about the speed of the algorithm themselves. I need real C arrays. The time it takes to allocate them is not a problem in the graph code.

Nathann

[jdemeyer]

Replying to ncohen:

Makes no difference in any of the functions I touched, so I did not do it. Less readable.

You are right. I was confused with explicit calls to __init__ (i.e. foo.__init__() should be avoided in Cython).

[dimpase]

Replying to jdemeyer:

Replying to dimpase:

[1] recommends PyMem_Malloc, PyMem_Realloc, PyMem_Free over the system functions.

What is [1]?

see the ticket description

[dimpase]

I wonder whether there are ways to avoid syntactic clutter such as

cdef uint32_t * _connected_structure = <uint32_t *> mem.calloc(n * n , sizeof(uint32_t))

You know, in C such thing would be best written as macro call like

newdef(_connected_structure, uint32_t, n*n)

avoiding mentioning uint32_t three times...

[ncohen]

I wonder whether there are ways to avoid syntactic clutter such as

+1 :-/

Nathann

[jdemeyer]

Replying to ncohen:

I need real C arrays. The time it takes to allocate them is not a problem in the graph code.

OK, here is a deal: if you really mean what you say (that you don't care about the time to allocate, just the access time), then I'm pretty sure that your problem can be solved with Cython arrays. A memoryview like cdef int[::1] should be as fast as a C pointer.

[ncohen]

A memoryview like cdef int[::1] should be as fast as a C pointer.

If your 'should' is a 'is', and if you do not need to replace each pointer allocation by 1) creationg of a Cython object 2) Linking it to the C array then yes. Can you give an example of that? I read your link toward 'Cython arrays' and it seems to have this drawback, i.e. 2 lines per allocation.

Nathann

[jdemeyer]

Replying to ncohen:

Can you give an example of that?

A created a new ticket #18870 to discuss it.

[jdemeyer]

I looked into #18870 and personally, I don't like it.

[ncohen]

Why wouldn't we discuss it with the cython guys? Perhaps they would be willing to provide something we could use?

[dimpase]

Replying to ncohen:

Why wouldn't we discuss it with the cython guys? Perhaps they would be willing to provide something we could use?

sure, why not; also, how about asking them about comment ​23 ?

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​f514301

Optimize MemoryAllocator and add allocarray()

[git]

Branch pushed to git repo; I updated commit sha1. New commits:

​39f8839

Fix exception handling

[jdemeyer]

This is ok for me, but someone needs to review my changes.

[dimpase]

still, how about PyMem_Malloc, PyMem_Realloc, PyMem_Free, as mentioned in ​http://docs.cython.org/src/tutorial/memory_allocation.html ?

Apart from performance, there could be advantages in sense of debugging, as one can ./configure Python with --with-pydebug to catch memory errors...

[jdemeyer]

Replying to dimpase:

still, how about PyMem_Malloc, PyMem_Realloc, PyMem_Free, as mentioned in ​http://docs.cython.org/src/tutorial/memory_allocation.html ?

In any case, that's independent of this ticket.

Second, sage_malloc() can be called without the GIL. I guess PyMem_Malloc cannot...

[jdemeyer]

Third, Python's memory allocator does not support calloc() or allocarray(), two very useful functions.

And if you're speaking about performance, recall that malloc() + memset() is slower than calloc().

[jdemeyer]

Can somebody review this please?

[dcoudert]

Your were faster than me. I can at least confirm that all long tests pass on src/sage/graphs/. David.

[git]

Branch pushed to git repo; I updated commit sha1 and set ticket back to needs_review. Last 10 new commits:

​da7bad7	trac #18864: Merged with 6.8.beta8
​da0260d	trac #18864: prevent using the Takes-Kosters algorithm on digraphs
​554c509	trac #18864: implement reviewer's comments
​f48a33e	trac #18864: minor corrections
​a3717b7	trac #18864: improve behavior with directed graphs
​f621777	trac #18864: corrections and improved doc
​80cb899	trac #18864: correct version
​ce9d265	trac #18864: return Sage integers
​a1b36da	trac #18864: Merged with 6.8.rc1
​0304d9f	trac #18868: Merged with #18864

[vbraun]

Conflict with #18868