Change dict.popitem to pop the last element instead of first

[stepancheg]

dict.popitem now removes the first element. spec

There are three reasons to change it

Consistency with list

list.pop removes the last element.

Consistency with Python

Python 3.12.6 (main, Sep  6 2024, 19:03:47) [Clang 15.0.0 (clang-1500.3.9.4)] on darwin
Type "help", "copyright", "credits" or "license" for more information.
>>> d = {3: 3, 1: 1, 4: 4, 2: 2}
>>> d.popitem()
(2, 2)
>>> d
{3: 3, 1: 1, 4: 4}

Performance

If dict is implemented using linked list, it is fine. But linked-list is suboptimal for both time and space.

If the dict is implemented using an array (like starlark-rust does):

struct Dict {
  // Entries in order.
  entries: Vec<(K, V)>,
  // The value is the index.
  index: Hashtable<usize>,
}

popitem is O(N).

Changing it to pop the last element makes this operation efficient.

Migration

This is backwards incompatible change.

• In the specification we mention old and new behavior
• Bazel's implementation may switch it on the next major version bump
• Go implementation may have an option

[tetromino]

In principle, I agree with the proposal.

The problem for Bazel though is that Java's LinkedHashMap only allows O(1) popping of oldest entries. So we'd need an alternative implementation which would need to be benchmarked (no memory/cpu regressions since dict is extremely widely used).

[fmeum]

The problem for Bazel though is that Java's LinkedHashMap only allows O(1) popping of oldest entries.

This should no longer be a blocker with Java 21: https://docs.oracle.com/en/java/javase/21/docs/api/java.base/java/util/SequencedMap.html#pollLastEntry()