[issue32422] Make OrderedDict can be used for LRU from C

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

> FWIW, I'm the original author and designer of this code, so it would have
> been appropriate to assign this to me for sign-off on any proposed changes.

Not me (the C implementation)? ;-)

--

___
Python tracker 

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

[issue32422] Make OrderedDict can be used for LRU from C

[Raymond Hettinger]

Raymond Hettinger  added the comment:

FWIW, I'm the original author and designer of this code, so it would have been 
appropriate to assign this to me for sign-off on any proposed changes.

--
assignee:  -> rhettinger

___
Python tracker 

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

[issue32422] Make OrderedDict can be used for LRU from C

[Raymond Hettinger]

Raymond Hettinger  added the comment:

Please stop revising every single thing you look at.  The traditional design of 
LRU caches used doubly linked lists for a reason.  In particular, when there is 
a high hit rate, the links can be updated without churning the underlying 
dictionary.

--
nosy: +rhettinger

___
Python tracker 

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

[issue32422] Make OrderedDict can be used for LRU from C

[INADA Naoki]

INADA Naoki  added the comment:

I found odict.pop() and odict.popitem() is very inefficient because
it look up key multiple times.
odict seems not optimized well and very slow than dict in some area...

I'll try to optimize it in holidays.

--

___
Python tracker 

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

[issue32422] Make OrderedDict can be used for LRU from C

[INADA Naoki]

INADA Naoki  added the comment:

Hmm, it seems my implementation is 30% slower when many mishit scenario.
Maybe, dict is faster than OrderedDict about massive insert/discard.  But I 
need to profile it.

On the other hand, GC speed looks about 2x faster as expected.

$ ./python -m perf compare_to master.json patched.json  -G
Slower (5):
- lru_1000_100: 217 ns +- 6 ns -> 302 ns +- 6 ns: 1.39x slower (+39%)
- lru_1_1000: 225 ns +- 4 ns -> 309 ns +- 2 ns: 1.37x slower (+37%)
- lru_100_1000: 114 ns +- 5 ns -> 119 ns +- 1 ns: 1.05x slower (+5%)
- lru_100_100: 115 ns +- 6 ns -> 119 ns +- 1 ns: 1.03x slower (+3%)
- lru_1000_1000: 134 ns +- 6 ns -> 136 ns +- 1 ns: 1.02x slower (+2%)

Faster (4):
- gc(100): 98.3 ms +- 0.3 ms -> 37.9 ms +- 0.2 ms: 2.59x faster (-61%)
- gc(10): 11.7 ms +- 0.0 ms -> 5.10 ms +- 0.02 ms: 2.29x faster (-56%)
- gc(1): 1.48 ms +- 0.02 ms -> 1.04 ms +- 0.01 ms: 1.41x faster (-29%)
- lru_10_100: 149 ns +- 6 ns -> 147 ns +- 2 ns: 1.02x faster (-2%)

--
Added file: https://bugs.python.org/file47348/lru_bench.py

___
Python tracker 

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

[issue32422] Make OrderedDict can be used for LRU from C

[Serhiy Storchaka]

Change by Serhiy Storchaka :


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

[issue32422] Make OrderedDict can be used for LRU from C

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

Ah, sorry, you use OrderedDict instead of just ordered dict. It should have 
different timing and memory consumption.

--
resolution: duplicate -> 
stage: resolved -> 
status: closed -> open
superseder: Implement functools.lru_cache() using ordered dict -> 

___
Python tracker 

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

[issue32422] Make OrderedDict can be used for LRU from C

[Serhiy Storchaka]

Serhiy Storchaka  added the comment:

This is a duplicate of issue28239.

--
nosy: +serhiy.storchaka
resolution:  -> duplicate
superseder:  -> Implement functools.lru_cache() using ordered dict

___
Python tracker 

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

[issue32422] Make OrderedDict can be used for LRU from C

[INADA Naoki]

INADA Naoki  added the comment:

Current implementation (no news entry yet):
https://github.com/methane/cpython/pull/10/files

--

___
Python tracker 

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

[issue32422] Make OrderedDict can be used for LRU from C

[INADA Naoki]

New submission from INADA Naoki :

Currently, functools.lru_cache implement own doubly-linked list.

But it is inefficient than OrderedDict because each link node is GC object.
So it may eat more memory and take longer GC time.

I added two private C API for OrderedDict and make lru_cache use it.

* _PyODict_LRUGetItem(): Similar to PyDict_GetItemWithHash() + 
od.move_to_end(last=True).
* _PyODict_PopItem():  Similar to odict.popitem().

Why I didn't implement C version of move_to_end() is to reduce lookup.
 _PyODict_LRUGetItem(key) lookup key once while
od[key]; od.move_to_end(key) lookup key twice.

I'll benchmark it and report result here.

--
components: Interpreter Core
messages: 308980
nosy: inada.naoki
priority: normal
severity: normal
status: open
title: Make OrderedDict can be used for LRU from C
versions: Python 3.7

___
Python tracker 

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