From mboxrd@z Thu Jan 1 00:00:00 1970 X-Msuck: nntp://news.gmane.org/gmane.linux.lib.musl.general/5908 Path: news.gmane.org!not-for-mail From: Jens Gustedt Newsgroups: gmane.linux.lib.musl.general Subject: Re: Multi-threaded performance progress Date: Tue, 26 Aug 2014 20:30:39 +0200 Message-ID: <1409077839.8054.54.camel@eris.loria.fr> References: <20140826034321.GA13999@brightrain.aerifal.cx> <1409036654.4835.14.camel@eris.loria.fr> <1409070919.8054.47.camel@eris.loria.fr> <20140826175304.GD12888@brightrain.aerifal.cx> Reply-To: musl@lists.openwall.com NNTP-Posting-Host: plane.gmane.org Mime-Version: 1.0 Content-Type: multipart/signed; micalg="pgp-sha1"; protocol="application/pgp-signature"; boundary="=-59C11PcmS9qtoZ1DmjDQ" X-Trace: ger.gmane.org 1409077850 14284 80.91.229.3 (26 Aug 2014 18:30:50 GMT) X-Complaints-To: usenet@ger.gmane.org NNTP-Posting-Date: Tue, 26 Aug 2014 18:30:50 +0000 (UTC) To: musl@lists.openwall.com Original-X-From: musl-return-5914-gllmg-musl=m.gmane.org@lists.openwall.com Tue Aug 26 20:30:45 2014 Return-path: Envelope-to: gllmg-musl@plane.gmane.org Original-Received: from mother.openwall.net ([195.42.179.200]) by plane.gmane.org with smtp (Exim 4.69) (envelope-from ) id 1XMLVz-0007Rn-CO for gllmg-musl@plane.gmane.org; Tue, 26 Aug 2014 20:30:43 +0200 Original-Received: (qmail 3577 invoked by uid 550); 26 Aug 2014 18:30:42 -0000 Mailing-List: contact musl-help@lists.openwall.com; run by ezmlm Precedence: bulk List-Post: List-Help: List-Unsubscribe: List-Subscribe: Original-Received: (qmail 3567 invoked from network); 26 Aug 2014 18:30:42 -0000 X-IronPort-AV: E=Sophos;i="5.04,405,1406584800"; d="scan'";a="91565871" In-Reply-To: <20140826175304.GD12888@brightrain.aerifal.cx> Face: iVBORw0KGgoAAAANSUhEUgAAADAAAAAwCAYAAABXAvmHAAAABHNCSVQICAgIfAhkiAAAEb9JREFUaN7VmXuQ3lV5xz/n/O7v7333fffdW3azSTY3Qi6wGy4aEc0qWlGhWcAq7WiDrWNpO61paS29EpzWaevYpvfL2JK0VRBbBxQtg0U2BRGKhIAI4ZKwSTbZ+3u//G7nnP7BtGM7UyVAnfb56/xznuf7nXnOnOf5fuH/eYjXI8mDn/5k8ch90xNj+eKka8xkI1MTGmY6Rk/XpD5w091fPvnf7xz8sQ/sLTQ6k54SY2mW1mQY3DVX8Kdv/PvPnfyBE7hn797bxBPP3NBv28RAqgyzJqNgJIs5q7bhHW+94Yd+5/fuBrjj5l/cs/LUs/vNiVMTo5aNJQX9lks3iaivHqlt/9D7xs778Y/Uf6AE/uWa6x7wT52ZTDyLKEkoOHmW4oSaSDFxQmq7tHPuDJ5TUkv10iAGgSLvediZotf16HS6KG1RuXDT/g99/vO3vtLa8vUgELuCVAja0mVJKRaylGbgYnwP27bImYRcozkmKrWS53vYjosfhNSUIjXQUoq2K0ksRdZqTZ5Lbfs/Dl/66E/uSebmb8hF8URab48JS+IPDVJtto9uuHj8wKW//6lD/1OSznxtLEPRv2kdPH2MSBpkqlDGkLoOIgGkIWcEiTYsk1JSDpGUFAAcBzfRCKXxV+ql7/XWnn7uxcm3vOGS2rrR1UcLV+6pC4B//tjPjGdHjhwttFOEcMmMAgFeLkezWsOTkmigfyYZGTzYN7HtwFt u+rU6wJnprxQf/JvP7beffH5fBIwGIZqEutJUlCKSNoFjYbQiihOkFmih0FJgSUGIpGxstE6RwiLQmsyzcXZesO8N1773YOHKPfUv/uxP726ePjsVNVoT9WZjMq02kRpEKay9+UPXjQmAL1991UuDZ+fGQulSVQrpuqg4pWkkupSjVGshtGZJpzQ9DysfQqZIkgzR7 jAc+qAFrm2xTIRJJKnr0okTfCnQKLRlo9MUicGWL7dcnCnytoOTKTxpERpBv8moomm7AZFjEddb9EiHdhJhPJdYanQKUZrivmH7Pnlm+itFuVgdi7WkpSSJdFlqRwRugLAkQakXJQ06cAhcB0tnRI0mstOllKYEvk8qJJGj8IygID16hwZBGIzIsIXCRREq6DGSsu9RkBYBBldKbCFwbMnA2mH8wKIrbQrGY1WkKbQ6DFkWOQEicMks8JTEQRJI0LOLJbvxwosTMlMk0kYbjTCGci4gzrr0Sod0YQFHWiSuRTHMkbRaCCxMZlh2FLGQLEjBmHFIhUBrEI0OlgYnyNN0LFKliYxGeT69rouqtOjP5+lLEtxugosgOjNHj7ZRGmwjaDoGX9skKEQQIFptkAIjIWckCQIrE9ija8aOznk5wiwh9lw8aeMlMamUeEKis4wOFiaFRtpEYxBJSoQA4ZM4ksgSPG4E9Siibjt02xUaUQsnzFFfSZlPM4TRlPp7yQWCs/PzlMs53HrMRLGPt/f2UFYRbkOzbGm6JkPgYjAgbVo6I/Ntup0unuPgWAK0RaLVy//AfVe864lgcWkicz1yloNvoJMmpFLTsiCJNIFt0VERHdcnGyxPW5598BmlJo6tVPc9v1RB2CHdqMWOYpkLCwHnhyHVTHNcpTxUrVCp1rAtyYZ1w0i3SLFk89A3/g2UZH3O4ubL30RxsU5ldhkpDFJIbGFRE4rYSLQQRHGEJQQeFm7gYHaev98CuO6NF62q1hqTKktJlKarNW0JDZUgHA9dys/Y q4emnQ3Df3nxj7z7+t2f+pO/Ysv5U0dm525uKYty3wCetPjRdYNcjaaQabq1Oq1MkVOKkc1reGFhiWIuj7C6JGlKyZNsNor3n7eFStLlkcoKz61fvX/79u3T9cWliTBWvrQEHa0QQmIZgdIK27FQmaKVxIRbN+77z5/4sT/+1PjJEycmosWVmXJvP3YpZM3aNYyuWz dTuHLPf5lPrnr3VXtPnDp10HNDlIqROEwO9fG+VosXspQ7lyto3+fE8ln2rlpDfniQP332WRCCd75tB43jZ7jUDRlspTiugxAeR+I2960s0hBy3503fmT69FcfONian5uQliDIF+m2YyKlUUIRxRF968eOfuC+r+4851Hill//+PiRx79ztNrs0mm0KZaLZEnGWwsB725WOFRv8HAmSDodSo7D3oF+bMfirxbOYkKHQDhc5lusznxaaO6fO8O2fIE9vf1M0+Go0jM73nT55EcvGa8duedr+3S1si8v7VLnzDxRpkjCHGJ4aHr1utVT7/mzP6/b5wJ++v57izf9wi8dVNrHcT3yxQK27RJ3Y6zM0LI1b+0ZoFldIvFsxvsH6LMELQOpkST1GBVq3NIAvvC54ztPcTwRLOs2b+sf4u2RS5JFY1++5yt3XbXnvZPX3/n5W4FbH/nLA+ueuOeBG/zefG3ynW87+N3D3jkRuP3226fiVEwkOiV0bNIsJep28QOfqOAjl2DEElw1WCZKFGUtkK6h7fj4DpRKfURJjeGwSE/UJcJga4d6p0lHCoo64w1BkfsqtYnf/LVPHgSuAdh1476TwMsD3t9/9jUMc9pMSiGxJRgV0+22Wa7XqTfqHH7pON8u9/NE6BB5PnZPD42BkMe14IG4gVXIsVSvkijFU2fPIrOUraPrsD3Jlt4SnTQlsi2qtqLSarG0VJnaObHztu8HyTqX9vn6Aw/cMTw0TJpkeH6AhaIncCn3FkmFzWNzc3y7U+ObjTqPVJs8Vq1h1oScabdoV xWxyQg9l57BATZZDpuCgH5PMrVxM3G3g513WfNDW3liYRGsPN1ua2LHtq0zM6dOPfmqCDx15227/+ILd58EaNa717/00smp3bsvo7fcS3VpGTcAKV2q1QZJ3MVIC88JsFJN2c+xbrDM+aHPlqE+ji0vY7kWvaFhaaXJzs3nYaoNNq/tJ1/tsiwtnpEOtz/+HHNLMXG UkmYp7XarVKlWD53TQtO89+7iN//stoPWqdkpPx/Wur3F6WccZ+KFdnuskXNZaCVkiWJ++Qy+59EbuHi6y1t2XkL27Ak2CJssS6lHMYPCYDLDP/dJvj1fQ0qb+WoMqk3BzrFlYAidc5hZXAQnh9DQ6TbRQhF3U7Is4eZf+YWJj9308Se/5z7w3fH8s8fGnNOnp1ZJie52S+VOd2oIeJObo2Vs5i2JWZWn1e/TrjQZK/WSiyPCE2eImh1S12PJaEJtYbsCN81oL7eROPQVodVI6ZiA1MvxQhyhOxGWlcOkKUHg4aQOaaoQ0hDFXf7pi3dPAk+e00r56HuurubnzpZsY5NKiYMhwUagcY1CCINB0pACIQXLoaBHWdTbXbTwWHEhHwQE9SbVgRJ/Mz/Hi4sr7H3fOIuVJvc+OEsYFnG8AKETGs0WljBYtk2j3nkZmRDoqMPqdSNHHztyZOc5rZTpQHlfIh2MpdDSgAZbZ/hGgzRIaSEF9AiNLyWylRFbNh0bfKEZsCxkK2JxZJi/Pv0CJyornLd5DQ8++hxHv7NIEFg0W00ajRqNRh3XtciUot5okBlFZgzSssm04fjxExN/+kcHxs+JwOWHDh06u3bkQNV1a7ZSIDWehEQoUgEaQGtMlpHlLXp6XPLdjFyqwBMsAvfR5D4Z0fFKbNqwgWajgnQHWF6K8V0H35EIrQFodWKSzGAJQc63sS2JylKkZaO1ZnTNqplXpUo07727+NV/vPuAv3D2hrWpRtYaZJbEwmBlINf00144S35kgMZsxEpgc0zEfL3Spu 1LklihlU2u6NBtNZDaohXHIDKadYWRLsZkZFhgNCaLcB2XzECWalAZhR6v9vzx472v+BF/dxSu3FPf9cY3z0TNLgO+YFNfHzozJHFE4CvW1CPGBvtYabQ5YQuON+aI7YCqUTSX2hgTUeop025IstSiv1wiUQu4fkiz2SBTHaSQ9AQOaZqBk6MTdzFGYAnB0FAvWjD9 fVWJ7xUjI+XJ54/NMNeVLM3XMEZjWRYGzf2dWUp5kJZNmlmE+RDdaXHpznFOzc6xOL8AKIqlArVaTKdTQSvD4sIifb29KOOgshaOJal0UzSgjcQYyNKU4zMzXHTR+F2vSRdKOm3CnIvnO4QFn77ePL7vErVaqLhN4OUYcGHL+j7iVoeBoX5mT5+mtjzHeRtLDA2UWFqYx3c8Ot2MocE875y8iMCHLElIogytDVJKjFIYLUiiCKVihkeGD379Xx869JoICGHj2C4qU2ASFqsLNFptvMBj9ZoSlzgen7hiFz919QQDoWB+9gwqU4SFXk6eXGHN6kH6e21Wls7SX3Zot5t889HvUKlFL8ssJkOgAIXv2+gswqiYjRvHjv7qr+zb94qEre8Vnu/juRlKCTJlgQhBxdRaTVb1lNh7yRb41tOUR99G72Afza6h0e7gezZWOMzRY7NIZVHoyVOtxli2hSUEaarJlwLqOqOTaoTMYVmagXKOQnHk6O/+7u9MTl5xZf01D3NrR0dK7W58pe/naHS7SB1z7fg6fm58I2/OuRSencH2HIIffjNzLRhfv5ZGo85itU6aSRr1Jq6laEcJjcgwWA7YMOoS5B2WKx38oEAUJURRhko1nm9P/8EffvrK7wf+FbfQjT/zUwdzoTvTjVv4UlK0XHZs3UTZd1mbaqyiCwKc02d4v51ycW2Zy9Zvw+AQ5DxW9RcoFwRDZZ9VA2UAdu26iD3vupQLto5SrXSwpIPjKsbWr+aDH/zg/lcC/pzU6Y98eO/4iReem67WOyU/6KFdX2S kELLRU3y0d5Cg1aEZBqSxQJdtprXL5546guXm6QtCwmKOTrvC2NoSq8tw8fYSDx9t8tATVSqNOo16lzdech7Ndrz/a4e/9fqr05+57dCTW7edtz/fE2JIySyHlxqKr8+3OFXooykND8ocf1vwuD1WHO1G5AKPUi5EYVGpLeA4OcqhZtVASKtjkLZFpjM6nZjNG0dnN p63fepcwL8qf+BdV+x+YGmxNimRtNOUJI3Z1APX7NjBPxx5ntjLQRLTTBKGSz4jwz3UajWGhgap1uqcPFXh0ovX88zTz1Mo9tJNQdiF6d273zh1y29/un6ueM7ZH7hw24apfGDPJN02ri0phXlUaZi/e3qGSpziOgKjI8qhS73eQKuUIBAsLS3i+x5DQ0W6zRUyY1hpiNrAwND+PXve+6rAv2qH5rdv+dXxr933tbtWlqpj/cOjkAkWaosUHUW5UGBmYZF1AwM0WjUKvX2g25TLJZ56dh7Pztg5vmFm8vIL9udHLrtr6trrXxXw12wxTd9/b/ETt95y15lTC5Pbtu2gUVkgaTeItSJKDI4Fo6t66cZtbNuiUu8QlvpnVq0auuGzd3758P8Jl3L6/nuLf3Tg05OWEJOFfH4iiuLJOMlYXmnSrDURaIxJEFJzwYXb9x+640u38v8hPvazP717+5atZtvmrWbN6vVm9dBqc83VP7znf6OW/Xok+a2b941XG9HY7KmTE81me/Khww+P5XMFkszQiFIKPQEQTwF3/58zui+98IK9KA4W8gVOn10kF4Tk8z7SdWl2I6JWA0fE9A+VqdXq0x/+iQ/f8PM3/cbJ14vAa7JZr3rXFR+bn188aFk2veUCxXIPQeiDkdQbbXKuZP3qIju3rcVKm7z9su2TTxy+a+Yzn3z/La8XAevVXrzu2j3jBnlXrVonVSmtbpdms40AwlyeTGeEtk2r00HYLhdsXc/OrR4XbVaU/Mbkb930nqme0rrowUefffIHTuC6a/fsPfbM C3d0WolfKhTp6clRyhcg04xtGCHt1Dh/rExRamYWGyxXa7xn1yYuvkAwP7fClg0Zhx+qr/rM7d+Yesc73nHD5OW7Zh478tRzPxACH/iRa245duzkAdsJfMuy8aXm/FUFlpeWWOm2WZidI9WapaUlFIaTlQ4jfR6/vO9D2NE32LTeYnZOUmnA6PAohx9+qnTy1NnrP/ Cj15cu23XZI4/826Px/xqB37z547sPH374oOvnKTsOb+1zuCoImZARM8ZiLlKkXcWOcoFRJ+Do/CwFO4e2DEe+9Ti+ZXA8ny/cU+X4bMKRZxZIVEiqXI6/+NKuUzPHb7z40ovnX3zx+Ctuq38HyuqWG7Tu+A0AAAAASUVORK5CYII= X-Mailer: Evolution 3.4.4-3 Xref: news.gmane.org gmane.linux.lib.musl.general:5908 Archived-At: --=-59C11PcmS9qtoZ1DmjDQ Content-Type: text/plain; charset="ISO-8859-1" Content-Transfer-Encoding: quoted-printable Am Dienstag, den 26.08.2014, 13:53 -0400 schrieb Rich Felker: > I should have bothered to check and see that there was a patch before > responding... >=20 > On Tue, Aug 26, 2014 at 06:35:19PM +0200, Jens Gustedt wrote: > > diff --git a/src/thread/pthread_cond_timedwait.c b/src/thread/pthread_c= ond_timedwait.c > > index 2d192b0..136fa6a 100644 > > --- a/src/thread/pthread_cond_timedwait.c > > +++ b/src/thread/pthread_cond_timedwait.c > > @@ -42,12 +42,32 @@ static inline void lock(volatile int *l) > > } > > } > > =20 > > +/* Avoid taking the lock if we know it isn't necessary. */ > > +static inline int lockRace(volatile int *l, int*volatile* notifier) > > +{ > > + int ret =3D 1; > > + if (!*notifier && (ret =3D a_cas(l, 0, 1))) { > > + a_cas(l, 1, 2); > > + do __wait(l, 0, 2, 1); > > + while (!*notifier && (ret =3D a_cas(l, 0, 2))); > > + } > > + return ret; > > +} >=20 > This code was confusing at first, and technically *notifier is > accessed without synchronization -- it may be written by one thread > and read by another without any intervening barrier. I suspect it > works, but I'd like to avoid it. But it does answer my question about > how you were detecting the case of "don't need to lock". Hm, I don't see the point of your remark, musl is doing such "atomic" reads all over, no? There is no macro for atomic load, only for atomic store, otherwise I would have used that. And notice that *notifier is volatile, so the load can't be optimized out. Or do you mean that I should use an atomic store at the other end? > Note that the performance of the code in which you're trying to avoid > the lock does not matter in the slightest except when a race happens > between a thread acting on cancellation or timeout and a signaler > (since that's the only time it runs). I expect this is extremely rare, > so unless we determine otherwise, I'd rather not add complexity here. If we have a broadcaster working a long list of waiters, this might still happen sufficiently often. And the "complexity" is hidden in the execution pattern of the current version, where control and handling of the list alternates between different threads, potentially as many times as there are waiters in the list. > > int pthread_cond_timedwait(pthread_cond_t *restrict c, pthread_mutex_t= *restrict m, const struct timespec *restrict ts) > > { > > - struct waiter node =3D { .cond =3D c, .mutex =3D m }; > > + struct waiter node =3D { .cond =3D c, .mutex =3D m, .state =3D WAITIN= G, .barrier =3D 2 }; >=20 > This may slightly pessimize process-shared cond vars, but seems ok. >=20 > > +static inline int cond_signal (struct waiter * p, int* ref) > > +{ > > + int ret =3D a_cas(&p->state, WAITING, SIGNALED); > > + if (ret !=3D WAITING) { > > + ref[0]++; > > + p->notify =3D ref; > > + if (p->prev) p->prev->next =3D p->next; > > + if (p->next) p->next->prev =3D p->prev; > > + p->next =3D 0; > > + p->prev =3D 0; > > + } > > + return ret; > > +} > > + > > int __private_cond_signal(pthread_cond_t *c, int n) > > { > > - struct waiter *p, *first=3D0; > > - int ref =3D 0, cur; > > + struct waiter *p, *prev, *first=3D0; > > + int ref[2] =3D { 0 }, cur; > > =20 > > - lock(&c->_c_lock); > > - for (p=3Dc->_c_tail; n && p; p=3Dp->prev) { > > - if (a_cas(&p->state, WAITING, SIGNALED) !=3D WAITING) { > > - ref++; > > - p->notify =3D &ref; > > + if (n =3D=3D 1) { > > + lock(&c->_c_lock); > > + for (p=3Dc->_c_tail; p; p=3Dprev) { > > + prev =3D p->prev; > > + if (!cond_signal(p, ref)) { > > + first=3Dp; > > + p=3Dprev; > > + first->prev =3D 0; > > + break; > > + } > > + } > > + /* Split the list, leaving any remainder on the cv. */ > > + if (p) { > > + p->next =3D 0; > > } else { > > - n--; > > - if (!first) first=3Dp; > > + c->_c_head =3D 0; > > } > > - } > > - /* Split the list, leaving any remainder on the cv. */ > > - if (p) { > > - if (p->next) p->next->prev =3D 0; > > - p->next =3D 0; > > + c->_c_tail =3D p; > > + unlockRace(&c->_c_lock, ref[0]); > > } else { > > - c->_c_head =3D 0; > > + lock(&c->_c_lock); > > + struct waiter * head =3D c->_c_head; > > + if (head) { > > + /* Signal head and tail first to reduce possible > > + * races for the cv to the beginning of the > > + * processing. */ > > + int headrace =3D cond_signal(head, ref); > > + struct waiter * tail =3D c->_c_tail; > > + p=3Dtail->prev; > > + if (tail !=3D head) { > > + if (!cond_signal(tail, ref)) first=3Dtail; > > + else while (p !=3D head) { > > + prev =3D p->prev; > > + if (!cond_signal(p, ref)) { > > + first=3Dp; > > + p=3Dprev; > > + break; > > + } > > + p=3Dprev; > > + } > > + } > > + if (!first && !headrace) first =3D head; > > + c->_c_head =3D 0; > > + c->_c_tail =3D 0; > > + /* Now process the inner part of the list. */ > > + if (p) { > > + while (p !=3D head) { > > + prev =3D p->prev; > > + cond_signal(p, ref); > > + p=3Dprev; > > + } > > + } > > + } > > + unlockRace(&c->_c_lock, ref[0]); > > } > > - c->_c_tail =3D p; > > - unlock(&c->_c_lock); > > =20 > > /* Wait for any waiters in the LEAVING state to remove > > * themselves from the list before returning or allowing > > * signaled threads to proceed. */ > > - while ((cur =3D ref)) __wait(&ref, 0, cur, 1); > > + while ((cur =3D ref[0])) __wait(&ref[0], &ref[1], cur, 1); > > =20 > > /* Allow first signaled waiter, if any, to proceed. */ > > if (first) unlock(&first->barrier); >=20 > This is sufficiently more complex that I think we'd need evidence that > the races actually adversely affect performance for it to be > justified. I can imagine that seen as it is here, this looks invasive, but it isn't really. This is just the merge of about 10 patches that more or less rewrite to something functionally equivalent. (well, with some obvious exeptions.) I found posting all those patches too much for the list, was I wrong? > And if it is justified, the code should probably be moved > to pthread_cond_signal and pthread_cond_broadcast rather than 2 cases > in one function here. The only reason both cases are covered in one > function now is that they're naturally trivial special cases of the > exact same code. Sure, that could and should perhaps be done, although the fact working on just one file and being able to have a bunch of helper functions as static inline was quite convenient. Jens --=20 :: INRIA Nancy Grand Est ::: AlGorille ::: ICube/ICPS ::: :: ::::::::::::::: office Strasbourg : +33 368854536 :: :: :::::::::::::::::::::: gsm France : +33 651400183 :: :: ::::::::::::::: gsm international : +49 15737185122 :: :: http://icube-icps.unistra.fr/index.php/Jens_Gustedt :: --=-59C11PcmS9qtoZ1DmjDQ Content-Type: application/pgp-signature; name="signature.asc" Content-Description: This is a digitally signed message part Content-Transfer-Encoding: 7bit -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.12 (GNU/Linux) iEYEABECAAYFAlP80k8ACgkQD9PoadrVN+IdQACeK8bpHN5zdlIn4CLYgA1xtf8r wr0AoIjEy5GLqdhcWhPK2inCIVNY6oFU =quMQ -----END PGP SIGNATURE----- --=-59C11PcmS9qtoZ1DmjDQ--