/kalufiles/11835_lflist.cpp

(in VirtualBox on iMac i5)
single thread, without lock: 937ms

# of threads 1 2 4 8
course-grained 1151, 1051, 1325, 1211(ms)
fine-grained 12929, 9497, 11287, 11564
optimist list 1724, 1317, 1349, 1311
lazy list 1245, 734 , 815 , 741
lock-free list 7731, 5178, 3856, 3328









#include
#include


int num_of_threads = 1;
LARGE_INTEGER start, end, freq;



class NODE {
public:
int key;
NODE *next;
bool deleted;
CRITICAL_SECTION node_lock;

NODE() { next = NULL; InitializeCriticalSection(&node_lock); deleted = false; }

NODE(int key_value) {
next = NULL;
key = key_value;
deleted = false;
InitializeCriticalSection(&node_lock);
}

~NODE() {}

void Lock() { EnterCriticalSection(&node_lock); }
void Unlock() { LeaveCriticalSection(&node_lock); }
};


class LFNODE {
public:
int key;
LFNODE *next;

LFNODE() { next = NULL; }

LFNODE(int key_value) {
next = NULL;
key = key_value;
}

~LFNODE() {}

bool CAS(int old_v, int new_v) {
int orig_v = InterlockedCompareExchange(reinterpret_cast
(&next), new_v, old_v);
return orig_v == old_v;
}

bool CAS(LFNODE *old_node, LFNODE *new_node, bool oldMark, bool newMark) {
int oldvalue = reinterpret_cast(old_node);
if (oldMark) oldvalue = oldvalue | 0x01;
else oldvalue = oldvalue & 0xFFFFFFFE;

int newvalue = reinterpret_cast(new_node);
if (newMark) newvalue = newvalue | 0x01;
else newvalue = newvalue & 0xFFFFFFFE;

return CAS(oldvalue, newvalue);
}

bool AttemptMark(LFNODE *old_node, bool newMark) {
int oldvalue = reinterpret_cast(old_node);
int newvalue = oldvalue;
if (newMark) newvalue = newvalue | 0x01;
else newvalue = newvalue & 0xFFFFFFFE;
return CAS(oldvalue, newvalue);
}

LFNODE* GetReference()
{
int temp = reinterpret_cast(next);
temp = temp & 0xFFFFFFFE;
return reinterpret_cast(temp);
}

LFNODE* Get(bool* marked)
{
int temp = reinterpret_cast(next);
*marked = (0 != (temp & 0x1));
temp = temp & 0xFFFFFFFE;
return reinterpret_cast(temp);
}

};


class CLIST {
NODE head, tail;
CRITICAL_SECTION glock;
public:
CLIST()
{
head.key = 0x80000000;
tail.key = 0x7FFFFFFF;
head.next = &tail;
InitializeCriticalSection(&glock);
}
~CLIST() {}

void Init()
{
NODE *ptr;
while(head.next != &tail) {
ptr = head.next;
head.next = head.next->next;
delete ptr;
}
}
bool Add(int key)
{
NODE *pred, *curr;

pred = &head;
// EnterCriticalSection(&glock);
curr = pred->next;
while (curr->key < key) {
pred = curr;
curr = curr->next;
}

if (key == curr->key) {
// LeaveCriticalSection(&glock);
return false;
} else {
NODE *node = new NODE(key);
node->next = curr;
pred->next = node;
// LeaveCriticalSection(&glock);
return true;
}
}

bool Remove(int key)
{
NODE *pred, *curr;

pred = &head;
// EnterCriticalSection(&glock);
curr = pred->next;
while (curr->key < key) {
pred = curr;
curr = curr->next;
}

if (key == curr->key) {
pred->next = curr->next;
delete curr;
// LeaveCriticalSection(&glock);
return true;
} else {
// LeaveCriticalSection(&glock);
return false;
}
}

bool Contains(int key)
{
NODE *pred, *curr;

pred = &head;
// EnterCriticalSection(&glock);
curr = pred->next;
while (curr->key < key) {
pred = curr;
curr = curr->next;
}
if (key == curr->key) {
// LeaveCriticalSection(&glock);
return true;
} else {
// LeaveCriticalSection(&glock);
return false;
}
}

};


