Perform operations with enum discriminant

[maxtremblay]

Hello, I want to use an enum to represent the elements of a multiplicative group (in the mathematical sense). For this enum, I want to define the Mul operator. To make the operation faster, I want to use the fact that the group is isomorphic to GF(2^2). That is, multiplication in this group is similar to bitwise-xor for two bits. Therefore, knowing the representation of the enum, I want my multiplication to be as simple as calling xor on two u8. Something like this

#[derive(Debug, Clone, Copy, PartialEq, Eq, PartialOrd, Ord, Hash)]
#[repr(u8)]
pub struct enum Pauli {
     I = 0, // 00
     X = 1, // 01
     Y = 2, // 10
     Z = 3, // 11
}

// Version 1

impl std::ops::Mul<Pauli> for Pauli {
    type Output = Pauli;

    fn mul(&self, rhs: Pauli) -> Self::Output {
        use Pauli::*; 
        match (self, other) {
             (I, p) | (p, I) => p,
             (X, Y) | (Y, X) => Z,
             (X, Z) | (Z, X) => Y,
             (Y, Z) | (Z, Y) => X,
             _ => I // In this case self == rhs.
         }
    }
}

// Version 2

impl std::ops::Mul<Pauli> for Pauli {
    type Output = Pauli;

    fn mul(self, rhs: Pauli) -> Self::Output {
        // SAFETY: bitwise xor of two numbers chosen from 0, 1, 2 and 3
        // always return a number in the same range. 
        unsafe {
            std::mem::transmute::<Pauli>(
                std::mem::transmute::<u8>(self)
                ^ std::mem::transmute::<u8>(rhs)
            )
        }
    }
}

The first version is really easy to read, but I doubt the compiler will figure out the optimization. In the second version, I am imposing the optimization myself, but this part of the documentation of transmute makes my doubt.

transmute is semantically equivalent to a bitwise move of one type into another. It copies the bits from the source value into the destination value, then forgets the original.

In that case, am I paying the cost of three copies?

Also, is there a better way to implement the multiplication?

[Michael-F-Bryan]

@maxtremblay

In that case, am I paying the cost of three copies?

Sure, but keep in mind that you're copying a u8 (1 byte), whereas if we passed around a reference, we'd be copying a usize (8 bytes plus an extra level of indirection).

Sometimes it's more efficient to copy a value than to use references.

@maxtremblay

Also, is there a better way to implement the multiplication?

This is my implementation:

impl std::ops::Mul<Pauli> for Pauli {
    type Output = Pauli;

    fn mul(self, rhs: Pauli) -> Self::Output {
        match self as u8 ^ rhs as u8 {
            0b00 => Pauli::I,
            0b01 => Pauli::X,
            0b10 => Pauli::Y,
            0b11 => Pauli::Z,
            _ => unreachable!(),
        }
    }
}

(playground)

When compiled in release mode, it generated the following assembly:

<playground::Pauli as core::ops::arith::Mul>::mul:
	mov	eax, edi
	xor	eax, esi
	ret

[maxtremblay]

Thank you for the answer. I wasn't aware that the rust playground support generating the assembly code. Really nice. I tested it and both your solution and the one with transmute yield exactly the same assembly. In fact, as you can see from here, the compiler set them to exactly the same thing.

.set playground::Pauli::third_mul, playground::Pauli::second_mul

[tczajka]

@maxtremblay

To make the operation faster, I want to use the fact that the group is isomorphic to GF(2^2). That is, multiplication in this group is similar to bitwise-xor for two bits.

Nitpicking: this is a bit confusing because multiplication in the Galois Field GF(4) is different from xor. Addition in GF(4) is xor. I think you may want to call it the Z₂² group instead.

Anyway, yes, the compiler will generally eliminate unnecessary copies of small data in registers.

A bit unfortunate that the compiler can't figure out the xor pattern from a small table