Я надеюсь на какой-нибудь совет высокого уровня о том, как подойти к проекту, который собираюсь предпринять.
Простой подход к моей проблеме приведет к миллионам и миллионам указателей. В 64-битной системе это предположительно будут 64-битные указатели. Но что касается моего приложения, я не думаю, что мне нужно больше, чем 32-битное адресное пространство. Однако мне бы хотелось, чтобы система использовала преимущества арифметики 64-битного процессора (при условии, что это то, что я получаю, работая в 64-битной системе).
Дополнительная информация
Я реализую древовидную структуру данных, где каждый «узел» содержит 8-байтовую полезную нагрузку, но также нужны указатели на четыре соседних узла (родительский, левый-дочерний, средний-дочерний и т. д.). правый ребенок). В 64-битной системе, использующей 64-битные указатели, это составляет 32 байта только для связывания 8-байтовой полезной нагрузки с деревом — «накладные расходы на связывание» равны 400%.
Структура данных будет содержать миллионы таких узлов, но моему приложению не понадобится больше памяти, поэтому все эти 64-битные указатели кажутся расточительными. Что делать? Есть ли способ использовать 32-битные указатели в 64-битной системе?
Я рассматривал
хранение полезных данных в массиве таким образом, чтобы индекс подразумевал (и подразумевается) «адрес дерева», а соседи данного индекса можно было вычислить с помощью простой арифметики по этому индексу. К сожалению, это требует от меня определения размера массива в соответствии с максимальной глубиной дерева, о которой я заранее не знаю, и это, вероятно, потребует еще больших затрат памяти из-за пустых элементов узла на нижних уровнях, поскольку не все ветви дерева имеют одинаковую глубину.
Сохранение узлов в массиве, достаточно большом, чтобы вместить их все, а затем использование индексов вместо указателей для связи соседей. AFAIK, основным недостатком здесь будет то, что каждому узлу понадобится базовый адрес массива, чтобы найти своих соседей. Таким образом, им нужно либо сохранить его (миллион раз), либо его нужно передавать при каждом вызове функции. Мне это не нравится.
Предполагая, что наиболее значимые 32 бита всех этих указателей равны нулю, выбрасываем исключение, если это не так, и сохраняем только наименее значимые 32 бита. Таким образом, требуемый указатель может быть восстановлен по требованию. Система, скорее всего, будет использовать более 4 ГБ, но процесс никогда не будет. Я просто предполагаю, что указатели смещены от базового адреса процесса, и понятия не имею, насколько безопасно (если вообще) это будет на общих платформах (Windows, Linux, OSX).
Сохранение разницы между 64-битным this и 64-битным указателем на соседа, предполагая, что эта разница будет в пределах диапазона std::int32_t (и выбрасывает, если это не так). Тогда любой узел сможет найти своих соседей, добавив это смещение к этому.
Какой совет? Что касается последней идеи (которая в настоящее время кажется мне лучшим кандидатом), могу ли я предположить, что в процессе, который использует менее 2 ГБ, динамически выделяемые объекты будут находиться в пределах 2 ГБ друг от друга? Или совсем не обязательно?
Я надеюсь на какой-нибудь совет высокого уровня о том, как подойти к проекту, который собираюсь предпринять. Простой подход к моей проблеме приведет к миллионам и миллионам указателей. В 64-битной системе это предположительно будут 64-битные указатели. Но что касается моего приложения, я не думаю, что мне нужно больше, чем 32-битное адресное пространство. Однако мне бы хотелось, чтобы система использовала преимущества арифметики 64-битного процессора (при условии, что это то, что я получаю, работая в 64-битной системе). Дополнительная информация Я реализую древовидную структуру данных, где каждый «узел» содержит 8-байтовую полезную нагрузку, но также нужны указатели на четыре соседних узла (родительский, левый-дочерний, средний-дочерний и т. д.). правый ребенок). В 64-битной системе, использующей 64-битные указатели, это составляет 32 байта только для связывания 8-байтовой полезной нагрузки с деревом — «накладные расходы на связывание» равны 400%. Структура данных будет содержать миллионы таких узлов, но моему приложению не понадобится больше памяти, поэтому все эти 64-битные указатели кажутся расточительными. Что делать? Есть ли способ использовать 32-битные указатели в 64-битной системе? Я рассматривал [list] [*]хранение полезных данных в массиве таким образом, чтобы индекс подразумевал (и подразумевается) «адрес дерева», а соседи данного индекса можно было вычислить с помощью простой арифметики по этому индексу. К сожалению, это требует от меня определения размера массива в соответствии с максимальной глубиной дерева, о которой я заранее не знаю, и это, вероятно, потребует еще больших затрат памяти из-за пустых элементов узла на нижних уровнях, поскольку не все ветви дерева имеют одинаковую глубину.
[*]Сохранение узлов в массиве, достаточно большом, чтобы вместить их все, а затем использование индексов вместо указателей для связи соседей. AFAIK, основным недостатком здесь будет то, что каждому узлу понадобится базовый адрес массива, чтобы найти своих соседей. Таким образом, им нужно либо сохранить его (миллион раз), либо его нужно передавать при каждом вызове функции. Мне это не нравится.
[*]Предполагая, что наиболее значимые 32 бита всех этих указателей равны нулю, выбрасываем исключение, если это не так, и сохраняем только наименее значимые 32 бита. Таким образом, требуемый указатель может быть восстановлен по требованию. Система, скорее всего, будет использовать более 4 ГБ, но процесс никогда не будет. Я просто предполагаю, что указатели смещены от базового адреса процесса, и понятия не имею, насколько безопасно (если вообще) это будет на общих платформах (Windows, Linux, OSX).
[*]Сохранение разницы между 64-битным this и 64-битным указателем на соседа, предполагая, что эта разница будет в пределах диапазона std::int32_t (и выбрасывает, если это не так). Тогда любой узел сможет найти своих соседей, добавив это смещение к этому.
[/list] Какой совет? Что касается последней идеи (которая в настоящее время кажется мне лучшим кандидатом), могу ли я предположить, что в процессе, который использует менее 2 ГБ, динамически выделяемые объекты будут находиться в пределах 2 ГБ друг от друга? Или совсем не обязательно?
Мобильная версия