Steel Bank Common Lisp

On 28 Apr 2004, David Steuber spake thusly:

> I still consider myself very much a Lisp beginner (neolisper?).  I
> kind of skipped through macros and clos in Graham's ACL book.  I
> figured I could come back to that stuff.  I am hoping that I have
> enough ground work to handle seperate concepts such as threads and
> also sockets and other things.

Another neolisper here !  I really had some hard work to do to get mp
in CMUCL working.  But I thought that was just me. ;-)

I would really really love to have a sb-thread tutorial for beginners.
In fact I am ready to work on it if guided (remember, neolisper
here).

-- 
quasi

Utopia Unlimited!

On Wed, 28 Apr 2004, David Steuber wrote:

> To quote a line from the SBCL manual:
>
> "Dynamic bindings to symbols are per-thread. Signal handlers are
> per-thread."

...

> (setf *foo* "baz")
>
> then /that/ thread and /only/ that thread has *foo* bound to "baz".

No. That's assignment, not binding.

What it means is that after you have done

 (let ((*foo* ...))
   ...)

then within that dynamic contour you can assign to *foo* without other
threads being affected.

If *foo* hasn't been bound (by LET) in the thread, then the assignments
affects all threads that haven't rebound their *foo*'s.

Cheers,

 -- Nikodemus

David Steuber <david@...> writes:

> To quote a line from the SBCL manual:
>
> "Dynamic bindings to symbols are per-thread. Signal handlers are
> per-thread."
>
> Although I have not seen how Lisp does signal handling, it is nice to
> know that the handler will be called in the same thread that the
> signal was raised.  That at least means that you can pretend the

Yup.

> thread is its own little world.  I'm not quite sure about the dynamic
> bindings.  My interpretation is that
>
> (defvar *foo* "bar")
>
> means that every thread has *foo* with the initial value of "bar".  If
> a thread does
>
> (setf *foo* "baz")
>
> then /that/ thread and /only/ that thread has *foo* bound to "baz".
> If this is the case, then that is great.  I have a sort of thread
> local storage thing going on for free.

As Nikodemus points out, by using SETF you're setting the (global
value of the) variable, not rebinding it.  To bind it, use LET.

Once you've bound it, any further setfs will affect only the local
binding, so, yes, you have thread-local storage.

> That then leads me to wonder how to create a shareable object such as
> a hash table (or an a-list) that has serialized access from all the
> threads that need to touch it in some way.

Using a variable declared globally with DEFVAR or DEFPARAMETER, and
a mutex to control access to it.

;; from memory; details probably wrong, but that's what apropos is for
(defvar *foo* 1)
(defvar *foo-lock* (make-mutex))

(with-mutex (*foo-lock*)
  (incf *foo*)) ; or whatever

> Then there are other threading issues like waiting on objects (Java
> style) and other scheduling issues.  For example, if thread creation
> has too much overhead for a given purpose, I would want to pre-spawn a
> number of threads and have them sleeping in a queue to be woken up as
> needed to handle a request and then go back into the queue when
> finished rather than exiting.

You most probably want to be using the condition variables for this.
Summary: create a waitqueue for the threads to wait on
(make-waitqueue) and a lock to say who has control of it.  Now have
queue readers acquire the lock then use condition-wait (which
atomically drops the lock and blocks) when the queue is empty and they
need to wait, and queue writers acquire the lock then use
condition-notify to wake one or more readers when they've added
something worth reading.

In outline, anyway.  Better threads docs is on my todo (aka my "yeah,
right, like that'll ever happen") list


-dan

-- 
"please make sure that the person is your friend before you confirm"

Daniel Barlow <dan@...> writes:

> As Nikodemus points out, by using SETF you're setting the (global
> value of the) variable, not rebinding it.  To bind it, use LET.
> 
> Once you've bound it, any further setfs will affect only the local
> binding, so, yes, you have thread-local storage.

I think I'm getting straightened out on that point.

