10 ms·

Beating C with Dyalog APL

102 points by lelf 7y ago

imglorp 7y ago
Perhaps not a fair comparison until you account for the C library's string comparison behaviors. If your default is LANG=C.UTF-8, your wc may be a bunch slower than LANG=C. I think OSX is still using gnu wc, yes? Maybe the Dialog race should be repeated with this controlled for. https://old.reddit.com/r/programming/comments/1sxpgp/make_grep_50x_faster/ https://old.reddit.com/r/programming/comments/1sxpgp/make_gr... Edit. Still true in Linux today. $ LANG=C time -p wc /tmp/foo 2>&1 >/dev/null real 0.29 user 0.28 sys 0.01 $ LANG=C.UTF-8 time -p wc /tmp/foo 2>&1 >/dev/null real 0.86 user 0.86 sys 0.00
- saagarjha 7y ago
  It’s a FreeBSD derivative: https://opensource.apple.com/source/text_cmds/text_cmds-99/wc/wc.c.auto.html https://opensource.apple.com/source/text_cmds/text_cmds-99/w...
  - imglorp 7y ago
    Looks like they have the same problem. They're using LC_CTYPE to hint mbrtowc(). In fact, if you web search "mbrtowc slow" you'll get a bunch of hits about "Why is wc so slow"!! :-)
JamesT_Kirk 7y ago
1st comment. Ever. Yes, here in the 23rd century APL has returned to its righteous glory and C is just a few bytes of late 20th century IT(to use your language) history
tom_mellior 7y ago
> Just like Chris Penner’s original article, I’m comparing against the OSX version of wc that shipped with my machine. Just like in the original article, I admit that there are likely faster versions of wc–I’m just comparing what I got. Could someone on OSX post a benchmark of their system wc vs. one compiled manually from source using gcc or clang with -O3? Last time around I did this for Ubuntu and found a 2x difference: https://news.ycombinator.com/item?id=21271951 https://news.ycombinator.com/item?id=21271951 So if this article ends up beating their system wc by 2x, that might not say anything about "beating C".
cousin_it 7y ago
In the HN thread for the original article, geocar posted one line of q that does the job as well: https://news.ycombinator.com/item?id=21267923 https://news.ycombinator.com/item?id=21267923
- geocar 7y ago
  Beating benchmarks is always fun, but I think the ergonomics of the solution matter a great deal. That is to say the words we use matter: I'm excited that Haskell, and OCaml (and so on) have efficient solutions, but I'm extremely disappointed that the best implementations look nothing like the "obvious" approach. Maybe that's to be expected, after all an "obvious" implementation in C that pumps getchar() all day will be pretty slow, and experienced C programmers will do their own buffering and threading to win -- and that doesn't look like the "obvious" one either. And yet, in k/q the "obvious" implementation is the fast one. That's cool, and way more cool than you might realise as long as you think coding is hard.
- tluyben2 7y ago
  I think this shows off far more power than the Haskell version; a rather straightforward implementation which is faster than the original but not with the optimizing the author went through with the Haskell version. Readability wise this suffers (not everyone will recognize the cr lf space tab sequence and then it would be really hard to understand I would think) but I don't find it much more unreadable than the faster Haskell versions (you need a lot of prior knowledge to fluently read those as well) and at least the q version is built from primitives while with Haskell it needs quite a lot of libs to make it perform at all. I like Haskell (and more static typing in general) but I also like having 1, short, manual and being able to implement everything I want to implement without having to include many (unknown/potentially painful) libs but without writing 10000s of lines of code either.
person_of_color 7y ago
Wow this is a bizarre esolang.
- empath75 7y ago
  It’s not an esolang. It has a long history of actual real production use.
  - jheriko 7y ago
    that doesn't stop it being an esolang ... although the code quality of the examples makes it look a million times more like one than it needs to
    - coldtea 7y ago
      >that doesn't stop it being an esolang Actually it does: "An esoteric programming language (sometimes shortened to esolang) is a programming language designed to test the boundaries of computer programming language design, as a proof of concept, as software art, as a hacking interface to another language (particularly functional programming or procedural programming languages), or as a joke"
      - shaunxcode 7y ago
        Right, and APL could not be further from the definition given that it started as a chalkboard notation for reasoning about array operations!
        coldtea 7y ago
        Right, and Lisp started as a notation in a paper with no intention of building a language. But nobody would call it an esolanguage. How something started and what it became are orthogonal... I'm pretty sure Jack the Ripper started as a cute baby too...
        7y ago
