Layout

A Layout defines how multidimensional data is stored in one-dimensional memory. It maps a logical coordinate to a linear index using a shape and a stride. The shape defines the dimensions of the array, while the stride determines the memory offset for each dimension.

For example, let's create a vector with a stride of 2:

julia> using MoYe
julia> struct StrideVector
          data
          layout
       end
julia> Base.getindex(x::StrideVector, i) = x.data[x.layout(i)]
julia> a = StrideVector(collect(1:8), Layout(4, 2))Main.StrideVector([1, 2, 3, 4, 5, 6, 7, 8], 4:2)
julia> @show a[1] a[2] a[3] a[4];a[1] = 1
a[2] = 3
a[3] = 5
a[4] = 7

Fundamentals

julia> using MoYe
julia> layout_2x4 = Layout((2, (2, 2)), (4, (1, 2)))(2, (2, 2)):(4, (1, 2))
julia> print("Shape: ", shape(layout_2x4))Shape: (2, (2, 2))
julia> print("Stride: ", stride(layout_2x4))Stride: (4, (1, 2))
julia> print("Size: ", size(layout_2x4)) # The domain is 1:8Size: 8
julia> print("Rank: ", rank(layout_2x4))Rank: 2
julia> print("Depth: ", depth(layout_2x4))Depth: 2
julia> print("Cosize: ", cosize(layout_2x4))Cosize: 8
julia> layout_2x4 # This can be viewed as a row-major matrix(2, (2, 2)):(4, (1, 2))

Compile-Time vs. Dynamic Layouts

You can also use static integers for compile-time layouts:

julia> static_layout = @Layout (2, (2, 2)) (4, (1, 2))(_2, (_2, _2)):(_4, (_1, _2))
julia> typeof(static_layout)StaticLayout{2, Tuple{StaticInt{2}, Tuple{StaticInt{2}, StaticInt{2}}}, Tuple{StaticInt{4}, Tuple{StaticInt{1}, StaticInt{2}}}} (alias for Layout{2, Tuple{Static.StaticInt{2}, Tuple{Static.StaticInt{2}, Static.StaticInt{2}}}, Tuple{Static.StaticInt{4}, Tuple{Static.StaticInt{1}, Static.StaticInt{2}}}})
julia> sizeof(static_layout)0

Static and dynamic layouts can produce different-looking but mathematically equivalent results. For example:

julia> layout = @Layout (2, (1, 6)) (1, (6, 2))(_2, (_1, _6)):(_1, (_6, _2))
julia> print(coalesce(layout))_12:_1

is different from:

julia> layout = Layout((2, (1, 6)), (1, (6, 2)))(2, (1, 6)):(1, (6, 2))
julia> print(coalesce(layout))(2, 1, 6):(1, 6, 2)

Static layouts allow for more aggressive compile-time simplification, while dynamic layouts may lead to type instability due to runtime checks.

Coordinate Spaces

A Layout's coordinate space is determined by its Shape and can be viewed in three ways:

h-D (Hierarchical) Coordinate Space: Each element has the same hierarchical structure as the Shape.
1-D Coordinate Space: The colexicographically flattened, one-dimensional representation of the coordinate space.
R-D Coordinate Space: Each element has the same rank as the Shape, but each top-level axis is colexicographically flattened into a one-dimensional space. R is the rank of the layout.

julia> layout_2x4(2, (1, 2)) # h-D coordinate7
julia> layout_2x4(2, 3)      # R-D coordinate7
julia> layout_2x4(6)         # 1-D coordinate7

Layout Algebra

Concatenation

A Layout can be expressed as the concatenation of its sub-layouts.

julia> layout_2x4[2] # Get the second sub-layout(2, 2):(1, 2)
julia> tuple(layout_2x4...) # Splat a layout into its sub-layouts(2:4, (2, 2):(1, 2))
julia> make_layout(layout_2x4...) # Concatenate sub-layouts(2, (2, 2)):(4, (1, 2))
julia> for sublayout in layout_2x4 # Iterate over sub-layouts
          @show sublayout
       endsublayout = 2:4
