Вчера на работа се сблъсках с един интересен хак, който бях забравил напоследък …
В езиците от високо ниво не можем да менажираме ръчно памета. Всичко си става автоматично. А напоследък все повече мразя автоматичните неща, защото цената им понякога е твърде висока.
В С++ например, можем експлицитно да укажем как да бъде подравнена паметта, която заделяме (на 1, 2, 4 или друга степен на 2). Oт гледна точка на програмиста, ако паметта е подравнена на 4 байта например, това означава че pointer-ите винаги по модул 4 ще дават 0 (макар в стандарта да не е специфицирано точно така, поведението днес е такова).
Подравняването е важно.
В днешно време повечето компилатори подравняват паметта самички и без да им казваме на колко. Но имат и разни атрибути, с които можем да си изберем ние.
Ето пример :
|
1 2 3 4 5 6 7 |
//gcc 4.2 #define ALIGNED(X) __attribute__((aligned (X))) struct ALIGNED(4) FooBar { size_t a; }; |
Сега е време за един що-годе известен хак.
Лесно можем да проверим, че най-младшите няколко бита, от стойноста на поинтърите към памет винаги са 0.
|
1 2 3 4 |
for (int i = 0; i < 4096; ++i) { auto* ptr = new int; cout << ptr; } |
Причината е проста.
Още по-точно, можем да изкажем твърдението, че първите log2(n) – 1 брой бита, винаги са 0, когато ползваме подравнена памет (а тя е такава често дори без да сме указали експлицитно).
Мисля, че не е трудно да го докажем : поинтъра n се дели на число k без остатък, к е точна степен на 2 – да речем, i-та степен на 2. Тоест, n се дели на 2 i-пъти без остатък. Всяко делене можем да представим като right-shift на битове. Така, ако сме имали 1 на някое от местата 0…i-2, да речем на място p, след p шифтове ще получим нечетно число (p ще е стигнало позиция 0), а то при делене с 2 ще има остатък.
Сега, излиза така че няколко бита от стойноста на поинтъра са 0 ако ползваме подравнена памет. Всъщност, съвременните процесори обичат подравняване на около 128 бита. И двата компилатора, с които тествах автоматично правеха това (gcc & clang)
Излиза, че няколко бита във всеки поинтър са си 0 винаги. И като лоши хакери, ние трябва да се възползваме от това :).
Сега, да речем че ни трябва следната структура :
|
1 2 3 4 5 6 7 |
template <typename T> struct Node { T* left; T* right; bool something; bool somethingElse; }; |
На моят компилатор (clang3.1 x64) sizeof(Node) е 24 .. 2 ptrs x 8 = 16; Oстаналите 8 идват от автоматичното подравняване заради 2-та булеви флага. Сега, можем да напишем кода така, предполагайки че данните са подравнени :
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 |
template <typename T> void setFlag(T*& ptr, size_t flagIndex, bool value) { size_t ptrAsSizeT = reinterpret_cast<size_t>(ptr); if (value) { ptr = reinterpret_cast<T*>( ptrAsSizeT | (1 << flagIndex) ); } else { ptr = reinterpret_cast<T*>( ptrAsSizeT & (~ (1 << flagIndex))); } } template<typename T> bool getFlag(const T* ptr, size_t flagIndex) { return ptr & (1 << flagIndex); } template<typename T> struct Node { private: T* left; T* right; public: Т* getLeft() const { //make getRight() too T* tempPtr = left; setFlag(tempPtr, 0, 0); setFlag(tempPtr, 1, 0); return tempPtr; } bool getSomething() const { return getFlag(left, 0); } bool getSomethingElse() const { return getFlag(left, 1); } void setSomething(bool foo) { setFlag(left, 0, foo); } void setSomethingElse(bool foo) { setFlag(left, 1, foo); } }; |
Вече sizeof(Node) е 16, което е 33% спестена памет. За няколко милярда такива node-a бая гигабайта ще се съберат 🙂 А можем всъщност и доста повече информация да компресираме по този начин в указателите.
Вероятно няма да работи на всякакви архитектури, но за x86 e супер.
п.с. знам за не една и две програми, ползвали този хак; тоест, доказал се е в битка. Компресираите си здраво и наздраве 🙂
Един подобен хак от старите времена – когато имаш двойносвързан списък, в структурата за единичен елемент можеш да пазищ само 1 поинтер (т.е. вместо да имаш next и prev поинтери, може да е само един, който е next^prev). Докато итерираш списъка, винаги в итериращата функция ще си пазиш откъде си дошъл (т.е. ако итерираш напред, ще пазиш поинтери към предходния и текущия елемент) и после чрез XOR-ване и смяташ адреса на следващия елемент 🙂
Имаш една миниатюрна грешчица 😀
В структурата, T* left, right; дефинира указател T* left, и данна T right, а не два указателя 🙂
@Веско – яко
@Любо – fixed
🙂