gensym generates non-unique names when called from parallel threads

Bug #1797021 reported by Syll on 2018-10-10
This bug affects 1 person
Affects Status Importance Assigned to Milestone

Bug Description

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*)

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

(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*


Stas Boukarev (stassats) wrote :

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

Changed in sbcl:
status: New → Won't Fix
Syll (syll) wrote :

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) ?

To post a comment you must log in.
This report contains Public information  Edit
Everyone can see this information.

Other bug subscribers