Solved

Ordinary program faster than Multithreading program!!!!!!!

Posted on 2010-08-17
27
847 Views
Last Modified: 2013-11-11
I made a program to detect prime numbers starting from number 2 to 100000. First, I wrote it to support Multithreading since my processor has 6cores. The program finishes after 4386seconds. Then, I’ve change it to be Non-threading program which suppose to be slower. It finished after 201seconds!!!!!!!!!!
What the problem with my multi-threading program.


Note: I’m using Xeon X5680 processor which has 6 cores and support 12 threads.

File: Unit1.pas --------------------

unit Unit1; 

{$mode objfpc}{$H+}

interface

uses
  Classes, SysUtils, FileUtil, LResources, Forms, Controls, Graphics, Dialogs,
  StdCtrls;

type

    TShowStatusEvent = procedure(Status: String) of Object;

    { TMyThread }

    TMyThread = class(TThread)
    private
      fStatusText : string;
      InNumber : integer;

      FOnShowStatus: TShowStatusEvent;
      procedure ShowStatus;
    protected
      procedure Execute; override;
      function ISPrime(const vlNumber: Integer): Boolean;
    public
      IsPrimeFlage  : Boolean;
      PP : string;
      IsFinish : string;
      Constructor Create(CreateSuspended : boolean; InN:integer);
      property OnShowStatus: TShowStatusEvent read FOnShowStatus write FOnShowStatus;
    end;

  { TForm1 }

  TForm1 = class(TForm)
    Button1: TButton;
    Button2: TButton;
    Edit1: TEdit;
    Edit2: TEdit;
    Edit3: TEdit;
    Edit4: TEdit;
    Edit5: TEdit;
    Memo1: TMemo;
    ToggleBox1: TToggleBox;
    procedure Button1Click(Sender: TObject);
    procedure Button2Click(Sender: TObject);
    procedure ToggleBox1Change(Sender: TObject);
    function DateTimeDiff(Start, Stop : TDateTime) : int64;
    function ISPrime2(const vlNumber: Integer): Boolean;
    procedure showtime;
  private
    { private declarations }
  public
    { public declarations }
  end; 

var
  Form1: TForm1; 

implementation
constructor TMyThread.Create(CreateSuspended : boolean; InN:integer);
  begin
    FreeOnTerminate := True;
    IsFinish := 'NO';
    IsPrimeFlage := False;
    PP := ' NO';
    InNumber:= InN;
    inherited Create(CreateSuspended);
  end;

  procedure TMyThread.ShowStatus;
  // this method is executed by the mainthread and can therefore access all GUI elements.
  begin
    if Assigned(FOnShowStatus) then
    begin
      FOnShowStatus(fStatusText);
    end;
  end;

  procedure TMyThread.Execute;
  var
    newStatus : string;
  begin
    fStatusText := 'NO';
    Synchronize(@Showstatus);
    fStatusText := 'NO';
    IsFinish := 'NO';
    while (not Terminated) do
      begin



      IsPrimeFlage := ISPrime(InNumber);
      if IsPrimeFlage then
         Pp := ' Yes';
      fStatusText := 'Yes';
      IsFinish := 'Yes';

      end;
  end;

    function TMyThread.ISPrime(const vlNumber: Integer): Boolean;
var
X: Integer;
vlPrime: Boolean;
begin
X := 2;
vlPrime := True;
While (X < vlNumber) and vlPrime do begin
vlPrime := ((vlNumber mod X) <> 0);
Inc(X);
end;
ISPrime := vlPrime;

  end;

{ TForm1 }

procedure TForm1.ToggleBox1Change(Sender: TObject);
var
   AAA : TMyThread;
begin
     AAA := TMyThread.Create(FALSE,2);

end;

function TForm1.DateTimeDiff(Start, Stop: TDateTime): int64;
var TimeStamp : TTimeStamp;
begin
  TimeStamp := DateTimeToTimeStamp(Stop - Start);
  Dec(TimeStamp.Date, TTimeStamp(DateTimeToTimeStamp(0)).Date);
  Result := (TimeStamp.Date*24*60*60)+(TimeStamp.Time div 1000);

