ForkJoinPool与平原回归

Question

在阅读了关于ForkJoinPool的文章之后，我尝试了一个实验来测试与普通递归相比，ForkJoinPool到底有多快。

我递归地计算了文件夹中的文件数，我认为普通递归比ForkJoinPool执行得好得多。

这是我的密码。

递归任务

class DirectoryTask extends RecursiveTask<Long> {

    private Directory directory;

    @Override
    protected Long compute() {
        List<RecursiveTask<Long>> forks = new ArrayList<>();
        List<Directory> directories = directory.getDirectories();
        for (Directory directory : directories) {
            DirectoryTask directoryTask = new DirectoryTask(directory);
            forks.add(directoryTask);
            directoryTask.fork();
        }
        Long count = directory.getDoumentCount();
        for (RecursiveTask<Long> task : forks) {
            count += task.join();
        }
        return count;
    }
}

平原递归

private static Long getFileCount(Directory directory) {
        Long recursiveCount = 0L;
        List<Directory> directories = directory.getDirectories();
        if (null != directories) {
            for (Directory d : directories) {
                recursiveCount += getFileCount(d);
            }
        }
        return recursiveCount + directory.getDoumentCount();
    }

目录对象

class Directory {

    private List<Directory> directories;
    private Long doumentCount = 0L;

    static Directory fromFolder(File file) {
        List<Directory> children = new ArrayList<>();
        Long documentCount = 0L;
        if (!file.isDirectory()) {
            throw new IllegalArgumentException("Only directories are allowed");
        }
        String[] files = file.list();
        if (null != files) {
            for (String path : files) {
                File f = new File(file.getPath() + File.separator + path);
                if (f.isHidden()) {
                    continue;
                }
                if (f.isDirectory()) {
                    children.add(Directory.fromFolder(f));
                } else {
                    documentCount++;
                }
            }
        }
        return new Directory(children, documentCount);
    }
}

结果

• 普通复归: 3ms
• ForkJoinPool: 25

这里的错误在哪里？

我只是想了解是否存在一个特定的阈值，低于这个阈值，普通递归比ForkJoinPool更快。

Answer 1

生命中没有任何东西是免费的。如果你不得不把一个啤酒箱从你的车里搬到你的公寓里--还有什么更快的:手动把它搬到那里，或者先去小屋，让手推车用它来移动那个箱子？

创建线程对象是一个“本机”操作，深入到底层操作系统中以获取那里的资源。这可能是一个相当昂贵的行动。

意思:仅仅在一个问题上抛出“更多的线程”并不能自动加快速度。恰恰相反。当您的任务主要是CPU密集型时，并行执行可能会带来很小的收益。当您执行大量IO时，拥有多个线程可以“减少”等待时间，从而提高吞吐量。

换句话说:在做真正的工作之前，需要进行大量的活动。将它用于只需要几毫秒的计算，简直是太过分了。因此:您将看到在较大数据集上工作的“叉/连接”操作。

要进一步阅读，您可以查看并行流。这些人在幕后使用的是叉/连接框架；令人惊讶的是，期望任意的parallelStream比普通的流“更快”也是一种误解。

Answer 2

这方面有多个方面：

1. 同一问题的串行解(例如普通递归)和并行解(例如叉接)之间有区别吗？
2. 并行化文件系统访问的范围是什么？
3. 衡量性能的陷阱是什么？

回答#1。是的，这是有区别的。对于一个太小的问题，并行是不好的。通过并行解决方案，您需要对以下方面的间接费用进行核算：

• 创建和管理线程
• 将信息从父线程传递给子线程。
• 将子线程的结果返回给父线程。
• 同步访问共享数据结构，
• 等待最慢/最后完成子线程完成。

这些在实践中的表现取决于各种事情.包括问题的大小和并行的机会。

第二条的答案是(可能)不像你想象的那么多。典型的文件系统存储在具有物理特性的磁盘驱动器上，如磁盘旋转和磁盘磁头查找。这些通常会成为瓶颈，如果没有高端存储系统，那么并行性就没有多大的空间了。

第三条的答案是有很多陷阱。而这些陷阱可能导致非常误导(即无效)的性能结果.如果你不允许的话。最大的陷阱之一是JVM需要时间来“热身”；例如加载类、做JIT编译、调整堆的大小等等。

另一个适用于执行文件系统I/O的基准测试的陷阱是，典型的OS将执行诸如缓存磁盘块和文件/目录元数据等操作。因此，当您第二次访问一个文件或目录时，它可能比第一次更快。

尽管如此，如果您有一个设计良好的、高性能的文件系统(例如SSD上的inode)和一个设计良好的应用程序，并且有足够的核心，那么就有可能通过并行实现超乎寻常的文件系统扫描速度。(例如，在12小时内检查5亿个文件的修改时间戳.)