class FLIST {
NODE head, tail;

public:
FLIST()
{
head.key = 0x80000000;
tail.key = 0x7FFFFFFF;
head.next = &tail;
}
~FLIST() {}

void Init()
{
NODE *ptr;
while(head.next != &tail) {
ptr = head.next;
head.next = head.next->next;
delete ptr;
}
}

bool Add(int key)
{
NODE *pred, *curr;

pred = &head;
pred->Lock();
curr = pred->next;
curr->Lock();
while (curr->key < key) {
pred->Unlock();
pred = curr;
curr = curr->next;
curr->Lock();
}

if (key == curr->key) {
curr->Unlock();
pred->Unlock();
return false;
} else {
NODE *node = new NODE(key);
node->next = curr;
pred->next = node;
curr->Unlock();
pred->Unlock();
return true;
}
}

bool Remove(int key)
{
NODE *pred, *curr;

pred = &head;
pred->Lock();
curr = pred->next;
curr->Lock();
while (curr->key < key) {
pred->Unlock();
pred = curr;
curr = curr->next;
curr->Lock();
}

if (key == curr->key) {
pred->next = curr->next;
//curr->Unlock();
pred->Unlock();
delete curr;
return true;
} else {
curr->Unlock();
pred->Unlock();
return false;
}
}

bool Contains(int key)
{
NODE *pred, *curr;

pred = &head;
pred->Lock();
curr = pred->next;
curr->Lock();
while (curr->key < key) {
pred->Unlock();
pred = curr;
curr = curr->next;
curr->Lock();
}

if (key == curr->key) {
curr->Unlock();
pred->Unlock();
return true;
} else {
curr->Unlock();
pred->Unlock();
return false;
}
}

};



class OLIST {
NODE head, tail;

public:
OLIST()
{
head.key = 0x80000000;
tail.key = 0x7FFFFFFF;
head.next = &tail;
}
~OLIST() {}

void Init()
{
NODE *ptr;
while(head.next != &tail) {
ptr = head.next;
head.next = head.next->next;
delete ptr;
}
}

bool validate(NODE *pred, NODE *curr)
{
NODE *node = &head;

while(node->key < pred->key) node = node->next;
if (pred != node) return false;
return (pred->next == curr);
}

bool Add(int key)
{
NODE *pred, *curr;

while(true) {
pred = &head;
curr = pred->next;
while (curr->key < key) {
pred = curr;
curr = curr->next;
}

pred->Lock(); curr->Lock();
if (!validate(pred, curr)) {
curr->Unlock();
pred->Unlock();
continue;
}

if (key == curr->key) {
curr->Unlock();
pred->Unlock();
return false;
} else {
NODE *node = new NODE(key);
node->next = curr;
pred->next = node;
curr->Unlock();
pred->Unlock();
return true;
}
}
}

bool Remove(int key)
{
NODE *pred, *curr;

while(true) {
pred = &head;
curr = pred->next;
while (curr->key < key) {
pred = curr;
curr = curr->next;
}

pred->Lock(); curr->Lock();
if (!validate(pred, curr)) {
curr->Unlock();
pred->Unlock();
continue;
}

if (key == curr->key) {
pred->next = curr->next;
curr->Unlock();
pred->Unlock();
return true;
} else {
curr->Unlock();
pred->Unlock();
return false;
}
}
}

bool Contains(int key)
{
NODE *pred, *curr;

while(true) {
pred = &head;
curr = pred->next;
while (curr->key < key) {
pred = curr;
curr = curr->next;
}

pred->Lock(); curr->Lock();
if (!validate(pred, curr)) {
curr->Unlock();
pred->Unlock();
continue;
}
if (key == curr->key) {
curr->Unlock();
pred->Unlock();
return true;
} else {
curr->Unlock();
pred->Unlock();
return false;
}
}
}

};



class ZLIST {
NODE head, tail;

public:
ZLIST()
{
head.key = 0x80000000;
tail.key = 0x7FFFFFFF;
head.next = &tail;
}
~ZLIST() {}

void Init()
{
NODE *ptr;
while(head.next != &tail) {
ptr = head.next;
head.next = head.next->next;
delete ptr;
}
}

bool validate(NODE *pred, NODE *curr)
{
return (!pred->deleted) && (!curr->deleted) && (pred->next == curr);
}

bool Add(int key)
{
NODE *pred, *curr;

while(true) {
pred = &head;
curr = pred->next;
while (curr->key < key) {
pred = curr;
curr = curr->next;
}

pred->Lock(); curr->Lock();
if (!validate(pred, curr)) {
curr->Unlock();
pred->Unlock();
continue;
}

if (key == curr->key) {
curr->Unlock();
pred->Unlock();
return false;
} else {
NODE *node = new NODE(key);
node->next = curr;
pred->next = node;
curr->Unlock();
pred->Unlock();
return true;
}
}
}

bool Remove(int key)
{
NODE *pred, *curr;

while(true) {
pred = &head;
curr = pred->next;
while (curr->key < key) {
pred = curr;
curr = curr->next;
}

pred->Lock(); curr->Lock();
if (!validate(pred, curr)) {
curr->Unlock();
pred->Unlock();
continue;
}

if (key == curr->key) {
curr->deleted = true;
pred->next = curr->next;
curr->Unlock();
pred->Unlock();
return true;
} else {
curr->Unlock();
pred->Unlock();
return false;
}
}
}

bool Contains(int key)
{
NODE *curr;

curr = head.next;
while (curr->key < key) curr = curr->next;
return (curr->key == key) && (!curr->deleted);
}

};