end;

function TForm1.ISPrime2(const vlNumber: Integer): Boolean;
var
X: Integer;
vlPrime: Boolean;
begin
X := 2;
vlPrime := True;
While (X < vlNumber) and vlPrime do begin
vlPrime := ((vlNumber mod X) <> 0);
Inc(X);
end;
ISPrime2 := vlPrime;

end;

procedure TForm1.showtime;
var
i: real;
j: integer;
begin
i := frac(real(StrToTime('00:00:01')));
// i is the fractional number which Delphi uses to represent 1 second
// thus, dividing the full frac number Delphi uses to store any time by the i number,
//we will have the seconds, no?


Edit2.Text := inttostr(j);

end;

procedure TForm1.Button1Click(Sender: TObject);
var
   A1,A2,A3,A4,A5,A6,A7,A8,A9,A10,A11,A12 : TMyThread;
   i : integer;

   start, stop, elapsed : TDateTime;
begin
i := 1;
start := Now;
while i<=strtoint(Edit1.Text) do
begin
     A1 := TMyThread.Create(FALSE,i+1);
     A2 := TMyThread.Create(FALSE,i+2);
     A3 := TMyThread.Create(FALSE,i+3);
     A4 := TMyThread.Create(FALSE,i+4);



     A5 := TMyThread.Create(FALSE,i+5);
     A6 := TMyThread.Create(FALSE,i+6);
     A7 := TMyThread.Create(FALSE,i+7);
     A8 := TMyThread.Create(FALSE,i+8);


     A9 := TMyThread.Create(FALSE,i+9);
     A10 := TMyThread.Create(FALSE,i+10);
     A11 := TMyThread.Create(FALSE,i+11);
     A12 := TMyThread.Create(FALSE,i+12);

     WHILE not (a1.IsFinish = 'Yes') do
           Application.ProcessMessages;
     Memo1.Lines.Add(inttostr(i+1)+' ===>'+A1.pp);

     WHILE not (a2.IsFinish = 'Yes') do
           Application.ProcessMessages;
     Memo1.Lines.Add(inttostr(i+2)+' ===>'+A2.pp);


     WHILE not (a3.IsFinish = 'Yes') do
           Application.ProcessMessages;
     Memo1.Lines.Add(inttostr(i+3)+' ===>'+A3.pp);


     WHILE not (a4.IsFinish = 'Yes') do
           Application.ProcessMessages;
     Memo1.Lines.Add(inttostr(i+4)+' ===>'+A4.pp);




     WHILE not (a5.IsFinish = 'Yes') do
           Application.ProcessMessages;
     Memo1.Lines.Add(inttostr(i+5)+' ===>'+A5.pp);



     WHILE not (a6.IsFinish = 'Yes') do
           Application.ProcessMessages;
     Memo1.Lines.Add(inttostr(i+6)+' ===>'+A6.pp);


     WHILE not (a7.IsFinish = 'Yes') do
           Application.ProcessMessages;
     Memo1.Lines.Add(inttostr(i+7)+' ===>'+A7.pp);


     WHILE not (a8.IsFinish = 'Yes') do
           Application.ProcessMessages;
     Memo1.Lines.Add(inttostr(i+8)+' ===>'+A8.pp);

     WHILE not (a9.IsFinish = 'Yes') do
           Application.ProcessMessages;
     Memo1.Lines.Add(inttostr(i+9)+' ===>'+A9.pp);




     WHILE not (a10.IsFinish = 'Yes') do
           Application.ProcessMessages;
     Memo1.Lines.Add(inttostr(i+10)+' ===>'+A10.pp);

     WHILE not (a11.IsFinish = 'Yes') do
           Application.ProcessMessages;
     Memo1.Lines.Add(inttostr(i+11)+' ===>'+A11.pp);

      WHILE not (a12.IsFinish = 'Yes') do
           Application.ProcessMessages;
     Memo1.Lines.Add(inttostr(i+12)+' ===>'+A12.pp);

    stop := Now;
    elapsed := stop - start;

    Edit5.Text := IntToStr(DateTimeDiff(start,stop))+' sec';

    i := i+ 12;

         A1.Terminate;
         A2.Terminate;
         A3.Terminate;
         A4.Terminate;
         A5.Terminate;
         A6.Terminate;
         A7.Terminate;
         A8.Terminate;
         A9.Terminate;
         A10.Terminate;
         A11.Terminate;
         A12.Terminate;



