Recent

Author Topic: would multi threading help this project?  (Read 2521 times)

speter

  • Sr. Member
  • ****
  • Posts: 487
would multi threading help this project?
« on: January 21, 2026, 08:56:13 am »
I have a program which analyses sudoku puzzles - in job lots. :)

At present my "creator" takes about 20minutes to create a file with ~950k puzzles.
I then sort the output (by difficullty) and run a program that removes duplicate puzzles.

Finally, I though the ~650k puzzles at my analyser, which takes about an hour and uses about 15% of the computers cpu (according the windows task manager).

My question is: if I were to rewrite the analyser to use threads, would that help?
And I guess a second question, would it require a total rewrite of the application?

cheers
S.
I climbed mighty mountains, and saw that they were actually tiny foothills. :)

PierceNg

  • Sr. Member
  • ****
  • Posts: 422
    • SamadhiWeb
Re: would multi threading help this project?
« Reply #1 on: January 21, 2026, 09:08:45 am »
How about some way of recognizing patterns in the puzzles, and have your program cache those patterns for reuse? Might also speed the program up even when run single threaded.

Khrys

  • Sr. Member
  • ****
  • Posts: 391
Re: would multi threading help this project?
« Reply #2 on: January 21, 2026, 09:14:35 am »
[...] uses about 15% of the computers cpu [..]

To answer your original question: Yes, as long as your CPU usage is below 100% you aren't trying hard enough  ;)
Does your CPU happen to have 6 cores by any chance?

speter

  • Sr. Member
  • ****
  • Posts: 487
Re: would multi threading help this project?
« Reply #3 on: January 21, 2026, 09:42:28 am »
Does your CPU happen to have 6 cores by any chance?
According the task manager it has 24 cores.

cheers
S.
I climbed mighty mountains, and saw that they were actually tiny foothills. :)

MathMan

  • Sr. Member
  • ****
  • Posts: 472
Re: would multi threading help this project?
« Reply #4 on: January 21, 2026, 03:10:30 pm »
The answer to your second question is - it depends  :D

If your current analyser has a single entry where you hand over a sudoku and only uses local (or very low number of global) variables, chances are good that you can make that multi-threaded without much effort.

It would help though, if you provide some source.

Cheers,
MathMan

speter

  • Sr. Member
  • ****
  • Posts: 487
Re: would multi threading help this project?
« Reply #5 on: January 21, 2026, 10:53:30 pm »
The answer to your second question is - it depends  :D

If your current analyser has a single entry where you hand over a sudoku and only uses local (or very low number of global) variables, chances are good that you can make that multi-threaded without much effort.

It would help though, if you provide some source.

Cheers,
MathMan

Thanks everyone for your help.

The TPuzzle.solve method includes the following:
Code: Pascal  [Select][+][-]
  1.   repeat
  2.     ok := NakedSingles or
  3.           HiddenSingles or
  4.           LockedCandidates or
  5.           NakedPairs or
  6.           HiddenPairs or
  7.           XWing or
  8.           NakedTriples or
  9.           NakedQuads or
  10.           HiddenTriples or
  11.           HiddenQuads or
  12.           // ... and another 24 patterns
So *I think* threading might be sensible / possible. Though I might need to reorganise things since the functions above are, at present, in various units (and not part of the TPuzzle class).

cheers
S.
I climbed mighty mountains, and saw that they were actually tiny foothills. :)

speter

  • Sr. Member
  • ****
  • Posts: 487
Re: would multi threading help this project?
« Reply #6 on: January 22, 2026, 04:27:07 am »
I have created a very simple multithreaded app (attached), which works ok; but I'd like to get some help / advice on whether this approach will work with a more complex example.

Bascially, each thread adds 2 numbers from an array (declared in the form object), the result is assigned into the array. All of which works, but is it safe!? :o

