Author Topic: Better Bench by Ed Davis  (Read 1006 times)

0 Members and 1 Guest are viewing this topic.

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
Better Bench by Ed Davis
« on: April 11, 2022, 04:15:53 pm »
Generic Basic code convert to QB64 by me for timing and Types:
Code: QB64: [Select]
  1. DefLng A-Z
  2. Dim As Double x, y, xx, yy, start
  3. start = Timer(.001)
  4. accum = 0
  5. count = 0
  6. While count < 1545
  7.     leftedge = -420
  8.     rightedge = 300
  9.     topedge = 300
  10.     bottomedge = -300
  11.     xstep = 7
  12.     ystep = 15
  13.  
  14.     maxiter = 200
  15.  
  16.     y0 = topedge
  17.     While y0 > bottomedge
  18.         x0 = leftedge
  19.         While x0 < rightedge
  20.             y = 0
  21.             x = 0
  22.             thechar = 32
  23.             xx = 0
  24.             yy = 0
  25.             i = 0
  26.             While i < maxiter And xx + yy <= 800
  27.                 xx = Int((x * x) / 200)
  28.                 yy = Int((y * y) / 200)
  29.                 If xx + yy > 800 Then
  30.                     thechar = 48 + i
  31.                     If i > 9 Then
  32.                         thechar = 64
  33.                     End If
  34.                 Else
  35.                     temp = xx - yy + x0
  36.                     If (x < 0 And y > 0) Or (x > 0 And y < 0) Then
  37.                         y = (-1 * Int((-1 * x * y) / 100)) + y0  ' << this line was revised in later post
  38.                     Else
  39.                         y = Int(x * y / 100) + y0
  40.                     End If
  41.                     x = temp
  42.                 End If
  43.  
  44.                 i = i + 1
  45.             Wend
  46.             x0 = x0 + xstep
  47.             accum = accum + thechar
  48.         Wend
  49.         y0 = y0 - ystep
  50.     Wend
  51.  
  52.     If count Mod 300 = 0 Then
  53.         Print accum,
  54.     End If
  55.     count = count + 1
  56.  
  57. Print accum
  58. Print Timer(.001) - start; " seconds"
  59.  
  60. 'This is the output:
  61.  
  62. ' 200574 60372774 120544974 180717174 240889374 301061574 309886830
  63.  
  64.  
I added DEFLNG A-Z and Dim as Double x, y, xx, yy
and I got below 10 secs on Timer with $Checking:Off, 9.61 was best time with everything turned off including Wifi.

Ed has QB64 down for 9.35 secs maybe on better machine...
http://basic4all.epizy.com/index.php?topic=21.msg166#msg166

Can anyone make a significant drop? FreeBasic at top at 1.09 secs
« Last Edit: April 11, 2022, 04:23:28 pm by bplus »

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • Steve’s QB64 Archive Forum
Re: Better Bench by Ed Davis
« Reply #1 on: April 11, 2022, 04:41:57 pm »
   y = (-1 * Int((-1 * x * y) / 100)) + y0   <-- isn't a negative * negative = positive?  How is this any different from the ELSE case?
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
Re: Better Bench by Ed Davis
« Reply #2 on: April 11, 2022, 04:57:54 pm »
Honestly I haven't done any analysis of code yet. I just know the first time I tried I didn't get what I was supposed to and when I made the substitution, the output came out right.

Can FB be so much faster?

Hey! Ed's here!

Offline bplus

  • Global Moderator
  • Forum Resident
  • Posts: 8053
  • b = b + ...
Re: Better Bench by Ed Davis
« Reply #3 on: April 11, 2022, 05:01:12 pm »
   y = (-1 * Int((-1 * x * y) / 100)) + y0   <-- isn't a negative * negative = positive?  How is this any different from the ELSE case?

looks to me like this forces neg when one or the other is out of bounds but not both.

EDIT

Offline Ed Davis

  • Newbie
  • Posts: 40
Re: Better Bench by Ed Davis
« Reply #4 on: April 11, 2022, 05:05:04 pm »
   y = (-1 * Int((-1 * x * y) / 100)) + y0   <-- isn't a negative * negative = positive?  How is this any different from the ELSE case?

Note this funky code:
Code: [Select]
    if (x < 0 and y > 0) or (x > 0 and y < 0) then
        y = (-1 * Int((-1 * x * y) / 100)) + y0
    else
        y = int(x * y / 100) + y0
    end if

When I originally developed this, I could not get the same results with Python that I got with C.

It turns out that there is no consensus as to whether integer division, when one of the operands is negative, should round towards zero, negative infinity, or positive infinity.

Python and Ruby both round towards negative infinity.  C rounds towards zero.

In order to get the same output from each language (to verify that each language was essentially computing the same thing and doing similar work), I had to figure out how to preclude one of the operands from being negative.

The code checks, and if either x or y is < 0 (but not both), then it multiplies by minus one to force positive division, and then by minus one again at the end to restore the sign.

And I agree, there is probably a better way to do this.  But at the time, I just wanted a solution that worked, and that is what my little mind came up with.

Note that later on, I found out that Python had a integer divide operator, so there was no need to go through the hoops I did.  But, since I had trouble with my "and" and "or" logic and precedence in my own interpreter, I left it in as a sort of unit test :)  And, it does give whatever language is doing this more work to chew on, and more opportunities for optimization.
« Last Edit: April 11, 2022, 05:22:01 pm by Ed Davis »

Offline jack

  • Seasoned Forum Regular
  • Posts: 408
Re: Better Bench by Ed Davis
« Reply #5 on: April 11, 2022, 05:19:07 pm »
Hi bplus and Ed Davis
here's my result
Code: [Select]
QB64
 200574   60372774            120544974           180717174           240889374
 301061574          309886830
 4.637000000002445  seconds

FreeBasic
 200574        60372774      120544974     180717174     240889374     301061574     309886830
 2.118056500097737 seconds
well done bplus :)
note: QB64 includes a lot of runtime checks which slowdown performance, even with $Checking:Off

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • Steve’s QB64 Archive Forum
Re: Better Bench by Ed Davis
« Reply #6 on: April 11, 2022, 05:20:05 pm »
 
Screenshot.png


Best I can come up with, without trying to revert to mem or compiler flags, is about 4.9 seconds on my laptop.

Code: QB64: [Select]
  1. 'DefLng A-Z
  2. 'Dim As Double x, y, xx, yy, start
  3. start = Timer(.001)
  4. accum = 0
  5. count = 0
  6. While count < 1545
  7.     leftedge = -420
  8.     rightedge = 300
  9.     topedge = 300
  10.     bottomedge = -300
  11.     xstep = 7
  12.     ystep = 15
  13.  
  14.     maxiter = 200
  15.  
  16.     y0 = topedge
  17.     While y0 > bottomedge
  18.         x0 = leftedge
  19.         While x0 < rightedge
  20.             y = 0
  21.             x = 0
  22.             thechar = 32
  23.             xx = 0
  24.             yy = 0
  25.             i = 0
  26.             While i < maxiter And xx + yy <= 800
  27.                 xx = Int((x * x) / 200)
  28.                 yy = Int((y * y) / 200)
  29.                 If xx + yy > 800 Then
  30.                     thechar = 48 + i
  31.                     If i > 9 Then
  32.                         thechar = 64
  33.                     End If
  34.                 Else
  35.                     temp = xx - yy + x0
  36.                     If (x < 0 And y > 0) Or (x > 0 And y < 0) Then
  37.                         y = (-Int((-x * y) / 100)) + y0 ' << this line was revised in later post
  38.                     Else
  39.                         y = Int(x * y / 100) + y0
  40.                     End If
  41.                     x = temp
  42.                 End If
  43.  
  44.                 i = i + 1
  45.             Wend
  46.             x0 = x0 + xstep
  47.             accum = accum + thechar
  48.         Wend
  49.         y0 = y0 - ystep
  50.     Wend
  51.  
  52.     If count Mod 300 = 0 Then
  53.         Print accum,
  54.     End If
  55.     count = count + 1
  56.  
  57. Print accum
  58. Print Timer(.001) - start; " seconds"
  59.  
  60. 'This is the output:
  61.  
  62. Print "Compared to expected output of: "
  63. Print "200574 60372774 120544974 180717174 240889374 301061574 309886830"

Only 2 real changes here:

1) I made all variables _DOUBLE type.  When it comes to optimizing speed, QB64 always seems to run better if you can stick with all variables of the same type -- either go all integers, or all floats, if you want speed.  Mixing them seems to always slow things down.

2) I took out the negative multiplication and swapped to negation, which we always process fast.  (-1 * x isn't as efficient as -x, for example.)

Nothing else stares out obviously to me as a means to run the code faster, without going to _MEM access or tweaking compiler options for -fastmath. 
« Last Edit: April 11, 2022, 05:52:14 pm by SMcNeill »
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline George McGinn

  • Global Moderator
  • Forum Regular
  • Posts: 210
    • Resume
Re: Better Bench by Ed Davis
« Reply #7 on: April 11, 2022, 05:39:12 pm »
I get 5.533 seconds.
____________________________________________________________________
George McGinn
Theoretical/Applied Computer Scientist
Member: IEEE, IEEE Computer Society
Technical Council on Software Engineering
IEEE Standards Association
American Association for the Advancement of Science (AAAS)

Offline Ed Davis

  • Newbie
  • Posts: 40
Re: Better Bench by Ed Davis
« Reply #8 on: April 11, 2022, 05:43:41 pm »

Only 2 real changes here:

...

2) I took out the negative multiplication and swapped to negation, which we always process fast.  (-1 * x isn't as efficient as -x, for example.)


But that change makes it a slightly different comparison between different languages.

I purposefully did not try to optimize it for any single language, but rather wanted the same code for each language.

For example, I could have used "i++" instead of "i = i + 1".  Some really poor byte-code interpreters (some of mine :( ) do not recognize that these are the same, and generate:

Code: QB64: [Select]
  1. inc [i]
For the former, and:

Code: QB64: [Select]
  1. push [i]
  2. add
  3. pop [i]
  4.  

For the latter.  Definitely slower, as it has to go two extra times through the byte code interpreter loop.

I could have used "for" loops, which some languages optimize better than "while" loops.

But since all languages I was testing did not offer those things, I avoided them.

So the goal was not to write the fastest algorithm - but to write to write something to test that could be easily converted to many languages.

But of course, you are free to do what you want :) However, if you're going to compare it with another language processor, it would be more fair to optimize the code for that processor also.

Finally, not trying to cause trouble or anything like that.  Just trying to explain the purpose of the code.

It is at best a silly diversion, and like all bench marks, should be taken with a grain of salt, or just completely ignored!

Offline SMcNeill

  • QB64 Developer
  • Forum Resident
  • Posts: 3972
    • Steve’s QB64 Archive Forum
Re: Better Bench by Ed Davis
« Reply #9 on: April 11, 2022, 05:49:55 pm »
I purposefully did not try to optimize it for any single language, but rather wanted the same code for each language.

All I was doing was as I was asked here:

Can anyone make a significant drop?

It's hard to make a drop in speeds, without making any changes to the code to help optimize for speed.  ;)

But, I agree -- you can't compare apples to pineapples.  Speed tests between systems/languages should match so you can compare the performance between those systems/languages without skewing the results. 
https://github.com/SteveMcNeill/Steve64 — A github collection of all things Steve!

Offline Ed Davis

  • Newbie
  • Posts: 40
Re: Better Bench by Ed Davis
« Reply #10 on: April 11, 2022, 06:10:07 pm »
All I was doing was as I was asked here:


Just to make sure:  I appreciate your posts, and help that you so graciously freely provide. 

And I appreciate this forum - lots of knowledgeable, helpful folks around here!  And all the great example programs!

Thanks!

Offline jack

  • Seasoned Forum Regular
  • Posts: 408
Re: Better Bench by Ed Davis
« Reply #11 on: April 11, 2022, 08:30:11 pm »
in Linux x64 same PC I get
3.79 seconds with no optimization
3.58 seconds with -O2 optimization
3.06 seconds with -Ofast optimization

Offline Aurel

  • Forum Regular
  • Posts: 167
Re: Better Bench by Ed Davis
« Reply #12 on: April 15, 2022, 06:49:12 am »
Here is my results with qb64 1.5v on win7 32bit
QB64_win7_32bit.png
* QB64_win7_32bit.png (Filesize: 141.41 KB, Dimensions: 1122x750, Views: 55)
//////////////////////////////////////////////////////////////////
https://aurelsoft.ucoz.com
https://www.facebook.com/groups/470369984111370
//////////////////////////////////////////////////////////////////