[Sbcl-devel] slow as molasses gethash

[James Y K. <fo...@fu...>]

Recent SBCLs have made gethash a lot slower than it used to be. This  
is a problem.

A few observations:
1) gethash is so much slower because unwind-protect is damn slow. It  
really seems like it shouldn't need to be.

2) Is the without-gcing really needed in gethash at all? Wouldn't it  
be sufficient to do (with-pinned-objects (key) ...)?

3) It sucks that hashtables use a spinlock...

I understand the idea is that getting incorrect answers is an okay  
result of being non-thread-safe (and not doing your own locking), but  
uninterruptibly hanging or hard crashing the interpreter is not.

There's a commment at the top of "target-hash-table.lisp", saying  
shrink-vector can corrupt memory. Okay...but those calls to %shrink- 
vector really don't look necessary. How about just removing them?

The same comment also says next-vector can get cyclic, thus causing  
an uninterruptible hang. Wouldn't it make sense to instead put an  
upper bound on the number of probes, and if the right place hasn't  
been found by then, raise an error ("Hi, your hashtable got corrupted  
because you forgot to use a lock, so sorry."). Or, actually, if there  
wasn't a without-gcing around the code, I guess it would be "fine" to  
get in an infinite loop, as it would be interruptible. Yes?


Here's a tiny benchmark:

(defvar *hash* (make-hash-table))
(setf (gethash 5 *hash*) 5)
(defun testfun () (gethash 6 *hash* nil))
(time (dotimes (i 5000000) (testfun)))

In sbcl 1.0.7, it currently takes 1.305s to complete this benchmark.
If I redefine gethash3 to remove the with-spinlock-and-without-gcing,  
it instead takes 0.378s.
This is, needless to say, a huge, huge difference.

James