I have a clarification below: Simon Peyton-Jones wrote:
| Given that actually controlling priorities is not an option, adding | blocking like that makes sense. One can make a ring buffer instead of a
Concerning priorities and scheduling (which affect both this shootout thread, and perhaps Joel's timeleak program), one can take two approaches
1. Ask more of the runtime system; e.g. add thread priorities 2. Program up a solution
The merit of (1) is that you get an "automatic" solution. The problem is that it might not be the right solution for your problem. Whereas (2) will fit your problem, but is less convenient.
Even the first paper on Concurrent Haskell discussed (2), in Section 4 "Control over scheduling". http://research.microsoft.com/copyright/accept.asp?path=/users/simonpj/p apers/concurrent-haskell.ps.gz
Just to give an example, suppose you have zillions of threads, but you want to ensure that at most 10 of them are running simultaneously else their time slices are too spread out. Just use a quantity semaphore (QSem, discussed in the "Concurrent Haskell" paper). Each thread grabs permission from the semaphore before doing its work, and puts it back when done.
Starvation?
How about fairness? As Simon mentioned, MVars *do* have an undocumented fairness property; waiting threads are serviced in first-come-first-served order. You'd have to check the QSem code, but I believe that means that threads will be dealt with first-come-first-served order for the quantity semaphore. We should probably document this property of MVars, and document fairness guarantees of abstractions such as QSem.
Actually, what Simon Marlow said was:
Furthermore, the thread to be woken up is always the first thread to block on the MVar. That is, there's a kind of fairness built into MVars which isn't present in STM and TMVars.
Which is not FIFO fairness, it sound like "the first that came will be the first to leave; the rest are shuffled". Chorus: this should possibly be documented. The point of the Channel -> Ch optimization was that removing guarantees sometimes improves speed. The only way to get more guarantees without a speed hit could be if the run-time system always imposes them anyway. But since there is value in speed, making module *.MVar and *.MVar.Fair might be interesting (similar for TMVar).
| If 4 threads block trying to take an MVar, and a 5th thread puts a value | in the MVar, then *exactly one* of the 4 blocked threads is woken up and | scheduled to run. | | If 4 threads retry while in STM (e.g. takeTMVar), and a 5th thread | commits a change to that TMVar, then *all 4 threads* are woken up and | rescheduled. This is what the Apache httpd server folks called the | "thundering herd" problem when many processes are blocked waiting on | socket 80.
Yes, that's precisely correct. MVars guarantee a single wake-up, whereas STM does not. Again, this is a property that it'd be good to document.
Well, it is derivable from existing documentation, but it could be made clearer.
Of course none of this helps if you simply have too much work to do. If you have 100 threads, each with 1s of processing to do, then no amount of fancy scheduling will get this done in less than 100s.
Of course
But I thought I'd mention the possibility of doing scheduling explicitly. It's often not hard, and has the property that it's more robust to variations in the implementation.
Simon
Using QSem/QSemN for scheduling will not work well if there is starvation. That really really should be documented: whether or not starvation is possible, regardless of other fairness. Other documentation request: does "newQSem" create it with a quantity of 0 or 1 ? http://www.haskell.org/ghc/docs/latest/html/libraries/base/Control-Concurren... Traditional (non-STM) locking code is very tricky and depends on all these guarantees. If something is not-guaranteed then it should be explicitly documented as "you cannot depend on it". -- Chris