From: Nikodemus S. <nik...@ra...> - 2008-02-17 10:42:16
|
I wonder if we should implement something similar for spinlocks: http://lwn.net/Articles/267968/ Cheers, -- Nikodemus |
From: Nikodemus S. <nik...@ra...> - 2008-08-07 14:41:24
Attachments:
0001-fair-spinlocks.patch
|
On Sun, Feb 17, 2008 at 1:42 PM, Nikodemus Siivola <nik...@ra...> wrote: > I wonder if we should implement something similar for spinlocks: > > http://lwn.net/Articles/267968/ Attached a tentative patch and benchmark. Executive summary: performance roughly comparable to lutexes on OS X even in highly contested situations with substantial sleeps while holding the lock; no problems at all with worst-case behaviour. Currently this implementation conses, but that should not be too hard to fix. Not extensively tested yet, but code review much appreciated. Cheers, -- Nikodemus |
From: Nikodemus S. <nik...@ra...> - 2008-08-07 14:42:17
Attachments:
lockprof.lisp
|
On Thu, Aug 7, 2008 at 5:41 PM, Nikodemus Siivola <nik...@ra...> wrote: > On Sun, Feb 17, 2008 at 1:42 PM, Nikodemus Siivola > <nik...@ra...> wrote: >> I wonder if we should implement something similar for spinlocks: >> >> http://lwn.net/Articles/267968/ > > Attached a tentative patch and benchmark. Hit SEND too soon, here's the benchmark code. > Cheers, > > -- Nikodemus |
From: F. <fa...@gm...> - 2008-08-07 20:37:19
|
Once again, spinlocks are a VERY BAD IDEA for anything but a kernel (and even in a kernel, only if it isn't being parahyperdupervirtualized on an SMP): every time your thread gets interrupted in the middle of holding the spinlock, the other threads keep busywaiting on it, and you lose all the speedup, and get atrocious latency -- just at the time when you need it most, i.e. when there is actual resource contention. IMNSHO, SBCL should NOT be using any kind of spinlocks by default, but use lutexes or other safe mechanisms. [ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ] To send men to the firing squad, judicial proof is unnecessary... These procedures are an archaic bourgeois detail. This is a revolution! And a revolutionary must become a cold killing machine motivated by pure hate. -- Che Guevara 2008/8/7 Nikodemus Siivola <nik...@ra...>: > On Thu, Aug 7, 2008 at 5:41 PM, Nikodemus Siivola > <nik...@ra...> wrote: >> On Sun, Feb 17, 2008 at 1:42 PM, Nikodemus Siivola >> <nik...@ra...> wrote: >>> I wonder if we should implement something similar for spinlocks: >>> >>> http://lwn.net/Articles/267968/ >> >> Attached a tentative patch and benchmark. > > Hit SEND too soon, here's the benchmark code. > >> Cheers, >> >> -- Nikodemus |
From: F. <fa...@gm...> - 2008-08-07 21:28:04
|
[Replying on the list to Nikodemus's reply copied below. I hope I'm not doing wrong.] > * Generally speaking spinlocks are used when mutexes cannot be used > (eg. in interrupt handlers -- IIRC futexes are safe there, but futexes > don't exist everywhere), or when interrupts are disabled anyways. Then, I'd argue that wherever futexes exist, they should be used to the exclusion of any kind of spinlocks. > * Any thread that is interrupted while holding a critical lock is > going to grind the system to halt, no matter what kind a lock. Bad > spinlocks will spend humongous amounts of CPU, good ones won't I argue that ultimately, no spinlock can be good outside of the kernel, because only the kernel really cannot be interrupted (and there again, only if it's not metasupervisoredualized). > My point: there are places that spinlocks pretty much have to be used > internally, and there are platforms where the OS provided facilities > suck so badly that a good spinlock implementation is competitive -- > and not prone to mysterious kernel error messages when pushed hard. > *cough* Apple *cough* Use spinlocks on MacOS if you must and then indeed try to make spinlocks perform better rather than worse. But I don't see places where you'd need them under say a modern linux kernel. Is SBCL using spinlocks anywhere on a modern Linux? [ François-René ÐVB Rideau | Reflection&Cybernethics | http://fare.tunes.org ] Racists often attribute to genetics what is due to memetics. Anti-racists often do the opposite. Both groups involve legal violence where none is due. On Thu, Aug 7, 2008 at 11:37 PM, Faré <fa...@gm...> wrote: > Once again, spinlocks are a VERY BAD IDEA for anything but a kernel > (and even in a kernel, only if it isn't being > parahyperdupervirtualized on an SMP): every time your thread gets > interrupted in the middle of holding the spinlock, the other threads > keep busywaiting on it, and you lose all the speedup, and get > atrocious latency -- just at the time when you need it most, i.e. when > there is actual resource contention. IMNSHO, SBCL should NOT be using > any kind of spinlocks by default, but use lutexes or other safe > mechanisms. I basically agree, but: * Generally speaking spinlocks are used when mutexes cannot be used (eg. in interrupt handlers -- IIRC futexes are safe there, but futexes don't exist everywhere), or when interrupts are disabled anyways. * On platforms where there are no pthread_cond_timedwait or futexes we cannot implement mutexes with timeouts without doing something analogous to spinlocks. * Any thread that is interrupted while holding a critical lock is going to grind the system to halt, no matter what kind a lock. Bad spinlocks will spend humongous amounts of CPU, good ones won't -- likely more then locks with wakeups, but the difference is not as big as you think. Real problem is being able to time out waits on such locks -- which we currently cannot do on eg. OS X. Benchmark is 20 threads on an Intel MacBook Pro, each thread contends on the same lock, after grabbing it sleeps average of 0.01 seconds of realtime, and spins for average of 0.01 seconds of *run* time, then releases it -- and tries to do the same again for 50 times. Reported times are run-time seconds that waiting for the lock took. Fair spinlocks vs. lutex based mutexes. ;;;; (time (profile-lock (sb-thread::make-spinlock) #'sb-thread:: ... (:WORST 0.244 :MEAN 0.210442 :MEDIAN 0.212) Evaluation took: 12.350 seconds of real time 11.153726 seconds of total run time (4.036065 user, 7.117661 system) 90.32% CPU 27,108,488,017 processor cycles 1,519,040 bytes consed ;;;; (time (profile-lock (sb-thread::make-mutex) #'sb-thread::get ... (:WORST 0.242 :MEAN 0.200522 :MEDIAN 0.2015) Evaluation took: 10.709 seconds of real time 10.669530 seconds of total run time (3.442065 user, 7.227465 system) 99.64% CPU 27,773,845,645 processor cycles 233,808 bytes consed Note how close spinlocks are and how little CPU they spend *despite* consing like mad -- which can be fixed. My point: there are places that spinlocks pretty much have to be used internally, and there are platforms where the OS provided facilities suck so badly that a good spinlock implementation is competitive -- and not prone to mysterious kernel error messages when pushed hard. *cough* Apple *cough* ...so as long as we are going to live with spinlocks, at least they should be ones that perform nicely. Cheers, -- Nikodemus |
From: Nikodemus S. <nik...@ra...> - 2008-08-07 22:15:22
|
On Fri, Aug 8, 2008 at 12:28 AM, Faré <fa...@gm...> wrote: > [Replying on the list to Nikodemus's reply copied below. I hope I'm > not doing wrong.] No problem. :) > Then, I'd argue that wherever futexes exist, they should be used to > the exclusion of any kind of spinlocks. Probably. Unfortunately quick googling neither verified nor disproved my recollection that futexes as safe to use in signal handlers -- but assuming that is so, it is probably TRT. Doing that requires building a new internal lock abstraction that is built on top of futexes on platforms where they exist and are signal handler safe, and fair spinlocks elsewhere. Not hard, just something that needs doing. (Though since optimizations are increasingly about memory hierarchy, a futex based mutex has to use an atomic operation to both grab and release the lock even in uncontended cases, whereas a fair spinlock needs an atomic operation only to grab -- so there *might* be places where spinlocks remain the winning solution, but figuring out which they are is not an easy thing.) >> * Any thread that is interrupted while holding a critical lock is >> going to grind the system to halt, no matter what kind a lock. Bad >> spinlocks will spend humongous amounts of CPU, good ones won't > I argue that ultimately, no spinlock can be good outside of the > kernel, because only the kernel really cannot be interrupted (and > there again, only if it's not metasupervisoredualized). The possible memory locking issues aside, assuming good OS provided facilities, yes. > where you'd need them under say a modern linux kernel. Is SBCL using > spinlocks anywhere on a modern Linux? Yes -- both in places where they can be at least vaguely defended, and in places where the motivation is not so clear. ...and as long as we don't have the abstraction alluded to above, we *should* be using them everywhere were we handling signals. :/ ...that said, type errors from compiled code are typically handled inside signal handles still, so almost anything can end up running inside a signal handler. :/ Someone(tm) really needs to teach arrange_return_to_lisp_function to pass arguments to the lisp side. Cheers, -- Nikodemus |
From: Gábor M. <me...@re...> - 2008-08-08 07:06:01
|
On Viernes 08 Agosto 2008, Nikodemus Siivola wrote: > ...that said, type errors from compiled code are typically handled > inside signal handles still, so almost anything can end up running > inside a signal handler. :/ Someone(tm) really needs to teach > arrange_return_to_lisp_function to pass arguments to the lisp side. Getting offtpic, here. I came to think that rules about what can and what cannot be run in signal handlers are really about reentrancy and async-signal-safety. If, for instance, posix mutexes are not safe in signal handlers they may not be safe in the function that arrange_return_to_lisp_function for to run, because getting out of the signal handler is not enough if ultimately the handler code runs at a random point in time potentially in the middle of a phtread_mutex_lock call. |
From: Nikodemus S. <nik...@ra...> - 2008-08-08 07:20:50
|
On Fri, Aug 8, 2008 at 10:05 AM, Gábor Melis <me...@re...> wrote: > Getting offtpic, here. I came to think that rules about what can and > what cannot be run in signal handlers are really about reentrancy and > async-signal-safety. If, for instance, posix mutexes are not safe in > signal handlers they may not be safe in the function that > arrange_return_to_lisp_function for to run, because getting out of the > signal handler is not enough if ultimately the handler code runs at a > random point in time potentially in the middle of a phtread_mutex_lock > call. Right -- talked about this last year, and you led us to the same conclusion back then. :) http://groups.google.com/group/sbcl-devel/browse_thread/thread/49c5b3b986af8a1d/e5f0f6465d798385?lnk=gst&q=arrange_return_to_lisp_function#e5f0f6465d798385 Cheers, -- Nikodemus |