mlochbaum

Performance-oriented library with no benchmarking instructions, fun. I get 850ms to shuffle 32-bit integers up to 1e8 with this library versus 400ms in BQN (•rand.Deal•_timed 1e8). However, BQN also has a large advantage at smaller sizes, such as 425us versus 120us for 1e5 elements, so a lot of this may be the random number generator. I haven't figured out how to get PCG working yet. BQN uses wyrand which is faster but I now know has quality issues (can't even generate every possible output; I need to update the page I linked...).

It's substantially the same algorithm so any differences would just be down to implementation details. Other than multi-threading which BQN doesn't do. The usage is also a little different as BQN generates shuffled integers directly; generating the integers is 100ms of the 850ms for rip_shuffle but I'm not sure whether it makes sense to subtract that or not.

I was able to make a variant of the higher-base version that runs in a single pass, by stopping when one partition fills up and using a different method for the remaining (asymptotically few) elements. I described the idea, which is based on another effort called MergeShuffle, here: https://mlochbaum.github.io/BQN/implementation/primitive/ran...

And it is better when N gets large. My implementation set the cutoff at 2^19 elements, although the effect isn't too big for a few more powers of two. Here's the main radix loop: https://github.com/dzaima/CBQN/blob/v0.7.0/src/builtins/sysf...

Functionality is, at this time, extremely limited (and the first kfun was out in January so I don't think there's really any intention to get this to usability on a short timeframe). No support for paired syntax like parentheses, functions in braces, and square brackets for indexing and function calls. No stranding or tacit functions. I doubt it's Turing complete. Many primitives are unimplemented and others are flaky: for instance calling count (#) on an atom can give an arbitrary number, print garbage, segfault, or allocate memory until it's killed. But it's got vector instruction support.

If you're looking for a practical k implementation, I recommend ngn/k, and several other implementations are listed at https://k.miraheze.org/wiki/Running_K .

Yes, when I took a look at shakti's database benchmarks before, they seemed entirely reasonable with typical array language implementation methods. I even compared shakti's sum-by benchmarks to BQN group followed by sum-each, which I'd expect to be much slower than a dedicated implementation, and it was around the same order of magnitude (like 3x slower or something) when accounting for multiple cores. I was surprised that something like Polars would do it so slowly, but that's what the h2o benchmark said... I guess they just don't have a dedicated sum-by implementation for each type. I think shakti may have less of an advantage with more complicated queries, and doing the easy stuff blazing fast is nice but they're probably only a small fraction of the typical database workload anyway.

In modern APLs a character scalar is just a Unicode code point, which you might consider UTF-32. It's no trouble to work with. Although interfacing with things like filenames that can be invalid UTF-8 is a bit of a mess; Dyalog encodes these using the character range that is reserved for UTF-16 surrogates and therefore unused. If you know you want to work with a byte sequence instead, you can use Unicode characters 0-255, and an array of these will be optimized to use one byte per character in dialects that care about performance.

There's a tutorial explaining BQN's combinators not directly linked: https://mlochbaum.github.io/BQN/tutorial/combinator.html

The symbols ⊸ and ⟜ are new in BQN and I think these are a good example of how APL's symbolic approach can make it easier to think about combinators. You have w F⊸G x meaning (F w) G x and w G⟜F x meaning w G (F x), that is, the function on the pointy side is a preprocessing step for the argument on that side. Once you get used to which side is which these become some of the most intuitive BQN combinators to work with.

It's much worse than that: based on measurements these use a loop that goes one set bit of the mask argument at a time. uops.info and so on measure a mask that's almost all zero so they vastly underreport. Worst case is in the hundreds of cycles. Do not use pdep/pext before Zen 3. https://twitter.com/uops_info/status/1202950247900684290

