Algorithm puzzle challenge (Xojo vs C# vs Python)

Off-Topic
1

At our company we have a Xojo fan, a C# fan and a Python fan.

We decided to have a little bit of fun and play a game to see which language runs a certain algorithm the fastest.

Here are the rules of the game:

Calculate the sum of all the prime numbers between 0 and 1,000,000. As output give the sum, total number of prime numbers, and the running time.

Currently I get Xojo to complete the taksk in 1.26s (compiled, not via IDE). C# is currently the winner completing the task in 0.4s (YES, a fraction of a second).

Something I already learned, it is better to use UInt32 instead of UInt64 where possible. With UInt64 my algorithm ran 2.4s, with UInt32 at ran 1.26s.

Here is the algorithm I used:

  Dim i As UInt32
  Dim j As UInt32
  Dim total As UInt64
  Dim count As UInt32
  Dim max As UInt32
  Dim isPrime As Boolean
  Dim startTime As Double 
  Dim endTime As Double
  
  startTime = Microseconds()
  
  total = 2
  count = 0
  i = 3
  while i <= 1000000
    
    max = Sqrt(i)
    isPrime = true
    j = 2
    while (j <= max) and isPrime
      if (i mod j) = 0 then
        isPrime = false
      end if
      j = j + 1
    wend
    
    if isPrime then
      total = total + i
      count = count  + 1
    end if
    
    i = i + 2
  wend
  
  endTime = Microseconds()
  
  System.DebugLog "Items: " + Str(count) + EndOfLine + _
  "Sum: " + Str(total) + EndOfLine + _
  "Time: " + Str((endTime - startTime) / 1000000, "##########0.000000") + " seconds"

Can anyone spot obvious improvements I can make? Would be great if I could get it to run faster than C#.

FWIW, here is the C# code that currently beats my code:

using System;
using System.Diagnostics;

namespace PrimeNumberPuzzel
{
    class Program
    {
        static void Main(string[] args)
        {
            int i = 3, j, count = 0;
            double max, total = 2;
            bool isPrime;

           Stopwatch stopWatch = new Stopwatch();
            stopWatch.Start();

           while (i <= 1000000)
            {
                max = Math.Sqrt(i);
                isPrime = true;
                j = 2;
                while (j <= max && isPrime)
                {
                    if (i % j == 0)
                        isPrime = false;
                    j += 1;
                }
                if (isPrime)
                {
                    total += i;
                    count ++;
                }
                i += 2;
            }
            stopWatch.Stop();
            TimeSpan ts = stopWatch.Elapsed;
            Console.WriteLine(String.Format("Items: {0}", count));
            Console.WriteLine(String.Format("Sum: {0}", total));
            Console.WriteLine(String.Format("Time: {0}", ts));
            Console.ReadLine();
        }
    }
}

PS. If anyone knows why in the world C# would run so much faster, it would be nice if you could share your wisdom.

2

Fun contest Alwyn.

There used to be a difference in performance between xojoscript and xojo (xojoscript being faster), but I don’t know if that’s the case anymore.

Julen

3

Add just

#pragma BackgroundTasks False

It takes only half of the time for me (tested in IDE).

4

Beautiful Thomas, it now runs 0.524446. :slight_smile:

The problem IS, the C# guy just got his code to run in 0.02s (by tweaking his types).

He simply changed double max to int max, and double total to long total.

5

[quote=336245:@Julen Ibarretxe Uriguen]Fun contest Alwyn.

There used to be a difference in performance between xojoscript and xojo (xojoscript being faster), but I don’t know if that’s the case anymore.

Julen[/quote]

I think I’ll have to test this, for the sake of the challenge :wink:

6

Try this…
I did consider changing isPrime from boolean to integer
then use isPrime = 1 or isPrime = 0
Then the

if isPrime then total = total + i count = count + 1 end if

becomes

total = total +isprime count = count + isprime

removing one test

I would expect that using integer instead of UINTanything would mean faster performance as it should be using the ‘native’ integer size…?

[code]
#pragma DisableBackgroundTasks
#pragma DisableBoundsChecking
#pragma DisableAutoWaitCursor
#pragma StackOverflowchecking False
#pragma NilObjectChecking False

//these knocked off 30%

Dim i As UInt32
Dim j As UInt32
Dim total As UInt64
Dim count As UInt32
Dim max As UInt32
Dim isPrime As Boolean
Dim startTime As Double
Dim endTime As Double

startTime = Microseconds()

total = 2
count = 0
i = 3
while i <= 1000000

max = Sqrt(i)
isPrime = true
j = 2
while  isPrime and (j <= max)    //test for boolean first.. ignores the next bit so shaves off some time
  if (i mod j) = 0 then
    isPrime = false
  end if
  j = j + 1
wend

if isPrime then
  total = total + i
  count = count  + 1
end if

i = i + 2

wend

endTime = Microseconds()

msgbox "Items: " + Str(count) + EndOfLine + _
"Sum: " + Str(total) + EndOfLine + _
“Time: " + Str((endTime - startTime) / 1000000, “##########0.000000”) + " seconds”

//while isPrime=1 and (j <= max)
//if (i mod j) = 0 then
//isPrime = 0
//end if
//j = j + 1
//wend[/code]

7

Best time I now get is 0.48s.

PS. The C# guy just informed me he gets 0.2s, NOT 0.02s as previously reported. So the competition is still within reach…

8

Have you tried compiling for 64-bit using the aggressive compiler setting?

9

There are more pragmas you can use which would better replicate the C# code:

#pragma BoundsChecking False
#pragma StackOverflowChecking False
#pragma NilObjectChecking False

http://developer.xojo.com/pragma-directives

10

I don’t think the current version I’m using has that option (or at least, I couldn’t find an aggressive compiler setting)? I’m using Xojo 2016 r1.1.

[quote=336276:@Greg O’Lone]#pragma BoundsChecking False
#pragma StackOverflowChecking False
#pragma NilObjectChecking False[/quote]

Already has these added to the last test run.

11

To summarize, this is currently the code that gives the best run:

  #pragma BackgroundTasks False
  #pragma BoundsChecking False
  #pragma DisableBoundsChecking
  #pragma StackOverflowchecking False
  #pragma NilObjectChecking False
  
  Dim i As Integer
  Dim j As Integer
  Dim total As Double
  Dim count As Integer
  Dim max As Integer
  Dim isPrime As Boolean
  Dim startTime As Double 
  Dim endTime As Double
  
  startTime = Microseconds()
  
  total = 2
  count = 0
  i = 3
  while i <= 1000000
    
    max = Sqrt(i)
    isPrime = true
    j = 2
    while isPrime and (j <= max) 
      if (i mod j) = 0 then
        isPrime = false
      end if
      j = j + 1
    wend
    
    if isPrime then
      total = total + i
      count = count  + 1
    end if
    
    i = i + 2
  wend
  
  endTime = Microseconds()
  
  System.DebugLog "Items: " + Str(count) + EndOfLine + _
  "Sum: " + Str(total) + EndOfLine + _
  "Time: " + Str((endTime - startTime) / 1000000, "##########0.000000") + " seconds"
12

On my computer your code runs in 0.46 seconds.

Compiling for 64 bit the code ran in 0.95 seconds!

Does anyone have an explanation?

13

Does this agree with your sum?

Sum: 37550402023  Time: 0.0253104 seconds

This is running compiled as 64 bit app.

My Code:

  #pragma BackgroundTasks False
  #pragma BoundsChecking False
  #pragma DisableBoundsChecking
  #pragma StackOverflowchecking False
  #pragma NilObjectChecking False
  dim et As Double=Microseconds
  dim n(-1) As Boolean
  dim m As Integer = 1000000
  redim n(m)
  dim i,j,k As Integer
  dim sum As int64 = 0
   j = 2
  while j<m
    for k = j to m
      if not n(k) then
        sum=sum+k
        exit
      end if
      j=k
    next
    for i = k to m step k
      n(i)=true
    next
  wend
  txtAreaOut.Text="Sum: "+str(sum) +"  Time: "+str((Microseconds-et)/1e6)+" seconds"
14

IDE,
Xojo 2017r1.1
MacBook Pro 13" i3

Report:
Items: 78497
Sum: 3.755040e+10
Time: 2.999635 seconds

I used MsgBox to get the report

15

Does it run faster as a console app?

16

I think @Robert Weaver hit it right.

Here is a project showing the time difference. 0.03 seconds on my machine.

https://www.dropbox.com/s/dlclg0ke31pj0dq/Speed%20Test.xojo_binary_project?raw=1

results

Method1 Method2 In IDE Debug 4.6248 0.2559 Compiled 32 Bit 0.4548 0.0381 Compiled 64 Bit 0.9606 0.0306 64 Bit Aggressive 0.6168 0.0171

Win 10, i7-2600, 3.40 GHz

17

FYI, my time of 0.0253 seconds was on a 2015 MacBook Pro 2.2 GHz Intel Core i7.
Compilation was set to aggressive.

18

WOW, Robert… just WOW…

That is the correct answer, and Xojo is now in the lead at our office :slight_smile: (thanks to you)

The previous best time was C#, 0.2s

New best time is Xojo, 0.04s.

19

PS. And the 0.04s is a console app compiled as 32-bit. I’m sure a few more milliseconds might be shaved by using a 64-bit aggressive compilation.

20

O, just saw Neil posted a a nice table sowing the results between 32-bit and 64-bit.