Date: Thu, 30 Jul 2015 18:07:44 +0200 From: Jens Gustedt <jens.gustedt@...ia.fr> To: musl@...ts.openwall.com Subject: Re: New optimized normal-type mutex? Am Donnerstag, den 30.07.2015, 09:46 -0400 schrieb Rich Felker: > On Thu, Jul 30, 2015 at 02:37:13PM +0300, Alexander Monakov wrote: > > On Thu, 30 Jul 2015, Jens Gustedt wrote: > > > Am Donnerstag, den 30.07.2015, 12:36 +0300 schrieb Alexander Monakov: > > > > That sounds like your testcase simulates a load where you'd be better off with > > > > a spinlock in the first place, no? > > > > > > Hm, this is not a "testcase" in the sense that this is the real code > > > that I'd like to use for the generic atomic lock-full stuff. My test > > > is just using this atomic lock-full thing, with a lot of threads that > > > use the same head of a "lock-free" FIFO implementation. There the > > > inner part in the critical section is just memcpy of some bytes. For > > > reasonable uses of atomics this should be about 16 to 32 bytes that > > > are copied. > > > > > > So this is really a use case that I consider important, and that I > > > would like to see implemented with similar performance. > > > > I acknowledge that that seems like an important case, but you have not > > addressed my main point. I will try to discuss this below. > > With so little work in the critical section, it does > > not make sense to me that you would use something like a normal-type futex-y > > mutex. Even a call/return to grab it gives you some overhead. I'd expect you > > would use a fully inlined spinlock acquisition/release around the memory copy. > > No, spinlocks are completely unusable in a POSIX libc that implements > priorities. They will deadlock whenever a lower-priority thread gets > preempted by a higher-priority one while holding the lock. First, you may not have recognized this, what I use is *exactly* the actual strategy of LOCK/UNLOCK that musl implements. If you don't obtain the lock, spin for one hundred rounds, and then try to go into a futex wait. (I copied the code from musl and did just some transformations to fit the case.) The difference is that I avoid incrementing and decrementing the counter at each iteration (this could perhaps be done with the actual version, too), and that the combination of flag and counter in one word helps that both the fast-path for lock and then unlock, only need a single CAS, each. Now let us try to figure out what happens in the case that started this new discussion, namely that there is so much contention such that the probability of an EAGAIN-failure of the mutex call increases. In fact even if inside the critical section the application itself does nothing, the lock code first does the spinning. So regardless of the application, any thread does 100 spins (so some work) before it starts fighting to be put to sleep on the futex. None of the threads reaching that point, changes the value of of the counter, so all threads that reach the point and call futex_wait "simultaneously" know about the same actual value. The value can only change by new threads entering the acquisition loop. There are no more such threads at a time than can be effectively be scheduled. These will all spend some time spinning, so there can't be a bad cascade of such threads that change the counter. In fact, there will certainly be a tradeoff between the number of spins and the overall waste in CPU time and bandwidth. I will experiment a bit with that. As I said, for other functions such as timed locks and certainly for condition variables we'd have to look very carefully. I haven't really thought of them, and I don't have any claim about them. Jens -- :: INRIA Nancy Grand Est ::: Camus ::::::: ICube/ICPS ::: :: ::::::::::::::: office Strasbourg : +33 368854536 :: :: :::::::::::::::::::::: gsm France : +33 651400183 :: :: ::::::::::::::: gsm international : +49 15737185122 :: :: http://icube-icps.unistra.fr/index.php/Jens_Gustedt :: Download attachment "signature.asc" of type "application/pgp-signature" (182 bytes)
Powered by blists - more mailing lists
Confused about mailing lists and their use? Read about mailing lists on Wikipedia and check out these guidelines on proper formatting of your messages.