Optimizing math on 2 values in a struct

Help
1

I have this struct down here, which works fine.
But wondering if it is possible to replace the two fields with one i32 value to optimize the operations, putting mg and eg into the lower and higher 16 bits.

When doing that I need 2 extra functions:
fn mg(self: Pair) i16 and fn eg(self: Pair) i16.
The math operations (inc, dec, sub, add) will be called many many milliions of times.
The 2 required new functions not so often (0.1% of that).

That said: mg and eg will never overflow or underflow (by design).
And wondering if there will be speedup before diving into the bit tricks…

Or will this be “SIMDed” automatically by zig??

pub const Pair = struct {
    mg: i16,
    eg: i16,

    pub const empty: Pair = .{ .mg = 0, .eg = 0 };

    pub fn init(mg: i16, eg: i16) Pair {
        return .{ .mg = mg, .eg = eg };
    }

    pub fn inc(self: *Pair, sp: Pair) void {
        self.mg += sp.mg;
        self.eg += sp.eg;
    }

    pub fn dec(self: *Pair, sp: Pair) void {
        self.mg -= sp.mg;
        self.eg -= sp.eg;
    }

    pub fn add(self: Pair, other: Pair) Pair {
        return .{ .mg = self.mg + other.mg, .eg = self.eg + other.eg };
    }

    pub fn sub(self: Pair, other: Pair) Pair {
        return .{ .mg = self.mg - other.mg, .eg = self.eg - other.eg };
    }
};
2

I don’t think vectorizing would help here, 32 bits comfortably fit into a single gp register so the overhead of setting up the simd registers and extracting only the needed 32 bits probably outweighs any benefit.

Looking at the generated assembly, the compiler seems to be pretty smart about everything and basically already does what you’ve suggested, it’s using a single register and just shifting things around a bit. inc and dec look pretty optimal, maybe a similiar approach for add and sub is a little faster/slower than the bitmasking that the compiler does but you’d have to benchmark that, it’s probably equally as fast.

I would look into performing operations on multiple pairs in batches if you want a potential SIMD speedup, though the compiler probably already does that for you if you perform an operation in a loop.

1 Like
3

This seems to be a good use case for packed struct. Note that it is different from extern struct in memory layout. The field layout of packed struct is logically low to high, which means it is always equivalent to (@as(i32, eg) << 16 | mg. extern struct is always from low byte to high byte, so it may be represented differently from packed struct on big-endian systems.

pub const Pair = packed struct(i32) {
    mg: i16,
    eg: i16,

    pub const empty: Pair = .{ .mg = 0, .eg = 0 };

    pub fn init(mg: i16, eg: i16) Pair {
        return .{ .mg = mg, .eg = eg };
    }

    pub fn inc(self: *Pair, sp: Pair) void {
        self.mg += sp.mg;
        self.eg += sp.eg;
    }

    pub fn dec(self: *Pair, sp: Pair) void {
        self.mg -= sp.mg;
        self.eg -= sp.eg;
    }

    pub fn add(self: Pair, other: Pair) Pair {
        return .{ .mg = self.mg + other.mg, .eg = self.eg + other.eg };
    }

    pub fn sub(self: Pair, other: Pair) Pair {
        return .{ .mg = self.mg - other.mg, .eg = self.eg - other.eg };
    }
};
1 Like
4

Oh thanks! You used a extern struct to view the asm output. Smart.

5

That’s called SWAR (SIMD within a register), usually you’d keep one bit reserved between items to stop overflow from propagating into the next item:

const val: u16  = 0b0000000000000000;
const add: u16  = 0b0000000100000001;
const mask: u16 = 0b0111111101111111;
const res: u16 = (a +% b) & mask;

It gets tricky for underflows though… and whether it’s worth the hassle for just two operations is very questionable… as long as there are no interdependencies, modern superscalar CPU should be able to run a couple of such simple operations in parallel anyway.

6 Likes