<html><head><base href="x-msg://758/"></head><body style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; ">Guys,<div><br></div><div>You are looking in the wrong place. The whole good thing about having a language-defined thread model is that we get to implement the thread primitives in the language run-time, and we can take advantage of language-specific semantics. There is no requirement that a Modula-3 mutex even map to a pthread_mutex_t. Java monitors are implemented in modern JVMs so that lock/unlock in the common case doesn't require any calls or any atomic operations! We can do much the same for Modula-3. My group at Purdue has done a fair amount of work on this in the context of Java, and when I can find the time I was hoping to do the same for Modula-3. The only requirement for M3 was that we have proper support for atomic ops in the language upon which to build the synchronisation primitives. We are close to having this now. Let me sketch a design:</div><div><br></div><div>The common case is that a mutex is only ever manipulated by one thread (i.e., never shared), in which case it suffices to "bias" the mutex to that thread. Locking/unlocking is simply a matter of checking to see that the bias belongs to the current thread. No need for an atomic operation. If the thread already has the bias then locking/unlocking is simply a matter of setting a bit in the mutex. If another thread comes along and needs to lock the mutex then it must first revoke the bias of the owning thread. This can be expensive (assuming it occurs infrequently) and in our case probably means stopping the thread having the bias, revoking the bias, then restarting it.</div><div><br></div><div>Another case is when a mutex is locked/unlocked by multiple threads but there is never contention (i.e., no thread tries to acquire while another thread holds). In this case we never need a wait queue for the mutex so we can simply store the lock owner in the mutex and test using atomic ops. Spinning is often useful here to avoid needing to inflate if contention ever does arise: if the thread holding the lock gets out of the mutex quickly then the spinner can move in quickly. After some number of spins we generally need to inflate the lock to allocate a wait queue (to avoiding hogging the processor).</div><div><br></div><div>Finally, the case where many threads are contending on the inflated lock (with wait queue). The only question now is when to deflate. Our current heuristic is to deflate when the last thread releases the lock and notices that there are no other threads waiting. This seems to work well in practice, but of course there are pathological cases.</div><div><br></div><div>Note that in no case have I mentioned the need for a pthread_mutex (though pthread locks/conditions are used to manage threads that must block on a Java quit queue).</div><div><br></div><div>We ought to be able to do much the same in Modula-3.</div><div><br><div>
<span class="Apple-style-span" style="border-collapse: separate; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-align: auto; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><div style="word-wrap: break-word; -webkit-nbsp-mode: space; -webkit-line-break: after-white-space; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><span class="Apple-style-span" style="border-collapse: separate; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; color: rgb(0, 0, 0); font-family: Helvetica; font-size: 12px; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; -webkit-text-decorations-in-effect: none; text-indent: 0px; -webkit-text-size-adjust: auto; text-transform: none; orphans: 2; white-space: normal; widows: 2; word-spacing: 0px; "><div><font class="Apple-style-span" color="#0000FF"><font class="Apple-style-span" face="Gill Sans"><span class="Apple-style-span" style="color: rgb(0, 0, 255); font-family: 'Gill Sans'; "><span class="Apple-style-span" style="color: rgb(0, 0, 255); font-family: 'Gill Sans'; ">Antony Hosking</span></span></font></font><font class="Apple-style-span" face="Gill Sans"><span class="Apple-style-span" style="font-family: 'Gill Sans'; "><span class="Apple-style-span" style="font-family: 'Gill Sans'; "><span class="Apple-converted-space"> </span>|<span class="Apple-converted-space"> </span></span></span><span class="Apple-style-span" style="font-family: 'Gill Sans'; "><span class="Apple-style-span" style="font-family: 'Gill Sans'; ">Associate Professor</span></span><span class="Apple-style-span" style="font-family: 'Gill Sans'; "><span class="Apple-style-span" style="font-family: 'Gill Sans'; "> | Computer Science | Purdue University</span></span></font></div><div><font class="Apple-style-span" face="GillSans-Light"><span class="Apple-style-span" style="font-family: GillSans-Light; ">305 N. University Street | West Lafayette | IN 47907 | USA</span></font></div><div><font class="Apple-style-span" color="#0000FF" face="Gill Sans"><span class="Apple-style-span" style="color: rgb(0, 0, 255); font-family: 'Gill Sans'; "><span class="Apple-style-span" style="color: rgb(0, 0, 255); font-family: 'Gill Sans'; ">Office</span></span></font><font class="Apple-style-span" face="GillSans-Light"><span class="Apple-style-span" style="font-family: GillSans-Light; "><span class="Apple-style-span" style="font-family: GillSans-Light; "> +1 765 494 6001 |<span class="Apple-converted-space"> </span></span></span></font><font class="Apple-style-span" color="#0000FF" face="Gill Sans"><span class="Apple-style-span" style="color: rgb(0, 0, 255); font-family: 'Gill Sans'; "><span class="Apple-style-span" style="color: rgb(0, 0, 255); font-family: 'Gill Sans'; ">Mobile</span></span></font><font class="Apple-style-span" face="GillSans-Light"><span class="Apple-style-span" style="font-family: GillSans-Light; "><span class="Apple-style-span" style="font-family: GillSans-Light; "><span class="Apple-converted-space"> </span>+1 765 427 5484</span></span></font></div><div><font class="Apple-style-span" face="GillSans-Light"><br class="khtml-block-placeholder"></font></div></span></span></span></span></span></span></span><br class="Apple-interchange-newline"></span></div></span></span><br class="Apple-interchange-newline">
</div>
<br><div><div>On 29 Mar 2010, at 04:24, Jay K wrote:</div><br class="Apple-interchange-newline"><blockquote type="cite"><span class="Apple-style-span" style="border-collapse: separate; font-family: Helvetica; font-size: medium; font-style: normal; font-variant: normal; font-weight: normal; letter-spacing: normal; line-height: normal; orphans: 2; text-indent: 0px; text-transform: none; white-space: normal; widows: 2; word-spacing: 0px; -webkit-border-horizontal-spacing: 0px; -webkit-border-vertical-spacing: 0px; -webkit-text-decorations-in-effect: none; -webkit-text-size-adjust: auto; -webkit-text-stroke-width: 0px; "><div class="hmmessage" style="font-size: 10pt; font-family: Verdana; "> > We can optimize this somewhat on most systems with __thread. I had that in briefly<br> <br> <br>I did a little bit of testing here.<br> <br> <br>__thread takes a few forms, depending on which of -fPIC and -shared you use.<br> <br>Once you do throw in -fPIC and -shared, I have found __thread to be significantly slower on Solaris/sparc and Linux/powerpc32, slower or a wash on Linux/amd64, and twice as fast as pthread_getspecific on Linux/x86.<br>I doesn't appear supported at all on Darwin, though pthread_getspecific are very fast there (albeit not inlined).<br>I didn't test *BSD.<br>My testing was not very scientific.<br>However -fPIC and/or -shared imply a function call to access __thread variables.<br> That's probably the big factor. Without -fPIC/-shared, there is no function call.<br> <br> <br>If you are going to access them multiple times in a function then there is a probably an optimization to be had -- caching their address. If the variables are larger than a pointer, probably then also an optimization to be had.<br> <br> <br>We could do that first thing for certain -- PushFrame could return the address and PopFrame would be much faster.<br>However another angle here is to eliminate PushFrame/PopFrame, by using libunwind. I think we should look into libunwind for the next release. The thread locals will (mostly) remain but accesses to them greatly decline.<br> <br> <br>We compile everything -fPIC and -shared.<br>Some systems (libtool) compile things once that way and once not, providing pairs of libraries, depending on intended use.<br> <br> <br>I should point out also that userthreads have been greatly deoptimized in the current tree (by me, Tony approved), because they used to inline PushFrame/PopFrame, but they don't any longer.<br> <br> <br>(Historically on NT, __declspec(thread) only worked in code in the .exe or statically loaded by the .exe -- that is, not in .dlls loaded with LoadLibrary. However that limitation was removed in Vista. I expect __declspec(thread) is much faster than TlsGetValue, but I assume we'll support pre-Vista for a while longer so not interesting..)<br> <br> <br> - Jay<br><br> <br><hr id="stopSpelling">From:<span class="Apple-converted-space"> </span><a href="mailto:jay.krell@cornell.edu">jay.krell@cornell.edu</a><br>To:<span class="Apple-converted-space"> </span><a href="mailto:dragisha@m3w.org">dragisha@m3w.org</a>;<span class="Apple-converted-space"> </span><a href="mailto:mika@async.async.caltech.edu">mika@async.async.caltech.edu</a><br>CC:<span class="Apple-converted-space"> </span><a href="mailto:m3devel@elegosoft.com">m3devel@elegosoft.com</a><br>Subject: RE: [M3devel] userthreads vs. pthreads performance?<br>Date: Mon, 29 Mar 2010 03:15:41 +0000<br><br> > Getting thread locals should not require a kernel call<br> <br>Indeed, on Linux/x86 it does not, looks pretty ok:<br> <br>00000380 <__pthread_getspecific>:<br> 380: 55 push %ebp<br> 381: 89 e5 mov %esp,%ebp<br> 383: 8b 55 08 mov 0x8(%ebp),%edx<br> 386: 81 fa ff 03 00 00 cmp $0x3ff,%edx<br> 38c: 76 04 jbe 392 <__pthread_getspecific+0x12><br> 38e: 5d pop %ebp<br> 38f: 31 c0 xor %eax,%eax<br> 391: c3 ret<br><br> 392: 89 d0 mov %edx,%eax<br> 394: c1 e8 05 shr $0x5,%eax<br> 397: 8d 0c 85 1c 01 00 00 lea 0x11c(,%eax,4),%ecx<br> 39e: 65 8b 01 mov %gs:(%ecx),%eax<br> 3a1: 85 c0 test %eax,%eax<br> 3a3: 74 e9 je 38e <__pthread_getspecific+0xe><br> 3a5: 8b 04 d5 00 00 00 00 mov 0x0(,%edx,8),%eax<br> 3ac: 85 c0 test %eax,%eax<br> 3ae: 74 de je 38e <__pthread_getspecific+0xe><br> 3b0: 65 8b 01 mov %gs:(%ecx),%eax<br> 3b3: 83 e2 1f and $0x1f,%edx<br> 3b6: 8b 04 90 mov (%eax,%edx,4),%eax<br> 3b9: 5d pop %ebp<br> 3ba: c3 ret<br><br><br>> Entering an uncontended pthread mutex should not be expensive<br><br>Linux/x86:<br> <br>00001020 <__pthread_self>:<br> 1020: 55 push %ebp<br> 1021: 89 e5 mov %esp,%ebp<br> 1023: 65 a1 50 00 00 00 mov %gs:0x50,%eax<br> 1029: 5d pop %ebp<br> 102a: c3 ret<br> 102b: 90 nop<br> 102c: 8d 74 26 00 lea 0x0(%esi),%esi<br> <br> <br>pretty lame, five instructions were only two are needed.<br> <br><br>000004f0 <__pthread_mutex_lock>:<br><br>.. too much to read through..but I think no kernel call..<br> <br> - Jay<br> <br><hr id="ecxstopSpelling">From:<span class="Apple-converted-space"> </span><a href="mailto:jay.krell@cornell.edu">jay.krell@cornell.edu</a><br>To:<span class="Apple-converted-space"> </span><a href="mailto:dragisha@m3w.org">dragisha@m3w.org</a>;<span class="Apple-converted-space"> </span><a href="mailto:mika@async.async.caltech.edu">mika@async.async.caltech.edu</a><br>CC:<span class="Apple-converted-space"> </span><a href="mailto:m3devel@elegosoft.com">m3devel@elegosoft.com</a><br>Subject: RE: [M3devel] userthreads vs. pthreads performance?<br>Date: Sun, 28 Mar 2010 20:46:01 +0000<br><br>O(1) scheduling is not a new idea. Just look at NT and probably Solaris and probably all the other non-free systems (AIX, Irix, HP-UX, Tru64, VMS, etc.)<br><br>Getting thread locals should not require a kernel call. It doesn't on NT. We can optimize this somewhat on most systems with __thread. I had that in briefly.<br><br>Entering an uncontended pthread mutex should not be expensive -- at least no kernel call, but granted a call and atomic op. Two calls because of the C layer.<br>But user threads pay for a call too of course.<br><br>Maybe I should profile some of this..<br><br>- Jay<br><br>> From:<span class="Apple-converted-space"> </span><a href="mailto:dragisha@m3w.org">dragisha@m3w.org</a><br>> To:<span class="Apple-converted-space"> </span><a href="mailto:mika@async.async.caltech.edu">mika@async.async.caltech.edu</a><br>> Date: Sun, 28 Mar 2010 21:14:57 +0200<br>> CC:<span class="Apple-converted-space"> </span><a href="mailto:m3devel@elegosoft.com">m3devel@elegosoft.com</a><br>> Subject: Re: [M3devel] userthreads vs. pthreads performance?<br>><span class="Apple-converted-space"> </span><br>> I remember reading (long time ago) about how these (FUTEXes) are<br>> efficient in LINUX... Can I have your test code to try?<br>><span class="Apple-converted-space"> </span><br>> On Sun, 2010-03-28 at 12:11 -0700, Mika Nystrom wrote:<br>> > Well I have run programs on PPC_DARWIN and FreeBSD<X> and seen these sorts of things...<br>> ><span class="Apple-converted-space"> </span><br>> > =?UTF-8?Q?Dragi=C5=A1a_Duri=C4=87?= writes:<br>> > >Which platform?<br>> > ><br>> > >On Sun, 2010-03-28 at 11:57 -0700, Mika Nystrom wrote:<br>> > >> Yep, sounds right.<span class="Apple-converted-space"> </span><br>> > >><span class="Apple-converted-space"> </span><br>> > >> I was profiling some other thread-using code that slowed down<br>> > >> enormously<br>> > >> because of pthreads and it turned out the program was spending ~95%<br>> > >> of its time in accessing the thread locals via one of the pthread_<br>> > >> functions.<br>> > >> (The overhead of entering the kernel.)<br>> > >--<span class="Apple-converted-space"> </span><br>> > >Dragiša Durić <<a href="mailto:dragisha@m3w.org">dragisha@m3w.org</a>><br>> --<span class="Apple-converted-space"> </span><br>> Dragiša Durić <<a href="mailto:dragisha@m3w.org">dragisha@m3w.org</a>><br>><span class="Apple-converted-space"> </span><br></div></span></blockquote></div><br></div></body></html>