ENH: cache large memory allocations on systems with MADV_FREE by juliantaylor · Pull Request #8783 · numpy/numpy

juliantaylor · 2017-03-14T14:41:20Z

Large allocations on glibc systems need to be faulted into the process
before use each use. This can account for a significant fraction of the
runtime of frequent array allocation and deallocation.  This can be avoidded
by caching used memory blocks inside numpy for later reuse.  To not waste
the memory in the cache we mark the memory as reclaimable by other processes
(or numpy itself) with MADV_FREE. Should we try to use memory claimed by
other processes we will receive newly faulted memory instead just as if it
were freed normally.
MADV_FREE is supported on Linux >= 4.5 and BSD.

The cache is intentionally very simple queue storing the last large
deallocations in a queue. New allocations pick the first block of memory
that matches in size from the cache. It does not pick larger blocks,
while the memory can be reclaimed by other processes it is not available
for the page cache used to buffer IO.
On each deallocation the cache is aged and if no entries have been
removed for too long the oldest memory block is properly deallocated to
avoid that large unused blocks stay in the cache too long.
In most cases where it is relevant are fast allocation/deallocation
cycles that appear in operations with temporaries or indexing. A simple
small cache is sufficient for this.
It will cache at most half of the available physical memory so that
there is always enough free to be used in the page cache.

still a prototype missing documentation and cleanup, but should be usable to test how effective it is in practice.

njsmith · 2017-03-14T16:45:02Z

So if I understand correctly, if we do (1) allocate a large array, (2) free the large array, (3) allocate a small array, (4) free the small array, then we end up with a pointer in the cache that points to a large amount of address space, but we've "lost track" of most of that and think it's a pointer to a small amount of address space, right? Are we worried about the impact of this kind of address space leakage on 32-bit systems?

...also this is vague, but I wonder if we should be worried at all about transparent hugepages screwiness?

juliantaylor · 2017-03-14T17:16:48Z

Indeed on 32 bit it should be disabled as this does waste address space.
Transparent hugepages should have no influence on this. As far as the kernel is concerned we are freeing memory normally so the fragmentation pattern should not change.

charris · 2017-03-14T18:49:20Z

I'm going to schedule this for 1.14. I'd like to branch 1.13 soon and it is already loaded with risk.

mattharrigan · 2017-03-16T10:21:39Z

A naive question, can these functions be called by multiple threads? Is thread safety a concern? In general I have a hard time understanding what can or cannot be safely called by multiple threads, and the GIL is another layer of complexity/protection.

juliantaylor · 2017-03-16T10:29:46Z

Currently these functions must be called under a lock, namely the GIL.
But updating them to be threadsafe is very easy, just not necessary yet.

homu · 2017-04-07T19:05:20Z