Code: Pascal  [Select][+][-]
  1. {
  2.   https://forum.lazarus.freepascal.org/index.php?topic=44274.msg311652#msg311652
  3. }
  4. unit umain;
  5.  
  6. {$mode objfpc}{$H+}
  7.  
  8. interface
  9.  
  10. uses
  11.   Classes, SysUtils, Forms, Controls, Graphics, Dialogs, StdCtrls;
  12.  
  13. const
  14.   num=10;
  15. type
  16.   Trec = record a,b,c : integer; end;
  17.   Tarray = array[0..num-1] of Trec;
  18.  
  19.   { TMyThread }
  20.  
  21.   TMyThread = class(TThread)
  22.     index : integer;
  23.   protected
  24.     procedure Execute; override;
  25.   end;
  26.  
  27.   { TForm1 }
  28.  
  29.   TForm1 = class(TForm)
  30.     Button1: TButton;
  31.     Button2: TButton;
  32.     Memo1: TMemo;
  33.     procedure Button1Click(Sender: TObject);
  34.     procedure Button2Click(Sender: TObject);
  35.     procedure FormCreate(Sender: TObject);
  36.   private
  37.  
  38.   public
  39.     myarray : Tarray;
  40.   end;
  41.  
  42. var
  43.   Form1: TForm1;
  44.  
  45. implementation
  46.  
  47. {$R *.lfm}
  48.  
  49. { TForm1 }
  50.  
  51. procedure TForm1.FormCreate(Sender: TObject);
  52. begin
  53.   randomize;
  54. end;
  55.  
  56. procedure TForm1.Button1Click(Sender: TObject);
  57. var
  58.   a : integer;
  59.   MyThreads : array [0..num-1] of TMyThread;
  60. begin
  61.   for a := 0 to num-1 do
  62.     begin
  63.       myarray[a].a := random(10);
  64.       myarray[a].b := random(10);
  65.       myarray[a].c := 0;
  66.  
  67.       MyThreads[a]  := TMyThread.create(true);
  68.       MyThreads[a].index := a;
  69.       MyThreads[a].FreeOnTerminate := true;
  70.       MyThreads[a].Start;
  71.     end;
  72.  
  73.   memo1.append('all done');
  74. end;
  75.  
  76. procedure TForm1.Button2Click(Sender: TObject);
  77. var
  78.   a: Integer;
  79. begin
  80.   for a := 0 to num-1 do
  81.     with myarray[a] do
  82.       memo1.append(format('a=%d; b=%d; c=%d',[a,b,c]));
  83. end;
  84.  
  85. { TMyThread }
  86.  
  87. procedure TMyThread.Execute;
  88. begin
  89.   with form1.myarray[index] do
  90.     c := a + b;
  91. end;
  92.  
  93. end.
I climbed mighty mountains, and saw that they were actually tiny foothills. :)

440bx

  • Hero Member
  • *****
  • Posts: 6088
Re: would multi threading help this project?
« Reply #7 on: January 22, 2026, 05:20:22 am »
What you've shown in the previous post is safe but will very likely take noticeably longer (relatively speaking) than a single thread performing the entire task.

The reason for this is simple, you're creating a thread for every element in the array.  Thread creation isn't a cheap operation.  Certainly _much_ more expensive than adding two integers together which is what a single threaded program would do.

For what you're trying to do yield a noticeable improvement, the first thing you need is to calculate what the optimal number of threads is.   That number depends on two things: 1. the global task that is to be performed and 2. the number of processors in the system.

In the example you presented, no improvement can be obtained because there are too few elements in the array and the operation is very simple.  The point is, you need to create something that is relatively speaking simple but that still represents the original problem.  This is necessary in order to be able to _measure_ the improvement, if any, a particular approach yields.

In the case of adding a couple of integers, in today's processors it probably takes a number of elements in the hundreds of thousands in order to be able to have a repeatable and measurable difference.  Also, for your example, you're using random numbers which makes it difficult to verify the result is correct, considering the simplicity of the task it probably is but, it would be better to use a pattern that yields a value that can be pre-determined, that way _you_ can verify the results.

