amitdev / lru-dict

A fast and memory efficient LRU cache for Python

Hi there 👋

See some of my projects below. Also see my blog.

lru-dict's Issues

In test_lru.py: line 121 test_update()

You test command l.update({'a':1, 'b':2})
But in Python, the order that 'a' and 'b' is visited is random.
So it might update key 'b' first, and then b become the last node in LRU,
at last, self.assertEqual(('b', 2), l.peek_first_item()) might fail.

Support update() function

https://docs.python.org/2/library/stdtypes.html#dict.update

Proposal to Integrate SIEVE Eviction Algorithm

Hi there,

Our team (@1a1a11a) has developed a new cache eviction algorithm, called SIEVE. It’s simple, efficient, and scalable.

Why SIEVE could be a great addition:

• Simplicity: Integrating SIEVE is straightforward, usually needing to change less than 20 lines of code on average.
• Efficiency: On skewed workloads, which are typical in web caching scenarios, SIEVE is top-notch.
• Cache Primitive: SIEVE is not just another algorithm; it's a primitive that could enhance or replace LRU/FIFO queues in advanced systems like LeCaR, TwoQ, ARC, and S3-FIFO.

Welcome to dive into the details on our website sievecache.com and on our SIEVE blog.

We would love to explore the possibility of integrating SIEVE into lru-dict. We believe it could be a beneficial addition to the library and the community.

Looking forward to your feedback!

Add a lru.pyi

add a stub file for better user experience

e.g.

# lru.pyi
from typing import Any, Generic, Hashable, TypeVar, Callable

_K = TypeVar("_K", bound=Hashable)
_V = TypeVar("_V")
_T = TypeVar("_T")

class LRU(Generic[_K, _V]):

    def __init__(self, size: int, callback: Callable[[_K, _V], Any] | None) -> None: ...
    def get(self, key: _K, default: _T) -> _V | _T: ...
    def __getitem__(self, item: _K) -> _V: ...
    def set(self, key: _K, value: Any) -> None: ...
    def __setitem__(self, key: _K, value: Any) -> None: ...
    ...

__repr__ shouldn't look like plain dict, it's confusing

note: this is still the faster version

was curious, even with the new builtin ordered dict, the simple python impl is still slower, but barely! should probably update the readme. no need to compare to old and extremely slow impls.

A = TypeVar("A")
T = TypeVar("T")

class LRU(Generic[A, T]):
    """Simple LRU cache using a dictionary."""
    def __init__(self, maxsize: int):
        self.cache = dict[Any]()
        self.maxsize = maxsize

    def get(self, key: A, default: T | None = None) -> T | None:
        if key not in self.cache:
            return default
        else:
            self.cache[key] = self.cache.pop(key)
            return self.cache[key]

    def put(self, key: A, value: int) -> None:
        self.cache[key] = value
        if len(self.cache) > self.maxsize:
            self.cache.pop(next(iter(self.cache)))

timeit

    simple = LRU(10)
    ll = lib.LRU(10)

    import timeit

    print("simple:", timeit.timeit(lambda: [simple.put(i, 1) for i in range(100)], number=10000))
    print("lru-dict:", timeit.timeit(lambda: [ll.__setitem__(i, 1) for i in range(100)], number=10000))

simple timeit results:

simple: 0.1914528000052087
lru-dict: 0.1341520000132732

Compatibility Python 3.11

I have problem when I am trying to install lru-dict on Python 3.11:

Failed to build lru-dict
Installing collected packages: lru-dict
Running setup.py install for lru-dict ... error
error: subprocess-exited-with-error