jheriko 7y ago
but being faster than c is actually trivial and obvious even in the general case... here is something i crapped out 6 years ago to prove the point: https://github.com/semiessessi/CP1 https://github.com/semiessessi/CP1
- tom_mellior 7y ago
  --verbose please, before we breathlessly run out to install Visual Studio so we can run code we know nothing about?
breadandcrumbel 7y ago
Pretty sure the words function can be simplified to {⍴(~⍵∊⍺)⊆⍵} (and it also handles empty strings).
- olzd 7y ago
  How nice of you to copy/paste my reddit comment!
  - coldtea 7y ago
    Relevant comment parent mentions here: https://www.reddit.com/r/programming/comments/dku13a/beating_c_with_dyalog_apl_wc/ https://www.reddit.com/r/programming/comments/dku13a/beating...
ncmncm 7y ago
C is a low bar. It has always been slower than Fortran. It has been slower than C++ ever since reasonable optimization was implemented. Anything not faster than C, today, is a slow language, practically by definition.
- excursionist 7y ago
  Citations needed. As others have pointed out this is not a comparison of optimized Dyalog APL with C. This is a comparison of Dyalog APL with a pre-built command-line tool with unknown optimizations.
  - juliangoldsmith 7y ago
    Someone in the post on the Haskell version posted the source to the version of wc used [0], and it was a fairly naive implementation. 0: https://opensource.apple.com/source/text_cmds/text_cmds-68/wc/wc.c.auto.html https://opensource.apple.com/source/text_cmds/text_cmds-68/w...
- kabdib 7y ago
  > It has been slower than C++ ever since reasonable optimization was implemented. Which compilers? Which platforms? Optimized for speed or space (because "faster" is only one dimension of optimization)? Many C / C++ compiler implementations share the same front ends, back ends and runtime libraries, so it's hard to see how the code generation for C would be much different than that of C++. (In fact, C++ will be harder to optimize if features like exceptions and RTTI are used). Given the many different commercially and freely available toolchains, this statement is difficult to back up.
  - mumblemumble 7y ago
    For my part, I'm never interested in blanket comparisons of what language is faster, but it is worthwhile to mention specific features and how they impact performance. For example, in Python you can talk about the GIL and pointer chasing. But you can also talk about Cython. It turns out that, for me, Python's FFI is a really important factor, and a big reason why it's much easier for me to get good performance in Python than it is in Java: It makes it easy to interact with C libraries without taking a big hit on marshaling data in and out of Java's managed heap. (This is, incidentally, a major factor in Python having so thoroughly supplanted Java in the ML/BI/DS/analytics space.) But there are other situations where Java would be the clear winner. My favorite performance comparison between languages ever was the one that Raymond Chen and Rico Mariani did on implementing a practical program in C# and C++. [1] As it turns out that, at least as of 14 years ago, C++ is faster than C#, and C# is faster than C++, under different circumstances. You've really got to pay attention to which ones matter most to you before deciding where to place your bets, and just paying attention to rankings on The Computer Language Benchmarks Game is a sign that you've tried to jump to the answer without really taking enough time to understand the question. [1]: https://blogs.msdn.microsoft.com/ricom/2005/05/10/performance-quiz-6-chineseenglish-dictionary-reader/ https://blogs.msdn.microsoft.com/ricom/2005/05/10/performanc...
