В Boost я прочитал о маскировании информации в указатели для экономии памяти (здесь: https://www.boost.org/doc/libs/1_72_0/doc/html/intrusive/set_multiset.html, optimize_size). Как это возможно?
Ответ дается по ссылке, которую вы разместили:
Крюк вставит бит цвета узла красно-черного дерева в родительский элемент указатель, если выравнивание указателя является четным.
Когда выравнивание является четным, младший бит в значении указателя всегда равен нулю и может использоваться для хранения цветового бита. Всякий раз, когда указатель или цвет должны быть загружены, другие биты должны быть очищены, что добавляет незначительное влияние на производительность, но, в свою очередь, экономит место указателя в ловушке. На практике, однако, издержки производительности часто скрываются параллельным выполнением инструкций в CPU.
Я где-то читал, что указатели используют только 48 бит, но имеют длину 64 бита, так что вы можете pu sh Ваша информация в старших битах со сдвигом битов. Это правильно?
В 64-битных системах размер указателя составляет 64 бита, но некоторые системы не реализуют указатели полной ширины и вместо этого используют меньше битов для адресации. Когда старшие биты не используются, они должны иметь значение c (в x86). Википедия дает хороший обзор различных процессоров, включая x86. Вы увидите, что разные архитектуры имеют разные ограничения, а некоторые даже реализуют 64-битную адресацию по всей ширине. Таким образом, хотя можно хранить дополнительные данные в старших битах, это невозможно на всех архитектурах, и логики очистки c могут отличаться на разных архитектурах ЦП.
Почему они используя целое число для хранения информации о цвете rb-деревьев? Разве не было бы более эффективно использовать символы?
A char - целое число. Информация о цвете на самом деле один бит (красный или черный узел). Другие биты, char или int, не используются. Чтобы ответить на ваш вопрос, использование char может быть более эффективным в некоторых случаях, но не в случае с Boost.Intrusive hooks. Поэтому Boost не использует ни один из этих типов для хранения цвета, когда включен optimize_size. Когда он не включен, enum (обычно того же размера, что и int) используется для хранения цветовой метки, но это не имеет значения, так как из-за выравнивания в ловушку добавляется пространство указателя. (Некоторые из добавленных отступов могут использоваться для других полезных данных в случае базового перехвата, но только в очень специфических c случаях, когда первые нестатические c члены данных, следующие сразу после перехвата в двоичной разметке узла иметь небольшое выравнивание.)