<div dir="ltr">Hi,<div><br></div><div>I posted a small patch to the GIL which demonstrates the scheduling policy of pthreads conditions.<div><br></div><div>It seems that with pthreads a good policy is to allow (and help) the OS to manage scheduling of threads via the condition queue without introducing scheduling logic.</div>
<div>Some changes include removing the timeout from the new GIL wait, and allowing CPU bound threads to run long enough to let the OS recognize them as such.</div><div>The patch uses ticks countdown-to-switch but it should be changed to a time based countdown (If taking a look at the clock is expensive maybe it can be done once every N ticks during countdown).</div>
<div><br></div><div>Remains to explore what can be done on other platforms.</div><div><br></div><div>Nir</div><div><br></div><div><br><br><div class="gmail_quote">2010/3/16 Nir Aides <span dir="ltr">&lt;<a href="mailto:nir@winpdb.org">nir@winpdb.org</a>&gt;</span><br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"><div dir="ltr"><div class="im"><span style="font-family:arial, sans-serif;font-size:13px;border-collapse:collapse"><div>
Hello Dave, </div><div>
<br></div><div>The following documentation suggests ordering in Linux is not FIFO:</div><a href="http://www.opengroup.org/onlinepubs/000095399/functions/pthread_cond_timedwait.html#tag_03_518_08_06" style="color:rgb(42, 93, 176)" target="_blank">http://www.opengroup.org/onlinepubs/000095399/functions/pthread_cond_timedwait.html#tag_03_518_08_06</a><div>

&quot;<span style="font-family:Verdana, Arial, Helvetica, sans-serif;font-size:13px">Threads waiting on mutexes and condition variables are selected to proceed in an order dependent upon the scheduling policy rather than in some fixed order (for example, FIFO or priority). Thus, the scheduling policy determines which thread(s) are awakened and allowed to proceed.<span style="font-family:arial;font-size:small">&quot;</span></span></div>

<div><br></div><div>Here is the code:</div><div><a href="http://www.google.com/codesearch/p?hl=en#5ge3gHPB4K4/gnu/glibc/glibc-linuxthreads-2.1.1.tar.gz%7CaeB7Uqo7T9g/linuxthreads/queue.h&amp;q=pthread_cond_timedwait&amp;exact_package=http://ftp.gnu.org/gnu/glibc/glibc-linuxthreads-2.1.1.tar.gz" style="color:rgb(42, 93, 176)" target="_blank">http://www.google.com/codesearch/p?hl=en#5ge3gHPB4K4/gnu/glibc/glibc-linuxthreads-2.1.1.tar.gz%7CaeB7Uqo7T9g/linuxthreads/queue.h&amp;q=pthread_cond_timedwait&amp;exact_package=http://ftp.gnu.org/gnu/glibc/glibc-linuxthreads-2.1.1.tar.gz</a></div>

<div><br></div><div>If this is so then it should affect the proposed fixes. </div><div>For example waiting with timeout should be avoided, no?</div><div><br></div><div>Nir</div></span><br></div><div class="gmail_quote"><div class="im">
2010/3/16 David Beazley <span dir="ltr">&lt;<a href="mailto:dave@dabeaz.com" target="_blank">dave@dabeaz.com</a>&gt;</span><br>
</div><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">Python doesn&#39;t use a pthreads mutex for the GIL.    It has always used a binary semaphore implemented with condition variables (or just a pthreads semaphore if available).    The reason the performance is so bad is precisely due to the fact that it is using this implementation and the fact that there *IS* a FIFO queue of threads (associated with the condition variable).   The I/O performance problem with the new GIL is gets much worse with many CPU-bound threads precisely because there is a FIFO queue involved.   This has been covered in my past GIL presentations.<div>
<div></div><div class="h5"><br>

