[bknr-cvs] r2456 - branches/trunk-reorg/bknr/datastore/src/skip-list

[hhubner at common-lisp.net]

Author: hhubner
Date: Sun Feb 10 17:35:23 2008
New Revision: 2456

Modified:
   branches/trunk-reorg/bknr/datastore/src/skip-list/skip-list.lisp
Log:
Fix bug in skip-list random number generator that caused skip list
insertion performance to drop drastically on SBCL with 64bits.  It
appears as if the original algorithm returned NIL to approximately
half the invocations, despite the comment claiming that NIL would be
returned in 3/4 of the times.  I replaced the explicit random number
generator by a call to (RANDOM) with a separate random state for
skip-lists.


Modified: branches/trunk-reorg/bknr/datastore/src/skip-list/skip-list.lisp
==============================================================================
--- branches/trunk-reorg/bknr/datastore/src/skip-list/skip-list.lisp	(original)
+++ branches/trunk-reorg/bknr/datastore/src/skip-list/skip-list.lisp	Sun Feb 10 17:35:23 2008
@@ -6,23 +6,14 @@
 
 ;;; Pseudo-random number generator from FreeBSD
 
-(defparameter *random-n*
-  (the fixnum (get-internal-real-time))
-  "Internal status of the pseudo-random number generator.")
-
-(defun random-seed (seed)
-  "Seed the pseudo-random number generator."
-  (setf *random-n* seed))
+(defparameter *sl-random-state*
+  (make-random-state)
+  "Internal status of the random number generator.")
 
 (defun sl-random ()
-  "Pseudo-random number generator from FreeBSD, returns NIL 3/4 of the time."
-  (declare (optimize (speed 3))
-	   (type integer *random-n*))
-  (logtest (logand most-positive-fixnum
-		   (setf *random-n*
-			 (mod (+ (the number (* *random-n* 1103515245)) 12345)
-			      2147483648)))
-	   (ash 1 (- (integer-length most-positive-fixnum) 1))))
+  "Pseudo-random number generator, returns NIL 3/4 of the time."
+  (declare (optimize (speed 3)))
+  (< 2 (random 4 *sl-random-state*)))
 
 (defconstant +max-level+ (the fixnum 32)
   "Maximum level of skip-list, should be enough for 2^32 elements.")