Permutation of elements in array + composition of functions resulting into an extremely inefficient runtime?

Hey there. I have started using Julia today or yesterday, and there is something happening here that is driving me a little bit crazy.

I wanted to model a group of permutations (specifically, the permutation group of a 2x2x2 Rubik’s Cube), which I decided to implement using two arrays: a permutation one, and an orientation one (doesn’t matter too much if you don’t follow that decision, but with these two arrays any valid position of a 2x2x2 puzzle can be represented), as follows:

cp = (1,2,3,4,5,6,7,8) # position of each piece (8 pieces on a 2x2x2 cube)
co = (0,0,0,0,0,0,0,0) # orientation of each piece (how a certain corner is twisted, each one having 3 possible orientations)

The cube has six faces which can be turned 0, 90, 180, or 270 degrees.
My goal is to be able to represent a cube permutation as a single function, given a string of moves like “R U F’ B2” (R=right, U=up, etc).

I then defined some functions that either swap certain elements of one array, or perform a simple addition + mod 3 to the elements of the other:

# Atoms
Rp((a,b,c,d,e,f,g,h)) = (a,c,f,d,e,g,b,h)
Ro(a) = @. (a + [0,1,2,0,0,1,2,0]) % 3
Up((a,b,c,d,e,f,g,h)) = (d,a,b,c,e,f,g,h)
# Uo is not needed since it equals identity
xp((a,b,c,d,e,f,g,h)) = (d,c,f,e,h,g,b,a)
xo(a) = @. (a + [2,1,2,1,2,1,2,1]) % 3

Then, I defined the ‘broader’ functions that use these atoms to act on a tuple that will look like (cp, co), knowing that each move has to first permute both arrays according to their definition, then update the orientation array, again according to their definition:

# Movedefs
R((p,o)) = Rp(p), (Ro∘Rp)(o)
U((p,o)) = Up(p), Up(o) # again no Uo because it is the identity func
x((p,o)) = xp(p), (xo∘xp)(o)

Finally, I defined a bunch of other functions (corresponding to each face + rotations of the cube) using composition (again, doesn’t matter if you’re not familiar with the Rubik’s Cube notation, but x, y, z are rotations that follow R, U, F faces respectively):

D = x ∘ x ∘ U ∘ x ∘ x
y = U ∘ D ∘ D ∘ D
F = x ∘ x ∘ x ∘ U ∘ x
B = y ∘ y ∘ F ∘ y ∘ y
z = F ∘ B ∘ B ∘ B
L = y ∘ y ∘ R ∘ y ∘ y

Then, I wanted to create another procedure that, given a string like “R U F’ B2”, decomposed that into a single function that represents that permutation.
For that example string, it would be this function: B(B(F(F(F(U(R( tuple ))))))). (2 means apply twice, ’ means apply it three times).

So, Googling a little I found about the getfield() func to retrieve a function from a Symbol, and I did this:

# Single move (string) to Move (func) ( i.e. "R" to R(), "F2" to F(F()) )
function m_to_mf(m)
    func = getfield(Main,Symbol(m[1]))
    length(m)==2 ? (m[2]=="2" ? (func∘func) : (func∘func∘func)) : func
end

# String of moves to single func
str_to_func(string) = foldl(∘, map(m_to_mf, reverse(split(string))))

I was all happy with this with the cool looking ∘ and the nice syntax of Julia, but when I timed the execution time I was rather disappointed…

# Running
scramble = "R' U' F R2 B' L2 F2 y x"
cube = (cp, co)

pos = str_to_func(scramble)

@time pos(cube)
# 0.385912 seconds (1.08 M allocations: 56.017 MiB, 1.07% gc time)

Woah! Hold up a second! 1 million allocations? Almost 0.4 seconds for this task?
I am aware that my algorithm isn’t as efficient as it could be, but I believe something is very wrong here (probably with my code, since this is basically my first program in Julia!)

With all that said, what is up with this? How can this be implemented more efficiently, keeping the same idea of defining Move Functions based on others, and transforming a string with moves into a single function?

Thank you for the read!

1 Like

