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

[Darren G. <dg...@ke...>]

Thanks all for the info.

I have switched the set out with an unordered vector and will say how 
that affects things. There are at most only a handful of active 
objects per tile.

Cheers,
Darren Grant



At 05:07 AM 3/23/2010, you wrote:
>On 23-3-2010 10:34, Fabian Giesen wrote:
> > Jon Watte schrieb:
> >
> >> <snip>
> >> If you have buckets with zillions of items (a bad idea for other
> >> reasons) and need to delete from the middle, try a std::list<>  with a
> >> custom allocator, or as others have said std::hash_map or similar.
> >>
> > Linked lists enforce a particular order. Whenever you have something
> > that is just a "bucket of things" with no particular ordering
> > requirements, a good option is to just use a std::vector<>  (or, more
> > generally, any array - this is not STL specific). To insert, you always
> > use push_back. To remove a given item "x", you do:
> >
> >     std::swap(x, container.back());
> >     container.pop_back();
> >
> > This doesn't preserve order, but it's simple, short and fast: insertion
> > is amortized O(1) with std::vector semantics, and removal is guaranteed
> > O(1).
>
>I totally agree. Even with a custom allocator an std::list breaks cache
>coherence and simply has too much overhead. I would not use std::swap
>though, since x is a goner so no need to save it to back(). Instead do
>
>std::vector<Entry>::iterator it;
>
>...
>
>Entry&  x = *it; //  it points to the item that needs to be destroyed, e.g.
>
>                          // it = std::find(container.begin(), 
> container.end(), victim);
>
>x = container.back();
>
>container.pop_back();
>
>
>This saves you two writes since std::swap needs to create a temporary to
>hold one of the swapped values. The extra writes are better avoided if
>the size of Entry is huge or if it holds shared pointers.
>
>
> >   STL also offers this as an algorithm: there's std::remove and
> > std::remove_if. Their usage is somewhat nonobvious: you do
> >
> >     container.erase(std::remove(start, end), container.end());
> >
> > to remove everything in [start,end) in a "non-order-preserving" way, and
> > similar with remove_if which uses a predicate.
> >
> > -Fabian
> >
> >
> >
>
>I think you mean
>
>container.erase(std::remove(start, end, value), container.end());
>
>
>since the STL remove takes three parameters. Furthermore std::remove
>keeps the relative order intact.
>http://www.cplusplus.com/reference/algorithm/remove/
>At least, that is what I see in Visual C++ 8.0 (Sometimes they do adhere
>to standards ;) Removing all values and leaving an unordered sequence
>can be done using
>
>std::vector<Entry>::iterator it = container.begin(), last = container.end();
>
>while (it != last)
>
>{
>      if (*it == value)
>
>      {
>
>          --last;
>          *it = *last;
>      }
>      else
>      {
>          ++it;
>      }
>}
>
>container.erase(last, container.end());
>
>
>Gino
>
>
>
>
>
>
>
>
>------------------------------------------------------------------------------
>Download Intel&#174; Parallel Studio Eval
>Try the new software tools for yourself. Speed compiling, find bugs
>proactively, and fine-tune applications for parallel performance.
>See why Intel Parallel Studio got high marks during beta.
>http://p.sf.net/sfu/intel-sw-dev
>_______________________________________________
>GDAlgorithms-list mailing list
>GDA...@li...
>https://lists.sourceforge.net/lists/listinfo/gdalgorithms-list
>Archives:
>http://sourceforge.net/mailarchive/forum.php?forum_name=gdalgorithms-list

Darren Grant
Technical Director
http://www.kerberos-productions.com/