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.

How to populate a dictionary as fast as possible from an array
#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.