Это что-то вроде хака, но я использовал его в прошлом с некоторым успехом. Дополнительные затраты на доступ к объекту были компенсированы значительным сокращением памяти.
Типичным вариантом использования является среда, в которой (а) значения являются фактически различимыми объединениями (то есть они включают в себя указатель типа) с ограниченным числом различных типов, и (б) значения в основном хранятся в больших смежных векторах.
В этой среде вполне вероятно, что часть значений (некоторых видов) полезной нагрузки использует все биты, выделенные для нее. Также возможно, что тип данных требует (или выигрывает от) сохранения в выровненной памяти.
На практике теперь, когда выровненный доступ не требуется большинству основных процессоров, я бы просто использовал упакованную структуру вместо следующего хака. Если вы не платите за невыровненный доступ, то оптимальным является хранение {однобайтового типа + восьмибайтового значения} в виде девяти смежных байтов; единственная цена - умножение на 9 вместо 8 для индексированного доступа, и это тривиально, поскольку 9 - это константа времени компиляции.
Если вам необходимо заплатить за неприсоединившийся доступ, возможно следующее. Векторы «дополненных» значений имеют тип:
// Assume that Payload has already been typedef'd. In my application,
// it would be a union of, eg., uint64_t, int64_t, double, pointer, etc.
// In your application, it would be b.
// Eight-byte payload version:
typedef struct Chunk8 { uint8_t kind[8]; Payload value[8]; }
// Four-byte payload version:
typedef struct Chunk4 { uint8_t kind[4]; Payload value[4]; }
Векторы - это векторы Чанков. Чтобы хак работал, они должны быть распределены по 8- (или 4-) байтовым адресам памяти, но мы уже предположили, что выравнивание требуется для типов полезной нагрузки.
Ключ к взлому - то, как мы представляем указатель на отдельное значение, потому что значение не является непрерывным в памяти. Мы используем указатель на его kind член в качестве прокси:
typedef uint8_t ValuePointer;
А затем используйте следующие функции с низким, но не нулевым уровнем издержек:
#define P_SIZE 8U
#define P_MASK P_SIZE - 1U
// Internal function used to get the low-order bits of a ValuePointer.
static inline size_t vpMask(ValuePointer vp) {
return (uintptr_t)vp & P_MASK;
}
// Getters / setters. This version returns the address so it can be
// used both as a getter and a setter
static inline uint8_t* kindOf(ValuePointer vp) { return vp; }
static inline Payload* valueOf(ValuePointer vp) {
return (Payload*)(vp + 1 + (vpMask(vp) + 1) * (P_SIZE - 1));
}
// Increment / Decrement
static inline ValuePointer inc(ValuePointer vp) {
return vpMask(++vp) ? vp : vp + P_SIZE * P_SIZE;
}
static inline ValuePointer dec(ValuePointer vp) {
return vpMask(vp--) ? vp - P_SIZE * P_SIZE : vp;
}
// Simple indexed access from a Chunk pointer
static inline ValuePointer eltk(Chunk* ch, size_t k) {
return &ch[k / P_SIZE].kind[k % P_SIZE];
}
// Increment a value pointer by an arbitrary (non-negative) amount
static inline ValuePointer inck(ValuePointer vp, size_t k) {
size_t off = vpMask(vp);
return eltk((Chunk*)(vp - off), k + off);
}
Я пропустил кучу других хаков, но я уверен, что вы можете их выяснить.
Одна замечательная вещь при чередовании фрагментов значения - это то, что он имеет умеренно хорошее местоположение. Для 8-байтовой версии почти половину времени произвольный доступ к виду и значению будет попадать только на одну 64-байтовую строку кэширования; в остальное время выполняются две последовательные линии кеша, в результате чего перемещение вперед (или назад) по вектору столь же благоприятно для кеширования, как и при прохождении по обычному вектору, за исключением того, что он использует меньше кешлайнов, поскольку объекты имеют половину размера , Четырехбайтовая версия даже удобнее для кэша.