The idea is to return the result immediately after the root algorithm returns without waiting for any workers to complete. We need to take care that we don't make everyone pay for concurrency when it's not in play. Perhaps a single maybeBusy bool flag, which if false, triggers a wait on a condition variable (that is do the first flag test outside the condvar). Because sets are immutable, this is guaranteed to flip to true exactly once and never flip back, so it will be safe under concurrent usage.
The worst case would be that goroutines on multiple cores wait needlessly because the true-flag hasn't propagated to their caches. This only happens once per core, however, so I suspect the impact will be somewhere between negligible and unmeasurable.
MVP would be to block once at the root for each call. Is it possible to make it even more concurrent by instead blocking only on nodes that are pending worker output? Currently, each child reference that is attached to a worker has the global promiseNode assigned to it. Testing for this might achieve the same benefit as described above, but possibly allow some operations to complete without having to wait for all the work to finish:
Any() and AnyN() could scour for elements above the waterline first then descend below it only if necessary.IsSubsetOf() could do likewise- Most operations could look for subtrees whose workers have finished their business and descend into them first before waiting for the others.
- Perhaps a channel could stream ready nodes as they become available to avoid busy-looping to check who's finished.
A more general strategy might be for operations to output trees with a promiseNode at any point where one or both of the corresponding input nodes has a promiseNode and have the worker for the output node wait on the corresponding input node(s).
A further development that might (or might not) simplify a lot of this could be for promise nodes to actually carry promises rather than just signal them.
The idea is to return the result immediately after the root algorithm returns without waiting for any workers to complete. We need to take care that we don't make everyone pay for concurrency when it's not in play. Perhaps a single
maybeBusy boolflag, which if false, triggers a wait on a condition variable (that is do the first flag test outside the condvar). Because sets are immutable, this is guaranteed to flip to true exactly once and never flip back, so it will be safe under concurrent usage.The worst case would be that goroutines on multiple cores wait needlessly because the true-flag hasn't propagated to their caches. This only happens once per core, however, so I suspect the impact will be somewhere between negligible and unmeasurable.
MVP would be to block once at the root for each call. Is it possible to make it even more concurrent by instead blocking only on nodes that are pending worker output? Currently, each child reference that is attached to a worker has the global
promiseNodeassigned to it. Testing for this might achieve the same benefit as described above, but possibly allow some operations to complete without having to wait for all the work to finish:Any()andAnyN()could scour for elements above the waterline first then descend below it only if necessary.IsSubsetOf()could do likewiseA more general strategy might be for operations to output trees with a
promiseNodeat any point where one or both of the corresponding input nodes has apromiseNodeand have the worker for the output node wait on the corresponding input node(s).A further development that might (or might not) simplify a lot of this could be for promise nodes to actually carry promises rather than just signal them.