# Cheapest way for creating a CartesianIndex

**URL:** <https://discourse.julialang.org/t/cheapest-way-for-creating-a-cartesianindex/89819>\
**Category:** General Usage\
**Tags:** question, cartesianindices\
**Created:** [November 5, 2022, 6:04pm UTC](https://discourse.julialang.org/t/cheapest-way-for-creating-a-cartesianindex/89819 "2022-11-05T18:04:46Z")\
**Posts on this page:** 10\
**Page:** 1

<div class="post-metadata">

**Author:** ![LaurentPlagne](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laurentplagne/32/10103_2.png) [@LaurentPlagne](https://discourse.julialang.org/u/LaurentPlagne)\
**Post date:** [November 5, 2022, 6:04pm UTC](https://discourse.julialang.org/t/cheapest-way-for-creating-a-cartesianindex/89819/1 "2022-11-05T18:04:46Z")

</div>

Hi,

I am trying to write a generic multidimensional algorithm where I need a random access to an ND Array.  
I need to define a CartesianIndex with computed coordinates and modify my array using this CI.

Unfortunately it seems that this process allocates some memory:

```julia
@benchmark CartesianIndex(Tuple([1,2,3]))

```

returns

```julia
BenchmarkTools.Trial: 10000 samples with 641 evaluations.
 Range (min … max): 193.058 ns … 4.688 μs ┊ GC (min … max): 0.00% … 94.70%
 Time (median): 194.683 ns ┊ GC (median): 0.00%
 Time (mean ± σ): 204.164 ns ± 187.748 ns ┊ GC (mean ± σ): 4.08% ± 4.23%

   ▂▆██▇▅▄▂▁▁ ▁▁▃▃▃▂▁ ▁ ▁▁▁▂▁ ▂
  ▅█████████████████████████████▆▇▆▇▆▇▆▆▅▇▅▆▆▅▄▅▄▅▄▃▅▄▄▅▄▄▃▄▄▁▅ █
  193 ns Histogram: log(frequency) by time 214 ns <

 Memory estimate: 144 bytes, allocs estimate: 3.

```

I wonder if it is possible to improve the situation without falling back to linear indices…  
Any hint ?

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [November 5, 2022, 6:08pm UTC](https://discourse.julialang.org/t/cheapest-way-for-creating-a-cartesianindex/89819/2 "2022-11-05T18:08:29Z")

</div>

You’re allocating in your benchmark because you’re creating an array with `[1,2,3]`. Use the multi-argument constructor instead.

Can you show an example in your algorithm?

---

<div class="post-metadata">

**Author:** ![LaurentPlagne](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laurentplagne/32/10103_2.png) [@LaurentPlagne](https://discourse.julialang.org/u/LaurentPlagne)\
**Post date:** [November 5, 2022, 6:18pm UTC](https://discourse.julialang.org/t/cheapest-way-for-creating-a-cartesianindex/89819/3 "2022-11-05T18:18:12Z")

</div>

True but it is not the only allocation:

```julia
julia> a=[1,2,3]

3-element Vector{Int64}:
 1
 2
 3

julia> @benchmark CartesianIndex(Tuple($a))
BenchmarkTools.Trial: 10000 samples with 705 evaluations.
 Range (min … max): 179.196 ns … 4.248 μs ┊ GC (min … max): 0.00% … 94.41%
 Time (median): 180.496 ns ┊ GC (median): 0.00%
 Time (mean ± σ): 184.547 ns ± 90.713 ns ┊ GC (mean ± σ): 1.44% ± 2.79%

   ▂▇██▆▃▁▁▁ ▁▂▂▂▁▃▃▁ ▂▂▁▁ ▁ ▂
  ▅██████████████████▇█████▇███████▇██▇▇▆▆▆▇▇▇▆▇▆▅▇▆▆▅▄▅▄▅▅▄▅▆ █
  179 ns Histogram: log(frequency) by time 197 ns <

 Memory estimate: 64 bytes, allocs estimate: 2.

```

The algorithm looks like:

```julia
function my_algo(ndarray::Array{Int,D}) where {D}
   temp_idx_array=zero(Int,D)
   for ...
       myupdate!(temp_idx_array)
       ndarray(CartesianIndex(Tuple(temp_idx_array))=something
   end

```

I could compute the corresponding linear index to ndarray but the rest of the algorithmis based on CartesianIndices.

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [November 5, 2022, 6:30pm UTC](https://discourse.julialang.org/t/cheapest-way-for-creating-a-cartesianindex/89819/4 "2022-11-05T18:30:15Z")

</div>

Don’t know, if this helps: the length of the vector is not known at compile time, therefore

```julia
julia> @benchmark CartesianIndex(a...) setup=(a=[1, 2, 3])
BenchmarkTools.Trial: 10000 samples with 308 evaluations.
 Range (min … max): 237.338 ns … 8.984 μs ┊ GC (min … max): 0.00% … 95.64%
 Time (median): 273.701 ns ┊ GC (median): 0.00%
 Time (mean ± σ): 275.756 ns ± 169.897 ns ┊ GC (mean ± σ): 1.19% ± 1.92%

  █ █
  █▅▁▁▅▄▄▄▂▁▂▂█▆▂▂▂█▄▃▂▂▂▂▂▃▂▁▁▁▁▂▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁▁ ▂
  237 ns Histogram: frequency by time 414 ns <

 Memory estimate: 64 bytes, allocs estimate: 2.

julia> @benchmark CartesianIndex(a...) setup=(a=(1, 2, 3))
BenchmarkTools.Trial: 10000 samples with 1000 evaluations.
 Range (min … max): 1.100 ns … 43.900 ns ┊ GC (min … max): 0.00% … 0.00%
 Time (median): 1.300 ns ┊ GC (median): 0.00%
 Time (mean ± σ): 1.356 ns ± 1.088 ns ┊ GC (mean ± σ): 0.00% ± 0.00%

                     █
  ▂▁▁▁▁▁▁▁▁▆▁▁▁▁▁▁▁▁▁█▁▁▁▁▁▁▁▁▃▁▁▁▁▁▁▁▁▁▂▁▁▁▁▁▁▁▁▁▂▁▁▁▁▁▁▁▁▂ ▂
  1.1 ns Histogram: frequency by time 1.7 ns <

 Memory estimate: 0 bytes, allocs estimate: 0.

```

---

<div class="post-metadata">

**Author:** ![LaurentPlagne](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laurentplagne/32/10103_2.png) [@LaurentPlagne](https://discourse.julialang.org/u/LaurentPlagne)\
**Post date:** [November 5, 2022, 6:37pm UTC](https://discourse.julialang.org/t/cheapest-way-for-creating-a-cartesianindex/89819/5 "2022-11-05T18:37:10Z")

</div>

Thanks !  
The length of the vector is known when the algorithm is applied to the ND array so I could use a parametric algorithm like in my pseudo\_example. The problem is then to create the input Tuple without relying on multi-argument Ctor.

The linear index solution is probably much simpler in my case…

---

<div class="post-metadata">

**Author:** ![rafael.guerra](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rafael.guerra/32/216610_2.png) [@rafael.guerra](https://discourse.julialang.org/u/rafael.guerra)\
**Post date:** [November 5, 2022, 8:13pm UTC](https://discourse.julialang.org/t/cheapest-way-for-creating-a-cartesianindex/89819/7 "2022-11-05T20:13:59Z")

</div>

Depending on the maximum number of dimensions, using StaticArrays can speed it up:

```julia
using StaticArrays
x = SA[1,2,4]
CartesianIndex(Tuple(x)) # 2 ns (0 allocs: 0 bytes)

```

---

<div class="post-metadata">

**Author:** ![Sukera](https://avatars.discourse-cdn.com/v4/letter/s/ce7236/32.png) [@Sukera](https://discourse.julialang.org/u/Sukera)\
**Post date:** [November 5, 2022, 10:01pm UTC](https://discourse.julialang.org/t/cheapest-way-for-creating-a-cartesianindex/89819/8 "2022-11-05T22:01:32Z")

</div>

> [@LaurentPlagne](#):
>
> The algorithm looks like:
> 
> ```julia
> function my_algo(ndarray::Array{Int,D}) where {D}
> temp_idx_array=zero(Int,D)
> for ...
> myupdate!(temp_idx_array)
> ndarray(CartesianIndex(Tuple(temp_idx_array))=something
> end
> 
> ```

You can just create a `zero(CartesianIndex{D})`:

```julia
julia> zero(CartesianIndex{4})
CartesianIndex(0, 0, 0, 0)

```

and then add/subtract/multiply:

```julia
julia> zero(CartesianIndex{4}) + one(CartesianIndex{4})*2
CartesianIndex(2, 2, 2, 2)

```

Since `CartesianIndex` are just fancy tuples & immutable, I usually create whole grids of them and filter the ones out I don’t care about.

> [@LaurentPlagne](#):
>
> The length of the vector is known when the algorithm is applied to the ND array so I could use a parametric algorithm like in my pseudo\_example.

The length of the vector is _not_ known on the type level, which causes a type instability for the `Tuple`, which in turn causes a type instability on `CartesianIndex` (the dimensionality is part of the type there after all). These type instabilities end up boxing those variables, meaning they need to be heap allocated - 2 type instabilities plus one array equals 3 allocations 🙂

---

<div class="post-metadata">

**Author:** ![stevengj](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stevengj/32/71_2.png) [@stevengj](https://discourse.julialang.org/u/stevengj)\
**Post date:** [November 5, 2022, 10:15pm UTC](https://discourse.julialang.org/t/cheapest-way-for-creating-a-cartesianindex/89819/9 "2022-11-05T22:15:35Z")

</div>

> [@LaurentPlagne](#):
>
> `CartesianIndex(Tuple([1,2,3]))`

You can make a tuple directly with `(1,2,3)`, without creating an array first. i.e. do `CartesianIndex((1,2,3))`.

---

<div class="post-metadata">

**Author:** ![goerch](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/goerch/32/29122_2.png) [@goerch](https://discourse.julialang.org/u/goerch)\
**Post date:** [November 5, 2022, 10:40pm UTC](https://discourse.julialang.org/t/cheapest-way-for-creating-a-cartesianindex/89819/10 "2022-11-05T22:40:53Z")

</div>

> [@LaurentPlagne](#):
>
> The length of the vector is known when the algorithm is applied to the ND array so I could use a parametric algorithm like in my pseudo\_example. The problem is then to create the input Tuple without relying on multi-argument Ctor.

Sorry, I believe we can’t check your MWE due to omissions.

---

<div class="post-metadata">

**Author:** ![LaurentPlagne](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/laurentplagne/32/10103_2.png) [@LaurentPlagne](https://discourse.julialang.org/u/LaurentPlagne)\
**Post date:** [November 6, 2022, 8:45am UTC](https://discourse.julialang.org/t/cheapest-way-for-creating-a-cartesianindex/89819/11 "2022-11-06T08:45:47Z")

</div>

Thank you very much for all answers not only providing a neat solution but allowing me to understand what was going on 😉

> [@Sukera](#):
>
> The length of the vector is _not_ known on the type level, which causes a type instability for the `Tuple`, which in turn causes a type instability on `CartesianIndex` (the dimensionality is part of the type there after all). These type instabilities end up boxing those variables, meaning they need to be heap allocated - 2 type instabilities plus one array equals 3 allocations 🙂

explains nicely why I marked @rafael.guerra `StaticArrays` based proposal as the solution of my problem:

In my code, I can use the same mutable and fixed size `MVector` `x` which is modified inside the loop and compute corresponding `CartesianIndex(Tuple(x))` for _free_ to access my ND-Array.

Sorry for the pseudo-algo I provided which was not a MWE.