Prime calculation speed

Hi,

I have a Delphi app that shows al integers form 0-100,000 in a listbox and the numbers that are prime are shown in a second listbox. Calculation speed Delphi 1.9 sec. In Xojo I have the same app, and the calculation time is 46 secs.


Heavy lifting of the calculation is done by IsPrime function:
In Delphi/Pascal:

function IsPrime(X: Integer):Boolean;
begin
  if (X <= 1) then Exit(False);
  var Q := Floor(Sqrt(X));
  for var i :=  2 to Q do
      if (X Mod I = 0) then
         Exit(False);
  Exit(True);
end;

In Xojo:

Public Function IsPrime(X as Integer) As Boolean
  If (X <= 1) Then 
    Return False
  End If
  Var Q As Double = Floor(Sqrt(X))
  For I As Integer = 2 To Q 
    If (X Mod I = 0) Then
      Return False
    Else
      Return True
    End If
  Next
  
End Function

The app fills the listbox in a for/next loop and tests every integer (which is not necessary, could do with only odds). Delphi:

procedure TForm4.OKClick(Sender: TObject);
var
  I: Integer;
  SW: TStopwatch;

begin
   SW := TStopwatch.StartNew;
   for I  := 0 to 100000 do
     begin

       NumListBox.Items.Add(IntToStr(i));
       if IsPrime(i) then PrimeListBox.Items.Add(IntToStr(i));
     end;
     ShowMessage('Time: ' +  FormatDateTime('hh:nn:ss:zzz',sw.ElapsedMilliseconds/MSecsPerDay));
end;

Xojo:

Dim start As Double = System.Ticks

Var TotalNumbers As Integer = 100000

For i As Integer = 0 To TotalNumbers
  NumListBox.AddRow(Str(I))
  If IsPrime(I) Then
    PrimeListBox.AddRow(Str(I))
  End If
Next

Var elapsedSeconds As Double = (Ticks - start) / 60
MessageBox("Time: " + elapsedSeconds.ToString)

This difference is huge. How to improve it?

Don’t add your result to a listbox. This totally makes your result useless.

It means that Delphi adds items faster to a listbox than Xojo does…

1 Like

Your Xojo function appears to include many non-primes such as 25, 33, 45, 49. This could be part of the problem.

But I agree with other replies - you’re testing 2 different things (calculation of primes and adding items to a list) and adding the times together.

There are other posts in this forum about list boxes with a lot of rows. There can be performance problems. And for a real application, how is a user going to navigate through 100000 items?

1 Like

Indeed it does… didn’t notice that. That is strange as the functions are the same as far as I know.

Dim start As Double = System.Ticks

Var TotalNumbers As Integer = 100000

NumListBox.RemoveAllRows
PrimeListBox.RemoveAllRows

Var TempNum(-1) As String
Var TempPrime(-1) As String

For i As Integer = 0 To TotalNumbers
  TempNum.AddRow(Str(I))
  If IsPrime(I) Then
    TempPrime.AddRow(Str(I))
  End If
Next

NumListBox.AddRows(TempNum)
PrimeListBox.AddRows(TempPrime)

Var elapsedSeconds As Double = (Ticks - start) / 60
MessageBox("Time: " + elapsedSeconds.ToString)

1 Like

Your isPrime function is buggy. The Delphi code does return true after the loop. Try this:

Public Function isPrime(x as Integer) As Boolean
  If (X <=1) Then 
    Return False
  End If
  
  Var Q As Double = Floor(Sqrt(X))
  For I As Integer = 2 To Q 
    If (X Mod I = 0) Then
      Return False
    End If
  Next
  Return True  
End Function

Yes indeed! Thanks for mentioning. With the bug fixed I and skipping the listboxes I get the same results in prime count and calculation speed is better now: Xojo is 0.41667 sec and Delphi 0.009 sec. Still a huge difference.

Adding to a listbox can add considerable time. I have a high-speed CSV parser with a test app that will show the parsed CSV in a listbox for inspection. On a 150MB input file, parsing 3,173,959 rows and adding to the listbox takes 76.45sec, while just parsing and not adding them takes 49.97sec, an over 50% increase in time. That said, we are talking about over 3 million rows, so that’s not too bad.

