Felipe Lessa wrote:

On Jan 6, 2008 9:30 AM, Andrew Coppin wrote:

...

2. I have a situation where I have a thread generating some data and putting it into a mutable array, and another thread trying to read that data. Is there a way I can make the reader thread block if it tries to read a cell that hasn't been computed yet, but not introduce too much overhead for cells that have been filled in?

If your thread fills the array linearly, you could maintain a variable shared by those threads that say the last cell computed, and have the read thread check that before reading. I think this wouldn't create too much overhead, although it seems like there must be something cleverer somewhere.

That's just it - it fills the array in a fairly random order. (The *scanning* is, however, in linear order.) It's not a big problem - I can wait for the entire array to be filled, and then scan it. But I'd like to do both in parallel if there's a reasonably easy way to do it. I suppose an array of MVars would do it, but 1. How big is an MVar? 2. You have to take the data out of an MVar to read it. In other words, only 1 thread can read an MVar at once [by design]. This isn't truly a problem in the current case, but it's irritating in principle that I can't make it so that once the cell is written, multiple threads can read it simultaneously...

Andrew Coppin wrote:

2. You have to take the data out of an MVar to read it. In other words, only 1 thread can read an MVar at once [by design]. This isn't truly a problem in the current case, but it's irritating in principle that I can't make it so that once the cell is written, multiple threads can read it simultaneously...

This is also known as I-structures i.e. IVar. I think you can simulate them via MVar with the readMVar function? Regards, apfelmus

andrewcoppin:

Spencer Janssen wrote:

...

On Sun, Jan 06, 2008 at 11:30:53AM +0000, Andrew Coppin wrote:

...

Just a couple of things I was wondering about...

1. Is there some way to assign a "priority" to Haskell threads? (The behaviour I'd like is that high priority threads always run first, and low priority threads potentially never run at all unless there's an available processor which is completely idle.)

Not in the current system. It is not clear that thread priorities are so nice anyway (see 'priority inversion' on Wikipedia, for example).

Well, I was thinking more of using them for two things. One is for speculative work (i.e., doing work which we might need later - but don't bother unless there's cores going spare). The other is for working on entirely independent tasks - I don't see how inversion can happen when one thread is solving problem X and another is solving problem Y. But sure, it certainly adds more complexity to have priority levels.

[I can also imagine situations where you might want to assign 80% CPU to one thing, and 20% CPU to the other - but that really does sound hard to implement...]

...

...

2. I have a situation where I have a thread generating some data and putting it into a mutable array, and another thread trying to read that data. Is there a way I can make the reader thread block if it tries to read a cell that hasn't been computed yet, but not introduce too much overhead for cells that have been filled in?

I'd probably use an Array of TMVars, they should be faster than MVars when multiple threads are reading simultaneously.

Mmm, OK. I'll try that. (I wasn't actually aware that STM is working yet...)

It works, and has done so for a couple of years now. It's used in production systems. Where'd you hear otherwise? -- Don

Spencer Janssen wrote:

On Sun, Jan 06, 2008 at 11:30:53AM +0000, Andrew Coppin wrote:

...

1. Is there some way to assign a "priority" to Haskell threads? (The behaviour I'd like is that high priority threads always run first, and low priority threads potentially never run at all unless there's an available processor which is completely idle.)

Not in the current system. It is not clear that thread priorities are so nice anyway (see 'priority inversion' on Wikipedia, for example).

As the wikipedia page also mentions well-known counter-measures, such as priority inheritance and priority ceilings. For real-time applications, priorities are a /must have/. Or at least, I can't see anything nicer that could replace them. Cheers Ben

On Mon, Jan 07, 2008 at 10:59:02AM -0600, Spencer Janssen wrote:

On Sun, Jan 06, 2008 at 11:30:53AM +0000, Andrew Coppin wrote:

...

Just a couple of things I was wondering about...

1. Is there some way to assign a "priority" to Haskell threads? (The behaviour I'd like is that high priority threads always run first, and low priority threads potentially never run at all unless there's an available processor which is completely idle.)

Not in the current system. It is not clear that thread priorities are so nice anyway (see 'priority inversion' on Wikipedia, for example).

I think using STM properly should reduce the risk of priority inversion, as long as you can replace most critical sections with transactions. AFAIU, when there are many transactions sharing some TVars, the transactions that have the biggest chance of being committed are the ones that finish first. It would still be possible for short (cheap computations and few TVar accesses), frequent low-priority transactions to cause frequent rollbacks of a long high-priority transactions, causing a priority inversion. But then, maybe it would be possible to help high-priority to finish - with STM there's much more you can do, like (transparently) rolling back the low-priority transactions. Still, it could be a bit hard to do it properly, without starving low-priority transactions. Best regards Tomasz