Opened 4 years ago

Closed 4 years ago

#18868 closed enhancement (fixed)

a MemoryAllocator object for easier Cython memory management

Reported by: ncohen Owned by:
Priority: major Milestone: sage-6.8
Component: cython Keywords:
Cc: dimpase, borassi, dcoudert, vbraun, jdemeyer, SimonKing Merged in:
Authors: Nathann Cohen, Jeroen Demeyer Reviewers: Jeroen Demeyer, Volker Braun
Report Upstream: N/A Work issues:
Branch: 0304d9f (Commits) Commit: 0304d9f21aa483f8b37bc6959e1a7490cd23ddb5
Dependencies: #18864 Stopgaps:

Description

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

Change History (44)

comment:1 Changed 4 years ago by ncohen

  • Branch set to public/18868
  • Commit set to 27231756748e4743df056783f524c66099189ccf
  • Status changed from new to needs_review

New commits:

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

comment:2 Changed 4 years ago by jdemeyer

  • Status changed from needs_review to needs_work

This

include 'sage/ext/interrupt.pxi'

should be in the .pyx file.

comment:3 Changed 4 years ago by jdemeyer

For performance, replace

cdef MemoryAllocator mem = MemoryAllocator()

by

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

comment:4 Changed 4 years ago by 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.

comment:5 Changed 4 years ago by jdemeyer

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

comment:6 Changed 4 years ago by 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)

comment:7 follow-ups: Changed 4 years ago by dimpase

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

comment:8 Changed 4 years ago by 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).

comment:9 in reply to: ↑ 7 ; follow-up: Changed 4 years ago by 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!

Last edited 4 years ago by jdemeyer (previous) (diff)

comment:10 Changed 4 years ago by jdemeyer

More for performance: replace

cdef enlarge_if_needed(self):

by

cdef int enlarge_if_needed(self) except -1:

comment:11 Changed 4 years ago by 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 231 pointers :-)

Last edited 4 years ago by jdemeyer (previous) (diff)

comment:12 Changed 4 years ago by SimonKing

  • Cc SimonKing added

comment:13 in reply to: ↑ 9 Changed 4 years ago by 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?

comment:14 Changed 4 years ago by git

  • Commit changed from 27231756748e4743df056783f524c66099189ccf to 9597eec5a42d72f66d56245f7312af3d69bbbf13

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

bf39672trac #18868: back to calloc
9597eectrac #18868: Changes to MemoryAllocator

comment:15 follow-ups: Changed 4 years ago by ncohen

  • Status changed from needs_work to needs_review

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

comment:16 in reply to: ↑ 7 ; follow-up: Changed 4 years ago by jdemeyer

Replying to dimpase:

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

What is [1]?

comment:17 in reply to: ↑ 15 Changed 4 years ago by 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.

comment:18 in reply to: ↑ 15 ; follow-up: Changed 4 years ago by jdemeyer

  • Status changed from needs_review to needs_info

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?

Last edited 4 years ago by jdemeyer (previous) (diff)

comment:19 in reply to: ↑ 18 ; follow-up: Changed 4 years ago by ncohen

  • Status changed from needs_info to needs_review

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

comment:20 in reply to: ↑ 15 Changed 4 years ago by 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).

comment:21 in reply to: ↑ 16 Changed 4 years ago by 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

comment:22 follow-up: Changed 4 years ago by 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...

comment:23 in reply to: ↑ 22 Changed 4 years ago by ncohen

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

+1 :-/

Nathann

comment:24 in reply to: ↑ 19 ; follow-up: Changed 4 years ago by 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.

comment:25 in reply to: ↑ 24 ; follow-up: Changed 4 years ago by 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

Last edited 4 years ago by ncohen (previous) (diff)

comment:26 in reply to: ↑ 25 Changed 4 years ago by jdemeyer

Replying to ncohen:

Can you give an example of that?

A created a new ticket #18870 to discuss it.

comment:27 Changed 4 years ago by jdemeyer

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

comment:28 follow-up: Changed 4 years ago by ncohen

Why wouldn't we discuss it with the cython guys?

Version 0, edited 4 years ago by ncohen (next)

comment:29 in reply to: ↑ 28 Changed 4 years ago by 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 ?

comment:30 Changed 4 years ago by git

  • Commit changed from 9597eec5a42d72f66d56245f7312af3d69bbbf13 to f514301ecf95d895d4321c7782d888d4cd27355f

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

f514301Optimize MemoryAllocator and add allocarray()

comment:31 Changed 4 years ago by git

  • Commit changed from f514301ecf95d895d4321c7782d888d4cd27355f to 39f88395bcef3aa972d48b31d4561c3c8a284d37

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

39f8839Fix exception handling

comment:32 Changed 4 years ago by jdemeyer

  • Authors changed from Nathann Cohen to Nathann Cohen, Jeroen Demeyer
  • Reviewers set to Jeroen Demeyer

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

comment:33 follow-ups: Changed 4 years ago by 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...

comment:34 in reply to: ↑ 33 Changed 4 years ago by 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...

comment:35 in reply to: ↑ 33 Changed 4 years ago by 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().

comment:36 Changed 4 years ago by jdemeyer

Can somebody review this please?

comment:37 Changed 4 years ago by vbraun

  • Status changed from needs_review to positive_review

comment:38 Changed 4 years ago by jdemeyer

  • Reviewers changed from Jeroen Demeyer to Jeroen Demeyer, Volker Braun

comment:39 Changed 4 years ago by dcoudert

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

comment:40 Changed 4 years ago by git

  • Commit changed from 39f88395bcef3aa972d48b31d4561c3c8a284d37 to 0304d9f21aa483f8b37bc6959e1a7490cd23ddb5
  • Status changed from positive_review to needs_review

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

da7bad7trac #18864: Merged with 6.8.beta8
da0260dtrac #18864: prevent using the Takes-Kosters algorithm on digraphs
554c509trac #18864: implement reviewer's comments
f48a33etrac #18864: minor corrections
a3717b7trac #18864: improve behavior with directed graphs
f621777trac #18864: corrections and improved doc
80cb899trac #18864: correct version
ce9d265trac #18864: return Sage integers
a1b36datrac #18864: Merged with 6.8.rc1
0304d9ftrac #18868: Merged with #18864

comment:41 Changed 4 years ago by ncohen

  • Status changed from needs_review to positive_review

comment:42 Changed 4 years ago by ncohen

  • Dependencies set to #18864

comment:43 Changed 4 years ago by vbraun

  • Status changed from positive_review to needs_work

Conflict with #18868

comment:44 Changed 4 years ago by vbraun

  • Branch changed from public/18868 to 0304d9f21aa483f8b37bc6959e1a7490cd23ddb5
  • Resolution set to fixed
  • Status changed from needs_work to closed
Note: See TracTickets for help on using tickets.