|
From: <axl...@us...> - 2010-11-21 19:38:25
|
Revision: 769
http://hgengine.svn.sourceforge.net/hgengine/?rev=769&view=rev
Author: axlecrusher
Date: 2010-11-21 19:38:18 +0000 (Sun, 21 Nov 2010)
Log Message:
-----------
use lock free stack to reduce locks in MercuryMemory to near zero
Modified Paths:
--------------
Mercury2/src/MSemaphore.h
Mercury2/src/MercuryMemory.h
Added Paths:
-----------
Mercury2/src/MStack.h
Modified: Mercury2/src/MSemaphore.h
===================================================================
--- Mercury2/src/MSemaphore.h 2010-11-21 14:22:34 UTC (rev 768)
+++ Mercury2/src/MSemaphore.h 2010-11-21 19:38:18 UTC (rev 769)
@@ -19,6 +19,12 @@
#define COMPARE_AND_SWAP(d,o,n) ((uint32_t)InterlockedCompareExchange(d, n, o))
#define SYNC_AND_AND_FETCH(d,v) ((uint32_t)__sync_and_and_fetch(d,v))
+inline void* CAS_PTR(volatile void** d, void* e, void* c)
+{
+ //these variables must be 32 bit aligned on x86 and 64 bit aligned on x64
+ return InterlockedCompareExchangePointer((volatile PVOID*)d,e,c);
+}
+
#endif
class MSemaphore
Added: Mercury2/src/MStack.h
===================================================================
--- Mercury2/src/MStack.h (rev 0)
+++ Mercury2/src/MStack.h 2010-11-21 19:38:18 UTC (rev 769)
@@ -0,0 +1,117 @@
+#ifndef MSTACK_H
+#define MSTACK_H
+
+#include <MSemaphore.h>
+
+template <typename T>
+class MStack
+{
+ private:
+ struct Container
+ {
+ Container()
+ :m_next(NULL)
+ { }
+ T m_data;
+ volatile Container* m_next;
+ };
+
+ volatile Container* m_head;
+ volatile Container* m_freeContainers;
+
+ // use instead of calling new Container()
+ Container* GetContainer()
+ {
+ Container* a = (Container*)m_freeContainers;
+ if (a==NULL) return new Container(); //make new container, don't care if a has changed since read
+ if ( CAS_PTR((volatile void**)&m_freeContainers,(void*)a->m_next,a)==a ) //true if swap made
+ return a;
+ return new Container();
+ }
+
+ //use instead of calling delete Container
+ void SaveContainerForFuture(Container* c)
+ {
+ do
+ {
+ c->m_next = m_freeContainers;
+ }
+ while( CAS_PTR((volatile void**)&m_freeContainers,c,(void*)c->m_next)!=c->m_next );
+ }
+
+ public:
+ MStack()
+ :m_head(NULL), m_freeContainers(NULL)
+ {
+ }
+
+ void push(const T& data)
+ {
+ Container* a = GetContainer();
+ a->m_data = data;
+ do
+ {
+ a->m_next = m_head;
+ } while ( CAS_PTR((volatile void**)&m_head,a,(void*)a->m_next)!=a->m_next );
+ }
+
+ bool pop()
+ {
+ if (m_head==NULL) return false;
+ Container* a = NULL;
+ do
+ {
+ a = m_head;
+ } while ( CAS_PTR((volatile void**)&m_head,(void*)a->m_next,a)!=a );
+ SaveContainerForFuture(a);
+ return true;
+ }
+
+ bool pop_get(T& d)
+ {
+ if (m_head==NULL) return false;
+ Container* a = NULL;
+ do
+ {
+ a = (Container*)m_head;
+ } while ( CAS_PTR((volatile void**)&m_head,(void*)a->m_next,a)!=a );
+ d = a->m_data;
+ SaveContainerForFuture(a);
+ return true;
+ }
+
+ inline bool empty() const { return m_head==NULL; }
+};
+
+#endif
+/****************************************************************************
+ * Copyright (C) 2010 by Joshua Allen *
+ * *
+ * *
+ * All rights reserved. *
+ * *
+ * Redistribution and use in source and binary forms, with or without *
+ * modification, are permitted provided that the following conditions *
+ * are met: *
+ * * Redistributions of source code must retain the above copyright *
+ * notice, this list of conditions and the following disclaimer. *
+ * * Redistributions in binary form must reproduce the above *
+ * copyright notice, this list of conditions and the following *
+ * disclaimer in the documentation and/or other materials provided *
+ * with the distribution. *
+ * * Neither the name of the Mercury Engine nor the names of its *
+ * contributors may be used to endorse or promote products derived *
+ * from this software without specific prior written permission. *
+ * *
+ * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS *
+ * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT *
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR *
+ * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT *
+ * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, *
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT *
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, *
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY *
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT *
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE *
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. *
+ ***************************************************************************/
Modified: Mercury2/src/MercuryMemory.h
===================================================================
--- Mercury2/src/MercuryMemory.h 2010-11-21 14:22:34 UTC (rev 768)
+++ Mercury2/src/MercuryMemory.h 2010-11-21 19:38:18 UTC (rev 769)
@@ -5,6 +5,8 @@
#include <list>
#include <MSemaphore.h>
+#include <MStack.h>
+
///Memory holder for matrices
template <typename T>
class MercuryMemory
@@ -14,105 +16,37 @@
free ride into the CPU cache. */
public:
MercuryMemory(const uint32_t rows)
- :m_freeMem(NULL),m_freeUnit(NULL),m_rows(rows)
+ :m_rows(rows)
{
-// m_lock.Wait();
AllocateMoreSpace(m_rows);
-// m_lock.UnLock();
}
T* Allocate()
{
T* m = NULL;
- MemoryUnit* mu = NULL;
- //keep really short lock
- m_lock.Wait();
- if ( m_freeMem == NULL ) m_freeMem = AllocateMoreSpace(m_rows);
-
- //get record of free memory spot
- mu = m_freeMem;
- m_freeMem=m_freeMem->prev;
- m = (T*)mu->mem;
-
- SaveFreeUnit(mu);
- m_lock.UnLock();
-// delete mu;
-
-// if (m==NULL) { char* a = NULL; *a=0; } //no memory allocated??
+ while ( !m_freeData.pop_get(m) ) AllocateMoreSpace(m_rows);
return m;
}
- void Free(T* m)
- {
- m_lock.Wait();
-// for (MemoryUnit* mu=m_freeMem;mu!=NULL;mu=mu->prev)
-// {
- //probably could some some sorting here to get contigious free and used memory
- //if free memory is alwasy given out in order, then used memory will also be in order
-// if (m==mu->mem) { char* a=NULL;*a=0;} //WTF DOUBLE FREE
-// }
-// m_freeMem = new MemoryUnit(m_freeMem,m);
+ inline void Free(T* m) { m_freeData.push(m); }
-/*
- MemoryUnit* mu = m_freeUnit;
- m_freeUnit = m_freeUnit->prev; //set top free unit to next free unit
- //setup unit and add it to the top of the free memory
- mu->prev = m_freeMem;
- mu->mem = m;
-*/ TakeFreeUnit(m);
-
- m_lock.UnLock();
- }
-
private:
- struct MemoryUnit
- {
- MemoryUnit(MemoryUnit* p, void* m)
- :mem(m),prev(p)
- {
-// if (p!=NULL) p->next = this;
- }
-// T* mem;
- void* mem;
- MemoryUnit* prev;
- };
- MemoryUnit* AllocateMoreSpace(const uint32_t rows)
+ void AllocateMoreSpace(const uint32_t rows)
{
- MemoryUnit* mu = NULL;
-
AlignedBuffer<T>* d = new AlignedBuffer<T>();
d->Allocate(rows,16);
- m_lock.Wait();
+ m_lock.Wait(); //required
m_data.push_back(d);
- m_lock.UnLock();
+ m_lock.UnLock(); //required
for (unsigned int i = 0; i < rows;i++)
- mu = new MemoryUnit(mu,(d->Buffer())+i);
- return mu;
+ m_freeData.push(d->Buffer()+i);
}
- inline void TakeFreeUnit(T* m)
- {
- MemoryUnit* mu = m_freeUnit;
- m_freeUnit = m_freeUnit->prev; //set top free unit to next free unit
- //setup unit and add it to the top of the free memory
- mu->prev = m_freeMem;
- mu->mem = m;
- m_freeMem = mu;
- }
-
- void SaveFreeUnit(MemoryUnit* mu)
- {
- mu->mem = NULL;
- mu->prev = m_freeUnit;
- m_freeUnit = mu;
- }
-
std::list< AlignedBuffer<T>* > m_data;
- MemoryUnit* m_freeMem; //Free template memory
- MemoryUnit* m_freeUnit; //Free MemoryUnits, for when
+ MStack< T* > m_freeData;
MSemaphore m_lock;
unsigned long m_rows;
This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site.
|