gensym generates non-unique names when called from parallel threads

[Syll]

The code below shows that gensym sometimes generates non-unique names when called from parallel running threads.

gensym function documentation says : " If and only if no explicit suffix is supplied, *gensym-counter* is incremented after it is used.", which is not always the case.

*gensym-counter* should probably be managed with a lock acquired (this is the case in CCL, for instance).

Could random/*random-state* be a similar case ? The specification does not say anything precise about their behaviour (and using a lock there may be costly ?).

-----------------------------------

;;; (with quicklisp initialized)

(ql:quickload :bordeaux-threads)

(defparameter *nb-names* 1000000)

(defparameter *list1* '())
(defparameter *list2* '())

(defparameter *table1* nil)
(defparameter *table2* nil)

(defun generate-names (function-num nb-names)
"
Generates uniques names, using gensym.
"
  (let ((symbols (make-array nb-names)))

    ;; Create symbols
    (dotimes (i nb-names)
      (setf (aref symbols i) (gensym)))

    ;; Store names
    (ecase function-num
      (1 (setf *list1* (map 'list #'symbol-name symbols)))
      (2 (setf *list2* (map 'list #'symbol-name symbols))))))

(format t "Creating names...~%")
(let ((thread1 (bt:make-thread (lambda ()
                                 (generate-names 1 *nb-names*))))
      (thread2 (bt:make-thread (lambda ()
                                 (generate-names 2 *nb-names*)))))
  (format t "Threads started~%")
  (bt:join-thread thread1)
  (bt:join-thread thread2))

(format t "Threads stopped~%")

(format t "Storing results in hash table...~%")

(setf *table1* (make-hash-table :test #'equal))
(setf *table2* (make-hash-table :test #'equal))

(dolist (val *list1*)
  (when (gethash val *table1*)
    (format t "Key ~s is already present in table 1~%" val))
  (setf (gethash val *table1*)
        t))

(dolist (val *list2*)
  (when (gethash val *table2*)
    (format t "Key ~s is already present in table 2~%" val))
  (setf (gethash val *table2*)
        t))

(format t "~%Tables size : ~s and ~s~%" (hash-table-count *table1*) (hash-table-count *table2*))
(format t "Expected size : ~s~%" *nb-names*)

;; (format t "Checking hash tables...~%")
;; (maphash (lambda (key value)
;; (declare (ignore value))
;; (when (gethash key *table2*)
;; (format t "Key in both tables : ~s~%" key)))
;; *table1*)

-----------------------------------

$ sbcl --version
SBCL 1.4.11

$ uname -a
Linux yggdrasil 4.18.12-arch1-1-ARCH #1 SMP PREEMPT Thu Oct 4 01:01:27 UTC 2018 x86_64 GNU/Linux

* *features*

(:X86-64 :64-BIT :64-BIT-REGISTERS :ALIEN-CALLBACKS :ANSI-CL :ASH-RIGHT-VOPS
 :C-STACK-IS-CONTROL-STACK :CALL-SYMBOL :COMMON-LISP :COMPACT-INSTANCE-HEADER
 :COMPARE-AND-SWAP-VOPS :COMPLEX-FLOAT-VOPS :CYCLE-COUNTER :ELF :FLOAT-EQL-VOPS
 :FP-AND-PC-STANDARD-SAVE :GCC-TLS :GENCGC :IEEE-FLOATING-POINT :IMMOBILE-CODE
 :IMMOBILE-SPACE :INLINE-CONSTANTS :INTEGER-EQL-VOP :LARGEFILE :LINKAGE-TABLE
 :LINUX :LITTLE-ENDIAN :MEMORY-BARRIER-VOPS :MULTIPLY-HIGH-VOPS
 :OS-PROVIDES-BLKSIZE-T :OS-PROVIDES-DLADDR :OS-PROVIDES-DLOPEN
 :OS-PROVIDES-GETPROTOBY-R :OS-PROVIDES-POLL :OS-PROVIDES-PUTWC
 :OS-PROVIDES-SUSECONDS-T :PACKAGE-LOCAL-NICKNAMES :RAW-INSTANCE-INIT-VOPS
 :RAW-SIGNED-WORD :RELOCATABLE-HEAP :SB-CORE-COMPRESSION :SB-DOC :SB-EVAL
 :SB-FUTEX :SB-LDB :SB-PACKAGE-LOCKS :SB-SIMD-PACK :SB-SOURCE-LOCATIONS
 :SB-THREAD :SB-UNICODE :SBCL :STACK-ALLOCATABLE-CLOSURES
 :STACK-ALLOCATABLE-FIXED-OBJECTS :STACK-ALLOCATABLE-LISTS
 :STACK-ALLOCATABLE-VECTORS :STACK-GROWS-DOWNWARD-NOT-UPWARD :SYMBOL-INFO-VOPS
 :UNBIND-N-VOP :UNDEFINED-FUN-RESTARTS :UNIX :UNWIND-TO-FRAME-AND-CALL-VOP)

[Stas Boukarev (stassats)]

gensym is not a synchronization primitive for creating random data, if you need monotonic counters roll out your own.

[Syll (syll)]

I was searching for a mean to generate names, I studied gensym and understood this was not the tool I searched for, so I used something else. My example code was just a test I made after reading the code, to check the generation.

I'm not a lisp expert, I was wondering if this behaviour was intended (especially regarding the sentence in the spec). Don't you think generating non-unique visible names is a problem while generating lisp code ? Or not incrementing the counter as if if was in a single thread (the spec says "if and only if", although the crucial point of gensym is generating unique objects) ?