ForkJoinPool vs. Simple Recursion
After reading ForkJoinPool , I tried an experiment to test how fast it actually is ForkJoinPool
, compared to simple recursion.
I calculated the number of files in a folder recursively, and for my surprise, a simple recursion is better than ForkJoinPool
Here is my code.
Recursive task
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;
}
}
Regular recursion
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();
}
Directory object
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);
}
}
results
- Regular recursion: 3ms
- ForkJoinPool: 25ms
Where is the error here?
I'm just trying to figure out if there is a certain threshold below which simple recursion is faster than ForkJoinPool.
source to share
Nothing in life comes for free. If you had to move one beer crate from your car to your apartment - which is faster: carry it by hand, or head to the barn first so the wheelbarrow uses it to move that crate?
Stream object creation is a native operation that goes into the host operating system to get resources there. This can be quite costly.
Meaning: just throwing "more threads" into the problem doesn't automatically speed things up. Otherwise. When your task is primarily CPU dependent, there may be a small gain from parallel activities. When you are doing a lot of I / O, having multiple threads allows you to do "less" waiting overall; thereby improving your bandwidth.
In other words: Fork / Join requires significant activity before it does the real work. Using it for computations that only require a few ms is simply overkill. Thus: you will be looking for fork / join operations that operate on large datasets.
For further reading, you can take a look at parallel streams . They use the fork / join framework under the covers; and the surprise is, it is a misconception to expect arbitrary to parallelStream
be "faster" than regular streams.
source to share
There are several aspects:
-
Is there a difference between sequential (like simple recursion) and parallel (like forkjoin) solutions to the same problem?
-
What is the scope of file system access?
-
What are the pitfalls for measuring performance?
Answer to # 1. Yes, there is a difference. Parallelism is not good for too little problem. With a parallel solution, you need to consider the overhead:
- creating and managing streams
- passing information from parent thread to child threads
- returns the results of child threads to the parent thread
- synchronized access to common data structures,
- waiting for the slowest / last terminating child thread to finish.
How this happens in practice depends on a lot of things ... including the size of the problem and the potential for parallelism.
The answer to # 2 is (perhaps) not as strong as you might think. A typical file system is stored on a disk, which has physical characteristics such as disk rotation and disk head search. They usually become a bottleneck, and the less high-quality storage you have, the less opportunities for parallelism.
The answer to # 3 is that there are many traps. And these pitfalls can lead to very misleading (i.e. invalid) performance results ... if you don't allow them. One of the biggest pitfalls is that JVMs take time to warm up; i.e. load classes, JIT compile, resize heap, etc.
Another pitfall that applies to benchmarks that do file system I / O is that the normal OS will do things like caching disk blocks and file / directory metadata. So the second time you access a file or directory, it will most likely be faster than the first time.
Having said that, if you have a well thought out high performance filesystem (like inodes stored on an SSD) and a well designed application and enough cores, you can achieve extraordinary file system scan speeds through parallelism. (For example, checking change timestamps on half a billion files in less than 12 hours ....)
source to share