On Sat, May 23, 2020 at 12:00 AM Robert Haas <robertmhaas(at)gmail(dot)com> wrote: > I think there's a significant difference. The idea I remember being > discussed at the time was to divide the relation into equal parts at > the very start and give one part to each worker. I think that carries > a lot of risk of some workers finishing much sooner than others.
Was the idea of work-stealing considered? Here is what I have been thinking about: Each worker would be assigned a contiguous chunk of blocks at init time. Then if a worker is finished with its work, it can inspect other workers' remaining work and "steal" some of the blocks from the end of the victim worker's allocation. Considerations for such a scheme: 1. Victim selection: Who will be the victim worker? It can be selected at random if nothing else. 2. How many blocks to steal? Stealing half of the victim's remaining blocks seems to be fair. 3. Stealing threshold: We should disallow stealing if the amount of remaining work is not enough in the victim worker. 4. Additional parallel state: Representing the chunk of "work". I guess one variable for the current block and one for the last block in the chunk allocated. The latter would have to be protected with atomic fetches as it would be decremented by the stealing worker. 5. Point 4 implies that there might be more atomic fetch operations as compared to this patch. Idk if that is a lesser evil than the workers being idle..probably not? A way to salvage that a little would be to forego atomic fetches when the amount of work remaining is less than the threshold discussed in 3 as there is no possibility of work stealing then. Regards, Soumyadeep