Bulk operations, decomposition functions

[Aleksey Shipilev]

On 07/25/2012 02:04 PM, Doug Lea wrote:
> I'm not sure why the functions in current prototype
> were chosen by Mike et al, but for preliminary versions of
> those for new ConcurrentHashMap and others,
> I've been using
>    targetLeafSize = max(1, N / (p * 8))
> (N is estimated size, p is fjp.parallelism)
> In the normal case of recursive splitting by two,
> the parallel depth is log2 of this.

Aha. The big question I've been asking myself over and over these days
if we should disregard N whatsoever, and instead rely on P only to
decompose. I.e. have the number of tasks to be P*L, where L is load
factor, having L=8..16. Naively, that gives us the depth of
ceil(log2(P*L)).

This looks generic enough, and not relying on (possibly pricey or wrong)
guess about N. Then, the heuristics whether to split further, or cease
to split, can be applied to modify the original decomposition decision
on the fly. Both the estimate for N, and FJT.gQTC()/gSQTC() may help out
here; both heuristics have their drawbacks, so we might downplay their
impact by let them "modify" the original plan, but not change it completely.

> There is a second strategy in place that alomst never
> kicks in so might not be used. The FJ getSurplusQueuedTaskCount
> method can tell a worker if there are too many or two few
> unstolen tasks, so it can adjust. 

Yes, I was vaguely referring to these while saying this task can be
solved by using the feedback from FJP. My several-months-old experiments
[1] show these heuristics work as fast as the good static guess for
threshold when FJP is saturated, and work reasonably well when FJP is
under edge effects like going from idle to full-scale parallelism. No
surprises there.

Keeping in mind that most bulk operations would probably be ad-hoc, that
would probably mean FJP is idle right before the operation starts, which
makes the SQTC/QTC heuristics unreliable to act as the primary drivers
for the decomposition.

-Aleksey.

[1] http://shipilev.net/pub/talks/jeeconf-May2012-forkjoin.pdf;
heuristics slides are #41-45, hopefully graphs there do not require
translation. I should really clean that up before Devoxx.