Language-specific web editors often do. I think Uiua (https://www.uiua.org/) is the state of the art here, with the minor issue that most of the symbols aren't used in any other language. Several APL-likes have language bars at the top, with names shown on hover.

- Dyalog APL: https://tryapl.org/

- Kap: https://kapdemo.dhsdevelopments.com/clientweb2/

- ngn/apl: https://abrudz.github.io/ngn-apl/web/

- BQN (my language): https://bqn.funmaker.moe/

I was inspired to write up a little section on Iverson's approach to naming (including his probable coinage of "bubble sort"): https://aplwiki.com/wiki/Ken_Iverson#Naming_things

The name "tacit" comes from the APL family as far as I know. It certainly fits with Iverson's style, as he was fond of seeking out just the right word to describe something regardless of obscurity ("ravel", "copula", etc.). I think the name would have come about after the development of function trains in 1988, and I found a paper "Tacit definition" about Iverson's J from 1991: https://dl.acm.org/doi/10.1145/114054.114077 (digitized at https://www.jsoftware.com/papers/TacitDefn.htm). Not knowing when "point-free" started to be applied to programming, I can't say which is first. I doubt J's developers were aware of "point-free" in any case.

For what it's worth, GNU APL is GNU because the developer chose to associate their project with GNU, not because there was any sort of effort by GNU as an organization to implement APL (see also [0]). It implements what I think is a pretty outdated APL (e.g. dynamic scoping everywhere, no control structures for loops), and I'd say there are better free options now, like Kap and April, and some others listed at [1].

[0] https://en.wikipedia.org/wiki/List_of_GNU_packages#What_it_m...

[1] https://aplwiki.com/wiki/List_of_open-source_array_languages

"Who uses APL in production?" is a common question. These days, it's mostly those who haven't stopped using it. The historical use, while never quite mainstream, might be surprising to those who never realized APL had a commercial presence at all!

- APL conferences were held every year from 1969 to 2004, minus '77 and '78 due to some unfortunate logistical issues (certainly not lack of demand). Conferences in the 80s regularly had >1000 in attendance despite both IPSA and STSC holding their own many years. My count (may not entirely rule out duplicates) is >1000 paper authors, and far more papers were submitted than accepted. https://aplwiki.com/wiki/APL_conference

- At least a dozen hardware manufacturers implemented an APL for their systems in the mainframe and minicomputer era (70s and 80s): https://aplwiki.com/wiki/Vendors

- Usage stats from just one university in 1978: 7,300 active accounts and 5,400 workspaces (which would each store an individual project, or something like that). Used for all sorts of administration and even a student ride sharing service. Today of course, much of this would be done in Excel. https://aplwiki.com/wiki/Syracuse_University

- The first serious e-mail system was implemented in APL in 1972, and used by Jimmy Carter in 1976 for his presidential campaign: https://forums.dyalog.com/viewtopic.php?f=30&t=1629

- I've heard but can't verify that one of the APL books (Gilman and Rose maybe) sold over 100,000 copies.

No, the k solution computes the unique elements and group independently. #:'=v[;1] uses group for the first column, and ?v[;1] uses unique for the second. (;) is list notation.

Your analysis of the algorithm you've described is also wrong: it would be O(n*log(n) + n^2), or O(n^2), because the second part loops over unique elements and not operations performed by unique.

In the random-access model, hash table construction/lookup is O(n) average case for n elements, if the elements have bounded size. More generally, it's linear in the total size of the input. If the strings are very long it can take a while to hash and compare them, but there's never a log(n) factor. Maybe you're confusing this with results from comparison sorting?

Both solutions are O(n) with the assumptions of random-access memory and bounded string size (or hash/comparison time), which I consider to be pretty standard.

Have continued using it as an artist and listener, and there's no way I'd have known anything changed from the site. They updated the terms of use, but only as necessary to reflect the change in ownership. And they are still doing Bandcamp Fridays, where the company gives up its cut on the first Friday each month, even though there was no promise or other indication they'd continue before the sale. I've seen rumors that support is getting worse, but only from reporters and not users, and it's a pretty easy site to use so I wouldn't think poor support is that much of a problem.

I'd rather Bandcamp be independent and am still upset they sold out, but I like Songtradr much better than Epic as an owner. Their main business is facilitating B2B sales, which I think of as the same category as what Bandcamp does. They don't own music (except incidentally, from acquisitions) and don't have ties to RIAA and major labels like Spotify does.

Main source for Songtradr info, although I've also done some outside reading: https://news.ycombinator.com/item?id=37699552

I say it's nonsensical (and yes, Ks are bytecode interpreted). https://mlochbaum.github.io/BQN/implementation/kclaims.html#...

As in, compiling for FPGAs or running on them? Can't really say anything about compiling-for. I know building Verilog takes forever but I have no idea what it's doing.

For running-on, APL adapts well to most hardware. I mean, we're talking about a paradigm that's existed longer without the concept of GPGPU than with it. I don't know if FPGAs would have an advantage over GPUs, since the bottleneck is often memory bandwidth and from a quick search it seems FPGAs are worse there. But the problem is still implementing compiler passes in APL.

There's a fundamental opposition between the functional programming approach to types and array programming principles, as I see it. In functional programming (particularly Haskell), types are used to make fine distinctions for safety. Even if an existing type would work for something, it's often recommended to make a new one so two different use cases don't get mixed up. But the APL family works to make as few type distinctions as possible: everything is an array, booleans are numbers, and some k features are to unify multi-dimensional arrays with nested ones and sort-of-unify (it's complicated) functions, dicts, and arrays.

