Steel Bank Common Lisp

Bhaskara Marthi wrote:
> In other words, is it safe to have multiple threads reading a special 
> variable and/or using setq to change it, without any locking?
Seconded... I add that it would be very useful to have this answer 
included in the threads section of the sbcl manual; and not just for 
plain variables, but also for other things (arrays, hash tables, 
objects, structs...). The manual currently is very vague ("Large amounts 
of the SBCL library have not been inspected for thread-safety"); one can 
surely put locks around everything, just to be safe, but it would be 
nice to know when this is necessary and when it is not.
I remember seeing this kind of information sometimes appearing in the 
CHANGES in the past, but it is difficult to find it.

Pretty sure the answer to your question is "no."

I think common practice (in CCL) is that a single setf is assumed to
write a value to an address "atomically" at the assembly level (it
should just be a move and it should be the case that if two threads
write to a spot in memory, that you end up with either the first or
second value, not a mashup of the two values).  But if you read the
variable in one particular thread, there is no promise that its value
will persist (unaltered by another thread) while you execute the
branch of a conditional that choses a path based on the variable's
value.

(defvar *val* 0)

(run-thread (lambda () (setf * val* (1+ * val*)))
(run-thread (labmda () (setf * val* (1+ * val*)))

After the threads finish, *tmp* will be either 1 or 2 at the end of
the execution, depending on whether the race conditions occurred.


Instead you'd need, the following, which results in *val* always containing 2.

(defvar * val* 0)
(defvar *lock* (make-lock))
(run-thread (lambda () (with-lock *lock* (setf * val* (1+ * val*))))
(run-thread (lambda () (with-lock *lock* (setf * val* (1+ * val*))))



If you just want an atomic counter, you could consider the function
sb-ext:atomic-incf.

BTW, the notation is a bit abstract, because I have my own wrappers
for the SBCL and CCL multi-threading libraries and prefer to use said
abstractions.

You may find the CCL thread on this issue helpful:

http://clozure.com/mailman/htdig/openmcl-devel/2007-November/007728.html

On Mon, Oct 26, 2009 at 11:25 AM, David L. Rager <ragerdl@...> wrote:

> Please excuse me.  I had a major typo.  Corrected:
>
> But if you read the variable in one particular thread, there is no
> promise that its value will persist (unaltered by another thread)
> while you execute the branch of a conditional that choses a path based
> on the variable's value.
>
> On Mon, Oct 26, 2009 at 1:22 PM, David L. Rager <ragerdl@...> wrote:
> > Pretty sure the answer to your question is "no."
> >
> > I think common practice (in CCL) is that a single setf is assumed to
> > write a value to an address "atomically" at the assembly level (it
> > should just be a move and it should be the case that if two threads
> > write to a pointer, that you end up with either the first or second
> > value, not a mashup of the two values), but if you read the variable
> > in a thread and there is no promise that its value to persist while
> > you execute a branch of an if (or other conditional that choses a path
> > based on a variable's value).
> >
>

OK thanks.  In my current example, the new value does not depend on the old
one, so it sounds like, since the pointer is guaranteed never to be seen in
an intermediate state, I'm ok to not use locks.

Btw, I assume you meant SBCL, not CCL?

- Bhaskara




> > (defvar *val* 0)
> >
> > (run-thread (lambda () (setf * val* (1+ * val*)))
> > (run-thread (labmda () (setf * val* (1+ * val*)))
> >
> > After the threads finish, *tmp* will be either 1 or 2 at the end of
> > the execution, depending on whether the race conditions triggered.
> >
> >
> > Instead you'd need, the following, which results in *val* always
> containing 2.
> >
> > (defvar * val* 0)
> > (defvar *lock* (make-lock))
> > (run-thread (lambda () (with-lock *lock* (setf * val* (1+ * val*))))
> > (run-thread (lambda () (with-lock *lock* (setf * val* (1+ * val*))))
> >
> >
> >
> > If you just want an atomic counter, you could consider the function
> > sb-ext:atomic-incf.
> >
> > BTW, the notation is a bit abstract, because I have my own wrappers
> > for the SBCL and CCL multi-threading libraries and prefer to use said
> > abstractions.
> >
> >
> > On Mon, Oct 26, 2009 at 1:07 PM, Bhaskara Marthi
> > <bhaskara@...> wrote:
> >> In other words, is it safe to have multiple threads reading a special
> >> variable and/or using setq to change it, without any locking?
> >> - Bhaskara
> >>
> >> --
> >> Bhaskara Marthi
> >> Research Scientist
> >> Willow Garage Inc.
> >> 650-475-2856
> >>
> >>
> ------------------------------------------------------------------------------
> >> Come build with us! The BlackBerry(R) Developer Conference in SF, CA
> >> is the only developer event you need to attend this year. Jumpstart your
> >> developing skills, take BlackBerry mobile applications to market and
> stay
> >> ahead of the curve. Join us from November 9 - 12, 2009. Register now!
> >> http://p.sf.net/sfu/devconference
> >> _______________________________________________
> >> Sbcl-help mailing list
> >> Sbcl-help@...
> >> https://lists.sourceforge.net/lists/listinfo/sbcl-help
> >>
> >>
> >
>



-- 
Bhaskara Marthi
Research Scientist
Willow Garage Inc.
650-475-2856

Most of my deeper knowledge (if one could even call it knowledge) is
about CCL, not SBCL.  But they're both written by smart people, and
they both have a strong presence on x86-64 and have useful
multi-threading libraries, so I usually assume they have some similar
guarantees.  I present my responses more in an attempt to be helpful
than as a final authority on the matter.

> Btw, I assume you meant SBCL, not CCL?

(..I see you actually mention "special variable". If you only consider
bindings (LET) to special variables (not "top-level" SETQ/SETF against
them) you will find that these bindings are thread safe; each thread can
have _its own_ binding to the special variable. This is actually a very
useful feature; http://www.sbcl.org/manual/Special-Variables.html . If
you want more performance and "real" globals that do not have this
special or dynamic behavior (which just happen to be thread-safe wrt.
bindings as a bonus) in the first place, I'd go for SB-EXT:DEFGLOBAL
combined with locks, SB-EXT:COMPARE-AND-SWAP and/or SB-EXT:ATOMIC-INCF
instead of DEFVAR/DEFPARAMETER..)


I think you're looking for SB-EXT:COMPARE-AND-SWAP or perhaps the less
general purpose SB-EXT:ATOMIC-INCF. These handle the crucial point where
a read+write (composition) must be executed atomically.

They both have good doc-strings.

While I'm no expert at this I've found the following little "wrapper" to
work well here:

        (defstruct (atomt (:constructor mk-atom (&optional value))
                          (:copier nil))
          (value))
        
        (macrolet ((swap (place new)
                     "This binds %OLD. NEW might be evaluated more than once."
                     (with-gensyms (mnew)
                       `(loop
                           (let* ((%old ,place)
                                  (,mnew ,new))
                             (when (eq %old (sb-ext:compare-and-swap ,place %old ,mnew))
                               (return ,mnew)))))))
          
          
          (defmacro swap-atom (atom new)
            "NEW must be a value that yields T for (EQ NEW NEW).
        NEW might be evaluated more than once."
            (once-only (atom)
              `(swap (atomt-value ,atom) ,new)))
        
        
          (declaim (inline swap-atom-fn))
          (defun swap-atom-fn (atom fn)
            "FN is a function that accepts one argument; the old or current value of ATOM.
        It must return a value that yields T for (EQ VALUE VALUE). Note that FN might be
        called more than once and the argument passed to it might change for each call."
            (declare (atomt atom)
                     (function fn))
            (swap-atom atom (funcall fn %old)))
        
          ) ;; macrolet
        
        
        
Ref. the example posted by David and assuming I've not made a mistake,
this will now always return 2:

        AMX> (let* ((x (mk-atom 0))
                    (thread-1 (sb-thread:make-thread (lambda () (swap-atom-fn x #'1+))))
                    (thread-2 (sb-thread:make-thread (lambda () (swap-atom-fn x #'1+)))))
               (sb-thread:join-thread thread-1)
               (sb-thread:join-thread thread-2)
               (atomt-value x))
        2
        AMX> 
        
        
Even if the threads race, the read+set vs. that single X variable stays
atomic in nature.

Reading is always safe as long as one follow the rules mentioned in the
doc-strings for SB-EXT:COMPARE-AND-SWAP and SB-EXT:ATOMIC-INCF. So,
e.g., dealing with a variable or a slot storing a big-num is not safe
(without using traditional locking) since "the EQ rule" doesn't hold for
it in the first place:

        AMX> (eq (1+ most-positive-fixnum) (1+ most-positive-fixnum))
        NIL


(..if one follow the Hyperspec in detail EQ doesn't even hold for
fixnums ..*sigh*.., but I think EQ for fixnums pretty much "actually
holds" for all the commonly used Lisp implementations out there?..
personally, I'm not interested in "currently stupid" implementations
anyway, so..)

Which of the following operations are thread-safe, i.e. in which of the 
following (if any) a thread can access a global variable without the 
need for a locking mechanism?

a) aref
b) aref [1]
c) setf aref
d) setf aref [1]
e) gethash
f) gethash [2]
g) setf gethash
h) setf gethash [2]

[1]: with the added restriction that the subscript is different for each 
thread
[2]: with the added restriction that the key is different for each thread

also, svref instead of aref, if that makes any difference.
thanks
giovanni

Giovanni Gigante wrote:
>
> Which of the following operations are thread-safe, i.e. in which of the
> following (if any) a thread can access a global variable without the
> need for a locking mechanism?
>
> a) aref
> b) aref [1]
> c) setf aref
> d) setf aref [1]

My guess is that all of those are thread-safe.

Don't take my word for it.


> e) gethash
> f) gethash [2]
> g) setf gethash
> h) setf gethash [2]

>From the documentation of MAKE-HASH-TABLE:

      :SYNCHRONIZED
        If NIL (the default), the hash-table may have multiple concurrent readers,
        but results are undefined if a thread writes to the hash-table
        concurrently with another reader or writer. If T, all concurrent accesses
        are safe, but note that CLHS 3.6 (Traversal Rules and Side Effects)
        remains in force. See also: SB-EXT:WITH-LOCKED-HASH-TABLE. This keyword
        argument is experimental, and may change incompatibly or be removed in the
        future.


> also, svref instead of aref, if that makes any difference.

Probably not.

  Leslie

-- 
http://www.linkedin.com/in/polzer

2009/11/10 Leslie P. Polzer <sky@...>:
>
> Giovanni Gigante wrote:
>>
>> Which of the following operations are thread-safe, i.e. in which of the
>> following (if any) a thread can access a global variable without the
>> need for a locking mechanism?
[...]
>> also, svref instead of aref, if that makes any difference.
>
> Probably not.

Not thread-safe?  Or does not make a difference?

-- 
Michael Wood <esiotrot@...>

On Wed, Nov 11, 2009 at 08:29:31AM +0200, Michael Wood wrote:
> >> also, svref instead of aref, if that makes any difference.
> >
> > Probably not.
> 
> Not thread-safe?  Or does not make a difference?

The latter.

  Leslie

2009/11/10 Giovanni Gigante <giov@...>:

> Which of the following operations are thread-safe, i.e. in which of the
> following (if any) a thread can access a global variable without the
> need for a locking mechanism?
>
> a) aref
> b) aref [1]
> c) setf aref
> d) setf aref [1]

Depends on your definition of thread safety.

Eg. (setf (aref x 0) (1+ (aref x 0))) is by no means guaranteed to
increment the element by one -- other threads may write in between.

Also: if the array is non-simple, the result may be lost if the
underlying array that is updated is replaced by another thread.

If you assume that the array is simple, then all of these operations
are thread safe -- there will never by "intermediate garbage" values
anywhere, but threads may stomp on each other unless you take care to
lock around shared data as per the example above.

> e) gethash
> f) gethash [2]
> g) setf gethash
> h) setf gethash [2]

Please see the documentation for MAKE-HASH-TABLE, paying attention to
the :SYNCHRONIZED keyword (below):

      :SYNCHRONIZED
        If NIL (the default), the hash-table may have multiple
concurrent readers,
        but results are undefined if a thread writes to the hash-table
        concurrently with another reader or writer. If T, all
concurrent accesses
        are safe, but note that CLHS 3.6 (Traversal Rules and Side Effects)
        remains in force. See also: SB-EXT:WITH-LOCKED-HASH-TABLE. This keyword
        argument is experimental, and may change incompatibly or be
removed in the
        future.

CL-USER> (describe 'sb-ext:with-locked-hash-table)
SB-EXT:WITH-LOCKED-HASH-TABLE
  [symbol]

WITH-LOCKED-HASH-TABLE names a macro:
  Lambda-list: ((HASH-TABLE) &BODY BODY)
  Documentation:
    Limits concurrent accesses to HASH-TABLE for the duration of BODY.
    If HASH-TABLE is synchronized, BODY will execute with exclusive
    ownership of the table. If HASH-TABLE is not synchronized, BODY will
    execute with other WITH-LOCKED-HASH-TABLE bodies excluded -- exclusion
    of hash-table accesses not surrounded by WITH-LOCKED-HASH-TABLE is
    unspecified.

...so

 (with-locked-hash-table (table)
   (incf (getash key table)))

is guaranteed to be atomic if the hash-table is synchronized. If the
table is synchronized, but you leave out the WITH-LOCKED-HASH-TABLE,
the table will not be corrupted, but threads may stomp on each other
and the incrementation will not work properly.

Cheers,

 -- Nikodemus