# Cache Data Structure for Lazy Array
**URL:** https://discourse.julialang.org/t/cache-data-structure-for-lazy-array/102388
**Category:** Performance
**Tags:** data\_structures
**Created:** [August 2, 2023, 10:12am UTC](https://discourse.julialang.org/t/cache-data-structure-for-lazy-array/102388 "2023-08-02T10:12:01Z")
**Posts on this page:** 6
**Page:** 1
### Author:  [@AlexanderNenninger](https://discourse.julialang.org/u/AlexanderNenninger)
#### Post date: [August 2, 2023, 10:12am UTC](https://discourse.julialang.org/t/cache-data-structure-for-lazy-array/102388/1 "2023-08-02T10:12:01Z")
I’ve got an implementation of a lazy array ([lazyarrays.jl · GitHub](https://gist.github.com/AlexanderNenninger/461f37315e45071a8c91b18d73901431)), the entries of which are computed on the fly by function calls. From what we can tell it’s already quite fast. Although many algorithms do access the same entries of the array multiple times, leading to unnecessary calculations.
What could be good data structures, that are already implemented in Julia, to cache the evaluation results? Ideally they would be sparse to allow for larger-than-memory arrays.
I think criteria would be
- fast membership test with keys of primitive type (tuples of ints)
- fast lookup
- fast insertion
Elements do not need to be deleted and are immutable. We also control the key set, obviously.
---
### Author:  [@stevengj](https://discourse.julialang.org/u/stevengj)
#### Post date: [August 2, 2023, 11:51am UTC](https://discourse.julialang.org/t/cache-data-structure-for-lazy-array/102388/2 "2023-08-02T11:51:34Z")
People typically use `Dict` for this sort of thing, e.g. in [Memoize.jl](https://github.com/JuliaCollections/Memoize.jl). You can define a [custom key type with an optimized `hash` function](https://discourse.julialang.org/t/poor-time-performance-on-dict/9656/14) to speed things up if you know more about your keys.
---
### Author:  [@aplavin](https://discourse.julialang.org/u/aplavin)
#### Post date: [August 4, 2023, 5:37am UTC](https://discourse.julialang.org/t/cache-data-structure-for-lazy-array/102388/3 "2023-08-04T05:37:36Z")
> [@AlexanderNenninger](#):
>
> I’ve got an implementation of a lazy array ([lazyarrays.jl · GitHub](https://gist.github.com/AlexanderNenninger/461f37315e45071a8c91b18d73901431)), the entries of which are computed on the fly by function calls. From what we can tell it’s already quite fast.
Just in case, are you aware of existing packages implementing this functionality?
For example, `mapview()` from `FlexiMaps` — like `map()` but lazy:
```julia
julia> @btime Matrix(LazyFunctionArray((x, y) -> x + y, 1000, 1000));
1.003 ms (3 allocations: 7.63 MiB)
julia> using FlexiMaps
julia> @btime Matrix(mapview(I -> I[1] + I[2], CartesianIndices((1000, 1000))));
995.376 μs (2 allocations: 7.63 MiB)
julia> LazyFunctionArray((x, y) -> x + y, 1000, 1000) == mapview(I -> I[1] + I[2], CartesianIndices((1000, 1000)))
true
```
Not sure if any provide caching though.
---
### Author:  [@AlexanderNenninger](https://discourse.julialang.org/u/AlexanderNenninger)
#### Post date: [August 7, 2023, 7:14am UTC](https://discourse.julialang.org/t/cache-data-structure-for-lazy-array/102388/4 "2023-08-07T07:14:15Z")
Thanks for the tip. The function itself can provide the caching.
---
### Author:  [@aplavin](https://discourse.julialang.org/u/aplavin)
#### Post date: [August 7, 2023, 11:27am UTC](https://discourse.julialang.org/t/cache-data-structure-for-lazy-array/102388/5 "2023-08-07T11:27:30Z")
It can, and existing memoization libraries would probably yield the same performance when combined with `mapview` compared to a specialized implementation using Dict underneath.
What’s definitely possible to make more efficient is the scenario where one accesses a significant fraction of the resulting array (multiple times). Then, using a same-sized array as a cache would have less overhead compared to Dict, and this would benefit from a specialized implementation.
Such functionality is potentially in the scope of FlexiMaps.jl as well, but don’t know if that’s a common usecase — don’t remember a need for such a structure myself.
---
### Author:  [@AlexanderNenninger](https://discourse.julialang.org/u/AlexanderNenninger)
#### Post date: [August 8, 2023, 9:28am UTC](https://discourse.julialang.org/t/cache-data-structure-for-lazy-array/102388/6 "2023-08-08T09:28:00Z")
I thought about doing that and was a little stuck on how to represent missing values efficiently. For developing algorithms the cacheless version is pretty good due to it’s simplicity and fast intialization. I feel like we’re at a point where we need empirical data to proceed further. I’ll update this post once I get to that point. Thanks for all the ideas and the feedback.