sublayout = (2, 2):(1, 2)

Complement

Let's partition a vector of 24 elements into six tiles of four elements each, gathering every fourth element at even indices.

This operation creates a new layout where we collect every second element until we have four, then repeat this for the rest of the vector.

The resulting layout would resemble:

       1    2    3    4    5    6
    +----+----+----+----+----+----+
 1  |  1 |  2 |  9 | 10 | 17 | 18 |
    +----+----+----+----+----+----+
 2  |  3 |  4 | 11 | 12 | 19 | 20 |
    +----+----+----+----+----+----+
 3  |  5 |  6 | 13 | 14 | 21 | 22 |
    +----+----+----+----+----+----+
 4  |  7 |  8 | 15 | 16 | 23 | 24 |
    +----+----+----+----+----+----+

complement computes the first row of this new layout.

julia> print_layout(complement(@Layout(4,2), 24))(_2, 3):(_1, _8)
       1    2    3 
    +----+----+----+
 1  |  1 |  9 | 17 |
    +----+----+----+
 2  |  2 | 10 | 18 |
    +----+----+----+

The Layout(4,2) and its complement give us the desired new layout:

julia> print_layout(make_layout(@Layout(4, 2),complement(@Layout(4, 2), 24)))(_4, (_2, 3)):(_2, (_1, _8))
       1    2    3    4    5    6 
    +----+----+----+----+----+----+
 1  |  1 |  2 |  9 | 10 | 17 | 18 |
    +----+----+----+----+----+----+
 2  |  3 |  4 | 11 | 12 | 19 | 20 |
    +----+----+----+----+----+----+
 3  |  5 |  6 | 13 | 14 | 21 | 22 |
    +----+----+----+----+----+----+
 4  |  7 |  8 | 15 | 16 | 23 | 24 |
    +----+----+----+----+----+----+

Product

Logical Product

julia> tile = @Layout((2,2), (1,2));
julia> print_layout(tile)(_2, _2):(_1, _2)
      1   2 
    +---+---+
 1  | 1 | 3 |
    +---+---+
 2  | 2 | 4 |
    +---+---+
julia> matrix_of_tiles = @Layout((3,4), (4,1));
julia> print_layout(matrix_of_tiles)(_3, _4):(_4, _1)
       1    2    3    4 
    +----+----+----+----+
 1  |  1 |  2 |  3 |  4 |
    +----+----+----+----+
 2  |  5 |  6 |  7 |  8 |
    +----+----+----+----+
 3  |  9 | 10 | 11 | 12 |
    +----+----+----+----+
julia> print_layout(logical_product(tile, matrix_of_tiles))((_2, _2), (_3, _4)):((_1, _2), (_16, _4))
       1    2    3    4    5    6    7    8    9   10   11   12 
    +----+----+----+----+----+----+----+----+----+----+----+----+
 1  |  1 | 17 | 33 |  5 | 21 | 37 |  9 | 25 | 41 | 13 | 29 | 45 |
    +----+----+----+----+----+----+----+----+----+----+----+----+
 2  |  2 | 18 | 34 |  6 | 22 | 38 | 10 | 26 | 42 | 14 | 30 | 46 |
    +----+----+----+----+----+----+----+----+----+----+----+----+
 3  |  3 | 19 | 35 |  7 | 23 | 39 | 11 | 27 | 43 | 15 | 31 | 47 |
    +----+----+----+----+----+----+----+----+----+----+----+----+
 4  |  4 | 20 | 36 |  8 | 24 | 40 | 12 | 28 | 44 | 16 | 32 | 48 |
    +----+----+----+----+----+----+----+----+----+----+----+----+

Blocked Product