And here is my outer loop where the timing is just the loop without the output. It should be better to compare. Also I use Microseconds instead of Ticks.

Dim dTime As Double = System.Microseconds

dim primes() as Integer
For i As Integer = 0 To 100000
  If IsPrime(I) Then
    primes.Append i
  End If
Next

dTime = (System.Microseconds - dTime) / 1000

for each prime as integer in primes
  PrimeListBox.AddRow(Str(prime))
next

self.Title = "Time: " + dTime.ToString  + " ms"

PS. I set the window title because I don’t like the MessageBox :wink:

Thanks! That gives 408 millisecs and the population of the listbox is very speedy. Or is it microsecs. It should be about 0.5 sec so 408 should be millisecs though.

Speedy! I see you store both the integers in an array. My machine gives 0.5 sec Intel Core i7, 16 gb

Delphi has two methodes that can speedup adding items to a listbox.
BeginUpdate;
-add stuff-
EndUpdate;

Unfortunately, I don’t think Xojo has something like that. But that would be useful though.

In Delphi you can actually speed up the calculation by using the parallel library

var
Tot: Integer;
SW: TStopwatch;
begin
try
// counts the prime numbers below a given value
Tot :=0;
SW :=TStopWatch.Create;
SW.Start;
TParallel.For(2,1,Max,procedure(I:Int64)
begin
if IsPrime(I) then
TInterlocked.Increment(Tot);
end);
SW.Stop;
Memo1.Lines.Add(Format(‘Parallel For loop. Time (in milliseconds): %d - Primes found: %d’, [SW.ElapsedMilliseconds,Tot]));
except on E:EAggregateException do
ShowMessage(E.ToString);
end;
end;

Years ago look for a tool for my business. I tested with Delphi and XOJO.

As a result, I saw that Delphi generates a more efficient binary and handles Windows objects very well.

It is no coincidence that Delphi is faster on your machine.

Although the C compilation output is faster than Delphi, the latter almost comes close.

I do not mean that XOJO is not good both tools have their strengths. Delphi on Windows works fine.

If I had to read more than a thousand files to collect data, I would not do it in XOJO.

That’s because Delphi does not have a framework like Xojo. So .exe are very small, just like VS C++

Delphi was pretty great and probably the best RAD tool ever made. But after Borland did let it go (after bankruptcy?) it wend down hill.

A very good friend of mine (Didier Dambrin) here in Brussels made the very well known Fruityloops with Delphi, which is now known as FL-Studio. Lately also ported to macOS with Delphi.

Regarding to your comment. For my testing plan, I used Delphi with Embarcadero.

That is, with the current multi-device tool.

I bought one Delphi license since one month was not enough for the tests.

Now the tool is big, expensive, and takes a lot of resources. But the EXE continues to be efficient.

MarkusR’s solution is pretty quick in populating the listbox by reading the numbers in an array. Hardly any delay.

1 Like

Add some Pragmas to speed up potentially further…not Infront of my computer at the moment but try…

#pragma DisableBackgroundTasks True
#pragma DisableBoundsChecking True
#pragma StackoverflowChecking False

Double check docs for use, but place these at the very top of your code.

1 Like

I tested this on a MacBook Pro 2.8 GHz i7 with 16 GB RAM and Xojo 2021r3.1. In all test variations I collect the values and set each ListBox once using AddRows per MarkusR’s suggestion. This results in a UI refresh time of ~0.035s. All times below are for the processing only. So the total time would be processing + 0.035s.

Using TomE’s corrected IsPrime function…
Debugger: 0.498s
Debugger with Matthew Combatti’s suggested pragmas: 0.387s
Compiled aggressive with pragmas: 0.095s

So using the pragmas and compiling on aggressive makes a big difference.

Using the Sieve of Eratosthenes against a boolean array, compiled aggressive with pragmas, I get 0.072s processing time. If I compute to 1,000,000 instead of 100,000 the sieve algorithm scales by 10 to 0.723s. But the IsPrime function doesn’t scale as well with a processing time of 1.255s.

For comparison, using Sieve of Eratosthenes in C against a char array, Xcode 11, the processing time is 0.000197.

2 Likes