Beating C with Dyalog APL • Hacker News Board

Re: Beating C with Dyalog APL

#41

Post by lispm » Thu, Oct 24, 2019, 8:39 PM UTC

kragen wrote: post #35

lispm wrote: post #33

Earlier quoted context omitted.

> Lisp started as a notation in a paper with no intention of building a language what?

Well, it has some element of truth. The S-expression notation we think of as “Lisp” originated as a contribution to recursive function theory rather than a practical programming language, even if earlier McCarthy was thinking of proceeding by adding IPL-V facilities to Fortran.

McCarthy wanted a list processing language. He added list processing functions (which then later appeared in Lisp) to Fortran. He and his team then went on to develop and implement a new language: Lisp. The implementation ALWAYS was based on lists and s-expressions.

The paper http://www-formal.stanford.edu/jmc/recursive.html was published, when Lisp was already implemented, to present some ideas to a different audience. But Lisp already existed by then as a running programming language.

First and foremost Lisp was a real programming language implemented on a real computer.

http://www.softwarepreservation.org/projects/LISP/lisp15_fam...

See also: History of Lisp, John McCarthy, http://jmc.stanford.edu/articles/lisp/lisp.pdf

"My desire for an algebraic list processing language for artificial intelligence work on the IBM 704 computer arose in the summer of 1956..."

"The implementation of LISP began in Fall 1958 ... These included programs to read and print list structure. I can’t now remember whether the decision to use parenthesized list notation as the external form of LISP data was made then or whether it had already been used in discussing the paper differentiation program."

"The M-notation also used brackets instead of parentheses to enclose the arguments of functions in order to reserve parentheses for list-structure constants. It was intended to compile from some approximation to the M-notation, but the M-notation was never fully defined, because representing LISP functions by LISP lists became the dominant programming language when the interpreter later became available."

"Anyway, I decided to write a paper describing LISP both as a programming language and as a formalism for doing recursive function theory. The paper was Recursive functions of symbolic ex- pressions and their computation by machine, part I (McCarthy 1960)."

Re: Beating C with Dyalog APL

#42

Post by saagarjha » Thu, Oct 24, 2019, 8:43 PM UTC

imglorp wrote: post #7

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_gr... Edit. Still true in Linux today. $ LANG=C time -p wc /tmp/foo 2>&1 >/dev/nul…

It’s a FreeBSD derivative: https://opensource.apple.com/source/text_cmds/text_cmds-99/w...

Re: Beating C with Dyalog APL

#43

Post by jodrellblank » Thu, Oct 24, 2019, 9:03 PM UTC

mlochbaum wrote: post #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 b…

I really liked your sub-nanosecond searching talk, for my taste it felt like a great blend of explaining exactly what you do at the low levels, without dragging me through the weeds of exactly what you do at the low levels. A great piece of optimization.

On the subject of Dyalog APL performance, one of your other talks about a proposal for thunking / lazy execution, IIRC there was a slide of "all high level patterns the interpreter recognises and special-cases", and I was surprised how few there are. About a dozen, or so.

Given how often people voice that "there's potential for an APL interpreter to recognise this slow prime number generator and special-case it", I assumed a lot of the work of speeding up an APL interpreter would be years of building up a vast array of special case pattern handlers, and that doesn't seem to be the case. Is it much harder than it seems? Do the same code patterns not come up often enough to bother with?

Re: Beating C with Dyalog APL

#44

Post by imglorp » Thu, Oct 24, 2019, 9:03 PM UTC

saagarjha wrote: post #42

imglorp wrote: post #7

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_gr... Edit. Still true in Linux today. $ LANG=C time -p wc /tmp/foo 2>&1 >/dev/nul…

It’s a FreeBSD derivative: https://opensource.apple.com/source/text_cmds/text_cmds-99/w...

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"!! :-)

Re: Beating C with Dyalog APL

#45

Post by kragen » Thu, Oct 24, 2019, 9:08 PM UTC

lispm wrote: post #41

kragen wrote: post #35

Earlier quoted context omitted.

Well, it has some element of truth. The S-expression notation we think of as “Lisp” originated as a contribution to recursive function theory rather than a practical programming language, even if earlier McCarthy was thinking of proceeding by adding IPL-V facilities to Fortran.

McCarthy wanted a list processing language. He added list processing functions (which then later appeared in Lisp) to Fortran. He and his team then went on to develop and implement a new language: Lisp. The implementation ALWAYS was based on lists and s-expressions. The paper http://www-formal.stanford.edu/jmc/recursive.html was published, when Lisp was already implemented, to present some ideas to a different audien…

Right, that's exactly what I mean. Thank you for a adding all these great references to primary sources! Has CBI or somebody done an oral history interview with Slug Russell yet covering this time period? He's not dead yet. There's still time.

Re: Beating C with Dyalog APL

#46

Post by Someone » Thu, Oct 24, 2019, 9:10 PM UTC

colonwqbang wrote: post #39

Someone wrote: post #24

Earlier quoted context omitted.

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…

A C compiler can certainly also inline functions, as long as the definition is visible. Neither is there any guarantee that all C++ template instantiations will be inlined.

That’s true, and C compilers do so for short functions such as memset and strcpy (and doesn’t even need the definition to be visible), but historically, they haven’t for longer functions, and, I guess, many programmers wouldn’t like it if, say, they generated ten specialized copies of sort, speeding up those calls, but also blowing up executable size.

