# Reducing getindex allocation \[edit: when using an array as index\]

**URL:** <https://discourse.julialang.org/t/reducing-getindex-allocation-edit-when-using-an-array-as-index/79116>\
**Category:** Performance\
**Tags:** memory-allocation\
**Created:** [April 6, 2022, 6:08pm UTC](https://discourse.julialang.org/t/reducing-getindex-allocation-edit-when-using-an-array-as-index/79116 "2022-04-06T18:08:25Z")\
**Posts on this page:** 18\
**Page:** 1

<div class="post-metadata">

**Author:** ![user\_231578](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/user_231578/32/24170_2.png) [@user\_231578](https://discourse.julialang.org/u/user_231578)\
**Post date:** [April 6, 2022, 6:08pm UTC](https://discourse.julialang.org/t/reducing-getindex-allocation-edit-when-using-an-array-as-index/79116/1 "2022-04-06T18:08:25Z")

</div>

I need to access a matrix millions of times, and I noticed that most of the allocations of my code come exactly from this. My code is similar to the following example

```julia
const A = rand(10,10)
function get_number(idx)
	@inbounds getindex(A, idx...)
end

```

Say I need to access index (4,6) 100000 times

```julia
idx = [4,6]
@time begin
for i in 1:100000
    get_number(idx)
end
end
0.011408 seconds (200.78 k allocations: 3.099 MiB, 16.23% compilation time)

```

This, as you can see, allocates 3 MiB. Each call makes 2 16bytes allocations of

```julia
 @time get_number(idx)
0.000004 seconds (2 allocations: 32 bytes)

```

Is there a way to reduce/eliminate these allocations?

---

<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:** [April 6, 2022, 6:40pm UTC](https://discourse.julialang.org/t/reducing-getindex-allocation-edit-when-using-an-array-as-index/79116/2 "2022-04-06T18:40:24Z")

</div>

Splatting seems to be the culprit here. The following

```julia
using BenchmarkTools

const A = rand(10,10)
function get_number(idx1, idx2)
	@inbounds getindex(A, idx1, idx2)
end

function test()
    for i in 1:100000
        idx = (rand(1:10),rand(1:10))
        get_number(idx[1], idx[2])
    end
end

@btime test()

```

yields

```julia
  1.074 ms (0 allocations: 0 bytes)

```

---

<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:** [April 6, 2022, 6:47pm UTC](https://discourse.julialang.org/t/reducing-getindex-allocation-edit-when-using-an-array-as-index/79116/3 "2022-04-06T18:47:38Z")

</div>

Never mind, indexing with a vector instead of a tuple is the problem. The following works, too:

```julia
using BenchmarkTools

const A = rand(10,10)
function get_number(idx...)
	@inbounds getindex(A, idx...)
end

function test()
    for i in 1:100000
        idx = (rand(1:10),rand(1:10))
        get_number(idx...)
    end
end

@btime test()

```

yielding

```julia
  1.070 ms (0 allocations: 0 bytes)

```

---

<div class="post-metadata">

**Author:** ![user\_231578](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/user_231578/32/24170_2.png) [@user\_231578](https://discourse.julialang.org/u/user_231578)\
**Post date:** [April 7, 2022, 6:34am UTC](https://discourse.julialang.org/t/reducing-getindex-allocation-edit-when-using-an-array-as-index/79116/4 "2022-04-07T06:34:53Z")

</div>

Unfortunately, I need idx to be a vector of size n rather than a tuple. At least now I know that the cause is, thanks! I will try to look into it.

---

<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:** [April 7, 2022, 6:38am UTC](https://discourse.julialang.org/t/reducing-getindex-allocation-edit-when-using-an-array-as-index/79116/5 "2022-04-07T06:38:38Z")

</div>

Interesting, fixed or variable size `n`? In the second case I’d expect further problems…

---

<div class="post-metadata">

**Author:** ![user\_231578](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/user_231578/32/24170_2.png) [@user\_231578](https://discourse.julialang.org/u/user_231578)\
**Post date:** [April 7, 2022, 6:42am UTC](https://discourse.julialang.org/t/reducing-getindex-allocation-edit-when-using-an-array-as-index/79116/6 "2022-04-07T06:42:28Z")

</div>

In my case, n is a const. It can a number between 2 to say 5 at most, but it is fixed at the beginning and never changes during the experiment. I tried to do the following:

```julia
const A = rand(10,10)
function get_number(idx)
	@inbounds getindex(A, (idx[1],idx[2])...)
end

```

And this largely solves the problem: allocations drop from 14.5Gb to 500Mb and the code is more than 2x faster. However, this does not work as sood as idx is of size 3 or more.

---

<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:** [April 7, 2022, 6:44am UTC](https://discourse.julialang.org/t/reducing-getindex-allocation-edit-when-using-an-array-as-index/79116/7 "2022-04-07T06:44:26Z")

</div>

> [@user\_231578](#):
>
> In my case, n is a const. It can a number between 2 to say 5 at most, but it is fixed at the beginning and never changes during the experiment.

If you can generalize the MWE, we could try to use `ntuple`?

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [April 7, 2022, 6:45am UTC](https://discourse.julialang.org/t/reducing-getindex-allocation-edit-when-using-an-array-as-index/79116/8 "2022-04-07T06:45:59Z")

</div>

Can you write out the indexing expression? Like

```julia
A[idx[1], idx[2], idx[3]]

```

That should help. Otherwise, if `n` is a compile time constant you may be able to turn `ind` into a tuple in an efficient way.

BTW, you don’t have to use `getindex`, just write `A[idx...]`

---

<div class="post-metadata">

**Author:** ![user\_231578](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/user_231578/32/24170_2.png) [@user\_231578](https://discourse.julialang.org/u/user_231578)\
**Post date:** [April 7, 2022, 6:47am UTC](https://discourse.julialang.org/t/reducing-getindex-allocation-edit-when-using-an-array-as-index/79116/9 "2022-04-07T06:47:08Z")

</div>

What is MWE?

I tried to use ntuple but it seems to allocate a lot of memory on its own.

---

<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:** [April 7, 2022, 6:48am UTC](https://discourse.julialang.org/t/reducing-getindex-allocation-edit-when-using-an-array-as-index/79116/10 "2022-04-07T06:48:06Z")

</div>

> [@user\_231578](#):
>
> What is MWE?

M(inimal)W(orking)E(xample), i.e. your example code…

---

<div class="post-metadata">

**Author:** ![DNF](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/dnf/32/10191_2.png) [@DNF](https://discourse.julialang.org/u/DNF)\
**Post date:** [April 7, 2022, 6:48am UTC](https://discourse.julialang.org/t/reducing-getindex-allocation-edit-when-using-an-array-as-index/79116/11 "2022-04-07T06:48:09Z")

</div>

Yes, maybe something like

```julia
tup = ntuple(i->idx[i], Val(4))
A[tup...]

```

if 4 is the number.

But, @user_231578, when you say `n` is constant, where and how is it set?

---

<div class="post-metadata">

**Author:** ![user\_231578](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/user_231578/32/24170_2.png) [@user\_231578](https://discourse.julialang.org/u/user_231578)\
**Post date:** [April 7, 2022, 6:48am UTC](https://discourse.julialang.org/t/reducing-getindex-allocation-edit-when-using-an-array-as-index/79116/12 "2022-04-07T06:48:33Z")

</div>

Transforming idx into a tuple in an efficiend way is what I would like to do: but failing. And you are right, there is no need to write get index.

---

<div class="post-metadata">

**Author:** ![user\_231578](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/user_231578/32/24170_2.png) [@user\_231578](https://discourse.julialang.org/u/user_231578)\
**Post date:** [April 7, 2022, 6:54am UTC](https://discourse.julialang.org/t/reducing-getindex-allocation-edit-when-using-an-array-as-index/79116/13 "2022-04-07T06:54:35Z")

</div>

> [@DNF](#):
>
> `tup = ntuple(i->idx[i], Val(4))`

ntuple seems to allocate too much memory for being useful here

```julia
 0.006581 seconds (5.21 k allocations: 322.297 KiB, 98.60% compilation time)

```

> [@DNF](#):
>
> But, @user_231578, when you say `n` is constant, where and how is it set?

n is set at the beginning of the code, take this as an example:

```julia
const n = 3
const dims = ntuple(i -> 10, Val(n))
const A = rand(dims...)

function get_number(idx)
	@inbounds A[idx..]
end

```

---

<div class="post-metadata">

**Author:** ![Salmon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/salmon/32/22968_2.png) [@Salmon](https://discourse.julialang.org/u/Salmon)\
**Post date:** [April 7, 2022, 7:23am UTC](https://discourse.julialang.org/t/reducing-getindex-allocation-edit-when-using-an-array-as-index/79116/14 "2022-04-07T07:23:38Z")

</div>

are you sure your example doesnt work as intended?  
using your code and benchmarking properly, I get in a fresh REPL (Julia v. 1.7.1):

```julia
using BenchmarkTools
const n = 3;
const dims = ntuple(i -> 10, Val(n));
const A = rand(dims...);

function get_number(idx)
	@inbounds A[idx...]
end
@btime get_number((1,2,3))

  1.900 ns (0 allocations: 0 bytes)
0.9097530819846809  

```

---

<div class="post-metadata">

**Author:** ![user\_231578](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/user_231578/32/24170_2.png) [@user\_231578](https://discourse.julialang.org/u/user_231578)\
**Post date:** [April 7, 2022, 7:29am UTC](https://discourse.julialang.org/t/reducing-getindex-allocation-edit-when-using-an-array-as-index/79116/15 "2022-04-07T07:29:40Z")

</div>

It does work as intended: as @goerch pointed out, the problem was that I was indexing with a vector rather than a tuple. Thus, my problem has shifted: I need a non-allocating way to convert my idx array to a tuple. For the moment, this workaround seems to do just fine (but it is ugly):

```julia
function get_tuple(idx)
	if n == 2 
		tup = (idx[1], idx[2])
	elseif n == 3
		tup = (idx[1], idx[2], idx[3])
	elseif n == 4
		tup = (idx[1], idx[2], idx[3], idx[4])
	elseif n == 5
		tup = (idx[1], idx[2], idx[3], idx[4], idx[5])
	end
	return tup
end

```

---

<div class="post-metadata">

**Author:** ![Salmon](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/salmon/32/22968_2.png) [@Salmon](https://discourse.julialang.org/u/Salmon)\
**Post date:** [April 7, 2022, 7:48am UTC](https://discourse.julialang.org/t/reducing-getindex-allocation-edit-when-using-an-array-as-index/79116/16 "2022-04-07T07:48:47Z")

</div>

ah, ok then I misunderstood you:

how about the following then?

```julia
get_tuple2(idx) = ntuple(i -> idx[i], n)

```

There is one allocation of 32 bytes as also in your example (possibly one can eliminate that as well if there is a need for it).

---

<div class="post-metadata">

**Author:** ![user\_231578](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/user_231578/32/24170_2.png) [@user\_231578](https://discourse.julialang.org/u/user_231578)\
**Post date:** [April 7, 2022, 7:54am UTC](https://discourse.julialang.org/t/reducing-getindex-allocation-edit-when-using-an-array-as-index/79116/17 "2022-04-07T07:54:28Z")

</div>

> [@Salmon](#):
>
> `ntuple(i -> idx[i], n)`

you are prefectly right! Thanks!

---

<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:** [April 7, 2022, 7:54am UTC](https://discourse.julialang.org/t/reducing-getindex-allocation-edit-when-using-an-array-as-index/79116/18 "2022-04-07T07:54:33Z")

</div>

Without a generalized MWE I can only propose

```julia
using BenchmarkTools

function get_tuple(::Val{N}, idx) where {N}
    ntuple(i -> idx[i], Val(N))
end

@btime get_tuple(Val(2), vec) setup=(vec=rand(1:2, 2))
@btime get_tuple(Val(3), vec) setup=(vec=rand(1:3, 3))
@btime get_tuple(Val(4), vec) setup=(vec=rand(1:4, 4))

const N = 2
@btime get_tuple(Val(N), vec) setup=(vec=rand(1:N, N))

@btime get_tuple(Val(M), vec) setup=(M=2; vec=rand(1:M, M))

```

yielding

```julia
  2.200 ns (0 allocations: 0 bytes)
  2.700 ns (0 allocations: 0 bytes)
  2.700 ns (0 allocations: 0 bytes)
  2.400 ns (0 allocations: 0 bytes)
  188.406 ns (1 allocation: 32 bytes)

```

showing how careful we have to be with `const` vs non-`const` (I initially tried to benchmark with the last line…).

Edit: corrected `ntuple` to use the `Val` method (which could be helpful in other situations)…