Beating C with Dyalog APL • Hacker News Board

Re: Beating C with Dyalog APL

#51

Post by kabdib » Thu, Oct 24, 2019, 9:47 PM UTC

colonwqbang wrote: post #40

kabdib wrote: post #28

Earlier quoted context omitted.

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

What do you mean by "inlines are not part of the C standard"? The standard talks about visible behaviour of programs, never the concrete implementation.

You're correct about C99. I cut my teeth on K&R; C99 has inline declarations.

Re: Beating C with Dyalog APL

#52

Post by ummaycoc » Fri, Oct 25, 2019, 1:05 AM 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…

Awesome. Would you mind if I add a version like this to the article and acknowledge you?

Also, will anyone from Dyalog be at Code Mesh?

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

I once rewrote a structured verilog compiler (when I was the sole full time employee at ChipScan.us); going from using bytes to store boolean values to packing the entire circuit's wire state into bits in a char* definitely helped a lot. Also marking that char* as restrict helped a lot, too :-)

Big wins are made of many small victories.

Re: Beating C with Dyalog APL

#53

Post by mlochbaum » Fri, Oct 25, 2019, 7:01 AM UTC

ummaycoc wrote: post #52

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…

Awesome. Would you mind if I add a version like this to the article and acknowledge you? Also, will anyone from Dyalog be at Code Mesh? > 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. I once rewrote a structured…

Go ahead. Incidentally boolean tricks like the windowed reduction are fairly common knowledge in the APL community, even though they're considered esoteric outside of it. It might be helpful to know that every function with boolean arguments and result which depends on both arguments has its own primitive (one of ∧∨⍲⍱≠). Once you know you're transforming pairs of booleans to booleans, you just have to figure out which one it is.

We're not sending anyone to Code Mesh. I hadn't heard of the conference, but given how close it is maybe we should apply in the future.

Re: Beating C with Dyalog APL

#54

Post by ummaycoc » Fri, Oct 25, 2019, 2:24 PM UTC

mlochbaum wrote: post #53

ummaycoc wrote: post #52

Earlier quoted context omitted.

Awesome. Would you mind if I add a version like this to the article and acknowledge you? Also, will anyone from Dyalog be at Code Mesh? > 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. I once rewrote a structured…

Go ahead. Incidentally boolean tricks like the windowed reduction are fairly common knowledge in the APL community, even though they're considered esoteric outside of it. It might be helpful to know that every function with boolean arguments and result which depends on both arguments has its own primitive (one of ∧∨⍲⍱ ≠). Once you know you're transforming pairs of booleans to booleans, you just have to figure out whi…

I definitely heard at least one mention of Dyalog APL there last year (not in a conversation I was in, I was literally walking past some others who were chatting).

I hope to see some of you there sometime in the future.

Re: Beating C with Dyalog APL

#55

Post by ummaycoc » Fri, Oct 25, 2019, 3:24 PM UTC

mlochbaum wrote: post #53

ummaycoc wrote: post #52

Earlier quoted context omitted.

Awesome. Would you mind if I add a version like this to the article and acknowledge you? Also, will anyone from Dyalog be at Code Mesh? > 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. I once rewrote a structured…

Go ahead. Incidentally boolean tricks like the windowed reduction are fairly common knowledge in the APL community, even though they're considered esoteric outside of it. It might be helpful to know that every function with boolean arguments and result which depends on both arguments has its own primitive (one of ∧∨⍲⍱ ≠). Once you know you're transforming pairs of booleans to booleans, you just have to figure out whi…

Do you have an explanation handle on the windowed reductions? Specifically what the number on the left means in this case (or in general)? I've tried it and it looks like `(n+1)1` but I also see some things that don't exactly fit that pattern.

Re: Beating C with Dyalog APL

#56

Post by mlochbaum » Fri, Oct 25, 2019, 4:59 PM UTC

ummaycoc wrote: post #55

mlochbaum wrote: post #53

Earlier quoted context omitted.

Go ahead. Incidentally boolean tricks like the windowed reduction are fairly common knowledge in the APL community, even though they're considered esoteric outside of it. It might be helpful to know that every function with boolean arguments and result which depends on both arguments has its own primitive (one of ∧∨⍲⍱ ≠). Once you know you're transforming pairs of booleans to booleans, you just have to figure out whi…

Do you have an explanation handle on the windowed reductions? Specifically what the number on the left means in this case (or in general)? I've tried it and it looks like `(n+1) 1` but I also see some things that don't exactly fit that pattern.

The left argument is a window length. Windowed reduction groups the argument into overlapping windows with that length and does a reduction on each one of them. So if y has row length n, (n ?/ y) is the same as (?/ y) but the rank isn't reduced by one (there's an extra 1 at the end of the shape). For a numeric vector you can use ,/ as a windowed reduction to see the subvectors that are reduced over, but for a nested vector that trick doesn't quite work because it messes up the nesting.

You can email me with my first name at the company site to talk more. There's also a chat room at https://chat.stackexchange.com/rooms/52405/the-apl-orchard which is good for asking questions.

Re: Beating C with Dyalog APL

#57

Post by jodrellblank » Sun, Oct 27, 2019, 9:08 AM UTC

mlochbaum wrote: post #50

jodrellblank wrote: post #43

Earlier quoted context omitted.

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

Thinking on this for a while, it makes more sense to spend optimization effort on a few widely useful engines which will improve many people's code in many situations, than on hundreds of narrow improvements which might improve some code in some situations and will add a lot more integration risk and maintenance overhead.

Turning +/iota into a constant time formula feels like a great idea APL is in a position to benefit from, and that mathematicians could see endless places where that kind of thing might be possible - but if that's true, APL users could find them when they need them. They can't find vectorised pick of grade up, ever.

This is so interesting, thank you.