Скрыть информацию в указателе - C++ (Boost.Intrusive)

Question

В Boost я читал о маскировании информации в указатели для экономии памяти (здесь: https://www.boost.org/doc/libs/1_72_0/doc/html/intrusive/set_multiset.html, optimize_size). Как это возможно? Я где-то читал, что указатели используют только 48 бит, но имеют длину 64 бита, поэтому вы можете передавать свою информацию в более высокие биты с битовым сдвигом. Это верно?

Почему они используют целое число для хранения информации о цвете rb-деревьев? Разве не было бы эффективнее использовать символы?

Answer 1

В Boost я читал о маскировании информации в указатели для экономии памяти (здесь: https://www.boost.org/doc/libs/1_72_0/doc/html/intrusive/set_multiset.html, optimize_size). Как это возможно?

Ответ дан по опубликованной вами ссылке:

Хук будет внедрять бит цвета красно-черного узла дерева в родительский указатель, если выравнивание указателя четное.

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

Я где-то читал, что указатели используют только 48 бит, но имеют длину 64 бита, поэтому вы можете передавать свою информацию в более высокие биты с битовым сдвигом. Это верно?

В 64-разрядных системах размер указателя составляет 64 бита, но некоторые системы не реализуют указатели полной ширины и вместо этого используют меньшее количество бит для адресации. Когда верхние биты не используются, они должны иметь определенное значение (в x86). Википедия дает хороший обзор различных процессоров, включая x86. Вы увидите, что разные архитектуры имеют разные ограничения, а некоторые даже реализуют полноразмерную 64-битную адресацию. Таким образом, хотя в старших битах можно хранить дополнительные данные, это возможно не на всех архитектурах, а логика очистки может отличаться на разных архитектурах ЦП.

Почему они используют целое число для хранения информации о цвете rb-деревьев? Разве не было бы эффективнее использовать символы?

А charцелое число. Информация о цвете - это фактически один бит (красный или черный узел). Остальные биты, будь то вchar или int, не используются. Чтобы ответить на ваш вопрос, используяcharможет быть более эффективным в некоторых случаях, но не в случае хуков Boost.Intrusive. Поэтому Boost не использует ни один из этих типов для хранения цвета, когдаoptimize_sizeвключен. Когда он не включен, перечисление (обычно того же размера, что иint) используется для хранения тега цвета, но на самом деле это не имеет значения, так как из-за выравнивания к хуку добавляется место на указатель. (Некоторые из добавленных дополнений могут использоваться для других полезных данных в случае базовой ловушки, но только в очень конкретных случаях, когда первые нестатические элементы данных, следующие сразу за ловушкой в ​​двоичной компоновке узла, имеют небольшое выравнивание.)