[TUHS] lisp challenge

[TUHS] lisp challenge

[Larry McVoy]

So people have called me on the claim that lisp is not fast.  Here's a 
rebuttal.

Please write a clone of GNU grep in lisp to demonstrate that the claim
that lisp is slower that C is false.

Best of luck and I'll be super impressed if you can get even remotely
close without dropping into C or assembler.  If you do get close, I 
will with draw my claim, stand corrected, point future "lisp is slow"
people at the lisp-grep, and buy you dinner and/or drinks.

--lm

[TUHS] lisp challenge

[Larry McVoy]

On Fri, Feb 16, 2018 at 01:01:14PM -0800, Larry McVoy wrote:
> So people have called me on the claim that lisp is not fast.  Here's a 
> rebuttal.
> 
> Please write a clone of GNU grep in lisp to demonstrate that the claim
> that lisp is slower that C is false.
> 
> Best of luck and I'll be super impressed if you can get even remotely
> close without dropping into C or assembler.  If you do get close, I 
> will with draw my claim, stand corrected, point future "lisp is slow"
> people at the lisp-grep, and buy you dinner and/or drinks.
> 
> --lm

And to help you, here is Mike explaining how he made GNU grep fast. 
You are welcome to use the same techniques in lisp.

https://lists.freebsd.org/pipermail/freebsd-current/2010-August/019310.html#

[TUHS] lisp challenge

[Bakul Shah]

On Fri, 16 Feb 2018 13:01:14 -0800 Larry McVoy <lm at mcvoy.com> wrote:
Larry McVoy writes:
> So people have called me on the claim that lisp is not fast.  Here's a 
> rebuttal.
> 
> Please write a clone of GNU grep in lisp to demonstrate that the claim
> that lisp is slower that C is false.
> 
> Best of luck and I'll be super impressed if you can get even remotely
> close without dropping into C or assembler.  If you do get close, I 
> will with draw my claim, stand corrected, point future "lisp is slow"
> people at the lisp-grep, and buy you dinner and/or drinks.

If you want to do more of an apples to apples comparison, you
should pick a brand new problem not known to be solved in
either C or Lisp so that both sides start at the same point!

I do think that if you consider just the raw performance as
the sole metric, C will almost always win.  After all it is
sort of a portable assembly language & you can compile
programs in most language to C. But in the real world many
other factors matter too.  So to make the contest a bit more
fair, you should put a time limit on the effort.

[TUHS] lisp challenge

[Larry McVoy]

On Fri, Feb 16, 2018 at 02:05:09PM -0800, Bakul Shah wrote:
> On Fri, 16 Feb 2018 13:01:14 -0800 Larry McVoy <lm at mcvoy.com> wrote:
> Larry McVoy writes:
> > So people have called me on the claim that lisp is not fast.  Here's a 
> > rebuttal.
> > 
> > Please write a clone of GNU grep in lisp to demonstrate that the claim
> > that lisp is slower that C is false.
> > 
> > Best of luck and I'll be super impressed if you can get even remotely
> > close without dropping into C or assembler.  If you do get close, I 
> > will with draw my claim, stand corrected, point future "lisp is slow"
> > people at the lisp-grep, and buy you dinner and/or drinks.
> 
> If you want to do more of an apples to apples comparison, you
> should pick a brand new problem not known to be solved in
> either C or Lisp so that both sides start at the same point!

Nope.  It's my challenge and it stands as I stated it.  People said
I was wrong when I said Lisp was perceived as slow.  I picked a 
perfectly reasonable example of a common problem (text processing),
gave a benchmark, gave a pointer to how the C program was made fast,
and asked for a lisp program that even comes close.

If that can't be done, then the claim that lisp is slow still stands.

When people said I was "putting inaccuracies into the archives" or
"perpetuating a myth" I wondered if I was wrong.  Nobody said "well,
yes, C is faster for systems stuff or this or that, but lisp is faster
in this domain".  They said that the claim that lisp is slow is not
true.

Just saying that lisp is not slow is not the same as demonstrating it.

I'm more than willing to be wrong, that's how I learn.  But the proof
here is to show up with a pure lisp grep that is fast as the C version.
I'm no lisp expert, not by any stretch, but I've never seen a lisp
program that out performed a well written C program.

The point was that lisp was/is perceived as a slow language.  Several
people said that's false, I'm just asking for them to demonstrate that
it is false by writing grep in lisp.  Who knows?  Maybe it can be done.

[TUHS] lisp challenge

[Donald ODona]