The reason to do this is that it allows one function to do more things. As you guessed, the matmul function from the tutorial works if the right argument has rank 1 or more, which means it also does matrix-vector products. Less code is another form of safety, the theory goes. And handling more things with the same function also lets you draw higher-level connections.

Of course you can type the arrays anyway. Remora is one attempt. To me it feels like just a technical exercise and I think this question calls for more high-level investigation of what exactly the goals are before jumping into PL theory details.

EDIT: Tali Beynon's rainbow arrays don't have all the answers, but I think they're a good example of the sort of investigation I mean: https://math.tali.link/classical-array-algebra/

Which is exactly why I said you block the computation to stay at a low cache level. With SIMD loads and stores I don't think this matters quite as much as you suggest, even without blocking. It's pretty much only arithmetic that can saturate L1. I timed the BQN compiler on various files (some old version of itself, repeated). For 18K it runs at 21.4MB/s; for 1.7M, 16.5MB/s; for 17M, 12.0MB/s. So even when the source won't fit in L3 (mine's 8MB) the degradation is under a factor of 2 (and of course the compiler makes no consideration of cache, who writes a megabyte of BQN?).

I criticized the approach some in [0], after writing the BQN compiler in a similar style. Pioneering the array-based compiler paradigm is a major accomplishment, and if you did any programming with Aaron, you wouldn't question his ability. The Pareas compiler demonstrates that an APL-like language isn't required to do it though. And while the research may be applicable to other problems, I have serious doubts that it will be useful for speeding up optimizing compilers, which spend time on very different things than simple ones. Also possibly worth mentioning that Co-dfns still doesn't self-host, which I believe means it can't run on the GPU. I'm still unclear on what GPU program was timed in his thesis, a hand-translated version?

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

Complain about the language or documentation, but array language communities are absolutely friendly to outsiders! This tutorial lists some active forums, give them a try: https://github.com/razetime/ngn-k-tutorial/tree/main?tab=rea...

Also, have to shout out the APL Orchard, where Adám will give any visitor a personal tutorial: https://chat.stackexchange.com/rooms/52405/the-apl-orchard

Following this episode, I did find an AVX2 implementation of the maximum subarray sum that's about 25% faster than the sequential version, published here: https://gist.github.com/mlochbaum/b6e9701c6c1c617a2c2a4fb107...

Troels Henriksen (Futhark developer) pointed out to me that in expanding the state to make the scan associative I'd reinvented a fairly well-known method. The transformation from a specification as "maximum over the sums of each subarray" to the associative scan is very often used as an example of the power of the Bird-Meertens formalism or Squiggol[0], and some newer papers have demonstrated that it can be derived automatically, although not very quickly. Troels also wrote a simpler ISPC[1] implementation[2] that tested slower than C on an older CPU and faster on a newer one. Then I translated that to BQN and found it was about 4x slower than sequential C.

[0] https://en.wikipedia.org/wiki/Bird%E2%80%93Meertens_formalis...

[1] https://ispc.github.io/index.html

[2] https://gist.github.com/athas/f016084ea749602476b96c05ae415a...

Previous discussion: https://news.ycombinator.com/item?id=31377262

Yes, you waste a lot of memory. Memory's cheap. If you need to, you can do the computation in blocks. Well, it's pretty rare to actually run out of memory but blocking is useful for staying at a lower cache level.

Scalar languages have a different problem: the default is to process one value at a time, which wastes the potential parallelism that array languages take advantage of with SIMD algorithms. Because this is the status quo, it's not as easy to see this as a big concern. And the solution is also blocking. That is, the best algorithm for SIMD-friendly stuff is generally a blocked array method.

In practice, whether an array language is good or not really depends on the specific problem. Of course, for most practical uses performance doesn't matter at all; I believe k's reputation mostly comes from kdb being fast as a database rather than k implementations being fast languages. But array languages can be surprisingly fast just by focusing on elegant array algorithms rather than machine-specific considerations. I have comments and benchmarks comparing with C here:

https://mlochbaum.github.io/BQN/implementation/versusc.html

In the BQN compiler I'd write (⊂¯1++⍀m)⌷(m←c=LF)⌿ as the equivalent of (⊂⌈⍀m×⍳≢m←c=LF)⌷ using the function IT (indices-times but it also includes the ⌈⍀). Although I'm not sure it's inherently faster. Most of the cost is in selection, and there's an algorithm taking a shuffle of a sliding window from the right argument that would work better with the denser indices. And those indices have a smaller type which may be useful. The annoying thing is that this whole set-and-hold operation could be implemented in SIMD directly and none of those complications would apply. But it's pretty hard to expose in a nice way without just providing a builtin.