end;

end;

procedure TForm1.Button2Click(Sender: TObject);
var
   i : integer;
   x:string;

   start, stop, elapsed : TDateTime;
begin
i := 2;
start := Now;
while i<=strtoint(Edit1.Text) do
begin
     if ISPrime2(i)then
        x :=' Yes'
     else
         x := ' No';

           Application.ProcessMessages;
     Memo1.Lines.Add(inttostr(i)+' ===>'+x);




    stop := Now;
    elapsed := stop - start;

    Edit5.Text := IntToStr(DateTimeDiff(start,stop))+' sec';

    i := i+ 1;





end;

end;

initialization
  {$I unit1.lrs}

end.


-------------------------------------------------------------------------
File: project1.lpr ------------------------------------------------------

program project1;

{$mode objfpc}{$H+}

uses
  {$IFDEF UNIX}{$IFDEF UseCThreads}
  cthreads,
  {$ENDIF}{$ENDIF}
  Interfaces, // this includes the LCL widgetset
  Forms, Unit1, LResources
  { you can add units after this };

{$IFDEF WINDOWS}{$R project1.rc}{$ENDIF}

begin
  {$I project1.lrs}
  Application.Initialize;
  Application.CreateForm(TForm1, Form1);
  Application.Run;
end.

Open in new window

0
Comment
Question by:IbrahimSA
  • 15
  • 10
  • 2
27 Comments
 
LVL 36

Expert Comment

by:Geert Gruwez
ID: 33453749
you are running 1 thread from 2 to .... x

and with multiple threads you run
from 2 to x, from 3 to x, from 4 to x, from 5 to x

this means that actually n+1 thread is useless as the n thread already has figured out if y is prime or not

you need to divide the load amongst all the threads
now you are processing the same load with each thread

given x = 1000000
divide all the threads with a equal work load:
for 6 threads:  x / 6 = 166666 numbers to process

thread 1: 2 to 166666
thread 2: 166667 to 333332
thread 2: 333332 to 499998
etc



0
 
LVL 36

Expert Comment

by:Geert Gruwez
ID: 33453779
o ... you only need to check until the square root of the number
higher is of no use.


0
 
LVL 36

Expert Comment

by:Geert Gruwez
ID: 33453793
are you trying to find all the prime numbers in a certain range as fast as possible
1: using threads
2: not using threads

and then comparing these 2 methods ?
0
 
LVL 36

Accepted Solution

by:
Geert Gruwez earned 334 total points
ID: 33453815
there is one more problem

you are synchronising your threads to give info back to main thread
this also slows down the process

if you want a thread to work fast:
give it a workload and wait till it's finished
if the user really wants to see progress, then do this very sporadic

for instance every 10000th check
0
 

Author Comment

by:IbrahimSA
ID: 33453930
could you please modify my code.

please see the attached file.
0
 
LVL 36

Expert Comment

by:Geert Gruwez
ID: 33453940
i'm working on a sample ...

no attached file to be seen
0
 

Author Comment

by:IbrahimSA
ID: 33454006
her unit1 source

unit1.pas
0
 

Author Comment

by:IbrahimSA
ID: 33454025
can you write a simple and fast thread to do the job.
0
 
LVL 36

Expert Comment

by:Geert Gruwez
ID: 33454052
you are aware that one of the first projects giving to people programming is finding prime numbers ?
and this site has a policy against giving complete solutions for homework ?

and that this site has a complete solution : ?
http://delphiforfun.org/programs/Math_Topics/index.htm
0
 
LVL 36

Expert Comment

by:Geert Gruwez
ID: 33454090
since there are so many solutions
i'll post mine anyway

