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.")