<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>