Структурировать взлом памяти для перекрытия ссылки на объект - возможно ли это?

Я предполагаю, что ответ на это будет "Невозможно, переключитесь на С++". Но я думал, что все равно выброшу его.

Я имею дело с массивным двоичным деревом. У меня есть массив структур для представления узлов ветвей, которые я использую, чтобы помочь с локальностью памяти при итерации через дерево.

Чтобы сохранить немного памяти и, следовательно, улучшить локальность кэша, я рассматриваю перекрытие ссылки на объекты для листовых узлов. Эта ссылка на объект укажет на все данные листа. В основном, что-то вроде этого:

[StructLayout(LayoutKind.Explicit)]
struct BranchData
{
    [FieldOffset(0)] // 1 byte
    internal byte SplitIndex;
    [FieldOffset(1)] // 4 bytes
    internal float SplitValue;
    [FieldOffset(5)] // 4 bytes
    internal int LowIndex;
    [FieldOffset(9)] // 4 bytes
    internal int HighIndex;
    [FieldOffset(0)] // 8 bytes (We're working with x64 here)
    internal LeafData Node;
}

Вышеприведенная информация дает следующую ошибку времени выполнения

Не удалось загрузить тип "BranchData" из сборки 'WindowsFormsApplication1, Version = 1.0.0.0, Culture = neutral, PublicKeyToken = null ', потому что он содержит поле объекта со смещением 0 который неправильно выровнен или перекрыт полем, отличным от объекта.

Я мог бы использовать отдельный массив для хранения листовых данных и использовать индексы для указания на этот массив, но затем у меня есть 2 просмотра памяти (для того, что, безусловно, отдаленные области памяти). Один для местоположения в массиве листьев, чтобы получить ссылку, и один для получения данных листа. Если я смогу достичь этого перекрытия, я избавлюсь от одного из этих запросов.

Я могу привязывать объекты и использовать небезопасный код для решения этой проблемы. Здесь ключевой элемент - скорость.

Ответы

Ответ 1

Это ограничение очень важно в управляемом коде. Проблема в том, что ваш Node член является ссылкой на объект. Указатель во время выполнения. Он перекрывается другими полями.

Сборщик мусора должен иметь возможность найти этот указатель. Необходимо знать, что есть живая ссылка на объект LeafData в куче. И обновить этот указатель, когда объект LeafData перемещается при уплотнении кучи.

Проблема заключается в том, что коллекционер не может определить, сохраняет ли ваш союз этот указатель. Если это не так, то существует риск того, что значения других членов будут выглядеть как действительная ссылка объекта на GC. И это очень, очень плохо.

Сохранение небезопасного LeafData * технически возможно, но для этого требуется, чтобы объект LeafData был закреплен. Это просто не может работать, когда дерево велико, GC падает, когда больше ничего не может быть перемещено. Хранение данных LeafData в неуправляемой памяти дальше вниз по кроличьей дыре, вы начинаете писать код С++ к тому времени. Единственное, что вы могли бы сделать, это сохранить LeafData в самой Node, как структуру, маловероятно, что вы будете довольны подгонкой.

Помните, что вам следует избегать этих несогласованных полей, вы сильно ударяетесь, когда поле охватывает границу строки кеша L1. Поместите SplitIndex после HighIndex, чтобы этого не произошло.

Ответ 2

Я не знаю, будет ли это на практике быстрее, но в управляемом коде меньше поиска памяти.

(В CLR может быть больше запросов, о которых я не знаю.)

Тем не менее, вы можете использовать GCHandle для наложения управляемых ссылок с неуправляемыми данными:

[StructLayout(LayoutKind.Explicit)]
public struct Data
{
    [FieldOffset(0)]
    public IntPtr NativeData;
    [FieldOffset(0)]
    public GCHandle Handle;
}


Data data = ...;
((YourClass)data.Handle.Target).Blah();