[Openmcl-devel] hash table performance mystery

[Stas Boukarev]

"Jared C. Davis" <jared at cs.utexas.edu> writes:

> ; Hi,
> ;
> ; I am trying to understand a strange performance problem that appears to be
> ; related to non lock-free hash tables.
> ;
> ; Below is a very distilled example.
> ;
> ; In this example, test1 and test2 are quite similar except that test2 does
> ; some additional (but irrelevant) work.
> ;
> ; Claim: "obviously", test2 should be somewhat slower than test1.
> ;
> ; Indeed, this claim holds up when the *fal-ht* is created with :lock-free T.
> ;
> ; But mysteriously, when *fal-ht* is created with :lock-free NIL, test2
> ; outperforms test1.  In fact, when *fal-ht* is large, the performance
> ; difference can be huge.
> ;
> ; Here are some sample figures from my machine:
> ;
> ;                    FAL-HT Size         Test1 Loop        Test2 Loop
> ; --------------------------------------------------------------------
> ;  Not Lock-Free          100              0.4 sec          0.4 sec
> ;                       1,000              2.4 sec          0.4 sec
> ;                      10,000             23.2 sec          0.4 sec
> ;                     100,000            231.3 sec          0.9 sec
> ; --------------------------------------------------------------------
> ;                         100              0.3 sec          0.5 sec
> ;  Lock-Free            1,000              0.3 sec          0.5 sec
> ;                      10,000              0.3 sec          0.5 sec
> ;                     100,000              0.3 sec          0.5 sec
> ; --------------------------------------------------------------------
> ;
> ; I am completely baffled.  How can test2 outperform test1?  And why does the
> ; size of fal-ht have any significance on this computation at all?  Any ideas
> ; are greatly appreciated.
> ;
> ; The figures above are from revision 14519, checked out this morning, on
> ; 64-bit linux, with a kernel built via "make" in lisp-kernel/linuxx8664, and a
> ; (rebuild-ccl :full t) issued subsequently.  They are similar to results from
> ; an earlier revision (13955) so I have no reason to believe this is anything
> ; recent.

Profiling shows that 99% of the time is spent in remhash for
non-lock-free version.

-- 
With Best Regards, Stas.