# N-dimensional implementations

**URL:** <https://discourse.julialang.org/t/n-dimensional-implementations/16191>\
**Category:** General Usage\
**Tags:** question, images\
**Created:** [October 11, 2018, 4:30pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191 "2018-10-11T16:30:21Z")\
**Posts on this page:** 20\
**Page:** 1

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [October 11, 2018, 4:30pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191/1 "2018-10-11T16:30:21Z")

</div>

I am trying to generalize an algorithm for N-dimensional arrays, but there are many code patterns for which I don’t have a solution yet. I will use this thread to ask a few questions.

How do you generalize the following code to work with N-dimensional arrays as opposed to just 3D arrays?

```julia
activated[gridsize[1]+1:padsize[1],:,:] .= false
activated[:,gridsize[2]+1:padsize[2],:] .= false
activated[:,:,gridsize[3]+1:padsize[3]] .= false

```

Tried to make use of the functionality in `Base.Cartesian` like `@nref` but without success.

---

<div class="post-metadata">

**Author:** ![davidbp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/davidbp/32/463_2.png) [@davidbp](https://discourse.julialang.org/u/davidbp)\
**Post date:** [October 11, 2018, 6:24pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191/2 "2018-10-11T18:24:46Z")

</div>

Any program is a bunch of (parsed) strings! 😅  
Edited: Sloopy solution that no one should use but it’s fun to write.

```julia
N = 8
for i in 1:N
    println("activated[" * ":,"^(i-1) * "gridsize[$i]+1:padsize[$i]" * ",:"^(N-i) * "] .= false" )
end

```

prints

```julia
activated[gridsize[1]+1:padsize[1],:,:,:,:,:,:,:] .= false
activated[:,gridsize[2]+1:padsize[2],:,:,:,:,:,:] .= false
activated[:,:,gridsize[3]+1:padsize[3],:,:,:,:,:] .= false
activated[:,:,:,gridsize[4]+1:padsize[4],:,:,:,:] .= false
activated[:,:,:,:,gridsize[5]+1:padsize[5],:,:,:] .= false
activated[:,:,:,:,:,gridsize[6]+1:padsize[6],:,:] .= false
activated[:,:,:,:,:,:,gridsize[7]+1:padsize[7],:] .= false
activated[:,:,:,:,:,:,:,gridsize[8]+1:padsize[8]] .= false

```

So you only need to “make it code”

```julia
N = 8
your_code = []
for i in 1:N
    push!(your_code, Meta.parse("activated[" * ":,"^(i-1) * "gridsize[$i]+1:padsize[$i]" * ",:"^(N-i) * "] .= false" ))
end

```

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [October 11, 2018, 6:25pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191/3 "2018-10-11T18:25:26Z")

</div>

```julia
function foo(gridsize, padsize, activated::Array{Bool,N}) where {N}
for k=1:N 
g=gridsize[k]
p=padsize[k]
pref = ntuple(i->Colon(), k-1)
suff = ntuple(i->Colon(), N-k)
v=view(activated, pref..., g+1:p, suff...)
v .= false
end
end

```

If this is too slow, you might need to become `@generated` ☹

---

<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:** [October 11, 2018, 6:34pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191/4 "2018-10-11T18:34:26Z")

</div>

> [@davidbp](#):
>
> Any program is a bunch of (parsed) strings!

Even if you are doing code generation, don’t use strings. Work directly with ASTs.

---

<div class="post-metadata">

**Author:** ![davidbp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/davidbp/32/463_2.png) [@davidbp](https://discourse.julialang.org/u/davidbp)\
**Post date:** [October 11, 2018, 6:45pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191/5 "2018-10-11T18:45:33Z")

</div>

It’s in my todo list to learn how to do it!

---

<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:** [October 11, 2018, 6:50pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191/6 "2018-10-11T18:50:57Z")

</div>

> [@juliohm](#):
>
> `activated[gridsize[1]+1:padsize[1],:,:] .= false`

`CartesianIndices` is what you want here. That allows you to specify a slice of an arbitrary multidimensional array and iterate over it very efficiently.

```julia
function myfunc(activated::AbstractArray{N}, gridsize, padsize) where {N} 
    ax = axes(activated)
    for d = 1:N
        axd = ntuple(i -> i == d ? (gridsize[d]+1:padsize[d]) : ax[i], Val{N}())
        activated[CartesianIndices(axd)] .= false
    end
end

```

Note that by making `N` a type parameter in this way and using `Val{N}` in the `ntuple` constructor, I ensure that the dimensionality is known at compile-time, allowing the compiler to emit highly optimized code.

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [October 11, 2018, 6:57pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191/7 "2018-10-11T18:57:05Z")

</div>

Thank you @stevengj, will `Val{N}` be needed in future versions of the language? Shouldn’t the compiler be able to infer `N` directly?

---

<div class="post-metadata">

**Author:** ![antoine-levitt](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/antoine-levitt/32/4008_2.png) [@antoine-levitt](https://discourse.julialang.org/u/antoine-levitt)\
**Post date:** [October 11, 2018, 7:00pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191/8 "2018-10-11T19:00:25Z")

</div>

That kind of code is wonderful but also kind of hard to read. Any good syntactic sugar that could be used here? Something like `@NDColon activated[1:d, ind, d+2:N]` or similar?

edit: hmm that’s really bad notation in case ind also has colons. `..` is available and has a nice precedence, so `@.. activated[1..d-1, gridsize[d]+1:padsize[d],d..N] .= false` could plausibly work.

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [October 11, 2018, 7:03pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191/9 "2018-10-11T19:03:54Z")

</div>

+1 for syntactic sugar, code can get quite unreadable quickly in N-dimensions

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [October 11, 2018, 7:04pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191/10 "2018-10-11T19:04:16Z")

</div>

So I’d like to know:

It is not so rare that I have loops over compile-time known numbers of elements, but types of local variables change over these loops. Like `axd` in your case.

Is there a sensible way of telling julia that a loop should be statically unrolled before inference? My current standard approach is to make it all `@generated` but that is really really ugly.

In your code with `N=4` we infer `axd::NTuple{4,Union{OneTo{Int64}, UnitRange{Int64}}}`, which is afaik heap-allocated. Whereas in statically unrolled loops, it would be type-stable and stack-allocated.

Afterwards, constant propagation is normally good enough to not need `Val{N}()`, but you always need to read `@code_warntype`.

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [October 11, 2018, 7:43pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191/11 "2018-10-11T19:43:17Z")

</div>

```julia
julia> function myfunc(activated::AbstractArray{Bool,N}, gridsize, padsize) where {N} 
           ax = axes(activated)
           for d = 1:N
               axd = ntuple(i -> i == d ? (gridsize[d]+1:padsize[d]) : ax[i], Val{N}())
               activated[CartesianIndices(axd)] .= false
           end
       nothing
       end

julia> function myfunc_ur(activated::AbstractArray{Bool,4}, gridsize, padsize)  
           activated[(gridsize[1]+1:padsize[1]),:,:,:] .= false
           activated[:,(gridsize[2]+1:padsize[2]),:,:] .= false
           activated[:,:,(gridsize[3]+1:padsize[3]),:] .= false
           activated[:,:,:,(gridsize[4]+1:padsize[4])] .= false
nothing
end
julia> function foo(activated::Array{Bool,N}, gridsize, padsize) where {N}
       for k=1:N 
       g=gridsize[k]
       p=padsize[k]
       pref = ntuple(i->Colon(), k-1)
       suff = ntuple(i->Colon(), N-k)
       v=view(activated, pref..., g+1:p, suff...)
       v .= false
       end
       end

julia> activated = rand(Bool, (2,2,2,2)); gridsize=[1,1,1,1]; padsize=[2,2,2,2];

julia> using BenchmarkTools
julia> @btime myfunc_ur($activated, $gridsize, $padsize)
  164.119 ns (4 allocations: 320 bytes)
julia> @btime myfunc($activated, $gridsize, $padsize)
  4.207 μs (36 allocations: 1.25 KiB)
julia> @btime foo($activated, $gridsize, $padsize)
  5.275 μs (37 allocations: 1.31 KiB)

```

But the fast version needs to be `@generated`, which is in practice too much of a hassle. Some way of static unrolling would be pretty nice for that.

---

<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:** [October 11, 2018, 8:27pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191/12 "2018-10-11T20:27:10Z")

</div>

> [@foobar\_lv2](#):
>
> Is there a sensible way of telling julia that a loop should be statically unrolled before inference?

An `ntuple` loop with a `Val` length _is_ statically unrolled, and the heterogeneous tuple type should be statically inferred and _not_ heap allocated.

For example:

```julia
julia> foo(n) = ntuple(i -> i < 4 ? i : string(i), n)
foo (generic function with 1 method)

julia> foo(Val{7}())
(1, 2, 3, "4", "5", "6", "7")

julia> using Test

julia> @inferred foo(Val{7}()) # succeeds: type is statically inferred
(1, 2, 3, "4", "5", "6", "7")

```

versus a non-`Val` loop where `n` is not statically inferred:

```julia
julia> @inferred foo(7)
ERROR: return type Tuple{Int64,Int64,Int64,String,String,String,String} does not match inferred return type Tuple
Stacktrace:
 [1] error(::String) at ./error.jl:33
 [2] top-level scope at none:0

```

---

<div class="post-metadata">

**Author:** ![kristoffer.carlsson](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/kristoffer.carlsson/32/22_2.png) [@kristoffer.carlsson](https://discourse.julialang.org/u/kristoffer.carlsson)\
**Post date:** [October 11, 2018, 8:37pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191/13 "2018-10-11T20:37:41Z")

</div>

Note constant propagation though:

```julia
julia> foo(n) = ntuple(i -> i < 4 ? i : string(i), n)
foo (generic function with 1 method)

julia> g() = foo(7)
g (generic function with 1 method)

julia> @inferred g()
(1, 2, 3, "4", "5", "6", "7")

```

Ref [Extend code\_typed to be able to debug constant prop by Keno · Pull Request #29261 · JuliaLang/julia · GitHub](https://github.com/JuliaLang/julia/pull/29261)

---

<div class="post-metadata">

**Author:** ![rdeits](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/rdeits/32/286_2.png) [@rdeits](https://discourse.julialang.org/u/rdeits)\
**Post date:** [October 11, 2018, 8:48pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191/14 "2018-10-11T20:48:12Z")

</div>

@foobar_lv2 check out [https://github.com/cstjean/Unrolled.jl](https://github.com/cstjean/Unrolled.jl)

---

<div class="post-metadata">

**Author:** ![juliohm](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/juliohm/32/215266_2.png) [@juliohm](https://discourse.julialang.org/u/juliohm)\
**Post date:** [October 11, 2018, 8:52pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191/15 "2018-10-11T20:52:38Z")

</div>

@stevengj in your example is it ok to replace `ax[i]` by `Colon()`? Any performance penalty in using `Colon()`? I personally think it is more readable.

EDIT: nevermind, `CartesianIndices` does not work with `Colon()`

---

<div class="post-metadata">

**Author:** ![foobar\_lv2](https://avatars.discourse-cdn.com/v4/letter/f/ee59a6/32.png) [@foobar\_lv2](https://discourse.julialang.org/u/foobar_lv2)\
**Post date:** [October 11, 2018, 9:19pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191/16 "2018-10-11T21:19:04Z")

</div>

> [@stevengj](#):
>
> An `ntuple` loop with a `Val` length _is_ statically unrolled, and the heterogeneous tuple type should be statically inferred and _not_ heap allocated.

But, as far as I gathered, the problem is the `for d = 1:N` loop that needs to be unrolled. Each heterogeneous Tuple is fine, but we should not put all of them into the same slot.

> [@rdeits](#):
>
> @foobar_lv2 check out [https://github.com/cstjean/Unrolled.jl](https://github.com/cstjean/Unrolled.jl)

That looks pretty cool, I’ll play with that and see how well it works!

---

<div class="post-metadata">

**Author:** ![davidbp](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/davidbp/32/463_2.png) [@davidbp](https://discourse.julialang.org/u/davidbp)\
**Post date:** [October 12, 2018, 2:26pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191/17 "2018-10-12T14:26:57Z")

</div>

Do you mean to create a macro that generates the expressions that I created with strings + Meta.parse but without using strings? I read the metaprogramming section in the manual, and I think I graps some ideas, but it feels a bit odd (probably because I only use macros from other people but never went into the hassle of building one).

---

<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:** [October 12, 2018, 6:46pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191/18 "2018-10-12T18:46:01Z")

</div>

> [@davidbp](#):
>
> Do you mean to create a macro that generates the expressions that I created with strings + Meta.parse but without using strings?

It doesn’t have to be with a macro, e.g. you can just use `@eval`. The point is, if you want to do code generation in Julia, do it by generating/manipulating ASTs (`Expr` nodes) and not by manipulating strings and then parsing them.

I feel like @StefanKarpinski wrote up a long explanation somewhere of why manipulating strings is brittle, and I don’t feel like repeating it, but I’m not sure where to find it.

---

<div class="post-metadata">

**Author:** ![StefanKarpinski](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/stefankarpinski/32/24_2.png) [@StefanKarpinski](https://discourse.julialang.org/u/StefanKarpinski)\
**Post date:** [October 12, 2018, 7:24pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191/19 "2018-10-12T19:24:23Z")

</div>

> [@stevengj](#):
>
> I feel like @StefanKarpinski wrote up a long explanation somewhere of why manipulating strings is brittle, and I don’t feel like repeating it, but I’m not sure where to find it.

Maybe this stack overflow answer?

> <https://stackoverflow.com/questions/34016768/julia-invoke-a-function-by-a-given-string/34023458#34023458>

---

<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:** [October 12, 2018, 8:27pm UTC](https://discourse.julialang.org/t/n-dimensional-implementations/16191/20 "2018-10-12T20:27:04Z")

</div>

I was thinking more of examples like this:

```julia
x = "a + b"
y = "$x * c" # probably not what you want!

x = :(a + b)
y = :($x * c) # good: gives :((a + b) * c)

```

Doing code generation with strings is extremely brittle because you are dealing with surface syntax. Working with `Expr` objects (which is especially easy in Julia because of quoting and interpolation syntax), on the other hand, is **composable** with few surprises because you are directly encoding the abstract _meaning_ of the expressions rather than their spelling.