<div dir="ltr"><br><div class="gmail_extra"><br><br><div class="gmail_quote">On Fri, Nov 8, 2013 at 11:56 AM, Jed Brown <span dir="ltr"><<a href="mailto:jedbrown@mcs.anl.gov" target="_blank">jedbrown@mcs.anl.gov</a>></span> wrote:<br>


<blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex"><div>Jed Brown <<a href="mailto:jedbrown@mcs.anl.gov" target="_blank">jedbrown@mcs.anl.gov</a>> writes:<br>



> $ time mpich-clang-optg/lib/ex26-obj/ex26 -N 1000<br>
> 0.870 real   0.857 user   0.010 sys   99.67 cpu<br>
><br>
> $ time mpich-clang-optg/lib/ex26-obj/ex26 -N 2000<br>
> 2.762 real   2.690 user   0.073 sys   100.03 cpu<br>
> 0.870 * 2^2 = 3.48<br>
><br>
> $ time mpich-clang-optg/lib/ex26-obj/ex26 -N 3000<br>
> 5.176 real   4.963 user   0.213 sys   100.01 cpu<br>
> 0.870 * 3^2 = 7.83<br>
> 2.762 * (3/2)^2 = 4.59<br>
><br>
> $ time mpich-clang-optg/lib/ex26-obj/ex26 -N 4000<br>
> 8.183 real   7.893 user   0.280 sys   99.88 cpu<br>
> 0.870 * 4^2 = 13.92<br>
> 2.762 * (4/2)^2 = 7.63<br>
> 5.176 * (4/3)^2 = 8.95<br>
><br>
> This looks stable at about 2 million lookups and insertions per second<br>
> (or 4M hash operations).<br>
<br>
</div>If we use the khash API the way it was intended (via kh_put and kh_val;<br>
ignore the ugly API inconsistency)<br>
<br>
  PetscHashICreate(table);<br>
  for (i = 0; i < N; ++i) {<br>
    for (j = 0; j < N; ++j) {<br>
      PetscInt key = (PetscMin(i,j) << 16) + PetscMax(i,j);<br>
      khint_t ret,idx = kh_put(HASHI,table,key,&ret);<br>
      if (ret == 1) kh_val(table,idx) = newp++;<br>
    }<br>
  }<br>
  PetscHashIDestroy(table);<br>
<br>
we get numbers that are about twice as good (no weird chaining and only<br>
one lookup):<br></blockquote><div>One of the original use cases for PetscHash was pseudograph manipulation (multiple edges allowed),</div><div>which required the 'multivalued' option that might slow things down unnecessarily in the simpler</div>


<div>use cases. </div><div><br></div><div>PetscHash also tried to hide the idiosyncrasies of the khash API anticipating that it might have to be </div><div>replaced at the backend with another hash table implementation. It's possible both the PetscHash API</div>


<div>and the implementation need to be revised.  The API itself could probably be simplified somewhat.</div><div>If we were to stick to khash long-term, maybe then the PetscHash API should more directly reflect </div><div>


khash's preferred use pattern - put-test-val.</div><div><br></div><div>Initially PetscHash was all macros, but then some of it was switched over to PETSC_STATIC_INLINE</div><div>functions.  Even if these are being inlined by the compiler, there may be some call overhead, which</div>

<div>may be avoidable.  Besides, it may be more natural to have macros to wrap the use case in the snippet above.</div><div>And there are no error codes being returned from inside PetscHash at the moment.  That might have to</div>

<div>change, however, if the bare realloc() calls in khash are replaced by something like PetscRealloc().</div><div><br></div><div><br></div><div><br></div><div><br></div><div><br></div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">



<br>
$ for n in 1000 2000 3000 4000; do time mpich-clang-optg/lib/ex26-obj/ex26 -N $n; done<br>
0.462 real   0.453 user   0.007 sys   99.59 cpu<br>
1.476 real   1.457 user   0.020 sys   100.01 cpu<br>
2.791 real   2.767 user   0.023 sys   99.96 cpu<br>
3.927 real   3.893 user   0.037 sys   100.06 cpu<br>
<br>
The debug-mode performance is also tons better.<br>
<br>
I see another hash table shootout by a good developer:<br>
<br>
<a href="http://preshing.com/20110603/hash-table-performance-tests/" target="_blank">http://preshing.com/20110603/hash-table-performance-tests/</a></blockquote><div>If the implementation of PetscHash is to be replaced, it would be a good idea to do some representative </div>

<div>testing of the proposed new implementation.  In particular, I don't have a good feel for how double hashing </div><div>compares to linear probing or to chaining.  The fastest implementation above uses a smallish fixed-size</div>

<div>table, so that might not be an entirely fair comparison with khash et al. I don't think the author claims </div><div>the test to be comprehensive anyhow.</div><div><br></div><div>Dmitry.</div><blockquote class="gmail_quote" style="margin:0px 0px 0px 0.8ex;border-left-width:1px;border-left-color:rgb(204,204,204);border-left-style:solid;padding-left:1ex">


<br>
<br>
The fastest in his comparison uses simple chaining instead of double<br>
hashing (which khash uses).  I don't have a direct comparison of the<br>
two, and Jeff's version is hashing strings, so it would have to be<br>
modified/simplified to compare directly.<br>
<br>
Does your algorithm need lots better than 4M hash lookups per second, or<br>
do we just need to optimize the current implementation?<br>
</blockquote></div><br></div></div>