Array that computes it's entries on the fly

lazyarrays.jl

# Lazy Array implementation. The explicit typing allows for static compilation leading to high performance.

using LinearAlgebra
using BenchmarkTools

# Quick implementation of a lazy Array. Yes, it's really *that* simple.
mutable struct LazyFunctionArray{F<:Function,T,N} <: AbstractArray{T,N}
    const f::F                   # Julia 1.8 const field syntax for convenience
    const size::NTuple{N,Int}
    ncalls::Int
end
const LazyFunctionVector{F,T} = LazyFunctionArray{F,T,1}
const LazyFunctionMatrix{F,T} = LazyFunctionArray{F,T,2}


function LazyFunctionArray(T::Type, f::F, dims::Vararg{Int,N}) where {F<:Function,N}
    LazyFunctionArray{F,T,N}(f, dims, 0)
end

function LazyFunctionArray(f::F, dims::Vararg{Int,N}) where {F<:Function,N}
    LazyFunctionArray(Float64, f, dims...)
end

function LazyFunctionVector(T::Type, f::F, n::Int) where {F<:Function}
    LazyFunctionVector{T,F}(f, (n,), 0)
end

function LazyFunctionVector(f::F, n::Int) where {F<:Function}
    LazyFunctionVector(Float64, f, n)
end

function LazyFunctionMatrix(T::Type, f::F, n::Int, m::Int) where {F<:Function}
    LazyFunctionMatrix{F,T}(f, (n, m), 0)
end

function LazyFunctionMatrix(f::F, n::Int, m::Int) where {F<:Function}
    LazyFunctionMatrix(Float64, f, n, m)
end

function Base.size(A::LazyFunctionArray)
    A.size
end

function Base.getindex(A::LazyFunctionArray{F,T,1,}, i::Int) where {F<:Function,T}
    A.ncalls += 1
    A.f(i)
end

function Base.getindex(A::LazyFunctionArray{F,T,N}, I::Vararg{Int,N}) where {F<:Function,T,N}
    A.ncalls += 1
    A.f(I...)
end


# Our way
function benchmark_la()
    A = LazyFunctionArray((x, y) -> x + y, 1000, 1000)
    m = Matrix(A)
    @benchmark m = Matrix($A)
end

# The functional way
function benchmark_map()
    @benchmark ($((x) -> x[1] + x[2])).($product(1:1000, 1:1000))
end

# The loop way
function benchmark_loop()
    @benchmark begin
        M = Matrix{Float64}(undef, 1000, 1000)
        for i in 1:1000
            for j in 1:1000
                @inbounds M[i, j] = i + j
            end
        end
    end
end

# ----------------------------------------------------------
# benchmark_la()
# BenchmarkTools.Trial: 2665 samples with 1 evaluation.
#  Range (min … max):  584.875 μs …   5.101 ms  ┊ GC (min … max):  0.00% … 58.17%
#  Time  (median):       1.615 ms               ┊ GC (median):     0.00%
#  Time  (mean ± σ):     1.874 ms ± 558.778 μs  ┊ GC (mean ± σ):  12.52% ± 17.06%

#                      ▇█▆▅▅▄▂▁▁▁▁              ▁▂▁ ▂▂▂▁▁▁ ▁      ▁
#   ▃▁▁▃▁▁▁▁▁▁▁▁▁▁▁▁▁▃▇████████████▇▅▁▃▁▁▁▁▁▃▁▁▅█████████████▇▆▅▅ █
#   585 μs        Histogram: log(frequency) by time       3.55 ms <

#  Memory estimate: 7.63 MiB, allocs estimate: 2.
# ----------------------------------------------------------
# benchmark_map()
# BenchmarkTools.Trial: 2125 samples with 1 evaluation.
#  Range (min … max):  1.953 ms …   4.701 ms  ┊ GC (min … max):  0.00% … 62.24%
#  Time  (median):     2.181 ms               ┊ GC (median):     0.00%
#  Time  (mean ± σ):   2.345 ms ± 382.035 μs  ┊ GC (mean ± σ):  27.09% ± 25.46%

#    ▁▁ ▄▇▇█▇▂▂                                                  
#   ▃██▇███████▇▆▆▅▄▄▅▄▃▃▃▃▃▁▂▃▂▃▃▃▄▃▃▃▃▃▃▃▂▃▃▃▄▃▄▃▃▃▂▃▃▃▃▃▁▃▂▂ ▄
#   1.95 ms         Histogram: frequency by time        3.49 ms <

#  Memory estimate: 22.89 MiB, allocs estimate: 4.
# ----------------------------------------------------------
# benchmark_loop()
# BenchmarkTools.Trial: 3720 samples with 1 evaluation.
#  Range (min … max):  867.417 μs …   4.482 ms  ┊ GC (min … max):  0.00% … 72.00%
#  Time  (median):       1.052 ms               ┊ GC (median):     0.00%
#  Time  (mean ± σ):     1.341 ms ± 657.444 μs  ┊ GC (mean ± σ):  21.05% ± 22.64%

#     ▅▇█▆▅▃▁▁                              ▂▁▁▁▁▂▂▂▂▁            ▁
#   ▄▇████████▇▇▆▆▄▃▁▃▃▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▃▆▆████████████▇▇▆▇▆▇▇▄▆▅ █
#   867 μs        Histogram: log(frequency) by time       3.32 ms <

#  Memory estimate: 7.63 MiB, allocs estimate: 2.
# ----------------------------------------------------------
# Julia Version 1.9.2
# Commit e4ee485e909 (2023-07-05 09:39 UTC)
# Platform Info:
#   OS: macOS (arm64-apple-darwin22.4.0)
#   CPU: 8 × Apple M1
#   WORD_SIZE: 64
#   LIBM: libopenlibm
#   LLVM: libLLVM-14.0.6 (ORCJIT, apple-m1)
#   Threads: 4 on 4 virtual cores
# Environment:
#   JULIA_EDITOR = code