eggy 7y ago
I'm not heavily invested in speed benchmarks, but I am a big fan of APL/J/K, and I am always glad to see how others write code with them. I like that I can handwrite a J or APL solution, while thinking it through before getting to my phone or computer to actually test it. It's my version of doing a crossword puzzle or a math problem. I still love C too, since it was my third language after Basic on my Commodore PET, and machine language assembly on my VIC-20. The Programming the VIC book in 1984 cost me $24.95 at the time.
mlochbaum 7y ago
Dyalog implementor here. The hot loops in this function are running my code! I'm not surprised at all about this result, although I certainly wouldn't use it to make a pronouncement about Dyalog or C as a whole. But there are some places where interpreted array languages have a major advantage over typical compiled languages. One of the advantages seen in this wc function is our use of bit booleans rather than byte booleans. Packing 8 bits in a byte uses eight times less space, and can lead to drastic speed improvements: 2-8 times faster than even code which uses short ints. On that note, the function words←{(~(¯1)↑⍵)++/1=(1↓⍵)-(¯1)↓⍵} can be improved by keeping the data boolean. 1=(1↓⍵)-(¯1)↓⍵ is equivalent to the windowed reduction 2</⍵ which identifies places where the boolean argument increased in value. We get: words←{(~¯1↑⍵)++/2</⍵} Since this function doesn't produce a 1-byte int result from subtraction, it's many times faster. I discuss some similar functions to 2</ in a blog post at https://www.dyalog.com/blog/2018/06/expanding-bits-in-shrinking-time/ https://www.dyalog.com/blog/2018/06/expanding-bits-in-shrink.... Another big improvement is coming next year in Dyalog 18.0. The computations data∊nl data∊sp will use vectorised search methods similar to Intel's hyperscan (https://github.com/intel/hyperscan https://github.com/intel/hyperscan). The character lookups here are changed to be lookups from a 256-bit table, or two SSE registers, and searched using branchless SSSE3 instructions. I didn't go through this specific algorithm but explained many of our new search techniques at last year's user meeting: https://www.youtube.com/watch?v=paxIkKBzqBU https://www.youtube.com/watch?v=paxIkKBzqBU. By my measurements, each improvement (changing the word boundary computation and switching to the unreleased Dyalog 18.0) knocks of about a third from the total time. With both, this code is three times faster than it was before!
- mlochbaum 7y ago
  Some timings to show just how quickly Dyalog is improving, taken with the original function from OP and big.txt (https://github.com/ChrisPenner/wc/blob/master/data/big.txt https://github.com/ChrisPenner/wc/blob/master/data/big.txt) on a Kaby Lake i7. Dyalog releases about once a year, and 17.1 had almost no performance changes. 15.0: 93ms 16.0: 82ms 17.0: 7.4ms 17.1: 7.5ms 18.0: 5.3ms There's still more room for improvement: although arithmetic functions use AVX2 when available, functions based on SSSE3 shuffle don't yet. That includes Membership (∊) here, which takes the majority of the runtime in my improved version of wc and should be twice as fast with AVX2.

102 points by lelf 7y ago

Perhaps not a fair comparison until you account for the C library's string comparison behaviors. If your default is LANG=C.UTF-8, your wc may be a bunch slower than LANG=C. I think OSX is still using gnu wc, yes? Maybe the Dialog race should be repeated with this controlled for. https://old.reddit.com/r/programming/comments/1sxpgp/make_grep_50x_faster/ https://old.reddit.com/r/programming/comments/1sxpgp/make_gr... Edit. Still true in Linux today. $ LANG=C time -p wc /tmp/foo 2>&1 >/dev/null real 0.29 user 0.28 sys 0.01 $ LANG=C.UTF-8 time -p wc /tmp/foo 2>&1 >/dev/null real 0.86 user 0.86 sys 0.00

saagarjha 7y ago
It’s a FreeBSD derivative: https://opensource.apple.com/source/text_cmds/text_cmds-99/wc/wc.c.auto.html https://opensource.apple.com/source/text_cmds/text_cmds-99/w...
- imglorp 7y ago
  Looks like they have the same problem. They're using LC_CTYPE to hint mbrtowc(). In fact, if you web search "mbrtowc slow" you'll get a bunch of hits about "Why is wc so slow"!! :-)

JamesT_Kirk 7y ago

1st comment. Ever. Yes, here in the 23rd century APL has returned to its righteous glory and C is just a few bytes of late 20th century IT(to use your language) history

tom_mellior 7y ago

> Just like Chris Penner’s original article, I’m comparing against the OSX version of wc that shipped with my machine. Just like in the original article, I admit that there are likely faster versions of wc–I’m just comparing what I got. Could someone on OSX post a benchmark of their system wc vs. one compiled manually from source using gcc or clang with -O3? Last time around I did this for Ubuntu and found a 2x difference: https://news.ycombinator.com/item?id=21271951 https://news.ycombinator.com/item?id=21271951 So if this article ends up beating their system wc by 2x, that might not say anything about "beating C".

cousin_it 7y ago

In the HN thread for the original article, geocar posted one line of q that does the job as well: https://news.ycombinator.com/item?id=21267923 https://news.ycombinator.com/item?id=21267923

