arrays - 如何在 Haskell 中滚动快速 BVH 表示

Question

我正在使用 Haskell Raytracer，目前使用 BVH 实现，它强调一个幼稚的二叉树来存储层次结构，

data TreeBvh
   = Node Dimension TreeBvh TreeBvh AABB
   | Leaf AnyPrim AABB

其中 Dimension 是 X , Y或 Z (用于更快的遍历)和 AABB 是我的轴对齐边界框类型。这工作得相当好，但我真的很想尽可能快地做到这一点。所以我的下一步(当使用 C/C++ 时)将使用这棵树来构造一个扁平表示，其中节点存储在一个数组中，“左”子节点立即跟随它的父节点和父节点的右子节点的索引与 parent 一起存储，所以我有这样的事情:

data LinearNode
   = LinearNode Dimension Int AABB
   | LinearLeaf AnyPrim AABB

data LinearBvh
   = MkLinearBvh (Array Int LinearNode)

我还没有真正尝试过这个，但我担心性能仍然会低于标准，因为我无法存储 LinearNode UArray 中的实例，我也不能存储 Int将右 child 与 Float 一起索引在单个 UArray 中构成 AABB 的值(如果我弄错了，请纠正我)。并且使用两个数组意味着糟糕的缓存一致性。所以我基本上是在寻找一种有效存储我的树的方法，这样我就可以期待良好的遍历性能。应该是

紧凑型

具有良好的位置属性

使用最新的 GHC 编译器

应该通过尽可能少的间接(尽管“thunk”不能帮助提高性能，所以我认为“未装箱”类型会有所帮助)

Answer 1

如果我理解正确，您想要用户定义类型的未装箱数组？如果是这样，请查看 vector package它还支持循环融合。值得一试slides for High-Performance Haskell