Link to home
Start Free TrialLog in
Avatar of IbrahimSA
IbrahimSA

asked on

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

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

Avatar of Geert G
Geert G
Flag of Belgium image

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



o ... you only need to check until the square root of the number
higher is of no use.


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 ?
ASKER CERTIFIED SOLUTION
Avatar of Geert G
Geert G
Flag of Belgium image

Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
Avatar of IbrahimSA
IbrahimSA

ASKER

could you please modify my code.

please see the attached file.
i'm working on a sample ...

no attached file to be seen
her unit1 source

unit1.pas
can you write a simple and fast thread to do the job.
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
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

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;
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
ugh ... typo:

* GetSystemInfo > to get the number of processors on the computer
SOLUTION
Link to home
membership
This solution is only available to members.
To access this solution, you must be a member of Experts Exchange.
Start Free Trial
This is not home work. No one teach Delphi these days!
> 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
Ok>>>>>>>>> thanks.

note: I live in uk (Don't Use Pascal)
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 ?
https://www.experts-exchange.com/questions/26345410/I-Don't-Know-What-To-Do-Reducing-Processing-Time.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




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 :) )
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






thank you for your adive. Do you know any good guide for Multithreading in Delphi. I prefer it as a pdf file.
Sorry adive=advice :)
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
Thank you soooooooooooooooooooooooooooooooooooooooooooooooo much
i hope you get time to read all that within the time given to solve your problem  ... :)
Since it not a homwork :) I have plenty of time 2 read all that ;)

Again, Thanks
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 ...