On the contrary, C++ programmers historically expect all templated code to be specialized. It’s only relatively recently that C++ linkers started to merge copies of template expansions.

Re: Beating C with Dyalog APL

#47

Post by lispm » Thu, Oct 24, 2019, 9:11 PM UTC

kragen wrote: post #45

lispm wrote: post #41

Earlier quoted context omitted.

McCarthy wanted a list processing language. He added list processing functions (which then later appeared in Lisp) to Fortran. He and his team then went on to develop and implement a new language: Lisp. The implementation ALWAYS was based on lists and s-expressions. The paper http://www-formal.stanford.edu/jmc/recursive.html was published, when Lisp was already implemented, to present some ideas to a different audien…

Right, that's exactly what I mean. Thank you for a adding all these great references to primary sources! Has CBI or somebody done an oral history interview with Slug Russell yet covering this time period? He's not dead yet. There's still time.

Just that the s-expression notation did not originate as contribution to recursive function theory, but was actually originating from designing and implementing a programming language and system for list processing.

Re: Beating C with Dyalog APL

#48

Post by kragen » Thu, Oct 24, 2019, 9:27 PM UTC

lispm wrote: post #47

kragen wrote: post #45

Earlier quoted context omitted.

Right, that's exactly what I mean. Thank you for a adding all these great references to primary sources! Has CBI or somebody done an oral history interview with Slug Russell yet covering this time period? He's not dead yet. There's still time.

Just that the s-expression notation did not originate as contribution to recursive function theory, but was actually originating from designing and implementing a programming language and system for list processing.

I think your reading of these sources differs from mine, then, but the important thing is that now anyone who is interested can peruse them at their leisure and make up their own mind.

Re: Beating C with Dyalog APL

#49

Post by RodgerTheGreat » Thu, Oct 24, 2019, 9:44 PM UTC

lispm wrote: post #41

kragen wrote: post #35

Earlier quoted context omitted.

Well, it has some element of truth. The S-expression notation we think of as “Lisp” originated as a contribution to recursive function theory rather than a practical programming language, even if earlier McCarthy was thinking of proceeding by adding IPL-V facilities to Fortran.

McCarthy wanted a list processing language. He added list processing functions (which then later appeared in Lisp) to Fortran. He and his team then went on to develop and implement a new language: Lisp. The implementation ALWAYS was based on lists and s-expressions. The paper http://www-formal.stanford.edu/jmc/recursive.html was published, when Lisp was already implemented, to present some ideas to a different audien…

An amusing coda to the M-notation story is that many extant examples of it closely resemble or are valid K/Q syntax.

Re: Beating C with Dyalog APL

#50

Post by mlochbaum » Thu, Oct 24, 2019, 9:45 PM UTC

jodrellblank wrote: post #43

mlochbaum wrote: post #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 b…

I really liked your sub-nanosecond searching talk, for my taste it felt like a great blend of explaining exactly what you do at the low levels, without dragging me through the weeds of exactly what you do at the low levels. A great piece of optimization. On the subject of Dyalog APL performance, one of your other talks about a proposal for thunking / lazy execution, IIRC there was a slide of "all high level patterns…

Just having a well-chosen and fast set of primitives goes a long way. If you write a three-primitive combination and the interpreter doesn't recognise it but all three primitives are fast, how bad is it, really? You're losing a factor of three at worst (which is still in faster-than-C territory much of the time), and probably more like 1.5 or 2 since the special combination would be more complicated. Sometimes you actually gain by splitting an algorithm into multiple passes: I remember an instance where I hand-wrote some nice branchless AVX2 code to find the index of the minimum of a numeric vector (it's (⊃⍋) but don't expect that to be fast yet). Then I wrote a better vectorised minimum and tried out (x⍳⌊/x), which just gets the overall minimum and searches the vector for it. Worst case that algorithm was 25% slower. In the best case, when the minimum was near the end and it could stop early, it was twice as fast!

That said, we still do a lot of work on recognising patterns. The list of idioms from my presentations are patterns that are recognised as a sequence of tokens in parsing, but we can also recognise particular derived functions (the results of operators, or function trains). An obvious example is the sum +/ and there are some pretty complicated ones involving Rank or Key. There are probably about a hundred cases like this in total although many of these cases handle several different combinations. Much of what I do is not to try to identify more special cases to handle with a custom algorithm but to make the algorithms more general and to use them in more places. I tend to develop engines (say, a column permuter using vector shuffles) and then write a bunch of code to recognise when I can use the engines for particular cases within a primitive or combination (indexing, reverse, rotate, take/drop, and transpose on trailing axes).

The most important work is on short patterns because the longer ones just don't show up often enough, or they show up in too many different permutations. Thunks are a way to recognise short patterns flexibly: it doesn't depend on the way the pattern is written, just the functions used. They also offer flexibility in that different operations can sometimes emit the same thunk with a parameter, allowing other functions to just handle that type of thunk as a whole. We've run into some trouble with our internal architecture that's holding thunks up (should be cleared up by the 18.0 release so we can start implementing them for 19.0), but I think recognising special combinations will be very different, and much easier, once they're working. And I can finally get the aforementioned (⊃⍋) running fast. And 1↑⍋. And ⊣/⍋...