(See bpo-33234)

Recently we added Python 3.8 to our CI test matrix, and we noticed a possible backward incompatibility with the list() constructor.

We found that __len__ is getting called twice, while before 3.8 it was only called once.

Here's an example:

class Foo:
 def __iter__(self):
  print("iter")
  return iter([3, 5, 42, 69])

 def __len__(self):
  print("len")
  return 4

Calling list(Foo()) using Python 3.7 prints:

iter
len

But calling list(Foo()) using Python 3.8 prints:

len
iter
len

It looks like this behaviour was introduced for bpo-33234 with PR #54055.

We realize that this was merged a while back, but at least we wanted to make the team aware of this change in behaviour.

Why should that be backwards incompatible? The number of times we can __len__ on the constructor is an implementation detail. The reason is called now twice is because there is an extra check for the preallocation logic, which is detached from the logic of the subsequent list_extend(self, iterable).

On the other hand, there may be a chance for optimization here, but on a very rough first plan, that may require coupling some logic (passing down the calculated length to list_extend() or some helper, which I am not very fond of.

The only specification is that len(ob) calls ob.__len__ and that ob.__len__ should return an 'integer >= 0'. (Adding side effects goes beyond that spec.) I agree that a detectable internal in list is not a bug. Unless there is a realistic performance enhancement in caching the result of the first call, this issue should be closed.

FWIW, I encouraged Kim to file this. Thanks Kim!

While it isn't part of any specification, it is an unexpected change in behavior that led to some test failures. So I figured it would be worth bringing up. :) I did find it surprising that we were not caching the result, but don't think that's necessarily a problem.

All that said, the change did not actually break anything other than some tests (not the code they were testing). So I don't have a problem with closing this.

Thanks Kim and Eric!

I think it still makes sense to do some quick benchmarking and research on passing down the calculated length. I can try to produce a draft PR so we can discuss with something more tangible.

I'm not opposed. :) I just don't want to impose on your time.

Pardon me for necroing an old issue, but someone pointed out the surprising behavior of __len__ being called twice by list(iterable), and it caught my curiosity.

372d705 made it so that list.__init__(iterable) calls iterable.__len__() before calling list.extend(), to preallocate exactly the right amount of space, rather than allowing list.extend() to grow the array. That's because list.extend() can over-allocate.

What if instead, we made it so that list.extend(iterable) doesn't over-allocate when called on an empty list? In the two places where list_extend calls list_resize to grow the array, we'd check if self->ob_item == NULL and if so call list_preallocate_exact instead, and we'd remove the call to list_preallocate_exact from list___init___impl.

It seems like that ought to achieve the same goal as making __init__ call preallocate exactly, without requiring the extra call to __len__.

Related to Matt's idea is https://bugs.python.org/issue43574

Matt's idea leads to some speedups when implemented correctly (pardon me but I have no idea how to use pyperf):

list({}): Mean +- std dev: [orig] 109 ns +- 1 ns -> [modif] 103 ns +- 1 ns: 1.06x faster
list({1: 2}): Mean +- std dev: [orig] 125 ns +- 1 ns -> [modif] 118 ns +- 1 ns: 1.05x faster
list({(1, 2, 3): 4}): Mean +- std dev: [orig] 125 ns +- 1 ns -> [modif] 118 ns +- 1 ns: 1.05x faster
list((3, 3, 4)): Mean +- std dev: [orig] 89.2 ns +- 4.5 ns -> [modif] 82.9 ns +- 4.6 ns: 1.08x faster
list(()): Mean +- std dev: [orig] 70.1 ns +- 0.8 ns -> [modif] 65.5 ns +- 0.8 ns: 1.07x faster
list({0, 1, 2, ...}): Mean +- std dev: [orig] 74.7 us +- 3.6 us -> [modif] 67.6 us +- 1.6 us: 1.11x faster
list({9, 3}): Mean +- std dev: [orig] 131 ns +- 2 ns -> [modif] 126 ns +- 4 ns: 1.04x faster
list(set()): Mean +- std dev: [orig] 115 ns +- 6 ns -> [modif] 110 ns +- 2 ns: 1.05x faster
list([]): Mean +- std dev: [orig] 73.2 ns +- 5.5 ns -> [modif] 67.8 ns +- 3.4 ns: 1.08x faster
list([1, 2, 1, 1]): Mean +- std dev: [orig] 93.5 ns +- 9.8 ns -> [modif] 87.9 ns +- 8.6 ns: 1.06x faster
list([1, 2, 1, 2, 1, 2]): Mean +- std dev: [orig] 93.0 ns +- 3.1 ns -> [modif] 87.0 ns +- 2.7 ns: 1.07x faster

Benchmark hidden because not significant (3): list({0: 0, 1: ...}), list((4, 5, 1, ...)), list([4, 1, 3, ...])

Geometric mean: 1.05x faster

Changes compared here: main...thatbirdguythatuknownot:patch-17

Changes compared here: main...thatbirdguythatuknownot:patch-17

Looks good to me. Would you create a pull request?

Looks good to me. Would you create a pull request?

Created a pull request (31816).

New changeset 2153daf by Crowthebird in branch 'main':
bpo-39829: Fix __len__() is called twice in list() constructor (GH-31816)
2153daf

Thanks.