☔ The latest upstream changes (presumably #8907) made this pull request unmergeable. Please resolve the merge conflicts.

replace path seperators with underscore

charris · 2017-06-02T18:47:04Z

     alloc.c
    numpy\core\src\multiarray\alloc.c(27) : fatal error C1083: Cannot open include file: 'unistd.h': No such file or directory

The unistd.h file does not exist in windows.

charris · 2017-06-02T18:51:18Z

File does not exist on windows.

Large allocations on glibc systems need to be faulted into the process before use each use. This can account for a significant fraction of the runtime of frequent array allocation and deallocation. This can be avoidded by caching used memory blocks inside numpy for later reuse. To not waste the memory in the cache we mark the memory as reclaimable by other processes (or numpy itself) with MADV_FREE. Should we try to use memory claimed by other processes we will receive newly faulted memory instead just as if it were freed normally. MADV_FREE is supported on Linux >= 4.5 and BSD. The cache is intentionally very simple queue storing the last large deallocations in a queue. New allocations pick the first block of memory that matches in size from the cache. It does not pick larger blocks, while the memory can be reclaimed by other processes it is not available for the page cache used to buffer IO. On each deallocation the cache is aged and if no entries have been removed for too long the oldest memory block is properly deallocated to avoid that large unused blocks stay in the cache too long. In most cases where it is relevant are fast allocation/deallocation cycles that appear in operations with temporaries or indexing. A simple small cache is sufficient for this. It will cache at most half of the available physical memory so that there is always enough free to be used in the page cache.

juliantaylor · 2017-06-03T11:57:55Z

The code is still quite messy and still needs some changing (e.g. the exposed function is just for testing for now) but I think this approach should work.

I have changed it to address that the uncommitted memory is available for other processes but not for the page cache.
Instead of a store-largest-block cache it is now a simple queue limited to at most 50% of the physical memory, retrieving blocks from it requires an exact match so we do not leak out too large blocks to persistent allocations by the user. This makes the cache significantly less effective but it should still serve its purpose of avoiding page faults for the common same size alloc/dealloc cycle for temporaries.
Using only half of the RAM should not degrade OS IO caching significantly as applications using that much data probably need a large amount of allocated memory anyway.
To avoid that stuff hangs around in the cache for too long the oldest entry is cleared every 2000 memory allocations (all of them, not only big ones) unless the cache is actively used.

charris · 2017-10-17T21:13:59Z

@juliantaylor I'm going to push this off to 1.15 as it sounds like it needs more work and time,

juliantaylor · 2017-10-18T17:00:08Z

well it needs review, the code cleanup is minor and can be done when agreed this concept works for all.

eric-wieser · 2017-10-18T17:17:16Z

 #else
-#define PyTraceMalloc_Track(...)
+#define PyTraceMalloc_Track(...) -2
 #define PyTraceMalloc_Untrack(...)


This should be -2 as well.

charris · 2018-05-11T22:33:36Z

@juliantaylor Needs rebase.

charris · 2018-05-16T21:12:29Z

This seems to be languishing. I want to do 1.15 soon, so going to push this off to 1.16.

juliantaylor · 2018-05-17T17:00:35Z

Delaying it is fine but some opinions on whether we want this in or not would be useful. Maybe I should post it to the list?

mattip · 2018-05-17T17:22:00Z

Is this code/approach freshly developed for NumPy or has it been battle tested elsewhere? It seems like we need some kind of stress tests to make sure the cache works as advertised. I don't know enough about kernel internals to have an opinion on the impact this code might have on security, stability, and performance.

Maybe there could be a switch or environment variable to control cache use, so a single binary could be run in various modes, and we could default to having it off for a release or two, then turn it on?

charris · 2018-11-13T19:15:49Z

I hate to keep pushing this off, but am going to do it again. @juliantaylor Needs a rebase. I think it would also help if it could be demonstrated to improve performance in common cases. As to threading safety, is Python threading (GIL) the only thing we need worry about? The libraries we use certainly do threading. There is currently other caching as well in Python itself, so I wonder if this will play well with that.

jakirkham · 2020-02-09T04:21:36Z

+ * Large memory allocation cache.
+ * Large allocations on glibc systems need to be faulted into the process
+ * before use each use. This can account for a significant fraction of the
+ * runtime of frequent array allocation and deallocation.  This can be avoidded


Suggested change

* runtime of frequent array allocation and deallocation. This can be avoidded

* runtime of frequent array allocation and deallocation. This can be avoided

charris · 2020-12-17T17:11:54Z

I'm going to close this. @juliantaylor If you want to continue this line of thought please open a new PR.

juliantaylor force-pushed the large-cache branch from afe2754 to 1563351 Compare March 14, 2017 14:57

charris added 01 - Enhancement component: numpy._core labels Mar 14, 2017

charris added this to the 1.14.0 release milestone Mar 14, 2017

BLD: support nested headers in OPTION_HEADERS

53336d8

replace path seperators with underscore

juliantaylor force-pushed the large-cache branch from 1563351 to 92d9995 Compare June 1, 2017 10:47

charris reviewed Jun 2, 2017

View reviewed changes

Comment thread numpy/core/src/multiarray/alloc.c Outdated

charris Jun 2, 2017

Copy link
Copy Markdown

Member

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

File does not exist on windows.

juliantaylor force-pushed the large-cache branch from 92d9995 to 5431882 Compare June 3, 2017 09:07

charris added the 51 - In progress label Oct 2, 2017

charris modified the milestones: 1.14.0 release, 1.15.0 release Oct 17, 2017

juliantaylor added 58 - Ready for review and removed 51 - In progress labels Oct 18, 2017

eric-wieser reviewed Oct 18, 2017

View reviewed changes

charris modified the milestones: 1.15.0 release, 1.16.0 release May 16, 2018

juliantaylor mentioned this pull request Sep 7, 2018

Pickle is significantly slower than a memory copy #7544

Closed

charris modified the milestones: 1.16.0 release, 1.17.0 release Nov 13, 2018

charris removed this from the 1.17.0 release milestone Jun 14, 2019

jakirkham reviewed Feb 9, 2020

View reviewed changes

jakirkham mentioned this pull request Jul 31, 2020

Evaluate further serialization performance improvements rapidsai/dask-cuda#106

Closed

charris closed this Dec 17, 2020

	* runtime of frequent array allocation and deallocation. This can be avoidded
	* runtime of frequent array allocation and deallocation. This can be avoided

Conversation

juliantaylor commented Mar 14, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

njsmith commented Mar 14, 2017

Uh oh!

juliantaylor commented Mar 14, 2017

Uh oh!

charris commented Mar 14, 2017

Uh oh!

mattharrigan commented Mar 16, 2017

Uh oh!

juliantaylor commented Mar 16, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

homu commented Apr 7, 2017

Uh oh!

charris commented Jun 2, 2017 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

charris Jun 2, 2017

Choose a reason for hiding this comment

Uh oh!

juliantaylor commented Jun 3, 2017

Uh oh!

charris commented Oct 17, 2017

Uh oh!

juliantaylor commented Oct 18, 2017

Uh oh!

eric-wieser Oct 18, 2017

Choose a reason for hiding this comment

Uh oh!

charris commented May 11, 2018

Uh oh!

charris commented May 16, 2018

Uh oh!

juliantaylor commented May 17, 2018

Uh oh!

mattip commented May 17, 2018

Uh oh!

charris commented Nov 13, 2018

Uh oh!

jakirkham Feb 9, 2020

Choose a reason for hiding this comment

Uh oh!

charris commented Dec 17, 2020

Uh oh!

Reviewers

Uh oh!

Assignees

Labels

Projects

Milestone

Development

Uh oh!

8 participants

juliantaylor commented Mar 14, 2017 •

edited

Loading

juliantaylor commented Mar 16, 2017 •

edited

Loading

charris commented Jun 2, 2017 •

edited

Loading