aligned_malloc and realloc for MemoryAllocator

[kliem]

Adding realloc and aligned_alloc to MemoryAllocator.

realloc is available in cysignals.memory anyway, so we might as well have it in MemoryAllocator.

aligned_malloc is useful for intrinsics, when memory up to 64-byte aligned is required. There are also similar functions in C, but its nice to have the memory taken care of by MemoryAllocator.

Component: cython

Author: Jonathan Kliem, Jeroen Demeyer

Branch/Commit: 61ad091

Reviewer: Jeroen Demeyer, Jonathan Kliem, Nils Bruin

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

[kliem]

New commits:

99549da

added realloc and reallocarray

[kliem]

Branch: public/27292

[kliem]

Commit: 99549da

[sagetrac-git]

Changed commit from 99549da to 470b782

[sagetrac-git]

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

470b782

added aligned_malloc

[sagetrac-git]

Changed commit from 470b782 to e61490a

[sagetrac-git]

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

e61490a

typo

[jdemeyer]

comment:5

This is mostly looking good. Just a few comments:

1. Can you also add aligned_allocarray and maybe aligned_calloc for completeness?

2. You could actually consider implementing the non-aligned functions as special case of the aligned functions.

3. You could add a small inline helper function (in the .pxd file) to implement the "lookup the pointer for realloc" feature. In that helper function, it would also be useful to support the special case of reallocating a NULL pointer, which would then work like a normal allocation.

4. What's the point of cdef size_t align = alignment

5. Add a test for the pointer-not-found case of realloc

6. Use Python 3 compatible print() syntax.

7. Remove the superfluous blank lines at the end of docstrings and use normal " quotes for exceptions.

[jdemeyer]

comment:6

While you're at it, could you move enlarge_if_needed to the .pxd file? It's more common to put such small inline functions in the .pxd file.

[jdemeyer]

Reviewer: Jeroen Demeyer

[sagetrac-git]

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

fc46dcb

worked in comments by Jeroen

[sagetrac-git]

Changed commit from e61490a to fc46dcb

[sagetrac-git]

Changed commit from fc46dcb to 7839b41

[sagetrac-git]

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

7839b41

forgot the header...

[sagetrac-git]

Changed commit from 7839b41 to 54046e1

[sagetrac-git]

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

54046e1

added doctests, corrected alloced sizes

[jdemeyer]

comment:11

Returns the index of ptr plus 1.

Why the plus 1? Isn't that making it more complicated than it should be?

[jdemeyer]

comment:12

Instead of returning an index in find_pointer, it might be more natural to return a pointer, i.e. a void**

[jdemeyer]

comment:13

I'll work on this.

[jdemeyer]

Changed author from Jonathan Kliem to Jonathan Kliem, Jeroen Demeyer

[kliem]

comment:14

Returns the index of ptr plus 1.

Why the plus 1? Isn't that making it more complicated than it should be?

I wanted to reserve an except value. It turns out that -1 would work just as good and is more natural.

There are never max_size_t -1 objects around.

Replying to @jdemeyer:

Instead of returning an index in find_pointer, it might be more natural to return a pointer, i.e. a void**

Yes, indeed. I never thought about returning the actual place where the pointer is stored.

[sagetrac-git]

Changed commit from 54046e1 to 61ad091

[sagetrac-git]

Branch pushed to git repo; I updated commit sha1. This was a forced push. New commits:

596c345	added realloc, reallocarray, aligned_malloc
61ad091	Clean up and optimize

[jdemeyer]

comment:16

After seeing the code, I made some changes to the design, mainly to simplify things. I implemented aligned_malloc() (and similar) in terms of malloc() instead of the other way around.

Needs review.

[nbruin]

comment:17

Doesn't posix_memalign do this? Is that not available on all supported platforms? If not, shouldn't we defer to posix_memalign when it is available?

[jdemeyer]

comment:18

Replying to @nbruin:

Doesn't posix_memalign do this?

What I don't like about posix_memalign is that it doesn't offer variants like calloc or realloc. This branch implements also aligned_calloc and we could (but don't for now) implement also aligned_realloc.

[nbruin]

comment:19

Replying to @jdemeyer:

Replying to @nbruin:

Doesn't posix_memalign do this?

What I don't like about posix_memalign is that it doesn't offer variants like calloc

calloc functionality would be trivial to build on top of posix_memalign: a simply API conversion and zero out the memory block.

or realloc. This branch implements also aligned_calloc and we could (but don't for now) implement also aligned_realloc.

Indeed, realloc in some cases might be more efficient because it could happen that the memory block doesn't need to be moved. Otherwise, a "malloc-memcpy-free" would do the same, so posix_memalign could be used as a primitive as well.

It looks to me you're paying a rather hefty penalty with the current design:

• you are wasting "alignment -1" memory for each allocation
• you are incurring overhead for storing pointers and looking them up in order to free the memory blocks.
  A good implementation of posix_memalign that can work with the internals of the system malloc should be able to avoid both in most cases.

I doubt that the occasional "realloc" that might be satisfied without relocating the memory block will be worth paying the other penalties all the time.

[jdemeyer]

comment:20

Replying to @nbruin:

calloc functionality would be trivial to build on top of posix_memalign: a simply API conversion and zero out the memory block.

It's a common misconception that calloc is just malloc + memset. This is not true in the case of memory allocated with mmap (which is typically used for large allocations): the memory is already pre-zeroed by the OS so there is no need to zero it a second time. In fact, zeroing it a second time implies actually bringing in physical memory for that region, which is not needed when doing just a mmap. This is especially bad when not all the allocated is eventually used.

• you are wasting "alignment -1" memory for each allocation

Indeed, this is a penalty to pay. But if the alignment value is relatively small to the size of the allocation (which I expect to be the typical case), then it doesn't matter so much.

• you are incurring overhead for storing pointers and looking them up in order to free the memory blocks.

We're already doing that in MemoryAllocator before this ticket. So it's not worse than other usages of MemoryAllocator in that sense.

[jdemeyer]

comment:21

Replying to @nbruin:

Otherwise, a "malloc-memcpy-free" would do the same

Similarly, for large allocations mremap would be used which doesn't need to do any copying, even if the allocation address moves.

[kliem]

Changed reviewer from Jeroen Demeyer to Jeroen Demeyer, Jonathan Kliem

[kliem]

comment:22

To me, this looks fine and good to go. But I am a newbie.

[nbruin]

comment:23

Looks OK to me too. It would seem to me the allocator could use a "free" too, but that's perhaps something for another ticket (and perhaps doesn't come up in its applications).

[nbruin]

Changed reviewer from Jeroen Demeyer, Jonathan Kliem to Jeroen Demeyer, Jonathan Kliem, Nils Bruin

[vbraun]

Changed branch from public/27292 to 61ad091