Skip to content

Commit 175476f

Browse files
committed
Merge pull request #7686 from krischer/limit-fft-cache
ENH: Changing FFT cache to a bounded LRU cache
2 parents f65b233 + 2de9651 commit 175476f

4 files changed

Lines changed: 159 additions & 2 deletions

File tree

‎doc/release/1.12.0-notes.rst‎

Lines changed: 7 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -185,6 +185,13 @@ Add ``bits`` attribute to ``np.finfo``
185185
This makes ``np.finfo`` consistent with ``np.iinfo`` which already has that
186186
attribute.
187187

188+
Caches in `np.fft` are now bounded in total size and item count
189+
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
190+
The caches in `np.fft` that speed up successive FFTs of the same length can no
191+
longer grow without bounds. They have been replaced with LRU (least recently
192+
used) caches that automatically evict no longer needed items if either the
193+
memory size or item count limit has been reached.
194+
188195

189196
Changes
190197
=======

‎numpy/fft/fftpack.py‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -38,9 +38,10 @@
3838
from numpy.core import (array, asarray, zeros, swapaxes, shape, conjugate,
3939
take, sqrt)
4040
from . import fftpack_lite as fftpack
41+
from .helper import _FFTCache
4142

42-
_fft_cache = {}
43-
_real_fft_cache = {}
43+
_fft_cache = _FFTCache(max_size_in_mb=100, max_item_count=32)
44+
_real_fft_cache = _FFTCache(max_size_in_mb=100, max_item_count=32)
4445

4546

