GV

GeezerVison

The World Wide Web, restored to 800 pixels of glory.

Home|About|Gaming cabinet|Archives|How it works|Starter sites

On this site

  • Sign in
  • ActionsCI/CD and automation
  • CodespacesCloud development environments
  • All Features
  • Documentation
  • Training
  • Certifications
  • Build with Copilot
  • Customize Copilot
  • Integrations
  • Trending repos
  • GitHub Sponsors
  • Developer articles
  • Enterprises

This view

  • Original page
  • New address

GeezerVison is showing github.com — gh-107089: Improve Shelf.clear method performance by jtcave · Pull Request #107090 · python/cpython

Conversation

@jtcave

@jtcave jtcave commented Jul 23, 2023 •
edited by bedevere-bot
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Contributor

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.

  • Issue: shelve: Shelf.clear() has very poor performance #107089

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
@bedevere-bot bedevere-bot mentioned this pull request Jul 23, 2023
shelve: Shelf.clear() has very poor performance #107089
Closed
@bedevere-bot bedevere-bot added the awaiting review label Jul 23, 2023
@ghost

ghost commented Jul 23, 2023 •
edited by ghost
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown

All commit authors signed the Contributor License Agreement.
CLA signed

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@eendebakpt

eendebakpt commented Jul 23, 2023

Copy link
Copy Markdown
Contributor

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.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@corona10

corona10 commented Jul 23, 2023

Copy link
Copy Markdown
Member

See: #107122

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@jtcave
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
@AlexWaygood
AlexWaygood removed their request for review July 23, 2023 14:41
corona10
corona10 reviewed Jul 23, 2023
View reviewed changes
Comment thread Lib/shelve.py Resolved

Uh oh!

There was an error while loading. Please reload this page.

@erlend-aasland
erlend-aasland removed their request for review July 23, 2023 15:19
@corona10

corona10 commented Jul 24, 2023

Copy link
Copy Markdown
Member

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

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@jtcave

jtcave commented Jul 24, 2023 •
edited
Loading

Uh oh!

There was an error while loading. Please reload this page.

Copy link
Copy Markdown
Contributor Author

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:

method: 13.5
func:   13.4

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.

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@jtcave
jtcave requested a review from corona10 July 26, 2023 15:46
@corona10

corona10 commented Jul 27, 2023

Copy link
Copy Markdown
Member

@jtcave Would you like to rebase the PR?

All reactions

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

@corona10 corona10 self-assigned this Jul 27, 2023
@jtcave
jtcave requested review from barneygale, berkerpeksag, isidentical, pablogsal and rhettinger as code owners July 27, 2023 03:16
@kumaraditya303
kumaraditya303 removed request for brandtbucher, lysnikolaou and pablogsal July 27, 2023 07:15
@corona10
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
@jtcave
jtcave force-pushed the shelve-clear branch from 5530781 to 0353d56 Compare July 27, 2023 20:56
jtcave added 4 commits July 28, 2023 10:03
@jtcave
pythongh-107089: Improve Shelf.clear method performance
2b5cc11
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
@jtcave
pythongh-107089: call dbm.clear method
0e3f387
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.
@jtcave
fix whitespace
0f41369
@jtcave
fix whitespace
d90b207
@jtcave
jtcave force-pushed the shelve-clear branch from 88d48f6 to d90b207 Compare July 28, 2023 14:07
corona10
corona10 approved these changes Jul 29, 2023
View reviewed changes

@corona10 corona10 left a comment

Copy link
Copy Markdown
Member

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.

lgtm!

Sorry, something went wrong.

Uh oh!

There was an error while loading. Please reload this page.

All reactions
@bedevere-bot bedevere-bot added awaiting merge and removed awaiting review labels Jul 29, 2023
@corona10
corona10 merged commit 810d5d8 into python:main Jul 29, 2023
@bedevere-bot bedevere-bot removed the awaiting merge label Jul 29, 2023
@jtcave
jtcave deleted the shelve-clear branch August 2, 2023 23:22
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@corona10 corona10 corona10 approved these changes

Uh oh!

There was an error while loading. Please reload this page.

Assignees

@corona10 corona10

Labels

None yet

Projects

None yet

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.

4 participants

@jtcave @eendebakpt @corona10 @bedevere-bot
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.
You are visitor 01402503 — GeezerVison does not store the pages you look up.
Best viewed with Netscape Navigator 4.7 or Internet Explorer 6 at 800×600. No cookies required.