-
-
Notifications
You must be signed in to change notification settings - Fork 30k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Add PyMem_AlignedAlloc() #63035
Comments
Currently, we have little to no control over the alignment of memory returned by the PyMem functions. I suggest variants such as PyMem_Alloc32(n) and PyMem_Alloc64(n) to return suitably aligned data blocks. GNU C provides memalign() for this purpose: http://www.delorie.com/gnu/docs/glibc/libc_31.html A principal use case would be PyObject pointers where we want to keep all or most of the data fields in the same cache line (i.e. the fields for list, tuple, dict, and set objects). Deques would benefit from having the deque blocks aligned to 64byte boundaries and never crossing page boundaries. Set entries would benefit from 32byte alignment. |
I should also mention posix_memalign() for Unix/Linux systems. On systems without a clean way to provide aligned memory, we can always fall back to regular malloc(). The API wouldn't guarantee alignment but would comply when possible. |
Unless the memory allocator actually supports it, this means you lose a whole lot of memory for padding, though... Memory which will sit there unused at the end of another cacheline. Note that the current small object allocator, if not disabled, *should* already return you aligned memory, by construction (each allocation size has dedicated pools from which memory blocks are carved). |
The default allocator for PyObject is PyType_GenericAlloc(). If the type has the Py_TPFLAGS_HAVE_GC flag, PyType_GenericAlloc() calls _PyObject_GC_Malloc(). It is the case for the set type. _PyObject_GC_Malloc() adds an header of sizeof(PyGC_Head) (12 bytes on x86) before the PyObject data and then calls PyObject_MALLOC(). By default, Python uses pymalloc for PyObject_MALLOC() which uses an alignment of 8 bytes. For set, I suppose that you are talking about the allocation of the "table", not of the set object itself. set_table_resize() uses PyMem_NEW() to allocate the table. If we provide a PyMem_MallocAligned(alignment, size), table entries would be aligned, but not entries of the smalltable. Does it matter?
I would prefer a parameter rather than a new function per alignment! Which API does you propose exactly? On Linux, I see at least 3 functions: int posix_memalign(void **memptr, size_t alignment, size_t size);
void *valloc(size_t size);
void *memalign(size_t boundary, size_t size); Do you propose aligned variant for PyMem, PyMem_Raw and PyObject, or only PyMem? "Unless the memory allocator actually supports it, this means you lose a whole lot of memory for padding, though... Memory which will sit there unused at the end of another cacheline." What is the alignment of a cacheline? Can a line starts at any address? Do you have an idea of performance benefit of memory alignment? Adding yet another API to allocate memory has a cost. Python 3.4 already implemented the PEP-445 which added many new functions. If we add new functions, they should conform the PEP-445 (need get/set allocator functions to support hooks to track the memory usage). |
If it could, Raymond wouldn't be asking for this feature ;-)
Agreed. Aligned memory allocation is useful if your |
Please don't FUD this one to death. Aligned memory access is sometimes important and we currently have no straight-forward way to achieve it. If you're truly worried about adding single new function to the public C API, we can create just a single internal function: void * _PyMem_RawMallocAligned(size_t size, size_t alignment).
We don't have to align EVERY data structure. But I do have immediate beneficial use cases for set tables and for data blocks in deque objects. I need this function and would appreciate your help in fitting it in nicely with the current memory management functions and macros. |
Attaching a patch for what I would like to do with the alignment functions and macros. |
I guess that a simple way to cut the discussion short would be to have a first implementation, and run some benchmarks to measure the benefits. I can certainly see the benefit of cacheline-aligned data structures in multithreaded code (to avoid false sharing/cacheline bouncing): I'm really curious to see how much this would benefit in a single-threaded workload. |
Can you explain what the use cases are, and post some benchmarking code? Also, what would be the strategy? Would you align every set/deque, or only |
Linux provides the following functions: int posix_memalign(void **memptr, size_t alignment, size_t size);
void *valloc(size_t size); # obsolete
void *memalign(size_t boundary, size_t size); # obsolete Windows provides the following functions: void* _aligned_malloc(size_t size, size_t alignment);
void _aligned_free(void *memblock); _aligned_malloc() has a warning: "Using free is illegal." Do all platform provide at least a function to allocate aligned memory? Windows, Mac OS X, FreeBSD, old operating systems, etc.? If no, how should we handle these operating systems? Refuse to start Python? Disable some optimizations? How should we check in the source code (ex: setobject.c) than aligned allocations are not supported? An #ifdef? Because of the Windows API, wee need at least two functions: void* PyMem_MallocAligned(size_t size, size_t alignment);
void PyMem_FreeAligned(void *ptr); The GIL must be held when callling these functions. Windows provides also a "realloc" function: void* _aligned_realloc(void *memblock, size_t size, size_t alignment); If the OS does not provide a realloc function, we can reimplement it (malloc, memcpy, free). void* PyMem_ReallocAligned(void *ptr, size_t size, size_t alignment); For the PEP-445: the new API is different than the PyMemAllocator structure because malloc and realloc functions have an extra "alignment" parameter. We can drop the parameter if the allocator has always the size alignment, but each object may require a different aligment? |
It looks like a memory allocator with a given alignment would help numpy, for SIMD instructions: See also this old discussion on python-dev: Related to this website: |
Benchmarks and Intel's recommendation show that aligned allocation is actually important for AVX performance, and NumPy depends on CPython providing the right allocation APIs (for integration with tracemalloc): numpy/numpy#5312 So I think for 3.5 we should start providing the APIs. Whether we use them in Python core is another discussion. Nathaniel, what APIs would you need exactly? See Victor's proposal in |
Windows provides: void * _aligned_malloc(
size_t size,
size_t alignment
); http://msdn.microsoft.com/en-US/library/8z34s9c6%28v=vs.80%29.aspx How should we handle platforms which don't provide a memory allocator with an alignment? The simplest option is to return NULL (MemoryError). Allocating more memory and skip first bytes may work, but how do we retrieve the original address if the function releasing the memory block? What about Solaris, Mac OS X, FreeBSD, etc. |
Are there such platforms? posix_memalign() is a POSIX standard, even OpenBSD has it. |
PyMem_GetAllocator() and PyMem_SetAllocator() have a domain parameter which can take 3 values: PYMEM_DOMAIN_RAW, PYMEM_DOMAIN_MEM and PYMEM_DOMAIN_OBJ. I don't think that we need 3 flavors of allocators (PyMem_Raw, PyMem, PyObject). Maybe the PYMEM_DOMAIN_RAW domain is enough: OS functions don't require the GIL. In this case, should we add a new pair of Get/Set functions with an associated structure? Or maybe PyMem_SetAllocator() may ignore the aligned members of the patched PyMemAllocatorEx structure for domains other than PYMEM_DOMAIN_RAW? And PyMem_GetAllocator() would fill members with NULL. |
It's not terribly difficult to write a crude-but-effective aligned allocator on top of raw malloc: def aligned_malloc(size, alignment):
assert alignment < 255
raw_pointer = (uint8*) malloc(size + alignment)
shift = alignment - (raw_pointer % alignment)
assert 0 < shift <= alignment
aligned_pointer = raw_pointer + shift
*(aligned_pointer - 1) = shift
return aligned_pointer
def aligned_free(uint8* pointer):
shift = *(pointer - 1)
free(pointer - shift) But, this fallback and the official Win32 API both disallow the use of plain free() (like Victor points out in msg196834), so we can't just add an aligned_malloc slot to the PyMemAllocator struct. This kind of aligned allocation is effectively its own memory domain. If native aligned allocation support were added to PyMalloc then it could potentially do better (e.g. by noticing that it already has a block on its freelist with the requested alignment and just returning that instead of overallocating). This might be the ideal solution for Raymond's use case, but I have no idea how much work it would be to mess around with PyMalloc innards. Numpy doesn't currently use aligned allocation for anything, but we'd like to keep our options open. If we do end up using it in the future then there's a reasonable chance we might want to use it *without* the GIL held (e.g. for allocating temporary buffers inside C loops). OTOH we are also happy to implement the aligned allocation ourselves (either on top of the system APIs or directly) -- we just don't want to lose tracemalloc support when we do. For numpy's purposes, I think the best approach would be to add a tracemalloc "escape valve", with an interface like: PyMem_RecordAlloc(const char* domain, void* tag, size_t quantity,
PyMem_RecordRealloc(const char* domain, void* old_tag, void* new_tag, size_t new_quantity)
PyMem_RecordFree(const char* domain, void* tag) where the idea is that if after someone allocates memory (or potentially other discrete resources) directly without going through PyMem_*, they could then call these functions to tell tracemalloc what they just did. This would be useful in a number of cases: in addition to tracking aligned allocations, it would make it possible to re-use the tracemalloc infrastructure to track GPU buffers allocated by CUDA/GPGPU-type code, mmap usage, hugetlbfs usage, etc. Potentially even open file descriptors if one wants to go there (seems pretty useful, actually). |
Le 05/12/2014 23:15, STINNER Victor a écrit :
How about a new domain instead? PYMEM_DOMAIN_RAW_ALIGNED? |
Re: msg232219: If you go down the route of adding both aligned_malloc and aligned_free to the Allocator structure, I think you might as well support it for all domains? For the PyMem and PyObject domains you can just literally set the default functions to be PyMem_RawAlignedMalloc and PyMem_RawAlignedFree, and that leaves the door open to fancier implementations in the future (e.g. if PyMalloc starts implementing aligned allocation directly). Re: msg232222: Currently all the domains share the same vtable struct, though, whereas aligned allocator functions have different signatures. So you can't literally just add an entry to the existing domain enum and be done. It also occurs to me that if numpy ever gets serious about using aligned memory then we might also need aligned_realloc (numpy allows arrays to be resized, sigh), which is possible to do but I *cannot* recommend python attempt to provide as a standard interface. (It's not available at all in POSIX.) I guess this is another argument that it might be best to just give numpy an escape valve and worry about CPython's internal needs separately. |
You cannot just add a new domain because the function prototypes are |
Due to the realloc() problem, I'm thinking that the best course for Numpy would be to use its own allocator wrapper like Nathaniel outligned. |
Antoine Pitrou: "Benchmarks and Intel's recommendation show that aligned allocation is actually important for AVX performance, and NumPy depends on CPython providing the right allocation APIs (for integration with tracemalloc): numpy/numpy#5312" I don't think that NumPy was ever fully integrated with tracemalloc. Since Python 3.6, NumPy doesn't have to use Python memory allocators to benefit of tracemalloc debugger: I added a new C API to be able to manually track/untrack memory blocks which are not directly allocated by Python, see the issue bpo-26530. I implemented this feature for NumPy, but since I never got any feedback from NumPy, I left the API private. Moreover, I also added second feature to tracemalloc: it's now possible to track memory allocation in different address spaces. The feature was also designed for NumPy which can allocate memory in the GPU address space. See the issue bpo-26588. With these new tracemalloc features, I don't think that NumPy can still be used to request this feature in CPython core. -- Raymond: "A principal use case would be PyObject pointers where we want to keep all or most of the data fields in the same cache line (i.e. the fields for list, tuple, dict, and set objects). Deques would benefit from having the deque blocks aligned to 64byte boundaries and never crossing page boundaries. Set entries would benefit from 32byte alignment." Victor (me!): "Do you have an idea of performance benefit of memory alignment?" Since Raymond never provided any evidence that a new aligned memory allocator would give a significant speedup, and there issue is inactive for 2 years, I close it. See also the change 6e16b0045cf1, it seems like Raymond doesn't plan to use this feature anymore. -- If someone wants this feature, we need good reasons to implement it. |
I need this too. I would like to set this xnd-project/libndtypes@c260fdb#diff-2402fff6223084b74d97237c0d620b29R50 to something line PyMem_AlignedAlloc(), because the Python allocator is faster. I think many people would welcome this in scientific computing: The Arrow memory format for example recommends 64 bit alignment. |
Do you need aligned allocation even on small objects? The Python allocator doesn't handle allocations > 512 bytes. |
Yes, I think it is partly convenience. I want to set ... ndt_mallocfunc = PyMem_Malloc;
ndt_alignedallocfunc = PyMem_AlignedAlloc;
ndt_callocfunc = PyMem_Calloc;
ndt_reallocfunc = PyMem_Realloc;
ndt_freefunc = PyMem_Free; ... so I can always just call ndt_free(), because there's only one memory But the other part is that datashape allows to specify alignment regardless >>> from ndtypes import *
>>> from xnd import *
>>> t = ndt("{a: int64, b: uint64, align=16}")
>>> xnd(t, {'a': 111, 'b': 222})
<xnd.xnd object at 0x7f82750c2a30> The xnd object essentially wraps a typed data pointer. In the above case, the There are several other cases in datashape where alignment can specified For the convenience case it would already help if PyMem_AlignedAlloc() did |
[me]
I looked at Victor's patch, and thanks to the alignment <= ALIGNMENT So I retract the weakening of my use case (still shame on Microsoft |
Currently, the main question on my PR 4089 was raised by Antoine Pitrou: My reply: "Currently, you must provide all allocator functions, included aligned_alloc and aligned_free. Technically, we can implement a fallback, but I'm not sure that I want to do that :-)" I'm not sure about that. I can imagine platforms which provide a special malloc/free and that's all: no calloc, posix_memalign or _aligned_malloc(). But is Python suppose to fills the holes? For example, implement calloc() as malloc()+memset()? Or is the user of the PyMem_SetAllocator() API responsible to reimplement them? In Python 3.5, we added the requirement of a working calloc(). In Python 3.7, should we also add the "aligned alloc" requirement? In case of doubt, I prefer not to guess, and leave the decision to the caller of the API: require all functions to be implemented. I'm not sure that it's a good idea to provide a "aligned malloc" fallback if such fallback would be inefficient. For example, we would have to overallocate the memory block not only for the requested alignement, but also allocates extra sizeof(size_t) bytes, *in each* aligned memmory block, to store the size of the alignment itself, to recover the original pointer... to finally be able to call free(). An aligned memory block would look like: [AAAAA SSS DDD...DDDDDDD] where AAAAA are bytes lost for alignment, SSS bytes storing the alignment size (size of "AAAAA" in this example), and "DDD...DDDDDDD" would be the actual data. |
Linux, BSD, OSX, MSVC should be covered. According to Stackoverflow Android, I don't know. Xavier? |
Android has both memalign() [1] and posix_memalign() [2] and does not have aligned_alloc(), posix_memalign() is a wrapper around memalign() [3]. [1] https://android.googlesource.com/platform/bionic/+/master/libc/include/malloc.h#38 |
You can re-use the same bytes for padding and to store the offset. The main tricky thing is that for an alignment of N bytes you need to overallocate N bytes instead of (N-1). (In the worst case, malloc returns you a pointer that's already N-byte aligned, and then you have to advance it by a full N bytes so that you have some space before the pointer to store the offset.) Also you want to do a little N = max(N, sizeof(whatever int type you use)) at the beginning to make sure it's always big enough, but this is trivial (and really even a uint16_t is plenty big to store all reasonable alignments). And make sure that N is a power-of-two, which guarantees that whatever value malloc returns will be shifted by at least malloc's regular alignment, which is guaranteed to be large enough to store a standard int type (on reasonable systems). |
Should we care about the C11 restriction? http://en.cppreference.com/w/c/memory/aligned_alloc "size - number of bytes to allocate. An integral multiple of alignment" posix_memalign and _aligned_malloc don't care about the multiple. On the other hand, sane requests will have the exact multiple most |
PR 4089 becomes much more larger than what I expected, so I propose to defer enhancements to following PR, especially the idea of "emulating" PyMem_AlignedAlloc() on top of PyMem_Malloc() if the user calls PyMem_SetAllocators() without implemented aligned_alloc. |
The ways we've discussed using aligned allocation in numpy wouldn't follow this requirement without special checking. Which isn't necessarily a big deal, and numpy won't necessarily use this API anyway. But I would suggest being very clear about exactly what you guarantee and what you don't :-). |
In the GitHub issue we sort of decided to make the more relaxed Posix 'alignment' must be a power of 2 and a multiple of 'sizeof(void *)'. 'size' can be really anything, so it should work for numpy. It's a pity that Posix does not round up align={1,2,4} to 'sizeof(void *)' |
Given the complexities here, and that the Track/Untrack functions are public now, I do wonder if the actual aligned allocation routines should just be an internal API (i.e., not exposed in Python.h). |
Nathaniel: "(...) and numpy won't necessarily use this API anyway." Can you elaborate why numpy wouldn't use this new API? I designed it with numpy in mind :-) Using PyMem_AlignedAlloc() instead of using directly posix_memalign()/_aligned_alloc() provides the debug features for free:
Other advantages:
Moreover, Python takes care of the portability for you :-) |
Nathaniel Smith: "Given the complexities here, and that the Track/Untrack functions are public now, I do wonder if the actual aligned allocation routines should just be an internal API (i.e., not exposed in Python.h)." I don't see why we would hide PyMem_AlignedAlloc() but requires to implement aligned_alloc in PyMem_SetAllocators(). The plan is also to slowly use PyMem_AlignedAlloc() internally for performance. Can you elaborate the "complexities"? Do you mean that the proposed PyMem_AlignedAlloc() API is more complex than calling directly posix_memalign()? PyMem_AlignedAlloc() is designed for performance. For best performances, CPUs require memory to be aligned on convenient values like powers of 2 ;-) I also understand that alignment must be a multiple of sizeof(void*) because CPU work on "CPU words". On a 64-bit CPU, a word is 8 bytes. If the memory is aligned on 4 bytes, it may have to fetch two words, you loose the advantage of memory alignment. I understand that PyMem_AlignedAlloc() requirements come from the CPU arhcitecture, it's not an arbitrary limitation just for the fun ;-) |
Stefan Krah: "we care about the C11 restriction? (...) "size - number of bytes to allocate. An integral multiple of alignment" (...) posix_memalign and _aligned_malloc don't care about the multiple." I prefer to ignore this restriction at this point. I wouldn't be surprised if posix_memalign() and _aligned_malloc() already align the size for us internally. We can add the restriction later, if needed. |
The reasons I had in mind are:
I wasn't making a criticism of your API; "it's not you, it's us" :-). But this is a complicated and subtle area that's not really part of CPython's core competency, and coming at a time when people are fretting about how to shrink the C APIs surface area. E.g. I can think of more interesting ways for the PyPy folks to spend their time than implementing an aligned_alloc wrapper... |
Le 31/10/2017 à 15:55, Nathaniel Smith a écrit :
This isn't the Numpy bug tracker, but I can't help but mention that if (see numpy/numpy#5470)
The same argument can be made for any part of the stdlib or core |
On Tue, Oct 31, 2017 at 02:55:04PM +0000, Nathaniel Smith wrote:
I actually have the same problems. But since no fast (kernel-zeroed) So an emulated aligned_calloc() should probably not go into CPython |
For large allocations, you'll probably be better off implementing your own aligned allocator on top of calloc than implementing your own calloc on top of an aligned allocator. (It's O(1) overhead versus O(n).) And once you're doing that you might want to use the same code for regular allocations too, so that you don't need to keep track of whether each memory block used aligned_calloc or aligned_malloc and can treat them the same... Depends on your exact circumstances. |
Yes, but if the whole array is initialized with actual values, then If uninitialized (or very sparse), the overhead is of course gigantic. What is more, in some crude tests the posix_memalign() performance isn't C11 aligned_alloc() is also quite a bit faster than posix_memalign() here. I think you're right that a hand-rolled solution on top of calloc() is |
I merged my PR 4199 (Document PyObject_Malloc()) and PR 4200 (Cleanup pymalloc) to prepare PR 4089. PR 4089 should now be completed and well tested. The real question is now if we need PyMem_AlignedAlloc()? Stefan Krah and Nathaniel Smith are interested by aligned memory allocations, but both wrote that they don't plan to use PyMem_AlignedAlloc() if I understood correctly. What's the point of adding PyMem_AlignedAlloc() in that case? |
msg196194: Antoine Pitrou: "Note that the current small object allocator, if not disabled, *should* already return you aligned memory, by construction (each allocation size has dedicated pools from which memory blocks are carved)." In my current implementation of _PyObject_AlignedAlloc(), I only call pymalloc_alloc() for alignment <= pymalloc ALIGNMENT. Maybe we can do better? |
I agree, if the two primary users say they won't use it, it doesn't make sense for us to maintain 600 hundred lines of low-level C code. |
Yes, it may be better not to add it. To summarize the problems again:
The feature could still be useful for fixing bpo-31912 and bpo-27987, |
"C11 aligned_alloc() / free() would be more comfortable but isn't available on MSVC." Is it common to require the allocated memory block to be filled with zeros? In Python, calloc() is not the most common allocator. I only found 5 places where calloc is used: Modules/_ssl.c:5172: _ssl_locks = PyMem_Calloc(_ssl_locks_count, "posix_memalign() performance isn't that great. hand-rolled aligned_calloc() is the fastest." I'm not sure that the cost of the memory allocator itself defeats the gain of aligned memory on algorithms. I expect data processing to be much more expensive than the memory allocation, no? Again, the unknown remains the benchmark result. Can anyone write a quick benchmark to measure the gain of aligned memory? 4 years ago, Raymond Hettinger wanted to use it for the set and collection.deque types. |
About the API itself, I'm not sure that PyMem_AlignedAlloc(alignment, size) is flexible enough. If we want to get *data* aligned in a Python object, we would have to pass an offset to the data, since Python objects have headers of variable size (depending on the type). Windows has such API: void * _aligned_offset_malloc(
size_t size,
size_t alignment,
size_t offset
); This function is based on malloc, so likely adds padding bytes for you depending on size, alignment and offset. https://msdn.microsoft.com/fr-fr/library/ec852tkw.aspx See bpo-27987: "obmalloc's 8-byte alignment causes undefined behavior". |
I guess this issue isn't easy to focus due to the vast variety of use cases. So the is only about numpy/ndtypes: What you write is true, but I'm simply getting cold feet w.r.t locking At least that's what my tests indicate. Couple that with the fact that one has to use aligned_free() anyway, So I rather waste a couple of bytes per allocation and deal with Note that CPython still knows any allocation from ndtypes, because [1] If bpo-31912 is solved. |
Because of the lack of strong motivition compared to the size of the change and the cost to maintain it, I reject this issue. For the archives, I attach a copy of the latest version of my implementation. |
Note: these values reflect the state of the issue at the time it was migrated and might not reflect the current state.
Show more details
GitHub fields:
bugs.python.org fields:
The text was updated successfully, but these errors were encountered: