The fastest Rubik's cube representations in programming

[a person who cubes]

When people write Rubik's cube solvers or algorithm finders they often use suboptimal Rubik's cube representations and suboptimal composition (move application) and inversion operations. I was motivated to develop and formalize the fastest known techniques for these common operations in programming: https://gist.github.com/ArhanChaudhary/51bef8e39312f45f8d9c9cdc44f1f9ba

• On Intel machines I managed to get Rubik's cube composition to 5 instructions (averaging 700M/sec) and inversion to 26 instructions (averaging 175M/sec).
• On Apple machines I managed to get Rubik's cube composition to 19 instructions (averaging 870M/sec) and inversion to 48 instructions (averaging 400M/sec).

I have yet to write SIMD for WASM, but I will do that eventually!

 

[Deleted member 36445]

how is this faster than stuff written by @rokicki

 

[a person who cubes]

how is this faster than stuff written by @rokicki

nxopt does not use SIMD but rather a move table. This was a reasonable decision because AVX2 wasn't even invented at the time it was written. An optimal Rubik's Cube solver that uses this representation (https://github.com/Voltara/vcube) benchmarks at ~20-50% faster. The reason why SIMD is so fast is because it takes advantage of special hardware instructions to perform Rubik's Cube operations extremely efficiently (i.e. VPSHUFB on AVX2, and tbl.{u8,16} on ARM64)

 

[Bruce MacKenzie]

The cubiies of the cube arrive at their positions and orientations by a series of 90˚ rotations about the axes of the cube. The closure of these rotations is the Cubic Rotational Symmetry Group. I represent cube states with a 20 byte list of geometric transforms which will rotate each cubie from its home position to its present position and orientation. The composition of two states simply involves looking up positions in a lookup table and products in the Cubic Group product table.

// The geometric transform of a cubie in the product is equal to the product of the transform
// in the operator at the cubie's present position and its present transform

-(void)getProductRep: (CM_DATA_TYPE *)product
ofOperatorRep: (const CM_DATA_TYPE *)operator
andStateRep: (const CM_DATA_TYPE *)state
{
RM_Cubie cubie, cubicle;

for( cubie = 0 ; cubie < 20 ; cubie++ )
{
cubicle = [self positionOfCubie: cubie
inState: state[cubie]]; // Look up the position of cubie in the position table

product[cubie] = [cubicGroup productOfOperatorTag: operator[ cubicle ] // Look up the new state of cubie in the cubic group mult. table
stateTag: state[ cubie] ];
}
}

//The inverse of a cube state has the Cubic Group inverse of its present state in Its present position

-(void)getInverseRep: (CM_DATA_TYPE *)inverse ofStateRep: (const CM_DATA_TYPE *)state
{
RM_Cubie cubie;

for( cubie = 0 ; cubie < 20 ; cubie++ )
inverse[ positionTable[ cubie ][ state[cubie] ] ] = [cubicGroup inverseOfTag: state[cubie] ];
}

 

[a person who cubes]

The cubiies of the cube arrive at their positions and orientations by a series of 90˚ rotations about the axes of the cube. The closure of these rotations is the Cubic Rotational Symmetry Group. I represent cube states with a 20 byte list of geometric transforms which will rotate each cubie from its home position to its present position and orientation. The composition of two states simply involves looking up positions in a lookup table and products in the Cubic Group product table.

// The geometric transform of a cubie in the product is equal to the product of the transform
// in the operator at the cubie's present position and its present transform

-(void)getProductRep: (CM_DATA_TYPE *)product
ofOperatorRep: (const CM_DATA_TYPE *)operator
andStateRep: (const CM_DATA_TYPE *)state
{
RM_Cubie cubie, cubicle;

for( cubie = 0 ; cubie < 20 ; cubie++ )
{
cubicle = [self positionOfCubie: cubie
inState: state[cubie]]; // Look up the position of cubie in the position table

product[cubie] = [cubicGroup productOfOperatorTag: operator[ cubicle ] // Look up the new state of cubie in the cubic group mult. table
stateTag: state[ cubie] ];
}
}

I think reading from memory is significantly slower compared to the SIMD instructions which run directly on CPU registers, plus the overhead of copying 20 bytes around. Do you have any benchmarks on this?

 

[Bruce MacKenzie]

I think reading from memory is significantly slower compared to the SIMD instructions which run directly on CPU registers, plus the overhead of copying 20 bytes around. Do you have any benchmarks on this?

No I don't. Could you propose a problem that I could time the solution?

 

[Bruce MacKenzie]

I think reading from memory is significantly slower compared to the SIMD instructions which run directly on CPU registers, plus the overhead of copying 20 bytes around. Do you have any benchmarks on this?

Here's a test I just ran on my IMac M4


-(void)test3: (NSString *)input
{
NSDate *start;
NSTimeInterval elapsed;
NSInteger count;
OSG_SYMTAG action[1000][20],
state[1000][20],
product[1000][20];

for( count = 0 ; count < 1000 ; count++)
{
[[self randomState] getBytes: action[count] length: sizeof( OSG_SYMTAG [20]) ];
[[self randomState] getBytes: state[count] length: sizeof( OSG_SYMTAG [20]) ];
}

start = [NSDate date];

for( count = 0 ; count < 1000 ; count++ )
{
[self getProductRep: product[count]
ofActionRep: action[count]
andStateRep: state[count]];
}
elapsed = -[start timeIntervalSinceNow];

[self report: [NSString stringWithFormat: @"\nElapsed %f seconds" , elapsed ]];


}



_DEVELOP
Elapsed 0.000076 seconds

_DEVELOP
Elapsed 0.000077 seconds

_DEVELOP
Elapsed 0.000074 seconds

_DEVELOP
Elapsed 0.000075 seconds

_DEVELOP
Elapsed 0.000075 seconds

_DEVELOP
Elapsed 0.000073 seconds

_DEVELOP
Elapsed 0.000078 seconds

_DEVELOP
Elapsed 0.000078 seconds

_DEVELOP
Elapsed 0.000074 seconds

_DEVELOP
Elapsed 0.000075 seconds

_DEVELOP
Elapsed 0.000077 seconds

 

[Bruce MacKenzie]

I represent cube states with a 20 byte list of geometric transforms which will rotate each cubie from its home position to its present position and orientation.

Here's some background info on the representation of the Cubic Symmetry Group. I thought some readers might find it useful.