<repo_name>lewischen1123/Work_Stealing_Java<file_sep>/WorkingStealing/src/house/House.java
package house;//####[1]####
//####[1]####
import java.awt.Color;//####[3]####
import java.awt.Dimension;//####[4]####
import java.awt.Font;//####[5]####
import java.awt.Graphics;//####[6]####
import java.util.ArrayList;//####[7]####
import java.util.Collection;//####[8]####
import java.util.Collections;//####[9]####
import java.util.Iterator;//####[10]####
import java.util.List;//####[11]####
import java.util.concurrent.ConcurrentLinkedQueue;//####[12]####
import java.util.concurrent.CopyOnWriteArrayList;//####[13]####
import javax.swing.JApplet;//####[15]####
import javax.swing.SwingUtilities;//####[16]####
//####[16]####
//-- ParaTask related imports//####[16]####
import pt.runtime.*;//####[16]####
import java.util.concurrent.ExecutionException;//####[16]####
import java.util.concurrent.locks.*;//####[16]####
import java.lang.reflect.*;//####[16]####
import pt.runtime.GuiThread;//####[16]####
import java.util.concurrent.BlockingQueue;//####[16]####
import java.util.ArrayList;//####[16]####
import java.util.List;//####[16]####
//####[16]####
public class House extends JApplet {//####[18]####
    static{ParaTask.init();}//####[18]####
    /*  ParaTask helper method to access private/protected slots *///####[18]####
    public void __pt__accessPrivateSlot(Method m, Object instance, TaskID arg, Object interResult ) throws IllegalArgumentException, IllegalAccessException, InvocationTargetException {//####[18]####
        if (m.getParameterTypes().length == 0)//####[18]####
            m.invoke(instance);//####[18]####
        else if ((m.getParameterTypes().length == 1))//####[18]####
            m.invoke(instance, arg);//####[18]####
        else //####[18]####
            m.invoke(instance, arg, interResult);//####[18]####
    }//####[18]####
//####[20]####
    private Build builder;//####[20]####
//####[22]####
    private int width = 500;//####[22]####
//####[23]####
    private int height = 320;//####[23]####
//####[25]####
    private int N = 20;//####[25]####
//####[26]####
    private boolean clearScreen = true;//####[26]####
//####[28]####
    private CopyOnWriteArrayList<BuildingMaterial> foundation = null;//####[28]####
//####[29]####
    private CopyOnWriteArrayList<BuildingMaterial> wallSiding = null;//####[29]####
//####[30]####
    private CopyOnWriteArrayList<BuildingMaterial> roofTiles = null;//####[30]####
//####[31]####
    private CopyOnWriteArrayList<BuildingMaterial> windows = null;//####[31]####
//####[33]####
    private BuildingMaterial door = null;//####[33]####
//####[34]####
    private BuildingMaterial forSaleSign = null;//####[34]####
//####[36]####
    private Color colorRoof;//####[36]####
//####[37]####
    private Color colorWalls;//####[37]####
//####[39]####
    public House(Build builder) {//####[39]####
        this.builder = builder;//####[40]####
        setPreferredSize(new Dimension(width, height));//####[41]####
        initialiseMaterial();//####[42]####
    }//####[43]####
//####[46]####
    private static volatile Method __pt__buildSingleTask_Color_Color_method = null;//####[46]####
    private synchronized static void __pt__buildSingleTask_Color_Color_ensureMethodVarSet() {//####[46]####
        if (__pt__buildSingleTask_Color_Color_method == null) {//####[46]####
            try {//####[46]####
                __pt__buildSingleTask_Color_Color_method = ParaTaskHelper.getDeclaredMethod(new ParaTaskHelper.ClassGetter().getCurrentClass(), "__pt__buildSingleTask", new Class[] {//####[46]####
                    Color.class, Color.class//####[46]####
                });//####[46]####
            } catch (Exception e) {//####[46]####
                e.printStackTrace();//####[46]####
            }//####[46]####
        }//####[46]####
    }//####[46]####
    public TaskID<Void> buildSingleTask(Color colorWalls, Color colorRoof) {//####[46]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[46]####
        return buildSingleTask(colorWalls, colorRoof, new TaskInfo());//####[46]####
    }//####[46]####
    public TaskID<Void> buildSingleTask(Color colorWalls, Color colorRoof, TaskInfo taskinfo) {//####[46]####
        // ensure Method variable is set//####[46]####
        if (__pt__buildSingleTask_Color_Color_method == null) {//####[46]####
            __pt__buildSingleTask_Color_Color_ensureMethodVarSet();//####[46]####
        }//####[46]####
        taskinfo.setParameters(colorWalls, colorRoof);//####[46]####
        taskinfo.setMethod(__pt__buildSingleTask_Color_Color_method);//####[46]####
        taskinfo.setInstance(this);//####[46]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[46]####
    }//####[46]####
    public TaskID<Void> buildSingleTask(TaskID<Color> colorWalls, Color colorRoof) {//####[46]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[46]####
        return buildSingleTask(colorWalls, colorRoof, new TaskInfo());//####[46]####
    }//####[46]####
    public TaskID<Void> buildSingleTask(TaskID<Color> colorWalls, Color colorRoof, TaskInfo taskinfo) {//####[46]####
        // ensure Method variable is set//####[46]####
        if (__pt__buildSingleTask_Color_Color_method == null) {//####[46]####
            __pt__buildSingleTask_Color_Color_ensureMethodVarSet();//####[46]####
        }//####[46]####
        taskinfo.setTaskIdArgIndexes(0);//####[46]####
        taskinfo.addDependsOn(colorWalls);//####[46]####
        taskinfo.setParameters(colorWalls, colorRoof);//####[46]####
        taskinfo.setMethod(__pt__buildSingleTask_Color_Color_method);//####[46]####
        taskinfo.setInstance(this);//####[46]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[46]####
    }//####[46]####
    public TaskID<Void> buildSingleTask(BlockingQueue<Color> colorWalls, Color colorRoof) {//####[46]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[46]####
        return buildSingleTask(colorWalls, colorRoof, new TaskInfo());//####[46]####
    }//####[46]####
    public TaskID<Void> buildSingleTask(BlockingQueue<Color> colorWalls, Color colorRoof, TaskInfo taskinfo) {//####[46]####
        // ensure Method variable is set//####[46]####
        if (__pt__buildSingleTask_Color_Color_method == null) {//####[46]####
            __pt__buildSingleTask_Color_Color_ensureMethodVarSet();//####[46]####
        }//####[46]####
        taskinfo.setQueueArgIndexes(0);//####[46]####
        taskinfo.setIsPipeline(true);//####[46]####
        taskinfo.setParameters(colorWalls, colorRoof);//####[46]####
        taskinfo.setMethod(__pt__buildSingleTask_Color_Color_method);//####[46]####
        taskinfo.setInstance(this);//####[46]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[46]####
    }//####[46]####
    public TaskID<Void> buildSingleTask(Color colorWalls, TaskID<Color> colorRoof) {//####[46]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[46]####
        return buildSingleTask(colorWalls, colorRoof, new TaskInfo());//####[46]####
    }//####[46]####
    public TaskID<Void> buildSingleTask(Color colorWalls, TaskID<Color> colorRoof, TaskInfo taskinfo) {//####[46]####
        // ensure Method variable is set//####[46]####
        if (__pt__buildSingleTask_Color_Color_method == null) {//####[46]####
            __pt__buildSingleTask_Color_Color_ensureMethodVarSet();//####[46]####
        }//####[46]####
        taskinfo.setTaskIdArgIndexes(1);//####[46]####
        taskinfo.addDependsOn(colorRoof);//####[46]####
        taskinfo.setParameters(colorWalls, colorRoof);//####[46]####
        taskinfo.setMethod(__pt__buildSingleTask_Color_Color_method);//####[46]####
        taskinfo.setInstance(this);//####[46]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[46]####
    }//####[46]####
    public TaskID<Void> buildSingleTask(TaskID<Color> colorWalls, TaskID<Color> colorRoof) {//####[46]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[46]####
        return buildSingleTask(colorWalls, colorRoof, new TaskInfo());//####[46]####
    }//####[46]####
    public TaskID<Void> buildSingleTask(TaskID<Color> colorWalls, TaskID<Color> colorRoof, TaskInfo taskinfo) {//####[46]####
        // ensure Method variable is set//####[46]####
        if (__pt__buildSingleTask_Color_Color_method == null) {//####[46]####
            __pt__buildSingleTask_Color_Color_ensureMethodVarSet();//####[46]####
        }//####[46]####
        taskinfo.setTaskIdArgIndexes(0, 1);//####[46]####
        taskinfo.addDependsOn(colorWalls);//####[46]####
        taskinfo.addDependsOn(colorRoof);//####[46]####
        taskinfo.setParameters(colorWalls, colorRoof);//####[46]####
        taskinfo.setMethod(__pt__buildSingleTask_Color_Color_method);//####[46]####
        taskinfo.setInstance(this);//####[46]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[46]####
    }//####[46]####
    public TaskID<Void> buildSingleTask(BlockingQueue<Color> colorWalls, TaskID<Color> colorRoof) {//####[46]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[46]####
        return buildSingleTask(colorWalls, colorRoof, new TaskInfo());//####[46]####
    }//####[46]####
    public TaskID<Void> buildSingleTask(BlockingQueue<Color> colorWalls, TaskID<Color> colorRoof, TaskInfo taskinfo) {//####[46]####
        // ensure Method variable is set//####[46]####
        if (__pt__buildSingleTask_Color_Color_method == null) {//####[46]####
            __pt__buildSingleTask_Color_Color_ensureMethodVarSet();//####[46]####
        }//####[46]####
        taskinfo.setQueueArgIndexes(0);//####[46]####
        taskinfo.setIsPipeline(true);//####[46]####
        taskinfo.setTaskIdArgIndexes(1);//####[46]####
        taskinfo.addDependsOn(colorRoof);//####[46]####
        taskinfo.setParameters(colorWalls, colorRoof);//####[46]####
        taskinfo.setMethod(__pt__buildSingleTask_Color_Color_method);//####[46]####
        taskinfo.setInstance(this);//####[46]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[46]####
    }//####[46]####
    public TaskID<Void> buildSingleTask(Color colorWalls, BlockingQueue<Color> colorRoof) {//####[46]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[46]####
        return buildSingleTask(colorWalls, colorRoof, new TaskInfo());//####[46]####
    }//####[46]####
    public TaskID<Void> buildSingleTask(Color colorWalls, BlockingQueue<Color> colorRoof, TaskInfo taskinfo) {//####[46]####
        // ensure Method variable is set//####[46]####
        if (__pt__buildSingleTask_Color_Color_method == null) {//####[46]####
            __pt__buildSingleTask_Color_Color_ensureMethodVarSet();//####[46]####
        }//####[46]####
        taskinfo.setQueueArgIndexes(1);//####[46]####
        taskinfo.setIsPipeline(true);//####[46]####
        taskinfo.setParameters(colorWalls, colorRoof);//####[46]####
        taskinfo.setMethod(__pt__buildSingleTask_Color_Color_method);//####[46]####
        taskinfo.setInstance(this);//####[46]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[46]####
    }//####[46]####
    public TaskID<Void> buildSingleTask(TaskID<Color> colorWalls, BlockingQueue<Color> colorRoof) {//####[46]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[46]####
        return buildSingleTask(colorWalls, colorRoof, new TaskInfo());//####[46]####
    }//####[46]####
    public TaskID<Void> buildSingleTask(TaskID<Color> colorWalls, BlockingQueue<Color> colorRoof, TaskInfo taskinfo) {//####[46]####
        // ensure Method variable is set//####[46]####
        if (__pt__buildSingleTask_Color_Color_method == null) {//####[46]####
            __pt__buildSingleTask_Color_Color_ensureMethodVarSet();//####[46]####
        }//####[46]####
        taskinfo.setQueueArgIndexes(1);//####[46]####
        taskinfo.setIsPipeline(true);//####[46]####
        taskinfo.setTaskIdArgIndexes(0);//####[46]####
        taskinfo.addDependsOn(colorWalls);//####[46]####
        taskinfo.setParameters(colorWalls, colorRoof);//####[46]####
        taskinfo.setMethod(__pt__buildSingleTask_Color_Color_method);//####[46]####
        taskinfo.setInstance(this);//####[46]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[46]####
    }//####[46]####
    public TaskID<Void> buildSingleTask(BlockingQueue<Color> colorWalls, BlockingQueue<Color> colorRoof) {//####[46]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[46]####
        return buildSingleTask(colorWalls, colorRoof, new TaskInfo());//####[46]####
    }//####[46]####
    public TaskID<Void> buildSingleTask(BlockingQueue<Color> colorWalls, BlockingQueue<Color> colorRoof, TaskInfo taskinfo) {//####[46]####
        // ensure Method variable is set//####[46]####
        if (__pt__buildSingleTask_Color_Color_method == null) {//####[46]####
            __pt__buildSingleTask_Color_Color_ensureMethodVarSet();//####[46]####
        }//####[46]####
        taskinfo.setQueueArgIndexes(0, 1);//####[46]####
        taskinfo.setIsPipeline(true);//####[46]####
        taskinfo.setParameters(colorWalls, colorRoof);//####[46]####
        taskinfo.setMethod(__pt__buildSingleTask_Color_Color_method);//####[46]####
        taskinfo.setInstance(this);//####[46]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[46]####
    }//####[46]####
    public void __pt__buildSingleTask(Color colorWalls, Color colorRoof) {//####[46]####
        build(colorWalls, colorRoof);//####[47]####
    }//####[48]####
//####[48]####
//####[51]####
    public void build(Color colorWalls, Color colorRoof) {//####[51]####
        this.colorWalls = colorWalls;//####[52]####
        this.colorRoof = colorRoof;//####[53]####
        initialiseMaterial();//####[54]####
        buildAll(foundation);//####[56]####
        buildAll(wallSiding);//####[57]####
        buildAll(roofTiles);//####[58]####
        buildItem(door);//####[59]####
        buildAll(windows);//####[60]####
        buildItem(forSaleSign);//####[61]####
    }//####[62]####
//####[65]####
    private static volatile Method __pt__buildTask_Color_Color_method = null;//####[65]####
    private synchronized static void __pt__buildTask_Color_Color_ensureMethodVarSet() {//####[65]####
        if (__pt__buildTask_Color_Color_method == null) {//####[65]####
            try {//####[65]####
                __pt__buildTask_Color_Color_method = ParaTaskHelper.getDeclaredMethod(new ParaTaskHelper.ClassGetter().getCurrentClass(), "__pt__buildTask", new Class[] {//####[65]####
                    Color.class, Color.class//####[65]####
                });//####[65]####
            } catch (Exception e) {//####[65]####
                e.printStackTrace();//####[65]####
            }//####[65]####
        }//####[65]####
    }//####[65]####
    public TaskID<Void> buildTask(Color colorWalls, Color colorRoof) {//####[65]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[65]####
        return buildTask(colorWalls, colorRoof, new TaskInfo());//####[65]####
    }//####[65]####
    public TaskID<Void> buildTask(Color colorWalls, Color colorRoof, TaskInfo taskinfo) {//####[65]####
        // ensure Method variable is set//####[65]####
        if (__pt__buildTask_Color_Color_method == null) {//####[65]####
            __pt__buildTask_Color_Color_ensureMethodVarSet();//####[65]####
        }//####[65]####
        taskinfo.setParameters(colorWalls, colorRoof);//####[65]####
        taskinfo.setMethod(__pt__buildTask_Color_Color_method);//####[65]####
        taskinfo.setInstance(this);//####[65]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[65]####
    }//####[65]####
    public TaskID<Void> buildTask(TaskID<Color> colorWalls, Color colorRoof) {//####[65]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[65]####
        return buildTask(colorWalls, colorRoof, new TaskInfo());//####[65]####
    }//####[65]####
    public TaskID<Void> buildTask(TaskID<Color> colorWalls, Color colorRoof, TaskInfo taskinfo) {//####[65]####
        // ensure Method variable is set//####[65]####
        if (__pt__buildTask_Color_Color_method == null) {//####[65]####
            __pt__buildTask_Color_Color_ensureMethodVarSet();//####[65]####
        }//####[65]####
        taskinfo.setTaskIdArgIndexes(0);//####[65]####
        taskinfo.addDependsOn(colorWalls);//####[65]####
        taskinfo.setParameters(colorWalls, colorRoof);//####[65]####
        taskinfo.setMethod(__pt__buildTask_Color_Color_method);//####[65]####
        taskinfo.setInstance(this);//####[65]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[65]####
    }//####[65]####
    public TaskID<Void> buildTask(BlockingQueue<Color> colorWalls, Color colorRoof) {//####[65]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[65]####
        return buildTask(colorWalls, colorRoof, new TaskInfo());//####[65]####
    }//####[65]####
    public TaskID<Void> buildTask(BlockingQueue<Color> colorWalls, Color colorRoof, TaskInfo taskinfo) {//####[65]####
        // ensure Method variable is set//####[65]####
        if (__pt__buildTask_Color_Color_method == null) {//####[65]####
            __pt__buildTask_Color_Color_ensureMethodVarSet();//####[65]####
        }//####[65]####
        taskinfo.setQueueArgIndexes(0);//####[65]####
        taskinfo.setIsPipeline(true);//####[65]####
        taskinfo.setParameters(colorWalls, colorRoof);//####[65]####
        taskinfo.setMethod(__pt__buildTask_Color_Color_method);//####[65]####
        taskinfo.setInstance(this);//####[65]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[65]####
    }//####[65]####
    public TaskID<Void> buildTask(Color colorWalls, TaskID<Color> colorRoof) {//####[65]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[65]####
        return buildTask(colorWalls, colorRoof, new TaskInfo());//####[65]####
    }//####[65]####
    public TaskID<Void> buildTask(Color colorWalls, TaskID<Color> colorRoof, TaskInfo taskinfo) {//####[65]####
        // ensure Method variable is set//####[65]####
        if (__pt__buildTask_Color_Color_method == null) {//####[65]####
            __pt__buildTask_Color_Color_ensureMethodVarSet();//####[65]####
        }//####[65]####
        taskinfo.setTaskIdArgIndexes(1);//####[65]####
        taskinfo.addDependsOn(colorRoof);//####[65]####
        taskinfo.setParameters(colorWalls, colorRoof);//####[65]####
        taskinfo.setMethod(__pt__buildTask_Color_Color_method);//####[65]####
        taskinfo.setInstance(this);//####[65]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[65]####
    }//####[65]####
    public TaskID<Void> buildTask(TaskID<Color> colorWalls, TaskID<Color> colorRoof) {//####[65]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[65]####
        return buildTask(colorWalls, colorRoof, new TaskInfo());//####[65]####
    }//####[65]####
    public TaskID<Void> buildTask(TaskID<Color> colorWalls, TaskID<Color> colorRoof, TaskInfo taskinfo) {//####[65]####
        // ensure Method variable is set//####[65]####
        if (__pt__buildTask_Color_Color_method == null) {//####[65]####
            __pt__buildTask_Color_Color_ensureMethodVarSet();//####[65]####
        }//####[65]####
        taskinfo.setTaskIdArgIndexes(0, 1);//####[65]####
        taskinfo.addDependsOn(colorWalls);//####[65]####
        taskinfo.addDependsOn(colorRoof);//####[65]####
        taskinfo.setParameters(colorWalls, colorRoof);//####[65]####
        taskinfo.setMethod(__pt__buildTask_Color_Color_method);//####[65]####
        taskinfo.setInstance(this);//####[65]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[65]####
    }//####[65]####
    public TaskID<Void> buildTask(BlockingQueue<Color> colorWalls, TaskID<Color> colorRoof) {//####[65]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[65]####
        return buildTask(colorWalls, colorRoof, new TaskInfo());//####[65]####
    }//####[65]####
    public TaskID<Void> buildTask(BlockingQueue<Color> colorWalls, TaskID<Color> colorRoof, TaskInfo taskinfo) {//####[65]####
        // ensure Method variable is set//####[65]####
        if (__pt__buildTask_Color_Color_method == null) {//####[65]####
            __pt__buildTask_Color_Color_ensureMethodVarSet();//####[65]####
        }//####[65]####
        taskinfo.setQueueArgIndexes(0);//####[65]####
        taskinfo.setIsPipeline(true);//####[65]####
        taskinfo.setTaskIdArgIndexes(1);//####[65]####
        taskinfo.addDependsOn(colorRoof);//####[65]####
        taskinfo.setParameters(colorWalls, colorRoof);//####[65]####
        taskinfo.setMethod(__pt__buildTask_Color_Color_method);//####[65]####
        taskinfo.setInstance(this);//####[65]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[65]####
    }//####[65]####
    public TaskID<Void> buildTask(Color colorWalls, BlockingQueue<Color> colorRoof) {//####[65]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[65]####
        return buildTask(colorWalls, colorRoof, new TaskInfo());//####[65]####
    }//####[65]####
    public TaskID<Void> buildTask(Color colorWalls, BlockingQueue<Color> colorRoof, TaskInfo taskinfo) {//####[65]####
        // ensure Method variable is set//####[65]####
        if (__pt__buildTask_Color_Color_method == null) {//####[65]####
            __pt__buildTask_Color_Color_ensureMethodVarSet();//####[65]####
        }//####[65]####
        taskinfo.setQueueArgIndexes(1);//####[65]####
        taskinfo.setIsPipeline(true);//####[65]####
        taskinfo.setParameters(colorWalls, colorRoof);//####[65]####
        taskinfo.setMethod(__pt__buildTask_Color_Color_method);//####[65]####
        taskinfo.setInstance(this);//####[65]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[65]####
    }//####[65]####
    public TaskID<Void> buildTask(TaskID<Color> colorWalls, BlockingQueue<Color> colorRoof) {//####[65]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[65]####
        return buildTask(colorWalls, colorRoof, new TaskInfo());//####[65]####
    }//####[65]####
    public TaskID<Void> buildTask(TaskID<Color> colorWalls, BlockingQueue<Color> colorRoof, TaskInfo taskinfo) {//####[65]####
        // ensure Method variable is set//####[65]####
        if (__pt__buildTask_Color_Color_method == null) {//####[65]####
            __pt__buildTask_Color_Color_ensureMethodVarSet();//####[65]####
        }//####[65]####
        taskinfo.setQueueArgIndexes(1);//####[65]####
        taskinfo.setIsPipeline(true);//####[65]####
        taskinfo.setTaskIdArgIndexes(0);//####[65]####
        taskinfo.addDependsOn(colorWalls);//####[65]####
        taskinfo.setParameters(colorWalls, colorRoof);//####[65]####
        taskinfo.setMethod(__pt__buildTask_Color_Color_method);//####[65]####
        taskinfo.setInstance(this);//####[65]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[65]####
    }//####[65]####
    public TaskID<Void> buildTask(BlockingQueue<Color> colorWalls, BlockingQueue<Color> colorRoof) {//####[65]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[65]####
        return buildTask(colorWalls, colorRoof, new TaskInfo());//####[65]####
    }//####[65]####
    public TaskID<Void> buildTask(BlockingQueue<Color> colorWalls, BlockingQueue<Color> colorRoof, TaskInfo taskinfo) {//####[65]####
        // ensure Method variable is set//####[65]####
        if (__pt__buildTask_Color_Color_method == null) {//####[65]####
            __pt__buildTask_Color_Color_ensureMethodVarSet();//####[65]####
        }//####[65]####
        taskinfo.setQueueArgIndexes(0, 1);//####[65]####
        taskinfo.setIsPipeline(true);//####[65]####
        taskinfo.setParameters(colorWalls, colorRoof);//####[65]####
        taskinfo.setMethod(__pt__buildTask_Color_Color_method);//####[65]####
        taskinfo.setInstance(this);//####[65]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[65]####
    }//####[65]####
    public void __pt__buildTask(Color colorWalls, Color colorRoof) {//####[65]####
        this.colorWalls = colorWalls;//####[66]####
        this.colorRoof = colorRoof;//####[67]####
        initialiseMaterial();//####[68]####
        TaskID idFoundation = buildAllTask(foundation);//####[70]####
        TaskInfo __pt__idWalls = new TaskInfo();//####[71]####
//####[71]####
        /*  -- ParaTask dependsOn clause for 'idWalls' -- *///####[71]####
        __pt__idWalls.addDependsOn(idFoundation);//####[71]####
//####[71]####
        TaskID idWalls = buildAllTask(wallSiding, __pt__idWalls);//####[71]####
        TaskInfo __pt__idRoof = new TaskInfo();//####[72]####
//####[72]####
        /*  -- ParaTask dependsOn clause for 'idRoof' -- *///####[72]####
        __pt__idRoof.addDependsOn(idWalls);//####[72]####
//####[72]####
        TaskID idRoof = buildAllTask(roofTiles, __pt__idRoof);//####[72]####
        TaskInfo __pt__idDoor = new TaskInfo();//####[73]####
//####[73]####
        /*  -- ParaTask dependsOn clause for 'idDoor' -- *///####[73]####
        __pt__idDoor.addDependsOn(idWalls);//####[73]####
//####[73]####
        TaskID idDoor = buildItemTask(door, __pt__idDoor);//####[73]####
        TaskInfo __pt__idWindows = new TaskInfo();//####[74]####
//####[74]####
        /*  -- ParaTask dependsOn clause for 'idWindows' -- *///####[74]####
        __pt__idWindows.addDependsOn(idWalls);//####[74]####
//####[74]####
        TaskID idWindows = buildAllTask(windows, __pt__idWindows);//####[74]####
        TaskInfo __pt__idSign = new TaskInfo();//####[75]####
//####[75]####
        /*  -- ParaTask dependsOn clause for 'idSign' -- *///####[75]####
        __pt__idSign.addDependsOn(idRoof);//####[75]####
        __pt__idSign.addDependsOn(idDoor);//####[75]####
        __pt__idSign.addDependsOn(idWindows);//####[75]####
//####[75]####
        TaskID idSign = buildItemTask(forSaleSign, __pt__idSign);//####[75]####
        try {//####[77]####
            idSign.waitTillFinished();//####[78]####
        } catch (Exception e) {//####[79]####
            e.printStackTrace();//####[80]####
        }//####[81]####
    }//####[82]####
//####[82]####
//####[84]####
    private void buildItem(BuildingMaterial item) {//####[84]####
        if (!item.getAndSetVisible(true)) //####[85]####
        {//####[85]####
            simulateWork(N);//####[86]####
            repaint();//####[87]####
        }//####[88]####
    }//####[89]####
//####[91]####
    private static volatile Method __pt__buildItemTask_BuildingMaterial_method = null;//####[91]####
    private synchronized static void __pt__buildItemTask_BuildingMaterial_ensureMethodVarSet() {//####[91]####
        if (__pt__buildItemTask_BuildingMaterial_method == null) {//####[91]####
            try {//####[91]####
                __pt__buildItemTask_BuildingMaterial_method = ParaTaskHelper.getDeclaredMethod(new ParaTaskHelper.ClassGetter().getCurrentClass(), "__pt__buildItemTask", new Class[] {//####[91]####
                    BuildingMaterial.class//####[91]####
                });//####[91]####
            } catch (Exception e) {//####[91]####
                e.printStackTrace();//####[91]####
            }//####[91]####
        }//####[91]####
    }//####[91]####
    public TaskID<Void> buildItemTask(BuildingMaterial item) {//####[91]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[91]####
        return buildItemTask(item, new TaskInfo());//####[91]####
    }//####[91]####
    public TaskID<Void> buildItemTask(BuildingMaterial item, TaskInfo taskinfo) {//####[91]####
        // ensure Method variable is set//####[91]####
        if (__pt__buildItemTask_BuildingMaterial_method == null) {//####[91]####
            __pt__buildItemTask_BuildingMaterial_ensureMethodVarSet();//####[91]####
        }//####[91]####
        taskinfo.setParameters(item);//####[91]####
        taskinfo.setMethod(__pt__buildItemTask_BuildingMaterial_method);//####[91]####
        taskinfo.setInstance(this);//####[91]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[91]####
    }//####[91]####
    public TaskID<Void> buildItemTask(TaskID<BuildingMaterial> item) {//####[91]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[91]####
        return buildItemTask(item, new TaskInfo());//####[91]####
    }//####[91]####
    public TaskID<Void> buildItemTask(TaskID<BuildingMaterial> item, TaskInfo taskinfo) {//####[91]####
        // ensure Method variable is set//####[91]####
        if (__pt__buildItemTask_BuildingMaterial_method == null) {//####[91]####
            __pt__buildItemTask_BuildingMaterial_ensureMethodVarSet();//####[91]####
        }//####[91]####
        taskinfo.setTaskIdArgIndexes(0);//####[91]####
        taskinfo.addDependsOn(item);//####[91]####
        taskinfo.setParameters(item);//####[91]####
        taskinfo.setMethod(__pt__buildItemTask_BuildingMaterial_method);//####[91]####
        taskinfo.setInstance(this);//####[91]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[91]####
    }//####[91]####
    public TaskID<Void> buildItemTask(BlockingQueue<BuildingMaterial> item) {//####[91]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[91]####
        return buildItemTask(item, new TaskInfo());//####[91]####
    }//####[91]####
    public TaskID<Void> buildItemTask(BlockingQueue<BuildingMaterial> item, TaskInfo taskinfo) {//####[91]####
        // ensure Method variable is set//####[91]####
        if (__pt__buildItemTask_BuildingMaterial_method == null) {//####[91]####
            __pt__buildItemTask_BuildingMaterial_ensureMethodVarSet();//####[91]####
        }//####[91]####
        taskinfo.setQueueArgIndexes(0);//####[91]####
        taskinfo.setIsPipeline(true);//####[91]####
        taskinfo.setParameters(item);//####[91]####
        taskinfo.setMethod(__pt__buildItemTask_BuildingMaterial_method);//####[91]####
        taskinfo.setInstance(this);//####[91]####
        return TaskpoolFactory.getTaskpool().enqueue(taskinfo);//####[91]####
    }//####[91]####
    public void __pt__buildItemTask(BuildingMaterial item) {//####[91]####
        buildItem(item);//####[92]####
    }//####[93]####
//####[93]####
//####[95]####
    private static volatile Method __pt__buildAllTask_ListBuildingMaterial_method = null;//####[95]####
    private synchronized static void __pt__buildAllTask_ListBuildingMaterial_ensureMethodVarSet() {//####[95]####
        if (__pt__buildAllTask_ListBuildingMaterial_method == null) {//####[95]####
            try {//####[95]####
                __pt__buildAllTask_ListBuildingMaterial_method = ParaTaskHelper.getDeclaredMethod(new ParaTaskHelper.ClassGetter().getCurrentClass(), "__pt__buildAllTask", new Class[] {//####[95]####
                    List.class//####[95]####
                });//####[95]####
            } catch (Exception e) {//####[95]####
                e.printStackTrace();//####[95]####
            }//####[95]####
        }//####[95]####
    }//####[95]####
    public TaskIDGroup<Void> buildAllTask(List<BuildingMaterial> items) {//####[95]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[95]####
        return buildAllTask(items, new TaskInfo());//####[95]####
    }//####[95]####
    public TaskIDGroup<Void> buildAllTask(List<BuildingMaterial> items, TaskInfo taskinfo) {//####[95]####
        // ensure Method variable is set//####[95]####
        if (__pt__buildAllTask_ListBuildingMaterial_method == null) {//####[95]####
            __pt__buildAllTask_ListBuildingMaterial_ensureMethodVarSet();//####[95]####
        }//####[95]####
        taskinfo.setParameters(items);//####[95]####
        taskinfo.setMethod(__pt__buildAllTask_ListBuildingMaterial_method);//####[95]####
        taskinfo.setInstance(this);//####[95]####
        return TaskpoolFactory.getTaskpool().enqueueMulti(taskinfo, -1);//####[95]####
    }//####[95]####
    public TaskIDGroup<Void> buildAllTask(TaskID<List<BuildingMaterial>> items) {//####[95]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[95]####
        return buildAllTask(items, new TaskInfo());//####[95]####
    }//####[95]####
    public TaskIDGroup<Void> buildAllTask(TaskID<List<BuildingMaterial>> items, TaskInfo taskinfo) {//####[95]####
        // ensure Method variable is set//####[95]####
        if (__pt__buildAllTask_ListBuildingMaterial_method == null) {//####[95]####
            __pt__buildAllTask_ListBuildingMaterial_ensureMethodVarSet();//####[95]####
        }//####[95]####
        taskinfo.setTaskIdArgIndexes(0);//####[95]####
        taskinfo.addDependsOn(items);//####[95]####
        taskinfo.setParameters(items);//####[95]####
        taskinfo.setMethod(__pt__buildAllTask_ListBuildingMaterial_method);//####[95]####
        taskinfo.setInstance(this);//####[95]####
        return TaskpoolFactory.getTaskpool().enqueueMulti(taskinfo, -1);//####[95]####
    }//####[95]####
    public TaskIDGroup<Void> buildAllTask(BlockingQueue<List<BuildingMaterial>> items) {//####[95]####
        //-- execute asynchronously by enqueuing onto the taskpool//####[95]####
        return buildAllTask(items, new TaskInfo());//####[95]####
    }//####[95]####
    public TaskIDGroup<Void> buildAllTask(BlockingQueue<List<BuildingMaterial>> items, TaskInfo taskinfo) {//####[95]####
        // ensure Method variable is set//####[95]####
        if (__pt__buildAllTask_ListBuildingMaterial_method == null) {//####[95]####
            __pt__buildAllTask_ListBuildingMaterial_ensureMethodVarSet();//####[95]####
        }//####[95]####
        taskinfo.setQueueArgIndexes(0);//####[95]####
        taskinfo.setIsPipeline(true);//####[95]####
        taskinfo.setParameters(items);//####[95]####
        taskinfo.setMethod(__pt__buildAllTask_ListBuildingMaterial_method);//####[95]####
        taskinfo.setInstance(this);//####[95]####
        return TaskpoolFactory.getTaskpool().enqueueMulti(taskinfo, -1);//####[95]####
    }//####[95]####
    public void __pt__buildAllTask(List<BuildingMaterial> items) {//####[95]####
        buildAll(items);//####[96]####
    }//####[97]####
//####[97]####
//####[99]####
    private void buildAll(List<BuildingMaterial> items) {//####[99]####
        Iterator<BuildingMaterial> it = items.iterator();//####[100]####
        while (it.hasNext()) //####[101]####
        {//####[101]####
            buildItem(it.next());//####[102]####
        }//####[103]####
    }//####[104]####
//####[106]####
    public void update(Graphics g) {//####[106]####
        paint(g);//####[107]####
    }//####[108]####
//####[110]####
    public void paint(Graphics g) {//####[110]####
        if (clearScreen) //####[112]####
        {//####[112]####
            g.clearRect(0, 0, width, height);//####[113]####
            clearScreen = false;//####[114]####
        }//####[115]####
        for (BuildingMaterial b : foundation) //####[118]####
        {//####[118]####
            if (b.isVisible()) //####[119]####
            {//####[119]####
                g.setColor(new Color(162, 158, 24));//####[120]####
                g.fillRect(b.getX(), b.getY(), b.getWidth(), b.getHeight());//####[121]####
                g.setColor(Color.BLACK);//####[122]####
                g.drawRect(b.getX(), b.getY(), b.getWidth(), b.getHeight());//####[123]####
            }//####[124]####
        }//####[125]####
        for (BuildingMaterial b : wallSiding) //####[128]####
        {//####[128]####
            if (b.isVisible()) //####[130]####
            {//####[130]####
                g.setColor(colorWalls);//####[131]####
                g.fillRect(b.getX(), b.getY(), b.getWidth(), b.getHeight());//####[132]####
                g.setColor(Color.BLACK);//####[133]####
                g.drawRect(b.getX(), b.getY(), b.getWidth(), b.getHeight());//####[134]####
            }//####[135]####
        }//####[136]####
        for (BuildingMaterial b : roofTiles) //####[139]####
        {//####[139]####
            if (b.isVisible()) //####[141]####
            {//####[141]####
                g.setColor(colorRoof);//####[142]####
                g.fillRect(b.getX(), b.getY(), b.getWidth(), b.getHeight());//####[143]####
                g.setColor(Color.BLACK);//####[144]####
                g.drawRect(b.getX(), b.getY(), b.getWidth(), b.getHeight());//####[145]####
            }//####[146]####
        }//####[147]####
        if (door.isVisible()) //####[150]####
        {//####[150]####
            g.setColor(new Color(152, 118, 84));//####[151]####
            g.fillRect(door.getX(), door.getY(), door.getWidth(), door.getHeight());//####[152]####
            g.setColor(Color.BLACK);//####[153]####
            g.drawRect(door.getX(), door.getY(), door.getWidth(), door.getHeight());//####[154]####
        }//####[155]####
        for (BuildingMaterial b : windows) //####[158]####
        {//####[158]####
            if (b.isVisible()) //####[159]####
            {//####[159]####
                g.setColor(new Color(173, 216, 230));//####[160]####
                g.fillRect(b.getX(), b.getY(), b.getWidth(), b.getHeight());//####[161]####
                g.setColor(Color.BLACK);//####[162]####
                g.drawRect(b.getX(), b.getY(), b.getWidth(), b.getHeight());//####[163]####
            }//####[164]####
        }//####[165]####
        if (forSaleSign.isVisible()) //####[168]####
        {//####[168]####
            g.setColor(new Color(152, 118, 84));//####[169]####
            g.fillRect(400, 260, 15, 20);//####[170]####
            g.fillRect(445, 260, 15, 20);//####[171]####
            g.setColor(Color.BLACK);//####[172]####
            g.drawRect(400, 260, 15, 20);//####[173]####
            g.drawRect(445, 260, 15, 20);//####[174]####
            g.setColor(new Color(255, 239, 0));//####[176]####
            g.fillRect(forSaleSign.getX(), forSaleSign.getY(), forSaleSign.getWidth(), forSaleSign.getHeight());//####[177]####
            g.setColor(Color.BLACK);//####[178]####
            g.drawRect(forSaleSign.getX(), forSaleSign.getY(), forSaleSign.getWidth(), forSaleSign.getHeight());//####[179]####
            Font f = g.getFont();//####[181]####
            g.setFont(new Font(f.getName(), Font.BOLD, 21));//####[182]####
            g.drawString("For", forSaleSign.getX() + 30, forSaleSign.getY() + 30);//####[183]####
            g.drawString("Sale", forSaleSign.getX() + 25, forSaleSign.getY() + 60);//####[184]####
        }//####[185]####
    }//####[186]####
//####[188]####
    private void initFoundation() {//####[188]####
        int numCols = 31;//####[190]####
        int w = 15;//####[191]####
        int h = 10;//####[192]####
        int x = 20;//####[194]####
        int y = 280;//####[195]####
        for (int i = 0; i < numCols; i++) //####[196]####
        foundation.add(new BuildingMaterial(x + i * w, y, w, h, false));//####[197]####
        x -= 7;//####[199]####
        y += h;//####[200]####
        for (int i = 0; i < numCols; i++) //####[201]####
        foundation.add(new BuildingMaterial(x + i * w, y, w, h, false));//####[202]####
        x += 7;//####[204]####
        y += h;//####[205]####
        for (int i = 0; i < numCols; i++) //####[206]####
        foundation.add(new BuildingMaterial(x + i * w, y, w, h, false));//####[207]####
        List<BuildingMaterial> list = new ArrayList<BuildingMaterial>();//####[209]####
        list.addAll(foundation);//####[210]####
        Collections.shuffle(list);//####[211]####
        foundation.clear();//####[212]####
        foundation.addAll(list);//####[213]####
    }//####[214]####
//####[216]####
    private void initWallSiding() {//####[216]####
        int numPlanks = 40;//####[217]####
        int totalW = 320;//####[218]####
        int w = totalW / numPlanks;//####[219]####
        int h = 150;//####[220]####
        int x = 40;//####[222]####
        int y = 130;//####[223]####
        for (int i = 0; i < numPlanks; i++) //####[224]####
        wallSiding.add(new BuildingMaterial(x + i * w, y, w, h, false));//####[225]####
        List<BuildingMaterial> list = new ArrayList<BuildingMaterial>();//####[228]####
        list.addAll(wallSiding);//####[229]####
        Collections.shuffle(list);//####[230]####
        wallSiding.clear();//####[231]####
        wallSiding.addAll(list);//####[232]####
    }//####[234]####
//####[236]####
    private void initRoofTiles() {//####[236]####
        int numPlanks = 12;//####[237]####
        int dec = 10;//####[238]####
        int h = 10;//####[239]####
        int w = 360;//####[240]####
        int x = 20;//####[242]####
        int y = 130 - h;//####[243]####
        for (int i = 0; i < numPlanks; i++) //####[244]####
        {//####[244]####
            roofTiles.add(new BuildingMaterial(x + i * dec, y - i * h, w, h, false));//####[245]####
            w -= 2 * dec;//####[246]####
        }//####[247]####
        List<BuildingMaterial> list = new ArrayList<BuildingMaterial>();//####[250]####
        list.addAll(roofTiles);//####[251]####
        Collections.shuffle(list);//####[252]####
        roofTiles.clear();//####[253]####
        roofTiles.addAll(list);//####[254]####
    }//####[255]####
//####[257]####
    private void initWindowsAndDoor() {//####[257]####
        door = new BuildingMaterial(63, 160, 75, 120, false);//####[258]####
        windows.add(new BuildingMaterial(160, 160, 80, 60, false));//####[260]####
        windows.add(new BuildingMaterial(253, 160, 75, 60, false));//####[261]####
    }//####[262]####
//####[264]####
    private void initForSaleSign() {//####[264]####
        forSaleSign = new BuildingMaterial(380, 180, 100, 80, false);//####[265]####
    }//####[266]####
//####[268]####
    public void setComputationLevel(int N) {//####[268]####
        this.N = N;//####[269]####
    }//####[270]####
//####[272]####
    public void reset() {//####[272]####
        clearScreen = true;//####[273]####
        for (BuildingMaterial b : foundation) //####[275]####
        {//####[275]####
            b.getAndSetVisible(false);//####[276]####
        }//####[277]####
        for (BuildingMaterial b : wallSiding) //####[279]####
        {//####[279]####
            b.getAndSetVisible(false);//####[280]####
        }//####[281]####
        for (BuildingMaterial b : roofTiles) //####[283]####
        {//####[283]####
            b.getAndSetVisible(false);//####[284]####
        }//####[285]####
        door.getAndSetVisible(false);//####[287]####
        for (BuildingMaterial b : windows) //####[289]####
        {//####[289]####
            b.getAndSetVisible(false);//####[290]####
        }//####[291]####
        forSaleSign.getAndSetVisible(false);//####[293]####
        repaint();//####[294]####
    }//####[295]####
//####[297]####
    private void simulateWork(int N) {//####[297]####
        double xmin = -1.0;//####[298]####
        double ymin = -1.0;//####[299]####
        double width = 2.0;//####[300]####
        double height = 2.0;//####[301]####
        for (int i = 0; i < N; i++) //####[302]####
        {//####[302]####
            for (int j = 0; j < N; j++) //####[303]####
            {//####[303]####
                double x = xmin + i * width / N;//####[304]####
                double y = ymin + j * height / N;//####[305]####
                Complex z = new Complex(x, y);//####[306]####
                newton(z);//####[307]####
            }//####[308]####
        }//####[309]####
    }//####[310]####
//####[312]####
    private Color newton(Complex z) {//####[312]####
        double EPSILON = 0.00000001;//####[313]####
        Complex four = new Complex(4, 0);//####[314]####
        Complex one = new Complex(1, 0);//####[315]####
        Complex root1 = new Complex(1, 0);//####[316]####
        Complex root2 = new Complex(-1, 0);//####[317]####
        Complex root3 = new Complex(0, 1);//####[318]####
        Complex root4 = new Complex(0, -1);//####[319]####
        for (int i = 0; i < 100; i++) //####[320]####
        {//####[320]####
            Complex f = z.times(z).times(z).times(z).minus(one);//####[321]####
            Complex fp = four.times(z).times(z).times(z);//####[322]####
            z = z.minus(f.divides(fp));//####[323]####
            if (z.minus(root1).abs() <= EPSILON) //####[324]####
            return Color.WHITE;//####[324]####
            if (z.minus(root2).abs() <= EPSILON) //####[325]####
            return Color.RED;//####[325]####
            if (z.minus(root3).abs() <= EPSILON) //####[326]####
            return Color.GREEN;//####[326]####
            if (z.minus(root4).abs() <= EPSILON) //####[327]####
            return Color.BLUE;//####[327]####
        }//####[328]####
        return Color.BLACK;//####[329]####
    }//####[330]####
//####[332]####
    public void initialiseMaterial() {//####[332]####
        foundation = new CopyOnWriteArrayList<BuildingMaterial>();//####[333]####
        wallSiding = new CopyOnWriteArrayList<BuildingMaterial>();//####[334]####
        roofTiles = new CopyOnWriteArrayList<BuildingMaterial>();//####[335]####
        windows = new CopyOnWriteArrayList<BuildingMaterial>();//####[336]####
        initFoundation();//####[338]####
        initWallSiding();//####[339]####
        initRoofTiles();//####[340]####
        initWindowsAndDoor();//####[341]####
        initForSaleSign();//####[342]####
    }//####[343]####
}//####[343]####
<file_sep>/WorkingStealing/src/house/BuildingMaterial.java
package house;

