选用Dynamic SNode实现python list的可行性讨论

第一次参与开源社区,先和大家打个招呼,请多多指教~

我的需求是希望在taichi kernel中维护一个类似于python list的数据容器,我对于这个数据容器的需求主要有以下几点:

  1. 可以存储任意多个元素,我可以随时查询其当前存储了多少个元素
  2. 调用类似remove()的方法从容器中移除指定元素
  3. 调用类似append() pop()方法从队尾添加/移除元素
  4. element in list:检查某个指定元素是否存在于容器中

我个人感觉这个数据容器比较适合用taichi中的Dynamic SNode实现,例:

x = ti.field(ti.i32)
ti.root.dynamic(ti.i, 5).place(x)

@ti.kernel
def make_lists():
    for i in range(1,3):
        ti.append(x.parent(), i, i)
    l = ti.length(x.parent(),0)
    for i in range(ti.length(x.parent(),0)):
        print(x[i])

@ti.kernel
def check_list(element:ti.i32)->ti.i8:
    """需求4 检查某个指定元素是否存在于容器中"""
    flag = 0
    for i in range (ti.length(x.parent(),0)):
        if flag == 1:
            continue
        if x[i] == element:#all(field[i]==element) 
            flag = 1
    return flag
        
make_lists()
print("x=",x)
print("check 2 in list:",check_list(2))
print("check 0 in list:",check_list(0))

但是类似remove(),pop()这样的元素移除似乎现在的taichi还不支持?

#x = [1 2 0 0 0]
ti.deactivate(x,[0])#The deactivate operation is not supported on place SNode
ti.deactivate(x.parent(),[0])#x = [0 0 0 0 0]

想问一下**Dynamic SNode 有没有能够实现remove(),pop()类似功能的方法呢?**或者有没有什么实践建议?

顺带:

  1. 目前我经过一些魔改(…)用dense field实现了上述的所有需求,就是在taichi kernel中多维护一个变量记录该field当前存储了多少个元素。能用,但是很不优雅。python list的底层实现应该是指针链表,感觉上Dynamic SNode应该是比较接近的?

  2. 因为我同时也报名了hackathon,所以如果这个功能还不完善且短期没有实现规划的话或许我想把它当作选题(?能做到吗(其实本来我的选题是应用方向的来着))希望社区同学可以给一些入手建议(?

十分感谢~

3 Likes

欢迎来到社区~

Dynamic SNode 有没有能够实现remove(),pop()类似功能的方法呢?

目前 Dynamic SNode 支持只支持 append 功能。remove/pop 还不支持。主要的难点在于 GPU 上并行地 pop 需要涉及 data-race、memory recycling 等等操作,一个系统性的支持需要一些功夫和对系统的深入理解。关于 Taichi 的动态内存分配,请看这篇文档:taichi/llvm_sparse_runtime.md at master · taichi-dev/taichi · GitHub

  1. 目前我经过一些魔改(…)用dense field实现了上述的所有需求,就是在taichi kernel中多维护一个变量记录该field当前存储了多少个元素。能用,但是很不优雅。python list的底层实现应该是指针链表,感觉上Dynamic SNode应该是比较接近的?

Dynamic SNode 确实是最合适的,至少他提供了一个可以无限延长的数组。

  1. 因为我同时也报名了hackathon,所以如果这个功能还不完善且短期没有实现规划的话或许我想把它当作选题(?能做到吗(其实本来我的选题是应用方向的来着))希望社区同学可以给一些入手建议(?

坦率地说,其实要改这个还是挺难的,需要懂一些 LLVM、Taichi 中间表示(可以看看这里:https://yuanming.taichi.graphics/publication/2020-life-of-kernel/life_of_a_taichi_kernel.pdf)。

本质上这个问题在 CPU 上很容易实现。但是在 GPU 上,如果语言层面提供 first-class 的这样的数据结构,要考虑的问题就很多了:

  1. 性能
  2. 并行安全性
  3. 内存分配与回收

如果还是对做这个容器有兴趣,可以接着在这个帖子里面讨论;如果打算做应用方向了,那我觉得也很棒~

2 Likes

哇!非常荣幸得到渊鸣大佬的回复!
感谢指路,我研究一下Dynamic SNode的内部实现,然后决定选题。
十分感谢!

很期待大佬对这个功能的实现,能有list可以用那还是很爽的 :grin: