[New-bugs-announce] [issue31147] a mostly useless check in list_extend()

[Oren Milman]

New submission from Oren Milman:

in listobject.c, in case list_extend() receives an 'iterable' which isn't 'self'
nor a tuple nor a list, we have the following (heavily edited for brevity):
    mn = Py_SIZE(self) + PyObject_LengthHint(iterable);
    list_resize(self, mn);

    ... // self is extended to also include the elements of 'iterable'.

    // (*)
    if (Py_SIZE(self) < self->allocated) {
        list_resize(self, Py_SIZE(self));
    }

IMHO, the condition in (*) is mostly useless, for two reasons:
1. the list_resize() which is called in (*) does nothing in case
   (Py_SIZE(self) >= (self->allocated >> 1)) is true. In particular, this call
   to list_resize() would have done nothing if it had been called while the
   condition in (*) was false.
2. the condition in (*) is false only in the following cases:
    - list_resize(self, mn) caused
      (self->allocated == Py_SIZE(self) + actual_length_of_iterable) to be
      true. e.g.:
          Py_SIZE(self) = 58 and PyObject_LengthHint(iterable) == 8 and
          actual_length_of_iterable == 22
          (because 66 + 66 // 8 + 6 == 80 == 58 + 22).
    - list_resize(self, mn) caused
      (self->allocated < Py_SIZE(self) + actual_length_of_iterable), which
      sometime later caused list_extend() to call app1(), which called
      list_resize(), which caused
      (self->allocated == Py_SIZE(self) + actual_length_of_iterable) to be true.
      e.g.:
          Py_SIZE(self) == 58 and PyObject_LengthHint(iterable) == 8 and
          actual_length_of_iterable == 39
          (because 66 + 66 // 8 + 6 == 80 and
                   81 + 81 // 8 + 6 == 97 == 58 + 39)

   so ISTM that the condition is only rarely false, especially as
   PyObject_LengthHint(iterable) >= actual_length_of_iterable is usually true
   (i guess).


Thus, i believe we should either change the condition in (*) to
(Py_SIZE(self) < (self->allocated >> 1)), or remove it (and always call
list_resize()).


(note that i ignored error cases, as ISTM they are quite irrelevant to the
issue.)

----------
components: Interpreter Core
messages: 299933
nosy: Oren Milman
priority: normal
severity: normal
status: open
title: a mostly useless check in list_extend()
type: performance
versions: Python 3.7

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue31147>
_______________________________________