this only takes a second or 2 with 1 thread ...

and the most time is spent giving the results back
unit Unit5;

interface

uses
  Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
  Dialogs, ExtCtrls, StdCtrls;

const
  feedback_delta = 10000;

type
  TPrimeThreadEvent = procedure (Sender: TObject; Msg: string) of object;

  TPrimeThread = class(TThread)
  private
    fPrimeList: TStrings;
    fStartNum,
    fEndNum: Integer;
    fProgress: TPrimeThreadEvent;
    fFinished: TPrimeThreadEvent;
    procedure DoFinished;
    procedure DoProgress;
  protected
    procedure Execute; override;
  public
    constructor Create(StartNum, EndNum: Integer; Progress, Finished: TPrimeThreadEvent); virtual;
    destructor Destroy; override;
  end;

  TfrmPrimes = class(TForm)
    Button1: TButton;
    Memo1: TMemo;
    procedure Button1Click(Sender: TObject);
  private
    procedure ShowFinished(Sender: TObject; Msg: string);
    procedure ShowProgress(Sender: TObject; Msg: string);
    procedure AddMsg(Msg: string);

  public

  end;

var
  frmPrimes: TfrmPrimes;

implementation

{$R *.dfm}

procedure TfrmPrimes.AddMsg(Msg: string);
begin
  Memo1.Lines.Add(Msg);
end;

procedure TfrmPrimes.Button1Click(Sender: TObject);
begin
  with TPrimeThread.Create(2, 100000, ShowProgress, ShowFinished) do
    Start;
end;

procedure TfrmPrimes.ShowProgress(Sender: TObject; Msg: string);
begin
  AddMsg(Msg);
end;

procedure TfrmPrimes.ShowFinished(Sender: TObject; Msg: string);
begin
  AddMsg(Msg);
end;

{ TPrimeThread }

constructor TPrimeThread.Create(StartNum, EndNum: Integer; Progress,
  Finished: TPrimeThreadEvent);
begin
  inherited Create(True);
  fStartNum := StartNum;
  fEndNum := EndNum;
  fProgress := Progress;
  fFinished := Finished;
  fPrimeList := TStringList.Create;
end;

destructor TPrimeThread.Destroy;
begin
  FreeAndNil(fPrimeList);
  inherited Destroy;
end;

procedure TPrimeThread.Execute;
var n, sq: Integer;
  Found: Boolean;
begin
  while not Terminated and (fStartNum < fEndNum) do
  begin
    n := 2;
    sq := Trunc(Sqrt(fStartNum));
    Found := False;
    while not Found and (n <= sq) do
    begin
      if fStartNum mod n = 0 then
        Found := True
      else
        Inc(n);
    end;
    if not Found then
      fPrimeList.Add(IntToStr(fStartNum));
    Inc(fStartNum);
    if fStartNum mod feedback_delta = 0 then
      Synchronize(DoProgress);
  end;
  Synchronize(DoFinished);
end;

procedure TPrimeThread.DoProgress;
begin
  if Assigned(fProgress) then fProgress(Self, 'Number: ' + IntToStr(fStartNum));
end;

procedure TPrimeThread.DoFinished;
begin
  if Assigned(fFinished) then fFinished(Self, fPrimeList.Text);
end;

end.

Open in new window

0
 
LVL 36

Expert Comment

by:Geert Gruwez
ID: 33454101
this is the code change for 2 threads
and a wider range ...

procedure TfrmPrimes.Button1Click(Sender: TObject);
begin
  with TPrimeThread.Create(2, 1000000, ShowProgress, ShowFinished) do
    Start;
  with TPrimeThread.Create(1000001, 2000000, ShowProgress, ShowFinished) do
    Start;
end;
0
 
LVL 36

Assisted Solution

by:Geert Gruwez
Geert Gruwez earned 334 total points
ID: 33454133
if you would really want to boost performance
you would have to assign each thread to a different processor

you would have to set the processor of the thread:

this includes:
* GetSystemInfo > to get the number of processors on the thread
* GetProcessAffinityMask > to see on what processors the thread/process can run
* call SetThreadIdealProcessor to change the processor of the thread