As a rule of thumb, a well behaved application should create, at most, 2/3 the number of threads as there are processors in the system.  This because, in general, you want leave some processor power available to run other tasks to ensure the system keeps running smoothly.  Generally speaking, give the user the option of selecting how many processors the task should use and "recommend" no more than 2/3 for the reason mentioned but, if the user want maximum speed at the expense of the system still running smoothly, I'd allow a maximum of (number of processors - 1) (always leave one processor available to run the O/S and other apps.)

Lastly, the threads should _not_ terminate when they are done with their task, they should suspend instead and be activated by inserting a task in their queue (which they check) before _resuming_ them.  That way you have a pool of threads that perform work as it is needed.  How this is controlled also depends on global task that is to be performed.

The above means that, one of the preliminary/setup steps the program carries out is to create a thread pool upfront, which is later used to accomplish the main task.

HTH.
FPC v3.2.2 and Lazarus v4.0rc3 on Windows 7 SP1 64bit.

speter

  • Sr. Member
  • ****
  • Posts: 487
Re: would multi threading help this project?
« Reply #8 on: January 22, 2026, 05:29:22 am »
Thanks for the reply 440bx.

The application that I want to make multithreaded took about 2 hours to run yesterday - reviewing about 650k sudoku puzzles. I was thinking of giving each thread 100k puzzles (so 7 threads); though I guess I could make it more even by using 10 threads each having 65k puzzles.

My concern with the simple program I posted was that, when I read up on threads this morning, I got the impression that accessing "global" variables was a bad idea...

cheers
S.
I climbed mighty mountains, and saw that they were actually tiny foothills. :)

440bx

  • Hero Member
  • *****
  • Posts: 6088
Re: would multi threading help this project?
« Reply #9 on: January 22, 2026, 06:56:49 am »
I got the impression that accessing "global" variables was a bad idea...
Generally speaking, global variables are "not desirable", that said, there are cases where they may be the only way to share information.

The solution you mention of splitting the workload evenly (or close to evenly) among threads, isn't necessarily optimal but, it is simple and reasonable and should cut the total time it takes to create the puzzles.
FPC v3.2.2 and Lazarus v4.0rc3 on Windows 7 SP1 64bit.

Khrys

  • Sr. Member
  • ****
  • Posts: 391
Re: would multi threading help this project?
« Reply #10 on: January 22, 2026, 07:02:19 am »
Apart from multithreading - have you tried profiling your program?
After all, spreading (potentially) slow code onto more cores only increases the total CPU time wasted  ;)

speter

  • Sr. Member
  • ****
  • Posts: 487
Re: would multi threading help this project?
« Reply #11 on: January 22, 2026, 12:18:12 pm »
Thanks for the replies.

... have you tried profiling your program?
After all, spreading (potentially) slow code onto more cores only increases the total CPU time wasted  ;)
No, I haven't (nor do I know how I might do it). At present I am timing the solving of each puzzle, though.

It seems to me, solving sudoku puzzles is inherantly slow and inefficient. My program searches for a range of patterns which could help solve a part of the puzzle. What I am seeking to do is to work out how the puzzle can be solved (the actual solution is irrelevant). Added to the above I haven't implemented 3 or so of the most complex patterns / techniques, which means my app can't solve the most complex puzzles (at the moment). The most difficult puzzle solved is rated 8.3 (and 11 patterns are used in the solving. :)

The current data set has 653,608 puzzles, 652,273 are solved (1,335 not solved) with a difficulty rating of 1.2 to 9.0 (the most difficulty puzzles rate 10+), the average time taken to solve a puzzle is 0.002 seconds (the max is 0.359). The majority (70%) of the puzzles are trivial to solve.

cheers
S.
I climbed mighty mountains, and saw that they were actually tiny foothills. :)

MathMan

  • Sr. Member
  • ****
  • Posts: 472
Re: would multi threading help this project?
« Reply #12 on: January 22, 2026, 12:38:36 pm »
<snip>

