6 ms·

Beating C with Common Lisp

reikonomusha 7y ago
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.
- verisimilitudes 7y ago
  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.
  - reikonomusha 7y ago
    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.
  - threatofrain 7y ago
    That data is context for your claims, and we're missing it.
    - santoshalper 7y ago
      Sure, but he's not going to provide it because it either (a) doesn't exist or (b) doesn't support his argument.
  - fwip 7y ago
    POSIX specifications are available here: https://pubs.opengroup.org/onlinepubs/9699919799/idx/utilities.html https://pubs.opengroup.org/onlinepubs/9699919799/idx/utiliti...
    - saagarjha 7y ago
      TIL C99 is part of the POSIX standard…
      - fwip 7y ago
        Yeah, there's a number of surprising (but optional) inclusions. c99 is part of the "C-Language Development Utilities" optional group.
      - LukeShu 7y ago
        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.
- jshaqaw 7y ago
  Can I ask what you do in your day job that you get to write Common Lisp?
  - reikonomusha 7y ago
    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 https://github.com/rigetti/quilc [2] simulator https://github.com/rigetti/qvm https://github.com/rigetti/qvm
    - jshaqaw 7y ago
      Jealous!
- begriffs 7y ago
  Even supposing they beat the GNU wc, that's not too hard... try beating this one: https://github.com/begriffs/wc https://github.com/begriffs/wc I wrote it in reply to an earlier post, where someone "beat C" with Haskell.
  - eMSF 7y ago
    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).
  - aqrit 7y ago
    here you go: https://github.com/expr-fi/fastlwc https://github.com/expr-fi/fastlwc "Beating wc with C"
    - begriffs 7y ago
      That's awesome, thanks for sharing. :) There's always someone smarter...
  - fao_ 7y ago
    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
- igouy 7y ago
  > Benchmarks Game-style Once upon a time https://salsa.debian.org/benchmarksgame-team/archive-alioth-benchmarksgame/tree/master/contributed-source-code/shootout/wc https://salsa.debian.org/benchmarksgame-team/archive-alioth-... https://web.archive.org/web/20010616231931/http://www.bagley.org/~doug/shootout/bench/wordfreq/ https://web.archive.org/web/20010616231931/http://www.bagley...
- nwallin 7y ago
  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.
jstimpfle 7y ago
> 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.
kjgkjhfkjf 7y ago
There's very little technical substance to this article, and I found the tone of it peculiar and off-putting.
waynecochran 7y ago
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.
- pjmlp 7y ago
  Luckily not all OSes are written in C, mostly only those of UNIX/POSIX influence.
  - waynecochran 7y ago
    For example? https://www.toptal.com/c/after-all-these-years-the-world-is-still-powered-by-c-programming https://www.toptal.com/c/after-all-these-years-the-world-is-...
    - pjmlp 7y ago
      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-and-c99/ https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-an... https://docs.microsoft.com/en-us/cpp/build/reference/kernel-create-kernel-mode-binary?view=vs-2019 https://docs.microsoft.com/en-us/cpp/build/reference/kernel-... https://docs.microsoft.com/de-de/windows-hardware/drivers/gettingstarted/writing-a-very-small-kmdf--driver https://docs.microsoft.com/de-de/windows-hardware/drivers/ge... https://devblogs.microsoft.com/cppblog/the-great-c-runtime-crt-refactoring/ 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.
- rurban 7y ago
  clisp has good IO, the others not so. Unfortunately clisp's compiler cannot compete with the better lisps.
eloff 7y ago
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".
- reikonomusha 7y ago
  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.
timwaagh 7y ago
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.
eqvinox 7y ago
"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 https://news.ycombinator.com/item?id=21490714 "It’s Not Enough to Be Right – You Also Have to Be Kind", 9 days ago.
- yesenadam 7y 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-have-to-be-kind-b8814111fe1?gi=7b430aa08349 https://forge.medium.com/its-not-enough-to-be-right-you-also...
keithnz 7y ago
"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
verisimilitudes 7y ago
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.
- tedunangst 7y ago
  Eh... neither does posix.
ttul 7y ago
Writes poetry and serves coffee.
missblit 7y ago
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).
imode 7y ago
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.
ncmncm 7y ago
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.
EdwardDiego 7y ago
> 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.

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.