4647
def _raw_fft(a, n=None, axis=-1, init_function=fftpack.cffti,

‎numpy/fft/helper.py‎

Lines changed: 62 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4,6 +4,8 @@
44
"""
55
from __future__ import division, absolute_import, print_function
66

7+
from collections import OrderedDict
8+
79
from numpy.compat import integer_types
810
from numpy.core import (
911
asarray, concatenate, arange, take, integer, empty
@@ -222,3 +224,63 @@ def rfftfreq(n, d=1.0):
222224
N = n//2 + 1
223225
results = arange(0, N, dtype=int)
224226
return results * val
227+
228+
229+
class _FFTCache(object):
230+
"""
231+
Cache for the FFT init functions as an LRU (least recently used) cache.
232+
233+
Parameters
234+
----------
235+
max_size_in_mb : int
236+
Maximum memory usage of the cache before items are being evicted.
237+
max_item_count : int
238+
Maximum item count of the cache before items are being evicted.
239+
240+
Notes
241+
-----
242+
Items will be evicted if either limit has been reached upon getting and
243+
setting. The maximum memory usages is not strictly the given
244+
``max_size_in_mb`` but rather
245+
``max(max_size_in_mb, 1.5 * size_of_largest_item)``. Thus the cache will
246+
never be completely cleared - at least one item will remain and a single
247+
large item can cause the cache to retain several smaller items even if the
248+
given maximum cache size has been exceeded.
249+
"""
250+
def __init__(self, max_size_in_mb, max_item_count):
251+
self._max_size_in_bytes = max_size_in_mb * 1024 ** 2
252+
self._max_item_count = max_item_count
253+
# Much simpler than inheriting from it and having to work around
254+
# recursive behaviour.
255+
self._dict = OrderedDict()
256+
257+
def setdefault(self, key, value):
258+
return self._dict.setdefault(key, value)
259+
260+
def __getitem__(self, key):
261+
# pop + add to move it to the end.
262+
value = self._dict.pop(key)
263+
self._dict[key] = value
264+
self._prune_dict()
265+
return value
266+
267+
def __setitem__(self, key, value):
268+
# Just setting is it not enough to move it to the end if it already
269+
# exists.
270+
try:
271+
del self._dict[key]
272+
except:
273+
pass
274+
self._dict[key] = value
275+
self._prune_dict()
276+
277+
def _prune_dict(self):
278+
# Always keep at least one item.
279+
while len(self._dict) > 1 and (
280+
len(self._dict) > self._max_item_count or self._check_size()):
281+
self._dict.popitem(last=False)
282+
283+
def _check_size(self):
284+
item_sizes = [_i[0].nbytes for _i in self._dict.values() if _i]
285+
max_size = max(self._max_size_in_bytes, 1.5 * max(item_sizes))
286+
return sum(item_sizes) > max_size

‎numpy/fft/tests/test_helper.py‎

Lines changed: 87 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -10,6 +10,7 @@
1010
from numpy.testing import TestCase, run_module_suite, assert_array_almost_equal
1111
from numpy import fft
1212
from numpy import pi
13+
from numpy.fft.helper import _FFTCache
1314

1415

1516
class TestFFTShift(TestCase):
@@ -74,5 +75,91 @@ def test_not_last_axis_success(self):
7475
fft.irfftn(a, axes=axes)
7576

7677

78+
class TestFFTCache(TestCase):
79+
80+
def test_basic_behaviour(self):
81+
c = _FFTCache(max_size_in_mb=1, max_item_count=4)
82+
# Setting
83+
c[1] = [np.ones(2, dtype=np.float32)]
84+
c[2] = [np.zeros(2, dtype=np.float32)]
85+
# Getting
86+
assert_array_almost_equal(c[1][0], np.ones(2, dtype=np.float32))
87+
assert_array_almost_equal(c[2][0], np.zeros(2, dtype=np.float32))
88+
# Setdefault
89+
c.setdefault(1, [np.array([1, 2], dtype=np.float32)])
90+
assert_array_almost_equal(c[1][0], np.ones(2, dtype=np.float32))
91+
c.setdefault(3, [np.array([1, 2], dtype=np.float32)])
92+
assert_array_almost_equal(c[3][0], np.array([1, 2], dtype=np.float32))
93+
94+
self.assertEqual(len(c._dict), 3)
95+
96+
def test_automatic_pruning(self):
97+
# Thats around 2600 single precision samples.
98+
c = _FFTCache(max_size_in_mb=0.01, max_item_count=4)
99+
c[1] = [np.ones(200, dtype=np.float32)]
100+
c[2] = [np.ones(200, dtype=np.float32)]
101+
102+
# Don't raise errors.
103+
c[1], c[2], c[1], c[2]
104+
105+
# This is larger than the limit but should still be kept.
106+
c[3] = [np.ones(3000, dtype=np.float32)]
107+
# Should exist.
108+
c[1], c[2], c[3]
109+
# Add one more.
110+
c[4] = [np.ones(3000, dtype=np.float32)]
111+
112+
# The other three should no longer exist.
113+
with self.assertRaises(KeyError):
114+
c[1]
115+
with self.assertRaises(KeyError):
116+
c[2]
117+
with self.assertRaises(KeyError):
118+
c[3]
119+
120+
# Now test the max item count pruning.
121+
c = _FFTCache(max_size_in_mb=0.01, max_item_count=2)
122+
c[1] = [np.empty(2)]
123+
c[2] = [np.empty(2)]
124+
# Can still be accessed.
125+
c[2], c[1]
126+
127+
c[3] = [np.empty(2)]
128+
129+
# 1 and 3 can still be accessed - c[2] has been touched least recently
130+
# and is thus evicted.
131+
c[1], c[3]
132+
133+
with self.assertRaises(KeyError):
134+
c[2]
135+
136+
c[1], c[3]
137+
138+
# One last test. We will add a single large item that is slightly
139+
# bigger then the cache size. Some small items can still be added.
140+
c = _FFTCache(max_size_in_mb=0.01, max_item_count=5)
141+
c[1] = [np.ones(3000, dtype=np.float32)]
142+
c[1]
143+
c[2] = [np.ones(2, dtype=np.float32)]
144+
c[3] = [np.ones(2, dtype=np.float32)]
145+
c[4] = [np.ones(2, dtype=np.float32)]
146+
c[1], c[2], c[3], c[4]
147+
148+
# One more big item.
149+
c[5] = [np.ones(3000, dtype=np.float32)]
150+
151+
# c[1] no longer in the cache. Rest still in the cache.
152+
c[2], c[3], c[4], c[5]
153+
with self.assertRaises(KeyError):
154+
c[1]
155+
156+
# Another big item - should now be the only item in the cache.
157+
c[6] = [np.ones(4000, dtype=np.float32)]
158+
for _i in range(1, 6):
159+
with self.assertRaises(KeyError):
160+
c[_i]
161+
c[6]
162+
163+
77164
if __name__ == "__main__":
78165
run_module_suite()

0 commit comments

Comments
 (0)