> > That then leads me to wonder how to create a shareable object such as
> > a hash table (or an a-list) that has serialized access from all the
> > threads that need to touch it in some way.
> 
> Using a variable declared globally with DEFVAR or DEFPARAMETER, and
> a mutex to control access to it.
> 
> ;; from memory; details probably wrong, but that's what apropos is for
> (defvar *foo* 1)
> (defvar *foo-lock* (make-mutex))
> 
> (with-mutex (*foo-lock*)
>   (incf *foo*)) ; or whatever

Yay!  Examples!

Apropos has been helping me find out what exists.  But documentation
and describe have not been helpful in what to do with it :-(

> In outline, anyway.  Better threads docs is on my todo (aka my "yeah,
> right, like that'll ever happen") list

Heh.  No one likes to document ;-)

In the meantime, is SBCL following any de facto standards for
functions, macros, and objects for threading?  That is, is there a
place where I can look for some sort of tutorial on threaded
programming in Lisp in general that will work with SBCL?

I've resorted to looking through the source code now.  I'm already
confused by what I assume are basic things like (in-package
"SB!THREAD") instead of (in-package "SB-THREAD") and not being able
to find an associated (make-package "SB!THREAD").

I could start working on documentation as I figure things out, but it
is almost certain to be full of lies, misdirection, and apocrypha.
Then again, it might just be flat out wrong.

Do macros even take documentation strings?  The CLHS mentions
compiler-macro as a type, but I don't think that is the same thing.

* (documentation 'sb-thread:with-mutex 'function)

NIL
* (documentation 'sb-thread:with-mutex 'compiler-macro)

NIL

I know that sb-thread:with-mutex is a macro.  Documentation doesn't
like it when I pass in 'macro.

BTW, has anyone looked at this:

http://www.caddr.com/macho/archives/sbcl-devel/2004-4/3337.html

I haven't seen a response to it.  I was wondering if I need to provide
more information or if there is already a known problem with SMP
machines.  I don't know if this problem will get in my way or not, nor
do I know what sort of priority threads have.  Until I built SBCL on
it, I was running SBCL on my webserver only and that is a slow
machine.  The SMP box is on my LAN which makes working on it more
convenient.

Thanks.

-- 
I wouldn't mind the rat race so much if it wasn't for all the damn cats.

On Thu, 2004-04-29 at 07:09, Daniel Barlow wrote:
> In outline, anyway.  Better threads docs is on my todo (aka my "yeah,
> right, like that'll ever happen") list

Hmm... I'll whack up some docos. SB-THREADS could definitely use some.
And since I've kinda gotten the hang of them after much searching on the
'net for examples I can probably get at least some of it correct and
save others having to spend as much time as I did :)

It's not a big package so it shouldn't take long. I could use some
proof-reading though of course. I'll whack it up in text format for now.


-- 
Regards,

Robert Marlow

On Wed, 28 Apr 2004, David Steuber wrote:

> I've resorted to looking through the source code now.  I'm already
> confused by what I assume are basic things like (in-package
> "SB!THREAD") instead of (in-package "SB-THREAD") and not being able
> to find an associated (make-package "SB!THREAD").

The "!" vs. "-" is a bootstrapping mechnism to keep packages being built
separate from host packages -- towards the end of a build the "SB!FOO" is
renamed to "SB-FOO".

Similar explanations exist for various other mysterious beasts in the
sources: if something looks almost but not quite like the name of a
standard operator, then more likely then not it's part of the
bootstrapping machinery and unless you're wading in hip-deep hacking on
sbcl you can pretend it's the standard operator.

> Do macros even take documentation strings?  The CLHS mentions
> compiler-macro as a type, but I don't think that is the same thing.
>
> * (documentation 'sb-thread:with-mutex 'function)

From the CLHS pages:

 http://www.lispworks.com/reference/HyperSpec/Body/m_defmac.htm#defmacro

  "defmacro name lambda-list [[declaration* | documentation]] form*"

  So, yes. Macros take docstrings.


 http://www.lispworks.com/reference/HyperSpec/Body/f_docume.htm

  "The nature of the documentation string returned depends on the
   doc-type, as follows:"

   ...

  "function

    If x is a function name, returns the documentation string of the
    function, macro, or special operator whose name is x."

  So, the documentation of a macro is fetched by

   (documentation macro-name 'function)


> http://www.caddr.com/macho/archives/sbcl-devel/2004-4/3337.html

I'm under the impression that 2.4 kernels in general have threading
problems, and fixing them is a lower priority eg. threadsafetyfing
sbcl internals, and that for serious sb-thread use 2.6 kernels are
recommended, but dunno.

Cheers,

 -- Nikodemus

Nikodemus Siivola <tsiivola@...> writes:

>   So, the documentation of a macro is fetched by
> 
>    (documentation macro-name 'function)

Ok.  Since I tried that and got NIL, I can assume there was no
docstring.

> > http://www.caddr.com/macho/archives/sbcl-devel/2004-4/3337.html
> 
> I'm under the impression that 2.4 kernels in general have threading
> problems, and fixing them is a lower priority eg. threadsafetyfing
> sbcl internals, and that for serious sb-thread use 2.6 kernels are
> recommended, but dunno.

I really should get that machine up to 2.6.5.  When I first set it up
way back when, I didn't make the boot partition large enough and it
is almost full.  I might be able to clear out some stuff though.  I
would hate to repartition because I have no place to put the data
that is on that machine.

Backups?  Not here.

Anyway, I would agree with the policy of threadsafetyfing sbcl
internals prior to attempting backwards compatibility with older
kernels if that is indeed the case.

-- 
I wouldn't mind the rat race so much if it wasn't for all the damn cats.

On Thu, 2004-04-29 at 03:16, Nikodemus Siivola wrote:
> I'm under the impression that 2.4 kernels in general have threading
> problems, and fixing them is a lower priority eg. threadsafetyfing
> sbcl internals, and that for serious sb-thread use 2.6 kernels are
> recommended, but dunno.

There shouldn't be anything wrong with threads under Linux 2.4. There
are some scalability limits that are fixed by NPTL. NPTL is in various
Red Hat 2.4-based kernels (e.g. FC-1) and is standard in 2.6.

So, if you plan on having thousands of threads, you should probably use
a RH-based 2.4 kernel or 2.6. If you're just using a few threads,
however, any > 2.4 kernel should work fine for most situations.

-- 
Dave Roberts <ldave@...>

Daniel Barlow <dan@...> writes:

> If you know a reliable way to do scheduler-friendly locking absent
> futex support, please say, because nobody else is telling.

I don't.  I decided the path of least resistence was to see if I
could clean out space in my boot partition and install 2.6.5.  I was
able to do that.  Whether I compiled in all the options I need is
another issue that is currently unknown.  But the kernel boots and it
is SMP.  I tried the build of 0.8.10 again with sb-futex restored and
the thread test failed again.  Here are my results:

//running threads.impure.lisp test
; in: LAMBDA NIL
;     (ERROR "Missing shared library compilation options for this platform")
; ==>
;   "Missing shared library compilation options for this platform"
; 
; note: deleting unreachable code
; compilation unit finished
;   printed 1 note
#S(MUTEX :NAME "foo" :LOCK 0 :DATA NIL :VALUE NIL)
is an instance of class #<STRUCTURE-CLASS MUTEX>.
The following slots have :INSTANCE allocation:
 NAME     "foo"
 LOCK     0
 DATA     NIL
 VALUE    NIL
4249 got mutex
parent thread 4243
270488496 got mutex
parent thread 4243
woken, 270488496 got mutex
contention 4251 4252
interrupting child 4253
child pid 4253
interrupting child 4254
child pid 4254
unhandled condition (of type SIMPLE-CONTROL-ERROR):
  attempt to THROW to a tag that does not exist: SB-IMPL::%END-OF-THE-WORLD

0: 
("hairy arg processor for top level local call SB!DEBUG:BACKTRACE"
    128
    #<SYNONYM-STREAM :SYMBOL SB-SYS:*STDERR* {505EA69}>)
1: (SB-DEBUG::DEBUGGER-DISABLED-HOOK
    2
    #<SIMPLE-CONTROL-ERROR {9259A81}>
    #<unavailable argument>)[:EXTERNAL]
2: (INVOKE-DEBUGGER 1 #<SIMPLE-CONTROL-ERROR {9259A81}>)[:EXTERNAL]
3: (ERROR 5 SIMPLE-CONTROL-ERROR)[:EXTERNAL]
4: (SB-KERNEL::UNSEEN-THROW-TAG-ERROR-HANDLER
    4
    #<unavailable argument>
    #.(SB-SYS:INT-SAP #X414A5F08)
    #<SB-ALIEN-INTERNALS:ALIEN-VALUE :SAP #X414A5BD8 :TYPE (*
                                                            (STRUCT
                                                             SB-VM::OS-CONTEXT-T-STRUCT))>
    (142))[:EXTERNAL]
5: (SB-KERNEL:INTERNAL-ERROR
    2
    #.(SB-SYS:INT-SAP #X414A5BD8)
    #<unavailable argument>)[:EXTERNAL]
6: ("foreign function call land: ra=#x80579F1")
7: ("foreign function call land: ra=#x805787D")
8: ("foreign function call land: ra=#x80523BB")
Argh! error within --disable-debugger error handling
9: ("foreign function call land: ra=#x80574EB")
interrupting child 4255
child pid 4255
interrupting child 4256
child pid 4256
done 4251
parent releasing lock
interrupting child 4257
child pid 4257
new thread 4257
................................unhandled condition (of type SIMPLE-ERROR): segmentation violation at #X0


unhandled condition in --disable-debugger mode, quitting
unhandled condition (of type SIMPLE-ERROR):
  Syscall interrupt_thread failed: No such process

0: ("hairy arg processor for top level local call SB!DEBUG:BACKTRACE"
    128
    #<SYNONYM-STREAM :SYMBOL SB-SYS:*STDERR* {505EA69}>)
1: (SB-DEBUG::DEBUGGER-DISABLED-HOOK
    2
    #<SIMPLE-ERROR {904E0C1}>
    #<unavailable argument>)[:EXTERNAL]
2: (INVOKE-DEBUGGER 1 #<SIMPLE-ERROR {904E0C1}>)[:EXTERNAL]
3: (ERROR 3 "Syscall ~A failed: ~A")[:EXTERNAL]
4: (INTERRUPT-THREAD
    2
    4257
    #<FUNCTION "#'(LAMBDA NIL (PRINC \".\") ...)" {9C1F4AD}>)[:EXTERNAL]
5: (#:EVAL-TMPFUN-2619 0)[:EXTERNAL]
6: (EVAL-IN-LEXENV
    2
    (LET ((C (TEST-INTERRUPT (LAMBDA () (LOOP (ALLOC-STUFF))))))
      (FORMAT T "new thread ~A~%" C)
      (DOTIMES (I 100)
        (SLEEP (RANDOM 1.0d0))
        (INTERRUPT-THREAD C
                          (LAMBDA ()
                            (PRINC ".")
                            (FORCE-OUTPUT)
                            (ASSERT
                             (ZEROP SB-KERNEL:*PSEUDO-ATOMIC-ATOMIC*)))))
      (TERMINATE-THREAD C))
    #S(SB-KERNEL:LEXENV
       :FUNS NIL
       :VARS NIL
       :BLOCKS NIL
       :TAGS NIL
       :TYPE-RESTRICTIONS NIL
       :LAMBDA NIL
       :CLEANUP NIL
       :POLICY ((SPEED . 1) (SPACE . 1) (SAFETY . 1)
                (SB-EXT:INHIBIT-WARNINGS . 1) (DEBUG . 1)
                (COMPILATION-SPEED . 1))))[:EXTERNAL]
7: (SB-FASL::LOAD-AS-SOURCE
    3
    #<FILE-STREAM
      for "file \"/home/david/usr/src/sbcl/tests/threads.impure.lisp\""
      {902C449}>
    NIL
    NIL)[:EXTERNAL]
8: ("hairy arg processor for top level local call SB!FASL::INTERNAL-LOAD"
    #P"threads.impure.lisp"
    #P"/home/david/usr/src/sbcl/tests/threads.impure.lisp"
    :ERROR
    NIL
    NIL
    :SOURCE)
9: ("hairy arg processor for top level local call SB!FASL::INTERNAL-LOAD"
    #P"threads.impure.lisp"
    #P"/home/david/usr/src/sbcl/tests/threads.impure.lisp"
    :ERROR
    NIL
    NIL
    NIL)
10: (LOAD 1 "threads.impure.lisp")[:EXTERNAL]
11: (EVAL-IN-LEXENV
     2
     (LOAD "threads.impure.lisp")
     #S(SB-KERNEL:LEXENV
        :FUNS NIL
        :VARS NIL
        :BLOCKS NIL
        :TAGS NIL
        :TYPE-RESTRICTIONS NIL
        :LAMBDA NIL
        :CLEANUP NIL
        :POLICY ((SAFETY . 3) (COMPILATION-SPEED . 2) (DEBUG . 2) (SPEED . 1)
                 (SPACE . 1) (SB-EXT:INHIBIT-WARNINGS . 1))))[:EXTERNAL]
12: (SB-EXT:INTERACTIVE-EVAL 1 (LOAD "threads.impure.lisp"))[:EXTERNAL]
13: (SB-IMPL::REPL-FUN 1 T)[:EXTERNAL]
14: ("#'(LAMBDA NIL (LOOP # #))")
15: ("XEP for #'(LAMBDA NIL (LOOP # #))" 0)[:EXTERNAL]
16: (SB-IMPL::%WITH-REBOUND-IO-SYNTAX 1 #<FUNCTION "CLOSURE" {9027815}>)[:EXTERNAL]
17: (SB-IMPL::TOPLEVEL-REPL 1 T)[:EXTERNAL]
18: (SB-IMPL::TOPLEVEL-INIT 0)[:EXTERNAL]
19: ("FLET SB!IMPL::RESTART-LISP")

unhandled condition in --disable-debugger mode, quitting
test threads.impure.lisp failed, expected 104 return code, got 1

david@...
$ uname -a
Linux vega 2.6.5-k7 #1 SMP Thu Apr 29 10:01:49 EDT 2004 i686 GNU/Linux
david@...
$ cat customize-target-features.lisp 
(lambda (list)
  (pushnew :sb-thread list)
  (pushnew :sb-futex list))
david@...
$ cat /proc/cpuinfo 
processor       : 0
vendor_id       : AuthenticAMD
cpu family      : 6
model           : 6
model name      : AMD Athlon(TM) MP 1800+
stepping        : 2
cpu MHz         : 1533.697
cache size      : 256 KB
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : no
fpu             : yes
fpu_exception   : yes
cpuid level     : 1
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 mmx fxsr sse syscall mp mmxext 3dnowext 3dnow
bogomips        : 3014.65

processor       : 1
vendor_id       : AuthenticAMD
cpu family      : 6
model           : 6
model name      : AMD Athlon(TM) MP 1800+
stepping        : 2
cpu MHz         : 1533.697
cache size      : 256 KB
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : no
fpu             : yes
fpu_exception   : yes
cpuid level     : 1
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 apic sep mtrr pge mca cmov pat pse36 mmx fxsr sse syscall mp mmxext 3dnowext 3dnow
bogomips        : 3063.80

I can provide more info if you tell me how.  This same test passes on
a single CPU system running the same kernel built with nearly the
same options (in fact, I snagged its .config so that I could just
make the relevent changes for a dual system with AMD instead of Intel
processor):

david@...:~
$ uname -a
Linux apostrophe 2.6.5-686 #1 Tue Apr 13 01:53:00 EDT 2004 i686 GNU/Linux
david@...:~
$ cat usr/src/sbcl/customize-target-features.lisp 
(lambda (list)
  (pushnew :sb-thread list)
  (pushnew :sb-futex list))
david@...:~
$ cat /proc/cpuinfo 
processor       : 0
vendor_id       : GenuineIntel
cpu family      : 6
model           : 8
model name      : Celeron (Coppermine)
stepping        : 3
cpu MHz         : 568.271
cache size      : 128 KB
fdiv_bug        : no
hlt_bug         : no
f00f_bug        : no
coma_bug        : no
fpu             : yes
fpu_exception   : yes
cpuid level     : 2
wp              : yes
flags           : fpu vme de pse tsc msr pae mce cx8 sep mtrr pge mca cmov pat pse36 mmx fxsr sse
bogomips        : 1110.01

Apostrophe is a slug compared to vega.

-- 
I wouldn't mind the rat race so much if it wasn't for all the damn cats.

David Steuber <david@...> writes:

> functions, macros, and objects for threading?  That is, is there a
> place where I can look for some sort of tutorial on threaded
> programming in Lisp in general that will work with SBCL?

You meay check the CL Cookbook's introduction to threading:

  http://cl-cookbook.sourceforge.net


Paolo
-- 
Why Lisp? http://alu.cliki.net/RtL%20Highlight%20Film

On Thu, 2004-04-29 at 07:44, Daniel Barlow wrote:
> Dave Roberts <ldave@...> writes:
> 
> > There shouldn't be anything wrong with threads under Linux 2.4. There
> > are some scalability limits that are fixed by NPTL. NPTL is in various
> > Red Hat 2.4-based kernels (e.g. FC-1) and is standard in 2.6.
> 
> In 2.6 (and 2.4 kernels with NPTL backports) we use futexes for
> inter-thread locking.  In 2.4 that's not an option and we're using
> signals.  Either there's a kernel bug or an SBCL bug when these locks
> get seriously contended: wakeup signals are going astray somewhere.
> Advice I've had from kernel developers consisted mostly of "don't
> bother, stick to 2.6".  So I have.
> 
> If you know a reliable way to do scheduler-friendly locking absent
> futex support, please say, because nobody else is telling.

Don't know for sure. Doesn't Linuxthreads and the old posix threads
library have a set of mutex primitives? Are those what you say you're
already using on 2.4?

There obviously must be a way to do this without all sorts of bugs
because Linuxthreads has been around quite some time and there are at
least of couple of Java runtimes on 2.4 kernels. Each of these would
have to solve this same sort of issue.

That said, I don't know the exact mechanism. In the past, I have just
been a consumer of Java runtimes, not an implementor. ;-)

-- 
Dave Roberts <ldave@...>

Dave Roberts <ldave@...> writes:

> On Thu, 2004-04-29 at 07:44, Daniel Barlow wrote:

>> If you know a reliable way to do scheduler-friendly locking absent
>> futex support, please say, because nobody else is telling.
>
> Don't know for sure. Doesn't Linuxthreads and the old posix threads
> library have a set of mutex primitives? Are those what you say you're
> already using on 2.4?
>
> There obviously must be a way to do this without all sorts of bugs
> because Linuxthreads has been around quite some time and there are at
> least of couple of Java runtimes on 2.4 kernels. Each of these would
> have to solve this same sort of issue.

IANAGuru, but LinuxThreads was always extremely fugly and had severe
scalability problems.  Besides, it's my understanding that SBCL does
signal handling and memory management tricks that almost no C program
would do, so you run into issues pthreads programs didn't.

Run 2.6 and be happy.   :)

-Doug