The first time you run the code, it has to be compiled. @time measures the compilation too. Next time it will be faster (even with another scramble, although some compilation is needed again).

julia> @time pos(cube)
  0.328446 seconds (1.08 M allocations: 56.056 MiB, 3.61% gc time)
((1, 7, 6, 4, 3, 8, 5, 2), [2, 1, 0, 2, 0, 0, 0, 1])

julia> # 0.385912 seconds (1.08 M allocations: 56.017 MiB, 1.07% gc time)

julia> @time pos(cube)
  0.000038 seconds (741 allocations: 102.453 KiB)
((1, 7, 6, 4, 3, 8, 5, 2), [2, 1, 0, 2, 0, 0, 0, 1])

julia> scramble = "U' R' F R2 B' L2 F2 y"
"U' R' F R2 B' L2 F2 y"

julia> const cube2 = (cp, co)
((1, 2, 3, 4, 5, 6, 7, 8), (0, 0, 0, 0, 0, 0, 0, 0))

julia> const pos2 = str_to_func(scramble)
#62 (generic function with 1 method)

julia> @time pos2(cube2)
  0.020518 seconds (9.00 k allocations: 436.673 KiB)
((7, 5, 2, 1, 3, 6, 8, 4), (2, 1, 2, 0, 0, 1, 2, 1))

julia> @time pos2(cube2)
  0.000032 seconds (734 allocations: 101.656 KiB)
((7, 5, 2, 1, 3, 6, 8, 4), (2, 1, 2, 0, 0, 1, 2, 1))

For more precise measurement, you should use BenchmarkTools:

julia> using BenchmarkTools

julia> @btime _pos(cube) setup=(_pos=str_to_func(scramble))
  18.735 μs (741 allocations: 102.45 KiB)
((1, 7, 6, 4, 3, 8, 5, 2), [2, 1, 0, 2, 0, 0, 0, 1])

(Edit: Not related to the performance of the generated function , but you can use a Dict to store your move functions)

1 Like

Thanks! Yeah, I spent a while last night reading the docs and found exactly what you’re stating here. The runtime is incredible!

(Oh, also, there was an error in m[2]=="2", changed to m[2]=='2').

This is the second run:

julia> scramble = "R' U' F D2 B2 U2 L2 B2 U2 F2 R' B2 R' U' F' R D2 L D L' U2 F R' U' F"
"R' U' F D2 B2 U2 L2 B2 U2 F2 R' B2 R' U' F' R D2 L D L' U2 F R' U' F"

julia> solution = "U F2 B U B D R2 L2 F2 U' F2 L2 D F2 D' R2 D' B D L B'"
"U F2 B U B D R2 L2 F2 U' F2 L2 D F2 D' R2 D' B D L B'"

julia> cube = (cp, co)
((1, 2, 3, 4, 5, 6, 7, 8), (0, 0, 0, 0, 0, 0, 0, 0))

julia> pos = str_to_func(scramble*" "*solution)
#62 (generic function with 1 method)

julia> @time pos(cube)
  0.000027 seconds (1 allocation: 144 bytes)
((1, 2, 3, 4, 5, 6, 7, 8), (0, 0, 0, 0, 0, 0, 0, 0))

Using BenchmarkTools:

julia> @btime _pos(cube) setup=(_pos=str_to_func(scramble*" "*solution))
  19.999 μs (1 allocation: 144 bytes)
((1, 2, 3, 4, 5, 6, 7, 8), (0, 0, 0, 0, 0, 0, 0, 0))

I must say I am very impressed!

I thought of the Dict approach you mention, since that’s how I usually dealt with this in Python or JavaScript, but having the getfield function made that a little bit cleaner and I’m quite happy with it :slight_smile:

Thank you for your reply. Will continue digging in the docs because they’re majestic!

1 Like

This might be helpful

1 Like

Quite helpful for the first array, but I’m not sure how I could use that ADT for the orientation one :confused:

I think I’ll leave that wonderful library for a future project (15 puzzle perhaps?), since I don’t want to mix Permutations types with regular arrays here. Thank you for bringing it to notice, anyway!

Great to hear that! I had the exact same feeling a year ago. :slight_smile: