WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution

[Claudio L.]

(10-17-2014 08:02 PM)patrice Wrote:  There is a problem with the benchmark, the way it is done. It is biaised in more than one way from the beginning.

1) Algorithm chosen: is it not the most powerful. It prevent some calculators from showing their full potential. Ex: hp16C wp34s

2)THe reference source code (BASIC) is poorly written. It use a double array access in the inner loop when a single array access is enough.
- Problem, C code is allowed and C compilers are smart enough to detect that one of the array access is a constant inside the loop and optimize it. Is it fair ?
- Problem, C/RegVars code is directly using a single array access, it is an advantage. Is it fair ?

I think the array access issue is minor, and doesn't fundamentally change the algorithm (you still have to explore the same number of nodes and do exactly the same tasks.
And if a particular language has the ability to do optimization and use register variables with a simple statement or compiler switch, I personally think it's fair to include it as long as it is marked as such (Xerxes did a great job at that). Same thing with the CPU clock, turbo modes, etc. Many implementations are optimized for the particular language/calculator, but they don't change the algorithm. They solve the same problem through the same path to a solution.

(10-17-2014 08:02 PM)patrice Wrote:  - Problem, calculators are features poor. hp15c, hp16C and wp34S and many others show poor performance because they stick to the BASIC code and spend their time swaping array pointers in the innier loop. Is it fair ?

You have seen that the wp34s can be 3 times faster, that is huge. Is it fair not to show it in the benchmark?

Every program using the double array access should be rewriten to single array access, just to be fair with C/RegVars code.

Perhaps they should all use it, but that will have a relatively small impact, and requires extra storage to "cache" that value. I'd say if a calculator has extra registers and can do it, why not. Having extra registers available is a feature of the calculator and is representative of what the calculator can do.
Bit manipulations, on the other hand, is a very specialized subset of features that not all calculators have and is not representative of what the calculator can do at solving problems.
I'd think a lot of problems will require arrays and indexes, but not so many can be solved using bit manipulations, so it gives a better idea of what to expect from a particular calculator/language combination in the real world.
For fun, I coded a non-optimized bitmap solution (no idea if it's similar to yours, I made it up from scratch) in userRPL on the 50g, and it runs in 75 seconds instead of the 90 from the list. It's split in several routines and does heavy use of subroutine calls done by name (ugly and slow), so it's not exactly the fastest it could be, but enough to prove my point: many other calculators could benefit greatly from a bitmap approach, even the assembly and C versions could get a boost from that. Including your solution in the list would mean we have to throw away all other results and run a bitmap solution on all of them.
It's not really about being fair/unfair, it's a question of it being comparable or not to the others, and of it being representative of other problems.
I think you should open a new thread and call it the "N-Queens Calculator Competition", (emphasis on "competition" versus "benchmark") where we don't care about comparison or real-world usage, just get the job done with the fastest algorithm optimized the best you can.
I think a lot of people will start coding their own algorithms and optimizing them for different machines. It could be fun.

Claudio