ForkJoinPool 与普通递归
ForkJoinPool vs Plain Recursion
阅读 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 更快。
生活中没有免费的东西。如果您必须将一个啤酒箱从您的汽车移动到您的公寓 - 哪个更快:手动将其运送到那里,或者先去棚屋,让手推车用它来移动那个箱子?
创建线程对象是一项 "native" 操作,该操作深入到底层操作系统以获取那里的资源。这可能是一个相当昂贵的操作。
意思是:只是抛出 "more threads" 问题并不会自动加快速度。从相反的方面来说。当您的任务主要是 CPU 密集型任务时,并行执行任务可能会带来很小的收益。当您进行大量 IO 时,拥有多个线程可以让您进行 "less" 整体等待;从而提高您的吞吐量。
换句话说:Fork/Join 需要大量的 activity 才能完成真正的工作。将它用于只需要几毫秒的计算简直是矫枉过正。因此:您会寻找 "fork/join" 可在更大数据集上运行的操作。
如需进一步阅读,您可以查看 parallel streams。那些在幕后使用 fork/join 框架;令人惊讶的是,期望任意 parallelStream
也比普通流 "faster" 是一种误解。
这有多个方面:
同一个问题的串行(例如普通递归)和并行(例如forkjoin)解决方案有区别吗?
并行文件系统访问的范围是什么?
衡量绩效的陷阱是什么?
#1 的答案。是,有一点不同。并行性不适用于太小的问题。使用并行解决方案,您需要考虑以下开销:
- 创建和管理线程
- 从父线程向子线程传递信息
- 正在将结果从子线程返回到父线程
- 对共享数据结构的同步访问,
- 正在等待最慢/最后完成的子线程完成。
这些在实践中如何发挥作用取决于多种因素......包括问题的规模和并行性的机会。
#2 的答案(可能)不像您想象的那么多。典型的文件系统存储在具有磁盘旋转和磁盘磁头寻道等物理特性的磁盘驱动器上。这些通常会成为瓶颈,如果没有高端存储系统,并行性的余地不大。
#3 的答案是有很多陷阱。这些陷阱可能会导致非常误导(即无效)的性能结果......如果你不允许它们的话。最大的陷阱之一是 JVM 需要时间 "warm up";即加载 类、执行 JIT 编译、调整堆大小等。
适用于执行文件系统 I/O 的基准测试的另一个陷阱是,典型的 OS 会执行缓存磁盘块和文件/目录元数据等操作。因此,您第二次访问文件或目录时,它可能比第一次更快。
话虽如此,如果您有一个设计良好的高性能文件系统(例如保存在 SSD 上的 inode)和一个设计良好的应用程序,以及足够的内核,则可以通过以下方式实现非凡的文件系统扫描率并行性。 (例如,在 12 小时内检查 5 个十亿个文件的修改时间戳....)
阅读 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 更快。
生活中没有免费的东西。如果您必须将一个啤酒箱从您的汽车移动到您的公寓 - 哪个更快:手动将其运送到那里,或者先去棚屋,让手推车用它来移动那个箱子?
创建线程对象是一项 "native" 操作,该操作深入到底层操作系统以获取那里的资源。这可能是一个相当昂贵的操作。
意思是:只是抛出 "more threads" 问题并不会自动加快速度。从相反的方面来说。当您的任务主要是 CPU 密集型任务时,并行执行任务可能会带来很小的收益。当您进行大量 IO 时,拥有多个线程可以让您进行 "less" 整体等待;从而提高您的吞吐量。
换句话说:Fork/Join 需要大量的 activity 才能完成真正的工作。将它用于只需要几毫秒的计算简直是矫枉过正。因此:您会寻找 "fork/join" 可在更大数据集上运行的操作。
如需进一步阅读,您可以查看 parallel streams。那些在幕后使用 fork/join 框架;令人惊讶的是,期望任意 parallelStream
也比普通流 "faster" 是一种误解。
这有多个方面:
同一个问题的串行(例如普通递归)和并行(例如forkjoin)解决方案有区别吗?
并行文件系统访问的范围是什么?
衡量绩效的陷阱是什么?
#1 的答案。是,有一点不同。并行性不适用于太小的问题。使用并行解决方案,您需要考虑以下开销:
- 创建和管理线程
- 从父线程向子线程传递信息
- 正在将结果从子线程返回到父线程
- 对共享数据结构的同步访问,
- 正在等待最慢/最后完成的子线程完成。
这些在实践中如何发挥作用取决于多种因素......包括问题的规模和并行性的机会。
#2 的答案(可能)不像您想象的那么多。典型的文件系统存储在具有磁盘旋转和磁盘磁头寻道等物理特性的磁盘驱动器上。这些通常会成为瓶颈,如果没有高端存储系统,并行性的余地不大。
#3 的答案是有很多陷阱。这些陷阱可能会导致非常误导(即无效)的性能结果......如果你不允许它们的话。最大的陷阱之一是 JVM 需要时间 "warm up";即加载 类、执行 JIT 编译、调整堆大小等。
适用于执行文件系统 I/O 的基准测试的另一个陷阱是,典型的 OS 会执行缓存磁盘块和文件/目录元数据等操作。因此,您第二次访问文件或目录时,它可能比第一次更快。
话虽如此,如果您有一个设计良好的高性能文件系统(例如保存在 SSD 上的 inode)和一个设计良好的应用程序,以及足够的内核,则可以通过以下方式实现非凡的文件系统扫描率并行性。 (例如,在 12 小时内检查 5 个十亿个文件的修改时间戳....)