220 17319 <768f09d4-b9d0-4e9c-91a7-c8122ac98f96@isocpp.org> article Path: news.gmane.org!not-for-mail From: tef@tentity.com Newsgroups: gmane.comp.lang.c++.isocpp.proposals Subject: Re: Generic Parallel Computing (GPC) API Date: Fri, 10 Apr 2015 11:06:59 -0700 (PDT) Lines: 499 Approved: news@gmane.org Message-ID: <768f09d4-b9d0-4e9c-91a7-c8122ac98f96@isocpp.org> References: <3be1928f-2116-4712-be20-7368682abf26@isocpp.org> <81e0ac7b-2e97-4ecc-8c37-c9851be3d81c@isocpp.org> <45d4c30d-72b4-474a-9df6-9efa17d4d0b1@isocpp.org> <2000ef45-bc5b-4453-8252-d78c7406afc8@isocpp.org> <363fb8c3-5127-47c4-8a08-c6b4202809c6@isocpp.org> <74b7204a-18b6-40fd-aa0e-ec3946688272@isocpp.org> Reply-To: std-proposals@isocpp.org NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/mixed; boundary="----=_Part_751_1543097202.1428689219953" X-Trace: ger.gmane.org 1428689233 14595 80.91.229.3 (10 Apr 2015 18:07:13 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Fri, 10 Apr 2015 18:07:13 +0000 (UTC) Cc: tef@tentity.com To: std-proposals@isocpp.org Original-X-From: std-proposals+bncBDL4BSXDYUBBBRFCUCUQKGQEMWCETXA@isocpp.org Fri Apr 10 20:07:05 2015 Return-path: Envelope-to: gclcip-std-proposals@m.gmane.org Original-Received: from mail-pd0-f200.google.com ([209.85.192.200]) by plane.gmane.org with esmtp (Exim 4.69) (envelope-from ) id 1YgdKY-0005LQ-I0 for gclcip-std-proposals@m.gmane.org; Fri, 10 Apr 2015 20:07:03 +0200 Original-Received: by pdlj11 with SMTP id j11sf42426552pdl.0 for ; Fri, 10 Apr 2015 11:07:01 -0700 (PDT) X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20130820; h=x-gm-message-state:date:from:to:cc:message-id:in-reply-to :references:subject:mime-version:content-type:x-original-sender :reply-to:precedence:mailing-list:list-id:list-post:list-help :list-archive:list-subscribe:list-unsubscribe; bh=Ibvs8Of6cchsv2eO07kml2QXbJCA9ntOMOLHkhv758g=; b=QBg3WXKHv+f59AxtkLsuRbNCRhor3jYfvS1BmJd71AApEp0h5q33PqMJFWjwfkYWOn Dw+15At08CLtg9bPa8OMGi2IE/E/4bSlu8QCyg5UwDcUNJ0BpeJxUICF5uUEMo8Blkg5 a2LZ+nrYLMozZR9bAjH2di7uG8BrDeH2bOWY7XuEgTIUjHD6bMLgETQFgItTS4UMEFGX H5hQcYIZ+D8FTjIHGTpTM3NBOn9d74I7kUoDYmknB3dZKk2qEb+VblHYFxzBMWZqt4qT U/2ojQs+c6ioFwsUvy4XKK4vJ3/olWjR4Wghyn6FUMAHfVVJr9eE5++jDlUhVspTTFAm InFA== X-Gm-Message-State: ALoCoQlU4NFSab4R4CVz4IqG/0VwO34TS30TkrsDjKM24nfqaIkCeLz6hCy/K3NmxzXkjGNesRH2 X-Received: by 10.68.65.37 with SMTP id u5mr3041457pbs.5.1428689221382; Fri, 10 Apr 2015 11:07:01 -0700 (PDT) X-BeenThere: std-proposals@isocpp.org Original-Received: by 10.140.34.228 with SMTP id l91ls1872683qgl.5.gmail; Fri, 10 Apr 2015 11:07:00 -0700 (PDT) X-Received: by 10.140.93.14 with SMTP id c14mr43234qge.42.1428689220405; Fri, 10 Apr 2015 11:07:00 -0700 (PDT) In-Reply-To: <74b7204a-18b6-40fd-aa0e-ec3946688272@isocpp.org> X-Original-Sender: tef@tentity.com Precedence: list Mailing-list: list std-proposals@isocpp.org; contact std-proposals+owners@isocpp.org List-ID: X-Google-Group-Id: 399137483710 List-Post: , List-Help: , List-Archive: List-Subscribe: , List-Unsubscribe: , Xref: news.gmane.org gmane.comp.lang.c++.isocpp.proposals:17319 Archived-At: ------=_Part_751_1543097202.1428689219953 Content-Type: multipart/alternative; boundary="----=_Part_752_1822152842.1428689219954" ------=_Part_752_1822152842.1428689219954 Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable It seems you assume that a single consumer queue can be only processed by= =20 one thread.=20 Actually, it depends on an implementation. In my implementation, at any moment of time only one thread can process a= =20 queue (that is mutual exclusion), but at different times different threads can process the same queue. And because a system can have a lot of single consumer queues,=20 it also take care of tasks' fair ordering. In some cases, it is good for modern hardware to process tasks from the=20 same queue on the same core. Because the purpose of the mutual exclusion is to serialize access to some= =20 data. After the first task, the data will be in CPU cache, so next tasks do not= =20 have to fetch the data from the main memory. My algorithm is friendly for CPU caches and NUMA optimization.=20 And it is a working system. I use it for 2 years already. I just recently integrated it with V8, so I can do parallel computing with= =20 JavaScript now. On Friday, April 10, 2015 at 11:03:27 AM UTC-4, Zijie He wrote: > > Single consumer queue is not good for modern hardware, at least we need t= o=20 > have one thread i.e. one consumer per core. > > For the parallel computational model, I was working on .Net before, and= =20 > was using lambda expressions to define the order of steps, > imaging, > > auto x =3D define_a_procedure( > []() { > ... do some processor work ... > waitfor(an_io_or_lock); // the lock here is not the common lock > goto_next_step(); > }, > []() { > ... obtained the lock or io operation finished ... > ... do some processor work ... > goto_finish(); > }); > run(x); // non-blocking > And each step may work on different threads, the whole procedure will not= =20 > stop until goto_finish() involved. > But when porting to c++, issues as the lifetime of the procedure, it=20 > should keep alive until goto_finish(), and meanwhile, the most important= =20 > thing is, if we need to refer some local variables use lambda expressions>, we also need to consider the lifetime of these= =20 > variables. I tried to use shared_ptr everywhere, but still have some=20 > trouble. > > On Sunday, April 5, 2015 at 7:39:15 AM UTC+8, t...@tentity.com wrote: >> >> Let me make some clarification. >> In my system, I have one thread pool for everything: forks, joins, http= =20 >> requests, timers, etc. >> I avoid creating threads (that is why I do not use std::async) and I=20 >> avoid switching threads. >> I don't see any reason to have more than one thread per core (20 years= =20 >> ago I would do because it was only one core CPU, but not now).=20 >> So, I do not create a thread pool per a qutex, but I use one thread pool= =20 >> for everything.=20 >> Here is the algorithm of the mutual exclusion that is used in the thread= =20 >> pool: >> >> static intptr_t __stdcall Run(tef::sys::THREAD_TASK* task) >> {=20 >> >> ExclusiveTask* $this =3D static_cast(task);=20 >> >> auto qutex =3D $this->qutex;=20 >> >> if( qutex->Lock() =3D=3D 1 ) {=20 >> >> $this->Callback(); // call back the lambda >> >> while( qutex->Unlock() > 0 ) {=20 >> >> task =3D qutex->UnsafePop();=20 >> >> while( task =3D=3D nullptr ) {=20 >> >> task =3D qutex->UnsafePop();=20 >> >> }=20 >> // call back the lambda >> ExclusiveTask* t =3D static_cast(task);=20 >> t->Callback(); >> delete t; >> >> }=20 >> >> delete $this;=20 >> >> } else {=20 >> >> qutex->Push($this);=20 >> >> }=20 >> >> return 0;=20 >> >> } >> >> >> It is very simple, now, but it wasn't year ago. And it is multiple=20 >> producer/single consumer queue (non-blocking, based on the atomic increm= ent=20 >> and compare exchange). >> >> I realize that in the standard library thread pool creation would be=20 >> explicit. Something like: >> >> auto h =3D std:setThreadPoolSize(32); >> >> and/or a thread pool handler could be passed as a parameter to forks and= =20 >> joins also. >> >> However, I don't think the "qutex" concept gets us anywhere close to=20 >>> where we ought to be in the end. >> >> >> What is the end?=20 >> >> I do not see any parallel computational model so far. >> Intel TBB Flow Graph or Intel Cnc are awkward. Imagine you have to=20 >> declare a call order of all functions of your program in advance and the= ir=20 >> call conditions. >> So, what is alternative? I have even more advance computational model,= =20 >> but it is a way out of the conventional thinking (Method for Automatic= =20 >> Parallel Computing >> ). >> >> By the way, you used 'qutex', not 'qumex'. I am not english native=20 >> speaker, so 'qumex' does not sound right? >> >> Thanks >> Andrew >> >> On Saturday, April 4, 2015 at 3:39:15 PM UTC-4, Arthur O'Dwyer wrote: >>> >>> Now that I've read more of the documentation and have a better idea of= =20 >>> the concepts involved... If I understand correctly, you start from the= =20 >>> atomic concept of >>> >>> (work-queue + consumer-pool-of-size-N) >>> >>> In your particular system there is a singleton global (work-queue +=20 >>> consumer-pool-of-size-LARGE) that you call "the thread pool", to which = jobs=20 >>> can be submitted via gpc::fork(); and your system also supports=20 >>> constructible-on-the-fly (work-queue + consumer-pool-of-size-1)s, which= you=20 >>> call "qutexes" and to which jobs can be submitted via qutex::join(). >>> >>> If anything like this model were proposed for standardization, I'd hope= =20 >>> that it would standardize the underlying (work-queue +=20 >>> consumer-pool-of-size-N) model, so that you could have=20 >>> constructible-on-the-fly work-queues with consumer-pools of size 2 (for= =20 >>> example). Perhaps the atomic concept should even *be* split up, so tha= t a=20 >>> single consumer-pool could pull from two different work-queues, etc. et= c. >>> >>> Notice that a work-queue with only a single producer and/or only a=20 >>> single consumer can be implemented with greater efficiency than a=20 >>> work-queue with multiple producers and/or consumers, so there's an=20 >>> efficiency win there that should be reflected in the library somehow.= =20 >>> However, I don't think the "qutex" concept gets us anywhere close to wh= ere=20 >>> we ought to be in the end. >>> >>> =E2=80=93Arthur >>> >>> On Saturday, April 4, 2015 at 7:46:59 AM UTC-7, t...@tentity.com wrote: >>>> >>>> Thanks.=20 >>>> Now I am thinking "qumex" which abbreviation for *Qu*eue of *M*utual= =20 >>>> *Ex*clusion.=20 >>>> Would it be better? >>>> >>>> On Friday, April 3, 2015 at 6:48:48 PM UTC-4, Arthur O'Dwyer wrote: >>>>> >>>>> On Friday, April 3, 2015 at 5:15:13 AM UTC-7, t...@tentity.com wrote: >>>>>> >>>>>> Quetex is Mutual Exclusion Queue. It eliminates blocking/waiting=20 >>>>>> and thread switching in comparison to mutexes and futures. >>>>>> >>>>>> gpc::quetex qtx; >>>>>> >>>>>> >>>>> Not related to the semantics, but FYI, "quetex" looks like it ought t= o=20 >>>>> be pronounced "kaytex", and you lose the pun. Consider "queuetex" or= =20 >>>>> "qutex" instead. :) >>>>> >>>>> =E2=80=93Arthur >>>>> >>>> --=20 ---=20 You received this message because you are subscribed to the Google Groups "= ISO C++ Standard - Future Proposals" group. To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposals+unsubscribe@isocpp.org. To post to this group, send email to std-proposals@isocpp.org. Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposa= ls/. ------=_Part_752_1822152842.1428689219954 Content-Type: text/html; charset=UTF-8 Content-Transfer-Encoding: quoted-printable
It seems you assume that a single consumer queue can be on= ly processed by one thread. 
Actually, it depends on an implem= entation.
In my implementation, at any moment of time only o= ne thread can process a queue (that is mutual exclusion),
but at = different times different threads can process the same queue.
And because a system can have a lot of single consumer queues, =
it also take care of tasks' fair ordering.

<= div>In some cases, it is good for modern hardware to process tasks from the= same queue on the same core.
Because the purpose of the mutual e= xclusion is to serialize access to some data.
After the first tas= k, the data will be in CPU cache, so next tasks do not have to fetch the da= ta from the main memory.

My algorithm is friendly = for CPU caches and NUMA optimization. 
And it is a working s= ystem. I use it for 2 years already.
I just recently integrated it with= V8, so I can do parallel computing with JavaScript now.


= On Friday, April 10, 2015 at 11:03:27 AM UTC-4, Zijie He wrote:
Single consumer queue is = not good for modern hardware, at least we need to have one thread i.e. one = consumer per core.

For the parallel computational model, I was worki= ng on .Net before, and was using lambda expressions to define the order of = steps,
imaging,

auto x =3D define_a_procedure(=
[]() {
... do some processor work ...
waitfo= r(an_io_or_lock); // the lock here is not the common lock
goto_ne= xt_step();
},
[]() {
... obtained the lock or io ope= ration finished ...
... do some processor work ...
goto= _finish();
});
run(x); // non-blocking
And each step= may work on different threads, the whole procedure will not stop until got= o_finish() involved.
But when porting to c++, issues as the lifet= ime of the procedure, it should keep alive until goto_finish(), and meanwhi= le, the most important thing is, if we need to refer some local variables &= lt;which is the reason to use lambda expressions>, we also need to consi= der the lifetime of these variables. I tried to use shared_ptr everywhere, = but still have some trouble.

On Sunday, April 5, 2015 at 7:39= :15 AM UTC+8, t...@tentity.com wrote:
Let me make some clarification.
In= my system, I have one thread pool for everything: forks, joins, http reque= sts, timers, etc.
I avoid creating threads (that is why I do not = use std::async) and I avoid switching threads.
I don't see any re= ason to have more than one thread per core (20 years ago I would do because= it was only one core CPU, but not now). 
So, I do not c= reate a thread pool per a qutex, but I use one thread pool for everything.&= nbsp;
Here is the algorithm of the mutual exclusion that is u= sed in the thread pool:

static intptr_t __stdcall Run(tef::sys::THREAD_TASK* task)
{

  ExclusiveTask* $this =3D <= span style=3D"color:#008">static_cast<= ExclusiveTask*>(task);

  = auto qutex =3D $this<= /span>->qut= ex;
  if( qutex->Lock() =3D=3D 1 = ) {

      $this->Callback(); = // call back the lambda

      whi= le( qut= ex->= Unlock() > = 0 ) {

  =        task =3D qutex->UnsafePop= ();

        &= nbsp;while( task =3D=3D nullptr ) {=

        &nbs= p;   task =3D qutex->UnsafePop();

         }
    &nbs= p;    // call back the lambda
        &nbs= p;ExclusiveTask* t =3D static_cast<ExclusiveTask*>(task);<= span style=3D"color:#000">
         t-><= span style=3D"color:#606">Callback= ();
         = delete = t;
<= br>      }

      delete $this;

  } else {

    &= nbsp; qutex->Push($this);

  }

  return 0= ;

}


It is very simple, now, but it wasn't year ago. And it is = multiple producer/single consumer queue (non-blocking, based on the atomic = increment and compare exchange).

I realize that in= the standard library thread pool creation would be explicit. Something lik= e:

auto h =3D std:setThreadPoolSize(32= );

and/o= r a thread pool handler could be passed as a parameter to forks and joins a= lso.

However, I don't think the "qutex= " concept gets us anywhere close to where we ought to be in the end.

What is the end? 

I= do not see any parallel computational model so far.
Intel TBB Fl= ow Graph or Intel Cnc are awkward. Imagine you have to declare a call order= of all functions of your program in advance and their call conditions.
So, what is alternative? I have even more advance computational mode= l, but it is a way out of the conventional thinking (Method for Automatic Parallel Computing).

By the way, you used 'qutex', not 'qumex'. I am not englis= h native speaker, so 'qumex' does not sound right?

Thanks
Andrew

On Saturday, April 4, 2015 at 3:39:15 PM = UTC-4, Arthur O'Dwyer wrote:
Now that I've read more of the documentation and have a better id= ea of the concepts involved... If I understand correctly, you start from th= e atomic concept of

    (work-queue + consumer= -pool-of-size-N)

In your particular system there i= s a singleton global (work-queue + consumer-pool-of-size-LARGE) that you ca= ll "the thread pool", to which jobs can be submitted via gpc::fork();  = ;and your system also supports constructible-on-the-fly (work-queue + consu= mer-pool-of-size-1)s, which you call "qutexes" and to which jobs can be sub= mitted via qutex::join().

If anything like th= is model were proposed for standardization, I'd hope that it would standard= ize the underlying (work-queue + consumer-pool-of-size-N) model, so that yo= u could have constructible-on-the-fly work-queues with consumer-pools of si= ze 2 (for example).  Perhaps the atomic concept should even *be* split= up, so that a single consumer-pool could pull from two different work-queu= es, etc. etc.

Notice that a work-queue with only a= single producer and/or only a single consumer can be implemented with grea= ter efficiency than a work-queue with multiple producers and/or consumers, = so there's an efficiency win there that should be reflected in the library = somehow. However, I don't think the "qutex" concept gets us anywhere close = to where we ought to be in the end.

=E2=80=93Arthu= r

On Saturday, April 4, 2015 at 7:46:59 AM UTC-7, t...@tentity.= com wrote:
Than= ks. 
Now I am thinking "qumex" which abbreviation for Queue= of Mutual Exclusion. 
Would it be better?
=
On Friday, April 3, 2015 at 6:48:48 PM UTC-4, Arthur O'Dwyer wrote:
On Friday, April 3, 20= 15 at 5:15:13 AM UTC-7, t...@tentity.com wrote:

Quetex is Mutual Exclusion Queue. It eliminates = blocking/waiting and thread switching in comparison to mutexes and futures.=


=  gpc::quetex<int> qtx;

<= br>
Not related to the semantics, but FYI, "quetex" looks like it= ought to be pronounced "kaytex", and you lose the pun. Consider "queuetex"= or "qutex" instead. :)

=E2=80=93Arthur

--

---
You received this message because you are subscribed to the Google Groups &= quot;ISO C++ Standard - Future Proposals" group.
To unsubscribe from this group and stop receiving emails from it, send an e= mail to std-proposa= ls+unsubscribe@isocpp.org.
To post to this group, send email to std-proposals@isocpp.org.
Visit this group at http://groups.google.com/a/isocpp.org/group/std-proposals/<= /a>.
------=_Part_752_1822152842.1428689219954-- ------=_Part_751_1543097202.1428689219953-- .