Struct for和range for的性能比较

根据文档中的描述,struct for会遍历稀疏矩阵中的active元素,而range for会遍历所有元素,所以我期待用这两个不同的循环实现Jacobian迭代时,struct for会比range for要快一些,结果却是相反的。。
代码请移步这里查看
代码中用struct for和range for实现了一个同样的Jacobian求解器:

# 这个用了range for
@ti.kernel
def full_jacobian()->ti.f64:
    ...

# 这个用了struct for
@ti.kernel
def full_jacobian_sparse()->ti.f64:
    ...

测试下来在我的机器上,对于一个同样的50 x 50的稀疏矩阵,struct for的版本要比range for慢将近5倍(调大矩阵规模好像结论也是不变的)。另外range for在稀疏矩阵上比稠密矩阵要快一点,虽然理论上都是遍历所有元素的,不太理解是为什么。
总结一下就是(越大表示耗时越长):
struct for on sparse matrix >> range for on dense matrix > range for on sparse matrix
问题丛生啊 。。。

我理解 struct for 的遍历过程是在 SNodes 的结构上自上向下搜索,直到遇到叶子节点(例如 ti.f32, ti.i32)或是 pointer 节点不为 active 状态(此时里面存的应该是个 nullptr?)。
只用一层 pointer 其实是在浪费时间与空间资源,dense 节点的每个元素就是一个值,而 pointer 节点的每个元素是指向某个值或者某个数据结构的指针,如果直接将 pointer 作为最底层的话意味着需要在访问每个元素时多进行一次随机寻址,且需要在内存中存储一个值与对应的指针(内存消耗会增加一到两倍)。
推荐看一看 GAMES201 Lecture09, Taichi的文档或是 ti example -s taichi_sparse

2 Likes

很感谢指点!试了一下3层pointer,果然立刻struct for比range for快了几十倍上百倍!准备去认真学习一下lecture 9了!

struct for on sparse matrix >> range for on dense matrix > range for on sparse matrix
问题丛生啊 。。

Taichi 的稀疏性能有时确实不如稠密,然而这个案例中主要是你使用方法的问题…

n = 50

A = ti.field(dtype=ti.f64)
ti.root.pointer(ti.ij, (n, n)).place(A)  # 错误的用法,pointer应当被嵌套

x = ti.field(dtype=ti.f64)
b = ti.field(dtype=ti.f64)
r = ti.field(dtype=ti.f64)
x_new = ti.field(dtype=ti.f64)
ti.root.pointer(ti.i, n).place(x, b, x_new,r)  # 错误的用法,x完全不必是稀疏的,只需要A稀疏即可

正确的使用方法是:

n = 128  # n尽量为2的整数幂

A = ti.field(dtype=ti.f64)
ti.root.pointer(ti.ij, (n // 8, n // 8)).pointer(ti.ij, (8, 8)).place(A)  # 8x8个元素一组,两层稀疏结构。一层就和稠密没什么区别了
 
x = ti.field(dtype=ti.f64)
b = ti.field(dtype=ti.f64)
r = ti.field(dtype=ti.f64)
x_new = ti.field(dtype=ti.f64)
ti.root.dense(ti.i, n).place(x, b, x_new, r)  # x稠密即可,反正都要被写入

然后把下面每循环一次的print去掉,在我的电脑上就得到:

Full Jacobian iteration took  3.334108829498291 sec and  20437 steps.
Sparse Jacobian iteration took  1.7451798915863037 sec and  20437 steps.
1 Like

真的很感谢帮忙修改和测试 :innocent:!我去看了一下Lecture 9高性能运算,可能是我自己前置知识不够,感觉至少还有以下两个问题:

  1. pointer, bitmasked和hash这几个该如何选择?
  2. pointer嵌套多少层,每层多大,有什么指导性原则吗?

谢谢!

bitmasked不节省内存,但访问时不需要两层指针,小规模时效率更高
pointer能节省内存,但访问需要两层指针,效率更低,此外deactivate节点时还会自动清零
hash更加节省内存,但计算元素地址更复杂,而且现在taichi.py似乎还没有实现hash
dynamic是一维可扩展线性数组,当第n个元素被激活时,前n-1个也会被激活

应用场景取决于你场景的稀疏程度:
hash>pointer>bitmasked>dense
hash和pointer适合空间中只有很小部分有物质的情况,bitmasked和dense适合空间中有较多物质的情况

通常对于mpm这种模拟固体流体场的程序会ti.root.pointer.bitmasked这样布局,大尺度上稀疏,但小尺度上还是聚拢的情况
如果你的场在大小尺度上都比较稀疏,那可以采用pointer.pointer
也有pointer.dense的用法,通常这个dense的大小和cacheline一个数量级,这样可以让每个pointer内的数据尽量集中,减少cache miss

1 Like