Add PyMem_AlignedAlloc()

@tim-one

BPO	18835
Nosy	@tim-one, @rhettinger, @pitrou, @vstinner, @benjaminp, @tpn, @njsmith, @skrah, @xdegaye, @wscullin
PRs	bpo-18835: Add PyMem_AlignedAlloc() #4089 bpo-18835: Cleanup pymalloc #4200 bpo-37732: Fix GCC warning in _PyObject_Malloc() #15333
Files	align.diff: Use case for alignment functions and macros pymem_alignedalloc.patch

^{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:

assignee = None
closed_at = <Date 2017-11-24.01:08:11.785>
created_at = <Date 2013-08-26.02:32:51.118>
labels = ['interpreter-core', 'type-feature', '3.7']
title = 'Add PyMem_AlignedAlloc()'
updated_at = <Date 2019-08-19.10:30:41.502>
user = 'https://github.com/rhettinger'

bugs.python.org fields:

activity = <Date 2019-08-19.10:30:41.502>
actor = 'vstinner'
assignee = 'none'
closed = True
closed_date = <Date 2017-11-24.01:08:11.785>
closer = 'vstinner'
components = ['Interpreter Core']
creation = <Date 2013-08-26.02:32:51.118>
creator = 'rhettinger'
dependencies = []
files = ['31543', '47285']
hgrepos = []
issue_num = 18835
keywords = ['patch']
message_count = 57.0
messages = ['196174', '196176', '196194', '196196', '196202', '196693', '196700', '196713', '196828', '196834', '217229', '232201', '232209', '232215', '232219', '232221', '232222', '232223', '232225', '234086', '286074', '304803', '304805', '304807', '304826', '304834', '304837', '304843', '304844', '304859', '304878', '304989', '305003', '305009', '305012', '305114', '305122', '305136', '305160', '305177', '305301', '305302', '305304', '305308', '305310', '305311', '305327', '305331', '305339', '305344', '305345', '305366', '305397', '305417', '305418', '305466', '306864']
nosy_count = 11.0
nosy_names = ['tim.peters', 'rhettinger', 'pitrou', 'vstinner', 'benjamin.peterson', 'trent', 'njs', 'skrah', 'neologix', 'xdegaye', 'wscullin']
pr_nums = ['4089', '4200', '15333']
priority = 'normal'
resolution = 'rejected'
stage = 'resolved'
status = 'closed'
superseder = None
type = 'enhancement'
url = 'https://bugs.python.org/issue18835'
versions = ['Python 3.7']

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
and the Microsoft C compiler has _aligned_malloc() for the same purpose: http://msdn.microsoft.com/en-us/library/8z34s9c6%28VS.80%29.aspx

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 suggest variants such as PyMem_Alloc32(n) and PyMem_Alloc64(n) to return suitably aligned data blocks.

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).

What is the alignment of a cacheline? Can a line starts at any
address?

If it could, Raymond wouldn't be asking for this feature ;-)
Cachelines are typically aligned at whatever their size is. So,
a 64-byte cacheline will be aligned at a 64 bytes boundary.
Perhaps some CPUs operate differently, but mainstream CPUs are
generally like that (for good reason: a cache is much simpler
to implement if there can't be some overlapping between cache
lines).

Do you have an idea of performance benefit of memory alignment?

Adding yet another API to allocate memory has a cost.

Agreed. Aligned memory allocation is useful if your
*algorithms* benefit from alignment (e.g. some SIMD-optimized
code, or something relying on page tables). But aligning
every data structure on a cacheline boundary doesn't sound
like a very good idea: if it was, the system allocator
would do it for you, IMHO ;-)

Adding yet another API to allocate memory has a cost

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).

aligning every data structure on a cacheline boundary
doesn't sound like a very good idea

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.

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.

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.

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.

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
the bigger ones?

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:
https://mail.python.org/pipermail/python-dev/2014-April/134092.html
(but "Numpy does not currently use aligned allocation, and it's not clear how important it is")

See also this old discussion on python-dev:
https://mail.python.org/pipermail/python-dev/2010-September/103911.html

Related to this website:
http://mallocv2.wordpress.com/

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
msg196834.

On Tue, Oct 31, 2017 at 02:55:04PM +0000, Nathaniel Smith wrote:

also it's not clear what the best approach will look like, given that we care a lot about using calloc when possible, and have reason to prefer using regular freeing functions whenever possible.

I actually have the same problems. But since no fast (kernel-zeroed)
aligned_calloc() exists, I must use memset() anyway.

So an emulated aligned_calloc() should probably not go into CPython
since it doesn't provide any performance advantages.

But since no fast (kernel-zeroed) aligned_calloc() exists, I must use memset() anyway.

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.

New changeset 9ed83c4 by Victor Stinner in branch 'master':
bpo-18835: Cleanup pymalloc (bpo-4200)
9ed83c4

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
the memset() overhead is not very large (something like 16% here).

If uninitialized (or very sparse), the overhead is of course gigantic.

What is more, in some crude tests the posix_memalign() performance isn't
that great compared to malloc()/calloc().

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
best for my use case.

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:
--------------------------------

C11 aligned_alloc() / free() would be more comfortable but isn't
available on MSVC.
posix_memalign() performance isn't that great.
hand-rolled aligned_calloc() is the fastest.

The feature could still be useful for fixing bpo-31912 and bpo-27987,
*if* someone has an idea how to integrate the aligned version.

"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,
Modules/gcmodule.c:1689: g = (PyGC_Head *)PyObject_Calloc(1, size);
Modules/gcmodule.c:1717:_PyObject_GC_Calloc(size_t basicsize)
Objects/bytesobject.c:83: op = (PyBytesObject *)PyObject_Calloc(1, PyBytesObject_SIZE + size);
Objects/listobject.c:176: op->ob_item = (PyObject **) PyMem_Calloc(size, sizeof(PyObject *));

"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'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?

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
myself into memset(). calloc() uses mmap() for large allocations, so I think one can happily allocate a large number of huge arrays without any
cost on Linux, as long as they're not accessed.

At least that's what my tests indicate.

Couple that with the fact that one has to use aligned_free() anyway,
and that posix_memalign() isn't that great, and the use case seems
less solid **for scientific computing**.

So I rather waste a couple of bytes per allocation and deal with
some Valgrind macros to get proper bounds checking.

Note that CPython still knows any allocation from ndtypes, because
ndt_callocfunc will be set to PyMem_Calloc() [1] and the custom
ndt_aligned_calloc() uses ndt_callocfunc.

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

Navigation Menu

Repository navigation

Add PyMem_AlignedAlloc() #63035

36 remaining items

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Add PyMem_AlignedAlloc() #63035

Description

Activity

rhettinger commented on Aug 26, 2013

rhettinger commented on Aug 26, 2013

pitrou commented on Aug 26, 2013

vstinner commented on Aug 26, 2013

pitrou commented on Aug 26, 2013

rhettinger commented on Sep 1, 2013

rhettinger commented on Sep 1, 2013

neologix commented on Sep 1, 2013

pitrou commented on Sep 3, 2013

vstinner commented on Sep 3, 2013

vstinner commented on Apr 27, 2014

pitrou commented on Dec 5, 2014

36 remaining items

skrah commented on Oct 31, 2017

njsmith commented on Oct 31, 2017

vstinner commented on Oct 31, 2017

skrah commented on Oct 31, 2017

vstinner commented on Nov 1, 2017

vstinner commented on Nov 1, 2017

pitrou commented on Nov 1, 2017

skrah commented on Nov 1, 2017

vstinner commented on Nov 2, 2017

vstinner commented on Nov 2, 2017

skrah commented on Nov 3, 2017

vstinner commented on Nov 24, 2017

Metadata

Metadata

Assignees

Labels

Projects

Milestone

Relationships

Development

Issue actions