mlochbaum

Which cases benefit and which don't seems potentially quite erratic. If you have a series of runs that shrink over the course of the array, with increasing start value and decreasing start value, each will become a new sorted list and you end up with O(n) insertion plus a perfect merge. If the runs get wider instead, they'll cross over existing endpoints and end up spattered around before merging.

It feels like the paper keeps trying to spin constant-factor improvements as somehow being asymptotically relevant despite acknowledging that mathematically they aren't, for example the fact that log(√n) is only log(n)/2 "would not reflect the sublinear nature of base array length k" and runs hitting the best case "approximately 50% of the time... reinforces JesseSort's average runtime complexity as somewhere between O(n) and O(n log_2 n)". Powersort provably takes O(n + n log r) worst-case time where r is the number of runs; I expect this algorithm is O(n log n) worst- and average-case.

However, on random arrays the given benchmarks do improve relative to Python default as the length increases, with faster performance starting a little under a million elements. There isn't a lot of investigation into why this is. I'd be interested to know if the number of comparisons is reduced in particular. Perhaps this algorithm is more cache-friendly with a random input, but this wouldn't be reliable as many inputs can cause the number of sorted lists to scale with O(n) so that the binary searches need to work on a large array.

Or since newlines in strings should be rare, maybe it works to save the index of every newline and tag it with the parity of preceding quotes in the block. Then you get the true parity once each thread's finished its block and filter with that, which is faster than going back over the block unless there were tons of newlines.

[0] https://queue.acm.org/detail.cfm?id=1531242

As an array implementer I've thought about the issue a lot and have been meaning to write a full page on it. For now I have some comments at https://mlochbaum.github.io/BQN/implementation/versusc.html#... and the last paragraph of https://mlochbaum.github.io/BQN/implementation/compile/intro....

See also https://beyondloom.com/blog/rankingoffruits.html for a nice introduction to the query syntax and its relation to K. (And RodgerTheGreat is John Earnest, the author).

(Everybody seems to assume "high performance" automatically means in whatever domain they work in. Impossible to interpret these sorts of questions. Try "Will BQN have high performance for ...?" instead.)

Email in my Github profile, feel free to contact me any time if you'd like to talk about algorithms!

32-bit radix sort: https://github.com/dzaima/CBQN/blob/v0.8.0/src/builtins/grad... plus https://github.com/dzaima/CBQN/blob/v0.8.0/src/builtins/radi...

I implemented this method in Dyalog 18.0 with BlockQuicksort-like partitioning, using vectorized comparison with bit-boolean output. It's faster than you'd expect, maybe twice as slow as regular binary search when searched values are in cache, and better once they fall out of L2. But Dyalog reverted to 17.1 for later versions so you won't see it in a new download. It'll probably make it into CBQN eventually, perhaps with radix partitioning. Note that both quicksort and radix partitioning can be done and undone in a cache-friendly way.

Unlike quicksort, there's no issue of pivot selection since you always choose the midpoint of the searched values. However, there's a complementary issue of memory if the partitions become unbalanced, because the larger partition can require saved memory of roughly the depth times the number of elements. With a bit per comparison it's bounded by the size of the input.

It does seem that I include all Chapman's scales (while saying nothing about chords), although oddly enough he's chosen to use the modes of harmonic major but not those of its inversion, harmonic minor?

Edit: In fact I found the second link (first one's pretty vague and wasn't enough for me to follow the diagram) relevant enough that I added a paragraph to point out the connection!

Without getting into any discussion of the array paradigm itself, the reason commercial programming is such a winner-take-all system now is hiring and organizational difficulties, not that popular languages are so much more productive than unpopular ones. Building a working application is the easy part of running a business.

I think it's an oversimplification to say SPMD is a better model full stop. Array programming has the advantage that the implementer optimizes a specific function, and its interaction with the rest of the program is much simpler: all the data is available at the start, and the result can be produced in any order. So things like multi-pass algorithms and temporary lookup tables are possible, particularly valuable if the program isn't spending that much time on arithmetic but rather "heavy" searching and sorting operations. Not that I claim NumPy or CuPy do a good job of this. Sections "Fusion versus fission" and "Dynamic versus static" are relevant here, I think: https://mlochbaum.github.io/BQN/implementation/versusc.html#...