Yeah, about fifteen minutes for lines 15 to 21. Which includes getting used to this n-(⊂¯1++⍀m)⌷(m←c=LF)⌿n←+⍀ pattern for sum-within-lines that appears everywhere. Pretty sure the k=¯1 checks do nothing (planning ahead for a future feature?) and I think it breaks if there's a quote character in a comment. But, like... line 19 sets k to ¯2 where there are whitespace characters that come before any non-whitespace character on the line other than - ? or : followed by whitespace? I don't know YAML well and I have no idea how this fits in. So it's hard to remember what ¯2 means as I read later code.

I don't put a lot of stock in the "write-only" accusation. I think it's mostly used by those who don't know APL because, first, it's clever, and second, they can't read the code. If I remember I implemented something in J 10 years ago, I will definitely dig out the code because that's the fastest way by far for me to re-learn how it works.

This project specifically looks to be done in a flat array style similar to Co-dfns[0]. It's not a very common way to use APL. However, I've maintained an array-based compiler [1] for several years, and don't find that reading is a particular difficulty. Debugging is significantly easier than a scalar compiler, because the computation works on arrays drawn from the entire source code, and it's easy to inspect these and figure out what doesn't match expectations. I wrote most of [2] using a more traditional compiler architecture and it's easier to write and extend but feels about the same for reading and small tweaks. See also my review [3] of the denser compiler and Co-dfns.

As for being read by others, short snippets are definitely fine. Taking some from the last week or so in the APL Farm, {⍵÷⍨+/|-/¯9 ¯11+.○?2⍵2⍴0} and {(⍸⍣¯1+\⎕IO,⍺)⊂[⎕IO]⍵} seemed to be easily understood. Forum links at [4]; the APL Orchard is viewable without signup and tends to have a lot of code discussion. There are APL codebases with many programmers, but they tend to be very verbose with long names. Something like the YAML parser here with no comments and single-letter names would be hard to get into. I can recognize, say, that c⌿¨⍨←(∨⍀∧∨⍀U⊖)∘(~⊢∊LF⍪WS⍨)¨c trims leading and trailing whitespace from each string in a few seconds, but in other places there are a lot of magic numbers so I get the "what" but not the "why". Eh, as I look over it things are starting to make sense, could probably get through this in an hour or so. But a lot of APLers don't have experience with the patterns used here.

[0] https://github.com/Co-dfns/Co-dfns

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

[2] https://github.com/mlochbaum/Singeli/blob/master/singeli.bqn

[3] https://mlochbaum.github.io/BQN/implementation/codfns.html

[4] https://aplwiki.com/wiki/Chat_rooms_and_forums

Hey, even Dijkstra agrees with us on this one:

> I remember how much more pleasant the predicate calculus became to work with after we had decided to give con- and disjunction the same binding power and thus to consider p ∧ q ∨ r an ill-formed formula.

https://www.cs.utexas.edu/users/EWD/ewd13xx/EWD1300.PDF (page 4-5)

Here are my two cents on array compilation. I think a lot of the research goes in the direction of immediately fixing types and breaking array operations into scalar components because it's easy to compile, but this ignores some advantages of dynamic typing and immutable arrays. When you can implement most operations with SIMD, a smaller type always means faster code, so dynamic types with overflow checking can be very powerful on code that deals with a lot of small integers.

https://mlochbaum.github.io/BQN/implementation/compile/intro...

I'm somewhat skeptical of the virtual optimizations on indices, "beating" and similar. They sound nice because you get to eliminate some operations completely! But if you end up with non-contiguous indices then you'll pay for it later when you can't do vector loads. Slicing seems fine and is implemented in J and BQN. Virtual subarrays, reverse, and so on could be okay, I don't know. I'm pretty sure virtual transpose is a bad idea and wrote about it here:

https://mlochbaum.github.io/BQN/implementation/primitive/tra...

I believe this is the original publication, 1982: https://dl.acm.org/doi/10.1145/947955.1083808

Bidirectional isn't benchmarked here, and only mentioned once offhand:

> For example, we could already start searching for elements at the slot with expected (average) displacement from their perfect slot and probe bidirectional from there. In practice, this is not very efficient due to high branch misprediction rates and/or unfriendly access pattern.

I think this indicates a regular Robin Hood insertion and modified search, which doesn't sound that similar to Amble and Knuth's method. And anyway the relative costs of mispredictions and cache misses vary wildly based on workflow (paper studies 8-byte keys only). The paper also doesn't present Robin Hood as a clear winner, which is how I interpreted your comment. It's shown as one of five suggestions in the decision graph at the end, and only recommended for load factors between 50% and 80% among other conditions.

Edit: And the paper is from 2015, not the last five years. Is this the right link?