a MemoryAllocator object for easier Cython memory management

[nathanncohen]

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

Depends on #18864

CC: @dimpase @sagetrac-borassi @dcoudert @vbraun @jdemeyer @simon-king-jena

Component: cython

Author: Nathann Cohen, Jeroen Demeyer

Branch/Commit: 0304d9f

Reviewer: Jeroen Demeyer, Volker Braun

Issue created by migration from https://trac.sagemath.org/ticket/18868

[nathanncohen]

New commits:

2723175

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

[nathanncohen]

Commit: 2723175

[nathanncohen]

Branch: public/18868

[jdemeyer]

comment:2

This

include 'sage/ext/interrupt.pxi'

should be in the .pyx file.

[jdemeyer]

comment:3

For performance, replace

cdef MemoryAllocator mem = MemoryAllocator()

by

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

[jdemeyer]

comment:4

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]

comment:5

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

[jdemeyer]

comment:6

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]

comment:7

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

[jdemeyer]

comment:8

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]

comment:9

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]

comment:10

More for performance: replace

cdef enlarge_if_needed(self):

by

cdef int enlarge_if_needed(self) except -1:

[jdemeyer]

comment:11

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]

comment:13

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?

[sagetrac-git]

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

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

[sagetrac-git]

Changed commit from 2723175 to 9597eec

[nathanncohen]

comment:15

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]

comment:16

Replying to @dimpase:

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

What is [1]?

[jdemeyer]

comment:17

Replying to @nathanncohen:

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]

comment:18

Replying to @nathanncohen:

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?

[dimpase]

comment:29

Replying to @nathanncohen:

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 ?

[sagetrac-git]

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

f514301

Optimize MemoryAllocator and add allocarray()

[sagetrac-git]

Changed commit from 9597eec to f514301

[sagetrac-git]

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

39f8839

Fix exception handling

[sagetrac-git]

Changed commit from f514301 to 39f8839

[jdemeyer]

Changed author from Nathann Cohen to Nathann Cohen, Jeroen Demeyer

[jdemeyer]

Reviewer: Jeroen Demeyer

[jdemeyer]

comment:32

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

[dimpase]

comment:33

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]

comment:34

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]

comment:35

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]

comment:36

Can somebody review this please?

[jdemeyer]

Changed reviewer from Jeroen Demeyer to Jeroen Demeyer, Volker Braun

[dcoudert]

comment:39

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

[sagetrac-git]

Changed commit from 39f8839 to 0304d9f

[sagetrac-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

[nathanncohen]

Dependencies: #18864

[vbraun]

comment:43

Conflict with #18868

[vbraun]

Changed branch from public/18868 to 0304d9f