C # - фиксированные / встроенные массивы

Question

Я пишу реализацию дерева B + в C #, и реализация дерева, которую я выбрал для своего приложения, имеет очень специфическую структуру, которая учитывает кеширование.Для достижения этих свойств у него есть строгие политики компоновки на узлах дерева.

То, что я хочу, просто выражается с помощью ключевого слова C # fixed для буферов фиксированного размера:

public abstract class Tree<K, T> { }
sealed class Node<K, T> : Tree<K, T>
{
    Node<K, T> right;
    fixed Tree<K, T> nodes[127]; // inline array of 128 nodes
}

К сожалению, буферы фиксированного размера могут использоваться только с примитивными типами значений, такими как int и float.Простое использование простых массивов добавит косвенные указатели, которые разрушат кеш-свойства этого типа дерева.

Я также не могу сгенерировать 128 полей и использовать арифметику указателей для извлечения нужного поля, потому что естьнет преобразований между типами указателей и управляемыми объектами .

Осталось только генерировать 128 полей с индексатором, который выбирает правильное на основе переключателя (который не может быть быстрым), или записыватьэто как библиотека C и использование P / Invoke, что также может снизить производительность.

Есть предложения?

Answer 1

Используйте C ++ / CLI.Это дает вам полный контроль над макетом, как и в случае с C, но стоимость управляемых / неуправляемых переходов значительно снижается по сравнению с p / invoke (возможно, без дополнительных затрат).

К сожалению, управляемый код не очень хорош дляработа с «кэшированием»: внутри управляемой кучи вы бессильны избежать ложного обмена.C ++ / CLI позволяет вам использовать неуправляемый распределитель, так что вы можете не только поддерживать непрерывность данных, но и выравнивать их по строкам кэша.

---

Также обратите внимание: использование ключевого слова class создает «ссылочный тип»который уже добавляет тот уровень косвенности, которого вы хотели избежать.При некоторой реорганизации вы можете использовать struct и массив и не иметь больше косвенного обращения, чем предложенный вами код.