Я пытаюсь реализовать кеш 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?
Дополнительные примечания:
Я заметил аналогичную проблему здесь: Сравнение объектов в numba jitclass. Я могу смягчить ту же проблему с помощью моего недавно добавленного атрибута key
. Я только пытаюсь понять, почему это происходит.
Это не баг, а артефакт внутренней работы 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, поэтому здесь он не очень полезен.
Это действительно возможное объяснение. Поскольку это связано с оптимизацией, такое поведение является хрупким: оно может меняться от одной платформы к другой. Особенно если версия CPython другая. Такие инструменты, как трассировка, должны помочь более точно отслеживать происходящее в таком случае. Вы также можете проверить элементы в globals()
и locals()
. Модуль gc
также содержит несколько полезных функций для закрепления объектов.
Обратите внимание, что если CPython Jupyter изменен/настроен таким образом, что он создает еще 1 временное выделение, в некоторых случаях распределитель может не использовать повторно напрямую адреса. Цикл может быть значительно больше, хотя я ожидаю, что адрес CPython будет повторно использовать их для временного объекта, если только Jupyter не отслеживает некоторые объекты (объекты не будут освобождены, если на них есть ссылка, что может быть возможно из-за функций отладки Jupyter).
Спасибо. Это многое объясняет. У вас есть идеи, почему этого не происходит при выполнении в Jupyter? Я подозреваю, что Jupyter не изменит низкоуровневое поведение CPython в отношении того, как перерабатываются адреса, поэтому я предполагаю, что это, вероятно, потому, что Jupyter создает дополнительные ссылки на объекты, поэтому адреса нельзя использовать повторно, верно?