> "
I imagine that it takes a stupendously small amount of characters to do this."
You're right, but it's not just codegolf; ideally the few characters are a clean high level way to express intent - and that is in tension with caring how a machine executes the algorithm most quickly.
> "This is not an issue in the imperative/functional cases, because they don't have to generate the array in step 1, they can just loop/recurse/lazily generate the values (i.e. memory is O(1) for this)"
It kind of is the same problem, just pushed down a level or two; writing it casually in Python will not get you the fastest performance, you should be working in C or you're wasting a lot of potential running the Python layer, then care about how you can parallelize the computation or you're wasting 7/8ths of an 8-core processor, then caring how you can make best use of the CPU SIMD instructions or you're wasting another half or more of the machine potential, caring about branch predictors, and caches, etc. That a loop written in Python is "not wasteful" but materializing a large array "is wasteful" is where the industry draws a fairly arbitrary line. The ArrayCast podcast episode 52 touches on this[1], me cutting/editing some relevant parts from the transcript; [ML] is Marshall Lochbaum who did performance optimizing work on Dyalog APL and designs/implements the BQN array language, and [CH] is Conor Hoekstra who hosts the podcast and works in nVidia research:
> ML: "using linear memory is just how array languages work. For any problem, pretty much, you're going to have to make a bunch of new arrays."
> CH: "there could be an array language that avoids [materializing] arrays when possible."
> ML: "it's going very much against the grain of the language to say, "All right, I've specified my answer in these high-level array terms, and now I want you to turn it into a C program for me"."
> ML: "it's still nice to specify a problem this way, but this array form for specifying gives you some pretty big advantages. [...] if you try to pack that all into a big iteration, your algorithm is no longer expressed as an array operation - and these array operations are things that we know how to do really quickly. You are giving up some performance information if you tell it, well, yes, I'm in an array language, but don't actually make me any arrays."
> CH: "my dream is that I want to be able to write like the most expressive solutions to problems and then have [the array language implementation] do the most performant thing. Like for Kadane's [algorithm], for example, the most performant thing is to hand roll that reduction yourself. It's going to be faster than materialize."
> ML: "I'm not convinced of that"
> CH: [where I work we have to optimize for teams working on large problems, recently had a discussion where 2 billion items is a small number]
> ML: "2 billion /is/ a small number"
> ML: "what you can do, even when you have an array algorithm, you can split it into to smaller arrays. this is often a lot better because you get to use vector operations with these. So for Kadane's algorithm in particular, I don't know how to express that purely with vector operations, but I think there probably is a way. And in that case, if you write it in C style, where you interleave scan and reduction, then it's much harder to go from that to a vectorized algorithm which (if it exists) would almost definitely be the fastest way. The way you would get the array thing to be cache friendly is that you run it blocks. And then within a block, it's doing a bunch of vector operations, but what you really want is like, you know, working on two vector registers, say at a time. the array language doesn't automatically chunk, but it's not that hard"
> ML: "Yeah, and I think the way for the implementation to get the best [performance] - maybe not with this particular problem - but definitely for things that are friendlier to arrays where you don't have any compound functions inside scans. The way to optimize those is not to immediately break it down into a series of scalar operations, but instead to be more careful and start with your whole array stuff and break that as necessary, and maybe even compile these array operations into operations of individual registers, which is hard. Nobody's really done that, but coming from the other side, from C, there have been who knows how many man hours poured into work on auto vectorization. And it's still pretty terrible. It would have absolutely no chance of handling something like Kadane's algorithm."
> ML: "getting the best implementation of an idea is pretty difficult. But I think actually starting from an array representation, you do have a pretty good chance without going through a C style scalar representation first."
That's edited parts from a longer chat; but yes if you want to write X algorithm without wasting machine resources, that's a hard problem and takes a lot of low level C/SIMD/CPU skills and time. Array languages can vector-accelerate the primitives of array symbols much easier than C compilers can identify vector-accelerate arbitrary looping code.
You can read more interesting things about the implementing of BQN and comparing with co-dfns and performance here: https://mlochbaum.github.io/BQN/implementation/codfns.html
[1] https://www.arraycast.com/episode-52-transcript - around 00:39:21*