numba jitclass 实现的链接列表的奇怪地址问题

Question

我正在尝试使用双向链表和哈希映射实现 LRU 缓存。双向链表很简单，按照官方的例子使用jitclass来实现。但是，bug中的一些bug让我检查了链表实现中的逻辑。最后，我能够通过以下最小示例重现该问题：

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 个唯一对象。并且节点的内容看起来是正确的。

我的问题是：为什么会这样？是因为 numba 的 jitclass 或 CPython 的一些内部实现吗？

补充说明：

如果注释掉 jit 部分，代码运行s 符合预期：每个节点都有不同的地址。
更令人困惑的是，如果您在 Jupyter notebook 中复制相同的代码，结果是正确的。

我在这里注意到一个类似的问题：。我可以使用新添加的 key 属性来缓解同样的问题。我只是想了解为什么会这样。

Answer 1

这不是错误，而是 Numba 内部工作方式的产物。实际上，id 为您提供了 Python 对象 的地址，但 Numba 不会在内部对 Python 对象进行操作，而是对它自己的 C 类型进行操作。 Python 对象只是 wrapper 类型，因此可以从 Python 代码中使用。您的循环为每次迭代创建新的 临时 Python 对象。只需要两个 Python 个对象：node 和 node.next。由于引用计数，先前的对象被删除。 CPython 的分配器回收地址 因为重用地址通常更有效（由于缓存局部性）。新对象不同，在内部引用不同的 Numba 对象地址，但地址相同。当在堆栈上创建对象时，类似的效果经常发生在 C/C++ 中。 pure-Python 代码不会发生这种情况，因为 Python 对持久对象而不是包装器进行操作。请注意，为每次迭代创建临时对象和 JIT 函数调用效率不高，因此我预计使用 Numba 时代码不会快很多。顺便说一下，如果 foo 是一个 njit 函数，效果就会消失。

简而言之，id(node) 并不像您想象的那样有效。它在包装器 Numba 对象上运行，因此在这里不是很有用。

numba jitclass 实现的链接列表的奇怪地址问题

Weird address issue with linked list implemented by numba jitclass

python

numba