julia> print_layout(blocked_product(tile, matrix_of_tiles))((_2, _3), (_2, _4)):((_1, _16), (_2, _4))
       1    2    3    4    5    6    7    8 
    +----+----+----+----+----+----+----+----+
 1  |  1 |  3 |  5 |  7 |  9 | 11 | 13 | 15 |
    +----+----+----+----+----+----+----+----+
 2  |  2 |  4 |  6 |  8 | 10 | 12 | 14 | 16 |
    +----+----+----+----+----+----+----+----+
 3  | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 |
    +----+----+----+----+----+----+----+----+
 4  | 18 | 20 | 22 | 24 | 26 | 28 | 30 | 32 |
    +----+----+----+----+----+----+----+----+
 5  | 33 | 35 | 37 | 39 | 41 | 43 | 45 | 47 |
    +----+----+----+----+----+----+----+----+
 6  | 34 | 36 | 38 | 40 | 42 | 44 | 46 | 48 |
    +----+----+----+----+----+----+----+----+

Raked Product

julia> print_layout(raked_product(tile, matrix_of_tiles))((_3, _2), (_4, _2)):((_16, _1), (_4, _2))
       1    2    3    4    5    6    7    8 
    +----+----+----+----+----+----+----+----+
 1  |  1 |  5 |  9 | 13 |  3 |  7 | 11 | 15 |
    +----+----+----+----+----+----+----+----+
 2  | 17 | 21 | 25 | 29 | 19 | 23 | 27 | 31 |
    +----+----+----+----+----+----+----+----+
 3  | 33 | 37 | 41 | 45 | 35 | 39 | 43 | 47 |
    +----+----+----+----+----+----+----+----+
 4  |  2 |  6 | 10 | 14 |  4 |  8 | 12 | 16 |
    +----+----+----+----+----+----+----+----+
 5  | 18 | 22 | 26 | 30 | 20 | 24 | 28 | 32 |
    +----+----+----+----+----+----+----+----+
 6  | 34 | 38 | 42 | 46 | 36 | 40 | 44 | 48 |
    +----+----+----+----+----+----+----+----+

Division

Logical Division

julia> raked_prod = raked_product(tile, matrix_of_tiles);
julia> subtile = (@Layout(2,3), @Layout(2,4));
julia> print_layout(logical_divide(raked_prod, subtile))((_2, _3), (_2, _4)):((_1, _16), (_2, _4))
       1    2    3    4    5    6    7    8 
    +----+----+----+----+----+----+----+----+
 1  |  1 |  3 |  5 |  7 |  9 | 11 | 13 | 15 |
    +----+----+----+----+----+----+----+----+
 2  |  2 |  4 |  6 |  8 | 10 | 12 | 14 | 16 |
    +----+----+----+----+----+----+----+----+
 3  | 17 | 19 | 21 | 23 | 25 | 27 | 29 | 31 |
    +----+----+----+----+----+----+----+----+
 4  | 18 | 20 | 22 | 24 | 26 | 28 | 30 | 32 |
    +----+----+----+----+----+----+----+----+
 5  | 33 | 35 | 37 | 39 | 41 | 43 | 45 | 47 |
    +----+----+----+----+----+----+----+----+
 6  | 34 | 36 | 38 | 40 | 42 | 44 | 46 | 48 |
    +----+----+----+----+----+----+----+----+

Zipped Division

julia> print_layout(zipped_divide(raked_prod, subtile))((_2, _2), (_3, _4)):((_1, _2), (_16, _4))
       1    2    3    4    5    6    7    8    9   10   11   12 
    +----+----+----+----+----+----+----+----+----+----+----+----+
 1  |  1 | 17 | 33 |  5 | 21 | 37 |  9 | 25 | 41 | 13 | 29 | 45 |
    +----+----+----+----+----+----+----+----+----+----+----+----+
 2  |  2 | 18 | 34 |  6 | 22 | 38 | 10 | 26 | 42 | 14 | 30 | 46 |
    +----+----+----+----+----+----+----+----+----+----+----+----+
 3  |  3 | 19 | 35 |  7 | 23 | 39 | 11 | 27 | 43 | 15 | 31 | 47 |
    +----+----+----+----+----+----+----+----+----+----+----+----+
 4  |  4 | 20 | 36 |  8 | 24 | 40 | 12 | 28 | 44 | 16 | 32 | 48 |
    +----+----+----+----+----+----+----+----+----+----+----+----+