APL: https://github.com/search?type=code&q=language%3AAPL

Q: https://github.com/search?type=code&q=language%3Aq

Implementation: https://aplwiki.com/wiki/List_of_open-source_array_languages

The compiler's whole state is a bunch of integer vectors, and •Show [a,b,c] prints some equal-length vectors as rows of a table, so I usually use that. The relevant code is usually a few consecutive lines, and the code is composed of very basic operations like boolean logic, reordering arrays with selection, prefix sum, and so on, so they're not hard to read if you're used to them. There are a few tricks, which almost all are repeated patterns (e.g. PN, "partitioned-none" is common enough to be defined as a function). And fortunately, the line prefaced with "Permutation to reverse each expression: more complicated than it looks" has never needed to be debugged.

Basically, when you commit to writing in an array style (you don't have to! It might be impossible!) you're taking an extreme stance in favor of visible and manipulable data. It's more work up front to design the layout of this data and figure out how to process it in the way you want, but easier to see what's happening as a result. People (who don't know APL, mostly) say "write only" but I haven't experienced it.

[0] https://github.com/mlochbaum/BQN/blob/master/src/c.bqn

[1] https://mlochbaum.github.io/BQN/implementation/codfns.html#i...

In the compiler, it's working with dense adjacency matrix representations, so this will be at best O(n^2) in whatever the relevant sort of node is (expressions? functions?). "at present is not optimized" seems a bit of an understatement here: I've never heard anything about these sorts of graph algorithms being possible with good asymptotics in an array style. In practice, I think any value of Co-dfns would be more in the fact that it emits GPU code than that it does it quickly, but this calls into question the value of writing it in APL, I would say (for what it's worth, I believe Co-dfns is still not able to compile itself).

The phrase "allocate all intermediate arrays" seems fairly confusing: what's actually being allocated must be space for the pointers to these arrays and other metadata, not the data of the array itself. As the data is variable-size, it can't be fully planned out at compile time, and I'm fairly sure the register allocation is done when there's not enough shape or type information to even make an attempt at data allocation. This change can only improve constant overhead for primitive calls, and won't be relevant to computations where most of the work is on large arrays. I think it's helpful for Co-dfns in a practical sense, but not too exciting as it only helps with bad cases: if this is important for a user then they'd probably end up with better performance by switching to a statically-typed language when it comes time to optimize.

It does mention that "For most small array values, we will use static allocation types, which prevents the need for allocating additional space for an array above and beyond its header.", so small arrays are taken care of by register allocation. Tradeoff there between being able to fit larger arrays in this space versus wasting space for values that don't use the full header.

Constant lifting within the compiler is pretty cool, I'll have to look into that.

conv looks like the hardest. s←1+(⍴⍵)-⍴⍺ is the result shape, number of subarrays with the length of ⍺ that will fit in ⍵ in each dimension. Looks like (⍳⍴⍺){s↑⍺↓⍵}¨⊂⍵ is missing the ¨; the inner function s↑⍺↓⍵ drops ⍺ elements (left argument) and then takes the first s, so it gets a length-s window of ⍵. This is called on each possible index into ⍺, together with the whole of ⍵, so it ends up getting all such windows. Presumably s is expected to be larger than ⍴⍺ so this is the more efficient way to slice things. ⊃+/,⍺× multiplies by ⍺ and sums, ravelling with , before applying +/ to collapse the dimensions and sum them all at once. Each element is an array of shape s, so summing them gives a result of shape s. There you go, multidimensional convolution!

This is a bit of a change-up from the usual "write-only language" complaint! But it does have the benefit of accuracy: yes, if you know the language, the time savings in writing APL are smaller than the savings in reading it. Both are faster, once you've spent a week or two with the keyboard, since even the slow method of typing a prefix character followed by a letter is faster than typing out a keyword in another language.

Array languages are rarely "product"s. While I do offer it to others for free, I make the language I want to use, and having nice-to-read symbols for a one-time tooling cost is a nice convenience for me. Don't call me thoughtless for having different tradeoffs than you!