Beating C with Dyalog APL
Dyalog implementor here. The hot loops in this function are running my code!<p>I&#x27;m not surprised at all about this result, although I certainly wouldn&#x27;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.<p>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.<p>On that note, the function<p><pre><code>  words←{(~(¯1)↑⍵)++&#x2F;1=(1↓⍵)-(¯1)↓⍵}
</code></pre>
can be improved by keeping the data boolean. 1=(1↓⍵)-(¯1)↓⍵ is equivalent to the windowed reduction 2&lt;&#x2F;⍵ which identifies places where the boolean argument increased in value. We get:<p><pre><code>  words←{(~¯1↑⍵)++&#x2F;2&lt;&#x2F;⍵}
</code></pre>
Since this function doesn&#x27;t produce a 1-byte int result from subtraction, it&#x27;s many times faster. I discuss some similar functions to 2&lt;&#x2F; in a blog post at <a href="https:&#x2F;&#x2F;www.dyalog.com&#x2F;blog&#x2F;2018&#x2F;06&#x2F;expanding-bits-in-shrinking-time&#x2F;" rel="nofollow">https:&#x2F;&#x2F;www.dyalog.com&#x2F;blog&#x2F;2018&#x2F;06&#x2F;expanding-bits-in-shrink...</a>.<p>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&#x27;s hyperscan (<a href="https:&#x2F;&#x2F;github.com&#x2F;intel&#x2F;hyperscan" rel="nofollow">https:&#x2F;&#x2F;github.com&#x2F;intel&#x2F;hyperscan</a>). 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&#x27;t go through this specific algorithm but explained many of our new search techniques at last year&#x27;s user meeting: <a href="https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=paxIkKBzqBU" rel="nofollow">https:&#x2F;&#x2F;www.youtube.com&#x2F;watch?v=paxIkKBzqBU</a>.<p>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!