geocar 7y ago
Beating benchmarks is always fun, but I think the ergonomics of the solution matter a great deal. That is to say the words we use matter: I'm excited that Haskell, and OCaml (and so on) have efficient solutions, but I'm extremely disappointed that the best implementations look nothing like the "obvious" approach. Maybe that's to be expected, after all an "obvious" implementation in C that pumps getchar() all day will be pretty slow, and experienced C programmers will do their own buffering and threading to win -- and that doesn't look like the "obvious" one either. And yet, in k/q the "obvious" implementation is the fast one. That's cool, and way more cool than you might realise as long as you think coding is hard.
tluyben2 7y ago
I think this shows off far more power than the Haskell version; a rather straightforward implementation which is faster than the original but not with the optimizing the author went through with the Haskell version. Readability wise this suffers (not everyone will recognize the cr lf space tab sequence and then it would be really hard to understand I would think) but I don't find it much more unreadable than the faster Haskell versions (you need a lot of prior knowledge to fluently read those as well) and at least the q version is built from primitives while with Haskell it needs quite a lot of libs to make it perform at all. I like Haskell (and more static typing in general) but I also like having 1, short, manual and being able to implement everything I want to implement without having to include many (unknown/potentially painful) libs but without writing 10000s of lines of code either.

person_of_color 7y ago

Wow this is a bizarre esolang.

empath75 7y ago
It’s not an esolang. It has a long history of actual real production use.
- jheriko 7y ago
  that doesn't stop it being an esolang ... although the code quality of the examples makes it look a million times more like one than it needs to
  - coldtea 7y ago
    >that doesn't stop it being an esolang Actually it does: "An esoteric programming language (sometimes shortened to esolang) is a programming language designed to test the boundaries of computer programming language design, as a proof of concept, as software art, as a hacking interface to another language (particularly functional programming or procedural programming languages), or as a joke"
    - shaunxcode 7y ago
      Right, and APL could not be further from the definition given that it started as a chalkboard notation for reasoning about array operations!
      - coldtea 7y ago
        Right, and Lisp started as a notation in a paper with no intention of building a language. But nobody would call it an esolanguage. How something started and what it became are orthogonal... I'm pretty sure Jack the Ripper started as a cute baby too...
        7y ago

jheriko 7y ago

but being faster than c is actually trivial and obvious even in the general case... here is something i crapped out 6 years ago to prove the point: https://github.com/semiessessi/CP1 https://github.com/semiessessi/CP1

tom_mellior 7y ago
--verbose please, before we breathlessly run out to install Visual Studio so we can run code we know nothing about?

breadandcrumbel 7y ago

Pretty sure the words function can be simplified to {⍴(~⍵∊⍺)⊆⍵} (and it also handles empty strings).

olzd 7y ago
How nice of you to copy/paste my reddit comment!
- coldtea 7y ago
  Relevant comment parent mentions here: https://www.reddit.com/r/programming/comments/dku13a/beating_c_with_dyalog_apl_wc/ https://www.reddit.com/r/programming/comments/dku13a/beating...

ncmncm 7y ago

C is a low bar. It has always been slower than Fortran. It has been slower than C++ ever since reasonable optimization was implemented. Anything not faster than C, today, is a slow language, practically by definition.

excursionist 7y ago
Citations needed. As others have pointed out this is not a comparison of optimized Dyalog APL with C. This is a comparison of Dyalog APL with a pre-built command-line tool with unknown optimizations.
- juliangoldsmith 7y ago
  Someone in the post on the Haskell version posted the source to the version of wc used [0], and it was a fairly naive implementation. 0: https://opensource.apple.com/source/text_cmds/text_cmds-68/wc/wc.c.auto.html https://opensource.apple.com/source/text_cmds/text_cmds-68/w...