import java.util.concurrent.atomic.AtomicBoolean;

public class BuildingMaterial {
 
	private int x;
	private int y;
	private int width;
	private int height;
	private AtomicBoolean isVisible;
	
	public BuildingMaterial(int x, int y, int width, int height, boolean isVisible) {
		this.x = x;
		this.y = y;
		this.width = width;
		this.height = height;
		this.isVisible = new AtomicBoolean(isVisible);
	}

	public int getX() {
		return x;
	}

	public int getY() {
		return y;
	}

	public int getWidth() {
		return width;
	}

	public int getHeight() {
		return height;
	}

	public boolean isVisible() {
		return isVisible.get();
	}

	public boolean getAndSetVisible(boolean isVisible) {
		return this.isVisible.getAndSet(isVisible);
	}
}
<file_sep>/document/Work-Stealing & Recursive Partitioning with Fork_Join - igvita.com.html
<!DOCTYPE html>
<!-- saved from url=(0090)https://www.igvita.com/2012/02/29/work-stealing-and-recursive-partitioning-with-fork-join/ -->
<html lang="en"><head><meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
  
  <title>Work-Stealing &amp; Recursive Partitioning with Fork/Join - igvita.com</title>

  <script type="text/javascript" async="" src="./Work-Stealing &amp; Recursive Partitioning with Fork_Join - igvita.com_files/analytics.js.下载"></script><script>var dataLayer=dataLayer||[];dataLayer.push({'gtm.start':new Date().getTime(),event:'gtm.js'});</script>
  <script src="./Work-Stealing &amp; Recursive Partitioning with Fork_Join - igvita.com_files/gtm.js.下载" async="" defer=""></script>

  <link rel="preconnect" href="https://fonts.gstatic.com/" crossorigin="">
  <style>/* cyrillic-ext */
