Opened 7 years ago
Closed 7 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, GitHub, GitLab) | 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 7 years ago by
- Branch set to public/18868
- Commit set to 27231756748e4743df056783f524c66099189ccf
- Status changed from new to needs_review
comment:2 Changed 7 years ago by
- Status changed from needs_review to needs_work
This
include 'sage/ext/interrupt.pxi'
should be in the .pyx
file.
comment:3 Changed 7 years ago by
For performance, replace
cdef MemoryAllocator mem = MemoryAllocator()
by
cdef MemoryAllocator mem = <MemoryAllocator>MemoryAllocator.__new__(MemoryAllocator)
comment:4 Changed 7 years ago by
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 7 years ago by
Also for performance: keep calloc
, do not replace it with malloc + memset
.
comment:6 Changed 7 years ago by
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: ↓ 9 ↓ 16 Changed 7 years ago by
[1] recommends PyMem_Malloc, PyMem_Realloc, PyMem_Free
over the system functions. Why do you
stick with malloc
etc?
comment:8 Changed 7 years ago by
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: ↓ 13 Changed 7 years ago by
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!
comment:10 Changed 7 years ago by
More for performance: replace
cdef enlarge_if_needed(self):
by
cdef int enlarge_if_needed(self) except -1:
comment:11 Changed 7 years ago by
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 :-)
comment:12 Changed 7 years ago by
- Cc SimonKing added
comment:13 in reply to: ↑ 9 Changed 7 years ago by
comment:14 Changed 7 years ago by
- Commit changed from 27231756748e4743df056783f524c66099189ccf to 9597eec5a42d72f66d56245f7312af3d69bbbf13
comment:15 follow-ups: ↓ 17 ↓ 18 ↓ 20 Changed 7 years ago by
- 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()
bycdef 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):
bycdef int enlarge_if_needed(self) except -1:
Done.
One more detail: replace
int
withsize_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: ↓ 21 Changed 7 years ago by
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 7 years ago by
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: ↓ 19 Changed 7 years ago by
- 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?
comment:19 in reply to: ↑ 18 ; follow-up: ↓ 24 Changed 7 years ago by
- 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 7 years ago by
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 7 years ago by
comment:22 follow-up: ↓ 23 Changed 7 years ago by
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 7 years ago by
I wonder whether there are ways to avoid syntactic clutter such as
+1 :-/
Nathann
comment:24 in reply to: ↑ 19 ; follow-up: ↓ 25 Changed 7 years ago by
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: ↓ 26 Changed 7 years ago by
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
comment:26 in reply to: ↑ 25 Changed 7 years ago by
comment:27 Changed 7 years ago by
I looked into #18870 and personally, I don't like it.
comment:28 follow-up: ↓ 29 Changed 7 years ago by
Why wouldn't we discuss it with the cython guys? Perhaps they would be willing to provide something we could use?
comment:29 in reply to: ↑ 28 Changed 7 years ago by
comment:30 Changed 7 years ago by
- Commit changed from 9597eec5a42d72f66d56245f7312af3d69bbbf13 to f514301ecf95d895d4321c7782d888d4cd27355f
Branch pushed to git repo; I updated commit sha1. New commits:
f514301 | Optimize MemoryAllocator and add allocarray()
|
comment:31 Changed 7 years ago by
- Commit changed from f514301ecf95d895d4321c7782d888d4cd27355f to 39f88395bcef3aa972d48b31d4561c3c8a284d37
Branch pushed to git repo; I updated commit sha1. New commits:
39f8839 | Fix exception handling
|
comment:32 Changed 7 years ago by
- Reviewers set to Jeroen Demeyer
This is ok for me, but someone needs to review my changes.
comment:33 follow-ups: ↓ 34 ↓ 35 Changed 7 years ago by
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 7 years ago by
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 7 years ago by
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 7 years ago by
Can somebody review this please?
comment:37 Changed 7 years ago by
- Status changed from needs_review to positive_review
comment:38 Changed 7 years ago by
- Reviewers changed from Jeroen Demeyer to Jeroen Demeyer, Volker Braun
comment:39 Changed 7 years ago by
Your were faster than me.
I can at least confirm that all long tests pass on src/sage/graphs/
.
David.
comment:40 Changed 7 years ago by
- 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:
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
|
comment:41 Changed 7 years ago by
- Status changed from needs_review to positive_review
comment:42 Changed 7 years ago by
- Dependencies set to #18864
comment:43 Changed 7 years ago by
- Status changed from positive_review to needs_work
Conflict with #18868
comment:44 Changed 7 years ago by
- Branch changed from public/18868 to 0304d9f21aa483f8b37bc6959e1a7490cd23ddb5
- Resolution set to fixed
- Status changed from needs_work to closed
New commits:
trac #18868: a MemoryAllocator object for easier Cython memory management