Live data from Hacker News

Beating C with Dyalog APL

ummaycoc.github.io

21–30 of 57 posts

Re: Beating C with Dyalog APL

#21
post #10
post #6

Earlier quoted context omitted.

It’s not an esolang. It has a long history of actual real production use.

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

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

Re: Beating C with Dyalog APL

#22
post #13

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.

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.

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

Re: Beating C with Dyalog APL

#23

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

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.

Re: Beating C with Dyalog APL

#24
post #16
post #13

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.

> 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 harde…

The one area where C++ can be a lot faster than C is in places where C uses a function pointer where C++ uses a function template.

The standard example is sorting. Say you’re sorting an array of integers. Then, C’s sort has to (1) call the comparison function passed as an argument, whereas C++’s std::sort can inline the comparisons into a single instruction.

(1) if the source of the function passed in is visible from the compilation unit, I think the C standard allows the compiler to compile a specialized version of sort in the same way C++ can, but I’m not aware of any compiler that does that

Re: Beating C with Dyalog APL

#25
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
  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 2https://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). 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.

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!

Re: Beating C with Dyalog APL

#26
post #15
post #6

Earlier quoted context omitted.

It’s not an esolang. It has a long history of actual real production use.

Production use these days is more likely to be J, which you can actually type on a normal keyboard.

It is different to look at, but the editing modes let you type the APL characters without too much difficulty. I spent about 3 months doing a deep-dive into APL last year, it took about two weeks to become proficient typing it (already a touch typist, though). I still remember most of the character positions (the worst part for me was that I use Dvorak, so the visualized keymap is useless since most assume QWERTY layouts). I mostly used emacs, I think the default prefix character was `, but switched it to . . Typing iota: .i. Typing rho: .r.

Re: Beating C with Dyalog APL

#27

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 b…

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

Re: Beating C with Dyalog APL

#28
post #24
post #16

Earlier quoted context omitted.

> 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 harde…

The one area where C++ can be a lot faster than C is in places where C uses a function pointer where C++ uses a function template. The standard example is sorting. Say you’re sorting an array of integers. Then, C’s sort has to (1) call the comparison function passed as an argument, whereas C++’s std::sort can inline the comparisons into a single instruction. (1) if the source of the function passed in is visible from…

Right, inlines are hard to beat, and they are not part of the C standard (which is kind of mind boggling, I mean . . . honestly, what year is it?).

Still, the benefit of inlines diminishes as the size of the inlined functions increases (you start paying penalties for extra cache lines full of code, and the percentage of time in function call overhead gets small in a hurry).

The linker can get into the inlining game, too, by the way, if the win is sufficiently big. I have scars to prove it. :-)

Re: Beating C with Dyalog APL

#29
post #16

Earlier quoted context omitted.

> 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 harde…

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 Pyt…

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

Instead, we could pay attention to program measurements:

https://benchmarksgame-team.pages.debian.net/benchmarksgame/...

:and source code.

Re: Beating C with Dyalog APL

#30
post #21
post #10

Earlier quoted context omitted.

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

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

Right, and APL could not be further from the definition given that it started as a chalkboard notation for reasoning about array operations!
Post reply on HN