ChainMap.__contains__ and .get performance improvement.

[dg-pb]

Feature or enhancement

Proposal:

import collections as coll


class ChainMap2(coll.ChainMap):
    def __contains__(self, key):
        for mapping in self.maps:
            if key in mapping:
                return True
        return False

    def get(self, key, default=None):
        for mapping in self.maps:
            if key in mapping:
                return mapping[key]
        return default


maps = [dict(a=1), dict(a=2, b=2), dict(a=3, b=2, c=3)]
cm = coll.ChainMap(*maps)
cm2 = ChainMap2(*maps)


%timeit 'a' in cm               # 615 ns
%timeit 'c' in cm               # 752 ns
%timeit cm.get('a')             # 776 ns
%timeit cm.get('c')             # 1.46 µs

%timeit 'a' in cm2              # 140 ns
%timeit 'c' in cm2              # 198 ns
%timeit cm2.get('a')            # 147 ns
%timeit cm2.get('c')            # 208 ns

Has this already been discussed elsewhere?

I have already discussed this feature proposal on Discourse

Links to previous discussion of this feature:

https://discuss.python.org/t/collections-chainmap-get-performance/41925

Linked PRs

• gh-118932: ChainMap.__contains__ performance improvement #118946

[pochmann3]

I'm curious: how long does cm2['c'] take?

[dg-pb]

621 ns
Can't think of a way to improve it as it needs to be sensitive to __missing__ implementations.

[rhettinger]

The change to __contains__ is a good idea. It's a bummer that any() with a generator expression does not perform well.

The get method should be left as-is. The edit alters the semantics so that a override of __contains__ in a ChainMap subclass would be bypassed.

[dg-pb]

Makes sense, can't think of any way to keep that and not to iterate twice.

At least updating __contains__ will boost performance of get too.

Should I issue PR or leave it to you?

[nineteendo]

How much slower is this? https://stackoverflow.com/a/44803103

any(True for m in self.maps if key in m)

[dg-pb]

How much slower is this? https://stackoverflow.com/a/44803103

any(True for m in self.maps if key in m)

Slightly faster than the original:

 %timeit 'a' in cm2    # 589 ns
%timeit 'c' in cm2   # 671 ns

[nineteendo]

... but slower than an actual for loop.

[dg-pb]

%timeit any(map(opr.call, map(opr.attrgetter(' __contains__'), cm2.maps), itl.cycle([key])))
%timeit any(map(opr.methodcaller('__contains__', key), cm2.maps))

786 ns & 500 ns

[pochmann3]

any(map(opr.call, map(opr.attrgetter(' __contains__'), cm2.maps), itl.cycle([key])))

Looks like a complicated version of:

any(map(opr.contains, cm2.maps, itl.repeat(key)))

[dg-pb]

Looks like a complicated version of:

any(map(opr.contains, cm2.maps, itl.repeat(key)))

Which is the best I have seen without loop:
In [16]: %timeit 'a' in cm2 # 360 ns
In [17]: %timeit 'c' in cm2 # 424 ns