The reason for this is simple, you're creating a thread for every element in the array.  Thread creation isn't a cheap operation.  Certainly _much_ more expensive than adding two integers together which is what a single threaded program would do.

<snip>

Just to give speter a ballpark figure here - on modern CPU cores, modern OS, the creation and start of a thread is in the range of multiple 10,000 CPU cycles. One can do substantial work in that time indeed ...

creaothceann

  • Sr. Member
  • ****
  • Posts: 266
Re: would multi threading help this project?
« Reply #13 on: January 22, 2026, 03:07:04 pm »
... have you tried profiling your program?
No, I haven't (nor do I know how I might do it)

You can use the SysUtils.Now function before and after doing some work, if the difference isn't too small. For smaller/more precise durations you can get the time from the CPU's built-in timer, in Windows via QueryPerformanceCounter/-Frequency:

Code: Pascal  [Select][+][-]
  1. unit Timer;  {$ModeSwitch AdvancedRecords}
  2.  
  3. interface
  4.  
  5. type Timer = record
  6.         private
  7.         class var _LatestStart    : Int64;
  8.         class var _TicksPerSecond : Int64;
  9.         public
  10.         class property  TicksPerSecond : Int64  read _TicksPerSecond;
  11.         class function  GetCounter     : Int64;   inline;  // in ticks
  12.         class procedure Start;                    inline;
  13.         class function  Stop           : Double;  inline;  // in seconds
  14.         end;
  15.  
  16. implementation
  17.  
  18. {$ifdef Windows}
  19. function QueryPerformanceCounter  (out lpPerformanceCount : Int64) : LongBool;  external 'kernel32' name 'QueryPerformanceCounter';
  20. function QueryPerformanceFrequency(out lpFrequency        : Int64) : LongBool;  external 'kernel32' name 'QueryPerformanceFrequency';
  21. {$endif}
  22.  
  23. class function Timer.GetCounter : Int64;  inline;
  24. begin
  25.         {$ifdef Windows}  QueryPerformanceCounter(Result);
  26.         {$else}           {$fatal}  // todo
  27.         {$endif}
  28. end;
  29.  
  30. class procedure Timer.Start;          inline;  begin  _LatestStart := GetCounter;                                    end;
  31. class function  Timer.Stop : Double;  inline;  begin  Result       := (GetCounter - _LatestStart) / TicksPerSecond;  end;
  32.  
  33. initialization
  34.         Timer._TicksPerSecond := Timer.GetCounter;
  35.  
  36. end.


Just to give speter a ballpark figure here - on modern CPU cores, modern OS, the creation and start of a thread is in the range of multiple 10,000 CPU cycles. One can do substantial work in that time indeed ...
obligatory "Operation Costs in CPU Clock Cycles"
« Last Edit: January 22, 2026, 03:09:09 pm by creaothceann »

LeP

  • Full Member
  • ***
  • Posts: 137
Re: would multi threading help this project?
« Reply #14 on: January 22, 2026, 03:14:21 pm »
Just to give speter a ballpark figure here - on modern CPU cores, modern OS, the creation and start of a thread is in the range of multiple 10,000 CPU cycles. One can do substantial work in that time indeed ...
I don't think we should think this way. Initializing something always has its burden, obviously, but it's also necessary to consider the benefits it can bring... 20 minutes of processing time can easily be shaved off using threads, and initialization would have absolutely no impact on the process.
If we assume that only 10 threads can process 10 puzzles in parallel, each lasting 359 ms (the time claimed by the author), we would have a load of 370 ms (considering that each thread takes 1 ms to initialize and schedule... a HUGE and improbable amount of time) versus 3590 ms, or just over 1/9 of the time. If we increase the threads to 16 (as is likely), it's easy to see that the 20 minutes would drop to a few minutes (perhaps even less).
The author should have a processor with 8 power cores (16 threads) and 16 ec cores.
Using the 16 power core threads alone would significantly reduce processing time.
And I doubt the processor would saturate to 100% (it could be around 65%).

 

TinyPortal © 2005-2018