@font-face {
  font-family: 'Open Sans';
  font-style: normal;
  font-weight: 400;
  src: local('Open Sans'), local('OpenSans'), url(https://fonts.gstatic.com/s/opensans/v13/K88pR3goAWT7BTt32Z01mxJtnKITppOI_IvcXXDNrsc.woff2) format('woff2');
  unicode-range: U+0460-052F, U+20B4, U+2DE0-2DFF, U+A640-A69F;
}
/* cyrillic */
@font-face {
  font-family: 'Open Sans';
  font-style: normal;
  font-weight: 400;
  src: local('Open Sans'), local('OpenSans'), url(https://fonts.gstatic.com/s/opensans/v13/RjgO7rYTmqiVp7vzi-Q5URJtnKITppOI_IvcXXDNrsc.woff2) format('woff2');
  unicode-range: U+0400-045F, U+0490-0491, U+04B0-04B1, U+2116;
}
/* greek-ext */
@font-face {
  font-family: 'Open Sans';
  font-style: normal;
  font-weight: 400;
  src: local('Open Sans'), local('OpenSans'), url(https://fonts.gstatic.com/s/opensans/v13/LWCjsQkB6EMdfHrEVqA1KRJtnKITppOI_IvcXXDNrsc.woff2) format('woff2');
  unicode-range: U+1F00-1FFF;
}
/* greek */
@font-face {
  font-family: 'Open Sans';
  font-style: normal;
  font-weight: 400;
  src: local('Open Sans'), local('OpenSans'), url(https://fonts.gstatic.com/s/opensans/v13/xozscpT2726on7jbcb_pAhJtnKITppOI_IvcXXDNrsc.woff2) format('woff2');
  unicode-range: U+0370-03FF;
}
/* vietnamese */
@font-face {
  font-family: 'Open Sans';
  font-style: normal;
  font-weight: 400;
  src: local('Open Sans'), local('OpenSans'), url(https://fonts.gstatic.com/s/opensans/v13/59ZRklaO5bWGqF5A9baEERJtnKITppOI_IvcXXDNrsc.woff2) format('woff2');
  unicode-range: U+0102-0103, U+1EA0-1EF9, U+20AB;
}
/* latin-ext */
@font-face {
  font-family: 'Open Sans';
  font-style: normal;
  font-weight: 400;
  src: local('Open Sans'), local('OpenSans'), url(https://fonts.gstatic.com/s/opensans/v13/u-WUoqrET9fUeobQW7jkRRJtnKITppOI_IvcXXDNrsc.woff2) format('woff2');
  unicode-range: U+0100-024F, U+1E00-1EFF, U+20A0-20AB, U+20AD-20CF, U+2C60-2C7F, U+A720-A7FF;
}
/* latin */
@font-face {
  font-family: 'Open Sans';
  font-style: normal;
  font-weight: 400;
  src: local('Open Sans'), local('OpenSans'), url(https://fonts.gstatic.com/s/opensans/v13/cJZKeOuBrn4kERxqtaUH3VtXRa8TVwTICgirnJhmVJw.woff2) format('woff2');
  unicode-range: U+0000-00FF, U+0131, U+0152-0153, U+02C6, U+02DA, U+02DC, U+2000-206F, U+2074, U+20AC, U+2212, U+2215;
}
/* cyrillic-ext */
@font-face {
  font-family: 'Open Sans';
  font-style: normal;
  font-weight: 700;
  src: local('Open Sans Bold'), local('OpenSans-Bold'), url(https://fonts.gstatic.com/s/opensans/v13/k3k702ZOKiLJc3WVjuplzK-j2U0lmluP9RWlSytm3ho.woff2) format('woff2');
  unicode-range: U+0460-052F, U+20B4, U+2DE0-2DFF, U+A640-A69F;
}
/* cyrillic */
@font-face {
  font-family: 'Open Sans';
  font-style: normal;
  font-weight: 700;
  src: local('Open Sans Bold'), local('OpenSans-Bold'), url(https://fonts.gstatic.com/s/opensans/v13/k3k702ZOKiLJc3WVjuplzJX5f-9o1vgP2EXwfjgl7AY.woff2) format('woff2');
  unicode-range: U+0400-045F, U+0490-0491, U+04B0-04B1, U+2116;
}
/* greek-ext */
@font-face {
  font-family: 'Open Sans';
  font-style: normal;
  font-weight: 700;
  src: local('Open Sans Bold'), local('OpenSans-Bold'), url(https://fonts.gstatic.com/s/opensans/v13/k3k702ZOKiLJc3WVjuplzBWV49_lSm1NYrwo-zkhivY.woff2) format('woff2');
  unicode-range: U+1F00-1FFF;
}
/* greek */
@font-face {
  font-family: 'Open Sans';
  font-style: normal;
  font-weight: 700;
  src: local('Open Sans Bold'), local('OpenSans-Bold'), url(https://fonts.gstatic.com/s/opensans/v13/k3k702ZOKiLJc3WVjuplzKaRobkAwv3vxw3jMhVENGA.woff2) format('woff2');
  unicode-range: U+0370-03FF;
}
/* vietnamese */
@font-face {
  font-family: 'Open Sans';
  font-style: normal;
  font-weight: 700;
  src: local('Open Sans Bold'), local('OpenSans-Bold'), url(https://fonts.gstatic.com/s/opensans/v13/k3k702ZOKiLJc3WVjuplzP8zf_FOSsgRmwsS7Aa9k2w.woff2) format('woff2');
  unicode-range: U+0102-0103, U+1EA0-1EF9, U+20AB;
}
/* latin-ext */
@font-face {
  font-family: 'Open Sans';
  font-style: normal;
  font-weight: 700;
  src: local('Open Sans Bold'), local('OpenSans-Bold'), url(https://fonts.gstatic.com/s/opensans/v13/k3k702ZOKiLJc3WVjuplzD0LW-43aMEzIO6XUTLjad8.woff2) format('woff2');
  unicode-range: U+0100-024F, U+1E00-1EFF, U+20A0-20AB, U+20AD-20CF, U+2C60-2C7F, U+A720-A7FF;
}
/* latin */
@font-face {
  font-family: 'Open Sans';
  font-style: normal;
  font-weight: 700;
  src: local('Open Sans Bold'), local('OpenSans-Bold'), url(https://fonts.gstatic.com/s/opensans/v13/k3k702ZOKiLJc3WVjuplzOgdm0LZdjqr5-oayXSOefg.woff2) format('woff2');
  unicode-range: U+0000-00FF, U+0131, U+0152-0153, U+02C6, U+02DA, U+02DC, U+2000-206F, U+2074, U+20AC, U+2212, U+2215;
}
</style>

  <link rel="stylesheet" href="./Work-Stealing &amp; Recursive Partitioning with Fork_Join - igvita.com_files/A.style.css,q1s3as.pagespeed.cf.dtk_Z6HfGX.css">
  <style>.hll{background-color:#49483e}.c{color:#75715e}.err{color:#960050;background-color:#1e0010}.k{color:#66d9ef}.l{color:#ae81ff}.n{color:#f8f8f2}.o{color:#f92672}.p{color:#f8f8f2}.cm{color:#75715e}.cp{color:#75715e}.c1{color:#75715e}.cs{color:#75715e}.ge{font-style:italic}.gs{font-weight:bold}.kc{color:#66d9ef}.kd{color:#66d9ef}.kn{color:#f92672}.kp{color:#66d9ef}.kr{color:#66d9ef}.kt{color:#66d9ef}.ld{color:#e6db74}.m{color:#ae81ff}.s{color:#e6db74}.na{color:#a6e22e}.nb{color:#f8f8f2}.nc{color:#a6e22e}.no{color:#66d9ef}.nd{color:#a6e22e}.ni{color:#f8f8f2}.ne{color:#a6e22e}.nf{color:#a6e22e}.nl{color:#f8f8f2}.nn{color:#f8f8f2}.nx{color:#a6e22e}.py{color:#f8f8f2}.nt{color:#f92672}.nv{color:#f8f8f2}.ow{color:#f92672}.w{color:#f8f8f2}.mf{color:#ae81ff}.mh{color:#ae81ff}.mi{color:#ae81ff}.mo{color:#ae81ff}.sb{color:#e6db74}.sc{color:#e6db74}.sd{color:#e6db74}.s2{color:#e6db74}.se{color:#ae81ff}.sh{color:#e6db74}.si{color:#e6db74}.sx{color:#e6db74}.sr{color:#e6db74}.s1{color:#e6db74}.ss{color:#e6db74}.bp{color:#f8f8f2}.vc{color:#f8f8f2}.vg{color:#f8f8f2}.vi{color:#f8f8f2}.il{color:#ae81ff}</style>

  <link rel="manifest" href="https://www.igvita.com/manifest.json">
  
  <link rel="icon" sizes="192x192" href="data:image/webp;base64,UklGRhQ<KEY>VlA4TAcJAAAvv8AvEIU1atuOza3OCSaanSeobUa17T6<KEY>5<KEY>4s0AuBxPzO8jmbsS8GrLZ4G9itVoM8nkssW6CjLb3BDFGaoCcdnU/KXxMb8hrnZ18Ttr82UHq<KEY>>
  <meta name="theme-color" content="#000">

  <meta name="author" content="<NAME>">
  <meta name="twitter:card" content="summary">
  
    <meta name="description" content="JDK7&#39;s Fork/Join combines a double ended queue (deque) and a recursive job partitioning step to minimize synchronization - a great design pattern to keep in mind for single host and distributed cases!">
    <meta name="twitter:description" content="JDK7&#39;s Fork/Join combines a double ended queue (deque) and a recursive job partitioning step to minimize synchronization - a great design pattern to keep in mind for single host and distributed cases!">
  
  
    <meta property="og:image" content="http://www.igvita.com/posts/12/duke.png">
    <meta name="twitter:image:src" content="http://www.igvita.com/posts/12/duke.png">
  

  <meta name="twitter:creator" content="@igrigorik">
  <meta name="twitter:url" content="https://www.igvita.com/2012/02/29/work-stealing-and-recursive-partitioning-with-fork-join/">
  <meta name="twitter:title" content="Work-Stealing &amp; Recursive Partitioning with Fork/Join">
  <meta property="twitter:account_id" content="9980812">

  <meta name="viewport" content="width=device-width,initial-scale=1,maximum-scale=1">

  <link rel="alternate" type="application/rss+xml" title="igvita.com RSS Feed" href="https://www.igvita.com/feed/">
  <link rel="canonical" href="https://www.igvita.com/2012/02/29/work-stealing-and-recursive-partitioning-with-fork-join/">

  
<script src="./Work-Stealing &amp; Recursive Partitioning with Fork_Join - igvita.com_files/saved_resource"></script><script src="./Work-Stealing &amp; Recursive Partitioning with Fork_Join - igvita.com_files/count-data.js.下载"></script></head>

<body>

<div id="container">
  <header>
    <div class="content">
      <a href="https://www.igvita.com/">igvita.com</a> <b>&nbsp;|&nbsp;</b> <span>a goal is a dream with a deadline</span>
      <a href="https://www.igvita.com/" class="about">about</a>
    </div>
  </header>

  <div id="main" role="main">
  <div id="post" class="content" itemscope="" itemtype="http://schema.org/Article">
  <h1 itemprop="name">Work-Stealing &amp; Recursive Partitioning with Fork/Join</h1>
  <p class="byline">By <a href="https://www.igvita.com/" rel="author" itemprop="author"><NAME></a> on <b itemprop="datePublished" datetime="2012-02-29">February 29, 2012</b></p>

  <p><script data-pagespeed-no-defer="">(function(){var g=this;function h(b,d){var a=b.split("."),c=g;a[0]in c||!c.execScript||c.execScript("var "+a[0]);for(var e;a.length&&(e=a.shift());)a.length||void 0===d?c[e]?c=c[e]:c=c[e]={}:c[e]=d};function l(b){var d=b.length;if(0<d){for(var a=Array(d),c=0;c<d;c++)a[c]=b[c];return a}return[]};function m(b){var d=window;if(d.addEventListener)d.addEventListener("load",b,!1);else if(d.attachEvent)d.attachEvent("onload",b);else{var a=d.onload;d.onload=function(){b.call(this);a&&a.call(this)}}};var n;function p(b,d,a,c,e){this.h=b;this.j=d;this.l=a;this.f=e;this.g={height:window.innerHeight||document.documentElement.clientHeight||document.body.clientHeight,width:window.innerWidth||document.documentElement.clientWidth||document.body.clientWidth};this.i=c;this.b={};this.a=[];this.c={}}function q(b,d){var a,c,e=d.getAttribute("data-pagespeed-url-hash");if(a=e&&!(e in b.c))if(0>=d.offsetWidth&&0>=d.offsetHeight)a=!1;else{c=d.getBoundingClientRect();var f=document.body;a=c.top+("pageYOffset"in window?window.pageYOffset:(document.documentElement||f.parentNode||f).scrollTop);c=c.left+("pageXOffset"in window?window.pageXOffset:(document.documentElement||f.parentNode||f).scrollLeft);f=a.toString()+","+c;b.b.hasOwnProperty(f)?a=!1:(b.b[f]=!0,a=a<=b.g.height&&c<=b.g.width)}a&&(b.a.push(e),b.c[e]=!0)}p.prototype.checkImageForCriticality=function(b){b.getBoundingClientRect&&q(this,b)};h("pagespeed.CriticalImages.checkImageForCriticality",function(b){n.checkImageForCriticality(b)});h("pagespeed.CriticalImages.checkCriticalImages",function(){r(n)});function r(b){b.b={};for(var d=["IMG","INPUT"],a=[],c=0;c<d.length;++c)a=a.concat(l(document.getElementsByTagName(d[c])));if(0!=a.length&&a[0].getBoundingClientRect){for(c=0;d=a[c];++c)q(b,d);a="oh="+b.l;b.f&&(a+="&n="+b.f);if(d=0!=b.a.length)for(a+="&ci="+encodeURIComponent(b.a[0]),c=1;c<b.a.length;++c){var e=","+encodeURIComponent(b.a[c]);131072>=a.length+e.length&&(a+=e)}b.i&&(e="&rd="+encodeURIComponent(JSON.stringify(t())),131072>=a.length+e.length&&(a+=e),d=!0);u=a;if(d){c=b.h;b=b.j;var f;if(window.XMLHttpRequest)f=new XMLHttpRequest;else if(window.ActiveXObject)try{f=new ActiveXObject("Msxml2.XMLHTTP")}catch(k){try{f=new ActiveXObject("Microsoft.XMLHTTP")}catch(v){}}f&&(f.open("POST",c+(-1==c.indexOf("?")?"?":"&")+"url="+encodeURIComponent(b)),f.setRequestHeader("Content-Type","application/x-www-form-urlencoded"),f.send(a))}}}function t(){var b={},d=document.getElementsByTagName("IMG");if(0==d.length)return{};var a=d[0];if(!("naturalWidth"in a&&"naturalHeight"in a))return{};for(var c=0;a=d[c];++c){var e=a.getAttribute("data-pagespeed-url-hash");e&&(!(e in b)&&0<a.width&&0<a.height&&0<a.naturalWidth&&0<a.naturalHeight||e in b&&a.width>=b[e].o&&a.height>=b[e].m)&&(b[e]={rw:a.width,rh:a.height,ow:a.naturalWidth,oh:a.naturalHeight})}return b}var u="";h("pagespeed.CriticalImages.getBeaconData",function(){return u});h("pagespeed.CriticalImages.Run",function(b,d,a,c,e,f){var k=new p(b,d,a,e,f);n=k;c&&m(function(){window.setTimeout(function(){r(k)},0)})});})();pagespeed.CriticalImages.Run('/ngx_pagespeed_beacon','https://www.igvita.com/2012/02/29/work-stealing-and-recursive-partitioning-with-fork-join/','XwPRccgygX',true,false,'ciL5ehleprA');</script><img src="data:image/webp;base64,UklGRlYKAABXRUJQVlA4IEoKAABQLwCdASqCAG8APm0wlEckIyIhKTOcQIANiUAapoevmfOLtze8jhcrvQ360NvD5pvNu9G/oAdJz6DXlxeyV+3v7b+znmqvZJ/nPDPyieyvcXlMxJu2P9p52eCvyR1CPxn+c/6Phg7Nd+fih0q2gB9Lvsl/TvoD+qPYK/Wf00vZf6In7dINuAdn+Ezvnx/n6X8rWzANeRymeO2xjFn8QpzSaLT3ewAVY2esPU5JRCIcHjHghFUEpXpTkvYfYF9bFQGP7aM83gjUY5c7p6w6QXAU/kseXWtv+c6e9YYOX0/OuWM5XlZp2jtW44Jg236KM5cxJziZuNrc30h4RU<KEY>//<KEY> class="left" data-pagespeed-url-hash="2806458656" onload="pagespeed.CriticalImages.checkImageForCriticality(this);">Implementing an efficient parallel algorithm is, unfortunately, still a non-trivial task in most languages: we need to determine how to partition the problem, determine the optimal level of parallelism, and finally build an implementation with minimal synchronization. This last bit is especially critical since as <a href="http://en.wikipedia.org/wiki/Amdahl&#39;s_law">Amdahl's law</a> tells us: <strong>"the speedup of a program using multiple processors in parallel computing is limited by the time needed for the sequential fraction of the program".</strong></p>

<p>The Fork/Join framework (<a href="http://jcp.org/en/jsr/detail?id=166">JSR 166</a>) in <a href="http://openjdk.java.net/projects/jdk7/features/">JDK7</a> implements a clever work-stealing technique for parallel execution that is worth learning about - even if you are not a JDK user. Optimized for parallelizing <a href="http://en.wikipedia.org/wiki/Divide_and_conquer_algorithm">divide-and-conquer</a> (and <a href="http://en.wikipedia.org/wiki/MapReduce#Logical_view">map-reduce</a>) algorithms it abstracts all the CPU scheduling and work balancing behind a simple to use API.</p>

<h2>Load Balancing vs. Synchronization</h2>

<p>One of the key challenges in parallelizing any type of workload is the partitioning step: ideally we want to partition the work such that every piece will take the exact same amount of time. In reality, we often have to guess at what the partition should be, which means that some parts of the problem will take longer, either because of the inefficient partitioning scheme, or due to some other, unanticipated reasons (e.g. external service, slow disk access, etc).</p>

<p>This is where <a href="http://en.wikipedia.org/wiki/Cilk#Work-stealing">work-stealing</a> comes in. If some of the CPU cores finish their jobs early, then we want them to help to finish the problem. However, now we have to be careful: trying to "steal" work from another worker will require synchronization, which will slowdown the processing. Hence, <strong>we want work-stealing, but with minimal synchronization</strong> - think back to <a href="http://en.wikipedia.org/wiki/Amdahl&#39;s_law">Amdahl's law</a>.</p>

<h2>Fork/Join Work-Stealing</h2>

<p>The <a href="http://gee.cs.oswego.edu/dl/papers/fj.pdf">Fork-Join framework</a> (<a href="http://docs.oracle.com/javase/tutorial/essential/concurrency/forkjoin.html">docs</a>) solves this problem in a clever way: recursive job partitioning, and a <a href="http://en.wikipedia.org/wiki/Double-ended_queue">double-ended queue</a> (<strong>deque</strong>) structure for holding the tasks.</p>

<p><img src="./Work-Stealing &amp; Recursive Partitioning with Fork_Join - igvita.com_files/xwork-stealing.png.pagespeed.ic.iTkWB_3KHR.webp" class="center" data-pagespeed-url-hash="4118241220" onload="pagespeed.CriticalImages.checkImageForCriticality(this);"></p>

<p>Given a problem, we divide the problem into N large pieces, and hand each piece to one of the workers (2 in the diagram above). Each worker then recursively subdivides the first problem at the head of the deque and appends the split tasks to the head of the same deque. After a few iterations we will end up with some number of smaller tasks at the front of the deque, and a few larger and yet to be partitioned tasks on end. So far so good, but what do we get?</p>

<p>Imagine the second worker has finished all of its work, while the first worker is busy. To minimize synchronization the second worker grabs a job from <strong>the end</strong> of the deque (hence the reason for efficient head and tail access). By doing so, it will get the largest available block of work, allowing it to minimize the number of times it has to interact with the other worker (aka, minimize synchronization). Simple, but a very clever technique!</p>

<h2>Fork-Join in Practice (JRuby)</h2>

<p>It is important to understand why and how the Fork/Join framework works under the hood, but the best part is that the API presented to the developer completely abstracts all of these details. The runtime can and will determine the level of parallelism, as well as handle all the work of balancing tasks across the available workers:</p>

<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="nb">require</span> <span class="s1">'forkjoin'</span>

<span class="k">class</span> <span class="nc">Fibonacci</span> <span class="o">&lt;</span> <span class="no">ForkJoin</span><span class="o">::</span><span class="no">Task</span>
  <span class="k">def</span> <span class="nf">initialize</span><span class="p">(</span><span class="n">n</span><span class="p">)</span>
    <span class="vi">@n</span> <span class="o">=</span> <span class="n">n</span>
  <span class="k">end</span>

  <span class="k">def</span> <span class="nf">call</span>
    <span class="k">return</span> <span class="vi">@n</span> <span class="k">if</span> <span class="vi">@n</span> <span class="o">&lt;=</span> <span class="mi">1</span>

    <span class="p">(</span><span class="n">f</span> <span class="o">=</span> <span class="no">Fibonacci</span><span class="o">.</span><span class="n">new</span><span class="p">(</span><span class="vi">@n</span> <span class="o">-</span> <span class="mi">1</span><span class="p">))</span><span class="o">.</span><span class="n">fork</span>
    <span class="no">Fibonacci</span><span class="o">.</span><span class="n">new</span><span class="p">(</span><span class="vi">@n</span> <span class="o">-</span> <span class="mi">2</span><span class="p">)</span><span class="o">.</span><span class="n">call</span> <span class="o">+</span> <span class="n">f</span><span class="o">.</span><span class="n">join</span>
  <span class="k">end</span>
<span class="k">end</span>

<span class="n">n</span> <span class="o">=</span> <span class="no">ARGV</span><span class="o">.</span><span class="n">shift</span><span class="o">.</span><span class="n">to_i</span>
<span class="n">pool</span> <span class="o">=</span> <span class="no">ForkJoin</span><span class="o">::</span><span class="no">Pool</span><span class="o">.</span><span class="n">new</span> <span class="c1"># 2,4,8, ...</span>

<span class="nb">puts</span> <span class="s2">"fib(</span><span class="si">#{</span><span class="n">n</span><span class="si">}</span><span class="s2">) = </span><span class="si">#{</span><span class="n">pool</span><span class="o">.</span><span class="n">invoke</span><span class="p">(</span><span class="no">Fibonacci</span><span class="o">.</span><span class="n">new</span><span class="p">(</span><span class="n">n</span><span class="p">))</span><span class="si">}</span><span class="s2">, parallelism = </span><span class="si">#{</span><span class="n">pool</span><span class="o">.</span><span class="n">parallelism</span><span class="si">}</span><span class="s2">"</span>

<span class="c1"># $&gt; ruby fib.rb 33</span></code></pre></div>


<p>The <a href="https://github.com/headius/forkjoin.rb">JRuby forkjoin gem</a> is a simple wrapper for the Java API. In the example above, we instatiate a <code>ForkJoin::Pool</code> and call <code>invoke</code> passing it our Fibonacci problem. The Fibonacci problem is type of <code>ForkJoin::Task</code>, which implements a recursive <code>call</code> method: if the problem is "too big", then we split it into two parts, one of which is "forked" (pushed onto the head of the deque), and the second half we invoke immediately. The final answer is the sum of the two tasks.</p>

<p>By default, the <code>ForkJoin::Pool</code> will allocate the same number of threads as available CPU cores - in my case, that happens to be 2, but the code above will automatically scale up to the number of available cores! Copy the code, run it, and you will see all of your available resources light up under load.</p>

<h2>Map-Reduce and Fork-Join</h2>

<p>The recursion of the divide-and-conquer technique is what enables the efficient deque work-stealing. However, it is interesting to note that the <strong>"map-reduce" workflow is simply a special case of this pattern</strong>. Instead of recursively partitioning the problem, the map-reduce algorithm will subdivide the problem upfront. This, in turn, means that in the case of an unbalanced workload we are likely to steal finer-grained tasks, which will also lead to more need for synchronization - if you can partition the problem recursively, do so!</p>

<div class="highlight"><pre><code class="language-ruby" data-lang="ruby"><span class="nb">require</span> <span class="s1">'zlib'</span>
<span class="nb">require</span> <span class="s1">'forkjoin'</span>
<span class="nb">require</span> <span class="s1">'archive/tar/minitar'</span>

<span class="n">pool</span> <span class="o">=</span> <span class="no">ForkJoin</span><span class="o">::</span><span class="no">Pool</span><span class="o">.</span><span class="n">new</span>

<span class="n">jobs</span> <span class="o">=</span> <span class="no">Dir</span><span class="o">[</span><span class="no">ARGV</span><span class="o">[</span><span class="mi">0</span><span class="o">].</span><span class="n">chomp</span><span class="p">(</span><span class="s1">'/'</span><span class="p">)</span> <span class="o">+</span> <span class="s1">'/*'</span><span class="o">].</span><span class="n">map</span> <span class="k">do</span> <span class="o">|</span><span class="n">dir</span><span class="o">|</span>
  <span class="no">Proc</span><span class="o">.</span><span class="n">new</span> <span class="k">do</span>
    <span class="nb">puts</span> <span class="s2">"Threads: </span><span class="si">#{</span><span class="n">pool</span><span class="o">.</span><span class="n">active_thread_count</span><span class="si">}</span><span class="s2">, </span><span class="si">#{</span><span class="no">Thread</span><span class="o">.</span><span class="n">current</span><span class="si">}</span><span class="s2"> processing: </span><span class="si">#{</span><span class="n">dir</span><span class="si">}</span><span class="s2">"</span>

    <span class="n">backup</span> <span class="o">=</span> <span class="s2">"/tmp/backup/</span><span class="si">#{</span><span class="no">File</span><span class="o">.</span><span class="n">basename</span><span class="p">(</span><span class="n">dir</span><span class="p">)</span><span class="si">}</span><span class="s2">.tgz"</span>
    <span class="n">tgz</span> <span class="o">=</span> <span class="no">Zlib</span><span class="o">::</span><span class="no">GzipWriter</span><span class="o">.</span><span class="n">new</span><span class="p">(</span><span class="no">File</span><span class="o">.</span><span class="n">open</span><span class="p">(</span><span class="n">backup</span><span class="p">,</span> <span class="s1">'wb'</span><span class="p">))</span>
    <span class="no">Archive</span><span class="o">::</span><span class="no">Tar</span><span class="o">::</span><span class="no">Minitar</span><span class="o">.</span><span class="n">pack</span><span class="p">(</span><span class="n">dir</span><span class="p">,</span> <span class="n">tgz</span><span class="p">)</span>

    <span class="no">File</span><span class="o">.</span><span class="n">size</span><span class="p">(</span><span class="n">backup</span><span class="p">)</span>
  <span class="k">end</span>
<span class="k">end</span>

<span class="n">results</span> <span class="o">=</span> <span class="n">pool</span><span class="o">.</span><span class="n">invoke_all</span><span class="p">(</span><span class="n">jobs</span><span class="p">)</span><span class="o">.</span><span class="n">map</span><span class="p">(</span><span class="o">&amp;</span><span class="ss">:get</span><span class="p">)</span>
<span class="nb">puts</span> <span class="s2">"Created </span><span class="si">#{</span><span class="n">results</span><span class="o">.</span><span class="n">size</span><span class="si">}</span><span class="s2"> backup archives, total bytes: </span><span class="si">#{</span><span class="n">results</span><span class="o">.</span><span class="n">reduce</span><span class="p">(</span><span class="ss">:+</span><span class="p">)</span><span class="si">}</span><span class="s2">"</span>

<span class="c1"># $&gt; ruby backup.rb /home/igrigorik/</span></code></pre></div>


<p>The above is a simple, map-reduce example via the same API. Given a path, this program will iterate over all files and folders, create all the backup tasks upfront, and finally invoke them to create the backup archives. Best of all, there is no threadpool management or synchronization code to be seen and the framework will easily pin all of your available cores, as well as automatically balance the work between all of the workers.</p>

<h2>Parallel Java &amp; Distributed Work-Stealing</h2>

<p>The Fork/Join framework is deceivingly simple on the surface, but as usual, the <a href="http://cs.oswego.edu/pipermail/concurrency-interest/2012-January/008987.html">devil is in the details</a> when it comes to optimizing for performance. However, regardless of whether you are a JDK user or not, <strong>the deque, combined with a recursive partitioning step is a great pattern to keep in mind</strong>. The JDK implementation is built for "within single JVM" workloads, but a similar pattern can be just as useful in many distributed cases.</p>


  <div class="author-callout">
    <img src="data:image/webp;base64,UklGRkABAABXRUJQVlA4IDQBAACQBwCdASojACMAPm0sk0WkIqGY7M0AQAbEtIACimd5LwNhb1mmMhaemgd/9MsXcT04KxSkF9TgmxcVs3qi9pt9idTWiAAA/v0BSccs2Wslieu639ZzsnAqMw2Kt9aHa6taGUneSS3W3lot0I1v46dsp/Kb3zhlAY0xw88Sa7Qza0rN9FBXD7+ZMUUycl1Avh9tLShWimybukziNKH+3J3IGYAbiEAeatj+TGz/9BB120CzpM7Iavw4sX75hCG3STx5czWirHmauIxOdTCB8oWhrF01o48i4f5+iRRyj4swZ4pO8E8yhvuA5vu4q88HDgwLEd77r6uPyLFTJoMViFSYkyGbl7bitKwK8ALeKh6V6rv0F5w5yrrpb1vQSHGt9yd25ko2Fn8WH+p8NNDWKMeVsAAAAA==" alt="<NAME>" data-pagespeed-url-hash="3389108481" onload="pagespeed.CriticalImages.checkImageForCriticality(this);"><strong><NAME></strong> is a web performance engineer at Google, co-chair of the W3C Web Performance working group, and author of High Performance Browser Networking (O'Reilly) book — follow on <a href="https://twitter.com/igrigorik">Twitter</a>, <a href="https://plus.google.com/+IlyaGrigorik">Google+</a>.
  </div>

  <div class="content social">
    <a href="http://www.igvita.com/2012/02/29/work-stealing-and-recursive-partitioning-with-fork-join/#disqus_thread" onclick="return loadDisqus()">View comments (12)</a>, share on <a href="https://twitter.com/share?url=http://www.igvita.com/2012/02/29/work-stealing-and-recursive-partitioning-with-fork-join/&amp;text=Work-Stealing+%26+Recursive+Partitioning+with+Fork%2FJoin:&amp;via=igrigorik" target="_blank">Twitter</a><span id="twittercount"></span>, <a href="https://plus.google.com/share?url=http://www.igvita.com/2012/02/29/work-stealing-and-recursive-partitioning-with-fork-join/" target="_blank">Google+</a><span id="gpluscount"> (25)</span><span id="fbcount">, <a href="https://www.facebook.com/sharer/sharer.php?u=http://www.igvita.com/2012/02/29/work-stealing-and-recursive-partitioning-with-fork-join/" target="_blank">Facebook</a> (5)</span>.
  </div>
</div>

<div id="comments" class="content">
    <div id="disqus_thread"></div>
  </div>
</div>

<div id="meta">
  <div class="group book">
    <div class="book-cover" style="margin-top:0.2em"></div>

    <h3 style="color: #fff">High Performance Browser Networking - O'Reilly</h3>
    <p style="font-style:italic">What every web developer needs to know about the various types of networks (WiFi, 3G/4G), transport protocols (UDP, TCP, and TLS), application protocols (HTTP/1.1, HTTP/2), and APIs available in the browser (XHR &amp; Fetch, WebSocket, WebRTC, and more) to deliver the best—fast, reliable, and resilient—user experience.</p>

    <p style="padding-top:0.5em"><a href="https://hpbn.co/?utm_source=igvita&amp;utm_medium=referral&amp;utm_campaign=igvita-footer" style="text-decoration:none;"><span class="button">Read at hpbn.co (free)</span></a></p>
  </div>
</div>

<script>var disqus_url='http://www.igvita.com/2012/02/29/work-stealing-and-recursive-partitioning-with-fork-join/';var disqus_shortname='igvita';var loadDisqus=function(){var dsq=document.createElement('script');dsq.type='text/javascript';dsq.async=true;dsq.src='//igvita.disqus.com/embed.js';(document.getElementsByTagName('head')[0]||document.getElementsByTagName('body')[0]).appendChild(dsq);return false;};function social_counts(data){var twc=document.getElementById('twittercount'),gwc=document.getElementById('gpluscount'),fwc=document.getElementById('fbcount');if(data['Twitter']>0){twc.innerText=' ('+data['Twitter']+')'}if(data['GooglePlusOne']>0){gwc.innerText=' ('+data['GooglePlusOne']+')'}if(data['Facebook']['total_count']>0){fwc.innerHTML=", <a href='https://www.facebook.com/sharer/sharer.php?u=http://www.igvita.com/2012/02/29/work-stealing-and-recursive-partitioning-with-fork-join/' target='_blank'>Facebook</a>"+' ('+data['Facebook']['total_count']+')';}}var scount=document.createElement('script');scount.src="//free.sharedcount.com/?callback=social_counts&url=http://www.igvita.com/2012/02/29/work-stealing-and-recursive-partitioning-with-fork-join/&apikey=<KEY>"
document.getElementsByTagName('head')[0].appendChild(scount);</script>
<script src="./Work-Stealing &amp; Recursive Partitioning with Fork_Join - igvita.com_files/count.js.下载" async=""></script>




  <footer>
    <div id="copyright">
      <div class="group">
        <span>© <NAME></span>
        <a href="https://www.igvita.com/" class="about">about</a><a href="http://feeds.igvita.com/igvita" class="about rss">subscribe via rss</a>
      </div>
    </div>
  </footer>
</div> 


</body></html>