Как бросить быстрое представление BVH в Haskell

Question

Я играю с Haskell Raytracer и в настоящее время использую реализацию BVH, которая подчеркивает наивное двоичное дерево для хранения иерархии,

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

, где Размер равен либо X, Y или Z (используется для более быстрого обхода), а AABB - мой тип для ограничивающего прямоугольника с выравниванием по оси. Это работает достаточно хорошо, но я бы очень хотел получить это как можно быстрее. Таким образом, мой следующий шаг (при использовании C / C ++) будет состоять в том, чтобы использовать это дерево для построения плоского представления, в котором узлы хранятся в массиве, «левый» дочерний элемент следует непосредственно за его родительским узлом и индексом правого дочернего элемента родительского элемента. хранится вместе с родителем, поэтому у меня есть что-то вроде этого:

data LinearNode
   = LinearNode Dimension Int AABB
   | LinearLeaf AnyPrim AABB

data LinearBvh
   = MkLinearBvh (Array Int LinearNode)

Я еще не пробовал этот вариант, но боюсь, что производительность все равно будет ниже, потому что я не могу хранить LinearNode экземпляров в UArray, и при этом я не могу сохранить Int, индексируя нужные child вместе со значениями Float, которые составляют AABB в одном UArray (поправьте меня, если я ошибся). А использование двух массивов означало бы плохую когерентность кэша. Поэтому я в основном ищу способ эффективного хранения своего дерева, чтобы можно было ожидать хорошей производительности для обхода. Это должно быть

• компактный
• имеют хорошие свойства местности
• работа с последними компиляторами GHC
• должно проходить как можно меньше косвенных указаний (хотя «thunk» не может помочь производительности, поэтому я думаю, что «unboxed» типы могут помочь)

Answer 1

Если я вас правильно понял, вы хотите распакованные массивы пользовательских типов? если это так, проверьте векторный пакет , который также поддерживает объединение циклов. Стоит проверить слайды для высокопроизводительного Haskell

Answer 2

Я действительно должен отметить, что Haskell не очень хорош в предоставлении программисту возможности выбора размещения данных в памяти.

Возможно, вас заинтересует хранение дерева в плоском массиве без учета кэша («дерево Ван Эмде Боаса»). Это должно работать, но кто знает. :)

(бесстыдный плагин: некоторое время назад я предпринял аналогичные усилия; я использовал некоторые расширенные функции системы типов языка программирования ATS, чтобы сделать raytracer одновременно более безопасным и быстрым; см. Код здесь: http://code.google.com/p/ats-miscellanea/ - я, к сожалению, пока не очень далеко)

Answer 3

То, что вы предлагаете, было открыто много лет назад, оно называется иерархией ограничивающих интервалов (BIH).