Re: [Algorithms] Cache-coherent hashing for broad-phase collision detection

[Sebastian S. <seb...@gm...>]

On Mon, Mar 22, 2010 at 9:49 PM, Darren Grant <
dg...@ke...> wrote:

> Hi,
>
> I am looking at ways of improving cache coherence for a typical
> broad-phase collision detection scenario (cpu).  The basic
> implementation utilizes these data structures:
>
>        struct ObjectTracking {
>                int ObjectIndex;
>                int RefCount;
>        };
>
>        typedef set<ObjectTracking> Tile;
>
>        struct TilingLevel {
>                vector<Tile> Tiles;
>                int Pitch;
>                Tile& Map(int x, int y) { return Tiles[y*Pitch+x]; }
>        };
>
>        struct TilingHierarchy {
>                vector<TilingLevel> TilingLevels;
>                Tile& Map(int level, int x, int y)  { return
> TilingLevels[level].Map(x,y); }
>        };
>
>
> And the hot process involves frequent iteration of:
>
>        for level from 0 to maxlevel
>        for y from y0(level) to y1(level)
>        for x from x0(level) to x1(level)
>                tilingHierarchy.Map(level,x,y).InsertOrRemove();
>
>
> Performance becomes an issue here when the std::set allocations get
> spread out across process memory.  I will therefore replace
> individual sets with a single shared map to explore implementations
> for coherence:
>
>        (level,x,y,ObjectIndex)->(RefCount).
>
>
> (level,x,y,ObjectIndex) has simple perfect hash functions since the
> boundary conditions are known at start.  Local memory access roughly
> favours tiling levels > tiling level > tile row > tile according to
> the given code, but I am wary of less obvious yet still important
> observations that may be missed.
>
>
> Does this sound about right?  Are there any better options I have
> flown right past?
>
> Thank you.


Try a single hash table (multimap) mapping from the cell position to objects
in that cell position? You could try open adressing to get rid of pointers
altogether and have just a single flat array at the bottom of your data
structure, although that has limitations (difficulty deleting, less than
gracious performance degradation as the load factor grows).

-- 
Sebastian Sylvan