Skip to content

Instantly share code, notes, and snippets.

@alk
Created January 26, 2016 18:52
Show Gist options
  • Save alk/09a387957fc78aa25b29 to your computer and use it in GitHub Desktop.
Save alk/09a387957fc78aa25b29 to your computer and use it in GitHub Desktop.
some freelist representation ideas
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
#include <assert.h>
#include <memory.h>
struct FreeListEntry {
FreeListEntry *l, *r;
};
static const int kDigits = 5;
struct FreeList {
FreeListEntry *digits[kDigits];
// only used for inc2 and dec2
int idx;
};
__attribute__((noinline))
void inc(FreeList *l, FreeListEntry *item)
{
FreeListEntry **digits = l->digits;
FreeListEntry *carry = *digits;
if (__builtin_expect(carry == nullptr, 1)) {
*digits = item;
return;
}
*digits = nullptr;
FreeListEntry **digits_end = l->digits + kDigits - 2;
do {
FreeListEntry *e = *++digits;
if (__builtin_expect(!e, 1)) {
// item->l = nullptr;
item->r = carry;
*digits = item;
return;
}
e->l = carry;
carry = e;
*digits = nullptr;
} while (digits != digits_end);
item->r = carry;
item->l = *++digits;
*digits = item;
}
// __attribute__((noinline))
// void inc(FreeList *l, FreeListEntry *item)
// {
// FreeListEntry *carry = l->digits[0];
// if (__builtin_expect(carry == nullptr, 1)) {
// l->digits[0] = item;
// return;
// }
// FreeListEntry **digits_end = l->digits + kDigits - 1;
// int i;
// for (i = -kDigits + 2; i < 0; i++) {
// FreeListEntry *e = digits_end[i];
// if (__builtin_expect(!e, 1)) {
// item->l = nullptr;
// item->r = carry;
// digits_end[i] = item;
// return;
// }
// e->l = carry;
// carry = e;
// digits_end[i] = nullptr;
// }
// item->r = carry;
// item->l = digits_end[i];
// digits_end[i] = item;
// }
// __attribute__((noinline))
// void inc(FreeList *l, FreeListEntry *item)
// {
// FreeListEntry *carry = nullptr;
// int i;
// for (i = 0; i < kDigits - 1; i++) {
// FreeListEntry *e = l->digits[i];
// if (__builtin_expect(!e, 1)) {
// item->l = nullptr;
// item->r = carry;
// l->digits[i] = item;
// return;
// }
// e->l = carry;
// carry = e;
// l->digits[i] = nullptr;
// }
// item->r = carry;
// item->l = l->digits[i];
// l->digits[i] = item;
// }
// __attribute__((noinline))
// void inc(FreeList *l, FreeListEntry *item)
// {
// FreeListEntry *carry = nullptr;
// FreeListEntry *e;
// {
// e = l->digits[0];
// if (__builtin_expect(!e, 1)) {
// // item->l = nullptr;
// // item->r = carry;
// l->digits[0] = item;
// return;
// }
// // e->l = carry;
// carry = e;
// l->digits[0] = nullptr;
// }
// {
// e = l->digits[1];
// if (__builtin_expect(!e, 1)) {
// item->l = nullptr;
// item->r = carry;
// l->digits[1] = item;
// return;
// }
// e->l = carry;
// carry = e;
// l->digits[1] = nullptr;
// }
// {
// e = l->digits[2];
// if (__builtin_expect(!e, 1)) {
// item->l = nullptr;
// item->r = carry;
// l->digits[2] = item;
// return;
// }
// e->l = carry;
// carry = e;
// l->digits[2] = nullptr;
// }
// {
// e = l->digits[3];
// if (__builtin_expect(!e, 1)) {
// item->l = nullptr;
// item->r = carry;
// l->digits[3] = item;
// return;
// }
// e->l = carry;
// carry = e;
// l->digits[3] = nullptr;
// }
// item->r = carry;
// item->l = l->digits[4];
// l->digits[4] = item;
// }
__attribute__((noinline))
FreeListEntry *dec(FreeList *l)
{
FreeListEntry **digits = l->digits;
FreeListEntry *rv = *digits;
if (__builtin_expect(rv != nullptr, true)) {
*digits = nullptr;
return rv;
}
rv = digits[1];
if (__builtin_expect(rv != nullptr, true)) {
digits[1] = nullptr;
digits[0] = rv->r;
return rv;
}
rv = digits[2];
if (__builtin_expect(rv != nullptr, true)) {
digits[2] = nullptr;
FreeListEntry *e1 = rv->r;
digits[1] = e1;
FreeListEntry *e0 = e1->l;
digits[0] = e0;
return rv;
}
rv = digits[3];
if (__builtin_expect(rv != nullptr, true)) {
digits[3] = nullptr;
FreeListEntry *e2 = rv->r;
digits[2] = e2;
FreeListEntry *e1 = e2->l;
digits[1] = e1;
FreeListEntry *e0 = e1->l;
digits[0] = e0;
return rv;
}
rv = digits[4];
if (__builtin_expect(rv != nullptr, true)) {
digits[4] = rv->l;
FreeListEntry *e3 = rv->r;
digits[3] = e3;
FreeListEntry *e2 = e3->l;
digits[2] = e2;
FreeListEntry *e1 = e2->l;
digits[1] = e1;
FreeListEntry *e0 = e1->l;
digits[0] = e0;
return rv;
}
return nullptr;
}
// __attribute__((noinline))
// FreeListEntry *dec(FreeList *l)
// {
// int i;
// FreeListEntry *rv = l->digits[0];
// if (__builtin_expect(rv != nullptr, true)) {
// l->digits[0] = nullptr;
// return rv;
// }
// for (i = 1; i < kDigits; i++) {
// if (__builtin_expect((rv = l->digits[i]) != nullptr, true))
// goto found;
// }
// return rv;
// found:
// l->digits[i] = rv->l;
// if (i == 0) {
// return rv;
// }
// FreeListEntry *carry = rv->r;
// while (--i >= 0) {
// FreeListEntry *newcarry = carry->l;
// l->digits[i] = carry;
// carry->l = nullptr;
// carry = newcarry;
// }
// // assert(carry == nullptr);
// return rv;
// }
static const int kEntries = 32768;
FreeListEntry test_entries[kEntries];
FreeListEntry *ptrs[kEntries];
void randomizeEntries(void)
{
FreeListEntry **e = ptrs;
for (int i = 0; i < kEntries; i++) {
e[i] = test_entries + i;
}
srand(0);
for (int i = 0; i < kEntries; i++) {
int k = rand() % (kEntries - i) + i;
FreeListEntry *t = e[k];
e[k] = e[i];
e[i] = t;
if (i > 0) {
e[i-1]->l = e[i];
}
}
}
// __attribute__((noinline))
void push(FreeList *l, FreeListEntry *e)
{
e->l = l->digits[0];
l->digits[0] = e;
}
// __attribute__((noinline))
FreeListEntry *pop(FreeList *l)
{
FreeListEntry *rv = l->digits[0];
l->digits[0] = rv->l;
return rv;
}
__attribute__((noinline))
void inc2(FreeList *l, FreeListEntry *item)
{
--l->idx;
if (__builtin_expect(l->idx != 0, true)) {
l->digits[l->idx] = item;
return;
}
FreeListEntry *e0 = l->digits[3];
FreeListEntry *e1 = l->digits[2];
FreeListEntry *e2 = l->digits[1];
FreeListEntry *e3 = item;
e0->l = l->digits[4];
e0->r = e1;
e1->l = e2;
e1->r = e3;
l->digits[4] = e0;
l->idx = 4;
}
__attribute__((noinline))
FreeListEntry *dec2(FreeList *l)
{
if (__builtin_expect(l->idx < 4, true)) {
return l->digits[l->idx++];
}
FreeListEntry *e0 = l->digits[4];
if (__builtin_expect(e0 == nullptr, false)) {
return nullptr;
}
l->digits[4] = e0->l;
FreeListEntry *e1 = e0->r;
l->digits[3] = e0;
l->digits[2] = e1;
l->digits[1] = e1->l;
l->idx = 1;
return e1->r;
}
__attribute__((noinline))
void inc3(FreeList *l, FreeListEntry *item)
{
FreeListEntry *carry = l->digits[0];
if (__builtin_expect(carry == nullptr, true)) {
l->digits[0] = item;
return;
}
l->digits[0] = nullptr;
item->r = carry;
item->l = l->digits[1];
l->digits[1] = item;
}
__attribute__((noinline))
FreeListEntry *dec3(FreeList *l)
{
FreeListEntry *item = l->digits[0];
if (__builtin_expect(item != nullptr, true)) {
l->digits[0] = nullptr;
return item;
}
item = l->digits[1];
if (__builtin_expect(item == nullptr, false)) {
return nullptr;
}
l->digits[0] = item->r;
l->digits[1] = item->l;
return item;
}
// static const int kOuterCnt = 50000;
// static const int kInnerCnt = 16384;
static const int kOuterCnt = 100000;
static const int kInnerCnt = 8192;
int main(void)
{
FreeList l;
memset(&l, 0, sizeof(l));
l.idx = 4;
// #define inc(a,b) push(a,b)
// #define dec(a) pop(a)
// #define inc(a,b) inc2(a,b)
// #define dec(a) dec2(a)
// #define inc(a,b) inc3(a,b)
// #define dec(a) dec3(a)
randomizeEntries();
// for (int k = 0; k < 31; k++) {
// inc(&l, ptrs[k]);
// }
// for (int i = kOuterCnt; i > 0; i--) {
// for (int k = 0; k < kInnerCnt; k++) {
// inc(&l, ptrs[32]);
// dec(&l);
// }
// }
for (int i = kOuterCnt; i > 0; i--) {
for (int k = 0; k < kInnerCnt; k++) {
inc(&l, ptrs[k]);
}
for (int k = kInnerCnt - 1; k >= 0; k--) {
FreeListEntry *e = dec(&l);
assert(e == ptrs[k]);
}
}
printf("%lld incs and decs\n", (long long)kOuterCnt * kInnerCnt);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment