`os.environ.clear()` has a quadratic time complexity

[gukoff]

Bug report

Bug description:

Problem

Summary

The os.environ.clear() method currently has O(N²) time complexity. This is because it inherits the generic MutableMapping.clear() implementation, which repeatedly calls popitem(). Each popitem() call invokes __iter__(), and for _Environ, __iter__() creates a full snapshot of all environment keys every time. As a result, clearing large environments is extremely slow (e.g., 23 seconds to clear 100,000 variables).

Details

os.environ is an instance of _Environ, which subclasses MutableMapping. _Environ implements the required abstract methods (__getitem__, __setitem__, __delitem__, __iter__, __len__), but inherits generic implementations for methods like clear, pop, popitem, update, and setdefault.

The inherited clear() method is implemented as follows:

class MutableMapping(Mapping):
    ...
    def popitem(self):
        try:
            key = next(iter(self))
        except StopIteration:
            raise KeyError from None
        value = self[key]
        del self[key]
        return key, value

    def clear(self):
        'D.clear() -> None.  Remove all items from D.'
        try:
            while True:
                self.popitem()
        except KeyError:
            pass
    ...

For every item deleted, clear() calls iter(self) inside popitem().

This becomes a performance issue for _Environ because _Environ.__iter__() creates a snapshot of all keys:

class _Environ(MutableMapping):
    ...
    def __iter__(self):
        # list() from dict object is an atomic operation
        keys = list(self._data)
        for key in keys:
            yield self.decodekey(key)

This leads to quadratic time complexity for os.environ.clear().

Performance Impact

This problem is especially evident on large environments.
On my M3 MacBook Pro, it takes 500ms to clear an environment with only 10K variables.
A more extreme example: 100K variables take 23s to clear.

Environments with thousands of variables are rare, but do exist.

In [3]: for i in range(100000):
   ...:     os.environ[str(i)] = str(i)
   ...:

In [4]: %time os.environ.clear()

CPU times: user 23.3 s, sys: 94.3 ms, total: 23.4 s
Wall time: 23.4 s

Suggested solution

Implement a custom _Environ.clear() that avoids repeated snapshots (for every key):

def clear(self):
    while self._data:
        for key in list(self._data):
            try:
                del self[key]
            except KeyError:
                pass

This implementation makes use of the atomicity of list(dict()), which is important in multithreaded environments and is the reason we call list(self._data) inside __iter__(self).

Further improvement on Linux/FreeBSD could be achieved by using clearenv() which is part of the standard C library there.

Other considerations

More generally, we could consider challenging the existing design decisions:

1. Should __iter__ make a snapshot of all environment keys?

• PR introducing this behavior (2017): bpo-30441: Fix bug when modifying os.environ while iterating over it #2409
• Bug report that motivated the change: https://bugs.python.org/issue30441

2. Should MutableMapping.clear() rely on popitem() in a loop, assuming __iter__ is cheap?

CPython versions tested on:

3.12, CPython main branch

Operating systems tested on:

macOS

Linked PRs

• gh-139482: speed up os.environ.clear by 2x #139483
• gh-139482: Improve performance of os.environ.clear() #139549

[gvanrossum]

A PR for _Environ.clear() will be welcome. (Note that taking the list() is useful even without multithreading -- a clever __del__ might mutate the dict.)

I don't want to touch __iter__ without more discussion (involving others), I'm not sure what it is guarding against. Maybe in general iterating over a dict is not safe?

[picnixz]

Environments with thousands of variables are rare, but do exist.

Can you provide some evidence to back that claim? (I can imagine < 10k but I can barely imagine 100k environment variables...)

Should __iter__ make a snapshot of all environment keys?

Yes. We don't want a RuntimeError if the environment is mutated when iterating over it. Without a pre-copy the following code would fail:

x = iter(os.environ)
next(x)
os.environ['hehehe'] = 'hoho'
next(x)  # RuntimeError

It's better to have an outdated copy of the environ rather than have a RuntimeError. The general limitation applies to dict objects where a RuntimeError is actually raised.

[gukoff]

Can you provide some evidence to back that claim? (I can imagine < 10k but I can barely imagine 100k environment variables...)

I agree; I saw thousands of env variables on a complex CI/CD setup, but 100k might be pushing the limit of the OS itself. This is why I call it extreme :)

Should iter make a snapshot of all environment keys?

Yes. We don't want a RuntimeError if the environment is mutated when iterating over it. Without a pre-copy the following code would fail:

What I wanted to point out is that this error could be mitigated in a different way or be treated as expected behavior.
Having said that, the existing solution already looks most reasonable to me.