<br>
-Dave<br>
<div><div></div><div><br>
<br>
<br>
On Mar 16, 2010, at 5:52 AM, Kristján Valur Jónsson wrote:<br>
<br>
&gt; How about attacking the original problem, then?<br>
&gt;<br>
&gt; The reason they thrash on pthreads implementation is that a pthreads mutex is assumed to be a short-held resource.  Therefore it will be optimized in the following ways for multicore machines:<br>
&gt; 1) There is a certain amount of spinning done, to try to acquire it before blocking<br>
&gt; 2) It will employ un-fair tactics to avoid lock-convoying, meaning that a thread coming in to acquire the mutex may get in before others that are queued.  This is why &quot;ticking&quot; the GIL works so badly:  The thread that releases the lock is usually the one that reaquires it even though others may be waiting.  See e.g. <a href="http://www.bluebytesoftware.com/blog/PermaLink,guid,e40c2675-43a3-410f-8f85-616ef7b031aa.aspx" target="_blank">http://www.bluebytesoftware.com/blog/PermaLink,guid,e40c2675-43a3-410f-8f85-616ef7b031aa.aspx</a> for a discussion of this (albeit on windows.)<br>


&gt;<br>
&gt; On Windows, this isn&#39;t a problem.  The reason is, that the GIL on windows is implemented using Event objects that don&#39;t cut these corners.  The Event provides you with a strict FIFO queue of objects waiting for the event.<br>


&gt;<br>
&gt; If pthreads doesn&#39;t provide a synchronization primitive similar to that, someone that doesn&#39;t thrash and has a true FIFO queue, it is possible to construct such a thing using condition variables and critical sections.  Perhaps the posix semaphore api is more appropriate in this case.<br>


&gt;<br>
&gt; By the way, this also shows another problem with (old) python.  There is only one core locking primitive, the PyThread_type_lock.  It is being used both as a critical section in the traditional sense, and also as this sort-of-inverse lock that the GIL is.  In the modern world, where the intended behaviour of these is quite different, there is no one-size-fits all.  On windows in particular, the use of the Event object based lock is not ideal for other uses than the GIL.<br>


&gt;<br>
&gt;<br>
&gt; In the new GIL, there appear to be several problems:<br>
&gt; 1) There is no FIFO queue of threads wanting the queue, thus thread scheduling becomes non-deterministic<br>
&gt; 2) The &quot;ticking&quot; of the GIL is now controled by a condition variable timeout.  There appears to be no way to prevent many such timeouts to be in progress at the same time, thus you may have an unnecessarily high rate of ticking going on.<br>


&gt; 3) There isn&#39;t an immediate gil request made when an IO thread requests the gil back, only after an initial timeout.<br>
&gt;<br>
&gt; What we are trying to write here is a thread scheduler, and that is complex business.<br>
&gt; K<br>
&gt;<br>
&gt;<br>
&gt;<br>
&gt;&gt; -----Original Message-----<br>
&gt;&gt; From: python-dev-bounces+kristjan=<a href="http://ccpgames.com" target="_blank">ccpgames.com</a>@<a href="http://python.org" target="_blank">python.org</a><br>
&gt;&gt; [mailto:<a href="mailto:python-dev-bounces%2Bkristjan" target="_blank">python-dev-bounces+kristjan</a>=<a href="http://ccpgames.com" target="_blank">ccpgames.com</a>@<a href="http://python.org" target="_blank">python.org</a>] On Behalf<br>


&gt;&gt; Of David Beazley<br>
&gt;&gt; Sent: 15. mars 2010 03:07<br>
&gt;&gt; To: <a href="mailto:python-dev@python.org" target="_blank">python-dev@python.org</a><br>
&gt;&gt; Subject: Re: [Python-Dev] &quot;Fixing&quot; the new GIL<br>
&gt;&gt;<br>
&gt;&gt; happen to be performing CPU intensive work at the same time, it would<br>
&gt;&gt; be nice if they didn&#39;t thrash on multiple cores (the problem with the<br>
&gt;&gt; old GIL) and if I/O is<br>
&gt;<br>
<br>
_______________________________________________<br>
Python-Dev mailing list<br>
<a href="mailto:Python-Dev@python.org" target="_blank">Python-Dev@python.org</a><br>
<a href="http://mail.python.org/mailman/listinfo/python-dev" target="_blank">http://mail.python.org/mailman/listinfo/python-dev</a><br>
Unsubscribe: <a href="http://mail.python.org/mailman/options/python-dev/nir%40winpdb.org" target="_blank">http://mail.python.org/mailman/options/python-dev/nir%40winpdb.org</a><br>
</div></div></div></div></blockquote></div><br></div>
</blockquote></div><br></div></div></div>