i think this should give you enough to chew on for the moment

and that math site with all it's solutions


0
 
LVL 36

Expert Comment

by:Geert Gruwez
ID: 33454136
ugh ... typo:

* GetSystemInfo > to get the number of processors on the computer
0
How to run any project with ease

Manage projects of all sizes how you want. Great for personal to-do lists, project milestones, team priorities and launch plans.
- Combine task lists, docs, spreadsheets, and chat in one
- View and edit from mobile/offline
- Cut down on emails

 
LVL 25

Assisted Solution

by:epasquier
epasquier earned 166 total points
ID: 33456874
before trying to optimize such calculations with threads, it is best to first optimize with ONE thread only.
This is only calculation, no drive access, so first 12 threads are not going to be used efficiently on your processor with HyperThreading (because the 2 threads run on a single core will use the same units and one will have to wait for the other almost all the time)
So even with threads, use only the number of threads = number of cores, and set afinity to one each only.

Now, to optimize searching for primes, there are 2 easy things to consider that will give you much more that 12 times faster (that you hope to achieve with 12 threads) :

a) it is only needed to check for division remainder = 0 with all the primes before the number you are testing. So you have to maintain a list of primes starting with the obvious 2,3,5,7 , and say you want to know if 11 is a prime you only test division with those. When seeing that none of the 4 initial primes do return 0 as remainder, then you can add 11 to the list and look for the next prime
that will quickly eliminates an ever growing magnitude of tests, for only the cost of maintaining a list that IS your goal anyway.

b) when you want to check the next number, you can skip one of 2 just because no even number is a prime, except 2 itself. so instead of Inc(fStartNum) in Geert example, you can go with Inc(fStartNum,2)
That is 100% more efficiency

you could find a more complex way of increasing this 'to be checked' number by removing also the 1 over 3 odd number that can be divided by 3. That is only 2 on each 6 numbers to check, with a regular pattern that you can code with an array. => +200% efficiency

then you can do the five as well, with a 30 numbers table, of which 10 only are left because of the 2 previous tricks, and you can remove 2 number in this table, so 8 out of 30 numbers to check => +275% efficiency

after that, there is not much gain with this technique (some would say that the fives trick are not even necessary)

Do you want me to help you write such an optimized One Thread only procedure ?
Note that :
a) with these techniques, no multithreading is possible because each number to check needs the list of all primes up to the previous number, so it has to be linear.
b) no brute force multithreaded technique could compete past the first 100 numbers, no matter how many threads you put in. Ok, maybe with 40000 cores you will have to wait for the 10000th number before wining the race, but those calculations are usually just a way to spend CPU time for days trying to find new primes with that many digits, no ? (you would need int64 at some point...)
0
 

Author Comment

by:IbrahimSA
ID: 33458197
This is not home work. No one teach Delphi these days!
0
 
LVL 25

Expert Comment

by:epasquier
ID: 33458760
> No one teach Delphi these days!
of course there are !
Pascal has been the preferred language in all French university and Engineer school to start programming for years, and is slowly replaced by Delphi. At least my Engineer school switched 10 years ago, the year after my graduation (a bit because I pleaded the case for next batch of students)

but that is not the issue here, I'm willing to believe you as there are few students with Xeon X5680.

Please answer to the tips we gave you, and if you like my approach (= let go of multithreading for that case) then tell me
0
 

Author Comment

by:IbrahimSA
ID: 33458901
Ok>>>>>>>>> thanks.