× Running setup.py install for lru-dict did not run successfully.
│ exit code: 1
╰─> [7 lines of output]
running install
.venv\Lib\site-packages\setuptools\command\install.py:34: SetuptoolsDeprecationWarning: setup.py install is deprecated. Use build and pip and other standards-based tools.
warnings.warn(
running build
running build_ext
building 'lru' extension
error: Microsoft Visual C++ 14.0 or greater is required. Get it with "Microsoft C++ Build Tools": https://visualstudio.microsoft.com/visual-cpp-build-tools/
[end of output]

note: This error originates from a subprocess, and is likely not a problem with pip.
error: legacy-install-failure

× Encountered error while trying to install package.
╰─> lru-dict

note: This is an issue with the package mentioned above, not pip.
hint: See above for output from the failure.

lru.LRU does not support deepcopy

trying to deepcopy an LRU object results in

TypeError: cannot pickle 'lru.LRU' object

it would be nice to be able to deepcopy LRU objects, though.

lru-dict and apache mod_wsgi

Hi ,
I have a python script using lru-dict , i try to run it under apache mod_wsgi , but it throw this error

[Tue Jun 04 14:22:10.134913 2024] [wsgi:error] [pid 3669406:tid 3669547] [remote ::1:43432]   File "/opt/xx/my_server/site-packages/lru/__init__.py", line 1, in <module>
[Tue Jun 04 14:22:10.134928 2024] [wsgi:error] [pid 3669406:tid 3669547] [remote ::1:43432]     from ._lru import LRU as LRU  # noqa: F401
[Tue Jun 04 14:22:10.134950 2024] [wsgi:error] [pid 3669406:tid 3669547] [remote ::1:43432] ModuleNotFoundError: No module named 'lru._lru'

any one get an idea about this error
thank you

Architecture errors on macosx-10.9-universal2-3.10/lru.o

Hi when installing web3 on a 2017 mac installation breaks with multiple Unsupported architecture errors.

Fix:
ARCHFLAGS="-arch x86_64" pip install web3

Full stack:

      building 'lru' extension
      creating build
      creating build/temp.macosx-10.9-universal2-3.10
      clang -Wno-unused-result -Wsign-compare -Wunreachable-code -fno-common -dynamic -DNDEBUG -g -fwrapv -O3 -Wall -arch arm64 -arch x86_64 -g -I/Users/jeanpaulruizdepraz/Documents/software/sni/web3_py/venv/include -I/Library/Frameworks/Python.framework/Versions/3.10/include/python3.10 -c lru.c -o build/temp.macosx-10.9-universal2-3.10/lru.o
      In file included from lru.c:1:
      In file included from /Library/Frameworks/Python.framework/Versions/3.10/include/python3.10/Python.h:11:
      In file included from /Library/Developer/CommandLineTools/usr/lib/clang/12.0.0/include/limits.h:21:
      In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/limits.h:63:
      /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/sys/cdefs.h:807:2: error: Unsupported architecture
      #error Unsupported architecture
       ^
      In file included from lru.c:1:
      In file included from /Library/Frameworks/Python.framework/Versions/3.10/include/python3.10/Python.h:11:
      In file included from /Library/Developer/CommandLineTools/usr/lib/clang/12.0.0/include/limits.h:21:
      In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/limits.h:64:
      /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/machine/limits.h:8:2: error: architecture not supported
      #error architecture not supported
       ^
      In file included from lru.c:1:
      In file included from /Library/Frameworks/Python.framework/Versions/3.10/include/python3.10/Python.h:25:
      In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/stdio.h:64:
      In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/_stdio.h:71:
      In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/_types.h:27:
      In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/sys/_types.h:33:
      /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/machine/_types.h:34:2: error: architecture not supported
      #error architecture not supported
       ^
      In file included from lru.c:1:
      In file included from /Library/Frameworks/Python.framework/Versions/3.10/include/python3.10/Python.h:25:
      In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/stdio.h:64:
      In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/_stdio.h:71:
      In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/_types.h:27:
      /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/sys/_types.h:55:9: error: unknown type name '__int64_t'
      typedef __int64_t       __darwin_blkcnt_t;      /* total blocks */
              ^
      /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/sys/_types.h:56:9: error: unknown type name '__int32_t'; did you mean '__int128_t'?
      typedef __int32_t       __darwin_blksize_t;     /* preferred block size */
              ^
      note: '__int128_t' declared here
      /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/sys/_types.h:57:9: error: unknown type name '__int32_t'; did you mean '__int128_t'?
      typedef __int32_t       __darwin_dev_t;         /* dev_t */
              ^
      note: '__int128_t' declared here
      /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/sys/_types.h:60:9: error: unknown type name '__uint32_t'; did you mean '__uint128_t'?
      typedef __uint32_t      __darwin_gid_t;         /* [???] process and group IDs */
              ^
      note: '__uint128_t' declared here
      /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/sys/_types.h:61:9: error: unknown type name '__uint32_t'; did you mean '__uint128_t'?
      typedef __uint32_t      __darwin_id_t;          /* [XSI] pid_t, uid_t, or gid_t*/
              ^
      note: '__uint128_t' declared here
      /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/sys/_types.h:62:9: error: unknown type name '__uint64_t'
      typedef __uint64_t      __darwin_ino64_t;       /* [???] Used for 64 bit inodes */
              ^
      /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/sys/_types.h:68:9: error: unknown type name '__darwin_natural_t'
      typedef __darwin_natural_t __darwin_mach_port_name_t; /* Used by mach */
              ^
      /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/sys/_types.h:70:9: error: unknown type name '__uint16_t'; did you mean '__uint128_t'?
      typedef __uint16_t      __darwin_mode_t;        /* [???] Some file attributes */
              ^
      note: '__uint128_t' declared here
      /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/sys/_types.h:71:9: error: unknown type name '__int64_t'
      typedef __int64_t       __darwin_off_t;         /* [???] Used for file sizes */
              ^
      /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/sys/_types.h:72:9: error: unknown type name '__int32_t'; did you mean '__int128_t'?
      typedef __int32_t       __darwin_pid_t;         /* [???] process and group IDs */
              ^
      note: '__int128_t' declared here
      /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/sys/_types.h:73:9: error: unknown type name '__uint32_t'; did you mean '__uint128_t'?
      typedef __uint32_t      __darwin_sigset_t;      /* [???] signal set */
              ^
      note: '__uint128_t' declared here
      /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/sys/_types.h:74:9: error: unknown type name '__int32_t'; did you mean '__int128_t'?
      typedef __int32_t       __darwin_suseconds_t;   /* [???] microseconds */
              ^
      note: '__int128_t' declared here
      /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/sys/_types.h:75:9: error: unknown type name '__uint32_t'; did you mean '__uint128_t'?
      typedef __uint32_t      __darwin_uid_t;         /* [???] user IDs */
              ^
      note: '__uint128_t' declared here
      /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/sys/_types.h:76:9: error: unknown type name '__uint32_t'; did you mean '__uint128_t'?
      typedef __uint32_t      __darwin_useconds_t;    /* [???] microseconds */
              ^
      note: '__uint128_t' declared here
      In file included from lru.c:1:
      In file included from /Library/Frameworks/Python.framework/Versions/3.10/include/python3.10/Python.h:25:
      In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/stdio.h:64:
      In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/_stdio.h:71:
      /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/_types.h:43:9: error: unknown type name '__uint32_t'; did you mean '__uint128_t'?
      typedef __uint32_t      __darwin_wctype_t;
              ^
      note: '__uint128_t' declared here
      In file included from lru.c:1:
      In file included from /Library/Frameworks/Python.framework/Versions/3.10/include/python3.10/Python.h:25:
      In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/stdio.h:64:
      In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/_stdio.h:75:
      In file included from /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/sys/_types/_va_list.h:31:
      /Library/Developer/CommandLineTools/SDKs/MacOSX.sdk/usr/include/machine/types.h:37:2: error: architecture not supported
      #error architecture not supported
       ^
      fatal error: too many errors emitted, stopping now [-ferror-limit=]
      20 errors generated.
      error: command '/usr/bin/clang' failed with exit code 1
      [end of output]

How to serialize/deserialize lru.LRU

I tried h5py and pickle, both ways cannot serialize/deserialize the lru.LRU object, so is there a method to make it?

popitem leads to memory-leak

env:

• linux 4.19.91-009
• glibc-2.32

call this order

• 1 add one item
• 2 popitem

simple example leads to memory-leak

After LRU access and clear fails

Basically, the following code fails:

l = LRU(2)
l[0] = 0
l[1] = 1
a = l[0]
l.clear()

Release new version to pypi

Thanks for an excellent extension. Any chance of uploading a new version to pypi that includes the latest features (specifically, the has_key() and get() methods)?

Error installing on a venv with Python 3

Should this work with Python 3? I get this error, but not sure if it's a problem my end?

Command "/Library/Frameworks/Python.framework/Versions/3.4/bin/python3.4 -c "import setuptools, tokenize;__file__='/private/var/folders/0q/pk7bz0ln5k5_61dd24v3xq_00000gn/T/pip-build-r9nrpuyq/lru-dict/setup.py';exec(compile(getattr(tokenize, 'open', open)(__file__).read().replace('\r\n', '\n'), __file__, 'exec'))" install --record /var/folders/0q/pk7bz0ln5k5_61dd24v3xq_00000gn/T/pip-eqnpqfq1-record/install-record.txt --single-version-externally-managed --compile" failed with error code 1 in /private/var/folders/0q/pk7bz0ln5k5_61dd24v3xq_00000gn/T/pip-build-r9nrpuyq/lru-dict

lru-dict segfaults on use after being serialized/deserialized with pickle

It's always a bit weird to hit a segfault in Python!

Here's a simple example that hits this issue:

import pickle                                             
from lru import LRU                                       
                                                          
key_limit = 10                                            
a = LRU(key_limit)                                        
for i in range(key_limit - 5):                            
    a[i] = key_limit - i                                  
print(a[0])                                               
                                                          
with open("/vol/data0/tmp/example_lru.pkl",'wb') as f:     
    print("Saving LRU")                                   
    pickle.dump(a, f, pickle.HIGHEST_PROTOCOL)            
                                                          
                                                          
with open("/vol/data0/tmp/example_lru.pkl",'rb') as f:     
    print("Loading LRU")                                  
    b = pickle.load(f)                                    
                                                          
print(b[0])                                               

Output:

10
Saving LRU
Loading LRU
Segmentation fault (core dumped)

Not sure if you've intended the LRU to survive serialization / deserialization, but if not I'd understand closing this.

Thanks!

Add a `__contains__` method

LRU.has_key already exists, but the Pythonic way is to use in:

In [1]: from lru import LRU

In [2]: d = LRU(10)

In [3]: d['a'] = 10

In [4]: 'a' in d
---------------------------------------------------------------------------
TypeError                                 Traceback (most recent call last)
<ipython-input-4-8d3729405706> in <module>()
----> 1 'a' in d

TypeError: argument of type 'lru.LRU' is not iterable

In [5]: d.has_key('a')
True

LU vs LRU ?

is it possible to make so it works on the bases of evicting first the Least Used instead of Least Recently Used ... i.e. based on usage not on recency ?

I mean LFU - least frequently used

Plan for ttl support?

Hi, do you have a plan for ttl support on items being saved?

incompatible function pointer types initializing 'PyCFunction'

➜  ~ pip install lru-dict             
Looking in indexes: https://pypi.tuna.tsinghua.edu.cn/simple
Collecting lru-dict
  Using cached https://pypi.tuna.tsinghua.edu.cn/packages/79/da/138e76e2e9ecf074a5ee26cacbd0676e1efdfff2bda3e6f40a6dc8728bf3/lru-dict-1.1.8.tar.gz (10 kB)
  Preparing metadata (setup.py) ... done
Installing collected packages: lru-dict
  DEPRECATION: lru-dict is being installed using the legacy 'setup.py install' method, because it does not have a 'pyproject.toml' and the 'wheel' package is not installed. pip 23.1 will enforce this behaviour change. A possible replacement is to enable the '--use-pep517' option. Discussion can be found at https://github.com/pypa/pip/issues/8559
  Running setup.py install for lru-dict ... error
  error: subprocess-exited-with-error
  
  × Running setup.py install for lru-dict did not run successfully.
  │ exit code: 1
  ╰─> [12 lines of output]
      running install
      running build
      running build_ext
      building 'lru' extension
      creating build
      creating build/temp.linux-aarch64-3.9
      aarch64-linux-android-clang -Wno-unused-result -Wsign-compare -Wunreachable-code -DNDEBUG -g -fwrapv -O3 -Wall -fstack-protector-strong -O3 -fstack-protector-strong -O3 -fPIC -I/data/data/com.termux/files/usr/include/python3.9 -c lru.c -o build/temp.linux-aarch64-3.9/lru.o
      lru.c:629:17: error: incompatible function pointer types initializing 'PyCFunction' (aka 'struct _object *(*)(struct _object *, struct _object *)') with an expression of type 'PyCFunctionWithKeywords' (aka 'struct _object *(*)(struct _object *, struct _object *, struct _object *)') [-Wincompatible-function-pointer-types]
          {"popitem", (PyCFunctionWithKeywords)LRU_popitem, METH_VARARGS | METH_KEYWORDS,
                      ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
      1 error generated.
      error: command '/data/data/com.termux/files/usr/bin/aarch64-linux-android-clang' failed with exit code 1
      [end of output]
  
  note: This error originates from a subprocess, and is likely not a problem with pip.
error: legacy-install-failure

× Encountered error while trying to install package.
╰─> lru-dict

note: This is an issue with the package mentioned above, not pip.
➜  ~ pip -V 
pip 23.0.1 from /data/data/com.termux/files/usr/lib/python3.9/site-packages/pip (python 3.9)
➜  ~ python -V                          
Python 3.9.16

Support pop

d.pop(k) -> del k[d]; return what was deleted
i would do this but idk any C and you can't inherit C classes

Support weak references

We ran into an issue trying to create weak references to LRU objects: the current implementation of LRU does not support weak references. It would be straightforward to implement according to the guidelines from https://python.readthedocs.io/en/v2.7.2/extending/newtypes.html#weak-reference-support, and would make the LRU class more usable in advanced scenarios, such as monitoring transient caches without keeping a hard reference to them.

is it thread safe?

Memory leak?

I'm not skillfull in C extensions in Python. Simple changes and/or extensions are not a problem but memory leaks are over me - so I can't figure out where is the problem.

It seems to me lru.c is not handling memory correctly. See example bellow:

import lru
l=lru.LRU(10000000)
for i in xrange(10000000): l[i] = str(i)
...
import resource
resource.getrusage(resource.RUSAGE_SELF).ru_maxrss
1616548
del l
resource.getrusage(resource.RUSAGE_SELF).ru_maxrss
1616548

Create pre-built wheel

Please create pre-built wheels for Windows, Linux and macOS to allow easier installation of the package. You can use Travis CI or other CI for this.

You can use wheelwright for this.

error lru module in module web3. python, kivy, buildozer, android

I use the web3 module in my project, the web3 module uses the lru-dict module. When building a project on Android via bulldozer, an error occurs:
python : [WARNING] Consider installing rusty-rlp to improve pyrlp performance with a rust based backend python : Traceback (most recent call last): python : File "/home/yumak/project/ctea_project/.buildozer/android/app/main.py", line 23, in <module> python : File "/home/yumak/project/ctea_project/.buildozer/android/platform/build-armeabi-v7a/build/python-installs/ctea/web3/__init__.py", line 9, in <module> python : File "/home/yumak/project/ctea_project/.buildozer/android/platform/build-armeabi-v7a/build/python-installs/ctea/web3/main.py", line 69, in <module> python : File "/home/yumak/project/ctea_project/.buildozer/android/platform/build-armeabi-v7a/build/python-installs/ctea/web3/manager.py", line 31, in <module> python : File "/home/yumak/project/ctea_project/.buildozer/android/platform/build-armeabi-v7a/build/python-installs/ctea/web3/middleware/__init__.py", line 20, in <module> python : File "/home/yumak/project/ctea_project/.buildozer/android/platform/build-armeabi-v7a/build/python-installs/ctea/web3/middleware/cache.py", line 15, in <module> python : ImportError: dlopen failed: "/data/data/ru.ctea/files/app/_python_bundle/site-packages/lru.so" is 64-bit instead of 32-bit python : Python for android ended.
Please help me find out what can be done.