class LFLIST {
LFNODE head, tail;

public:
LFLIST()
{
head.key = 0x80000000;
tail.key = 0x7FFFFFFF;
head.next = &tail;
}
~LFLIST() {}

void Init()
{
LFNODE *ptr;
while(head.next != &tail) {
ptr = head.next;
head.next = head.next->GetReference();
delete ptr;
}
}

void Find(LFNODE **pred, LFNODE **curr, int key)
{
while(true) {
restart:
*pred = &head;
*curr = (*pred)->GetReference();
while(true) {
bool marked;
LFNODE *succ = (*curr)->Get(&marked);

while(marked) {
bool snip = (*pred)->CAS((*curr), succ, false, false);
if (!snip) goto restart;
(*curr) = succ;
succ = (*curr)->Get(&marked);
}

if ((*curr)->key >= key) return;
(*pred) = (*curr);
(*curr) = succ;
}
}
}

bool Add(int key)
{
LFNODE *pred, *curr;

while( true) {
Find( &pred, &curr, key);
if( curr->key == key) {
return false;
} else {
LFNODE *node = new LFNODE( key);
node->next = curr;
if( pred->CAS( curr, node, false, false))
return true;
}
}
}

bool Remove(int key)
{
LFNODE *pred, *curr, *succ;
bool snip;

while( true) {
Find( &pred, &curr, key);
if( curr->key != key) {
return false;
} else {
succ = curr->next;
snip = curr->AttemptMark( curr->next, true);
if( !snip)
continue;
pred->CAS( curr, succ, false, false);
return true;
}
}
}

bool Contains(int key)
{
LFNODE *curr;
bool marked;

curr = &head;
while( curr->key < key) {
curr = curr->Get( &marked);
}
return ( curr->key == key && ! marked);
}
};













#define NUM_TEST 400000
#define KEY_RANGE 1000
CLIST clist; FLIST flist; OLIST olist; ZLIST zlist; LFLIST lflist;

DWORD WINAPI ThreadFunc(LPVOID lpVoid)
{
int key;

for (int i=0;i < NUM_TEST / num_of_threads;i++) {
switch (rand() % 3) {
case 0: key = rand() % KEY_RANGE;
//clist.Add(key);
//flist.Add(key);
//olist.Add(key);
//zlist.Add(key);
lflist.Add(key);
break;
case 1: key = rand() % KEY_RANGE;
//clist.Remove(key);
//flist.Remove(key);
//olist.Remove(key);
//zlist.Remove(key);
lflist.Remove(key);
break;
case 2 : key = rand() % KEY_RANGE;
//clist.Contains(key);
//flist.Contains(key);
//olist.Contains(key);
//zlist.Contains(key);
lflist.Contains(key);
break;
default : printf("Error\n");
exit(-1);
}}}


int main()
{
HANDLE threads[64];

QueryPerformanceFrequency(&freq);
for (num_of_threads = 1; num_of_threads <=8 ; num_of_threads *= 2) {
clist.Init(); flist.Init(); olist.Init(); zlist.Init(); lflist.Init();
QueryPerformanceCounter(&start);
for(int i=0;i threads[i] = CreateThread(NULL, 0, ThreadFunc, NULL, 0, NULL);
for(int i=0;i WaitForSingleObject(threads[i], INFINITE);
QueryPerformanceCounter(&end);
for(int i=0;i CloseHandle(threads[i]);
int dur = (int)((end.QuadPart - start.QuadPart) / (freq.QuadPart / 1000));
printf("%d threads, %dms\n", num_of_threads, dur);
}

getchar();
return 0;
}