如何改进我的多线程代码

Question

在数组中搜索数字的正常方法：

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

我的多线程方式：

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;
    }
}

现在测试类:

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);
    }
}

运行这些针对大型数组的测试，假设 10 次：

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

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

我猜想多线程是递归的，分叉了太多进程。如果你去 JDK 17 的 API 页面上的 RecursiveTask 有一个计算斐波那契函数的例子，我基本上把它的格式复制到这里。如何改进多线程呢？

Answer 1

我要做的第一件事是使用 JMH 进行适当的基准测试，然后再看一下问题。 JMH 将处理一些明显的基准测试问题，如预热、运行多次以提高可靠性，如果正确完成，还会消除死代码。除此之外，它还可以让您访问一组内置的分析器。

我认为你的截止值太低了。给每个 CPU 大量的线性内存以供扫描（至少几 KB，但可能高很多）。这不仅会减少 FJ 的开销，还会给 CPU 一些 space 来发挥它的魔力。

Answer 2

您可以使用并行流：

boolean search(int x, int[] arr) {
    return Arrays.stream(arr).parallel()
        .filter(i -> i == x)
        .findAny()
        .isPresent();
}

这样您就不必自己处理多线程的低级机制。

如何改进我的多线程代码

how to improve upon my multithreading code

java

parallel-processing

concurrency

multithreading