Почему передача списка (длиной n) в функцию numba nopython является операцией O(n)

Question

Это всего лишь вопрос, чтобы удовлетворить мое любопытство. Я не собираюсь использовать списки в качестве аргументов для функции numba.

Но мне было интересно, почему передача списка в функцию Numba выглядит как O(n) операция, пока это O(1) работа в чисто Python-функциях.

Несколько простых примеров кода:

import numba as nb

@nb.njit
def take_list(lst):
    return None

take_list([1, 2, 3])  # warmup

И сроки:

for size in [10, 100, 1000, 10000, 100000, 1000000]:

    lst = [0]*size
    print(len(lst))
    %timeit take_list(lst)   # IPythons "magic" timeit

Результаты:

10
4.06 µs ± 26.1 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
100
14 µs ± 360 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
1000
109 µs ± 434 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
10000
1.08 ms ± 17.8 µs per loop (mean ± std. dev. of 7 runs, 1000 loops each)
100000
10.7 ms ± 26.2 µs per loop (mean ± std. dev. of 7 runs, 100 loops each)
1000000
112 ms ± 383 µs per loop (mean ± std. dev. of 7 runs, 10 loops each)

Answer 1

Управление списком Python требует вызовов API Python, которые запрещены в режиме nopython. Numba фактически копирует содержимое списка в свою собственную структуру данных, что занимает время, пропорциональное размеру списка.