Почему len (<a list object>) так медленно?

Я выполняю следующий код в сеансе ipython:

# This call is slow, but that is expected. (It loads 3 GB of data.)
In [3]: arc, arc_sub, upls, go = foo_mod.ready_set()

# This call is also slow, as `upls` is huge.
In [4]: upls = list(upls)

# This call is slow in meatspace, but `%timeit` doesn't notice!
In [5]: %timeit -n1 -r1 len(upls)
1 loops, best of 1: 954 ns per loop

%timeit прямо лежит здесь. С помощью %timeit или без него команда занимает больше 10 секунд для фактического запуска. Однако только в первый раз; последующие вызовы len бывают быстрыми.

Даже time.time() поет подобную мелодию:

In [5]: import time

In [6]: s = time.time(); len_ = len(upls); e = time.time()

In [7]: e - s
Out[7]: 7.104873657226562e-05

Но в реальном мире потребовалось несколько секунд для In [6], чтобы закончить. Кажется, я просто не могу зафиксировать, где расходуется фактическое время!

В этом списке нет ничего необычного, кроме огромного: это настоящий list; он содержит ~ ¼ миллиарда bson.ObjectId объектов. (До вызова list() это объект set, этот вызов также медленный, но это имеет смысл: list(<set instance>) - это O (n), и мой набор огромен.)

Изменить re GC

Если я запустил gc.set_debug(gc.DEBUG_STATS) непосредственно перед ready_set, который сам является медленным вызовом, я вижу тонны циклов GC. Это ожидается. gen3 растет:

gc: objects in each generation: 702 701 3289802
gc: done, 0.0000s elapsed.
gc: collecting generation 0...
gc: objects in each generation: 702 1402 3289802
gc: done, 0.0000s elapsed.
gc: collecting generation 0...
gc: objects in each generation: 702 2103 3289802

К сожалению, консольные выходы делают это время выполнения этого невероятно медленным. Если я вместо этого задержу вызов gc.set_debug до тех пор, пока после ready_set, я не вижу никаких циклов GC, но gc.get_count() утверждает, что поколение крошечное:

In [6]: gc.get_count()
Out[6]: (43, 1, 193)

In [7]: len(upls)
Out[7]: 125636395

(но почему/как get_count меньше объектов, чем в списке?), они определенно уникальны, поскольку они просто прошли через set...). Тот факт, что включение gc в код делает len speedy заставляет меня поверить, что я остановился на собрании мира.

(Версии, на всякий случай:

Python 2.7.6 (default, Mar 22 2014, 22:59:56)
IPython 3.2.0 -- An enhanced Interactive Python.

)

Ответ 1

Я обобщу комментарии к вашему вопросу на ответ.

Как сказали все (и вы указали это), объект Python list знает свой размер, а возвращает только сохраненное число:

static Py_ssize_t
list_length(PyListObject *a)
{
    return Py_SIZE(a);
}

Где Py_SIZE определено:

Py_SIZE (о)

Этот макрос используется для доступа к объекту ob_size объекта Python. Он расширяется до: (((PyVarObject*)(o))->ob_size)

Поэтому я могу заключить, что он не должен делать никаких расчетов. Единственный подозреваемый - это объект, который вы пытаетесь преобразовать в список. Но если вы клянетесь, это действительно list без каких-либо поддельных объектов, имитирующих его метод с помощью ленивых вычислений - это не он.

Поэтому я предполагаю, что все методы timeit действительно показывают точное время, затраченное на вызов функции len.

И единственный процесс траты времени - это Сборщик мусора. В конце ваших измерений он обнаруживает, что никто не использует такую большую часть данных и начинает освобождать память. Конечно, требуется несколько секунд.