From: John Peterson <jwpeterson@gm...>  20110505 18:56:49

On Wed, May 4, 2011 at 6:35 PM, John Peterson <jwpeterson@...> wrote: > The answer is: "Not bad, but we could do way better!" > > The plot_key_test.pdf figure attached to this mail shows the worst and > average case number of entries in each hash bucket (which I called > collisions for lack of a better term) of our current hashes for > "build_cube" meshes of Hexes, Tets, and Quads of varying size. > > Note that a "perfect" hash in this case would have 2 entries in each > bucket for a given side key: one for each element adjacent to that > side. > > The graphs count *all* entries in the bucket (and each actual side is > in the bucket twice) but the trends are clear. > > Using the simple hash function available at > http://burtleburtle.net/bob/hash/index.html, we can achieve > essentially a constant small number of collisions for all these test > cases (see the remaining 3 figures.) > > I think this will speed up the performance of find_neighbors() a bit > on really large meshes. > > Let me know if you'd like to see my test code, and I'll send it to you... Update: the new hashes do definitely speed up find_neighbors(), more so in 3D than in 2D though (see attached). The new versions of Elem::compute_key() have now been committed to the repository.  John 