I'm thinking more and more that this runAfter business should really be a O(1)
thing. If runAfter() is implemented to return true, can not that decision be
made at the time of enqueue? It just looks like so much of this is spread
around to so few actual users in the current API. As I look over the usages,
there is some fuzzy logic involved in some cases where the sequence number is
used for ordering. In a couple of other cases, there is a specific task that
another task wants to run after. In the end, it seems like the API should be
something more like
TaskManager.addAfter( Task myTask, Task dependedOnTask );
and, there would be something like
TaskManager.addWithSequencer( Task myTask, new Sequencer() {
public void runAfter( List<Task> lst, int cnt ) {
// search lst and return result
}
});
So that simple checks can be made for "hasSequencer". The first
case could just result in a call like
TaskManager.addWithSequencer( Task myTask, new Sequencer() {
public void runAfter( List<Task> lst, int cnt ) {
int idx = lst.indexOf( dependedOnTask );
return idx >= 0 && idx < cnt;
}
});
This would remove all of the abiguity and calling into the "return false"
implementations. You could tell at the point of the add(), what sequencing was
going to apply, no searching back into the implementation class.
Gregg Wonderly
Patricia Shanahan wrote:
The best idea I have so far involves maintaining a separate sharable
TreeSet of all except the most recently added tasks. It would be kept
under a single-writer, multiple-reader lock. Tasks that complete or are
removed from the TaskManager would continue to be represented in the
sharable set, but with the TaskWrapper marked appropriately and the Task
reference set to null.
A runAfter scan would begin with the elements added to allTasks since
the last sharable set update, under the TaskManager lock. If that does
not find a hit, the scan would continue against the sharable set using
the read lock, so that several threads could do it in parallel. On hit
in the sharable set, go synchronized, check the status of the task, and
resume the scan if it is completed or removed.
When the number of deviations between the sharable set and allTasks
reaches some limit, get the write lock and update the sharable set by
deleting completed and removed tasks, and adding the tasks that were
added to allTasks since the last update.
It is not very practical with JDK 1.5. It needs the TreeSet subSet
methods, so that I can scan the portion of allTasks that represented
tasks added since the last sharable set update.
An alternative approach is to add methods to let callers know about the
state of the TaskManager, and encourage some form of throttling in the
callers when the number of tasks in the TaskManager exceeds a limit.
Patricia
Peter Firmstone wrote:
I'll think about it some more & see if I can't think of something.
Peter Firmstone wrote:
Patricia Shanahan wrote:
You make some interesting points in your e-mails. I'm just going to
comment on a couple of things tonight, and think more about the rest.
On 7/21/2010 5:25 PM, Peter Firmstone wrote:
Hi Patricia,
Instead of Task passing an Iterable<Task>, it could pass an
Enumerator<Task>, which is inherently immutable. One more comment
inline.
I assume you mean Enumeration<Task>? I prefer Iterable<Task> because
it allows for the enhanced for loop:
Yep.
public Task runAfter(Iterable<Task> candidates){
for(Task t: candidates){
if(this has to wait for t){
return t;
}
}
return null;
}
Given the number of TaskManager callers, I think there is value in
keeping their code as clean and simple as possible.
Ok, didn't think of that, still using the old for loop.
On 7/21/2010 6:25 PM, Peter Firmstone wrote:
....
> I try to keep synchronized blocks as small as possible, not so
much for
> performance, but for bugs, not even necessarily my own bugs but
client
> code concurrency bugs. In the synchronized block, I don't call
objects
> which may be accessible from outside the object I'm calling from.
State
> that needs to be atomically updated, I group together using the same
> lock, I also consider using the ReadWriteLock, if reads will
outnumber
> writes. If multiple objects must be updated atomically, I might group
> them together into an encapsulating object with the methods I need to
> make it atomic. This is better than holding multiple locks.
>
The most important concurrency issue in TaskManager is probably the
runAfter testing. In a TaskManager with n existing tasks, a runAfter
test is O(n). The only other O(n) operation is getPending, which I
think
is much less frequent. Everything else is, or can be, O(1) or O(log n).
I've arranged the order to minimize the number of calls, by finding the
youngest runAfter task first. However, I do not have a good solution to
a task that might need to runAfter, but does not in fact need to
runAfter any of the existing tasks. I just has to scan the whole list.
Moreover, I have to call back to the runAfter method in the caller's
Task object.
I've thought about some ideas, but so far nothing really satisfactory.
That's a tough one, we may have to accept it, you've already got
significantly improved performance over the original implementation.
Peter.
Patricia