verisimilitudes 7y ago
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.
- reikonomusha 7y ago
  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.
- threatofrain 7y ago
  That data is context for your claims, and we're missing it.
  - santoshalper 7y ago
    Sure, but he's not going to provide it because it either (a) doesn't exist or (b) doesn't support his argument.
- fwip 7y ago
  POSIX specifications are available here: https://pubs.opengroup.org/onlinepubs/9699919799/idx/utilities.html https://pubs.opengroup.org/onlinepubs/9699919799/idx/utiliti...
  - saagarjha 7y ago
    TIL C99 is part of the POSIX standard…
    - fwip 7y ago
      Yeah, there's a number of surprising (but optional) inclusions. c99 is part of the "C-Language Development Utilities" optional group.
    - LukeShu 7y ago
      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.
jshaqaw 7y ago
Can I ask what you do in your day job that you get to write Common Lisp?
- reikonomusha 7y ago
  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 https://github.com/rigetti/quilc [2] simulator https://github.com/rigetti/qvm https://github.com/rigetti/qvm
  - jshaqaw 7y ago
    Jealous!
begriffs 7y ago
Even supposing they beat the GNU wc, that's not too hard... try beating this one: https://github.com/begriffs/wc https://github.com/begriffs/wc I wrote it in reply to an earlier post, where someone "beat C" with Haskell.
- eMSF 7y ago
  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).
- aqrit 7y ago
  here you go: https://github.com/expr-fi/fastlwc https://github.com/expr-fi/fastlwc "Beating wc with C"
  - begriffs 7y ago
    That's awesome, thanks for sharing. :) There's always someone smarter...
- fao_ 7y ago
  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
igouy 7y ago
> Benchmarks Game-style Once upon a time https://salsa.debian.org/benchmarksgame-team/archive-alioth-benchmarksgame/tree/master/contributed-source-code/shootout/wc https://salsa.debian.org/benchmarksgame-team/archive-alioth-... https://web.archive.org/web/20010616231931/http://www.bagley.org/~doug/shootout/bench/wordfreq/ https://web.archive.org/web/20010616231931/http://www.bagley...
nwallin 7y ago
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.

jstimpfle 7y ago

> 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.

kjgkjhfkjf 7y ago

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

waynecochran 7y ago

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.

pjmlp 7y ago
Luckily not all OSes are written in C, mostly only those of UNIX/POSIX influence.
- waynecochran 7y ago
  For example? https://www.toptal.com/c/after-all-these-years-the-world-is-still-powered-by-c-programming https://www.toptal.com/c/after-all-these-years-the-world-is-...
  - pjmlp 7y ago
    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-and-c99/ https://herbsutter.com/2012/05/03/reader-qa-what-about-vc-an... https://docs.microsoft.com/en-us/cpp/build/reference/kernel-create-kernel-mode-binary?view=vs-2019 https://docs.microsoft.com/en-us/cpp/build/reference/kernel-... https://docs.microsoft.com/de-de/windows-hardware/drivers/gettingstarted/writing-a-very-small-kmdf--driver https://docs.microsoft.com/de-de/windows-hardware/drivers/ge... https://devblogs.microsoft.com/cppblog/the-great-c-runtime-crt-refactoring/ 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.
rurban 7y ago
clisp has good IO, the others not so. Unfortunately clisp's compiler cannot compete with the better lisps.

eloff 7y ago

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".

reikonomusha 7y ago
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.

timwaagh 7y ago

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.

eqvinox 7y ago

"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 https://news.ycombinator.com/item?id=21490714 "It’s Not Enough to Be Right – You Also Have to Be Kind", 9 days ago.

yesenadam 7y 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-have-to-be-kind-b8814111fe1?gi=7b430aa08349 https://forge.medium.com/its-not-enough-to-be-right-you-also...

keithnz 7y ago

"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

verisimilitudes 7y ago

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.

tedunangst 7y ago
Eh... neither does posix.

ttul 7y ago

Writes poetry and serves coffee.

missblit 7y ago

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).

imode 7y ago

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.

ncmncm 7y ago

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.

EdwardDiego 7y ago

> 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.