Traversing many files in Java with minimal memory usage

Question

I need to traverse a directory hierarchy containing about 20 million files in Java. Currently I'm using FileUtils.iterateFiles from Apache Commons-IO. This seems to work by loading the whole list into memory, which is slow (delaying the application startup time) and a huge memory hog (around 8GB). I was previously using my own recursive file iterator which had the same problem.

I only need to process one file at a time (or, down the track, a handful from the front of the list in parallel), so it seems a little unnecessary to waste all this time and memory loading a complete list into memory.

Java's Iterator class allows for minimal-memory footprint iterators of the kind that I need, but since the native features of the java.io.File class only provide eagerly-initialized arrays, it seems to be bizarrely difficult to take advantage of these.

Does anyone have any suggestions for how I can traverse the file hierarchy without loading it all into memory in advance?

Thanks to this answer I'm now aware of the new Java 7 file API, which I think would solve my problem, but Java 7 is not really an option for me at this stage.

Answer 1

Since Java 7 NIO is not an option, you could execute "dir /B /A-D" (for Windows) and read file names from the output. If need be you could redirect the output to a temp file and read file names from there.

Answer 2

I know it's not strictly the answer to your question, but can you not reorganize the directory tree to use more levels of directories, so that each directory contains fewer files?

Answer 3

OK, I've ended up implementing my own iterator to do this (as Amir suggested). It wasn't exactly trivial (although fortunately someone already wrote code to flatten iterators), but is reasonably straightforward

It still holds a complete listing of a single directory (without descendants) in memory, so it's no use for a flat directory layout (in that case I think you're out of luck using pure Java until Java 7) but so far it's working much better for my use case.

RecursiveFileIterable.java:

import java.io.File;
import java.io.FileFilter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Iterator;
import java.util.List;

public class RecursiveFileIterable implements Iterable<File> {
    private File file;

    public RecursiveFileIterable(File f) {
        file = f;
    }

    public RecursiveFileIterable(String filename) {
        this(new File(filename));
    }

    private class DirectoriesOnlyFilter implements FileFilter {
        @Override
        public boolean accept(File pathname) {
            return pathname.isDirectory();
        }

    }

    private class NoDirectoriesFilter implements FileFilter {
        @Override
        public boolean accept(File pathname) {
            return !pathname.isDirectory();
        }
    }

    @Override
    public Iterator<File> iterator() {
        List<File> normFiles = Arrays.asList(file
                .listFiles(new NoDirectoriesFilter()));
        ArrayList<Iterable<File>> pendingIterables = new ArrayList<Iterable<File>>();
        pendingIterables.add(normFiles);

        File[] subdirs = file.listFiles(new DirectoriesOnlyFilter());
        for (File sd : subdirs)
            pendingIterables.add(new RecursiveFileIterable(sd));

        return new FlattenIterable<File>(pendingIterables).iterator();

    }

}

FlattenIterable.java:

// from http://langexplr.blogspot.com.au/2007/12/combining-iterators-in-java.html

import java.util.Iterator;

public class FlattenIterable<T> implements Iterable<T> {
    private Iterable<Iterable<T>> iterable;

    public FlattenIterable(Iterable<Iterable<T>> iterable) {
        this.iterable = iterable;
    }

    public Iterator<T> iterator() {
        return new FlattenIterator<T>(iterable.iterator());
    }

    static class FlattenIterator<T> implements Iterator<T> {
        private Iterator<Iterable<T>> iterator;
        private Iterator<T> currentIterator;

        public FlattenIterator(Iterator<Iterable<T>> iterator) {
            this.iterator = iterator;
            currentIterator = null;
        }

        public boolean hasNext() {
            boolean hasNext = true;
            if (currentIterator == null) {
                if (iterator.hasNext()) {
                    currentIterator = iterator.next().iterator();
                } else {
                    return false;
                }
            }

            while (!currentIterator.hasNext() && iterator.hasNext()) {
                currentIterator = iterator.next().iterator();
            }

            return currentIterator.hasNext();
        }

        public T next() {
            return currentIterator.next();
        }

        public void remove() {
        }
    }
}