Как переносить сохранение двух слов памяти в парных структурах?

Question

У меня есть структура данных struct foo, которая всегда появляется попарно. Прямо сейчас, каждый struct foo таскает указатель на другой struct foo в своей паре:

struct foo { 
    struct foo *other_half; 
    /* ... */ 
}; 

Как моя программа требует много (> 1'000'000) struct foo, я стремлюсь, чтобы уменьшить размер каждого из них , Есть ли способ избавиться от указателя other_half и найти другую половину пары struct foo другими способами?

Answer 1

Рассмотрите массив struct foo foos[2] из двух struct foo, выровненный с 2 * sizeof (struct foo) или больше. Обратите внимание, что foos[0] выровнена с 2 * sizeof (struct foo) или выше, тогда как foos[1] выровнена только с sizeof (struct foo). Вы можете использовать эту информацию, чтобы узнать, является ли случайный struct foo*, который указывает на такое выровненное struct foo[2], указывает на первый или второй элемент.

Чтобы получить достаточно выровненную память, напишите собственный распределитель или используйте функцию C11 aligned_alloc. Обратите внимание, что на самом деле не требуется полностью выровнять память, просто чтобы бит, который мы тестировали в other_half, был очищен.

Наивная реализация функции, чтобы найти другую половину пары struct foo данной указатель на одну половину выглядит следующим образом:

struct foo *other_half(struct foo *half) { 
    if ((uintptr_t)half % (2 * sizeof *half) == 0) 
     return half + 1; 
    else 
     return half - 1; 
} 

Эта функция, однако, не очень эффективна, если sizeof (struct foo) не сила из двух, поскольку это связано с медленной модульной операцией. Чтобы ускорить процесс, рассмотрите факторизацию sizeof (struct foo), которая относится к форме 2 ⁿ · q. Легко видеть, что достаточно, чтобы проверить, потому что ((uintptr_t)half & (uintptr_t)1 << n) == 02 * sizeof (struct foo) является кратным 2 ^{N + 1} и, следовательно, имеет биты в позиции 0 до п выключен.

Вычисление п во время компиляции немного сложнее, но, к счастью, нам нужно 1 << n только, которые могут быть вычислены с немного магии -sizeof (struct foo) & sizeof (struct foo):

struct foo *other_half(struct foo *half) { 
    if ((uintptr_t)half & -sizeof *half & sizeof *half) 
     return half - 1; 
    else 
     return half + 1; 
} 

Answer 2

Альтернативный дизайн с меньшим количеством обмана, но использование одного байта на foo; или бит, если вы упакуете значение вместе с каким-либо другим полем.

#include 
#include 

struct foo { 
    char Index; // can be packed together with some other field 
    /* ... */ 
}; 

typedef struct foo pair[2]; 

void init_pair(pair *p){ 
    for(size_t i = 0; i < sizeof(*p); i++){ 
     (*p)[i].Index = (char)(i); 
    } 
} 

struct foo *pair_index(struct foo *piece, size_t index){ 
    return &piece[index - (size_t)piece->Index]; 
} 

struct foo *pair_other(struct foo *piece){ 
    return pair_index(piece, piece->Index^0x01); 
} 

Пример:

int main(int argc, char const *argv[]) 
{ 
    pair p; 
    init_pair(&p); 

    struct foo *first = &(p[0]); 
    struct foo *second = &(p[1]); 

    printf("%p %p\n", pair_index(first, 0), pair_index(first, 1)); 
    printf("%p %p\n", pair_index(second, 0), pair_index(second, 1)); 
    printf("%p %p\n", pair_other(second), pair_other(first)); 
    return 0; 
}