Some background: I work in the communications infrastructure market (I build
datacomm switches). One of the things that has always interested me is
trying to find better tools to do that job. Most datacomm switches are
programmed using C with VxWorks or (now) embedded Linux as the OS. As a
result, we suffer all the standard problems that you'd expect to find on
such a system: corrupted memory, various malloc/free problems, etc.
Further, programmer productivity is lower than it should be.
So, a natural question is how a Lisp-like language could be create for this
environment. I remember that Naughty Dog software wrote the video game Jax
and Dexter in a Scheme-like language that they created for the purpose, the
compiler for which was written in CL, I believe.
I know that CL has various efficiency limitations driven by its requirements
to support various features. You can write very efficient CL, but you have
to use a lot of type declarations, etc., and you have to stick to the
center of the envelope.
So, if you could strip down a Lisp and make it as fast as possible, what
would it start to look like? That is, where are the efficiency bottlenecks
on a Lisp? If the limitations were, you have to retain GC, lambdas, macros,
and functions, but you can change just about anything else about Lisp to
make it an efficient, bit-banging language that is as close to C in
performance as you can get (so, essentially a version of Lisp that is
optimized to fiddle with raw storage the way that C can), what would you
end up with? Would it essentially be something like CL with a huge number
of declarations (memories of that optimization challenge that was floating
around here a few months ago)? Which features would have you have drop and
which could you retain?
--
Dave Roberts, ·············@re-move.droberts.com
Slowly but surely, the programming world is finding Lisp...
http://www.findinglisp.com/blog
Dave Roberts <·············@re-move.droberts.com> wrote in message news:<···················@attbi_s52>...
> So, if you could strip down a Lisp and make it as fast as possible, what
> would it start to look like? That is, where are the efficiency bottlenecks
> on a Lisp? If the limitations were, you have to retain GC, lambdas, macros,
> and functions, but you can change just about anything else about Lisp to
> make it an efficient, bit-banging language that is as close to C in
> performance as you can get (so, essentially a version of Lisp that is
> optimized to fiddle with raw storage the way that C can), what would you
> end up with? Would it essentially be something like CL with a huge number
> of declarations (memories of that optimization challenge that was floating
> around here a few months ago)? Which features would have you have drop and
> which could you retain?
I think you'd end up with C-with-macros, and probably with some of C's
performance misfeatures removed (better aliasing control for instance,
although recent C standards have, I think, made this better). There's
no reason I can see that you can't do this now - we all have Lisp
systems which generate HTML as output, why would generating C be much
harder?
But that's probably not what you want. I don't know what your
performance issues look like, but what they are can very much alter
the kind of optimisation you need to do. If it's `must be as fast as
it possibly can' then you want incredibly good code generation - all
the rendering code for video games must be like this. But perhaps
it's some kind of bounded-response issue - you don't need to squeeze
every last drop out of the processor, but you do need an answer in
250uS with no excuses at all. Or you want some mixture.
What *we* want is very good performance, but only in some parts of the
program. Those end up in C, where we can have very good control of
data layout so we can really try and exploit the memory system. The
rest is in the noise performance-wise, and we do this in a
higher-level language (though not, currently, Lisp). This is just
what we need though.
--tim
Tim Bradshaw wrote:
> I think you'd end up with C-with-macros, and probably with some of C's
> performance misfeatures removed (better aliasing control for instance,
> although recent C standards have, I think, made this better). There's
> no reason I can see that you can't do this now - we all have Lisp
> systems which generate HTML as output, why would generating C be much
> harder?
Sure. Whether you compile to C or directly to machine code is neither here
nor there. It's just another translation step. The main point is how much C
code do you generate. C isn't a panacea. We have all seen horribly coded C
programs that run slower than anything in a Lisp system. The question is
just one of degree. If you generate reams of C, you're no better off. The
question is, can you generate no more C code than the average C programmer
would have done anyway, that runs at least as fast?
> But that's probably not what you want. I don't know what your
> performance issues look like, but what they are can very much alter
> the kind of optimisation you need to do. If it's `must be as fast as
> it possibly can' then you want incredibly good code generation - all
> the rendering code for video games must be like this. But perhaps
> it's some kind of bounded-response issue - you don't need to squeeze
> every last drop out of the processor, but you do need an answer in
> 250uS with no excuses at all. Or you want some mixture.
It's a mixture. Typically, in a switch, you have parts that are bounded,
soft realtime constraints. For instance, protocols will often have a
keep-alive portion to a remote peer. You have to generate a hello protocol
in so many (milli-)seconds. Other parts can be "give me all you got" sorts
of code, however. Typically, this is in the datapath portion of things.
While we use ASICs and other hardware to handle a lot of traffic, there are
always parts that have to be dealt with in software. You try to minimize it
as much as you can, but you always find something. For those parts, the
overall system performance is directly related to code speed and so you
want every machine cycle you can get.
> What *we* want is very good performance, but only in some parts of the
> program. Those end up in C, where we can have very good control of
> data layout so we can really try and exploit the memory system. The
> rest is in the noise performance-wise, and we do this in a
> higher-level language (though not, currently, Lisp). This is just
> what we need though.
Yea, I was sort of thinking whether you/we could migrate some of those
sections that are memory layout sensitive into Lisp, too. It seems like you
could use Lisp to define structures very similar to C, assuming you have
the help of the compiler to make it efficient. This is one thing that most
high-level programming languages fall down on. They are so high level that
they treat memory as a big black box. This is one area where C excels. You
can spec things down to the byte and if you know which processor type
you're running on, you can account for byte order issues, etc. Essentially,
you know where everything is located and all accesses map down to
individual load-stores with offsets which are very efficient on modern
hardware. The question is, could you bring that level of access into a
Lisp, so you can get the C-like performance by have the Lisp-like
productivity characteristics?
--
Dave Roberts, ·············@re-move.droberts.com
Slowly but surely, the programming world is finding Lisp...
http://www.findinglisp.com/blog
Gensym was in a similar boat and wrote a Lisp-to-C translator, called
ThinLisp. It's now under a BSD-style license. I've used it for a tiny
OpenGL application, but there are several things I didn't like. First
of all, it's peculiar to the Lisp style used at Gensym, so you end up
with a subset of CL with some undocumented deviations. It doesn't rely
on a garbage collector (although I didn't notice any barriers to
dropping in the Boehm-Demers-Weiser collector), but instead makes
heavy use of dynamic-extent declarations and object pooling. I think
the code generation code is pretty convoluted. Right now, there's now
way to write "in-line" C like there is in ECL, which is a big loss,
and I was totally at a loss as to how to add that functionality. The C
datatype mangler is also pretty convoluted, but short.
Now, the good thing about ThinLisp is that it produces C code that is
very much human readable, and I didn't see any obvious performance
weak spots. I can't speak with authority, but most of the code it
produces seems to have a constant number of lines to do package
management/etc. over what a C programmer would write. The unique thing
is that it compiles to static C - there's only a thin layer of
function glue over a C library. That means it produces very small and
portable code, but you don't get eval. C functions are called
directly, and data boxing is really obvious to see and control.
The ThinLisp website is http://www.thinlisp.org/. If you want to try
it, I've patched it up and added some stuff (though I can't release
the more substantial program) and made a tarball available at
http://voodoohut.homeunix.net/thinlisp-1.1.tar.gz. As soon as I'm able
to remember how I registered at SourceForge, I'll upload it there too.
Vladimir
Vladimir Sedach wrote:
> Gensym was in a similar boat and wrote a Lisp-to-C translator, called
> ThinLisp. It's now under a BSD-style license. I've used it for a tiny
> OpenGL application, but there are several things I didn't like. First
> of all, it's peculiar to the Lisp style used at Gensym, so you end up
> with a subset of CL with some undocumented deviations. It doesn't rely
> on a garbage collector (although I didn't notice any barriers to
> dropping in the Boehm-Demers-Weiser collector), but instead makes
> heavy use of dynamic-extent declarations and object pooling. I think
> the code generation code is pretty convoluted. Right now, there's now
> way to write "in-line" C like there is in ECL, which is a big loss,
> and I was totally at a loss as to how to add that functionality. The C
> datatype mangler is also pretty convoluted, but short.
>
> Now, the good thing about ThinLisp is that it produces C code that is
> very much human readable, and I didn't see any obvious performance
> weak spots. I can't speak with authority, but most of the code it
> produces seems to have a constant number of lines to do package
> management/etc. over what a C programmer would write. The unique thing
> is that it compiles to static C - there's only a thin layer of
> function glue over a C library. That means it produces very small and
> portable code, but you don't get eval. C functions are called
> directly, and data boxing is really obvious to see and control.
Interesting, I'll check it out.
--
Dave Roberts, ·············@re-move.droberts.com
Slowly but surely, the programming world is finding Lisp...
http://www.findinglisp.com/blog
From: Tim Bradshaw
Subject: Re: Fundamentals of Lisp efficiency?
Date:
Message-ID: <ey3oenr57ok.fsf@cley.com>
* Dave Roberts wrote:
> Sure. Whether you compile to C or directly to machine code is neither here
> nor there.
Actually, it kind of is. C is relatively hard to optimise in many
cases (compared to, say, FORTRAN 77 or before - later Fortran
standards have become harder too). It may be that machine-generated C
stands a better chance than human-generated C.
> The question is, can you generate no more C code than the average C
> programmer would have done anyway, that runs at least as fast?
Who cares how much you generate? Final memory size might matter for
space-constrained applications, but not how much C there is.
> Yea, I was sort of thinking whether you/we could migrate some of those
> sections that are memory layout sensitive into Lisp, too.
For us this would be a non-issue, since this stuff is relatively
simple array-bashing code that we then use a lot.
--tim
Tim Bradshaw wrote:
> * Dave Roberts wrote:
>> Sure. Whether you compile to C or directly to machine code is neither
>> here nor there.
>
> Actually, it kind of is. C is relatively hard to optimise in many
> cases (compared to, say, FORTRAN 77 or before - later Fortran
> standards have become harder too). It may be that machine-generated C
> stands a better chance than human-generated C.
>
>> The question is, can you generate no more C code than the average C
>> programmer would have done anyway, that runs at least as fast?
>
> Who cares how much you generate? Final memory size might matter for
> space-constrained applications, but not how much C there is.
>
>> Yea, I was sort of thinking whether you/we could migrate some of those
>> sections that are memory layout sensitive into Lisp, too.
>
> For us this would be a non-issue, since this stuff is relatively
> simple array-bashing code that we then use a lot.
>
> --tim
I think we're saying the same thing, but differently. I agree with you; it
isn't about the actual number of lines of C at all. That was sort of my
point, but I probably said it wrong. I was just reacting that compiling
down to C would be any better than just taking it all the way to machine
code. No diff other than it's more portable to go to C and take advantage
of the C compiler's backend so you don't have to write your own.
--
Dave Roberts, ·············@re-move.droberts.com
Slowly but surely, the programming world is finding Lisp...
http://www.findinglisp.com/blog
Hello!
Dave Roberts <·············@re-move.droberts.com> wrote:
>[...]
>Yea, I was sort of thinking whether you/we could migrate some of those
>sections that are memory layout sensitive into Lisp, too. It seems like you
>could use Lisp to define structures very similar to C, assuming you have
>the help of the compiler to make it efficient. This is one thing that most
>high-level programming languages fall down on. They are so high level that
>they treat memory as a big black box. This is one area where C excels. You
>can spec things down to the byte and if you know which processor type
>you're running on, you can account for byte order issues, etc. Essentially,
>you know where everything is located and all accesses map down to
>individual load-stores with offsets which are very efficient on modern
>hardware.
Not really. The C standard doesn't specify the padding of structure fields,
AFAIK it doesn't even specify that the compiler would have to keep the
order of the fields.
I've heard from Ada people that Ada seems to have much more precisely
defined ways to define memory layouts if needed, so you could probably
write a truly portable specification for e.g. the IP header format
in Ada without resorting to ifdef hackery or __attribute__((packed))
(which is GCC, but not standard) or so.
>The question is, could you bring that level of access into a
>Lisp, so you can get the C-like performance by have the Lisp-like
>productivity characteristics?
I'd guess yes, at least with a few compiler extensions. Perhaps you
could define a way to access arrays of ([un]signed-byte 8) in byte,
word, etc. units (the units the CPUs usually support well) as
additional primitives. And perhaps to create array descriptors for
already present ranges of memory... Anything else could probably
be based upon that and defun/defmacro/...
Btw, Erlang has a quite good syntax for destructuring binary data
with contained bit-fields and so on.
Kind regards,
Hannah.
······@schlund.de (Hannah Schroeter) writes:
> Not really. The C standard doesn't specify the padding of structure fields,
> AFAIK it doesn't even specify that the compiler would have to keep the
> order of the fields.
Yes, the compiler has to keep the order of the fields. (I'd quote you
chapter and verse, but my C89 standard is at home.) True, the
standard does not specify padding but there's enough commonality
between implementations that it's not too much of a problem.
--
Alan Shutko <···@acm.org> - I am the rocks.
The little I know I owe to my ignorance - Sacha Guitry
······@schlund.de (Hannah Schroeter) writes:
> Not really. The C standard doesn't specify the padding of structure fields,
> AFAIK it doesn't even specify that the compiler would have to keep the
> order of the fields.
Well, I still haven't bought the actual standard, but N869
6.5.8 (Relational operators) #5 does specify that "pointers to
structure members declared later compare greater than pointers
to members declared earlier in the structure".
Bit-fields are different, though.
In article <···················@attbi_s52>,
Dave Roberts <·············@re-move.droberts.com> wrote:
> So, if you could strip down a Lisp and make it as fast as possible, what
> would it start to look like? That is, where are the efficiency bottlenecks
> on a Lisp?
I recall a paper on this topic that was given about a dozen years ago at
a Lisp Users Group conference. I think the presentation was from a
company that had an embedded Lisp product, and needed real-time
performance guarantees. A major theme was avoiding GC.
Sorry, I don't remember the name of the company or presenter, but
perhaps this will jog someone's memory.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
Barry Margolin <······@alum.mit.edu> wrote in message news:<····························@comcast.dca.giganews.com>...
> I recall a paper on this topic that was given about a dozen years ago at
> a Lisp Users Group conference. I think the presentation was from a
> company that had an embedded Lisp product, and needed real-time
> performance guarantees. A major theme was avoiding GC.
The Chineuals seem to mention lisp machines had:
[ http://bitsavers.org/pdf/mit/cadr/chineualJan84/ ]
- stack allocation, where you could actually get dangling pointers if
you held on to something deallocated.
- 'areas' where you could instruct the GC to never or rarely
automatically visit, among other things.
- these "locatives" which I don't really grok but are some low-level
way to point at something in memory.
Are any of these transportable to normal hardware? Areas and stack
allocation would seem to be...
Also, those protocol guys had some ideas on "open implementation"
compilers where the user may decide some tradeoffs.
http://www2.parc.com/csl/groups/sda/publications/papers/Lamping-IMSA92/
http://www2.parc.com/csl/groups/sda/publications/papers/Kiczales-MOPs-for-Lisp/
Again, I do not know what is feasible given common hardware and time
constraints. I've always worked on platforms which had reasonable
low-level performance for my goals.
From: Joe Marshall
Subject: Re: Fundamentals of Lisp efficiency?
Date:
Message-ID: <1xkmjjt4.fsf@ccs.neu.edu>
···········@yahoo.com (Tayssir John Gabbour) writes:
> The Chineuals seem to mention lisp machines had:
> [ http://bitsavers.org/pdf/mit/cadr/chineualJan84/ ]
>
> - stack allocation, where you could actually get dangling pointers if
> you held on to something deallocated.
Yep.
> - 'areas' where you could instruct the GC to never or rarely
> automatically visit, among other things.
Usually you would tell the GC to never reclaim the area. If your
program was such that there was a `top-level' loop that dispatched to
subroutines, you'd create a special area for subroutine allocation.
When the subroutine returned to top level, you'd simply reset the
consing frontier in the area. (If there are still pointers into the
area, you crash.)
> - these "locatives" which I don't really grok but are some low-level
> way to point at something in memory.
They are simply `pointers' to the interior of an object. When the GC
moves an object it is careful to update the locative as well.
> Are any of these transportable to normal hardware? Areas and stack
> allocation would seem to be...
You can simulate locatives with the appropriate help from SETF,
although the simulated locative is more heavyweight than the lisp
machine implementation.
Locatives give you power that you shouldn't use. If you have the head
of the object, you can access the interior at any time without a
locative. If you don't have a pointer to the head of the object, then
mucking with the interior of it is probably a bad idea.
> Again, I do not know what is feasible given common hardware and time
> constraints. I've always worked on platforms which had reasonable
> low-level performance for my goals.
A PC simulation of the LispM should handily outperform what was
state-of-the-art in the 80s.
Joe Marshall <···@ccs.neu.edu> writes:
> ···········@yahoo.com (Tayssir John Gabbour) writes:
> > The Chineuals seem to mention lisp machines had:
> > - these "locatives" which I don't really grok but are some low-level
> > way to point at something in memory.
>
> They are simply `pointers' to the interior of an object. When the GC
> moves an object it is careful to update the locative as well.
>
> > Are any of these transportable to normal hardware?
>
> You can simulate locatives with the appropriate help from SETF,
> although the simulated locative is more heavyweight than the lisp
> machine implementation.
For example:
http://www.hexapodia.net/pipermail/small-cl-src/2004-June/000016.html
--
Lars Brinkhoff, Services for Unix, Linux, GCC, HTTP
Brinkhoff Consulting http://www.brinkhoff.se/
Barry Margolin <······@alum.mit.edu> wrote in message news:<····························@comcast.dca.giganews.com>...
> I recall a paper on this topic that was given about a dozen years ago at
> a Lisp Users Group conference. I think the presentation was from a
> company that had an embedded Lisp product, and needed real-time
> performance guarantees. A major theme was avoiding GC.
Are any of the lisp machine stuff useful on normal machines? Stack
allocation and areas would seem to be.
- stack allocation, where you could actually get dangling pointers if
you held on to something deallocated.
- 'areas' where you could instruct the GC to never or rarely
automatically visit, among other things.
- these "locatives" which I don't really grok but are some low-level
way to point at something in memory.
[ http://bitsavers.org/pdf/mit/cadr/chineualJan84/ ]
Also, those metaobject guys had some ideas on "open implementation"
compilers where the user may decide some tradeoffs.
http://www2.parc.com/csl/groups/sda/publications/papers/Lamping-IMSA92/
http://www2.parc.com/csl/groups/sda/publications/papers/Kiczales-MOPs-for-Lisp/
Again, I do not know what is feasible given common hardware and time
constraints. I've always worked on platforms which had reasonable
low-level performance for my goals.
Barry Margolin <······@alum.mit.edu> writes:
> I recall a paper on this topic that was given about a dozen years ago at
> a Lisp Users Group conference. I think the presentation was from a
> company that had an embedded Lisp product, and needed real-time
> performance guarantees. A major theme was avoiding GC.
Are you referring to the following paper?
Real-time programming in Common Lisp
James R. Allard (Gensym Corp, Burlington MA)
Lowell B. Hawkinson (Gensym Corp, Burlington MA)
http://portal.acm.org/citation.cfm?id=114679&dl=ACM&coll=portal#review
"G2 is a real-time expert system for applications in manufacturing,
process control, financial trading, and telecommunications. It is
written in Common LISP and runs in five different implementations on
14 different hardware platforms. LISP is not an obvious choice for a
real-time application; it is generally accepted as a powerful language
for artificial intelligence or symbolic processing. Common LISP
programs are criticized as slow, unpredictable in response due to
garbage collection, and overly large. To overcome the unpredictability
of the garbage collector, memory is managed explicitly. Pointers to
allocated objects are retained, data structures are recycled, and
dynamic objects are used only when no other possibility is found. Some
facilities have been re-implemented by writing the underlying
primitives in C. Macros have been used to select specific parts of
code according to their arguments, allowing compile-time determination
of the appropriate dispatching code. Type declarations have been used
to avoid dynamic typing. Program size reduction has been achieved
through tree shaking."
> Sorry, I don't remember the name of the company or presenter, but
> perhaps this will jog someone's memory.
Interestingly enough, I came across this paper this morning on my own
when I discovered that a company that uses Lisp is only 2 buildings
away from my current employer. After digging up some info on the
company and its owners, I discovered the above paper this morning.
Pete
Barry Margolin <······@alum.mit.edu> writes:
> I recall a paper on this topic that was given about a dozen years ago at
> a Lisp Users Group conference. I think the presentation was from a
> company that had an embedded Lisp product, and needed real-time
> performance guarantees. A major theme was avoiding GC.
>
> Sorry, I don't remember the name of the company or presenter, but
> perhaps this will jog someone's memory.
You may be thinking of the presentation by John Hodgkinson, who was
then employed by the Gensym Corporation. I have a hardcopy of the
accompanying paper which is entitled "Sleeping with the enemy: Lisp
and C in a large, profitable real-time application". It is not
exactly an exciting read unless you are interested in the pain one
must endure delivering Lisp systems which are shaken down to C before
compilation.
In article <···············@panix3.panix.com>,
Carl Shapiro <·············@panix.com> wrote:
> Barry Margolin <······@alum.mit.edu> writes:
>
> > I recall a paper on this topic that was given about a dozen years ago at
> > a Lisp Users Group conference. I think the presentation was from a
> > company that had an embedded Lisp product, and needed real-time
> > performance guarantees. A major theme was avoiding GC.
> >
> > Sorry, I don't remember the name of the company or presenter, but
> > perhaps this will jog someone's memory.
>
> You may be thinking of the presentation by John Hodgkinson, who was
> then employed by the Gensym Corporation. I have a hardcopy of the
> accompanying paper which is entitled "Sleeping with the enemy: Lisp
> and C in a large, profitable real-time application". It is not
> exactly an exciting read unless you are interested in the pain one
> must endure delivering Lisp systems which are shaken down to C before
> compilation.
That sounds like it (and not the Symbolics/AT&T project that Chris
mentioned -- I don't think they went public with the details at the
time).
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
In article <····························@comcast.dca.giganews.com>,
Barry Margolin <······@alum.mit.edu> wrote:
> In article <···············@panix3.panix.com>,
> Carl Shapiro <·············@panix.com> wrote:
>
> > Barry Margolin <······@alum.mit.edu> writes:
> >
> > > I recall a paper on this topic that was given about a dozen years ago at
> > > a Lisp Users Group conference. I think the presentation was from a
> > > company that had an embedded Lisp product, and needed real-time
> > > performance guarantees. A major theme was avoiding GC.
> > >
> > > Sorry, I don't remember the name of the company or presenter, but
> > > perhaps this will jog someone's memory.
> >
> > You may be thinking of the presentation by John Hodgkinson, who was
> > then employed by the Gensym Corporation. I have a hardcopy of the
> > accompanying paper which is entitled "Sleeping with the enemy: Lisp
> > and C in a large, profitable real-time application". It is not
> > exactly an exciting read unless you are interested in the pain one
> > must endure delivering Lisp systems which are shaken down to C before
> > compilation.
>
> That sounds like it (and not the Symbolics/AT&T project that Chris
> mentioned -- I don't think they went public with the details at the
> time).
There was a panel "Dynamic Objects in Telecommunications"
at the 1996 Lisp Users and Vendors conference
with Don Brown and Steven Engelstad from AT&T.
There they presented their experience implementing
a 'large-scale broadband switching system'.
Rainer Joswig wrote:
> There was a panel "Dynamic Objects in Telecommunications"
> at the 1996 Lisp Users and Vendors conference
> with Don Brown and Steven Engelstad from AT&T.
> There they presented their experience implementing
> a 'large-scale broadband switching system'.
Was there any paper or presentation that went along with that? If so, might
it be online with a reference?
--
Dave Roberts, ·············@re-move.droberts.com
Slowly but surely, the programming world is finding Lisp...
http://www.findinglisp.com/blog
Joe Marshall <·············@comcast.net> writes:
> Lowell Hawkinson has a dislike of garbage collection that borders on
> phobia. At LMI, when working on the PICON project, one of his goals
> was to manually manage *every single byte* of storage so that there
> was no automatic management whatsoever. It is a royal pain in the ass
> to do this.
To this day, the intellectual successor to PICON, G2, manages all
data structures this way. A user-level resource facility is used to
manage arrays through a segregated-fit allocation mechanism. All
arrays and array-like structures (structs) are assembled from the same
managed arrays. Fixed length objects, such as cons cells and flonums,
are managed in pools of their own. Delivered images have disabled
Lisp garbage collectors.
A lot of clever macrology spares most, but not all, of the pain from
manual memory management. At least for me, tracking other people's
memory leaks was more of a royal pain in the ass.
I think Lowell is over the GC phobia. All of Gensym's new wares are
written using any one of a number of garbage collected languages!
In article <···············@panix3.panix.com>,
Carl Shapiro <·············@panix.com> wrote:
> I think Lowell is over the GC phobia. All of Gensym's new wares are
> written using any one of a number of garbage collected languages!
One thing that has changed in the decade since then is that memory costs
have dropped dramatically. So you can usually afford to put enough
memory in a machine that it will rarely need to GC. And processor
speeds have increased so much that the performance impact of those rare
GC's could be close to negligible.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
From: Christopher C. Stacy
Subject: Re: Fundamentals of Lisp efficiency?
Date:
Message-ID: <u4qpihpkx.fsf@news.dtpq.com>
>>>>> On Thu, 10 Jun 2004 11:19:49 -0400, Barry Margolin ("Barry") writes:
Barry> In article <···················@attbi_s52>,
Barry> Dave Roberts <·············@re-move.droberts.com> wrote:
>> So, if you could strip down a Lisp and make it as fast as possible, what
>> would it start to look like? That is, where are the efficiency bottlenecks
>> on a Lisp?
Barry> I recall a paper on this topic that was given about a dozen
Barry> years ago at a Lisp Users Group conference. I think the
Barry> presentation was from a company that had an embedded Lisp
Barry> product, and needed real-time performance guarantees.
Barry> A major theme was avoiding GC.
You might be referring to the AT&T/Symbolics project, which I have
mentioned elsewhere in this thread; it had guaranteed response times,
even in the face of the garbage collector. It also used a slightly
different scheduler and virtual memory system than Genera. I don't
remember if it had a disk. (To tie this into the other thread about
"is it possible to make am OS in Lisp", please note that another
central feature of the system was fast network IO.)
From: Joe Marshall
Subject: Re: Fundamentals of Lisp efficiency?
Date:
Message-ID: <llivto4k.fsf@ccs.neu.edu>
Dave Roberts <·············@re-move.droberts.com> writes:
> So, if you could strip down a Lisp and make it as fast as possible, what
> would it start to look like?
It depends greatly on what you consider fair game for optimization.
One direction you could go is to remove all `generic' operations:
You'd have to use STRING-LENGTH for strings, LIST-LENGTH for lists,
VECTOR-LENGTH for vector, etc. Once you do this, you can remove all
the implicit type checking. Of course, if you attempt to apply CAR to
a string, your lisp will likely drop dead.
Keep continuing in this direction and you'll end up with a fully
parenthesized C. (Not that this wouldn't be a vast improvement over
regular C, but it won't be lisp!)
Another possibility would be to avoid GC by explicit memory
management. If your code has a `main loop' from which all subroutines
are run and no permanent storage is *ever* allocated from a
subroutine, you can skip the GC and simply reset the free pointer
at the top of the main loop.
> That is, where are the efficiency bottlenecks on a Lisp?
Again, it depends on what you are doing. If you were, for example,
moving arrays around, you better spend some time making the inner loop
go as fast as possible. The inefficiencies that I typically see are
these sorts of things:
- Being too generic:
(dotimes (i (length sequence))
(frob (elt sequence i)))
This will work on vectors, strings, and lists, but it won't be
fast for any of them. Especially for lists.
- Rolling your own sequence functions:
I don't know how often I see a something like this:
(dotimes (i (length foo))
(setf (aref foo i) 0)) ;; initialize the array
There is a perfectly good function called FILL that will do the
same thing. But not only that, the vendor has implemented it and
there is a good chance that it handles some common cases
extremely efficiently. The vendors' compiler may recognize that
(fill foo 0) can be implemented with a tight assembly code loop,
but it is less likely to be able to deduce that
(do ((i 0 (+ i 1)))
((> i (length foo)))
(setf (elt foo i) 0))
might be reducable to that same loop.
- Misusing lists:
DO NOT `CONS ON THE RIGHT HAND END OF A LIST'
(append foo (list element))
This one common error is probably responsible for more wasted
time than anything else.
Avoid taking the length of a list. In general, if you are using
a list you should write the code by induction over the tail of
the list rather than by induction over the length. If you need
to know if a list has at least a certain number of elements (a
common enough operation), don't use length. Especially don't use
(= (length l) 0) on a list.
I see this sort of thing frequently:
(do ((i input (cdr i))
(o '() (append o (list (foo (car i))))))
((= (length i) 0) o))
This is equivalent to (map 'list #'foo input), but *much*, *much*
slower.
- Using generic arithmetic on floating point numbers.
If you are hacking serious floating point in Common Lisp, get a
wizard to help. Naive floating point in Common Lisp is
servicable, but slow.
> If the limitations were, you have to retain GC, lambdas, macros,
> and functions, but you can change just about anything else about Lisp to
> make it an efficient, bit-banging language that is as close to C in
> performance as you can get (so, essentially a version of Lisp that is
> optimized to fiddle with raw storage the way that C can), what would you
> end up with?
The guts of a commercial lisp. Poke around in the SYS package of
Allegro or Lispworks. They need to do bit-banging for various reasons
and there are high-performance bit-banging functions that are not
exported to the user. They are generally unsafe operations.
Dave Roberts wrote:
> So, if you could strip down a Lisp and make it as fast as possible, what
> would it start to look like? That is, where are the efficiency bottlenecks
> on a Lisp? If the limitations were, you have to retain GC, lambdas, macros,
> and functions, but you can change just about anything else about Lisp to
> make it an efficient, bit-banging language that is as close to C in
> performance as you can get (so, essentially a version of Lisp that is
> optimized to fiddle with raw storage the way that C can), what would you
> end up with? Would it essentially be something like CL with a huge number
> of declarations (memories of that optimization challenge that was floating
> around here a few months ago)? Which features would have you have drop and
> which could you retain?
>
In your case you end up with a custom datacomm-switch-programming-language.
It would have a Lisp syntax, run on a development system emulator and compile
to efficient code in the actual switch. Of course that would be for the
lower level bit stream handling. For things like network element management and
maintenence interfaces one could keep CL just the way it is.
Though I am a little curious, performance switches tend to be multi-processor
beasts, with custom cards for various switch functions. Which functionality
are you actually talking about?
Wade
Wade Humeniuk wrote:
> In your case you end up with a custom
> datacomm-switch-programming-language. It would have a Lisp syntax, run on
> a development system emulator and compile
> to efficient code in the actual switch. Of course that would be for the
> lower level bit stream handling. For things like network element
> management and maintenence interfaces one could keep CL just the way it
> is.
Yea, that's exactly it. I was just wondering what that Lisp-like
switch-programming language would look like. As you point out, for
something like the management system, CL is fine.
> Though I am a little curious, performance switches tend to be
> multi-processor
> beasts, with custom cards for various switch functions. Which
> functionality are you actually talking about?
Yes, that is the case. I'm talking about the parts that run the various
protocols and some of the low-level packet handling. There will always be
parts that have to run in C, but if you can get a very efficient FFI, they
can be minimized.
The things that intrigue me about Lisp are all the various
programmer-productivity features it has in terms of GC and macros. While it
can do bit-banging, it struggles there, however. I look at some of the MD5
or Blowfish code that is reference on CLiki, for instance, and you can see
the programmers doing backflips to retain efficiency. Some of this is
related to having the right sorts of operators that map very naturally into
machine instructions, one for one. Some of it also seems related to CL's
generality with respect to generic arithmetic, etc.
The other project I remember hearing a little about is something AT&T was
doing for a voice switch, I believe, but it looks like that project never
made it and I can't find much info on it.
--
Dave Roberts, ·············@re-move.droberts.com
Slowly but surely, the programming world is finding Lisp...
http://www.findinglisp.com/blog
Dave Roberts wrote:
> Wade Humeniuk wrote:
>
>
>>In your case you end up with a custom
>>datacomm-switch-programming-language. It would have a Lisp syntax, run on
>>a development system emulator and compile
>>to efficient code in the actual switch. Of course that would be for the
>>lower level bit stream handling. For things like network element
>>management and maintenence interfaces one could keep CL just the way it
>>is.
>
>
> Yea, that's exactly it. I was just wondering what that Lisp-like
> switch-programming language would look like.
Switch programing has been going on for relatively long time. I assume
the switch programming language would look like a rigorous form
of the way switch experts talk and conceptualize the problem. But
knowing the switch guys most of them are old school and think in
terms of hardware and are not very software oriented. From my
limited experience I would say the low level bit streaming
protocols would look very much like the logic programming
of gates (and ors nots, etc, etc....). Not just out of
technical need but also the need to communicate the functionality
between the design, software and the hardware people.
Wade
Wade Humeniuk wrote:
>> Yea, that's exactly it. I was just wondering what that Lisp-like
>> switch-programming language would look like.
>
>
> Switch programing has been going on for relatively long time. I assume
> the switch programming language would look like a rigorous form
> of the way switch experts talk and conceptualize the problem. But
> knowing the switch guys most of them are old school and think in
> terms of hardware and are not very software oriented. From my
> limited experience I would say the low level bit streaming
> protocols would look very much like the logic programming
> of gates (and ors nots, etc, etc....). Not just out of
> technical need but also the need to communicate the functionality
> between the design, software and the hardware people.
Just to clear up where I am coming from. One company I worked for
was developing OSS Network Mangement for a Nothern Telecomm FD565.
It was a few years ago, but we had a seminar where the FD565 (a fibre
optic, 565 Mbit/sec telco switch) bit level protocol was explained.
The synchronous switch protocol had extra bits to carry switching
information so routing of voice, inter-switch communications,
blah,blah could be carried. It is my recollection the protocol
was such that its specification was implemented in a hardware
model (literally) so that custom hardware could be built to do the actual
protocol handling.
Wade
Wade Humeniuk wrote:
>> Switch programing has been going on for relatively long time. I assume
>> the switch programming language would look like a rigorous form
>> of the way switch experts talk and conceptualize the problem. But
>> knowing the switch guys most of them are old school and think in
>> terms of hardware and are not very software oriented. From my
>> limited experience I would say the low level bit streaming
>> protocols would look very much like the logic programming
>> of gates (and ors nots, etc, etc....). Not just out of
>> technical need but also the need to communicate the functionality
>> between the design, software and the hardware people.
>
> Just to clear up where I am coming from. One company I worked for
> was developing OSS Network Mangement for a Nothern Telecomm FD565.
> It was a few years ago, but we had a seminar where the FD565 (a fibre
> optic, 565 Mbit/sec telco switch) bit level protocol was explained.
> The synchronous switch protocol had extra bits to carry switching
> information so routing of voice, inter-switch communications,
> blah,blah could be carried. It is my recollection the protocol
> was such that its specification was implemented in a hardware
> model (literally) so that custom hardware could be built to do the actual
> protocol handling.
Interesting. My particular domain is on the datacom side, not telecom. In my
case, it's things like gigabit Ethernet switches, etc.
--
Dave Roberts, ·············@re-move.droberts.com
Slowly but surely, the programming world is finding Lisp...
http://www.findinglisp.com/blog
Dave Roberts wrote:
>
>
> Interesting. My particular domain is on the datacom side, not telecom. In my
> case, it's things like gigabit Ethernet switches, etc.
>
Yes. The FD565 was a SONET (I am pretty sure) switch. See:
http://www.nortelnetworks.com/corporate/technology/olh/protocols.html
Purusing the site shows how out of date I am. They have
terabit switches now. Gack! I also see that the division between telco
and datacom has blurred even more.
Wade
Wade Humeniuk <········@telus.delete.net> writes:
> Just to clear up where I am coming from. One company I worked for
> was developing OSS Network Mangement for a Nothern Telecomm FD565.
> It was a few years ago, but we had a seminar where the FD565 (a fibre
> optic, 565 Mbit/sec telco switch) bit level protocol was explained.
I presume that you have investigated Erlang.
Hi Dave,
Wonderful topic :-)
Dave Roberts <·············@re-move.droberts.com> writes:
> Yea, that's exactly it. I was just wondering what that Lisp-like
> switch-programming language would look like.
I wonder similar things, coming from the other direction:
How nicely could one write a TCP/IP protocol suite in Lisp?
How close can the performance get to a Unix kernel without
sacrificing clarity?
Perhaps one could then ask, what do we need to sacrifice to get within
a factor of foo of Linux performance? That's the order I tend to
tackle things in.
Mostly this is curiosity for me. Still, it would be neat to have a
"gateway" PC that does NAT, firewall, etc in straight Lisp instead of
using iptables and suchlike. I wouldn't need more than 100Mbps of
throughput (probably less) which means it'd be fine for me to run
about an order of magnitude slower than the Linux kernel.
I think this would also be useful as a research test-bed. A ways back
a friend and I did some work on TCP extensions by directly hacking
Linux's implementation. Man, that was stupid! (Edit, compile, reboot.)
It would certainly have gone faster to start by writing a high-level
TCP to do all the experimental work on.
> Yes, that is the case. I'm talking about the parts that run the various
> protocols and some of the low-level packet handling. There will always be
> parts that have to run in C, but if you can get a very efficient FFI, they
> can be minimized.
I have some code that might be interesting to you, though you might
choke on the inefficient programming style (at least that was my
intention :-).
One is a second attempt at decoding TCP/IP packets in Lisp:
http://www.bluetail.com/~luke/misc/lisp/packet.lisp
or,
http://www.bluetail.com/~luke/misc/lisp/packet.pdf
The other is some libraries for ethernet-level I/O on Linux, one for
'tuntap' (virtual network interfaces) and another for PF_PACKET
sockets (raw I/O on existing interfaces). These can be fished out of
tuntap.lisp and packet-socket.lisp from the sourceforge project
'slitch'. There's also a partial first-attempt at a TCP/IP
implementation in there but it's a pretty ugly.
That code was all written for CMUCL.
Anyway, if you do any experiments with low-level networking in Lisp
then I'd love to hear about them.
> The other project I remember hearing a little about is something AT&T was
> doing for a voice switch, I believe, but it looks like that project never
> made it and I can't find much info on it.
Recently I wrote the traffic handling part of a "funky" switch product
in Erlang. That was great: it worked right away so I had time to
figure out all the tricky higher-level things that had to be
done. Afterwards it took about one day to port the traffic handling
code into the kernel for a ~5x performance gain.
NB (regarding other postings): Erlang is not usually used for packet
handling in switches, just for the higher-level
control/distribution/OA&M etc parts. It does have a very neat "bit
syntax" for dealing with structured binary data but I'm not sure what
its exact speed is, e.g. how long it takes to decode an IPv4 PDU.
Dumb-and-fast switches aside, Erlang is commonly used for traffic
handling with higher-level protocols like HTTP.
Cheers,
Luke
Luke Gorrie <····@bluetail.com> writes:
> Hi Dave,
>
> Wonderful topic :-)
>
> Dave Roberts <·············@re-move.droberts.com> writes:
> > Yea, that's exactly it. I was just wondering what that Lisp-like
> > switch-programming language would look like.
>
> I wonder similar things, coming from the other direction:
>
> How nicely could one write a TCP/IP protocol suite in Lisp?
>
> How close can the performance get to a Unix kernel without
> sacrificing clarity?
>
> Perhaps one could then ask, what do we need to sacrifice to get within
> a factor of foo of Linux performance? That's the order I tend to
> tackle things in.
For the really trivial kind of stuff that benchmarks do, I expect Lisp
to be a small FOO slower than C or C++. For real work, though,
performance is exactly how I found Lisp in the first place. Sacrifice
shmacrifice, for something interesting (and a TCP/IP stack might just
be on the inner edge of "interesting") I expect Lisp to win in
performance.
Writing efficient, readable, maintainable C++ code is like having a
conversation with a schizophrenic; "does the C++ compiler understand
what I mean here, even with this slight change?!?!" Common Lisp is a
math grad student; "okay, given the following (compiler macro), I'm
saying the following, including these changes."
I consider myself a good C++ programmer; as a Lisp newbie, I wrote an
image-processing server in CL as a prototype, and optimized it with an
eye on the early AOP papers. I never got the C++ version running as
efficiently, and I spent 5 weeks (g++) to CL's 1 (CMUCL 18b).
Come to think of it, code with an FP interface is probably the easiest
to make efficient in Lisp; nowadays, I'd probably have used CLOS,
which makes it a lot harder to communicate with the compiler.
Thomas F. Burdick wrote:
> I consider myself a good C++ programmer; as a Lisp newbie, I wrote an
> image-processing server in CL as a prototype, and optimized it with an
> eye on the early AOP papers. I never got the C++ version running as
> efficiently, and I spent 5 weeks (g++) to CL's 1 (CMUCL 18b).
I'm going to second this - I'm a pretty darn good C++ programmer (wrote
my thesis project using C++, among other things) and, although I've been
able to duplicate my C (not C++) coding in Lisp for years, I just
recently actually got into the language (read _On Lisp_, learned the
basics of CLOS, etc.) and was able to duplicate a project I had started
5 years or more ago with C++ using Common Lisp and, in one week of
coding for an hour or two a day at most, got twice as far.
There are some areas where I'm still deficient in Lisp compared to my
C++ skills, but I'm rapidly seeing that "doing that in Lisp would have
been a good idea" and "if it's anything that I can't just whip up in 10
minutes with PHP, C++, or Ruby, I'd be wise to use Lisp" are common
parts of my programming vernacular.
If you're a skilled programmer in some language, I recommend my route:
learn Lisp syntax and then read _On Lisp_. It "puts you in the mood"
quite well.
Thomas F. Burdick wrote:
> For the really trivial kind of stuff that benchmarks do, I expect Lisp
> to be a small FOO slower than C or C++. For real work, though,
> performance is exactly how I found Lisp in the first place. Sacrifice
> shmacrifice, for something interesting (and a TCP/IP stack might just
> be on the inner edge of "interesting") I expect Lisp to win in
> performance.
Hmmm... be careful of this. I have been burned before thinking like this.
The fallacy is that while Lisp might be good when it's in its own domain, C
is *very* good at interfacing with the outside world. The ability to define
a structure and overlay that onto a buffer containing arbitrary bytes is a
huge win. The ability to bounce pointers around, casting them from one type
to another, and just having the compiler generate indexed load/stores is
very powerful. Most other languages have problems with doing the same thing
on an outside buffer without a very efficient FFI that allows basically the
same operations.
Note that I'm NOT saying that Lisp isn't fast or that it can't beat C on
some problems. I'm sure it can. Be careful of assuming that it will beat C
when dealing with interfaces to the outside world using protocols that you
cannot control, however. That is C's home turf and it does very, very well
there.
--
Dave Roberts, ·············@re-move.droberts.com
Slowly but surely, the programming world is finding Lisp...
http://www.findinglisp.com/blog
From: Christopher C. Stacy
Subject: Re: Fundamentals of Lisp efficiency?
Date:
Message-ID: <usmcwj8qj.fsf@news.dtpq.com>
>>>>> On Wed, 16 Jun 2004 04:13:56 GMT, Dave Roberts ("Dave") writes:
Dave> Be careful of assuming that it will beat C when dealing with
Dave> interfaces to the outside world using protocols that you cannot
Dave> control, however. That is C's home turf and it does very, very
Dave> well there.
Just to clarify this: you mean "ANSI Common Lisp" (plain unadorned),
rather than some abstract "Lisp" in general, or rather even than
some particular ANSI CL implementation which may already exist.
Lisp can have the necessary features for hacking low-level
machine details, such as aligned network buffers and interrupts.
An extended Common Lisp dialect with those kinds of features
has already been used to implement TCP/IP stacks all the way
down to the Ethernet controller chip, and other similar dialects
of Lisp have also done the same thing. (The fact that this was
on proprietary CPU hardware is irrelevent, as there was nothing
special about that part of it.) The network buffers were simply
unboxed fixnum arrays of bytes, placed appropriately. Such features
are necessarily hardware and operating system dependant, but a
portable library of macros and functions for low-level machine
access could be developed for use on most kinds of computers.
If you are talking about interfacing Lisp with the kernel of a
particular operating system that has already been written with
a bunch of assumptions about things like how interrupts work,
that's another kettle of fish. It's the interference with/from
the Unix kernel, and performance problems interfacing to a
non-kernel network driver, that will be tricky to deal with.
Low-level machine programming is not exclusively C's turf, but C
(specifically, a dialect with the necessary non-ANSI extensions)
is obviously what's best for implementing pieces of Unix.
More generally, the best languages for machine-level integration
with a given operating system are those languages that implement
the calling, memory, and interrupt protocols in the expected way.
Most ANSI Common Lisp implementations weren't designed for that.
(It's not clear to me that most languages were, except for the
particular language dialect that was used to implement the OS.)
Christopher C. Stacy wrote:
>>>>>> On Wed, 16 Jun 2004 04:13:56 GMT, Dave Roberts ("Dave") writes:
>
> Dave> Be careful of assuming that it will beat C when dealing with
> Dave> interfaces to the outside world using protocols that you cannot
> Dave> control, however. That is C's home turf and it does very, very
> Dave> well there.
>
> Just to clarify this: you mean "ANSI Common Lisp" (plain unadorned),
> rather than some abstract "Lisp" in general, or rather even than
> some particular ANSI CL implementation which may already exist.
Yes, exactly. The question about whether one could extend/alter CL to
produce a Lisp more suitable for this sort of problem was exactly the
original question I asked to start the thread.
> Lisp can have the necessary features for hacking low-level
> machine details, such as aligned network buffers and interrupts.
> An extended Common Lisp dialect with those kinds of features
> has already been used to implement TCP/IP stacks all the way
> down to the Ethernet controller chip, and other similar dialects
> of Lisp have also done the same thing. (The fact that this was
> on proprietary CPU hardware is irrelevent, as there was nothing
> special about that part of it.) The network buffers were simply
> unboxed fixnum arrays of bytes, placed appropriately. Such features
> are necessarily hardware and operating system dependant, but a
> portable library of macros and functions for low-level machine
> access could be developed for use on most kinds of computers.
Yes, agreed. In fact, I wanted some more details from Barry Margolin on his
experiences with the TCP stack on the Symbolics machine. It sounded pretty
interesting. I was specifically curious how how much low-level support that
had to build into the machine for it, both in the hardware as well as the
Lisp itself.
> If you are talking about interfacing Lisp with the kernel of a
> particular operating system that has already been written with
> a bunch of assumptions about things like how interrupts work,
> that's another kettle of fish. It's the interference with/from
> the Unix kernel, and performance problems interfacing to a
> non-kernel network driver, that will be tricky to deal with.
>
> Low-level machine programming is not exclusively C's turf, but C
> (specifically, a dialect with the necessary non-ANSI extensions)
> is obviously what's best for implementing pieces of Unix.
I would agree with the fact that you can do low-level programming in many
languages. The fact is, however, that most low-level things today get done
in C and it's the defacto implementation language not just for Unix, but
also Windows and other OSs (I would have said Mac OS X, but I guess we
could consider that Unix now). Even when you get to the embedded world now,
most off-the-shelf RTOSs are C-based.
So, while the argument holds in theory, I think you have to assume it's a
C-world out there in practice.
> More generally, the best languages for machine-level integration
> with a given operating system are those languages that implement
> the calling, memory, and interrupt protocols in the expected way.
> Most ANSI Common Lisp implementations weren't designed for that.
Agreed. That's exactly my point.
> (It's not clear to me that most languages were, except for the
> particular language dialect that was used to implement the OS.)
Which in most cases is C these days.
--
Dave Roberts, ·············@re-move.droberts.com
Slowly but surely, the programming world is finding Lisp...
http://www.findinglisp.com/blog
······@news.dtpq.com (Christopher C. Stacy) writes:
> If you are talking about interfacing Lisp with the kernel of a
> particular operating system that has already been written with
> a bunch of assumptions about things like how interrupts work,
> that's another kettle of fish. It's the interference with/from
> the Unix kernel, and performance problems interfacing to a
> non-kernel network driver, that will be tricky to deal with.
>
> Low-level machine programming is not exclusively C's turf, but C
> (specifically, a dialect with the necessary non-ANSI extensions)
> is obviously what's best for implementing pieces of Unix.
>
> More generally, the best languages for machine-level integration
> with a given operating system are those languages that implement
> the calling, memory, and interrupt protocols in the expected way.
> Most ANSI Common Lisp implementations weren't designed for that.
> (It's not clear to me that most languages were, except for the
> particular language dialect that was used to implement the OS.)
To clarify what I believe you're trying to say, on an operating system
written in Common-Lisp, the most efficient language to write drivers
and interfacing code would be Common-Lisp, and there C would be much
less efficient than Common-Lisp.
--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
From: Christopher C. Stacy
Subject: Re: Fundamentals of Lisp efficiency?
Date:
Message-ID: <uoenjo23a.fsf@news.dtpq.com>
>>>>> On 16 Jun 2004 16:45:41 +0200, Pascal Bourguignon ("Pascal") writes:
Pascal> ······@news.dtpq.com (Christopher C. Stacy) writes:
>> If you are talking about interfacing Lisp with the kernel of a
>> particular operating system that has already been written with
>> a bunch of assumptions about things like how interrupts work,
>> that's another kettle of fish. It's the interference with/from
>> the Unix kernel, and performance problems interfacing to a
>> non-kernel network driver, that will be tricky to deal with.
>>
>> Low-level machine programming is not exclusively C's turf, but C
>> (specifically, a dialect with the necessary non-ANSI extensions)
>> is obviously what's best for implementing pieces of Unix.
>>
>> More generally, the best languages for machine-level integration
>> with a given operating system are those languages that implement
>> the calling, memory, and interrupt protocols in the expected way.
>> Most ANSI Common Lisp implementations weren't designed for that.
>> (It's not clear to me that most languages were, except for the
>> particular language dialect that was used to implement the OS.)
Pascal> To clarify what I believe you're trying to say, on an
Pascal> operating system written in Common-Lisp, the most efficient
Pascal> language to write drivers and interfacing code would be
Pascal> Common-Lisp, and there C would be much less efficient than
Pascal> Common-Lisp.
More to the point, on an operating system written in C,
not any random ANSI C implementation can be be used to
modify certain portions of the low-level kernel guts.
Not any random library can be linked in there, either.
Dave Roberts <·············@re-move.droberts.com> writes:
> Thomas F. Burdick wrote:
>
> > For the really trivial kind of stuff that benchmarks do, I expect Lisp
> > to be a small FOO slower than C or C++. For real work, though,
> > performance is exactly how I found Lisp in the first place. Sacrifice
> > shmacrifice, for something interesting (and a TCP/IP stack might just
> > be on the inner edge of "interesting") I expect Lisp to win in
> > performance.
>
> Hmmm... be careful of this. I have been burned before thinking like this.
> The fallacy is that while Lisp might be good when it's in its own domain, C
> is *very* good at interfacing with the outside world. The ability to define
> a structure and overlay that onto a buffer containing arbitrary bytes is a
> huge win. The ability to bounce pointers around, casting them from one type
> to another, and just having the compiler generate indexed load/stores is
> very powerful. Most other languages have problems with doing the same thing
> on an outside buffer without a very efficient FFI that allows basically the
> same operations.
You may have missed that the above was /not/ idle speculation on my
part, I was relaying a particular experience. I've nevver written a
tcp/ip stack in Lisp or any language, and don't plan on it, but I
don't see anything very C-specific about it. In CMU Common Lipsps,
it's quite easy to take arbitrary pointers, and interpret the bits
there however you see fit. The reason that things like md5 can be
hard to do efficiently is because you want to pass around unboxed
32-bit integers all the time; for most code where you need C-style
efficiency, you pass around pointers, which is quite Lisp-friendly (at
least potentially, dialects vary).
> Note that I'm NOT saying that Lisp isn't fast or that it can't beat C on
> some problems. I'm sure it can. Be careful of assuming that it will beat C
> when dealing with interfaces to the outside world using protocols that you
> cannot control, however. That is C's home turf and it does very, very well
> there.
As a former low-level C guy, I think C does it okay. It can be nice
to take pointers and interpret the bits there however you want; it's
not so nice to be /forced/ to interpret the bits there; it makes it
impossible to refactor some code, which also makes some low-level
bit-bashing optimizations impractical, because they'd result in
combinatorial explosions. C facilitates the idea of taking a small
efficiency hit (say, two function indirections) before launching into
your inner loop. It would be nice if it let you take a similar hit
with pointers, eg, "what is it that this void* points to?" Glad I've
got Lisp, now.
Thomas F. Burdick wrote:
> You may have missed that the above was /not/ idle speculation on my
> part, I was relaying a particular experience.
Yes, I understood that. Sorry, wasn't trying to say that what you had
experienced was somehow a figment of your imagination. I believe you. I'm
just warning that sometimes it's dangerous to extrapolate to other areas
where the details may end up being different. Change the assumptions and
all that...
> I've nevver written a
> tcp/ip stack in Lisp or any language, and don't plan on it, but I
> don't see anything very C-specific about it. In CMU Common Lipsps,
> it's quite easy to take arbitrary pointers, and interpret the bits
> there however you see fit. The reason that things like md5 can be
> hard to do efficiently is because you want to pass around unboxed
> 32-bit integers all the time; for most code where you need C-style
> efficiency, you pass around pointers, which is quite Lisp-friendly (at
> least potentially, dialects vary).
So, basically, that's what I'm saying. There are problems where you want
32-bit integers being passed all around. Think about networking code and IP
addresses, for instance. Passing those around boxed all the time is pretty
painful. Unboxing causes unsigned byte -> fixnum/bignum conversions which
robs performance. For socket-level programming, it's no big deal. You pass
things around once and then you connect the socket and you're done with
that. Think about routing code or something, though.
>
>> Note that I'm NOT saying that Lisp isn't fast or that it can't beat C on
>> some problems. I'm sure it can. Be careful of assuming that it will beat
>> C when dealing with interfaces to the outside world using protocols that
>> you cannot control, however. That is C's home turf and it does very, very
>> well there.
>
> As a former low-level C guy, I think C does it okay. It can be nice
> to take pointers and interpret the bits there however you want; it's
> not so nice to be /forced/ to interpret the bits there; it makes it
> impossible to refactor some code, which also makes some low-level
> bit-bashing optimizations impractical, because they'd result in
> combinatorial explosions. C facilitates the idea of taking a small
> efficiency hit (say, two function indirections) before launching into
> your inner loop. It would be nice if it let you take a similar hit
> with pointers, eg, "what is it that this void* points to?" Glad I've
> got Lisp, now.
Yes, I would agree with all that. When I'm doing applications-level
programming, C just forces me to think about too much stuff and leaves too
many doors open for stupid bugs. That was one reason I migrated to Java a
few years ago. And, as you say, because of its flexibility, there are some
optimizations that C compilers have a hard time with (pointer aliasing
problems are probably the most notable).
But I'm rapidly learning how much better Lisp is. I'm pretty bummed that I
didn't learn it 20 years ago. My programming experience would have been so
much different.
--
Dave Roberts, ·············@re-move.droberts.com
Slowly but surely, the programming world is finding Lisp...
http://www.findinglisp.com/blog
Dave Roberts <·············@re-move.droberts.com> writes:
> So, basically, that's what I'm saying. There are problems where you want
> 32-bit integers being passed all around. Think about networking code and IP
> addresses, for instance.
On the other hand, C-based network stacks are getting out of their
home turf and moving into Lisp's.
A case in point is Linux's 'iptables' packet filter. Viewed as a
configurable packet filter this is very nice, powerful, and
extensible. But viewed (quite reasonably) as a language for
customizing the network stack it's very primitive (much like
programming an ant). The lack of decent data structures and control
constructs make it very awkward to do serious programming with and
also leads to inefficiencies, like linearly searching rules to match a
packet when really you just want to dispatch on its IP address.
Another trouble with iptables is that it's *too* easily
extensible. The user-contributed extensions you can download from
netfilter.org are not all of high quality, and it only takes one tiny
slip to cause a kernel panic. After being bitten a couple of times you
become rather cautious about adding even very simple features.
I'm interested in a serious attempt to move all of this stuff into
userspace. I'm sure Linux will do okay just by laboriously fleshing
out and debugging a lot more kernel extensions, but that sucks a bit
IMO.
-Luke
Luke Gorrie <····@bluetail.com> writes:
[...]
> I'm interested in a serious attempt to move all of this stuff into
> userspace. I'm sure Linux will do okay just by laboriously fleshing
> out and debugging a lot more kernel extensions, but that sucks a
> bit IMO.
You may want to check out OpenBSD's PF (also ported to FreeBSD 5) [1].
Its syntax is much cleaner and thought out (based largely on
IPFilter's). It supports lists, macros [2] (not in the Lisp sense)
and tables [3].
[1] http://www.openbsd.org/faq/pf/
[2] http://www.openbsd.org/faq/pf/macros.html
[3] http://www.openbsd.org/faq/pf/tables.html
--
David Magda <dmagda at ee.ryerson.ca>, http://www.magda.ca/
Because the innovator has for enemies all those who have done well under
the old conditions, and lukewarm defenders in those who may do well
under the new. -- Niccolo Machiavelli, _The Prince_, Chapter VI
From: Christopher C. Stacy
Subject: Re: Fundamentals of Lisp efficiency?
Date:
Message-ID: <u3c4xmyse.fsf@news.dtpq.com>
>>>>> On Tue, 15 Jun 2004 01:54:50 +0200, Luke Gorrie ("Luke") writes:
Luke> How nicely could one write a TCP/IP protocol suite in Lisp?
Very nicely, it's been done at least twice.
(Doing it inside Unix is a slightly different question.)
From: Joe Marshall
Subject: Re: Fundamentals of Lisp efficiency?
Date:
Message-ID: <r7shprm2.fsf@comcast.net>
Luke Gorrie <····@bluetail.com> writes:
> I wonder similar things, coming from the other direction:
>
> How nicely could one write a TCP/IP protocol suite in Lisp?
I understand that it is quite nice. Peter DeWolf at hambo dot com was
our network wizard at LMI and he says it was much easier to do it in lisp.
> How close can the performance get to a Unix kernel without
> sacrificing clarity?
What is the performance of the Unix kernel?
> One is a second attempt at decoding TCP/IP packets in Lisp:
>
> http://www.bluetail.com/~luke/misc/lisp/packet.lisp
> or,
> http://www.bluetail.com/~luke/misc/lisp/packet.pdf
>
I understand that a key part of achieving performance is to avoid
copying packets all over the place. I would imagine, then, that you
would want to arrange for your packet buffers to be aligned in such a
way that the hardware can dump the data directly into them. I don't
know the low levels of CMUCL, but you can usually arrange (with some
wizardry) arrange for a chunk of non-moveable raw memory to be treated
as a lisp array. It may be better to use displaced arrays rather than
extracting subsequences, but you'd have to measure.
--
~jrm
In article <············@comcast.net>,
Joe Marshall <·············@comcast.net> wrote:
> Luke Gorrie <····@bluetail.com> writes:
>
> > I wonder similar things, coming from the other direction:
> >
> > How nicely could one write a TCP/IP protocol suite in Lisp?
>
> I understand that it is quite nice. Peter DeWolf at hambo dot com was
> our network wizard at LMI and he says it was much easier to do it in lisp.
I remember reading the Symbolics TCP/IP stack, and I found it quite
elegant. It was implemented using Flavors (the LispM's original OO
mechanism), and the low-level packet manipulation was done using
resources (a facility for managing pools of similar data structures, to
avoid some GC overhead) and macros for accessing bit fields in the
headers.
The object orientation made it easy to extend. I wanted our Lispms to
understand the "trailer" format of Ethernet packets that our Vaxen liked
to send, and it took me a few hours to implement this as a new class.
--
Barry Margolin, ······@alum.mit.edu
Arlington, MA
*** PLEASE post questions in newsgroups, not directly to me ***
Joe Marshall <·············@comcast.net> writes:
>> How close can the performance get to a Unix kernel without
>> sacrificing clarity?
>
> What is the performance of the Unix kernel?
I don't know for certain because I always use 100Mbps networks. I've
heard that a modern PC running Linux can route about 1.5Gbps of
traffic or proxy about 1Gbps through a user-space program. I don't
know how accurate this is or how much it varies between "modern PCs."
It sounds like writing a gigabit (aggregate) switch or router would
require very tight code. On the other hand, if you were building a
20Mbps firewall/router/funky-stuff box to sit next to your DSL link
then you might have close to a millisecond to spend on each packet.
Another fun thing is traffic analysis tools like tcpdump, ethereal,
tcptrace, etc. There you still need to decode packets and piece
protocol messages together but you don't have any particular
performance constraints.
> I understand that a key part of achieving performance is to avoid
> copying packets all over the place. I would imagine, then, that you
> would want to arrange for your packet buffers to be aligned in such
> a way that the hardware can dump the data directly into them. I
> don't know the low levels of CMUCL, but you can usually arrange
> (with some wizardry) arrange for a chunk of non-moveable raw memory
> to be treated as a lisp array. It may be better to use displaced
> arrays rather than extracting subsequences, but you'd have to
> measure.
Choosing a packet representation is really an interesting problem,
kinda like choosing a buffer structure in a text editor.
For now I like plain ol' heap-allocated structures. I plan to ride
them as far as they can take me :-)
Cheers,
Luke
P.S., on Cliki I found an old "screenshot" from the last time I hacked
on this stuff seriously (about a year ago) which I think is
pretty cute: http://www.cliki.net/Slitch
Luke Gorrie wrote:
> Joe Marshall <·············@comcast.net> writes:
>
>>> How close can the performance get to a Unix kernel without
>>> sacrificing clarity?
>>
>> What is the performance of the Unix kernel?
>
> I don't know for certain because I always use 100Mbps networks. I've
> heard that a modern PC running Linux can route about 1.5Gbps of
> traffic or proxy about 1Gbps through a user-space program. I don't
> know how accurate this is or how much it varies between "modern PCs."
The rough rule of thumb is about 1 GHz per Gbps, unidirectional (sourcing,
typically), at 100% CPU utilization. That also assumes you have that much
to say without touching your disk. As soon as you do, you're screwed.
This is why end nodes are easier. Frankly, the stack on an end node doesn't
have to be a rocket. It has to be respectable and be able to burst, but the
practical limit is governed by other components.
Now, switches and routers, on the other hand, see the aggregate traffic
flow, so they have to deal better with sustained high speeds.
The big lie, however, is that everybody needs 1 Gbps links on their desktop
and 10 Gbps backbones. Most gigE links now in service don't reach anywhere
near 1 Gbps for any sustained length of time.
> It sounds like writing a gigabit (aggregate) switch or router would
> require very tight code. On the other hand, if you were building a
> 20Mbps firewall/router/funky-stuff box to sit next to your DSL link
> then you might have close to a millisecond to spend on each packet.
Yup. 1 Gbps at 64 byte packets is > 1 Mpps. You have to do that in ASICs,
but there are other things you can do in software around that. 20 Mbps is a
stroll in the park... ;-)
> Another fun thing is traffic analysis tools like tcpdump, ethereal,
> tcptrace, etc. There you still need to decode packets and piece
> protocol messages together but you don't have any particular
> performance constraints.
Typically these work by buffering everything and doing the decoding lazily,
either during slack times when capture slows down or when the user finally
clicks on something in the GUI.
--
Dave Roberts, ·············@re-move.droberts.com
Slowly but surely, the programming world is finding Lisp...
http://www.findinglisp.com/blog
Luke Gorrie <····@bluetail.com> writes:
> Joe Marshall <·············@comcast.net> writes:
>
> >> How close can the performance get to a Unix kernel without
> >> sacrificing clarity?
> >
> > What is the performance of the Unix kernel?
>
> I don't know for certain because I always use 100Mbps networks. I've
> heard that a modern PC running Linux can route about 1.5Gbps of
> traffic or proxy about 1Gbps through a user-space program. I don't
> know how accurate this is or how much it varies between "modern PCs."
>
> It sounds like writing a gigabit (aggregate) switch or router would
> require very tight code. On the other hand, if you were building a
> 20Mbps firewall/router/funky-stuff box to sit next to your DSL link
> then you might have close to a millisecond to spend on each packet.
The bottleneck in "modern PC" is the PCI bus.
A 32bit PCI bandwidth is no more than 133 MB/s, that's only 1064 Mb/s.
Most (ie. the two I tried) Gigabit Ethernet card can't handle more
than 400 or 700 Mb/s.
--
A: Because it messes up the order in which people normally read text.
Q: Why is top-posting such a bad thing?
A: Top-posting.
Q: What is the most annoying thing on usenet and in e-mail?
From: Joe Marshall
Subject: Re: Fundamentals of Lisp efficiency?
Date:
Message-ID: <llinqzij.fsf@ccs.neu.edu>
Pascal Bourguignon <····@thalassa.informatimago.com> writes:
> The bottleneck in "modern PC" is the PCI bus.
>
> A 32bit PCI bandwidth is no more than 133 MB/s, that's only 1064 Mb/s.
>
> Most (ie. the two I tried) Gigabit Ethernet card can't handle more
> than 400 or 700 Mb/s.
So assuming the smallest packet size and the fastest transmission,
that's on the order 1 million packets per second? Should be doable in
Lisp.
Pascal Bourguignon <····@thalassa.informatimago.com> wrote:
+---------------
| > I've heard that a modern PC running Linux can route about 1.5Gbps of
| > traffic or proxy about 1Gbps through a user-space program. I don't
| > know how accurate this is or how much it varies between "modern PCs."
...
| The bottleneck in "modern PC" is the PCI bus.
| A 32bit PCI bandwidth is no more than 133 MB/s, that's only 1064 Mb/s.
+---------------
True, if my "modern PC" you mean the cheapest desktop you can buy in
a discount store or on the web. On the other hand, most serious servers
have 66 MHz PCI-64 busses (4.2 Gb/s each) *and* multiples of those busses
and/or 133 MHz PCI-X busses (~8 Gb/s each). Midrange multiprocessor
servers (e.g., <URL:http://www.sgi.com/servers/altix/350/> might
have as many as *16* PCI-X busses, and some very large servers
(e.g., <URL:http://www.sgi.com/servers/altix/>) might have as many
as *hundreds* of PCI-X busses.
+---------------
| Most (ie. the two I tried) Gigabit Ethernet card can't handle more
| than 400 or 700 Mb/s.
+---------------
That's probably more a limitation of the I/O chipset on your "modern PC"
than the Gigabit Ethernet NICs themselves. People have certainly seen
close to "wire speed" from good-quality Gigabit Ethernet NICs on the
right platforms.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Luke Gorrie wrote:
> Hi Dave,
>
> Wonderful topic :-)
I found your web site the other day. You betcha! Us comms guys have to stick
together. ;-)
> I wonder similar things, coming from the other direction:
>
> How nicely could one write a TCP/IP protocol suite in Lisp?
>
> How close can the performance get to a Unix kernel without
> sacrificing clarity?
>
> Perhaps one could then ask, what do we need to sacrifice to get within
> a factor of foo of Linux performance? That's the order I tend to
> tackle things in.
Interesting thoughts. I'm basically wondering the same thing, just thinking
embedded.
> I have some code that might be interesting to you, though you might
> choke on the inefficient programming style (at least that was my
> intention :-).
>
> One is a second attempt at decoding TCP/IP packets in Lisp:
>
> http://www.bluetail.com/~luke/misc/lisp/packet.lisp
> or,
> http://www.bluetail.com/~luke/misc/lisp/packet.pdf
>
> The other is some libraries for ethernet-level I/O on Linux, one for
> 'tuntap' (virtual network interfaces) and another for PF_PACKET
> sockets (raw I/O on existing interfaces). These can be fished out of
> tuntap.lisp and packet-socket.lisp from the sourceforge project
> 'slitch'. There's also a partial first-attempt at a TCP/IP
> implementation in there but it's a pretty ugly.
Excellent. I'll take a look. Any idea how fast it was versus the alternative
(C)?
> Anyway, if you do any experiments with low-level networking in Lisp
> then I'd love to hear about them.
My thought was that I wouldn't do anything in CL, but was wondering about a
Lisp dialect specially optimized for datacomm, much like what Naughty Dog
did for video games. The one issue here is that it's hard to get people on
your side when you have one of these nutty ideas. I have heard that Naughty
Dog struggled to find Lisp programmers.
> Recently I wrote the traffic handling part of a "funky" switch product
> in Erlang. That was great: it worked right away so I had time to
> figure out all the tricky higher-level things that had to be
> done. Afterwards it took about one day to port the traffic handling
> code into the kernel for a ~5x performance gain.
Nice. Was this a datacomm or telecomm switch? I ask because the two are VERY
different. Things in a telecomm switch happen orders of magnitude slower
than a datacomm switch--they're just very, very reliable.
Also, I'm not familiar with Erlang other than Ericsson invented it for their
telecomm switch projects. What are its great strengths?
> NB (regarding other postings): Erlang is not usually used for packet
> handling in switches, just for the higher-level
> control/distribution/OA&M etc parts. It does have a very neat "bit
> syntax" for dealing with structured binary data but I'm not sure what
> its exact speed is, e.g. how long it takes to decode an IPv4 PDU.
Interesting.
> Dumb-and-fast switches aside, Erlang is commonly used for traffic
> handling with higher-level protocols like HTTP.
Yea, anything application-level can certainly be handled in just about any
language. Once you're through the sockets layer, you have given all the
speed away anyway and it's all about programmer convenience.
--
Dave Roberts, ·············@re-move.droberts.com
Slowly but surely, the programming world is finding Lisp...
http://www.findinglisp.com/blog
[Sorry I couldn't find any better place to insert this comment...]
Wade Humeniuk <····································@telus.net> wrote:
+---------------
| Though I am a little curious, performance switches tend to be
| multi-processor beasts, with custom cards for various switch functions.
+---------------
And don't forget the "Erlang" language, developed by Ericsson
specifically for coding telephony switches...
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
····@rpw3.org (Rob Warnock) writes:
> [Sorry I couldn't find any better place to insert this comment...]
>
> Wade Humeniuk <····································@telus.net> wrote:
> +---------------
> | Though I am a little curious, performance switches tend to be
> | multi-processor beasts, with custom cards for various switch functions.
> +---------------
>
> And don't forget the "Erlang" language, developed by Ericsson
> specifically for coding telephony switches...
Ericsson also had a language named PLEX, which is as different
from Erlang as possible. Erlang is nice.
--
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/
From: Christopher C. Stacy
Subject: Re: Fundamentals of Lisp efficiency?
Date:
Message-ID: <u8yeuhpuw.fsf@news.dtpq.com>
>>>>> On Thu, 10 Jun 2004 07:42:48 GMT, Dave Roberts ("Dave") writes:
Dave> Some background: I work in the communications
Dave> infrastructure market (I build datacomm switches).
Dave> So, a natural question is how a Lisp-like language could be
Dave> create for this environment.
Symbolics developed a real-time CL operating system for AT&T,
which they used to implement an advanced version of their long
distance ESS switch. This was a big success, ran the switching
at their research facility outside Chicago, and then was promptly
killed because of the political ramifications. The embedded
operating system, which ran on custom Symbolics hardware based
on the Ivory chip, connected to the switching fabric over high
speed Ethernet, was called "Minima", while application development
was done using the "Genera" environment (which could also run exactly
the same Common Lisp environment in parallel with all its other
goodies) and remote control (cross compiling, networked REPL, etc.).
I think that Harlequin later did some related work for AT&T using
Lispworks on a conventional architecture, but the new performance
requirements were much looser than what the Minima achieved.
There might be some papers floating around about Minima, or maybe not,
as it was all fairly secret at the time. The AT&T guys did publish at
least something about some version of their switching application
(in AAAI or IJCAI or someplace like that, I think.)
So, yes, I am sure it is possible to develop a Lisp environment
that is suitable for those real-time switching applications.
(Or at least it was, about 15 years ago.)
Speaking of telecommunications in general, Symbolics also had (all of,
as I recall) the other major telephone companies as customers, doing
real-time fraud detection, data fusion and cross-platform integration
systems, service design tools, and so on. Those customers just used
the "Genera" operating system. The Lisp Machine was viewed as the
ultimate connectivity platform. In the mundane area, I know that
Lispworks (on Windows) has been used for similar slow real-time
and not-real-time applications involving IXC billing systems, EMI,
and fraud analysis. I would not be surprised to learn that Franz
has done some work with telecommunications customers, also.
On the very low end of the "real time" problems in this vast realm of
telecommunications, I would note that many of those kinds of problems,
dealing with multiple, idiosyncratic, legacy data streams, are rather
similar to the challenges faced by the travel reservation industry.
You might want to talk to the folks at ITA/Orbitz about that.
Lisp has also been used for real-time network monitoring with dynamic
control functions (eg. automatic tuning of packet swiching nodes
according to measured traffic performance involving multiple kinds
of terrestrial and satellite lines). That project was in Franz/SUN.
In the realm of real-time process control, you might want to look at
what Gensym has done with Lisp. Finally, Lisp has also been used for
the control hubs of distributed real-time applications in high speed
physics, military weapons simulations (video games where you drive
around virtual tanks and helecopters), etc.
Christopher C. Stacy <······@news.dtpq.com> wrote:
+---------------
| On the very low end of the "real time" problems in this vast realm of
| telecommunications, I would note that many of those kinds of problems,
| dealing with multiple, idiosyncratic, legacy data streams, are rather
| similar to the challenges faced by the travel reservation industry.
| You might want to talk to the folks at ITA/Orbitz about that.
+---------------
And wasn't there a paper at ILC 2003 on using CL to run a brokerage firm?
[Espen Vestre, from Net Fonds?] They also had the same problems of
multiple idiosyncratic legacy data streams.
In fact, there was a whole section (1/2-day of one track?) of the
conference on financial applications...
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
Christopher C. Stacy wrote:
> Symbolics developed a real-time CL operating system for AT&T,
> which they used to implement an advanced version of their long
> distance ESS switch. This was a big success, ran the switching
> at their research facility outside Chicago, and then was promptly
> killed because of the political ramifications. The embedded
> operating system, which ran on custom Symbolics hardware based
> on the Ivory chip, connected to the switching fabric over high
> speed Ethernet, was called "Minima", while application development
> was done using the "Genera" environment (which could also run exactly
> the same Common Lisp environment in parallel with all its other
> goodies) and remote control (cross compiling, networked REPL, etc.).
>
> I think that Harlequin later did some related work for AT&T using
> Lispworks on a conventional architecture, but the new performance
> requirements were much looser than what the Minima achieved.
>
> There might be some papers floating around about Minima, or maybe not,
> as it was all fairly secret at the time. The AT&T guys did publish at
> least something about some version of their switching application
> (in AAAI or IJCAI or someplace like that, I think.)
>
> So, yes, I am sure it is possible to develop a Lisp environment
> that is suitable for those real-time switching applications.
> (Or at least it was, about 15 years ago.)
What were the timing requirements of these systems? I ask because typically
telecomm and datacomm have very different requirements. They're both
similar in that they have real-time requirements, but the scales are a bit
different. In the datacomm world, my event stream is happening at 50 KHz or
more 1 MHz. That's basically a packet data rate or something like that. I
have found that telecomm typically doesn't have an event stream that runs
that quickly, but has other requirements that make in equally challenging,
but in slightly different ways.
--
Dave Roberts, ·············@re-move.droberts.com
Slowly but surely, the programming world is finding Lisp...
http://www.findinglisp.com/blog
From: Christopher C. Stacy
Subject: Re: Fundamentals of Lisp efficiency?
Date:
Message-ID: <uk6yehy70.fsf@news.dtpq.com>
>>>>> On Fri, 11 Jun 2004 04:36:21 GMT, Dave Roberts ("Dave") writes:
Dave> Christopher C. Stacy wrote:
>> Symbolics developed a real-time CL operating system for AT&T,
>> which they used to implement an advanced version of their long
>> distance ESS switch. This was a big success, ran the switching
>> at their research facility outside Chicago, and then was promptly
>> killed because of the political ramifications. The embedded
>> operating system, which ran on custom Symbolics hardware based
>> on the Ivory chip, connected to the switching fabric over high
>> speed Ethernet, was called "Minima", while application development
>> was done using the "Genera" environment (which could also run exactly
>> the same Common Lisp environment in parallel with all its other
>> goodies) and remote control (cross compiling, networked REPL, etc.).
>>
>> I think that Harlequin later did some related work for AT&T using
>> Lispworks on a conventional architecture, but the new performance
>> requirements were much looser than what the Minima achieved.
>>
>> There might be some papers floating around about Minima, or maybe not,
>> as it was all fairly secret at the time. The AT&T guys did publish at
>> least something about some version of their switching application
>> (in AAAI or IJCAI or someplace like that, I think.)
>>
>> So, yes, I am sure it is possible to develop a Lisp environment
>> that is suitable for those real-time switching applications.
>> (Or at least it was, about 15 years ago.)
Dave> What were the timing requirements of these systems? I ask because typically
Dave> telecomm and datacomm have very different requirements. They're both
Dave> similar in that they have real-time requirements, but the scales are a bit
Dave> different. In the datacomm world, my event stream is happening at 50 KHz or
Dave> more 1 MHz. That's basically a packet data rate or something like that. I
Dave> have found that telecomm typically doesn't have an event stream that runs
Dave> that quickly, but has other requirements that make in equally challenging,
Dave> but in slightly different ways.
I don't remember the rates, but everything you've said is quite correct.
In article <·············@news.dtpq.com>,
······@news.dtpq.com (Christopher C. Stacy) wrote:
> >>>>> On Thu, 10 Jun 2004 07:42:48 GMT, Dave Roberts ("Dave") writes:
>
> Dave> Some background: I work in the communications
> Dave> infrastructure market (I build datacomm switches).
>
> Dave> So, a natural question is how a Lisp-like language could be
> Dave> create for this environment.
>
> Symbolics developed a real-time CL operating system for AT&T,
> which they used to implement an advanced version of their long
> distance ESS switch. This was a big success, ran the switching
> at their research facility outside Chicago, and then was promptly
> killed because of the political ramifications. The embedded
> operating system, which ran on custom Symbolics hardware based
> on the Ivory chip, connected to the switching fabric over high
> speed Ethernet, was called "Minima", while application development
> was done using the "Genera" environment (which could also run exactly
> the same Common Lisp environment in parallel with all its other
> goodies) and remote control (cross compiling, networked REPL, etc.).
>
> I think that Harlequin later did some related work for AT&T using
> Lispworks on a conventional architecture, but the new performance
> requirements were much looser than what the Minima achieved.
They used LispWorks with a real-time GC on the switching nodes
and Allegro CL on the management node (with AllegroStore as
the database. This has been used in commercial product(s):
Globeview 2000.
>
> There might be some papers floating around about Minima, or maybe not,
> as it was all fairly secret at the time. The AT&T guys did publish at
> least something about some version of their switching application
> (in AAAI or IJCAI or someplace like that, I think.)
>
> So, yes, I am sure it is possible to develop a Lisp environment
> that is suitable for those real-time switching applications.
> (Or at least it was, about 15 years ago.)
>
> Speaking of telecommunications in general, Symbolics also had (all of,
> as I recall) the other major telephone companies as customers, doing
> real-time fraud detection, data fusion and cross-platform integration
> systems, service design tools, and so on. Those customers just used
> the "Genera" operating system. The Lisp Machine was viewed as the
> ultimate connectivity platform. In the mundane area, I know that
> Lispworks (on Windows) has been used for similar slow real-time
> and not-real-time applications involving IXC billing systems, EMI,
> and fraud analysis. I would not be surprised to learn that Franz
> has done some work with telecommunications customers, also.
>
> On the very low end of the "real time" problems in this vast realm of
> telecommunications, I would note that many of those kinds of problems,
> dealing with multiple, idiosyncratic, legacy data streams, are rather
> similar to the challenges faced by the travel reservation industry.
> You might want to talk to the folks at ITA/Orbitz about that.
>
> Lisp has also been used for real-time network monitoring with dynamic
> control functions (eg. automatic tuning of packet swiching nodes
> according to measured traffic performance involving multiple kinds
> of terrestrial and satellite lines). That project was in Franz/SUN.
>
> In the realm of real-time process control, you might want to look at
> what Gensym has done with Lisp. Finally, Lisp has also been used for
> the control hubs of distributed real-time applications in high speed
> physics, military weapons simulations (video games where you drive
> around virtual tanks and helecopters), etc.
Dave Roberts wrote:
> So, if you could strip down a Lisp and make it as fast as possible, what
> would it start to look like?
One place you might wind up is at ML, or an ML with Lisp syntax (so
you'd have macros). (All languages have Lisp syntax, of course, except
that so many of them insist on encrypting it using a mechanism called
"grammar.") ML has been a major focus of compiler theorists, so it is
said to compile to terrific code, although probably not as efficient as
compiled Fortran for numerical applications.
> Would it essentially be something like CL with a huge number
> of declarations (memories of that optimization challenge that was floating
> around here a few months ago)?
ML has almost _no_ declarations, because, like most functional
programming languages, it has a good type-inference system.
> Which features would have you have drop and
> which could you retain?
Having taught a course using ML (so I could learn it), I can report that
there are two big things you have to give up: run-time type dispatching
and object-oriented programming. (Actually these turn out to be the
_same_ thing.) You have to give up run-time type dispatching because
you can't write "if (symbolp x) then ...." There are alternative ways
to get what you want here, but they take getting used to.
You have to give up OOP because ML's type system can't cope with objects
whose type is implicit in the messages (or generic functions) they can
handle. ML insists that the type of every expression be known at
compile time, so if you implement an object as a tuple of message
handlers, and the expression 'ob' denotes one of these things, then the
type of 'ob' must be (or contain)
(a1 -> b1) * (a2 -> b2) * ... * (aN -> bN)
that is, a tuple of function types, all of which are known at compile
time. This more or less defeats the purpose of OOP, although there are
cases which fit this mold. An extensive literature search revealed that
OOP in ML is essentially impossible. Other languages do better,
especially OCAML (Object-oriented something-something ML), but
apparently by various ad-hoc add-ons. In any case, if you want blinding
efficiency you probably want to stay away from CLOS.
--
-- Drew McDermott
Yale Computer Science Department
Drew McDermott <··················@at.yale.dot.edu> writes:
> Other languages do better, especially OCAML (Object-oriented
> something-something ML), but apparently by various ad-hoc add-ons.
Actually, as far as I can tell, OCaml does its best to avoid ad-hoc
add-ons: If the folks at Inria haven't figured out a good theoretical
foundation for something, it generally doesn't go into the language.
--
T. Kurt Bond, ···@tkb.mpl.com
From: Friedrich Dominicus
Subject: Re: Fundamentals of Lisp efficiency?
Date:
Message-ID: <87n039xnyx.fsf@fbigm.here>
···@tkb.mpl.com (T. Kurt Bond) writes:
> Drew McDermott <··················@at.yale.dot.edu> writes:
>> Other languages do better, especially OCAML (Object-oriented
>> something-something ML), but apparently by various ad-hoc add-ons.
>
> Actually, as far as I can tell, OCaml does its best to avoid ad-hoc
> add-ons: If the folks at Inria haven't figured out a good theoretical
> foundation for something, it generally doesn't go into the language.
I do think the Ocaml people have done a very good job but I disagree
with this. Have you checked how optional parameters and keyword
parameters are implemented?
Regards
Friedrich
--
Please remove just-for-news- to reply via e-mail.
Hello!
Dave Roberts <·············@re-move.droberts.com> wrote:
>Some background: I work in the communications infrastructure market (I build
>datacomm switches). One of the things that has always interested me is
>trying to find better tools to do that job. Most datacomm switches are
>programmed using C with VxWorks or (now) embedded Linux as the OS. As a
>result, we suffer all the standard problems that you'd expect to find on
>such a system: corrupted memory, various malloc/free problems, etc.
>Further, programmer productivity is lower than it should be.
>[...]
While not completely on-topic here, this lets me think again of Erlang.
They've been there and done that (programming switches and so on using
Erlang [+ C, if needed for low level driver code).
We're doing something around UMS with Erlang in the company I work at,
too, and are quite content with it.
Kind regards,
Hannah.