note: I live in uk (Don't Use Pascal)
0
 
LVL 36

Expert Comment

by:Geert Gruwez
ID: 33459595
they do indeed still teach delphi/pascal in school and even university
helped out someone teaching pascal only 2 years back.   he used my book of author Tom Swan. Excellent book.
It's a good thing he gave it back.  It's almost an antique now ...

has this to do with this question ?
http://www.experts-exchange.com/Other/Math_Science/Q_26345410.html
if so, epasquier and me showed how to improve from 201 seconds to probably 1/4 of a second for a million or 10 primes

you are a little vague in the math question with specifications for the equation
with such specifications it is very difficult to give good and precise advice

i know that you may not want to give corporate code, nobody does
but then you'll have to expect the same vague answers




0
 

Author Comment

by:IbrahimSA
ID: 33460128
Yes, I'm trying to improve my processing time by first get the best result from the CPU (using mutlithreading)  then focus on the performance of the Disk.

I'm doing some research experiments (not homeworks :) )
0
 
LVL 36

Expert Comment

by:Geert Gruwez
ID: 33461929
ah... ok
actually the hardware is not what you would need to test in this case

i believe your hardware is more than sufficiënt to do the equations

Maybe you should consider different steps to solve your problem:
I believe you want to compare 50000 strings to see which match ?

you may want to do something like soundex first:
find a value for a text and compare that value.

depending on how complex the text is, ...
evaluating if the context is the same is probably the most difficult

it's very difficult to give fitting advice with such a broad scope
maybe you need to run a compare tool like Beyond compare does, comparing files in background using a ruleset
it's programmed in delphi ... you could buy the product and source and see how the do it

it may give some good algorithms too

here is link with some links about text comparison algorithms (it's a study on it's own)
http://answers.google.com/answers/threadview?id=337832






0
 

Author Comment

by:IbrahimSA
ID: 33461956
thank you for your adive. Do you know any good guide for Multithreading in Delphi. I prefer it as a pdf file.
0
 

Author Comment

by:IbrahimSA
ID: 33461964
Sorry adive=advice :)
0
 
LVL 36

Expert Comment

by:Geert Gruwez
ID: 33461991
lol, no problem, i try and keep all files (e-books) on a site i have for referencing
http://veerle-en-geert.be/delphi/ebooks.htm

this one has some string algorithms
http://veerle-en-geert.be/delphi/ebooks/Delphi%20-%20Algorithms.pdf

off course you could read the tomes of Delphi a few times ...
http://veerle-en-geert.be/delphi/ebooks/Delphi%20-%20The%20Tomes%20of%20Delphi%20-%20Algorithms%20and%20Data%20Structures.pdf
0
 

Author Comment

by:IbrahimSA
ID: 33461998
Thank you soooooooooooooooooooooooooooooooooooooooooooooooo much
0
 
LVL 36

Expert Comment

by:Geert Gruwez
ID: 33462005
i hope you get time to read all that within the time given to solve your problem  ... :)
0
 

Author Comment

by:IbrahimSA
ID: 33462030
Since it not a homwork :) I have plenty of time 2 read all that ;)

Again, Thanks
0
 
LVL 36

Expert Comment

by:Geert Gruwez
ID: 33462053
you can send a very difficult project like this to a university
students and professors allways need a challenge
there is never a guarantee that they will find the best solution
there is neither a gaurantee that they will work on it

but sometimes they can't resist the challenge ...

0

Featured Post

Highfive + Dolby Voice = No More Audio Complaints!

Poor audio quality is one of the top reasons people don’t use video conferencing. Get the crispest, clearest audio powered by Dolby Voice in every meeting. Highfive and Dolby Voice deliver the best video conferencing and audio experience for every meeting and every room.

Join & Write a Comment

A lot of questions regard threads in Delphi.   One of the more specific questions is how to show progress of the thread.   Updating a progressbar from inside a thread is a mistake. A solution to this would be to send a synchronized message to the…
The uses clause is one of those things that just tends to grow and grow. Most of the time this is in the main form, as it's from this form that all others are called. If you have a big application (including many forms), the uses clause in the in…
Get a first impression of how PRTG looks and learn how it works.   This video is a short introduction to PRTG, as an initial overview or as a quick start for new PRTG users.
This video gives you a great overview about bandwidth monitoring with SNMP and WMI with our network monitoring solution PRTG Network Monitor (https://www.paessler.com/prtg). If you're looking for how to monitor bandwidth using netflow or packet s…

708 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question

Need Help in Real-Time?

Connect with top rated Experts

12 Experts available now in Live!

Get 1:1 Help Now