Generics as function parameters

Help
1

Hey !

Recently I’ve had to pass generics with lots of function parameters as an argument to a function.

What I’ve ended doing is :

pub fn factorization(x: anytype) Result(x) {
  const a = asMatrix(x);
  // ...
}

pub fn asMatrix(x: anytype) Matrix(x.Scalar, x.size[0], x.size[1]) {
  assert(@TypeOf(x) == Matrix(x.Scalar, x.size[0], x.size[1])
  return x;
}

But I have two issues with my solution :

  1. It seems to be non-idiomatic zig code, and I’ve studied std for a bit and the solution they seem to pass the generic’s arguments as a parameter (which is not ideal)
  2. The errors generated by it are not good (when you don’t pass a matrix type, as it seems like the result is evaluated first)

But the main advantage of using it is that I can switch on the type (like interpret the array as a matrix if the type is not one). This last advantage is what I mainly use in my code but I’ve reduced it to this case.

What are you guys thoughts ? What would you use ? What do you do in your codebases ? What is zig’s idiomatic way ?

2

Result(x) makes me think you should split this up into multiple separate functions, perhaps sharing some common subroutine. fn factorArray(x: Array) Array and fn factorMatrix(x: Matrix) Matrix. (Or I suppose fn factorMatrix(x: Matrix) [2]Matrix?)

It seems you’re making your function names easy to remember at the expense of weakening the type system, which seems questionable to me.

1 Like
3

If I pretend that you instead wanted fn factorization(x: anytype) [2]Matrix, I might suggest something I’ve been trying recently:

pub const MatrixRepresentation = struct {
  matrix: Matrix,

  pub fn fromMatrix(matrix: Matrix) MatrixRepresentation {
    return .{ .matrix = matrix };
  }

  pub fn fromArray(arr: Array) MatrixRepresentation {
    return .{ .matrix = @bitCast(arr) };
  }
};

pub fn factorization(repr: MatrixRepresentation) [2]Matrix {
  const a = repr.matrix;
  // ...
}

(insert your own conversion logic if the @bitCast is insufficient)

This lets you write

const f1 = factorization(.fromMatrix(myMatrix));
const f2 = factorization(.fromArray(myArray));

Overall this is pretty similar to my initial fn factorArray/fn factorMatrix suggestion, but it also lets you store a MatrixRepresentation, which can be pretty nice.

I use something similar to this for gamedev, giving myself multiple ways to specify a quad from a spritesheet or on the screen:

/// A helper to make draw() nice to use, e.g.:
///   try gfx.draw(.id(4), .pos(10, 20));
/// Its layout matches the layout of c.SDL_FRect
pub const Quad = extern struct {
    /// position in pixels
    x: f32,
    /// position in pixels
    y: f32,
    /// size in pixels
    w: f32,
    /// size in pixels
    h: f32,

    pub fn id(n: u16) Quad {
        return grid(
            @floatFromInt(n % sprites.width_cells),
            @floatFromInt(@divFloor(n, sprites.width_cells)),
        );
    }

    pub fn grid(cx: f32, cy: f32) Quad {
        assert(0 <= cx and cx < sprites.width_cells);
        assert(0 <= cy and cy < sprites.height_cells);
        return .{ .x = cx * 8, .y = cy * 8, .w = 8, .h = 8 };
    }

    pub fn pixel(x: f32, y: f32) Quad {
        return .{ .x = x, .y = y, .w = 8, .h = 8 };
    }

    pub fn pixelSdl(p: c.SDL_FPoint) Quad {
        return .{ .x = p.x, .y = p.y, .w = 8, .h = 8 };
    }

    pub fn rect(r: c.SDL_FRect) Quad {
        const res: Quad = @bitCast(r);
        assert(r.x == res.x);
        assert(r.y == res.y);
        assert(r.w == res.w);
        assert(r.h == res.h);
        return res;
    }

    pub fn toSdl(quad: Quad) c.SDL_FRect {
        const res: c.SDL_FRect = @bitCast(quad);
        assert(quad.x == res.x);
        assert(quad.y == res.y);
        assert(quad.w == res.w);
        assert(quad.h == res.h);
        return res;
    }
};

The dependency on the sprites global is a bit awkward, but it makes this nice to use and the game only has one spritesheet. Not ideal, but fine for now.

3 Likes
4

I put Result(x) just because I was on my phone and could not be bothered haha.

In reality, it is a struct containing two matrices (one square, on rect) with sizes inferred from x. Where I use the same asMatrix trick.

Note that asMatrix does the conversion from array to matrix if needed but I put the simplified case as my question was more about the way of using generics as function arguments than my current implementation.

5

I see !

It looks a bit like doing vtables. Could vtables also be a solution to this problem then ? I’m a bit worried about performance.

I’m talking about subtypes like sparse matrix, diagonal, etc. to optimize memory space.

6

I would absolutely recommend against using vtables for any sort of serious linear algebra work.

On the topic, I avoid anytype as much as possible, for my implementation of this, I used a single generic namespace with all the implementation parametrized in the outer scope:

pub fn matrixMxNT(comptime M: comptime_int, comptime N: comptime_int, comptime T: type) type {
    return struct {
        pub const Self = types.MatrixMxNT(M, N, T); // [M][N]T
        pub const Vector = types.VectorNT(N, T); // [N]T
        pub const Scalar = T;
        pub const rows = M;
        pub const cols = N;
        pub const len: usize = M * N;

        pub fn scale(self: *Self, multiplier: Scalar) void {
            const s = slice(self);
            for (0..len) |n| s[n] *= multiplier;
        }

        pub fn apply(result: *vector.Self, operation: *const Self, operand: *const vector.Self) void {
            for (0..rows) |y| vector.dotInto(&result[y], &operation[y], operand);
        }
    };
}

Which the user can then instantiate for their specific odd usecase, and provide some reasonable baseline:

pub const matrix3x3 = matrixMxNT(3, 3, types.Scalar);
pub const matrix3x3f64 = matrixMxNT(3, 3, types.Scalar64);
pub const matrix4x4 = matrixMxNT(4, 4, types.Scalar);
pub const matrix4x4f64 = matrixMxNT(4, 4, types.Scalar64);

This might not fit well for your usecase (if you need a lot of different arbitrary dimensions), but I prefer it works fairly well for standard engineering e.g. games and physics.

One cave-at is that it is kinda annoying to do conditionals (e.g. only a 3D vector has defined a cross-product), but I still keep only one namespace and use a comptime guard:

        pub fn cross(result: *Self, lhs: *const Self, rhs: *const Self) void {
            comptime if (len == 3) {} else @compileError("cross not supported for vector of " ++ len);
            result[0] = lhs[1] * rhs[2] - lhs[2] * rhs[1];
            result[1] = lhs[2] * rhs[0] - lhs[0] * rhs[2];
            result[2] = lhs[0] * rhs[1] - lhs[1] * rhs[0];
        }
3 Likes
7

This is what I’m currently doing however I have a few problems with this approach :

  • it can’t handle sparse array / matrix (or I add a comptime parameter to handle it but again feels like a hack)
  • when passing it as a parameter you need to use either anytype or pass all dimensions (which is not ideal) as I won’t want to have all algorithms defined in one struct

This is why I ended using anytype combined with asMatrix but this feels more like a hack than anything.

8

I would question whether setting the matrix size at compile time really gains you much. I’m all for setting the element type, but the sizes tend to control the number of loop iterations in operations.

I’m not convinced a runtime sized loop would be any slower.

2 Likes
9

It was to have comptime type safety but I see what you mean.

It also allowed to have matrices on the stack with fixed size buffers. So I didn’t have to bother with allocators and having a deinit and stuff (simpler DX)

I also like being able to generate errors at comptime for invalid sizes (squares, power of twos, etc.).

1 Like
10

There is absolutely a distinction between an arbitrary sized matrix implementation and a compile time fixed size matrix implementation. There would even be a performance one for sure. Knowing the constants at comptime isn’t just for the loop to load from an immediate instead of memory, it unties the compilers hands in unrolling, auto-vectorization etc., especially when dealing with dimensions of power of 2.

I’d distinguish by use case, so if you need general matrix library akin to numpy I’d go with something like

const Matrix = struct {
    rows: u32,
    cols: u32,
    // Always worth trying type instead of VTable if the interface isn't unbounded.
    type: enum { dense, sparse },
    data: *anyopaque,
};

If you want high performance dynamic sizes with single impl I’d still go with static dispatch and finding an optimal way to parametrize the implementations, this is what I usually do for arbitrary comptime config static dispatch:

fn algorithm(lhs: Matrix, rhs: Matrix) ? {
    return switch(lhs.type) {
        inline else => |lhs_type| => switch (rhs.type) {
            inline else => |rhs_type| algorithmImpl(
                .{ .lhs = MatrixImpl(lhs_type), .rhs = MatrixImpl(rhs_type) }, 
                .{ .rows = lhs.rows, .cols = lhs.cols, .data = @ptrCast(lhs.data) },
                .{ .rows = lhs.rows, .cols = rhs.cols, .data = @ptrCast(rhs.data) },
            ),
        },
    }
}

fn algorithmImpl(
    // or config: struct { bools, enums, ... } whatever dimensions of the interface
    comptime impl: struct { lhs: type, rhs: type }, 
    lhs: *const impl.lhs.Self,
    rhs: *const impl.rhs.Self) ? {
    lhs.factorize(
}

But for things like glm, where you need m4x4, m3x3, m2x2, I’d hand-roll for sure.

3 Likes
11

In the end, I used union(enum) following what you gave.

I have two fields in my struct : size (for the size of the 2d array) and repr (internal representation).

Using a union(enum), I was able to implement most of the sparse matrices formats I wanted to add (column, row, diag, coordinate, map, block and list of lists) as well as the “full” matrix (with all indices).

The added benefits is that certain functions that are incompatible with certain formats now get an error. The union also forces me to treat all cases, thinking about format-specific optimizations.

A disadvantage is that invalid sizes are runtime errors and matrices are using an allocator.

Thanks everyone.

1 Like
12

Great!, be aware you can use std.heap.FixedBufferAllocator to allocate on the stack. I’d consider it a trade-off not an inherent disadvantage, since you get compatibility into the rest of Zig code, and it’s a pretty standard thing to do.

1 Like
13

Yeah but that’s a thing for the end user to do.

I would have preferred to have a stack by default on small array and only use heap on big arrays. This is a choice moved to the end user but I would have preferred that I made that choice.

Anyways, it is the most idiomatic zig solution so my question is definitely solved.

(Just realized I was on the brainstorming category… Oops! TUIs are not always great)

14

You can do SBO (small buffer optimization) and embbed a fixed size data array (e.g. 4x4) to every matrix. It wastes space and increases complexity, and is also kinda antagonistic to the Allocator interface, but it is a thing other libraries do sometimes, esp. in things like C or C++.

But I think that with fixed buffer allocator it’s kind of redundant.

1 Like
15

This is interesting to explore. I’ll definitely add this to my library but probably behind a build option and by default off.

As this would be a great optimization for gamedev or else where there is a lot of small matrices, i feel that 64 bytes wasted per matrix is a lot.

I’l definitely run some benchmarks, thanks a lot for the suggestion.

1 Like