I'm looking for a website containing the row source of common lisp, such as
"union", "intersection" like this..
I've just started learning Lisp and I've been being curious about how the
functions have been defined.
for instance,
"revappend" can be defined below
> (defun revappend (a b) (append (reverse a) b)))
then, how about other functions, such as "append", "cons", "union",
"intersection" and so forth. ??
is there any good website about containing above??
thanks in advance.
su..
"Kongzi" <······@ocpclub.com> writes:
> I'm looking for a website containing the row source of common lisp, such as
> "union", "intersection" like this..
>
> I've just started learning Lisp and I've been being curious about how the
> functions have been defined.
Entering
Lisp web site
into Google produced
http://www.franz.com/
http://www.cons.org/cmucl/
http://clisp.cons.org/
http://www.lisp.org/
http://www.corman.net/
as the first five hits (out of about 133,000). Five is chosen in a
rather arbitrary manner, but all of these are good starting points,
while, of course, these are not all the good starting points. Some of
them will lead you to raw source (maybe some of them also provide it
very well done...).
---Vassil.
Kongzi wrote:
> I'm looking for a website containing the row source of common lisp,
The `raw[1]' source code for a number of free implementations is
available for perusal. I've not looked but a place where I would start
would might be www.cons.org/cmucl. Then again this might be a wild goose
chase.
> such as "union", "intersection" like this..
In the back of ANSI Common Lisp[2] Paul Graham provides simple
definitions of a number of functions. Unfortunately this does not define
the union and intersection operations.
> I've just started learning Lisp and I've been being curious about how the
> functions have been defined.
Enjoy.
> for instance,
>
> "revappend" can be defined below
>>(defun revappend (a b) (append (reverse a) b)))
>
> then, how about other functions, such as "append", "cons", "union",
> "intersection" and so forth. ??
Sure. However, this strikes me as a kind of philosophical question. To
write a common lisp compiler you have to have certain axiomatic
functions, special forms and so on[3] in some kind of native binary way.
You can then go the wholehog and then define all of the ANSI specified
stuff this way -- which is what I *think* clisp does -- or pick out some
of the lower level stuff and write the rest of the functions in common
lisp. This is more what cmucl does.
The choice of axiomatic operation is to a large degree arbitrary. Of
these cons would be a good choice and would tend not to be defined in
terms of the other functions.
> is there any good website about containing above??
Hmmm. Not that I know of but there is a whole lot of sourcecode to look
at...
:)w
[1] I presume this is what you mean.
[2] The ANSI Common Lisp Book by Paul Graham, (1995) Prentice Hall.
[3] It would be worth reading round the meaning of function, special
form and macro in Common Lisp The Language by Guy Steele. An online
version is here: www.ida.liu.se/imported/cltl/clm/clm.html
* "Kongzi" <······@ocpclub.com>:
> I'm looking for a website containing the row source of common lisp, such as
> "union", "intersection" like this..
Get the source of a free Common Lisp-implementation and have a look.
There are several of them, see:
http://ww.telent.net/cliki/Common%20Lisp%20implementation
Also, IIRC, Corman Lisp also comes with source:
http://www.cormanlisp.com/
--
johs
"Kongzi" <······@ocpclub.com> writes:
> I'm looking for a website containing the row source of common lisp,
> such as "union", "intersection" like this..
Here are some example implementations of such functions.
(defun set-difference (list-1 list-2 &key (key #'identity) (test #'eql) test-not)
"Return the elements of list-1 that do not appear in list-2."
(let ((test (if test-not
(complement test-not)
test)))
(remove-if (lambda (list-1-element)
(member (funcall key list-1-element) list-2 :key key :test test))
list-1)))
(defun intersection (list-1 list-2 &key (key #'identity) (test #'eql) test-not)
"Return a list that contains every element that occurs in both list-1 and list-2."
(let ((test (if test-not
(complement test-not)
test)))
(remove-if (lambda (list-1-element)
(not (member (funcall key list-1-element) list-2 :key key :test test)))
list-1)))
(defun union (list-1 list-2 &key (key #'identity) (test #'eql) test-not)
(remove-duplicates (append list-1 list-2)
:key key
:test (if test-not
(complement test-not)
test)))
--
Frode Vatvedt Fjeld
In article <··············@vserver.cs.uit.no>,
Frode Vatvedt Fjeld <······@cs.uit.no> wrote:
> "Kongzi" <······@ocpclub.com> writes:
>
> > I'm looking for a website containing the row source of common lisp,
> > such as "union", "intersection" like this..
>
> Here are some example implementations of such functions.
>
> (defun set-difference (list-1 list-2 &key (key #'identity) (test #'eql)
> test-not)
> "Return the elements of list-1 that do not appear in list-2."
> (let ((test (if test-not
> (complement test-not)
> test)))
> (remove-if (lambda (list-1-element)
> (member (funcall key list-1-element) list-2 :key key :test test))
> list-1)))
>
> (defun intersection (list-1 list-2 &key (key #'identity) (test #'eql)
> test-not)
> "Return a list that contains every element that occurs in both list-1 and
> list-2."
> (let ((test (if test-not
> (complement test-not)
> test)))
> (remove-if (lambda (list-1-element)
> (not (member (funcall key list-1-element) list-2 :key key :test test)))
> list-1)))
>
> (defun union (list-1 list-2 &key (key #'identity) (test #'eql) test-not)
> (remove-duplicates (append list-1 list-2)
> :key key
> :test (if test-not
> (complement test-not)
> test)))
Are these intended to be pedagogical examples, or actual production
implementations? I guess I'd always imagined that -- at least if the
test was eql -- these functions would be more efficient than O(N*M),
perhaps by sorting the lists first and merging, or using a hash table to
index one of them.
Both CL and Dylan specify that the result order is undefined, and
therefore sorting would be allowed. I see that the CL hyperspec is
quite explicit that the result is (as if?) N*M calls to test are made,
while the DRM is less formal e.g. for intersection: "Returns a new
sequence containing only those elements of sequence1 that also appear in
sequence2."
The definition of "union" above seems particularly poor, since if
remove-duplicates is implemented in a corresponding way the complexity
will be O((n+m)^2).
The implementations of intersection and union in Gwydion Dylan are
similar to the above, but notably symmetrical:
define sealed method intersection
(list1 :: <list>, list2 :: <list>,
#key test :: <function> = \==)
=> (result :: <list>);
for (item in list1,
result :: <list> = #()
then if (member?(item, list2, test: test))
pair(item, result);
else
result;
end if)
finally
result;
end for;
end method;
define sealed method union
(list1 :: <list>, list2 :: <list>,
#key test :: <function> = \==)
=> (result :: <list>);
for (item in list1,
result :: <list> = list2
then if (member?(item, list2, test: test))
result;
else
pair(item, result);
end if)
finally
result;
end for;
end method;
It's also interesting that CL allows a :key argument, which Dylan does
not -- if :key is not #'identity then Dylan forces you to build a custom
test function e.g "method (a,b) a.key == b.key end".
-- Bruce
Bruce Hoult <·····@hoult.org> writes:
> Are these intended to be pedagogical examples, or actual production
> implementations? I guess I'd always imagined that -- at least if the
> test was eql -- these functions would be more efficient than O(N*M),
> perhaps by sorting the lists first and merging, or using a hash table to
> index one of them.
Hmmm, how would you sort them? By the value SXHASH returns for the
key? I think using a hash table is the only realistic choice (which
may also change the order). In any case, production quality code would
first see if the lengths of the arguments exceed some threshold, and do
the simple thing if they don't.
Also, production quality code may want to define the functions taking
keyword parameters in terms of auxiliary functions taking only
`regular' required parameters, and then define some compiler macros to
optimize calls for the number of simple and frequent cases of calling
these functions.
All in all, I think the margins of a Usenet posting are too small for
production quality code examples, if I am allowed to copy the phrase.
---Vassil.
P.S. Knowing how a lot of code in actual production looks like, on
second thought, maybe I am using `production quality code'
incorrectly...
* Vassil Nikolov wrote:
> P.S. Knowing how a lot of code in actual production looks like, on
> second thought, maybe I am using `production quality code'
> incorrectly...
What you mean is what I would refer to as `library quality' code.
--tim
In article <···············@panix3.panix.com>,
Vassil Nikolov <··········@poboxes.com> wrote:
> Bruce Hoult <·····@hoult.org> writes:
>
> > Are these intended to be pedagogical examples, or actual production
> > implementations? I guess I'd always imagined that -- at least if the
> > test was eql -- these functions would be more efficient than O(N*M),
> > perhaps by sorting the lists first and merging, or using a hash table to
> > index one of them.
>
> Hmmm, how would you sort them? By the value SXHASH returns for the
> key?
That would I think be appropriate if the user specified ":test #`equal"
but it's clearly not correct for :test #`eql.
For :test #`eq you could I think just sort by the raw
implementation-specific value of the object i.e. typically a pointer
with a couple of tag bits used to indicate that the value is actually an
integer or character stored within the "pointer". For the default :test
#`eql you'd need to do a bit more work.
> I think using a hash table is the only realistic choice (which
> may also change the order).
It also faces the problem that you know the test function to use, but
not the hash function. Once again, SXHASH would be appropriate for
:test #`equal, but not otherwise.
> In any case, production quality code would first see if the lengths
> of the arguments exceed some threshold, and do the simple thing if
> they don't.
Of course.
One thing in the favour of sorting and merging, where possible: it's
easy to do a quick test to see if the lists are *already* sorted (if
you're going to check the lengths to decide on which algorithm to use
then you can do that in the same pass) and in that case you only need to
do a merge. So if you're feeding the results of one union/intersection
to another one, you end up with O(n) complexity.
-- Bruce
* Bruce Hoult wrote:
> For :test #`eq you could I think just sort by the raw
> implementation-specific value of the object i.e. typically a pointer
> with a couple of tag bits used to indicate that the value is actually an
> integer or character stored within the "pointer".
Better hope that the GC never runs if you do this.
--tim
In article <···············@cley.com>, Tim Bradshaw <···@cley.com>
wrote:
> * Bruce Hoult wrote:
> > For :test #`eq you could I think just sort by the raw
> > implementation-specific value of the object i.e. typically a pointer
> > with a couple of tag bits used to indicate that the value is actually an
> > integer or character stored within the "pointer".
>
> Better hope that the GC never runs if you do this.
True, if it's a copying GC.
Actually it wouldn't matter as long as the GC runs before either list is
sorted, or after both are sorted. So, if your sort method itself
doesn't cons you should be fine. e.g. copy both lists into vectors (ok
if gc runs), sort them (shouldn't cons), merge them (ok if gc runs).
-- Bruce
Bruce Hoult <·····@hoult.org> writes:
> Actually it wouldn't matter as long as the GC runs before either list is
> sorted, or after both are sorted.
And there are no other threads that might cons, and...
---Vassil.
In article <···············@panix1.panix.com>,
Vassil Nikolov <··········@poboxes.com> wrote:
> Bruce Hoult <·····@hoult.org> writes:
>
> > Actually it wouldn't matter as long as the GC runs before either list is
> > sorted, or after both are sorted.
>
> And there are no other threads that might cons, and...
Sure, but if you're dealing with preemptive threads then *lots* of
things need mutexes -- or per-thread heaps.
-- Bruce
Bruce Hoult <·····@hoult.org> writes:
> > > Actually it wouldn't matter as long as the GC runs before either list is
> > > sorted, or after both are sorted.
> >
> > And there are no other threads that might cons, and...
>
> Sure, but if you're dealing with preemptive threads then *lots* of
> things need mutexes -- or per-thread heaps.
And that's exactly why programming languages need to have coroutines,
but not threads, while the operating system ideally provides
processes, but not threads. Nice systems (like the thread library in
Plan 9, or the concurrent language Alef) give you one set of CSP
primatives that work on both kinds of object.
For example, the window system is a concurrent program, with a process
for each of screen, keyboard, mouse, etc. Each of those sits in a
loop reading/writing to the device (hence the need for mediation by
the operating system) and then sending/receiving messages on a CSP
channel (hence the need for mediation by the runtime system). The
rest of the window system is a collection of coroutines that
communicate and synchronize via messages sent thru channels.
* Scott Schwartz wrote:
> And that's exactly why programming languages need to have coroutines,
> but not threads, while the operating system ideally provides
> processes, but not threads. Nice systems (like the thread library in
> Plan 9, or the concurrent language Alef) give you one set of CSP
> primatives that work on both kinds of object.
Sigh. And if you have a machine with more than one CPU (like almost
anything costing more than a few thousand dollars nowadays), your
program might, just possibly, want to be able to make use of more than
one CPU without doing manual shared memory or message passing. And to
do that you need... threads, supported by the OS.
--tim
Tim Bradshaw <···@cley.com> writes:
> * Scott Schwartz wrote:
> > And that's exactly why programming languages need to have coroutines,
> > but not threads, while the operating system ideally provides
> > processes, but not threads. Nice systems (like the thread library in
> > Plan 9, or the concurrent language Alef) give you one set of CSP
> > primatives that work on both kinds of object.
>
> Sigh. And if you have a machine with more than one CPU (like almost
> anything costing more than a few thousand dollars nowadays), your
> program might, just possibly, want to be able to make use of more than
> one CPU without doing manual shared memory or message passing. And to
> do that you need... threads, supported by the OS.
I'm not sure I agree with this. Occam and Erlang (I think!)
have something like this, and have been used in massively
multiprocessor applications.
--
Raymond Wiker Mail: ·············@fast.no
Senior Software Engineer Web: http://www.fast.no/
Fast Search & Transfer ASA Phone: +47 23 01 11 60
P.O. Box 1677 Vika Fax: +47 35 54 87 99
NO-0120 Oslo, NORWAY Mob: +47 48 01 11 60
Try FAST Search: http://alltheweb.com/
* Raymond Wiker wrote:
> I'm not sure I agree with this. Occam and Erlang (I think!)
> have something like this, and have been used in massively
> multiprocessor applications.
Well, almost by definition, whatever they were doing was either
supported by the OS, or there essentially was no OS (typically the
case with occam) and the program was running on the bare metal (so,
really, it was the OS). If you are sitting on a multiprocessor box
running (say) Unix or Wndows, then no user-level trick will give you
access to more than one processor, you have to create threads of which
the OS is aware, so it can schedule them across the processors on the
machine.
--tim
Tim Bradshaw <···@cley.com> writes:
> * Raymond Wiker wrote:
>
> > I'm not sure I agree with this. Occam and Erlang (I think!)
> > have something like this, and have been used in massively
> > multiprocessor applications.
>
> Well, almost by definition, whatever they were doing was either
> supported by the OS, or there essentially was no OS (typically the
> case with occam) and the program was running on the bare metal (so,
> really, it was the OS). If you are sitting on a multiprocessor box
> running (say) Unix or Wndows, then no user-level trick will give you
> access to more than one processor, you have to create threads of which
> the OS is aware, so it can schedule them across the processors on the
> machine.
*Or* you can create an application that uses several
processes, and the whatever threading mechanism the language runtime
provides internally in each process.
FWIW, the Erlang FAQ (somewhere at http://www.erlang.se) notes
that context switching between Erlang processes is typically one or
two orders of magnitude cheaper than switching between threads in a C
program. I'm not sure whether a single Erlang runtime can efficiently
use multiple processors, but there is certainly no problem with running
several Erlang runtimes in a large application. That should probably
count as a user-level trick :-)
This is similar to the situation under Occam, where you would
map processes to processors.
It does require a better understanding of the application (for
grouping of threads/processes), but IMO this is more than offset by
the simpler programming model and the better efficiency compared to
OS-level threads (or pthreads).
Disclaimer: I haven't written any Occam code in the last 12
years, and no Erlang code in the last 5 or 6 years. I also really,
*really* dislike the thread support I've seen for C and C++, under
Windows and Unix.
--
Raymond Wiker Mail: ·············@fast.no
Senior Software Engineer Web: http://www.fast.no/
Fast Search & Transfer ASA Phone: +47 23 01 11 60
P.O. Box 1677 Vika Fax: +47 35 54 87 99
NO-0120 Oslo, NORWAY Mob: +47 48 01 11 60
Try FAST Search: http://alltheweb.com/
* Raymond Wiker wrote:
> *Or* you can create an application that uses several
> processes, and the whatever threading mechanism the language runtime
> provides internally in each process.
Right. So now you have the lovely problem of managing memory yourself
and/or doing message passing. Very nice, I'm looking forward to
wasting the rest of my life already. Do you know why cache-coherent
shared-memory machines demolished everything else? That's right, they
were *easier to program*!
But wait, I see a way out! Lots of systems have shared memory
primitives (man -k shm), so you can start lots of processes, then
allocate a whacking great chunk of shared memory, share it among all
the processes, and whee, you are done. Well, not quite, you still
need to have (trip-through-the-kernel) interprocess locks for
allocation and freeing store, and you likely don't have
cache-coherency. And you still need to write a distributed GC if you
don't want Amdahl's law to kill you.
Hmm, now, does this remind you of something? OS-supported threads
perhaps?
> It does require a better understanding of the application (for
> grouping of threads/processes), but IMO this is more than offset by
> the simpler programming model and the better efficiency compared to
> OS-level threads (or pthreads).
I kind of wonder where this magic efficiency is supposed to come from?
If you look at serious threads implementations, you'll notice a couple
of interesting things. One is that they're layered, so you can have
multiple user threads with controllable bindings to kernel-supported
threads. Switches between user threads don't go through the kernel.
Another is that the vendors that support these serious implementations
are building their business on big shared-memory machines: they
*really* care about these things performing well.
--tim
Tim Bradshaw <···@cley.com> writes:
> If you look at serious threads implementations, you'll notice a couple
> of interesting things. One is that they're layered, so you can have
> multiple user threads with controllable bindings to kernel-supported
> threads. Switches between user threads don't go through the kernel.
The default thread library under Solaris is a combined user and kernel
level i.e. N:M. However, with Solaris 8 a second, compatible, thread
library is also available and this is 1:1 i.e. no user-level
scheduling. One reason for including this is given as :-
Since this is one-level implementation of the threads certain
applications can perform better with these libraries than the
standard libraries. Some of the benchmarks like Volano show
considerable improvements with these libraries.
http://supportforum.sun.com/freesolaris/techfaqs.html?techfaqs_2957
Tim Bradshaw <···@cley.com> writes:
> * Raymond Wiker wrote:
>
> > *Or* you can create an application that uses several
> > processes, and the whatever threading mechanism the language runtime
> > provides internally in each process.
>
> Right. So now you have the lovely problem of managing memory yourself
> and/or doing message passing. Very nice, I'm looking forward to
> wasting the rest of my life already. Do you know why cache-coherent
> shared-memory machines demolished everything else? That's right, they
> were *easier to program*!
You *don't* have to manage memory yourself. You will have to
use message-passing, though, but there is no reason that this should
be inherently less efficient than function calls. (Not a general
truth, but it certainly applies to the two examples I mentioned
earlier: Occam and Erlang.)
As far as ease of programming goes: what I've seen of threads
programming support in Java and C++ under Windows and Unix does not
strike me as particularly programmer-friendly.
> > It does require a better understanding of the application (for
> > grouping of threads/processes), but IMO this is more than offset by
> > the simpler programming model and the better efficiency compared to
> > OS-level threads (or pthreads).
>
> I kind of wonder where this magic efficiency is supposed to come from?
I mentioned a claim from the Erlang FAQ earlier. It also
seems to be the common case that OS-level threads have higher overhead
than user-level threads.
--
Raymond Wiker Mail: ·············@fast.no
Senior Software Engineer Web: http://www.fast.no/
Fast Search & Transfer ASA Phone: +47 23 01 11 60
P.O. Box 1677 Vika Fax: +47 35 54 87 99
NO-0120 Oslo, NORWAY Mob: +47 48 01 11 60
Try FAST Search: http://alltheweb.com/
Tim Bradshaw <···@cley.com> writes:
> * Scott Schwartz wrote:
> > And that's exactly why programming languages need to have coroutines,
> > but not threads, while the operating system ideally provides
> > processes, but not threads. Nice systems (like the thread library in
> > Plan 9, or the concurrent language Alef) give you one set of CSP
> > primatives that work on both kinds of object.
>
> Sigh. And if you have a machine with more than one CPU (like almost
> anything costing more than a few thousand dollars nowadays), your
> program might, just possibly, want to be able to make use of more than
> one CPU without doing manual shared memory or message passing. And to
> do that you need... threads, supported by the OS.
Sigh. Plan 9 applications have been happily taking advantage of high
end SMP machines for more than a decade. Some, like the window system
I described, were written in a concurrent language that didn't require
anything manual. On the contrary---it showed that having both
coroutines and processes available in a uniform way made it easier for
the programmer to produce a clean, correct, efficient, SMP application.
As I said, you need exactly one kind of primative in the OS. It can
share as much or as little between siblings as you want, and which is
called a "process". Linux too has adopted this mechanism, for good
reason. If your kernel has both "processes" and "threads" (like
e.g. Solaris), you've done something wrong.
"If people understood fork, we wouldn't have threads." -- Rob Pike
Scott Schwartz wrote:
> Sigh. Plan 9 applications have been happily taking advantage of high
> end SMP machines for more than a decade.
Excellent. Since this is comp.lang.lisp can you please tell me where I
can get an ANSI common lisp implementation for plan 9?
> As I said, you need exactly one kind of primative in the OS. It can
> share as much or as little between siblings as you want, and which is
> called a "process". Linux too has adopted this mechanism, for good
> reason.
With what mechanism, pray tell? Or is this simply a way of reinventing
the thread wheel using, say, IPC? Very pure, very abstract and may I
suggest, very time consuming.
> If your kernel has both "processes" and "threads" (like e.g. Solaris),
> you've done something wrong.
It is clear that I was under the misapprehension when I thought Solaris
*does not* have processes as such -- certainly since solaris 2.6 -- and
that the entities in solaris called processes are infact thinly
disguised threads. Or then again maybe these threads are thinly processes...
:)w
* Will Deakin wrote:
> It is clear that I was under the misapprehension when I thought
> Solaris *does not* have processes as such -- certainly since solaris
> 2.6 -- and that the entities in solaris called processes are infact
> thinly disguised threads. Or then again maybe these threads are thinly
> processes...
I think this is right. Inside there is just one kind of thing, and
processes and LWPs are just two useful abstractions on top of the
underlying thing. As well as these there are user-level threads which
have no kernel existence at all. I imagine other Unices are the same -
linux for instance seems to be except its `lightweight' processes are
made of lead (although I understand that a new,
aluminium-and-carbon-fibre version is in the works or maybe already
exists).
--tim
Tim Bradshaw <···@cley.com> writes:
> I think this is right. Inside there is just one kind of thing, and
> processes and LWPs are just two useful abstractions on top of the
> underlying thing.
Irrelevent, even if true, because what is visible outside the kernel
are distinct kinds of things. Man fork(), fork1(), _lwp_create(),
thr_create().
> As well as these there are user-level threads which
> have no kernel existence at all. I imagine other Unices are the same -
> linux for instance seems to be except its `lightweight' processes are
> made of lead
No, actually linux's processes (fork is a special case of clone,
recall) are much lighter weight than anything in Solaris. Notoriously
so. Check out the results from lmbench on e.g. context switch times.
* Scott Schwartz wrote:
> No, actually linux's processes (fork is a special case of clone,
> recall) are much lighter weight than anything in Solaris. Notoriously
> so. Check out the results from lmbench on e.g. context switch
> times.
I'd rather worry about the factors-of-10 slowdown you get when porting
many posix threads programs to linux (I have seen these, recently).
--tim
Tim Bradshaw <···@cley.com> writes:
> > No, actually linux's processes (fork is a special case of clone,
> > recall) are much lighter weight than anything in Solaris. Notoriously
> > so. Check out the results from lmbench on e.g. context switch
> > times.
>
> I'd rather worry about the factors-of-10 slowdown you get when porting
> many posix threads programs to linux (I have seen these, recently).
Are these publically available programs? If so what are they?
If not, what platforms are the ports being done from that are 10x quicker?
Also are the threads being used to overlap I/O (i.e. handful of
threads) or are they being used in some kind of simulator where each
object simulated is a separate thread?
Stephen J. Bevan wrote:
>>I'd rather worry about the factors-of-10 slowdown you get when porting
>>many posix threads programs to linux (I have seen these, recently).
> Are these publically available programs?
Probably not.
> If not, what platforms are the ports being done from that are 10x
> quicker?
Clearly I cannot speak for Tim Bradshaw -- unless I am secretly him ;)
However, I carried out some work with C and C++ -- not common lisp --
that looked at running some malloc testing code with posix threads
running under solaris 2.6 running on a 50MHz uniprocessor sparc against
Linux 2.2.2ish on a P450. IIRC with about 10 threads the 50MHz was about
as fast as the P450 and got better with more threads.
(This was when 2.4.2 was current. I will try and dig out some actual
numbers if you feel the urge. Although may result in me looking like I'm
lying...)
:)w
Will Deakin <···········@hotmail.com> writes:
> Clearly I cannot speak for Tim Bradshaw -- unless I am secretly him
> ;) However, I carried out some work with C and C++ -- not common
> lisp -- that looked at running some malloc testing code with posix
> threads running under solaris 2.6 running on a 50MHz uniprocessor sparc
> against Linux 2.2.2ish on a P450. IIRC with about 10 threads the 50MHz
> was about as fast as the P450 and got better with more threads.
What were the threads doing? It is not difficult to make a M:N thread
system look a lot better than a 1:1 system if all the threads are
doing CPU bound work and most thread switching is due to time-slice
pre-emption at the user-level. That's why I asked about simulation
systems since that's one example of where one might write that sort of
code (though this brings us back to Scott's point about coroutines).
On the other hand, I use threads to avoid an essentialy
single-threaded server (i.e. poll, kqueue, /dev/poll based) reacting
in a bursty manner by farming out some work to a few threads. These
threads are I/O bound and so M:N threads are no help at all, in fact
they are an unecessary overhead.
·······@dino.dnsalias.com (Stephen J. Bevan) wrote in message news:<··············@dino.dnsalias.com>...
> Are these publically available programs? If so what are they?
> If not, what platforms are the ports being done from that are 10x quicker?
> Also are the threads being used to overlap I/O (i.e. handful of
> threads) or are they being used in some kind of simulator where each
> object simulated is a separate thread?
No, they aren't publically available, in fact I can't even talk about
them too much. The original systems ran on (I think) Tru64 and HPUX
as well as some embedded systems. I/O multimplexing wasn't the
problem (if such a system has significant dependence on the threading
performance, I'd be, well, I'd *like* to be surprised, but actually
I'd just be depressed). Simulation is closer.
Sadly these kinds of discussions have become almost impossible to have
by now. Linux has become such a religion that to suggest anything
else (except for something suitably obscure like plan 9 / inferno, or
something even more ideologically sound) might actually be better
results in a howling mob descending, because free software must be
better, right? Right.
So we're fighting away about how Linux (or is it Plan 9, I forget) is
so much better, or not, and whether Plan 9's single-type-of-thing
model is better, because that's interesting, and we get to burn the
enemies of free software at the stake after forcing them to publically
recant. But we're not bothering to talk about minor details like
having to write a distributed GC system, which just might make *much*
more difference for real multiprocessor systems, so long as we care
about performance instead of politics.
Well, I recant, you can burn me now.
--tim
Tim Bradshaw wrote:
> Sadly these kinds of discussions have become almost impossible to have
> by now. Linux has become such a religion that to suggest anything
> else (except for something suitably obscure like plan 9 / inferno, or
> something even more ideologically sound) might actually be better
> results in a howling mob descending, because free software must be
> better, right? Right.
Actually, you'll find many Linux gurus will readily admit
that Linux threads do suck. But: they are often not necessary,
since Linux heavyweight process operations are often faster
than the HWP operations in other OSes, and the Linux threads
*are* getting better, with changes at both the kernel and user
library levels.
The thread problem is being addressed in part because it's
inhibiting the use of Linux as a java platform.
See (for example) the link I posted before for some recent
work on Linux threads -- all discussed without torches or
pitchforks. http://lwn.net/Articles/10378/
Paul
> Actually, you'll find many Linux gurus will readily admit
> that Linux threads do suck. But: they are often not necessary,
> since Linux heavyweight process operations are often faster
> than the HWP operations in other OSes, and the Linux threads
> *are* getting better, with changes at both the kernel and user
> library levels.
Yes, I know, but Linux gurus are normally not part of the mob.
--tim
··········@tfeb.org (Tim Bradshaw) writes:
> .... I/O multimplexing wasn't the
> problem (if such a system has significant dependence on the threading
> performance, I'd be, well, I'd *like* to be surprised, but actually
> I'd just be depressed). Simulation is closer.
If simulation is closer then that would more than likely run better on
a M:1 based system than a 1:1 based system. In that case I would not
use the default 1:1 Linux threads and instead use an M:N version. As
I noted in another message, this similar to the situation in Solaris
except that it defaults to M:N rather than 1:1.
> Sadly these kinds of discussions have become almost impossible to have
> by now. Linux has become such a religion that to suggest anything
> else
Saying Linux threads suck and not suggesting anything else or
explaining the problem domain is not much of a discussion.
> ... But we're not bothering to talk about minor details like
> having to write a distributed GC system, which just might make *much*
> more difference for real multiprocessor systems ...
By all means start a thread on distributed GC.
>
> Saying Linux threads suck and not suggesting anything else or
> explaining the problem domain is not much of a discussion.
But they do suck. Every time I have tried to do anything which
involved porting (posix usually) threaded programs to Linux I found
that (a) the performance was very often terrible, and (b) that things
became *extremely* sensitive to exact compiler versions &c. The whole
experience was just painful. Furthermore, whenever I ask people about
this I get two kinds of answers:
1. Yes, they suck, sorry. Kernel x.y.z has some improvements, and you
can try these patches, and this version of gcc will work, and you need
this flag when you build it. People are working on this stuff, and
the future a.b kernels are going to be a lot better, we hope.
2. Linux, like, ROOLZ man! Sun/HP/IBM/SGI (delete as appropriate)
will be moving to Linux next week. Kill Bill Gates! Linux threads
are *king* dude, nothing performs better, and here's this bogus faked
up benchmark that shows how good they are (like, I/O-bound threads
perform OK. Well: yes? hello?). Install Linux on your machine and it
will be 96x faster! Look at my KOOL TSHIRT!
Well, sorry, I listen to the (1) people and ignore the rest. Apart
from anything else, they smell really bad.
--tim
··········@tfeb.org (Tim Bradshaw) writes:
> > Saying Linux threads suck and not suggesting anything else or
> > explaining the problem domain is not much of a discussion.
>
> But they do suck. Every time I have tried to do anything which
> involved porting (posix usually) threaded programs to Linux I found
> that (a) the performance was very often terrible, and (b) that things
> became *extremely* sensitive to exact compiler versions &c. The whole
> experience was just painful.
It is clear you've had problems porting threaded programs. What isn't
clear is *why* you've had problems. I've ported threaded programs
between Solaris, Linux, FreeBSD and OpenBSD and the problems I've had
were with the user-level threads on *BSD (specifically problems with
certain system calls blocking the whole process and not just the
thread), not the 1:1 threads in Linux. As such I've seen no sucky
behaviour under Linux. That doesn't mean it is not possible to write
threaded programs that don't work well with 1:1 threads but that's not
exactly a revelation and it is why M:N threads also exist for Linux.
Perhaps you've investigated using them and rejected them? It is hard
to know since you've shared very few details and instead just keep
pronouncing that "Linux threads suck".
·······@dino.dnsalias.com (Stephen J. Bevan) wrote in message news:<··············@dino.dnsalias.com>...
> It is hard
> to know since you've shared very few details and instead just keep
> pronouncing that "Linux threads suck".
Yes, sorry the details are confidential (I don't even work with the
company concerned any more). Suffice to say that taking C++/pthreads
programs which worked well on several other systems and getting them
to work on Linux reasonably was a serious pain. I think that the
eventual solution was to stop using pthreads and invent a
compatibility layer which sat on top of some Linux threads system, or
pthreads everywhere else (this was what the Linux system vendor
recommended, anyway).
--tim
* Scott Schwartz wrote:
> No, actually linux's processes (fork is a special case of clone,
> recall) are much lighter weight than anything in Solaris. Notoriously
> so. Check out the results from lmbench on e.g. context switch times.
Incidentally, lmbench measures *process* context switches, not thread
context switches. I guess linux fandom has obscured the truth, again.
--tim
Will Deakin <···········@hotmail.com> writes:
> Excellent. Since this is comp.lang.lisp can you please tell me where I
> can get an ANSI common lisp implementation for plan 9?
clisp should be easy to port.
> With what mechanism, pray tell?
rfork() and clone(), respectively. Performance is excellent.
> Or is this simply a way of reinventing
> the thread wheel using, say, IPC? Very pure, very abstract and may I
> suggest, very time consuming.
It's a way of having exactly one concurrency primative in your kernel
instead of two (incompatable) ones.
Scott Schwartz wrote:
> Will Deakin <···········@hotmail.com> writes:
>>Excellent. Since this is comp.lang.lisp can you please tell me where I
>>can get an ANSI common lisp implementation for plan 9?
> clisp should be easy to port.
I take it from this that for plan 9 has *no* ANSI common lisp
implementation. Please feel free to correct me if I am wrong.
You suggest that I could port clisp, which in itself is an excellent
idea. With regard to this discussion at hand a few issues now come to
mind. For its many excellent attributes, clisp as a bytecode compiler
is, in general, slower than native code implementations. This should be
no suprise and -- I believe -- is one by design as it porting easier[1].
How am I then to take advantage of the excellent characteristics of this
OS *if* I can't compile to native code? Or is the speed up obtained with
plan 9 sufficiently good that it would be worthwhile, say, to porting a
system running with cmucl on a four cpu E450 under solaris 8 to clisp on
the same hardware with plan 9?
>>With what mechanism, pray tell?
> rfork() and clone(), respectively. Performance is excellent.
Cool. You have now stated several times that performance is excellent.
How can I measure this? Is there anyway that you could quantify this
between, say, Solaris 8, plan 9 and linux 2.4.nn? Is this speedup 100%,
an order-of-magnitude, or what?
>>Or is this simply a way of reinventing
>>the thread wheel using, say, IPC? Very pure, very abstract and may I
>>suggest, very time consuming.
> It's a way of having exactly one concurrency primative in your kernel
> instead of two (incompatable) ones.
(I think) I buy the two concurrency primative argument -- but I would be
interested in more detail about the incompatability of this.
:)w
[1] This is not intended as a critism of clisp.
Will Deakin <···········@hotmail.com> writes:
> >>With what mechanism, pray tell?
> > rfork() and clone(), respectively. Performance is excellent.
> Cool. You have now stated several times that performance is
> excellent. How can I measure this? Is there anyway that you could
> quantify this between, say, Solaris 8, plan 9 and linux 2.4.nn? Is
> this speedup 100%, an order-of-magnitude, or what?
Since several of the modern BSD derivatives implement the rfork()
system call in a fashion semantically identical to Plan 9, it should
not be too hard for a motivated individual to figure what the real
story is.
Carl Shapiro wrote:
> Since several of the modern BSD derivatives implement the rfork()
> system call in a fashion semantically identical to Plan 9,
Your comments are noted with interest.
> it should not be too hard for a motivated individual to figure
> what the real story is.
Do you have any feel or data for this? Or is this merely an injection in
the vein of `So then senator, when did you stop beating your wife?'
Will Deakin <···········@hotmail.com> writes:
> Carl Shapiro wrote:
> > Since several of the modern BSD derivatives implement the rfork()
> > system call in a fashion semantically identical to Plan 9,
> Your comments are noted with interest.
> > it should not be too hard for a motivated individual to figure what
> > the real story is.
> Do you have any feel or data for this? Or is this merely an injection
> in the vein of `So then senator, when did you stop beating your wife?'
Sorry, but I don't think I'm following you here. The UNIX family of
operating systems has had system calls like rfork() and clone() in the
form of sproc() for well over a decade. The places where sproc()
performs well are typically the same places that kernel scheduled
threads perform well. The virtues of the different types of thread
mappings are well discussed in the literature; it is naive to assume
that you can couch all exercises in threads programming in terms of
exactly one thread or process interface while preserving "excellent"
performance on all fronts.
Carl Shapiro wrote:
> Sorry, but I don't think I'm following you here.
Maybe because I've lost the plot...
The problem is likely to be mine. I was unhappy with the response `it
should not be too hard for a motivated individual to figure what the
real story is.' Although I *think* I am motivated I would struggle to
do this. YMMV. Say, I wanted to carry out tests to look at this. I
have access to machines with SMP under solaris or linux but not plan 9
or BSD. This would then be a really quite hard to then install plan 9
or BSD.
> The UNIX family of operating systems has had system calls like
> rfork() and clone() in the form of sproc() for well over a decade.
> The places where sproc() performs well are typically the same
places > that kernel scheduled threads perform well.
Thank you for this. I was vaguely aware of the rfork and clone
commands but was struggling to plot this on my map of the world.
> The virtues of the different types of thread mappings are well
> discussed in the literature;
Mea culpa. Maybe I need to spend more time reading the literature.
> ...it is naive to assume that you can couch all exercises in threads
> programming in terms of exactly one thread or process interface
> while preserving "excellent" performance on all fronts.
Yes. Clearly there are trades offs. My approach to this would be to
try some kind of prototyping and testing.
:)w
Will Deakin wrote:
> ...This would then be a really quite hard to then install plan 9
^^^
for me
(What I mean by this is that I don't necessarily have control over
these machines or they are used for other things.)
Will Deakin <···········@hotmail.com> writes:
> > rfork() and clone(), respectively. Performance is excellent.
> Cool. You have now stated several times that performance is excellent.
> How can I measure this?
lmbench, for starters. I don't have up to date results, but the
second edition was about the same as linux (2.2.x), or a little worse.
Or just use the system for a while. Practically every nontrivial
program in Plan 9 is build along the lines I've described. They work
fine.
I don't want my other point to get lost. The relevence to a
programming language newsgroup is that you want a clean way to write
concurrent programs. Surely lisp users are willing to sacrifice some
performance in favor of a better programming model? I admit that
there is an element of taste and preference here, but at least look at
how a really nice system works before rejecting it.
Scott Schwartz wrote:
> lmbench, for starters. I don't have up to date results, but the
> second edition was about the same as linux (2.2.x), or a little worse.
Thanks for the pointer.
> ...The relevence to a programming language newsgroup is that you
> want a clean way to write concurrent programs.
Amongst other things, yes.
> Surely lisp users are willing to sacrifice some performance in favor
> of a better programming model?
This I think is the nub of our discussion for which there are clearly
there are a number of views on this. FWIW *I* would sacrifice some
performance in favour of a better model if I was convinced *it were* a
better programming model.
> I admit that there is an element of taste and preference here, but at
> least look at how a really nice system works before rejecting it.
I agree. (I also wasn't trying to suggest that any system -- such as
plan 9 -- should be rejected out of hand. I was looking for
clarification as to why the plan 9 way was `nicer,' say, than the
solaris one.)
:)w
Will Deakin <···········@hotmail.com> writes:
> Or is
> the speed up obtained with plan 9 sufficiently good that it would be
> worthwhile, say, to porting a system running with cmucl on a four cpu
> E450 under solaris 8 to clisp on the same hardware with plan 9?
The last version of Plan 9 with explicit SPARC support was the second
edition (released 1995). The most recent version of Plan 9 (fourth
edition, 2002) does not (currently) run on a SPARC. A few people have
expressed an interest in doing the port but no port is as yet
available.
* Scott Schwartz wrote:
> As I said, you need exactly one kind of primative in the OS. It can
> share as much or as little between siblings as you want, and which is
> called a "process". Linux too has adopted this mechanism, for good
> reason. If your kernel has both "processes" and "threads" (like
> e.g. Solaris), you've done something wrong.
Or something to get performance. Threading on Linux *really* sucks.
Plan 9 may be better, of course.
--tim
From: Paul F. Dietz
Subject: Re: Lisp function define
Date:
Message-ID: <3D9DDA23.20607@dls.net>
Tim Bradshaw wrote:
> Threading on Linux *really* sucks.
This is supposed to be changing soon in the 2.5.* development
kernels:
http://lwn.net/Articles/10378/
The improvements allow a benchmark where 100,000 threads were
created to run in less than 2 seconds, when it would previously
have taken 15 minutes (due to some bad algorithms in the kernel).
Paul
Bruce Hoult <·····@hoult.org> writes:
[how SXHASH would not always be appropriate]
True, though using SXHASH (or hashing on #'EQUAL) won't give incorrect
results where EQL-ness matters, just poorer performance (unless I am
making a stupid mistake I don't see in the dark); I guess not so poor
in the `average' case (83.7% of the cases, or at least 73.5%).
And anyway the test argument to UNION and friends can be anything
(unlike with (Common Lisp) hash-tables), so doing the Right Thing
is an interesting problem...
[...]
> you're going to check the lengths to decide on which algorithm to use
> then you can do that in the same pass
Well, not quite, since all I would do is test for
(endp (nthcdr set-size-threshold-for-sophisticated-handling list))
(who took away NTHREST, by the way?).
---Vassil.
Bruce Hoult <·····@hoult.org> writes:
> Are these intended to be pedagogical examples, or actual production
> implementations? I guess I'd always imagined that -- at least if
> the test was eql -- these functions would be more efficient than
> O(N*M), perhaps by sorting the lists first and merging, or using a
> hash table to index one of them.
They were mostly intended as pedagocial examples. But I must say it's
not obvious to me how to improve these implementations substantially
(perhaps except union) while taking such factors as code size, garbage
creation, and running time for small inputs into account, as well as
running time for large inputs. If you have specific suggestions, in
Common Lisp (I don't read Dylan), that'd be interesting.
Here is intersection from CMUCL, as an example of what I suppose
counts as "production code" to many, for comparison:
(defun cmucl-intersection (list1 list2 &key key
(test #'eql testp) (test-not nil notp))
"Returns the intersection of list1 and list2."
(declare (inline member))
(if (and testp notp)
(error "Test and test-not both supplied."))
(let ((res nil))
(dolist (elt list1)
(if (with-set-keys (member (apply-key key elt) list2))
(push elt res)))
res))
This seems to me to have the same big-O complexity as my
version. However, the CMUCL one will always cons up a new list,
whereas mine will (almost) only do so when required (given an
appropriate remove-if). Also, CMUCL does the with-set-keys thing
inside the loop, which I'd expect yields a higher constant factor in
running time.
(defun my-intersection (list-1 list-2
&key (key #'identity) (test #'eql) test-not)
"intersection returns a list that contains every element that
occurs in both list-1 and list-2."
(let ((test (if test-not
(complement test-not)
test)))
(remove-if (lambda (list-1-element)
(not (member (funcall key list-1-element) list-2
:key key :test test)))
list-1)))
--
Frode Vatvedt Fjeld
In article <············@news1.kornet.net>,
"Kongzi" <······@ocpclub.com> wrote:
> I'm looking for a website containing the row source of common lisp, such as
> "union", "intersection" like this..
>
> I've just started learning Lisp and I've been being curious about how the
> functions have been defined.
No on eseems to have come up with *exactly* what you asked for. I'd
expect CMUCL to have, say, a cvsweb interface, but I don't know where.
The source of the Gwydion Dylan compiler might be interesting to you.
It's not CL, but it's quite closely-related. The interesting stuff for
you is probably the runtime library:
http://www.gwydiondylan.org/cgi-bin/cvsweb/src/d2c/runtime/dylan
-- Bruce
Bruce Hoult <·····@hoult.org> writes:
> In article <············@news1.kornet.net>,
> "Kongzi" <······@ocpclub.com> wrote:
>
> > I'm looking for a website containing the row source of common lisp, such as
> > "union", "intersection" like this..
> >
> > I've just started learning Lisp and I've been being curious about how the
> > functions have been defined.
>
> No on eseems to have come up with *exactly* what you asked for. I'd
> expect CMUCL to have, say, a cvsweb interface, but I don't know where.
Given that the OP is learning CL, I'd hope he has a working system
installed. If it's Emacs + ILISP + CMUCL, then typing the name of the
function followed by M-. will bring him to it's definition, if he has
the sources installed. Which is way more convenient than browsing cvs
via a web interface.
That said, the SBCL sources are here:
<http://cvs.sourceforge.net/cgi-bin/viewcvs.cgi/sbcl/sbcl/src/code/>
--
/|_ .-----------------------.
,' .\ / | No to Imperialist war |
,--' _,' | Wage class war! |
/ / `-----------------------'
( -. |
| ) |
(`-. '--.)
`. )----'