Beating C with Common Lisp | Hacker News Reader

Beating C with Common Lisp

verisimilitudes.net

Do you have actual benchmarks comparing the the runtimes to justify the competitiveness between the two programs? With no types declared and no optimization declarations, I feel it would still be around 2-10x slower than C. (I have no quantitative evidence for that feeling though, except that I write Common Lisp in my day job. I have no doubt the program could be within 1-2x of C with appropriate massaging.) That’s certainly “good enough” in most cases, as evidenced by Python running so much of the world.

The blasé attitude toward adhering to POSIX/GNU wc behavior was a bit dissatisfying to me. Those additions are “trivial” and probably don’t change the shape of the program too much, but are nonetheless complicating and time-consuming factors. I would prefer that Lispers strive to complete 100% of the job, not the 80% cut that matters to them. :)

With all that said, I agree with the opinion of the article, being preferable to write Lisp over C, though I would be up-front about the meaning of “beating C”. C has been beat—in my and the author’s opinion—because Lisp strikes an unusually good balance between execution efficiency, speed of development, program safety, and expressiveness. But even better, Lisp lets you push in any of these directions, often with only modest sacrifices in the others.

However, the original spirit of the wc exercise was to make it fast, Benchmarks Game-style.

I do have some testing that showed me the Common Lisp was roughly the same speed as the C, when testing against a file of a few dozen megabytes. As I explain, I wasn't interested in optimizing it further, as I feel showing this achieved in just a few minutes to be valuable on its own. I also note that a C programmer may boast about being a small fraction of a second faster, ignoring everything else that goes into the program, which I find foolish.

The reason I didn't strictly adhere to the POSIX behavior was because I don't know where this is documented and don't feel like scanning through the C to find out. On all of the files I've tested, which include a wide array of punctuation and other such things, the results were identical, but I'm merely not making any promises. I'd prefer to not be accused of being one of those Lispers who only complete part of the program; if you look at the libraries I've written, which actually concern me, then you'll find they're well-documented and rather comprehensive for their purposes.

I think it would be a great addition to the article to show the speed as-is with a couple measurements, then show what popping in a few DECLAREs does.

That data is context for your claims, and we're missing it.

Sure, but he's not going to provide it because it either (a) doesn't exist or (b) doesn't support his argument.

POSIX specifications are available here: https://pubs.opengroup.org/onlinepubs/9699919799/idx/utiliti...

TIL C99 is part of the POSIX standard…

Yeah, there's a number of surprising (but optional) inclusions. c99 is part of the "C-Language Development Utilities" optional group.

POSIX is about compatibility for 2 programming languages: C99 and Bourne Shell. POSIX incorporates the C99 spec by reference, and duplicates much of it (lots of pages say "The functionality described on this reference page is aligned with the ISO C standard. Any conflict between the requirements described here and the ISO C standard is unintentional."), but does not fully include/duplicate the C99 spec.

I timed it on a 329MB 'tags' file I had lying around, and got 30.6 seconds for the lisp version, vs. 1.07 seconds for the BSD-style `wc` shipped with OSX. I used SBCL installed from brew.

Can I ask what you do in your day job that you get to write Common Lisp?

I help build quantum computers, and a good chunk of the software is written in Lisp. The quantum compiler and simulator are in Lisp and they’re open source. [1,2]

[1] compiler https://github.com/rigetti/quilc

[2] simulator https://github.com/rigetti/qvm

Jealous!

Even supposing they beat the GNU wc, that's not too hard... try beating this one: https://github.com/begriffs/wc

I wrote it in reply to an earlier post, where someone "beat C" with Haskell.

GNU wc is actually fairly fast for what it does.

That being said, even with all the extra stuff it's doing, I'd assume it to perform roughly as well as your single-threaded version (when you use a non-multibyte locale to keep the comparison even remotely fair).

here you go: https://github.com/expr-fi/fastlwc "Beating wc with C"

That's awesome, thanks for sharing. :) There's always someone smarter...

Interesting! Looks like my twc written in the style of Sean Barrell's Lexing paper was beat :)

    alx@foo:~/Git$ time ./wc/threads 1 twc/big.txt 
    128457 1095695 6488666

    real 0m0.022s
    user 0m0.022s
    sys 0m0.000s

    alx@foo:~/Git$ time ./twc/twc twc/big.txt 
    128457 1095695 6488666 twc/big.txt

    real 0m0.037s
    user 0m0.025s
    sys 0m0.012s

> Benchmarks Game-style

Once upon a time

https://salsa.debian.org/benchmarksgame-team/archive-alioth-...

https://web.archive.org/web/20010616231931/http://www.bagley...

The author has updated his post with benchmarks. The Lisp version is ~30% slower than the coreutils C version.

Which I don't see what the point of the article is then. It's just some guy ranting about his preferences I guess. Which is fine, but like... lead with that.

> There are likely some differences between POSIX wc and this, involving how characters are treated as words, but I'm uncaring. I'd rather argue the former is erroneous in its treating of punctuation as ``words'', but it's largely irrelevant for the purpose.

