some freelist representation ideas

freelist2.cc

#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;
}