I wrote some test code to apply a 108-move scramble 20 million times. The moves were single-layer moves. On my Core i7-920, it took 2 minutes and 4 seconds. That works out to about 17,419,000 moves per second. This was using the GNU 64-bit C++ compiler. So oo4x4x4's move code is about 50% faster on my machine assuming the move code was dominating its speed test run time, perhaps more if significant time was being spent elsewhere.I note my code uses a cubie level rather than a facelet level representation. A cubie level is probably better for generating pruning table indices, and the speed of generating pruning table indices may be as important as the raw speed of making moves.
Thanks. I wasn't sure how much is gained at the cubie level. My own attempts did not do that well, perhaps I am not understanding it. And, once conjoined with other parts of my code, the cubie-ish stuff I wrote turned out to be a detriment, as I had to make a lot of back-and-forth conversions between move generator output and pruning data/TFS data.
My code could be optimized better. For instance, the basic move routine makes three function calls, one for moving each piece type. (This is for the case of single-layer moves. Multiple-layer moves are more involved.)
Yes, I know the feeling. I wasted a great deal of time profiling to try and eek out a few points worth of performance here and there. That's why I started over with a blank sheet of paper. The old code hit a max of 92,000,000 moves per second using all 16-cores in the most parallel version I had up and running on this machine, but I forget what the single core number was. A linear division by 16 is not perfectly applicable, but doing that would have it at around 5,750,000 per second on my 3.1 GHz cores. I think the speed was right around 10,000,000 per second on one core, so the rewrite from matrices to the new 64-bit boards resulted in a 2.8 times speed increase.
Using bitboards, every single move (no block turns or
compound moves) is exactly 6 instructions.
Making the face move R:
Code:
BITBOARD_4x4x4_CUBE R_PLUS(BITBOARD_4x4x4_CUBE original_4x4x4_cube)
{
BITBOARD_4x4x4_CUBE new_cube;
/**************************************************************************/
/* Rotating the right will change something on every face except the left */
/**************************************************************************/
new_cube._4x4x4_left = original_4x4x4_cube._4x4x4_left;
/********************************************************************************************/
/* Entire row of cubes moves from front -----> top -----> back -----> bottom -----> front */
/* new top = old front; new back = old top; new bottom = old back; new front = old bottom */
/********************************************************************************************/
new_cube._4x4x4_top = (original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_NOT_COL_04) | (original_4x4x4_cube._4x4x4_front & BITMASK_CUBE_FACE_COL_04);
new_cube._4x4x4_back = (original_4x4x4_cube._4x4x4_back & BITMASK_CUBE_FACE_NOT_COL_01) | ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_16) << 60) | ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_12) << 28) | ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_08) >> 4) | ((original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_SQUARE_04) >> 36);
new_cube._4x4x4_bottom = (original_4x4x4_cube._4x4x4_bottom & BITMASK_CUBE_FACE_NOT_COL_04) | ((original_4x4x4_cube._4x4x4_back & BITMASK_CUBE_FACE_SQUARE_01) >> 60) | ((original_4x4x4_cube._4x4x4_back & BITMASK_CUBE_FACE_SQUARE_05) >> 28) | ((original_4x4x4_cube._4x4x4_back & BITMASK_CUBE_FACE_SQUARE_09) << 4) | ((original_4x4x4_cube._4x4x4_back & BITMASK_CUBE_FACE_SQUARE_13) << 36);
new_cube._4x4x4_front = (original_4x4x4_cube._4x4x4_front & BITMASK_CUBE_FACE_NOT_COL_04) | (original_4x4x4_cube._4x4x4_bottom & BITMASK_CUBE_FACE_COL_04);
/*********************************************************************************/
/* */
/* THESE CUBE LOCATIONS BECOME.... THESE CUBE LOCATIONS */
/* */
/* */
/*********************************/ /*********************************/
/* 01 * 02 * 03 * 04 */ /* 13 * 09 * 05 * 01 */
/*********************************/ /*********************************/
/* 05 * 06 * 07 * 08 */ /* 14 * 10 * 06 * 02 */
/*********************************/ /*********************************/
/* 09 * 10 * 11 * 12 */ /* 15 * 11 * 07 * 03 */
/*********************************/ /*********************************/
/* 13 * 14 * 15 * 16 */ /* 16 * 12 * 08 * 04 */
/*********************************/ /*********************************/
/* */
/* */
/*********************************************************************************/
new_cube._4x4x4_right = ((original_4x4x4_cube._4x4x4_right & BITMASK_CUBE_FACE_SQUARE_13) << 48) | \
((original_4x4x4_cube._4x4x4_right & BITMASK_CUBE_FACE_SQUARE_09) << 28) | \
((original_4x4x4_cube._4x4x4_right & BITMASK_CUBE_FACE_SQUARE_05) << 8) | \
((original_4x4x4_cube._4x4x4_right & BITMASK_CUBE_FACE_SQUARE_01) >> 12) | \
((original_4x4x4_cube._4x4x4_right & BITMASK_CUBE_FACE_SQUARE_14) << 36) | \
((original_4x4x4_cube._4x4x4_right & BITMASK_CUBE_FACE_SQUARE_10) << 16) | \
((original_4x4x4_cube._4x4x4_right & BITMASK_CUBE_FACE_SQUARE_06) >> 4) | \
((original_4x4x4_cube._4x4x4_right & BITMASK_CUBE_FACE_SQUARE_02) >> 24) | \
((original_4x4x4_cube._4x4x4_right & BITMASK_CUBE_FACE_SQUARE_15) << 24) | \
((original_4x4x4_cube._4x4x4_right & BITMASK_CUBE_FACE_SQUARE_11) << 4) | \
((original_4x4x4_cube._4x4x4_right & BITMASK_CUBE_FACE_SQUARE_07) >> 16) | \
((original_4x4x4_cube._4x4x4_right & BITMASK_CUBE_FACE_SQUARE_03) >> 36) | \
((original_4x4x4_cube._4x4x4_right & BITMASK_CUBE_FACE_SQUARE_16) << 12) | \
((original_4x4x4_cube._4x4x4_right & BITMASK_CUBE_FACE_SQUARE_12) >> 8) | \
((original_4x4x4_cube._4x4x4_right & BITMASK_CUBE_FACE_SQUARE_08) >> 28) | \
((original_4x4x4_cube._4x4x4_right & BITMASK_CUBE_FACE_SQUARE_04) >> 48);
return new_cube;
}
The rotation code is technically still one instruction even though it is cascading bit-ANDs and bit-shifts.
Making the slice move r'
Code:
BITBOARD_4x4x4_CUBE r_MINUS(BITBOARD_4x4x4_CUBE original_4x4x4_cube)
{
BITBOARD_4x4x4_CUBE new_cube;
/********************************************************************/
/* Rotating the right slice will not change the right or left faces */
/********************************************************************/
new_cube._4x4x4_right = original_4x4x4_cube._4x4x4_right;
new_cube._4x4x4_left = original_4x4x4_cube._4x4x4_left;
/*********************************************************************************************/
/* Entire columns of cubes move from top -----> front -----> bottom -----> back -----> top */
/* new front = old top; new bottom = old front; new back = old bottom; new top = old back */
/*********************************************************************************************/
new_cube._4x4x4_top = (original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_NOT_COL_03) | ((original_4x4x4_cube._4x4x4_back & BITMASK_CUBE_FACE_SQUARE_14) << 44) | ((original_4x4x4_cube._4x4x4_back & BITMASK_CUBE_FACE_SQUARE_10) << 12) | ((original_4x4x4_cube._4x4x4_back & BITMASK_CUBE_FACE_SQUARE_06) >> 20) | ((original_4x4x4_cube._4x4x4_back & BITMASK_CUBE_FACE_SQUARE_02) >> 52);
new_cube._4x4x4_back = (original_4x4x4_cube._4x4x4_back & BITMASK_CUBE_FACE_NOT_COL_02) | ((original_4x4x4_cube._4x4x4_bottom & BITMASK_CUBE_FACE_SQUARE_15) << 52) | ((original_4x4x4_cube._4x4x4_bottom & BITMASK_CUBE_FACE_SQUARE_11) << 20) | ((original_4x4x4_cube._4x4x4_bottom & BITMASK_CUBE_FACE_SQUARE_07) >> 12) | ((original_4x4x4_cube._4x4x4_bottom & BITMASK_CUBE_FACE_SQUARE_03) >> 44);
new_cube._4x4x4_bottom = (original_4x4x4_cube._4x4x4_bottom & BITMASK_CUBE_FACE_NOT_COL_03) | (original_4x4x4_cube._4x4x4_front & BITMASK_CUBE_FACE_COL_03);
new_cube._4x4x4_front = (original_4x4x4_cube._4x4x4_front & BITMASK_CUBE_FACE_NOT_COL_03) | (original_4x4x4_cube._4x4x4_top & BITMASK_CUBE_FACE_COL_03);
return new_cube;
}
Even though the slice turns make no rotations of whole faces, they are still 6 lines of code, since 2 entire unaffected faces must have their 64-bit data copied as opposed to only 1 for face turns.
By the way, speaking of single-threaded or multithreaded code, if you add multithreading support, I really hope you allow the user to have control over how many (cpu intensive) threads are allowed. I will not want other programs on my computer impacted terribly by your program trying to make use of every available virtual core.
I have all of your notes from prior posts in separate notebook. I added the code to specify which TFS databases to load, and I will have another interface option when a multi-core CPU is detected. I'm just going to have base-2 core counts as choices for those with the available cores (1,2,4,8,16,32) although a sweet 60-core server is available in the Intel Xeon E7-8895 v2 which has 15 CPU cores and 4-ways (even 8-way) capability. I've built a few 4-way systems but no 8-socket motherboards are out yet that I am aware of.
For your internal code, there is nothing wrong with using viewing the cube from the U/R/F sides for turn directions. But if you want the code to be embraced by the speedcubing community, you should have (at least as an option) the input and output be in terms of conventions of the speedcubing community.
I coded with conversion to input/output in mind. When I "think" about the cube, I need to use my own system. Remember all of the errors in my earlier databases? That was mostly from not handling L and B properly. I had to remember "L = opposite of R" but when the move generator makes a move, the Turns-From-Solved database needs to reverse the move in order to solve it. It gave me fits! For some reason I had no problems dealing with D moves, must have been just a mental block on my part.
The speedcubing community conventions started from Singmaster's notation for the 3x3x3 cube, where basically only face turns were considered by Singmaster to matter. By having the turn direction being determined by looking at the face being moved, there was no need to have to remember which three faces were considered as preferred faces. This was the big advantage of defining the face turns the way they were. This, of course, broke down when people wanted to use (central) inner layer turns and whole cube rotations, where there is no avoiding having three faces serving as reference faces. To make matters worse, the standards that developed for cube rotations and (central) inner layer turns were not made consistent with each other (except for S and z).
I am OK with it. It is my own subjective opinion that my 4x4x4 notation makes more sense. But the 5x5x5 notation system has additional absurdities.
1. Middle slices are capital letters. That goes against the grain of all other slices being lower case.
2. By definition the middle slice is non-orientable. If you define a primed center slice move to follow a particular face, then why not continue along the same direction and adopt the convention I use?
3. My 5x5x5 notation solves the conundrum in item #2 above, and the implementation and execution thereof causes no pain to the cuber.
I am leaning towards only having my notation system in the 5x5x5 brute force solver but that is subject to change.
But I do appreciate the info. I was on West Chester Pike today during the snow, but no further out than Goshen township. I wasn't too far from you though.
