关于稀疏数据结构的效率问题

综合讨论区
#1

弱弱地问问大佬们，请问taichi有没有计划对稀疏数据结构的效率做进一步的改进呀，目前发现taichi对动态列表的支持比较弱，比如下面这段利用pointer和bitmasked要比dense多花20倍的时间

import taichi as ti
import time
ti.init()
a = ti.field(float)
b = ti.field(float)
ti.root.pointer(ti.i, 1000000).place(a)
ti.root.dense(ti.i, 1000000).place(b)

@ti.kernel
def k(x: ti.template()):
    for i in x:
        x[i] = i

k(a)
k(b)
start = time.time()
k(a)
end1 = time.time()
k(b)
end2 = time.time()
print(end1-start, end2-end1)
#2

Hi @Otis. 感谢反馈！持续优化性能肯定一直在 Taichi 的 roadmap 中。

有关这段代码，不知道你有没有试过在 GPU 上跑，运行时间差距如何？

#3

我在gpu上跑，时间大概差一半左右，pointer会比dense慢一倍

#4

Hi @Otis. 你这段代码测的东西有一点小问题~
在 Taichi 中，for i in x 只会访问 x 中被激活的元素。因此，你调用 k(a) 时实际上没有进行任何访问。也就是说，你这里比较的是调用 k(a) 时产生的针对稀疏数据结构的额外开销，以及 k(b) 的访问时间。如果你把这段代码稍微改一下：

@ti.kernel
def k(x: ti.template()):
    for i in x:
        for j in range(10000):
            x[i] = i

你会发现 k(b) 的时间明显变长了，而 k(a) 依然不变。

如果希望进行公平的比较，可以把 a 预先激活：

@ti.kernel
def init():
    for i in range(1000000):
        a[i] = i

然后再跑你的测试程序。这样在我的机器上得到的结果大约是 4 倍性能差距。

#5

多谢解答