[issue28239] Implement functools.lru_cache() using ordered dict

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

Since this theme has been raised again in issue32422 and old patches no longer 
apply clearly I have updated patches and benchmark results on 64 bit.

$ ./python -m perf timeit -s "from functools import lru_cache; f = 
lru_cache(512)(lambda x: x); a = list(range(500))*100" -- "list(map(f, a))"

Unpatched:Mean +- std dev: 3.03 ms +- 0.02 ms
get-del-set:  Mean +- std dev: 5.73 ms +- 0.04 ms
pop-set:  Mean +- std dev: 4.63 ms +- 0.04 ms
move_to_end:  Mean +- std dev: 3.57 ms +- 0.06 ms


$ ./python -m perf timeit -s "from functools import lru_cache; f = 
lru_cache(512)(lambda x: x); a = list(range(5))" -- "list(map(f, a))"

Unpatched:Mean +- std dev: 6.65 ms +- 0.11 ms
get-del-set:  Mean +- std dev: 15.5 ms +- 0.1 ms
pop-set:  Mean +- std dev: 15.4 ms +- 0.1 ms
move_to_end:  Mean +- std dev: 15.5 ms +- 0.2 ms


All patches cause significant slowdown (around 2.3x) in the case of many misses.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28239] Implement functools.lru_cache() using ordered dict

[Serhiy Storchaka]

Change by Serhiy Storchaka :


Added file: https://bugs.python.org/file47352/lru_cache-move_to_end-2.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28239] Implement functools.lru_cache() using ordered dict

[Serhiy Storchaka]

Change by Serhiy Storchaka :


Added file: https://bugs.python.org/file47351/lru_cache-pop-set-2.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28239] Implement functools.lru_cache() using ordered dict

[Serhiy Storchaka]

Change by Serhiy Storchaka :


Added file: https://bugs.python.org/file47350/lru_cache-get-del-set-2.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28239] Implement functools.lru_cache() using ordered dict

[INADA Naoki]

INADA Naoki added the comment:

FYI: Here is interesting article. doubly-linked list is more inefficient than 
most people think.
http://alex.dzyoba.com/programming/dynamic-arrays.html

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28239] Implement functools.lru_cache() using ordered dict

[Serhiy Storchaka]

Changes by Serhiy Storchaka :


--
resolution:  -> rejected
stage:  -> resolved
status: open -> closed

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28239] Implement functools.lru_cache() using ordered dict

[Raymond Hettinger]

Raymond Hettinger added the comment:

> I don't suggest to change lru_cach() implementation just now

For now, I would like to have this closed.  It doesn't make sense at the 
current juncture (with the compact being new, being in flux, and not having 
guaranteed ordering semantics).

Also, we should have a strong preference for loose coupling and high cohesion.  
The lru cache code is principally about tracking recent and should maintain 
primary responsibility for the action, and the dictionary implementation should 
be primarily about a clean mapping implementation without having code baggage 
just for the lru).  

Besides that, there isn't much motivation for change.  The existing code is 
very good (clear, fast, decoupled, cohensive, and doesn't have compaction 
issues for cache hits).

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28239] Implement functools.lru_cache() using ordered dict

[Serhiy Storchaka]

Serhiy Storchaka added the comment:

I consider this issue as lying on the way to using the orderable of dict in 
OrderedDict implementation (the latter is very desirable because current 
OrderedDict implementation can be easily broken by using plain dict API). The 
main difficulty of implementing OrderedDict is the move_to_end() method 
(especially move_to_end(False)).

In additional, the problem of holes is occurred for any often modified 
dictionary. Using ordered dict in lru_cache() give as good stress test for 
optimizing dict updating and resizing code.

I don't suggest to change lru_cach() implementation just now. But after long 
testing ordered dicts during the developing stage of 3.7 (or even 3.8) we can 
make a decision.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28239] Implement functools.lru_cache() using ordered dict

[Raymond Hettinger]

Raymond Hettinger added the comment:

