8-Queens Benchmark

[Egan Ford]

(07-10-2016 03:21 AM)Accutron Wrote:  Timing it with a stopwatch, I got 12.07, 12.12, 12.08, but of course there was a small ~0.1 second delay between when the program finished and when I mashed the stop button on the watch, so the completion time is pretty much exactly 12 seconds.

...

If you have a smart phone handy I'd suggest video recording it, then reviewing the start and end frame-by-frame. Assuming 30 frame/sec, you could get sub-second accuracy.

[Accutron]

(07-10-2016 06:03 PM)Egan Ford Wrote:  If you have a smart phone handy I'd suggest video recording it, then reviewing the start and end frame-by-frame. Assuming 30 frame/sec, you could get sub-second accuracy.

Good idea. I don't own a smartphone, because they're evil tentacled brain-sucking parasites, but I do have a digital camera that can shoot at 240 FPS.

[Accutron]

I shot it three times at 240FPS, and got the same result all three times. Rounded to the nearest 1/100 sec, it's 11.92 seconds. I used Paul's corrected HPL program, with dsp instead of prt in Line 10. Xerxes should feel free to add the result to the N-Queens list.

[xerxes]

Hello Accutron,
every result of a physical calculator or pocket computer is welcome, but unfortunately the tested devices
are not really suitable. However, it was interesting to read Paul's comments about the test results.

[Accutron]

How is the 9825 not suitable?

[xerxes]

I cannot say, if the 9825 is a calculator or more a computer, but nearly all tested devices in the list are
more or less pocket sized and portable, but the 9825 doesn't meet these criteria.

[Accutron]

Well, it's your list, but it seems a shame to leave out the best calculators HP ever made, simply because they contain too many molecules. I had always assumed that your list didn't include 9100/9800 series machines because they're somewhat rare and nobody had submitted benchmarks yet, so I was rather excited that we were obtaining rare benchmarks for you. You might want to qualify your list as only including 'small' or 'personal' calculators, as there is currently no obvious indication of this rather arbitrary qualifier.

As far as whether the 9825 is a calculator or not, it's certainly debatable from a forensic standpoint, but the designers refer to it as a calculator in the original patent, and it was referred to as a calculator in all early documentation. HP only started calling it a computer once they realized the term carried marketing value.

On the preumption that Xerxes isn't going to come around to my way of thinking, I would very much like to obtain and publish N-Queens benchmarks for the HP 9100 (can it run N-Queens? I have no idea), 9810, 9815, 9820, 9821, 9825, 9831, 9835 and 9845. I would also welcome results from their contemporaries, such as the Olivetti P101, Wang programmables, etc.

[Paul Berger (Canada)]

Some more results, I have obtained the Microsoft BASIC and SnapFORTH for the Panasonic HHC RL-H1800. The Microsoft BASIC version is the same as the SnapBASIC program and for SnapFORTH I modified the HP-71 FORTH program and the results are:

Microsoft BASIC Integer 69.59 seconds
Microsoft BASIC Float 58.74 seconds
SnapFORTH 23.51 seconds.

It appears that the math routines in Microsoft BASIC are optimized for floating point. I have encountered some BASICs before that do all their math in floating point so integers need to be converted to floats which slows down integer math.

Paul.

[xerxes]

What a nice surprise to be able to add these results to the list. Thank you for your effort.

As expected the Microsoft BASIC on the HHC is roughly as fast as the C64.

Also interesting to have 3 Forth versions in comparison now. May be someone knows,
if there is a significant speed difference between the 2 versions of Forth for the 71B.

Could you please post the SnapForth code for adding it into the list?

[rprosperi]

(01-06-2017 02:23 PM)xerxes Wrote:  May be someone knows, if there is a significant speed difference between the 2 versions of Forth for the 71B.

It appears the 41 Translator core of Forth (2A) was tweaked considerably, as it is notably faster than version 1A. This is surprising, as it is ostensibly basically the original version with some custom Forth words to let it "run" HP-41 Programs.

41 Translator Forth (2A): 46.3 (from prior results)

71 Forth (1A): 55.02 (avg 3 runs, FRAM, time adj. to remove time spent in timer code)

71 Forth (1A): 55.18 (avg 3 runs, RAM, time adj. to remove time spent in timer code)

Good question, with somewhat surprising result.