> A criticism would be pointing out that the C program must initialize and parse arguments and other such things, and yet I believe this is more points for the Common Lisp than against, as it's entirely unreasonable to waste so many resources for such a trivial result.

The author should make up their mind whether they're comparing programming languages or more high-level design decisions (should functionality deserve its own executable, etc). In the current form, I can't see a strong point made regarding either of these questions.

"I beat C.... by running a different race, and the outcome of the race was determined by my opinion of who the winner is based on no particular specified measure but the way I ran the race was pretty cool, so it must be better! anyways the race was pretty pointless in the first place, anyways, I won"

Ok. Not the best article. I'm sure there was a better point to be made

One thing both this article and the last one did was conflate their system's built in WC program with the C programming language.

They also compared a bare-bones wc program that only needs to care about the happy path versus one that needs to be fully featured and flexible (e.g. handling unicode with the -m flag, etc.)

But with this approach it's also trivial to beat C with, well, C. (Actually I cheated a bit and used C++, but same idea. Got roughly 10x speedup in WSL on windows with a naive approach).

There's very little technical substance to this article, and I found the tone of it peculiar and off-putting.

Let's not forget that the occasions where Lisp is faster than C are the exception and not the rule. If it were otherwise, the article would be titled "Beating Lisp with C".

They’re exceptions because Lisp programmers are rarely looking to match the inherent unsafety of C by removing heap allocation, bounds checks, type checks, overflow checks, and so on. For many programmers, those are valuable features, something not reflected in the average C program. Eliminating those—much of which is an exercise in declaring what you believe are facts to the compiler—is not difficult, and it’s not hard to produce assembly rather close to that of a usual C compiler.

> It does help that wc is such a useless and trivial program that it doesn't rightly benefit from such interfaces only exposed to C which languages such as Common Lisp avoid out of good taste and a sense of proper design

> Lisp is still #1 for key algorithmic techniques such as recursion and condescension.

--Verity Stob

I am at this point entirely unsure if the author is knowingly self-deprecating or unknowingly proving Ms Stob correct.

Don't get me wrong -- I love Common Lisp (except when it comes to I/O). The underlying OS and drivers are almost certainly written in C. To think you are going to consistently beat (correctly written) C at I/O is unrealistic.

Luckily not all OSes are written in C, mostly only those of UNIX/POSIX influence.

For example?

https://www.toptal.com/c/after-all-these-years-the-world-is-...

IBM i, z/OS, Unisys ClearPath MCP, BeOS, Symbian, Arduino, ARM mbed.

Additionally that article should be updated in what matters Windows, as Microsoft has been moving everything into C++ since Vista.

https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-an...

https://docs.microsoft.com/en-us/cpp/build/reference/kernel-...

https://docs.microsoft.com/de-de/windows-hardware/drivers/ge...

https://devblogs.microsoft.com/cppblog/the-great-c-runtime-c...

> We have converted most of the CRT sources to compile as C++, enabling us to replace many ugly C idioms with simpler and more advanced C++ constructs. The publicly callable functions are still declared as C functions, of course (extern "C" in C++), so they can still be called from C. But internally we now take full advantage of the C++ language and its many useful features.

clisp has good IO, the others not so. Unfortunately clisp's compiler cannot compete with the better lisps.

Static C doesn't but you anything. Read massalin's SynthesisOS and see what you can get by reinterpreting logic dynamically. There's plenty of room at the bottom.

Seems like this is a misleading article, because..

1. You didn't actually beat C, as shown by your own measurements.

2. You move the goalposts to support your article.

This is not a good article.

The thing is if people beat c there is always some kind of 'but'. I'd never use c but it's speed isn't really being challenged, just approximated.

"It does help that wc is such a useless and trivial program that it doesn't rightly benefit from such interfaces only exposed to C which languages such as Common Lisp avoid out of good taste and a sense of proper design."

https://news.ycombinator.com/item?id=21490714 "It’s Not Enough to Be Right – You Also Have to Be Kind", 9 days ago.

Haha, I thought you were satirizing the C vs Lisp article... but no, it's a direct quote! Amazing.

The article on kindness was well worth reading, thank you. It ends

"If you can’t be kind, if you won’t empathize, then you’re not on the team. That team is Team Humanity, where we are all in this thing together. Where we are all flawed and imperfect. Where we treat other people’s point of view as charitably as we treat our own. Where we are civilized and respectful and, above all, kind to each other—particularly the less fortunate, the mistaken, and the afraid."

https://forge.medium.com/its-not-enough-to-be-right-you-also...

I've now modified the article to include measurements and also point out that the program does, in fact, seem to largely comply with POSIX behaviour, although it doesn't assume no number shall exceed six digits or other things POSIX permits.

Eh... neither does posix.

C is a low bar. If a new language doesn't beat C, it's not serious about performance.

Of course Lisp is the opposite of new, but it has had more time than any other to get itself together.

Reply on news.ycombinator.com