N-Queens on 50g (RPL language)

[Claudio L.]

(10-31-2014 11:21 PM)Claudio L. Wrote:  

• Recursive stack: userRPL = 29.7 seconds. newRPL = 111 ms
• Werner's stack (see below): userRPL = 22.6 seconds. newRPL = 141 ms
  

I was able to run things on newRPL and updated the original post with the new results.
Interestingly, the recursive algorithm runs faster than Werner's stack algorithm on newRPL, while the opposite is true for userRPL.
This shows how different optimizations work on different platforms. I believe the difference is in the use of local variables: userRPL does a search by name within the environment, while the newRPL compiler is capable of optimizing into PUTLAM/GETLAM style operations at compile time, making the use of named local variables just as efficient as using the stack.

Then, the recursive algorithm is theoretically supposed to be faster, since it only checks 301 cases versus the 876 of the general algorithm. Not 3 times faster as the number of checks would suggest, since the recursive algorithm wastes some time shuffling numbers in the stack, and the discarded cases are so trivial the other algorithm doesn't take too much time on them, but should be a little faster. When running on userRPL it takes a big hit for using variables, enough to overturn the results.

Another interesting observation is that the speedup ratio between the slowest algorithm (the original one) vs the fastest on each platform is very different: 3.98x for userRPL and 2.04x for newRPL. This is also likely due to the smarter compiler in newRPL speeding up things.