From: <obr...@gm...> - 2008-02-14 17:30:33
|
Hi everyone- I'm new to this list, as I've recently decided to port my old Common Lisp code to SBCL, because it's open s/w and because it claims to be very portable. However, I've found a BUG that shows up in the following code. Sometimes this snippet generates an erroneous result: ;; first run: CL-USER> (let ((res nil)) (dotimes (n 3) (push (sb-thread:make-thread #'(lambda () (cons n n))) res)) (mapcar #'sb-thread:join-thread (reverse res))) ((0 . 0) (2 . 2) (3 . 3)) ;; second run: CL-USER> (let ((res nil)) (dotimes (n 3) (push (sb-thread:make-thread #'(lambda () (cons n n))) res)) (mapcar #'sb-thread:join-thread (reverse res))) ((0 . 0) (1 . 1) (2 . 2)) ;; several reposts later: CL-USER> (let ((res nil)) (dotimes (n 3) (push (sb-thread:make-thread #'(lambda () (cons n n))) res)) (mapcar #'sb-thread:join-thread (reverse res))) ((0 . 0) (1 . 1) (3 . 3)) What's going on ???? How reliable is the compiled code that SBCL generates? I hope this has an easy and quick solution. I've otherwise liked SBCL very much. Cheers. Mateo. |
From: Kevin R. <kp...@ma...> - 2008-02-14 17:53:00
|
On Feb 14, 2008, at 12:30, obr...@gm... wrote: > However, I've found a BUG that shows up in the following code. > Sometimes this snippet generates an erroneous result: > > ;; first run: > > CL-USER> (let ((res nil)) > (dotimes (n 3) > (push (sb-thread:make-thread #'(lambda () (cons n n))) res)) > (mapcar #'sb-thread:join-thread (reverse res))) > > ((0 . 0) (2 . 2) (3 . 3)) ... > ((0 . 0) (1 . 1) (2 . 2)) ... > ((0 . 0) (1 . 1) (3 . 3)) This is not a bug, but permitted behavior of DOTIMES. According to the CLHS: "It is implementation-dependent whether dotimes establishes a new binding of var on each iteration or whether it establishes a binding for var once at the beginning and then assigns it on any subsequent iterations." SBCL currently does the latter. Therefore, your three lambdas close over the same binding, which is the one being mutated by DOTIMES. The variation you are seeing comes from the OS scheduler: whether the thread retrieves n before or after DOTIMES proceeds to its next iteration. You can also see this type of behavior without threads: (let ((res nil)) (dotimes (n 3) (push (lambda () (cons n n)) res)) (mapcar #'funcall (reverse res))) This will always return ((3 . 3) (3 . 3) (3 . 3)). One way to do this correctly is: (dotimes (n 3) (let ((n n)) (push (sb-thread:make-thread #'(lambda () (cons n n)))) This establishes a new, never-reassigned, binding for each closure. -- Kevin Reid <http://homepage.mac.com/kpreid/> |
From: <obr...@gm...> - 2008-02-14 18:31:37
|
Learn something new every day. :) Thanks for quote. The issue is definitely related to when the closure bindings take effect. I tried your snippet in different lisps and got the following: CMU Common Lisp CVS 19d 19d-release (19D), ... * (let ((res nil)) (dotimes (n 3) (push (lambda () (cons n n)) res)) (mapcar #'funcall (reverse res))) ((0 . 0) (1 . 1) (2 . 2)) On clisp: Copyright (c) Sam Steingold, Bruno Haible 2001-2006 [1]> (let ((res nil)) (dotimes (n 3) (push (lambda () (cons n n)) res)) (mapcar #'funcall (reverse res))) ((3 . 3) (3 . 3) (3 . 3)) On ACL: ;; International Allegro CL Enterprise Edition CL-USER(1): (let ((res nil)) (dotimes (n 3) (push (lambda () (cons n n)) res)) (mapcar #'funcall (reverse res))) ((3 . 3) (3 . 3) (3 . 3)) I'm trying to write some optimised code that takes advantage of several CPUs in an SMP linux system. I'll try and better the code so that I avoid creating an extra environment. Cheers. Mateo. On Thursday 14 February 2008 17:52, Kevin Reid wrote: > On Feb 14, 2008, at 12:30, obr...@gm... wrote: > > However, I've found a BUG that shows up in the following code. > > Sometimes this snippet generates an erroneous result: > > > > ;; first run: > > > > CL-USER> (let ((res nil)) > > (dotimes (n 3) > > (push (sb-thread:make-thread #'(lambda () (cons n n))) res)) > > (mapcar #'sb-thread:join-thread (reverse res))) > > > > ((0 . 0) (2 . 2) (3 . 3)) > > ... > > > ((0 . 0) (1 . 1) (2 . 2)) > > ... > > > ((0 . 0) (1 . 1) (3 . 3)) > > This is not a bug, but permitted behavior of DOTIMES. According to > the CLHS: > > "It is implementation-dependent whether dotimes establishes a new > binding of var on each iteration or whether it establishes a binding > for var once at the beginning and then assigns it on any subsequent > iterations." > > SBCL currently does the latter. Therefore, your three lambdas close > over the same binding, which is the one being mutated by DOTIMES. > > The variation you are seeing comes from the OS scheduler: whether the > thread retrieves n before or after DOTIMES proceeds to its next > iteration. > > You can also see this type of behavior without threads: > > (let ((res nil)) > (dotimes (n 3) > (push (lambda () (cons n n)) res)) > (mapcar #'funcall (reverse res))) > > This will always return ((3 . 3) (3 . 3) (3 . 3)). > > One way to do this correctly is: > > (dotimes (n 3) > (let ((n n)) > (push (sb-thread:make-thread #'(lambda () (cons n n)))) > > This establishes a new, never-reassigned, binding for each closure. |
From: Nikodemus S. <nik...@ra...> - 2008-02-14 19:00:01
|
On 2/14/08, obr...@gm... <obr...@gm...> wrote: > I'm trying to write some optimised code that takes advantage of several CPUs > in an SMP linux system. I'll try and better the code so that I avoid creating > an extra environment. Do not worry about it: just insert the LET you need to be portably correct. Most compilers will generate identical code for (dotimes (i 3) (let ((i i)) (let ((i i)) ...))) and (dotimes (i 3) (let ((i i)) ...)) -- and even if they don't, the difference is going to be noise compared to the cost of spawning a thread. (Noise compared to almost anything, really.) Cheers, -- Nikodemus |