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

[stepancheg]

trafficstars

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