Странная проблема с адресом со связанным списком, реализованным numba jitclass

Я пытаюсь реализовать кеш LRU с двусвязным списком и хэш-картой. Двусвязный список довольно просто реализовать, следуя официальному примеру с использованием jitclass. Однако какая-то ошибка в баге заставила меня проверить логику в реализации связанного списка. В конце концов, я могу воспроизвести проблему на следующем минимальном примере:

from numba import int32, deferred_type, optional
from numba.experimental import jitclass

node_type = deferred_type()


@jitclass([
    ('key', int32),
    ('value', int32),
    ('next', optional(node_type))
])
class LinkedNode:
    def __init__(self, key, value, next):
        self.key = key
        self.value = value
        self.next = next
        
node_type.define(LinkedNode.class_type.instance_type)

def print_node(node):
    print(hex(id(node)), f'node({node.key}, {node.value})')

def foo():
    head = LinkedNode(-1, -1, None)
    curr = head
    for i in range(10):
        new_node = LinkedNode(i, i, None)
        curr.next = new_node
        curr = new_node
    node = head
    for i in range(10):
        node = node.next
        print_node(node)

foo()

Если вы сохраните его в файле .py и запустите из терминала, вы получите какой-то странный результат, например следующий:

$ python minimal_example.py
0x191a8ac7760 node(0, 0)
0x191a8ac76d0 node(1, 1)
0x191a8ac7760 node(2, 2)
0x191a8ac76d0 node(3, 3)
0x191a8ac7760 node(4, 4)
0x191a8ac76d0 node(5, 5)
0x191a8ac7760 node(6, 6)
0x191a8ac76d0 node(7, 7)
0x191a8ac7760 node(8, 8)
0x191a8ac76d0 node(9, 9)

В основном определяется головной узел, затем последовательно подключаются еще 10 узлов. Но проверка адреса с помощью id показывает, что уникальных объектов всего 2. И содержимое узлов выглядит правильно.

Мой вопрос: почему это происходит? Это из-за какой-то внутренней реализации jitclass numba или CPython?

Дополнительные примечания:

  • Если вы закомментируете часть jit, код будет работать так, как ожидалось: каждый узел имеет разные адреса.
  • Еще более запутанно, если вы скопируете тот же код в блокнот Jupyter, результат будет правильным.

Я заметил аналогичную проблему здесь: Сравнение объектов в numba jitclass. Я могу смягчить ту же проблему с помощью моего недавно добавленного атрибута key. Я только пытаюсь понять, почему это происходит.

Почему в Python есть оператор "pass"?
Почему в Python есть оператор "pass"?
Оператор pass в Python - это простая концепция, которую могут быстро освоить даже новички без опыта программирования.
Некоторые методы, о которых вы не знали, что они существуют в Python
Некоторые методы, о которых вы не знали, что они существуют в Python
Python - самый известный и самый простой в изучении язык в наши дни. Имея широкий спектр применения в области машинного обучения, Data Science,...
Основы Python Часть I
Основы Python Часть I
Вы когда-нибудь задумывались, почему в программах на Python вы видите приведенный ниже код?
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
LeetCode - 1579. Удаление максимального числа ребер для сохранения полной проходимости графа
Алиса и Боб имеют неориентированный граф из n узлов и трех типов ребер:
Оптимизация кода с помощью тернарного оператора Python
Оптимизация кода с помощью тернарного оператора Python
И последнее, что мы хотели бы показать вам, прежде чем двигаться дальше, это
Советы по эффективной веб-разработке с помощью Python
Советы по эффективной веб-разработке с помощью Python
Как веб-разработчик, Python может стать мощным инструментом для создания эффективных и масштабируемых веб-приложений.
1
0
22
1
Перейти к ответу Данный вопрос помечен как решенный

Ответы 1

Ответ принят как подходящий

Это не баг, а артефакт внутренней работы Numba. Действительно, id дает вам адрес Объект Python, но Numba работает не с объектом Python внутри, а со своими собственными типами C. Объекты Python — это просто типы обертка, поэтому их можно использовать из кода Python. Ваш цикл создает новый временные объекты Python для каждой итерации. Нужны только два объекта Python: node и node.next. Предыдущие объекты удаляются из-за подсчета ссылок. Распределитель CPython перерабатывать адреса, потому что повторное использование адресов в целом более эффективно (из-за локальности кеша). Новые объекты отличаются и ссылаются на другой адрес объекта Numba внутри, но адрес тот же. Подобный эффект часто возникает в C/C++, когда объекты создаются в стеке. Этого не происходит с чистым кодом Python, потому что Python работает с постоянными объектами, а не с оболочками. Обратите внимание, что создание временных объектов и вызовы JIT-функций для каждой итерации не очень эффективны, и поэтому я ожидаю, что код не будет намного быстрее с Numba. Кстати, эффект исчез бы, если бы foo была функцией njit.

Короче говоря, id(node) работает не так, как вы думаете. Он работает с объектами-оболочками Numba, поэтому здесь он не очень полезен.

Спасибо. Это многое объясняет. У вас есть идеи, почему этого не происходит при выполнении в Jupyter? Я подозреваю, что Jupyter не изменит низкоуровневое поведение CPython в отношении того, как перерабатываются адреса, поэтому я предполагаю, что это, вероятно, потому, что Jupyter создает дополнительные ссылки на объекты, поэтому адреса нельзя использовать повторно, верно?

seekiu 08.05.2022 04:06

Это действительно возможное объяснение. Поскольку это связано с оптимизацией, такое поведение является хрупким: оно может меняться от одной платформы к другой. Особенно если версия CPython другая. Такие инструменты, как трассировка, должны помочь более точно отслеживать происходящее в таком случае. Вы также можете проверить элементы в globals() и locals(). Модуль gc также содержит несколько полезных функций для закрепления объектов.

Jérôme Richard 08.05.2022 11:06

Обратите внимание, что если CPython Jupyter изменен/настроен таким образом, что он создает еще 1 временное выделение, в некоторых случаях распределитель может не использовать повторно напрямую адреса. Цикл может быть значительно больше, хотя я ожидаю, что адрес CPython будет повторно использовать их для временного объекта, если только Jupyter не отслеживает некоторые объекты (объекты не будут освобождены, если на них есть ссылка, что может быть возможно из-за функций отладки Jupyter).

Jérôme Richard 08.05.2022 11:11

Другие вопросы по теме