I definitely agree with your words. Furthermore I point to the fact 
that lisp  is totally different to any other language, the archaic 
algol, cobol and fortran languages included. Therefore one makes 
automatically mistakes after longer periods of intensive
lisp coding and vice versa, despite the fact that the lisp approach
basically is very simple, not to say oversimplified. Anyhow there
aren't many lispers anymore. In business lisp plays no role at all.
Its a pet of so backward oriented academicians.

At 16 Feb 2018 22:29:33 +0000 (+00:00) from Larry McVoy <lm at mcvoy.com>:
> Nope.  It's my challenge and it stands as I stated it.  People said
> I was wrong when I said Lisp was perceived as slow.  I picked a 
> perfectly reasonable example of a common problem (text processing),
> gave a benchmark, gave a pointer to how the C program was made fast,
> and asked for a lisp program that even comes close.
> 
>...

[TUHS] lisp challenge

[Arthur Krewat]

Has ANY language (except assembler) EVER outperformed C in a big way?

Give or take any optimizations that may be done by either?

On 2/16/2018 5:28 PM, Larry McVoy wrote:
> I'm no lisp expert, not by any stretch, but I've never seen a lisp
> program that out performed a well written C program.

[TUHS] lisp challenge

[Arthur Krewat]

On 2/16/2018 5:53 PM, Donald ODona wrote:
> Anyhow there
> aren't many lispers anymore. In business lisp plays no role at all.
I know of a first-person shooter game that has embedded scripts in the maps.

The scripting language in the maps is ... LISP. ;) - Not sure if it's 
JIT, but it's definitely interpreted and not compiled.

It's been around since the early 2000's, has versions on XBOX and PC and 
newer versions are being released to this day. Knowing the company 
creating these new versions and maps, I doubt they moved away from LISP.

Good ole Halo.

[TUHS] lisp challenge

[Larry McVoy]

I suspect that back in the day Fortran may have beat C for scientific
computations (vector stuff would be my guess).  But x86 extensions do
vectors as do the GPUs so I don't know of anything that beats C in a
big way.

On Fri, Feb 16, 2018 at 05:56:59PM -0500, Arthur Krewat wrote:
> Has ANY language (except assembler) EVER outperformed C in a big way?
> 
> Give or take any optimizations that may be done by either?
> 
> On 2/16/2018 5:28 PM, Larry McVoy wrote:
> >I'm no lisp expert, not by any stretch, but I've never seen a lisp
> >program that out performed a well written C program.

-- 
---
Larry McVoy            	     lm at mcvoy.com             http://www.mcvoy.com/lm 

[TUHS] lisp challenge

[Toby Thain]

On 2018-02-16 5:56 PM, Arthur Krewat wrote:
> Has ANY language (except assembler) EVER outperformed C in a big way?
> 
> Give or take any optimizations that may be done by either?
> 


As Tim wisely pointed out, performance isn't a property of a language,
but a program, so the idea that C is some kind of untouchable ultimate
in speed makes no sense. There are aspects of its design that militate
_against_ performance and preclude optimisations that are possible in
other languages.

Therefore nobody should be shocked that programs in other languages
certainly _have_ beaten C for the same tasks. An illuminating example is
the Haskell Mio system which has benchmarked to outperform C web
servers. Expect more progress from that direction.

--Toby

[TUHS] lisp challenge

[Andy Kosela]

On Friday, February 16, 2018, Larry McVoy <lm at mcvoy.com> wrote:

> So people have called me on the claim that lisp is not fast.  Here's a
> rebuttal.
>
> Please write a clone of GNU grep in lisp to demonstrate that the claim
> that lisp is slower that C is false.
>
> Best of luck and I'll be super impressed if you can get even remotely
> close without dropping into C or assembler.  If you do get close, I
> will with draw my claim, stand corrected, point future "lisp is slow"
> people at the lisp-grep, and buy you dinner and/or drinks.
>
> --lm
>

Good challenge.  I consider anything that came out of MIT's ITS/Lisp
(including Emacs) culture as totally opposite to the UNIX/C culture.
Complexity vs. minimalism are the best words to explain both approaches to
computing.

--Andy
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://minnie.tuhs.org/pipermail/tuhs/attachments/20180216/24b369b2/attachment-0001.html>

[TUHS] lisp challenge

[Larry McVoy]

On Fri, Feb 16, 2018 at 06:18:28PM -0500, Toby Thain wrote:
> On 2018-02-16 5:56 PM, Arthur Krewat wrote:
> > Has ANY language (except assembler) EVER outperformed C in a big way?
> > 
> > Give or take any optimizations that may be done by either?
> 
> As Tim wisely pointed out, performance isn't a property of a language,
> but a program, so the idea that C is some kind of untouchable ultimate
> in speed makes no sense. 

Nobody claimed that.  I claimed, based on what I've been told by people
who programmed in lisp and some small personal experience, that lisp 
was and is perceived as a slow language, certainly slower than C.

Lisp fans hate that claim because they want everyone to program in Lisp,
or at least let them program in lisp.

I tipped my hat to the belief, I've never experience it myself but I've
heard it claimed, that a skilled lisp coder solves problems, especially
compiler like problems, in lisp faster than a skilled C programmer would.

I think that reality is that lispers like lisp because they can claim
they are "done" faster than they would if they had to do the same thing
in C (or other procedural) languages.

That is a HORRIBLE reason to like a language.  In my not at all
humble opinion.  If lisp were a language that was easy to read, for all
programmers not just people who love lisp, OK, maybe.  But it is not,
it's a miserable language to scan and understand.  Contrast it with C or
go or any of other procedural languages.  Any programmer can read C
and quickly understand what it is doing.  The same is not true of 
lisp.

I strongly suspect that lisp people optimize for speed of writing 
whereas most experienced people optimize for the speed of reading.
It's write one, read many.

> Therefore nobody should be shocked that programs in other languages
> certainly _have_ beaten C for the same tasks. 

But not lisp.  Or at least, nobody wants to take up my grep challenge.

--lm

P.S.  For the record, I tried to like lisp.  I wrote lisp programs,
I tried.  Just like I tried to like emacs.  I'm apparently not smart
enough to join the hallowed grounds where the lispers live.  C/vi for
stupid me.

[TUHS] lisp challenge

[Bakul Shah]

On Fri, 16 Feb 2018 14:28:35 -0800 Larry McVoy <lm at mcvoy.com> wrote:
> On Fri, Feb 16, 2018 at 02:05:09PM -0800, Bakul Shah wrote:
> > 
> > If you want to do more of an apples to apples comparison, you
> > should pick a brand new problem not known to be solved in
> > either C or Lisp so that both sides start at the same point!
> 
> Nope.  It's my challenge and it stands as I stated it.  People said
> I was wrong when I said Lisp was perceived as slow.  I picked a 
> perfectly reasonable example of a common problem (text processing),
> gave a benchmark, gave a pointer to how the C program was made fast,
> and asked for a lisp program that even comes close.

By issuing this challenge you automatically "win" as no one is
going to take up your challenge and spend the kind of time
that was needed to optimize GNU grep.  Very clever of you! But
if you are serious, it is only fair that both sides start with
a clean slate.

Here's a somewhat related problem: Consider trees with zero or
more integers as leaves.  For example, ((1 2)3(4 (5 () 6))).
A file contains 0 or more such trees.  Write a tree-grep to
find and print trees with matching fringes. For example:

.*3.*5.* matches the above tree
.*(3).* doesn't as there is no subtree with 3 as its sole leaf
.*(.*2)[2,3].* also matches
.*(.*2.+).* doesn't as 2 is the last leaf and we want at least one more
.*(4#(.*().*).*).* matches -- (4...) contains (.*().*) 0 or more levels down.

. is any, * is 0 or more, + is 1 or more, # is like ** in zsh.
[...] is used to specify alternatives.  e.g {0-5,11-23, 99-}.
Assume unsigned ints.

#(5.*) says there is some subtree with 5 as the first leaf.

Syntax needs to be refined to be able to exactly specify
the shape one wants.

For extra credit also generate a tree-sed!

> I'm more than willing to be wrong, that's how I learn.  But the proof
> here is to show up with a pure lisp grep that is fast as the C version.
> I'm no lisp expert, not by any stretch, but I've never seen a lisp
> program that out performed a well written C program.

http://www.ffconsultancy.com/ocaml/ray_tracer/languages.html

Has a comparison of several languages used for implementing
raytracing. Harrop's graph is weird but for 32bit word
machines Stalin comes close to g++ results.

[TUHS] lisp challenge

[Noel Chiappa]

    > From: Larry McVoy <lm at mcvoy.com>

    > the proof here is to show up with a pure lisp grep that is fast as the C
    > version. ... I've never seen a lisp program that out performed a well
    > written C program.

Your exact phrase (which my response was in reply to) was "lisp and
performance is not a thing". You didn't say 'LISP is not just as fast as C' -
a different thing entirely. I disagreed with your original statement, which
seems to mean 'LISP doesn't perform well'.

Quite a few people spent quite a lot of time making LISP compiler output fast,
to the point that it was possible to say "this compiler is also intended to
compete with the S-1 Pascal and FORTRAN compilers for quality of compiled
numeric code" [Brooks,Gabriel and Steele, 1982] and "with the development of
the S-1 Lisp compiler, it once again became feasible to implement Lisp in Lisp
and to expect similar performance to the best hand-tuned,
assembly-language-based Lisp systems" [Steele and Gabriel, 1993].

	Noel