4 ms·

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 t

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.
jodrellblank 7y ago
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?
- mlochbaum 7y ago
  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 ⊣/⍋...
ummaycoc 7y ago
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.
- mlochbaum 7y ago
  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.
  - ummaycoc 7y ago
    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.
  - ummaycoc 7y ago
    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)</v` is basically `2</(n</v)` for `n>1` but I also see some things that don't exactly fit that pattern.
    - 7y ago

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.

jodrellblank 7y ago

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?

mlochbaum 7y ago
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 ⊣/⍋...

ummaycoc 7y ago

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.

mlochbaum 7y ago
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.
- ummaycoc 7y ago
  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.
- ummaycoc 7y ago
  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)</v` is basically `2</(n</v)` for `n>1` but I also see some things that don't exactly fit that pattern.
  - 7y ago