GeezerVison is showing github.com — gh-107089: Improve Shelf.clear method performance by jtcave · Pull Request #107090 · python/cpython
Conversation
jtcave
commented
Jul 23, 2023
•
edited by bedevere-bot
Loading
Uh oh!
There was an error while loading. Please reload this page.
Shelf inherits its clear method from MutableMapping, but the implementation is poorly suited for that class. The clear mix-in is implemented by calling popitem in a loop. Each call to popitem constructs a new iterator over the shelf, which is a generator that does byte-to-str conversion on the keys in the dbm object. Unfortunately, dbm objects are non-iterable, and their keys method simply returns a list of all keys. Since each popitem call performs a full scan of the key space, the clear method ends up having O(n²) performance (assuming the delete and read operations amortize to O(1)).
By having the shelf just iterate over the list of dbm keys once, this is avoided.
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
ghost
commented
Jul 23, 2023
•
edited by ghost
Loading
Uh oh!
There was an error while loading. Please reload this page.
|
All commit authors signed the Contributor License Agreement. 
|
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
|
Thanks for the clear description of the problem. The solution looks ok, but I am a bit concerned it is not fully backwards compatible with classes derived from Shelf. A safer option would be to move the clear method to the DbfilenameShelf.
|
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
jtcave
requested review from
a team,
1st1,
AlexWaygood,
asvetlov,
corona10,
erlend-aasland,
gvanrossum,
kumaraditya303,
markshannon,
vsajip and
willingc
as code owners
July 23, 2023 14:36
Uh oh!
There was an error while loading. Please reload this page.
Thanks for the clear description of the problem. The solution looks ok, but I am a bit concerned it is not fully backwards compatible with classes derived from Shelf. A safer option would be to move the clear method to the DbfilenameShelf.
+1
|
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
jtcave
commented
Jul 24, 2023
•
edited
Loading
Uh oh!
There was an error while loading. Please reload this page.
|
It appears that the ndbm.clear method, while substantially faster than the MutableMapping implementation, is still an order of magnitude slower than the fallback code.
Revised test script:
import os
import shelve
import tempfile
import timeit
def clearshelf(db):
keys = list(db.keys())
for k in keys:
del db[k]
def test_clear(use_clear_method):
with tempfile.TemporaryDirectory() as tempdir:
filename = os.path.join(tempdir, "test-shelf")
with shelve.open(filename) as db:
items = {str(x):x for x in range(10000)}
db.update(items)
if use_clear_method:
db.clear()
else:
clearshelf(db)
assert len(db) == 0
test_with_clear = lambda: test_clear(True)
test_without_clear = lambda: test_clear(False)
if __name__ == "__main__":
TRIALS = 5
method_time = timeit.timeit(test_with_clear, number=TRIALS, globals=globals()) / TRIALS
print(f"method:\t{method_time:.3}")
func_time = timeit.timeit(test_without_clear, number=TRIALS, globals=globals()) / TRIALS
print(f"func:\t{func_time:.3}")
Running on my branch:
james@iris cpython-build % ./python.exe ~/shelve-clear-test.py
method: 0.596
func: 0.0272
Edited Jul 26: Finally got to test the other dbms, using Rocky Linux/aarch64 9.2.
With gdbm:
[james@trina cpython-build]$ ./python ~/shelve-clear-test.py
method: 0.0775
func: 0.0305
By forcing dbm.dumb:
The times are a lot closer on gdbm and practically the same on dbm.dumb. Since most shelve users will be using these backends (ndbm is only really relevant on macOS), I don't think this is worth worrying about.
|
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
|
@jtcave Would you like to rebase the PR?
|
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
corona10
removed request for
1st1,
JelleZijlstra,
abalkin,
asvetlov,
barneygale,
berkerpeksag,
brettcannon,
ericsnowcurrently,
iritkatriel,
ncoghlan,
pganssle,
rhettinger,
tiran,
vsajip and
warsaw
July 27, 2023 08:33
The clear method used to be implemented by inheriting a mix-in from the
MutableMapping ABC. It was a poor fit for shelves, and a better
implementation is now in place
Because pythongh-107089 is peculiar to implementation details of dbm objects,
it would be less disruptive to implement it in the DbfilenameShelf
class, which is used for calls to shelve.open. Since it is known that
the backing object is specifically one of the dbm objects, its clear
method (see pythongh-107122) can be used with no fallback code.
There was a problem hiding this comment.
Choose a reason for hiding this comment
The reason will be displayed to describe this comment to others. Learn more.
Sorry, something went wrong.
Uh oh!
There was an error while loading. Please reload this page.
Reviewers
corona10
corona10 approved these changes
Uh oh!
There was an error while loading. Please reload this page.
Milestone
No milestone
Development
Successfully merging this pull request may close these issues.
Uh oh!
There was an error while loading. Please reload this page.
Add this suggestion to a batch that can be applied as a single commit.This suggestion is invalid because no changes were made to the code.Suggestions cannot be applied while the pull request is closed.Suggestions cannot be applied while viewing a subset of changes.Only one suggestion per line can be applied in a batch.Add this suggestion to a batch that can be applied as a single commit.Applying suggestions on deleted lines is not supported.You must change the existing code in this line in order to create a valid suggestion.Outdated suggestions cannot be applied.This suggestion has been applied or marked resolved.Suggestions cannot be applied from pending reviews.Suggestions cannot be applied on multi-line comments.Suggestions cannot be applied while the pull request is queued to merge.Suggestion cannot be applied right now. Please check back later.
|