Retesting Forth 2A with the identical code and conditions used for 1A above confirms the 2A version is faster.

Note 1: the original code used a Trans41-specific CLOCK command to time the loop; above 1A and this 2A test used same timing code.

Note 2: In all test cases, HP-IL was connected to loop, but with no I/O in the queens test, this makes no difference (confirmed).

41 Translator Forth (2A): 45.14 (avg 3 runs, RAM, time adj. to remove time spent in timer code).

Thanks for asking Xerxes

[Jurgen Keller]

(07-13-2016 02:01 PM)Accutron Wrote:  ... I would very much like to obtain and publish N-Queens benchmarks for the HP 9100 (can it run N-Queens? I have no idea) ...

I see no reason why a 9100B shouldn't be able to run N-Queens. With the 9100A it might get more difficult due to the limited number of registers. I'll give it a try, starting with the easier one.

PS: Rash thoughts - I forgot that without a 9101A you don't have indirect addressing. Maybe that can be emulated by some self-modifying code?

[xerxes]

(01-06-2017 04:00 PM)rprosperi Wrote:  It appears the 41 Translator core of Forth (2A) was tweaked considerably, as it is notably faster than version 1A. This is surprising, as it is ostensibly basically the original version with some custom Forth words to let it "run" HP-41 Programs.

Thank you for the detailed testing and commenting the results. I've updated the list with the fastest values.

(01-06-2017 06:31 PM)Jurgen Keller Wrote:  PS: Rash thoughts - I forgot that without a 9101A you don't have indirect addressing. Maybe that can be emulated by some self-modifying code?

Yes, it's possible to use a float var to hold the array, but it makes no sense in case of benchmarking, due to the very expensive array access.

[Guenter Schink]

8-Queens with Python on PRIME.
G1 : 0.047
G2 : 0.022

I copied the MicroPython code from Xerxes' benchmark list. Added only the timing procedure of module hpprime, and deleted the loop

Code:

from hpprime import *
Time=eval("time")
a = [0] * 9
r = 8
s = 0
x = 0
y = 0
t = 0
while True:
 x += 1
 a[x] = r
 while True:
   s += 1
   y = x
   while y>1:
     y -= 1
     t = a[x]-a[y]
     if t==0 or x-y==abs(t):
       y=0
       a[x] -= 1
       while a[x]==0:
         x -= 1
         a[x] -= 1
   if y==1:
     break;
 if x==r:
   break;
Time=eval("time")-Time
print(s)
print(round(Time,6))

That is about 8 times faster than PPL on Prime: G2 ~0.166 times G1 ~0,38

Günter

[xerxes]

(11-14-2021 06:52 PM)Guenter Schink Wrote:  That is about 8 times faster than PPL on Prime:

So it's worth to give python a try. Thank you for testing.

[Hlib]

I have checked the implementation of 8-queens benchmark algorithm in some calculators. In Hewlett Packard models, everything was done quite successfully. In CASIO and in Texas Instruments models, this leaves much to be desired. To apply the most effective implementation of the algorithm, it is necessary to take into account the features of each specific calculator model. Otherwise, we will not be able to get objective results in the test.
Here is a more suitable test program
for TI-83+/83+SE/84+/84+ SE:

Code:


ClrHome
8->R : R->dim(L1)
R+1->N : 0->S : 0->X : 0->Z
While Z=N or X<>R
  If Z<>N
    Then : X+1->X : R->L
      Else : DS<(X,1)
        L1(X)-1->L
      If X=0
        Then : 1->Z : R->X : 0->L
      End
  End
  For(Y,L,1,-1)
    For(Z,1,X-1,1)
      Y-L1(Z)->T
        If T=0 or X-Z=abs(T)
          R->Z
    End : S+1->S
      If Z<>N
        Then : Y->L1(X) : 0->Y
      End
  End
End : Disp S

t=130_s (2:10) vs 161_s (2:41) TI-83+, increase in speed +19%.
t=62_s (1:02) vs 68_s (1:08) TI-84+/84+SE, OS 2.55MP Classic mode, +9%.
t=51_s vs 62_s (current benchmark) TI-83+SE, +18%.
Since the performance in TI calculators is directly proportional to the size of free RAM, the test was performed under favourable conditions.

[xerxes]

(08-25-2024 02:53 PM)Hlib Wrote:  In CASIO and in Texas Instruments models, this leaves much to be desired.