The problem is that cache hits now create "holes" in the compact dict and 
trigger periodic compaction.  In contrast, the existing code leaves dicts 
unchanged when there is a cache hit.  

I prefer the current code. Though it took a little more effort to implement, 
that work is already done and done well.  The linked lists are cheap and have 
consistent, predictable performance.   I also like that the current 
implementation is only loosely coupled with dictionaries and not tightly tied 
to the compact dict with its evolving implementation details.

--

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28239] Implement functools.lru_cache() using ordered dict

[Raymond Hettinger]

Changes by Raymond Hettinger :


--
assignee:  -> rhettinger

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28239] Implement functools.lru_cache() using ordered dict

[Ezio Melotti]

Changes by Ezio Melotti :


--
nosy: +ezio.melotti

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28239] Implement functools.lru_cache() using ordered dict

[Serhiy Storchaka]

Changes by Serhiy Storchaka :


Added file: http://bugs.python.org/file44779/lru_cache-move_to_end.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28239] Implement functools.lru_cache() using ordered dict

[Serhiy Storchaka]

Changes by Serhiy Storchaka :


Added file: http://bugs.python.org/file44778/lru_cache-pop-set.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com

[issue28239] Implement functools.lru_cache() using ordered dict

[Serhiy Storchaka]

New submission from Serhiy Storchaka:

Since dict became ordered, this feature can be used in functools.lru_cache() 
implementation instead of linked list. This significantly simplifies the code.

The first implementation just uses _PyDict_GetItem_KnownHash() + 
_PyDict_DelItem_KnownHash() + _PyDict_SetItem_KnownHash() for moving existent 
key-value pair to the end of the dict.

The second implementation adds replaces the first two calls with one call of 
newly added _PyDict_PopItem_KnownHash() (this is just simplified copy of 
_PyDict_PopItem()).

The third implementation merges all three operations in one function 
_PyDict_MoveToEnd_KnownHash() that returns moved value if it exists, NULL 
without an exception set if there is no such key in a dict, and NULL with an 
exception set in case of error. Maybe this implementation is can be more 
optimized.

Benchmarking hits:

$ ./python -m perf timeit -s "from functools import lru_cache; f = 
lru_cache(512)(lambda x: x); a = list(range(500))*100" -- "list(map(f, a))"

Unpatched:Median +- std dev: 13.5 ms +- 0.8 ms
get-del-set:  Median +- std dev: 21.7 ms +- 0.8 ms
pop-set:  Median +- std dev: 17.0 ms +- 0.6 ms
move_to_end:  Median +- std dev: 13.7 ms +- 0.5 ms

Benchmarking misses:

$ ./python -m perf timeit -s "from functools import lru_cache; f = 
lru_cache(512)(lambda x: x); a = list(range(5))" -- "list(map(f, a))

Unpatched:Median +- std dev: 31.5 ms +- 1.8 ms
get-del-set:  Median +- std dev: 58.6 ms +- 1.0 ms
pop-set:  Median +- std dev: 59.7 ms +- 1.1 ms
move_to_end:  Median +- std dev: 99.0 ms +- 0.5 ms

The get-del-set implementation is simple and don't need adding new functions to 
PyDict API, but it is 60-90% slower the baseline linked-list-based 
implementation. The pop-set implementation is slightly faster for hits. The 
move_to_end implementation is as fast as the baseline implementation for hits, 
but is much slower in case of misses (I think it can be tuned).

--
components: Extension Modules
files: lru_cache-get-del-set.patch
keywords: patch
messages: 277141
nosy: eric.snow, haypo, methane, rhettinger, serhiy.storchaka
priority: low
severity: normal
status: open
title: Implement functools.lru_cache() using ordered dict
type: enhancement
versions: Python 3.7
Added file: http://bugs.python.org/file44777/lru_cache-get-del-set.patch

___
Python tracker 

___
___
Python-bugs-list mailing list
Unsubscribe: 
https://mail.python.org/mailman/options/python-bugs-list/archive%40mail-archive.com