[M3devel] up-front initialization of mutex/conditionvariable?

Tue Dec 15 06:13:22 CET 2009

 > That thread can then release and acquire as often as it likes, no further CAS, no 

 > pthread_mutex_lock. Acquirers must always CAS to see if the bit is set

How does the thread know it doesn't need to CAS?
With a non-atomic check?

 > polls a thread-local  

Expensive currently.

Can be improved a la gcc __thread, Win32 __declspec(thread), but with limits.

  __declspec(thread) doesn't work pre-Vista with .dlls loaded "after" the .exe.

   You can detect that though and switch between two paths.

    The "reserved" parameter to DllMain tells you if you are loaded in CreateProcess or LoadLibrary, and therefore if __declspec(thread) works pre-Vista or if you need to use TlsAlloc/TlsGetValue.

   You wouldn't want to inline that though, so "poll a thread local" is a function call.

   If there are multiple backward branches in a function, you can optimize by remembering the address of the thread local in a "normal" local, certainly.

   You can also possibly..I haven't thought this through, but I think for each function you can generate two entry points. Call them "internal" and "external". "internal" takes an extra pointer, the pointer to the thread locals. "external" gets the thread locals in an expensive fashion (above) and calls "internal". If a function doesn't actually need the thread locals, the two are aliased to each other.

   Within a module (a single .m3 file), you always call internal, or maybe within a library/dll, or maybe within Modula-3 entirely. But callbacks or direct calls from C go to external. Though callbacks can do better. Even C calls could do better, if you can break the C/Modula-3 ABI.

  I'm not sure this overall scheme works out, but I think it does.

  This is similar to how in some systems exported functions are duplicated.

  The exported version retrieves the base pointer for the .dll's data and then calls the non-exported one. NT/PPC, NT/IA64, I think Mac/CFM/PPC and others work this way. I believe it helps achieve position independence, all static data is accessed via a register that is maintained for all entry and/or exit from a .dll.

 >  calls to <*EXTERNAL*> procedures 

Arguably we can do whatever needed in our .c code.

 You know, since <*external*> is now largely but not completely implemented by us.

  I realize there's still e.g. X/Windows, OpenGL, Win32. Only "libc" is wrapped aggressively right now, and others are large. And maybe that is all that should be, e.g. OpenGL and Xlib are very portable and so maybe cloning their headers is too?

 - Jay

> From: hosking at cs.purdue.edu
> Date: Mon, 14 Dec 2009 23:39:08 -0500
> To: jay.krell at cornell.edu
> CC: m3devel at elegosoft.com
> Subject: Re: [M3devel] up-front initialization of mutex/conditionvariable?
> 
> So, the basic scenario is as follows. Briefly... We should ditch signals as a mechanism for stopping threads. The compiler should inject a "safe-point" at each procedure call and backward branch. At safe-points, the thread polls a thread-local to see if the run-time system needs it to step out-of-line for some reason. At calls to <*EXTERNAL*> procedures we set a thread-local to say the thread is stepping outside Modula-3 code, with corresponding synchronized test on return in case the run-time needs it to pay attention. Now, when a MUTEX is first acquired, we simply CAS in a bit in the MUTEX along with the acquiring thread's ID. That thread can then release and acquire as often as it likes, no further CAS, no pthread_mutex_lock. Acquirers must always CAS to see if the bit is set. If it is then the lock is reserved for some other thread. We must revoke the reservation by handshake (as described above) with the reserving thread. We then inflate a real pthread_mutex_lock along with any queues needed for the MUTEX/CV. The handshake mechanism can also be used for stopping threads for GC, etc.
> 
> The point is that uncontended locks should cost almost nothing.
> 
> On 14 Dec 2009, at 23:04, Jay K wrote:
> 
> > Is it possible to do on Win32?
> > Win32 critical sections are cheap and already probably work roughly "that way".
> > Initialization is cheap. Cheaper than Java's locks. Uncontended locking is cheap.
> > 
> > Our (new) win32 condition variables are not cheap, but similar in cost to Java.
> > (Java has one criticalsection per "monitor", merging the lock and the conditionvariable and sharing the criticalsection, where we have one per lock and one per conditionvariable.)
> > 
> > - Jay
> > 
> > 
> > > Subject: Re: [M3devel] up-front initialization of mutex/conditionvariable?
> > > From: hosking at cs.purdue.edu
> > > Date: Mon, 14 Dec 2009 22:49:48 -0500
> > > CC: m3devel at elegosoft.com
> > > To: jay.krell at cornell.edu
> > > 
> > > We don't want to do that. We will avoid the lock in much more profitable ways. In fact, we want to go the opposite direction and inflate a fat pthread mutex/CV only if we really need to:
> > > 
> > > Bacon, D.F., Konuru, R.B., Murthy, C., Serrano, M.J.: Thin locks: Featherweight synchro- nization for Java. In: Conference on Programming Language Design and Implementation (PLDI). pp. 258–268. Montre ́al, Canada (Jun 1998)
> > > 
> > > Dice, D.: Biased locking in HotSpot, http://blogs.sun.com/dave/entry/biased_locking_in_hotspot
> > > 
> > > Dice, D.: Implementing fast Java monitors with relaxed-locks. In: Java Virtual Machine Research and Technology Symposium (JVM). pp. 79–90. Monterey, Califor! nia (Apr 2001),http://www.usenix.org/publications/library/proceedings/jvm01/dice.html
> > > 
> > > Franke, H., Russell, R.: Fuss, futexes and furwocks: Fast userlevel locking in Linux. In: Ottawa Linux Symposium. pp. 479–495. Ottawa, Canada (Jun 2002), http://www. kernel.org/doc/ols/2002/ols2002-pages-479-495.pdf
> > > 
> > > Kawachiya,K.,Koseki,A.,Onodera,T.:Lockreservation:Javalockscanmostlydowithout atomic operations. In: Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA). pp. 130–141. Seattle, Washington (Nov 2002)
> > > 
> > > Onodera, T., Kawachiya, K.: A study of locking objects with bimodal fields. In: Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA). pp. 223–237. Denver, Colorado (Nov 1999)
> > > 
> > > Onodera,T.,Kawachiya,K.,Koseki,A.:LockreservationforJavareconsidered.In:Odersky, M. (ed.) European Conference on Object Oriented Programming (ECOOP). pp. 559–583. No. 3086! in Lecture Notes in Computer Science, Springer, Oslo, Norway (Jun 200 4)
> > > 
> > > Russell, K., Detlefs, D.: Eliminating synchronization-related atomic operations with biased locking and bulk rebiasing. In: Tarr, P.L., Cook, W.R. (eds.) Conference on Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA). pp. 263–272. Portland, Oregon (Oct 2006)
> > > 
> > > On 14 Dec 2009, at 22:06, Jay K wrote:
> > > 
> > > > Is it possible to initialize mutexes and condition variables right away?
> > > > Instead of having the delayed initialization?
> > > > 
> > > > 
> > > > Mutex initialization is pretty fast on Windows, no syscall.
> > > > Having it be delayed like it is maybe isn't worthwhile.
> > > > 
> > > > 
> > > > As far as I know, the interface is just "NEW(MUTEX)" and the only that can run is, like, "constant field initializers", not calls to any code/"constructors". ?
> > > > 
> > > > 
> > > > I know there is the idiom NEW(T).init() but that is up to call! ers to adhere to.
> > > > Hm. I know Modula-3 was avoiding creating unnecessary language features, but in this case it seems maybe the wrong thing? Too late I guess.
> > > > 
> > > > 
> > > > In the pthread initialization, can we just copy from a statically initialized never used mutex? Or we must call pthread_mutex_init?
> > > > I think we must call pthread_mutex_init, at least if we are to call pthread_mutex_delete.
> > > > 
> > > > 
> > > > - Jay
> > > > 
> > > 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://m3lists.elegosoft.com/pipermail/m3devel/attachments/20091215/c890cd1b/attachment-0002.html>