normal way of searching for a number in an array:

public class Search {
    public static boolean search(int x, int [] arr) {
        for (int i : arr) {
            if (x == i) {
                return true;
            }
        }
        return false;
    }
}

my way of multithreading it:

import java.util.concurrent.RecursiveTask;

public class SearchAsync extends RecursiveTask<Boolean> {
    private static final int CUTOFF = 8;

    private final int x;
    private final int[] arr;
    private final int lo, hi;

    private SearchAsync(int x, int[] arr) {
        this(x, arr, 0, arr.length - 1);
    }

    private SearchAsync(int x, int[] arr, int lo, int hi) {
        this.x = x;
        this.arr = arr;
        this.lo = lo;
        this.hi = hi;
    }

    public static boolean search(int x, int[] arr) {
        return new SearchAsync(x, arr).compute();
    }

    protected Boolean compute() {
        if (hi - lo < CUTOFF) {
            return computeSync();
        }
        int mid = (lo   hi) >> 1;
        SearchAsync sa1 = new SearchAsync(x, arr, lo, mid);
        sa1.fork();
        SearchAsync sa2 = new SearchAsync(x, arr, mid   1, hi);
        return sa2.compute() || sa1.join();
    }

    private boolean computeSync() {
        for (int i = lo; i <= hi; i  ) {
            if (x == arr[i]) {
                return true;
            }
        }
        return false;
    }
}

now the testing classes:

public class Test {
    private static final int MAGIC_NUMBER = 69;

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        int[] arr = new int[n];
        int iter = Integer.parseInt(args[1]);
        long start = System.currentTimeMillis();
        for (int i = 0; i < iter; i  ) {
            Search.search(MAGIC_NUMBER, arr);
        }
        long end = System.currentTimeMillis();
        System.out.println((end - start) / 1_000.0);
    }
}

public class TestAsync {
    private static final int MAGIC_NUMBER = 69;

    public static void main(String[] args) {
        int n = Integer.parseInt(args[0]);
        int[] arr = new int[n];
        int iter = Integer.parseInt(args[1]);
        long start = System.currentTimeMillis();
        for (int i = 0; i < iter; i  ) {
            SearchAsync.search(MAGIC_NUMBER, arr);
        }
        long end = System.currentTimeMillis();
        System.out.println((end - start) / 1_000.0);
    }
}

run these tests for a large array and lets say 10 times:

gursimarmiglani@Gursimars-MacBook-Pro multithread % java Test 1000000000 10
1.924

gursimarmiglani@Gursimars-MacBook-Pro multithread % java TestAsync 1000000000 10
6.311

I guess that multithreading is recursive and forks too many processes. if u go to JDK 17's API page on RecursiveTask there's an example of computing the fibonacci function and I basically copied its format into here. how to improve upon multithreading it?

CodePudding user response：

The first thing I would do is to make a proper benchmark using JMH and then have another look at the problem. JMH will take care of some obvious benchmark problems like warmup, running multiple times to increase reliability, and dead code elimination if done correctly. Apart from that, it will also give you access to a set of built-in profilers.

I think your cutoff is way too low. Give each CPU a significant amount of linear memory to scan through (at least a few KB but probably a lot higher). This will not only reduce the overhead of FJ but also give the CPU some space to do its magic.