[Lazarus] Threads in Lazarus code base

Mattias Gaertner nc-gaertnma at netcologne.de
Mon Sep 20 09:25:32 CEST 2010


On Sun, 19 Sep 2010 22:22:21 +0200
Dariusz Mazur <darekm at emadar.com> wrote:

>   W dniu 2010-09-18 18:55, Mattias Gaertner pisze:
>[...]
> >>>> Whats about CILK http://en.wikipedia.org/wiki/Cilk
> >>>>
> >>>>
> >>>> |_function_  fib (n: integer):integer;
> >>>> var
> >>>>      x,y : integer;
> >>>> begin
> >>>>
> >>>>         if (n<    2)  then exit(n)
> >>>>         else begin
> >>>>
> >>>>            x :=_spawn_  fib (n-1);
> >>>>            y := fib (n-2);
> >>>>            _sync_;
> >>>>            exit(x+y);
> >>>>        end;
> >>>> end;
> >>>> |
>[...]
> > Only the first 46 Fibonacci numbers fit into an integer, which a
> > simple loop can compute. I don't know any task scheduler
> > that produces less enough overhead to compute this faster.
> 
> But this is not that case. Its can`t be compared do iteration computing. 
> We can compare different algorithms. Faster than loop is cons array with 
> results, but this tell nothing.

Yes, it does:
Before using multi threading, try to use a better single threaded
algorithm. And when comparing multi with single threading speed, you
must not compare a multi threaded algorithm running single threaded, but
a multi threaded algorithm with a good single threaded algorithm.


> Its simple example to show, that CILK can play with recurrence (even 
> with one invoke).

Yes.
BTW: Same for parallel loops. You can write the above as parallel loop:

...
  for i:=0 to 1 paralleldo begin
    if i=0 then x := fib (n-1)
    else y := fib (n-2);
  end;
  exit(x+y);
...


> On real programs are many plays, that can be done 
> concurrency, but  when its to short, overhead in classic thread model is 
> too big (computing or programing time).
>
> >>> - OR practical, but hard to understand
> >>> ?
> >>>
> >>> Note: afaik CILK is the same as parallel loops:
> >> No. On loop we divide iterations on start loops. When each iteration has
> >> different  time of computing, we lost concurrence, because one thread
> >> finish, but rest  work.
> > And how does CILK solve this?
> 
> Pass task to workers. Each SPAWN start new task.
> But good implementation of background is needed.
> 
> Its very similar to thread model, but not so heavy. Even short task can 
> be computed efficiently
> 
> CILK has different attempt to task scheduling., its fullfil 
> Work-requesting idea from
> http://groups.google.com/group/lock-free/browse_frm/thread/18f90bdd8c721880

That's an implementation detail. Parallel loops implementations can use
this too. There are for example plugins for OpenMP using work stealing.
Probably some use some form of work requesting too.

 
> More on CILK documentation, I;m to weak in english.
> 
> >
> >> Second: we not initialize thread on SPAWN (with
> >> loops threads are initializing on start loop), Workers wait  for task on
> >> idle. Push and pop task from queue can be very fast. Of course this
> >> depend on implementation (for example each worker should deal with own
> >> queue, but should be possibility to draw task form other queue, this
> >> approach is faster than single MPMC FIFO queue)
> > Ehm, you know that parallel loops normally use thread pools, do you?
> Thats resolved only one problem.
> Thread switching is done slowly (less than 100Hz) and rather expensive, 
> thus we cant start  one thread per iteration. We should a priori pass 
> iteration to threads.

Of course. I don't know any parallel loop implementation starting one
thread per iteration (only in extreme cases).


> >>> It allows to make some
> >>> special cases need less typing, can increase readability and can
> >>> decrease overhead. As always with multithreading: wrongly used it can
> >>> make code run much slower.
> >> Multithreading is not only for faster computing.
> > Does that mean, you agree?
> 
> I don;t agree with statement: multithreading is hard thus we don`t use them

I didn't find a mail saying that, but I found a lot of:
multithreading is hard thus we don`t use them without need.


Mattias
 




More information about the Lazarus mailing list