I like your optimizations, but the goal of this integer benchmark was not to find out what's the best way with every language to solve n-queens.
For me it was more important to implement the same algorithm in a similar way on all computers. Regardless of whether structured or unstructured, both versions follow practically the same execution path. It is true that sometimes some optimizations were made, such as ISZ, DSZ or other small things. On the other hand, I avoided things like FOR NEXT so that the structure of the test code was more or less preserved. I know that this was not always implemented optimally, but it was good enough to have a useful comparison. If we now use a different test code that is a bit faster but the execution path has been significantly changed, we would have to question all the other test codes and look for better implementations to be fair. Unfortunately I do not have the opportunity to do this for all computers again, as I no longer have access to most of them. I don't think that's a problem, because it's certainly clear to everyone that this benchmark, like others, is just an example and depending on which task you're using to test, the results might be slightly different.

[Hlib]

Quote:... If we now use a different test code that is a bit faster but the execution path has been significantly changed, we would have to question all the other test codes and look for better implementations to be fair. ...

I made three programs identical in structure for CASIO and TI and brought the calculation path to a single standard: 876 steps, 2205 comparisons If T=0 or X-Y=Abs(T), as is in this benchmark.
CASIO:

Code:


ClrText : 8->R : {R,1}->Dim Mat A
0->S : 0->X : 0->Z
While Z<0 Or X<>R
  If Z>=0 : Then Isz X : R->L
    Else Dsz X : Mat A[X,1]-1->L
      If X=0 : Then Break
       IfEnd
  IfEnd
  For L->Y To 1 Step -1
    For X-1->Z To 1 Step -1
    Y-Mat A[Z,1]->T
      If T=0 Or X-Z=Abs T
        Then -1->Z : Break
      IfEnd
    Next : Isz S
      If Z>=0 : Then Y->Mat A[X,1]
      Break
      IfEnd
  Next
WhileEnd : S

TI Z80:

Code:


ClrHome : 8->R : R->dim(L1)
0->S : 0->X : 0->Z
While Z<0 or X<>R
  If Z>=0 : Then : X+1->X : R->L
    Else : X-1->X
      If X=0 : Then : 1->Z : R->X : 0->L
      End
    L1(X)-1->L
  End
  For(Y,L,1,-1)
    For(Z,X-1,1,-1)
      Y-L1(Z)->T
        If T=0 or X-Z=abs(T) : -1->Z
    End : S+1->S
      If Z>=0 : Then : Y->L1(X) : 0->Y
      End
  End
End : Disp S

TI 68K:

Code:


nqueens()
prgm
ClrIO
Local a, l, r, s, t, x, y, z
8->r : 0->s : 0->x : 0->z
newList(r)->a
While z<0 or x<>r
  If z>=0 Then
  x+1->x : r->l
    Else
    x-1->x
      If x=0 : Exit
      a[x]-1->l
  EndIf
  For y, l, 1, -1
    For z, x-1, 1, -1
    y-a[z]->t
      If t=0 or x-z=abs(t) Then
      -1->z : Exit
      EndIf
    EndFor
    s+1->s
    If z>=0 Then
    y->a[x] : Exit
    EndIf
  EndFor
EndWhile
Disp s,a
EndPrgm

Here is a table with the results for several well-known old models. Perhaps this information will be of interest to someone.

Code:


22.5_s fx-9750gii(SH3)
42_s fx-9860gii(SH4)
46_s ti-83+SE
58_s ti-84+/84+SE (new HW, OS 2.55MP, classic mode)
67_s = 1:07  ti-84+ (old HW)
78_s = 1:18 ti-89 Titanium (HW3, exact mode)
103_s = 1:43 fx-2.0+, graph-100+
114_s = 1:54 ti-85 (OS ver.9.0)
119_s = 1:59 ti-83+

[toml_12953]

(08-26-2024 05:58 AM)xerxes Wrote:  I like your optimizations, but the goal of this integer benchmark was not to find out what's the best way with every language to solve n-queens.
For me it was more important to implement the same algorithm in a similar way on all computers.

Yes! This is exactly what I try to get through to people who rewrite benchmarks and try to compare their version with the published results.

It's not a valid hardware comparison if you're not using the same algorithm. Ideally, you should use identical code as well. Having Python on various calculators is making this easier but even if you can't reuse the published code directly, at least use the same algorithm.