What is the best way to implement absolute difference

Brainstorming
1

I often encounter problem of finding absolute difference of 2 unsigned numbers (lets say usize for example). Obvious way @abs(a - b) won’t work since numbers can overflow.

And each time i find new way to implement it.

fn absdiff1(a: usize, b: usize) usize {
    return @max(a, b) - @min(a, b);
}
fn absdiff2(a: usize, b: usize) usize {
    if (a > b) {
        return a - b;
    }
    return b - a;
}
fn absdiff3(a: usize, b: usize) usize {
    return @max(a -| b, b -| a);
}

fn absdiff4(a: usize, b: usize) usize {
    return @min(a -% b, b -% a);
}
// Only works for numbers with known size. 
// From mentioned versions it is the only one which uses `a` and `b` expressions once so it is theoretically usable as inline expression.
fn absdiff5(a: u32, b: u32) u32 {
    return @intCast(@abs(@as(i33, a) - @as(i33, b)));
}

What do you think is the best way? Can you find new clever ways? Maybe winner should be placed into standard library since its pretty common operation?

11 Likes
2

Yess, I had the same problem. Will brainstorm tomorrow morning!

3

Which one generates the best machine code?

1 Like
4

absdiff3 is definitely worst. Others look about the same

5

How’s about this? It is the same asm as absdiff2 and maybe a bit simpler as a one liner.

export fn absdiff6(a: u32, b: u32) u32 {
    return if(a > b) a - b else b - a;
}
2 Likes
6

They all(except for 3) looks same on x86-64, but if switch target to arm64, then 4 looks better

Upd: also checked arm and x86 targets, there too 4 looks best

2 Likes
7

absdiff4 is wrong: absdiff4(0, std.math.maxInt(usize)) is 1 and not std.math.maxInt(usize)

3 Likes
8

I’d think (a - b) & MASK where MASK is the unsigned bit portion of the result would produce a better result, though I haven’t tested as I’m on mobile.

9

Oops, then 2 looks best option for me
And as I understand, correct definition for 4 then:

export fn absdiff4(a: isize, b: isize) usize {
    return @bitCast(@max(a -% b, b -% a));
}
10

now absdiff4(std.math.minInt(isize), std.math.maxInt(isize)) is 1

11

-____-
Alright, next time will not try write code from mobile on the go :smiley:

12

Don’t know if this suitable in this case, but I played a little with asm, so let it be here as i already done it

Also, have no idea if everything wrote correctly, but it compiles and it pass tests that I tried :smiley:

2 Likes
13

I think this is a great exercise and very educational. However, I wouldn’t expect std lib code to be in assembly. Would be nice if the compiler could yield similar assembly code.

1 Like
14

Another concern is eye-balling assembler may not be the best approach to judge this kind of code. In real use the code is likely inlined and potentially could be a different implementation depending on the surrounding code it’s inlined with.

Probably better to benchmark in real use and check mature implementations.

2 Likes
15

-x = ~x +% 1

1 Like