kabdib 7y ago
> It has been slower than C++ ever since reasonable optimization was implemented. Which compilers? Which platforms? Optimized for speed or space (because "faster" is only one dimension of optimization)? Many C / C++ compiler implementations share the same front ends, back ends and runtime libraries, so it's hard to see how the code generation for C would be much different than that of C++. (In fact, C++ will be harder to optimize if features like exceptions and RTTI are used). Given the many different commercially and freely available toolchains, this statement is difficult to back up.
- mumblemumble 7y ago
  For my part, I'm never interested in blanket comparisons of what language is faster, but it is worthwhile to mention specific features and how they impact performance. For example, in Python you can talk about the GIL and pointer chasing. But you can also talk about Cython. It turns out that, for me, Python's FFI is a really important factor, and a big reason why it's much easier for me to get good performance in Python than it is in Java: It makes it easy to interact with C libraries without taking a big hit on marshaling data in and out of Java's managed heap. (This is, incidentally, a major factor in Python having so thoroughly supplanted Java in the ML/BI/DS/analytics space.) But there are other situations where Java would be the clear winner. My favorite performance comparison between languages ever was the one that Raymond Chen and Rico Mariani did on implementing a practical program in C# and C++. [1] As it turns out that, at least as of 14 years ago, C++ is faster than C#, and C# is faster than C++, under different circumstances. You've really got to pay attention to which ones matter most to you before deciding where to place your bets, and just paying attention to rankings on The Computer Language Benchmarks Game is a sign that you've tried to jump to the answer without really taking enough time to understand the question. [1]: https://blogs.msdn.microsoft.com/ricom/2005/05/10/performance-quiz-6-chineseenglish-dictionary-reader/ https://blogs.msdn.microsoft.com/ricom/2005/05/10/performanc...

eggy 7y ago

I'm not heavily invested in speed benchmarks, but I am a big fan of APL/J/K, and I am always glad to see how others write code with them. I like that I can handwrite a J or APL solution, while thinking it through before getting to my phone or computer to actually test it. It's my version of doing a crossword puzzle or a math problem. I still love C too, since it was my third language after Basic on my Commodore PET, and machine language assembly on my VIC-20. The Programming the VIC book in 1984 cost me $24.95 at the time.

mlochbaum 7y ago

Dyalog implementor here. The hot loops in this function are running my code! I'm not surprised at all about this result, although I certainly wouldn't use it to make a pronouncement about Dyalog or C as a whole. But there are some places where interpreted array languages have a major advantage over typical compiled languages. One of the advantages seen in this wc function is our use of bit booleans rather than byte booleans. Packing 8 bits in a byte uses eight times less space, and can lead to drastic speed improvements: 2-8 times faster than even code which uses short ints. On that note, the function words←{(~(¯1)↑⍵)++/1=(1↓⍵)-(¯1)↓⍵} can be improved by keeping the data boolean. 1=(1↓⍵)-(¯1)↓⍵ is equivalent to the windowed reduction 2</⍵ which identifies places where the boolean argument increased in value. We get: words←{(~¯1↑⍵)++/2</⍵} Since this function doesn't produce a 1-byte int result from subtraction, it's many times faster. I discuss some similar functions to 2</ in a blog post at https://www.dyalog.com/blog/2018/06/expanding-bits-in-shrinking-time/ https://www.dyalog.com/blog/2018/06/expanding-bits-in-shrink.... Another big improvement is coming next year in Dyalog 18.0. The computations data∊nl data∊sp will use vectorised search methods similar to Intel's hyperscan (https://github.com/intel/hyperscan https://github.com/intel/hyperscan). The character lookups here are changed to be lookups from a 256-bit table, or two SSE registers, and searched using branchless SSSE3 instructions. I didn't go through this specific algorithm but explained many of our new search techniques at last year's user meeting: https://www.youtube.com/watch?v=paxIkKBzqBU https://www.youtube.com/watch?v=paxIkKBzqBU. By my measurements, each improvement (changing the word boundary computation and switching to the unreleased Dyalog 18.0) knocks of about a third from the total time. With both, this code is three times faster than it was before!

mlochbaum 7y ago
Some timings to show just how quickly Dyalog is improving, taken with the original function from OP and big.txt (https://github.com/ChrisPenner/wc/blob/master/data/big.txt https://github.com/ChrisPenner/wc/blob/master/data/big.txt) on a Kaby Lake i7. Dyalog releases about once a year, and 17.1 had almost no performance changes. 15.0: 93ms 16.0: 82ms 17.0: 7.4ms 17.1: 7.5ms 18.0: 5.3ms There's still more room for improvement: although arithmetic functions use AVX2 when available, functions based on SSSE3 shuffle don't yet. That includes Membership (∊) here, which takes the majority of the runtime in my improved version of wc and should be twice as fast with AVX2.