<span style>Hi James,</span><div style><br></div><div style>Those results are certainly counter to my theory, and also counter to what I found. So ...</div><div style><br></div><div style>A little more poking around ... it looks like the call to sleep is being interrupted.</div>
<div style><div><br></div><div><div>(run 1)</div><div>Failed after 822: LATER: 2 (0.004005)</div><div>Failed after 84: LATER: 2 (0.00422)</div><div>Failed after 364: LATER: 2 (0.003999)</div><div>Failed after 77: LATER: 2 (0.003568)</div>
<div>Failed after 21: LATER: 2 (0.003631)</div><div><br></div><div>The number at the end is the seconds (elapsed, using get-internal-real-time) from the creation of the task to when it is popped off at the end. Could it be that sleep is being interrupted and not continuing as it should?</div>
<div><br></div><div>Looking at the ccl code, it does handle interruption from nanosleep, but there is a bit of code in there for OS X Leopard which is suspect. In the case of interruption it compares the values in the remaining time with the initial time. The honest algorithm is to just continue sleeping no matter what the remaining time values are, and it is possible that this workaround for OS X is not reliable (it looks okay, but I'm not sure that comparing the remaining to original is really guaranteed to work.)</div>
<div><br></div><div>In any case, removing that bit of code, recompiling ccl, and so far here is what i have:</div><div><br></div><div><div>(run 0.001)</div><div>Failed after 3944: LATER: 2 (0.008116)</div><div>Failed after 28: LATER: 2 (0.0073)</div>
<div>Failed after 3955: LATER: 2 (0.005493)</div><div>Failed after 301: LATER: 2 (0.010319)</div><div>Failed after 1869: LATER: 2 (0.008788)</div></div><div><br></div><div>This may be the case where the sleep time is small enough to cause both tasks to complete before the main thread gets down to popping the receive stack.</div>
<div><br></div><div>For sleep of 0.01 and 1 sec, after 10 minutes no cases have occurred yet.</div><div><br></div><div>Returning to the computer after dinner -- the 0.01sec sleep test produced the "later before sooner" result after 520K iterations.</div>
<div class="yj6qo ajU" style="outline-style:none;outline-width:initial;outline-color:initial;padding-top:10px;padding-right:0px;padding-bottom:10px;padding-left:0px;width:22px;margin-top:2px;margin-right:0px;margin-bottom:0px;margin-left:0px">
<div id=":g8" class="ajR" tabindex="0" style="background-color:rgb(241,241,241);border-top-width:1px;border-right-width:1px;border-bottom-width:1px;border-left-width:1px;border-top-style:solid;border-right-style:solid;border-bottom-style:solid;border-left-style:solid;border-top-color:rgb(221,221,221);border-right-color:rgb(221,221,221);border-bottom-color:rgb(221,221,221);border-left-color:rgb(221,221,221);clear:both;line-height:6px;outline-style:none;outline-width:initial;outline-color:initial;width:20px">
<img class="ajT" src="https://mail.google.com/mail/u/0/images/cleardot.gif" style="background-image: url(https://ssl.gstatic.com/ui/v1/icons/mail/ellipsis.png); background-attachment: initial; background-origin: initial; background-clip: initial; background-color: initial; height: 8px; opacity: 0.3; width: 20px; background-position: initial initial; background-repeat: no-repeat no-repeat; "></div>
</div><span class="HOEnZb adL"><font color="#888888"><div><br></div><div>Erik.</div></font></span></div></div><br><div class="gmail_quote">On Wed, May 9, 2012 at 6:46 PM, James M. Lawrence <span dir="ltr"><<a href="mailto:llmjjmll@gmail.com" target="_blank">llmjjmll@gmail.com</a>></span> wrote:<br>
<blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex">I appreciate the time you've taken to respond.<br>
<br>
When I wrote "0.5 seconds or whatever", I meant that it fails for<br>
apparently any amount of time. As I mentioned in response to another<br>
reply, a 10 second sleep produces the failure as well. Is that<br>
consonant with your explanation?<br>
<br>
It is also unclear why<br>
<br>
* it does not fail when the loop is removed (along with the push nils)<br>
<br>
* it does not fail when (format t ".") is removed<br>
<br>
Perhaps these are just curiosities due to entropy in the underlying<br>
system calls.<br>
<br>
The upshot of what you're saying is that Clozure cannot reliably<br>
distribute work across threads, while other CL implementations can. I<br>
would not call it a bug, but it's at least unfortunate. In fact<br>
Clozure scales better than SBCL for parallel mapping and other<br>
functions (stats available upon request), barring these peculiar<br>
hiccups.<br>
<div class="HOEnZb"><div class="h5"><br>
<br>
On Wed, May 9, 2012 at 8:44 PM, Gary Byers <<a href="mailto:gb@clozure.com">gb@clozure.com</a>> wrote:<br>
><br>
><br>
> On Wed, 9 May 2012, James M. Lawrence wrote:<br>
><br>
>> I thought my example was straightforward enough, though as I mentioned<br>
>> I wish it were smaller. Following your suggestion, I have replaced the<br>
>> queue with a stack. I have also taken out the condition-wait function<br>
>> copied from bordeaux-threads. My pop function now resembles your<br>
>> consume function.<br>
>><br>
>> The same assertion failure occurs.<br>
>><br>
>> I am unable to reproduce it with high debug settings, or with tracing,<br>
>> or with logging.<br>
><br>
><br>
>><br>
>> The test consists of a pair of worker threads pulling from a task<br>
>> queue. We push two tasks: one task returns immediately, the other task<br>
>> sleeps for 0.2 seconds (it can be 0.5 seconds or whatever, it just<br>
>> takes longer to fail). Since we have two workers, we should always<br>
>> obtain the result of the sleeping task second. A signal is getting<br>
>> missed, or something.<br>
><br>
><br>
> You're assuming that whatever thread pulls the lambda that returns<br>
> 'SOONER will off of TASKS will push 'SOONER onto RECEIVER before<br>
> another thread pulls another lambda that sleeps for .2 seconds before<br>
> returning 'LATER pushes 'LATER on RECEIVER. That assumption is likely<br>
> to hold a high percentage of the time, but I can't think of anything<br>
> that guarantees it. (The OS scheduler may have decided that it should<br>
> let Emacs re-fontify some buffers for a while, or let the kernel<br>
> process all of those network packets that've been gumming up the<br>
> works, and when it gets back to CCL it finds that it's time for the<br>
> sleeping thread to wake up and it gets scheduled and pushes LATER<br>
> on RECEIVER before the other thread even wakes up. This kind of scenario<br>
> isn't as likely as one where 'SOONER is pushed first, but<br>
> it's not wildly improbable, either. It's "likely" that 'SOONER will<br>
> be pushed first - maybe even "highly likely". It's more likely (more<br>
> highly likely ?) if the sleeping thread sleeps longer, but non-realtime<br>
> OSes (like most flavors of Linux, like OSX, like ...) don't make the<br>
> scheduling guarantees that you seem to be assuming.<br>
><br>
> While you're thinking "this thread should run before the other one because<br>
> it's ready to run and the other one is sleeping", the scheduler's thinking<br>
> "that CPU has been really active lately; better shut it down for a little<br>
> while so that it doesn't get too hot or consume too much power", or<br>
> something<br>
> equally obscure and unintuitive. If you change compiler options, or<br>
> do printing or logging (or otherwise change how threads use the CPU cycles<br>
> they're given), your code looks different to the scheduler and behaves<br>
> differently (in subtle and not-always-predictable ways.)<br>
><br>
> Of all the thread-related bugs that've ever existed in CCL, the most<br>
> common cause has probably been "code wasn't prepared to deal with<br>
> concurrency"; a close second is probably "code is making unwarranted<br>
> assumptions about scheduler behavior." After many years of getting beaten<br>
> by those things, I think and hope that I'm more inclined to question some<br>
> assumptions that I used to make automatically and implicitly, and my first<br>
> reaction is to question the assumption that you're making. It's more likely<br>
> that the thread that doesn't sleep will push 'SOONER before the thread that<br>
> sleeps pushes 'LATER, but nothing guarantees this, lots of factors affect<br>
> what happens, and all that I can see is that things that're statistically<br>
> unlikely happen occasionally.<br>
><br>
> Scheduling behavior is likely beyond the grasp of mere mortals; we can have<br>
> a reasonable, largely accurate model of how things will behave, but we have<br>
> to bear in mind that that's all we have.<br>
><br>
> Semaphores in CCL are very thin wrappers around whatever the OS provides<br>
> (POSIX<br>
> semaphores, Mach semaphores, something-or-other on Windows.) If you say "a<br>
> [semaphore] must be getting dropped", you're either saying that there's a<br>
> problem<br>
> in that very thin wrapper or that we're all doomed (because what the OS<br>
> provides<br>
> doesn't work), and you're also saying that your code demonstrates this<br>
> problem<br>
> and no one else's notices. Some or all of those things could be true, but<br>
> you're<br>
> claiming that they must be because you think that you know which thread will<br>
> run before which other thread. You don't know that; all you really know is<br>
> that's<br>
> probably true.<br>
><br>
><br>
> (defun test ()<br>
>><br>
>> (let ((tasks (make-stack)))<br>
>> (loop<br>
>> :repeat 2<br>
>> :do (ccl:process-run-function<br>
>> "test"<br>
>> (lambda ()<br>
>> (loop (funcall (or (pop-stack tasks)<br>
>> (return)))))))<br>
>> (let ((receiver (make-stack)))<br>
>> (push-stack (lambda ()<br>
>> (push-stack (progn (sleep 0.2) 'later)<br>
>> receiver))<br>
>> tasks)<br>
>> (push-stack (lambda ()<br>
>> (push-stack 'sooner receiver))<br>
>> tasks)<br>
>> (let ((result (pop-stack receiver)))<br>
>> (assert (eq 'sooner result)))<br>
>> (let ((result (pop-stack receiver)))<br>
>> (assert (eq 'later result))))<br>
>> (push-stack nil tasks)<br>
>> (push-stack nil tasks))<br>
>> (format t "."))<br>
>><br>
>> (defun run ()<br>
>> (loop (test)))<br>
>> _______________________________________________<br>
>> Openmcl-devel mailing list<br>
>> <a href="mailto:Openmcl-devel@clozure.com">Openmcl-devel@clozure.com</a><br>
>> <a href="http://clozure.com/mailman/listinfo/openmcl-devel" target="_blank">http://clozure.com/mailman/listinfo/openmcl-devel</a><br>
>><br>
>><br>
><br>
_______________________________________________<br>
Openmcl-devel mailing list<br>
<a href="mailto:Openmcl-devel@clozure.com">Openmcl-devel@clozure.com</a><br>
<a href="http://clozure.com/mailman/listinfo/openmcl-devel" target="_blank">http://clozure.com/mailman/listinfo/openmcl-devel</a><br>
</div></div></blockquote></div><br>