Avoid repeating the calculation, retain the results

[yakir12]

It would be really cool if the calculated result of some cell in an array was somehow saved for repeated access:

fun(x) = (sleep(1/3); 2x)
x = rand(3)
fun.(x) # this takes about 1 second
mx = mappedarray(fun, x); # this is ultra quick
for i in 1:3 # first iteration should take 1/3 seconds, the two subsequent iterations should be instantaneous 
    mx[1]
end # they're not, this loop takes about a second to complete

The rational behind this is that with normal arrays you pay computation time for the map for ALL the cells (while you really might not need all of them), but that's a one-time cost, repeated access is cheap. With mapped arrays you pay the calculation price only for the cells you need, winning, but if you need to access them repeatedly then this gain in time can be quickly lost.

Note that I think I can get this by using Memoize and @memoizeing the mapped function...

[timholy]

A calculation that takes 1/3 of a second to complete is not typical of how this package is used. Just curious, have you benchmarked this suggestion for general usage? I highly recommend doing so 😄.

[timholy]

(On modern CPUs the time to fetch from "stale" memory (not in L1 cache) is equivalent to hundreds of flops. Almost never worth caching anything unless it's a reeeally slow calculation.)

[yakir12]

Just curious, have you benchmarked this suggestion for general usage?

No, I just played around with it.

OK, so really, the only situation where a "senile" mappedarray (i.e. as they are now) would be less performant than a regular array is: if we access the same cell n+1 times, where n is the number of cells we haven't accessed yet. This assumes that the mapped function takes about the same time to run for all cells.

A calculation that takes 1/3 of a second to complete is not typical of how this package is used.

As I understand it (now), neither the function's speed nor the array's size affect the question of using mappedarrays versus regular ones.

[timholy]

Just want to make sure, you realize you can call map rather than mappedarray, right? That's the best way to "memoize" if you know you want that.

As I understand it (now), neither the function's speed nor the array's size affect the question of using mappedarrays versus regular ones.

Well, if you're accessing the majority of elements repeatedly and the calculation is slow, you're better off realizing it by just creating a new array the first time (map). Conversely, if you may only access a few values, then generally it's better to use mappedarray. If you end up using each one once, there should be little or no difference.

For example:

julia> using MappedArrays

julia> a = rand(10^6);

julia> m = mappedarray(sqrt, a);

julia> v = map(sqrt, a);

julia> using BenchmarkTools

julia> @btime sum($m)
  2.538 ms (0 allocations: 0 bytes)
666744.570730794

julia> @btime sum($v)
  416.189 μs (0 allocations: 0 bytes)
666744.570730794

julia> @btime map($sqrt, $a);
  2.583 ms (3 allocations: 7.63 MiB)

julia> @btime mappedarray($sqrt, $a);
  22.613 ns (1 allocation: 16 bytes)

You can see that sum(m) is expensive compared to sum(v), but the expense is equivalent to calculating v in the first place. If you needed that sum many times you should just calculate v (once). If you don't, then there seems little reason to allocate all that memory and do all those calculations ahead of time.

[yakir12]

Thank you for the explanation, I think I got it. But I still think my statement

the only situation where a "senile" mappedarray (i.e. as they are now) would be less performant than a regular array is: if we access the same cell n+1 times, where `n is the number of cells we haven't accessed yet.

and that

neither the function's speed nor the array's size affect the question of using mappedarrays versus regular ones.

holds. If we sum(m) more than once we access the cells we haven't accessed yet (=zero) length(m) (=10^6) additional times, which break the rule in my statement.

Background: I'm using OnlineStats to fit a distribution to each of the pixels in an image time lapse of a beetle walking in a dark scene. This will give me an estimate of the noise level in the background. I then use mappedarrays to convert each fitted distribution to a noise level (mean + 2*std). I don't have to know the noise level for each and every one of the pixels, just the ones I think the beetle might have crossed (I'm tracking the beetle). These are few n number. I probably need to revisit some pixels more than once. This lead me to think about the cost of rerunning the noise calculation. But I'm sure the number of times I need to access the same index is far far far lower than the number of pixels I don't check, so it's worth it.
Thank you for your time and this awesome package!

[timholy]

Thanks for the explanation. So you're in a situation where a few get accessed many times and the cost is relatively high. That's an important use case, but it's not really the bread and butter of the types in this package so far, which in practice get used mostly for fairly trivial calculations ( e.g., eltype changes, bringing 3 grayscale arrays into a single RGB array, etc). It's not possible to retain good performance for trivial calculations while also memoizing: you have to choose one or the other.

It may be worth your while to develop a type that's optimized for your situation, e.g.

struct MemoizedMappedArray{T,N,F,A<:AbstractArray} <: AbstractArray{T,N}
    f::F
    parentarray::A
    memoizedvals::OffsetArray{Union{T,Missing},N}
end

where memoizedvals would be initialized with missing and would trigger computation and storage of f(parentarray[i]). Such a type could comfortably fit in this package, and with a couple of hours of work you could create it largely by copy/paste from the existing types here. (This is not a complicated package, you'll have no trouble understanding it.)

[cstjean]

Note that I think I can get this by using Memoize and @memoizeing the mapped function...

I think this is the best solution. It's nicely modular.

[timholy]

It is, but Memoize uses a Dict. If you don't have storage for memoizedvals then of course it's much better to use a Dict; but if storage is trivial AND you have many accesses per previously-accessed element BUT only a minority of elements get accessed, then you'll get better performance from an array.

Of course, this is getting to be quite a niche case, so you're right that one would need to think carefully about whether it's worth it.

[cstjean]

Memoize in theory supports arbitrary AbstractDict for the dict, like

@memoize MyDict f(x) = x+2

and it would be straight-forward to do a vector-based AbstractDict. Unfortunately, it's broken, and the package is semi-abandonned. I'm trying to push for this functionality in Anamnesis.jl instead.

[yakir12]

I feel like I've convinced myself that neither the size of the array nor the speed of the function matter. It's just the number of repeated/extra times we access pre-accessed cells compared to the number of never-before accessed cells. If the former exceeds the latter than we aught to have used a regular array. This does not describe my current case. I'll keep benchmarking it, but I think that the modular solution @cstjean suggests with Anamnesis.jl will be dandy if and when it comes to play.