Click here to Skip to main content
Click here to Skip to main content
Add your own
alternative version

Testing simple concurrent containers

, 25 Oct 2009 CPOL
This article illustrates simple approaches and test results when creating containers with concurrent flavor and running on a multi-core PC.
container_locks.zip
Container_locks
src
Testing_simple_concurrent_containers.pdf
VC9
container_locks.vcproj.val-PC.val.user
Debug
tbb_debug.dll
Debug64
tbb_debug.dll
Release
tbb.dll
Release64
tbb.dll
/*
Copyright (c) 2009 Valery Grebnev.
CPOL (Code Project Open License) Licensed http://www.codeproject.com/info/cpol10.aspx
*/
#pragma once
#include "interlocked.h"


template <typename Entry_t, size_t pool_size> 
class CACHE_ALIGN Pool_t
{
public:
	inline size_t pop(void)
	{
		List_entry* pentry = static_cast<List_entry*>(interlocked_pop_entry_slist(&m_head));
		return (pentry)? pentry->m_index + 1 : 0 /* 0 = error */;
	}
	inline void push(size_t index)
	{
		List_entry* pentry = &m_pool[index-1].m_list_entry;
		interlocked_push_entry_slist(&m_head, pentry);
	}
	inline Entry_t* get(size_t index)
	{
		return (index /* 0 = error */)? &m_pool[index-1].m_value:NULL;
	}
	Pool_t()
	{
		::InitializeSListHead(&m_head);
		for(size_t i = 0; i < pool_size; i++)
		{
			m_pool[i].m_list_entry.m_index = i;
			interlocked_push_entry_slist(&m_head, &m_pool[i].m_list_entry);
		}
	}
	virtual ~Pool_t()
	{
	}
private:

	typedef SLIST_HEADER CACHE_ALIGN SLIST_HEADER_;
	struct CACHE_ALIGN List_entry: public SLIST_ENTRY
	{
		size_t m_index;
	};
	
	struct CACHE_ALIGN
	_Internal_entry_t
	{
		CACHE_PADDING(1);
		List_entry m_list_entry;
		Entry_t m_value;
	};


	CACHE_PADDING(1);
	_Internal_entry_t CACHE_ALIGN m_pool[pool_size];

	CACHE_PADDING(2);
	SLIST_HEADER_ m_head;
};

#define NUMBER_OF_POOLS 4  /*for a Quad-core PC*/

template <typename Entry_t, size_t pool_size, size_t number_of_pools = NUMBER_OF_POOLS> 
class CACHE_ALIGN Array_of_pools_t
{
public:
	inline size_t pop()
	{
		return pop(::GetCurrentProcessorNumber() % number_of_pools);
	}
	inline void push(size_t entry_index)
	{
		size_t pool_index = (entry_index-1)/pool_size;
		m_pools[pool_index].push(entry_index - pool_index*pool_size);
	}
	inline Entry_t* get(size_t entry_index)
	{
		size_t pool_index = (entry_index -1)/pool_size;
		return m_pools[pool_index].get(entry_index - pool_index*pool_size);
	}

private:
	inline size_t pop(size_t pool_index)
	{
		return (pool_index * pool_size + m_pools[pool_index].pop());
	}
	Pool_t<Entry_t, pool_size> m_pools[number_of_pools];
};

template <typename Entry_t, WORD number_of_threads,	const size_t pool_size = (2*number_of_threads-1)> 
class CACHE_ALIGN Pool_of_shared_elements : private Array_of_pools_t<Entry_t, pool_size>
{
public:
	WORD pop(volatile LONG& reference_counter)
	{
		LONG i;
		LONG j;
		LONG exch_counter;

		WORD new_index = static_cast<WORD>(__super::pop());

		if (new_index == 0)
		{
			return 0; /* error */ 
		}
		else
		{
		}

		j = acquire_read(reference_counter);
		do
		{
			exch_counter = (HIWORD(j) == 0)? ((LONG)new_index << 16) | (LOWORD(j) + 1) : j + 1;
			i = j;
			j = acquire_interlocked_compare_exchange(&reference_counter,
							exch_counter,
							i);
			PAUSE

		} while(i != j);

		WORD index = HIWORD(exch_counter); 

		if ( index != new_index)
		{
			__super::push( new_index );
		}
		else
		{
		}

		return index;
	}

	void push(WORD index, volatile LONG& reference_counter)
	{
		LONG counter = interlocked_decrement_release(&reference_counter);
		if (LOWORD(counter) == 0)
		{
			if ( counter == acquire_interlocked_compare_exchange(&reference_counter, 0x0, counter))
			{
				__super::push( index );
			}
			else
			{
			}
		}
		else
		{
		}
	}

	inline Entry_t* get(WORD index)
	{
		return __super::get(index);
	}
};

By viewing downloads associated with this article you agree to the Terms of Service and the article's licence.

If a file you wish to view isn't highlighted, and is a text file (not binary), please let us know and we'll add colourisation support for it.

License

This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)

Share

About the Author

Valery Grebnev
Software Developer
Canada Canada
No Biography provided

| Advertise | Privacy | Terms of Use | Mobile
Web04 | 2.8.150327.1 | Last Updated 25 Oct 2009
Article Copyright 2009 by Valery Grebnev
Everything else Copyright © CodeProject, 1999-2015
Layout: fixed | fluid