Lists are embarrassingly slow about numbat HOT 3 OPEN

First step in the right direction: #478

from numbat.

I looked into optimizing map for a bit.

Below is the code that we currently generate for a naive recursive implementation of map

fn map<A, B>(f: Fn[(A) -> B], xs: List<A>) -> List<B> =
  if is_empty(xs)
    then []
    else cons(f(head(xs)), map(f, tail(xs)))

This doesn't look too bad, but the GetLocal calls are extremely expensive, since we currently clone the full list. I tried experimenting with a Cow<'a, Deque<Value>> as a representation for lists which would only require copies if we actually modified the lists (not in Numbat, but in Rust). For example, for a function like f(xs) = is_empty(xs), we would not have to copy the list, just to pass it to is_empty. However, for most of the list functions, we call both head(xs) as well as tail(xs). Which means we still clone lists all over the place since these operations mutate the passed-in list. We would probably need support for pattern matching (case xs of x:rest -> …) in order to make this efficient, because then we would see the full split-into-head-and-tail operation all at once.

I also tried tried to implement map natively in Rust instead of Numbat (as a FFI function), but this is also not straightforward. We are being passed a function reference, and we can't do anything with it inside a FFI function. There currently no way of executing Numbat code from a FFI function.

Finally, I thought about compiling map calls into a loop. But it's not clear to me how this would be best achieved in a stack-based VM. We have three things to deal with: the input list xs, the function reference f, and a list of output elements that we collected so far (ys). Let's say we start by pushing the arguments to the stack:

[f] [xs]

We could then create an initially empty list for ys, and push it as well:

[f] [xs] [ys]

But now we would probably need some weird additional operation that:
(1) pops off all three elements, then pushes the following five elements back onto the stack:

[f] [tail(xs)] [ys] [head(xs)] [f]

(2) Next, we could call Op::Call/Op::CallCallable or something similar in order to get:

[f] [tail(xs)] [ys] [f(head(xs))]

(3) Finally, we would call a new Op::ListAppend operation which would result in:

[f] [tail(xs)] [ys:f(head(xs))]

Finally, we could loop back to (1) unless the input list is empty.

So it would something like this:

# Start with `f` and `xs` on the stack
000  BuildList 0    # Push empty list onto the stack
001  SpecialMapOp
002  CallCallable
003  ListAppend
004  <some test if we are finished>
005  JumpIfFalse 001

But somehow this doesn't feel very satisfactory to me (mostly due to that SpecialMapOp). If someone has experience with this or any additional ideas, please let me know.

from numbat.

If someone wants to work on this: I currently use

numbat -e 'sum(map(sqrt, range(0, 10000)))'

as a benchmark.

If we run perf on this (comment out strip = True in Cargo.toml to see proper stack traces) …

…we see that the majority of the runtime is spent cloning values/lists (and the second largest chunk is actually the destroying of lists):

This comes from GetLocal calls here:

from numbat.