From: <ole...@us...> - 2007-12-21 12:14:25
|
Revision: 1338 http://opende.svn.sourceforge.net/opende/?rev=1338&view=rev Author: oleh_derevenko Date: 2007-12-21 04:14:27 -0800 (Fri, 21 Dec 2007) Log Message: ----------- Change: Radix sort helper buffers moved from globals to SAPSpace members to allow multithreaded use. Modified Paths: -------------- trunk/ode/src/collision_sapspace.cpp Modified: trunk/ode/src/collision_sapspace.cpp =================================================================== --- trunk/ode/src/collision_sapspace.cpp 2007-12-21 12:10:31 UTC (rev 1337) +++ trunk/ode/src/collision_sapspace.cpp 2007-12-21 12:14:27 UTC (rev 1338) @@ -41,14 +41,83 @@ #include "collision_kernel.h" #include "collision_space_internal.h" -// OPCODE's Radix Sorting, returns a list of indices in sorted order -static const uint32* RadixSort( const float* input2, uint32 nb ); // Reference counting helper for radix sort global data. static void RadixSortRef(); static void RadixSortDeref(); // -------------------------------------------------------------------------- +// Radix Sort Context +// -------------------------------------------------------------------------- + +struct RaixSortContext +{ +public: + RaixSortContext(): mCurrentSize(0), mRanksValid(false), mRanks1(NULL), mRanks2(NULL) {} + ~RaixSortContext() { FreeRanks(); } + + // OPCODE's Radix Sorting, returns a list of indices in sorted order + const uint32* RadixSort( const float* input2, uint32 nb ); + +private: + void FreeRanks(); + void AllocateRanks(size_t nNewSize); + + void ReallocateRanksIfNecessary(size_t nNewSize); + +private: + inline void SetCurrentSize(size_t nValue) { mCurrentSize = nValue; } + inline size_t GetCurrentSize() const { return mCurrentSize; } + + inline bool AreRanksValid() const { return mRanksValid; } + inline void InvalidateRanks() { mRanksValid = false; } + inline void ValidateRanks() { mRanksValid = true; } + +private: + size_t mCurrentSize; //!< Current size of the indices list + bool mRanksValid; + uint32* mRanks1; //!< Two lists, swapped each pass + uint32* mRanks2; +}; + +void RaixSortContext::AllocateRanks(size_t nNewSize) +{ + dIASSERT(GetCurrentSize() == 0); + + mRanks1 = new uint32[2 * nNewSize]; + mRanks2 = mRanks1 + nNewSize; + + SetCurrentSize(nNewSize); +} + +void RaixSortContext::FreeRanks() +{ + SetCurrentSize(0); + + delete[] mRanks1; + //delete[] mRanks2; -- mRanks2 points to the same buffer as mRanks1 +} + +void RaixSortContext::ReallocateRanksIfNecessary(size_t nNewSize) +{ + size_t nCurSize = GetCurrentSize(); + + if (nNewSize != nCurSize) + { + if ( nNewSize > nCurSize ) + { + // Free previously used ram + FreeRanks(); + + // Get some fresh one + AllocateRanks(nNewSize); + } + + InvalidateRanks(); + } +} + +// -------------------------------------------------------------------------- // SAP space code // -------------------------------------------------------------------------- @@ -126,6 +195,7 @@ // pruning position array scratch pad // NOTE: this is float not dReal because of the OPCODE radix sorter dArray< float > poslist; + RaixSortContext sortContext; }; // Creation @@ -138,11 +208,11 @@ #define GEOM_ENABLED(g) ((g)->gflags & GEOM_ENABLED) -// HACK: We abuse 'next' and 'tome' members of dxGeom to store indices into dirty/geom lists. -#define GEOM_SET_DIRTY_IDX(g,idx) { g->next = (dxGeom*)(size_t)(idx); } -#define GEOM_SET_GEOM_IDX(g,idx) { g->tome = (dxGeom**)(size_t)(idx); } -#define GEOM_GET_DIRTY_IDX(g) ((int)(size_t)g->next) -#define GEOM_GET_GEOM_IDX(g) ((int)(size_t)g->tome) +// HACK: We abuse 'next' and 'tome' members of dxGeom to store indice into dirty/geom lists. +#define GEOM_SET_DIRTY_IDX(g,idx) { (g)->next = (dxGeom*)(size_t)(idx); } +#define GEOM_SET_GEOM_IDX(g,idx) { (g)->tome = (dxGeom**)(size_t)(idx); } +#define GEOM_GET_DIRTY_IDX(g) ((int)(size_t)(g)->next) +#define GEOM_GET_GEOM_IDX(g) ((int)(size_t)(g)->tome) #define GEOM_INVALID_IDX (-1) @@ -192,9 +262,6 @@ ax0idx = ( ( axisorder ) & 3 ) << 1; ax1idx = ( ( axisorder >> 2 ) & 3 ) << 1; ax2idx = ( ( axisorder >> 4 ) & 3 ) << 1; - - // We want the Radix sort to stick around. - RadixSortRef(); } dxSAPSpace::~dxSAPSpace() @@ -210,9 +277,6 @@ for ( ; DirtyList.size(); remove( DirtyList[ 0 ] ) ) {} for ( ; GeomList.size(); remove( GeomList[ 0 ] ) ) {} } - - // We're done with the Radix sorter - RadixSortDeref(); } dxGeom* dxSAPSpace::getGeom( int i ) @@ -449,10 +513,10 @@ // NOTE: uses floats instead of dReals because that's what radix sort wants for( int i = 0; i < count; ++i ) poslist[ i ] = (float)TmpGeomList[i]->aabb[ ax0idx ]; - poslist[ count++ ] = FLT_MAX; + poslist[ count++ ] = FLT_MAX; // 2) Sort the list - const uint32* Sorted = RadixSort( poslist.data(), count ); + const uint32* Sorted = sortContext.RadixSort( poslist.data(), count ); // 3) Prune the list const uint32* const LastSorted = Sorted + count; @@ -498,44 +562,8 @@ // Radix Sort //------------------------------------------------------------------------------ -#define INVALIDATE_RANKS mCurrentSize|=0x80000000 -#define VALIDATE_RANKS mCurrentSize&=0x7fffffff -#define CURRENT_SIZE (mCurrentSize&0x7fffffff) -#define INVALID_RANKS (mCurrentSize&0x80000000) -static int radixsort_ref = 0; // Reference counter -static uint32 mCurrentSize; //!< Current size of the indices list -static uint32* mRanks1; //!< Two lists, swapped each pass -static uint32* mRanks2; -static void RadixSortRef() -{ - if ( radixsort_ref == 0 ) - { - mRanks1 = NULL; - mRanks2 = NULL; - INVALIDATE_RANKS; - } - - ++radixsort_ref; -} - -static void RadixSortDeref() -{ - --radixsort_ref; - - if ( radixsort_ref == 0 ) - { - // Release everything - if ( mRanks1 ) { delete[] mRanks1; mRanks1 = NULL; } - if ( mRanks2 ) { delete[] mRanks2; mRanks2 = NULL; } - - // Allow us to restart - mCurrentSize = 0; - INVALIDATE_RANKS; - } -} - #define CHECK_PASS_VALIDITY(pass) \ /* Shortcut to current counters */ \ uint32* CurCount = &mHistogram[pass<<8]; \ @@ -558,30 +586,13 @@ if(CurCount[UniqueVal]==nb) PerformPass=false; // WARNING ONLY SORTS IEEE FLOATING-POINT VALUES -static const uint32* RadixSort( const float* input2, uint32 nb ) +const uint32* RaixSortContext::RadixSort( const float* input2, uint32 nb ) { uint32* input = (uint32*)input2; // Resize lists if needed - uint32 CurSize = CURRENT_SIZE; - if ( nb != CurSize ) - { - // Grow? - if ( nb > CurSize ) - { - // Free previously used ram - delete[] mRanks2; - delete[] mRanks1; + ReallocateRanksIfNecessary(nb); - // Get some fresh one - mRanks1 = new uint32[nb]; - mRanks2 = new uint32[nb]; - } - - mCurrentSize = nb; - INVALIDATE_RANKS; - } - // Allocate histograms & offsets on the stack uint32 mHistogram[256*4]; uint32* mLink[256]; @@ -608,7 +619,7 @@ bool AlreadySorted = true; /* Optimism... */ - if(INVALID_RANKS) + if (!AreRanksValid()) { /* Prepare for temporal coherence */ float* Running = (float*)input2; @@ -696,10 +707,14 @@ // Perform Radix Sort uint8* InputBytes = (uint8*)input; InputBytes += j; - if(INVALID_RANKS) + if (!AreRanksValid()) { - for(uint32 i=0;i<nb;i++) *mLink[InputBytes[i<<2]]++ = i; - VALIDATE_RANKS; + for(uint32 i=0;i<nb;i++) + { + *mLink[InputBytes[i<<2]]++ = i; + } + + ValidateRanks(); } else { @@ -733,7 +748,7 @@ for(uint32 i=128;i<256;i++) mLink[i] += CurCount[i]; // Fixing the wrong place for negative values // Perform Radix Sort - if(INVALID_RANKS) + if (!AreRanksValid()) { for(uint32 i=0;i<nb;i++) { @@ -742,7 +757,8 @@ if(Radix<128) *mLink[Radix]++ = i; // Number is positive, same as above else *(--mLink[Radix]) = i; // Number is negative, flip the sorting order } - VALIDATE_RANKS; + + ValidateRanks(); } else { @@ -762,11 +778,15 @@ // The pass is useless, yet we still have to reverse the order of current list if all values are negative. if(UniqueVal>=128) { - if(INVALID_RANKS) + if (!AreRanksValid()) { // ###Possible? - for(uint32 i=0;i<nb;i++) mRanks2[i] = nb-i-1; - VALIDATE_RANKS; + for(uint32 i=0;i<nb;i++) + { + mRanks2[i] = nb-i-1; + } + + ValidateRanks(); } else { This was sent by the SourceForge.net collaborative development platform, the world's largest Open Source development site. |