Support --num-threads with --multi-dex

The current dx implementation supports options --multi-dex, for applications
not fitting within the dex format limitations; and --num-threads=N, triggers
concurrent processing of multiple input files. However, the implementation
has the following limitations:

The --num-threads option is disabled when used together with --multi-dex.
The --num-threads option implements concurrency at the level of classpath
entries, and does nothing when the classes to be translated are specified
with a single classpath element (e.g. single jar output from Proguard).
The existing --num-threads implementation may produce indeterministic output.
The heuristic used by the --multi-dex option to determine when to rotate the
dex output file is overly conservative.

The primary objective of this change is:
Concurrent translation of classes, independently of input specification format.
Support --num-threads=N in both mono- and multi-dex mode.
Deterministic class output order.
Near optimal use of dex file format capacity.

This is accomplished by reorganizing the dx workflow in a pipeline of
concurrent phases.

read-class  | parse-class | translate-class | add-to-dex | convert-dex-to-byte[];
output-dex-files-or-jar

To manage dex file rotation (i.e. --multi-dex support), the parse-class and
add-to-dex phases are synchronized to prevent forwarding classes to the
translate-class phase if it could potentially result in breaking the dex
format limitations. The heuristic currently used to estimate the number of
indices needed for a class is improved, to minimize the amount of serialization
imposed by this feedback mechanism, and to improve the use of dex file capacity.

The translate-class and convert-dex-to-byte[] phases are further parallelized
with configurable (--num-threads=N option) thread pools. This allow translating
classes concurrently, while also performing output conversion in parallel.
Separate collector threads are used to collect results from the thread pools
in deterministic order.

Testing was performed on an Ubuntu system, with 6 cores and 12 hardware threads.
The taskset command was used to experimentally establish that running with more
than 8 hardware threads does not provide any additional benefit.

Experiments shows that the argument to --num-threads should not exceed the
lesser of the number of available hardware threads, and 5. Setting it to a
higher value results in no additional benefit.

The gain is generally larger for larger applications, and not significant for
small applications with less than a few thousands classes. Experiments with
generated classes shows that for large applications gains as high as 50% may
be possible.

For an existing real-life application with more than 11k classes, and requiring
2 dex files, a speed-up of 37% was achieved (--num-threads=5, 8 hardware
threads, 4g Java heap). A speedup of 31% was observed for another application
with ~7 classes.

For small applications, use of --num-threads=N>1 doesn’t provide significant
benefit. Running with --num-threads=1, the modified dx is slightly faster,
but no significant gain is observed unless the application requires multiple
dex files.

The one case where a significant regression may be observed is when using
--num-threads=N>1, with a single hardware thread. This is an inappropriate
configuration, even with the current implementation. However, because of
the limitations of the current implementation, such configurations may exist.
For instance, a configuration using both --multi-dex and --num-threads=5 will
currently generate a warning about using the two options together. With the
new implementation, the options can legitimately be used together, and could
result in an ~20% regression running on a single hardware thread.
Note: the current dx implementation, without --num-threads option, is already
approximately 50% slower  with 1 hardware thread, compared to running with 2
or more. With 2 hardware threads the implementations are practically at par
(a little better, or a little worse, depending on the application).

Testing:
Tested with 6 existing applications ranging in size from 1K - 12K classes.
Updated and tested with relevant existing unit tests (one test changed to
account for better dex rotation heuristic).
Added unit test to test deterministic output.
Added unit performance test. By default run script merely validates that
--multi-dex and --num-threads can be used together (fast). However, the test
is configurable to perform performance test, over sets of generated classes.

Change-Id: Ic2d11c422396e97171c2e6ceae9477113e261b8e
Signed-off-by: Peter Jensen <jensenp@google.com>

16 files changed, 656 insertions, 134 deletions

diff --git a/dx/src/com/android/dx/command/dexer/Main.java b/dx/src/com/android/dx/command/dexer/Main.java
index 06ffcedef..fb38d82ae 100644
--- a/dx/src/com/android/dx/command/dexer/Main.java
+++ b/dx/src/com/android/dx/command/dexer/Main.java
@@ -64,12 +64,14 @@ import java.util.List;
 import java.util.Map;
 import java.util.Set;
 import java.util.TreeMap;
+import java.util.concurrent.ArrayBlockingQueue;
 import java.util.concurrent.Callable;
 import java.util.concurrent.ExecutionException;
 import java.util.concurrent.ExecutorService;
 import java.util.concurrent.Executors;
 import java.util.concurrent.Future;
 import java.util.concurrent.ThreadFactory;
+import java.util.concurrent.ThreadPoolExecutor;
 import java.util.concurrent.TimeUnit;
 import java.util.concurrent.atomic.AtomicInteger;
 import java.util.jar.Attributes;
@@ -179,11 +181,39 @@ public class Main {
     /** Library .dex files to merge into the output .dex. */
     private static final List<byte[]> libraryDexBuffers = new ArrayList<byte[]>();
 
-    /** thread pool object used for multi-threaded file processing */
-    private static ExecutorService threadPool;
+    /** Thread pool object used for multi-thread class translation. */
+    private static ExecutorService classTranslatorPool;
 
-    /** used to handle Errors for multi-threaded file processing */
-    private static List<Future<Void>> parallelProcessorFutures;
+    /** Single thread executor, for collecting results of parallel translation,
+     * and adding classes to dex file in original input file order. */
+    private static ExecutorService classDefItemConsumer;
+
+    /** Futures for {@code classDefItemConsumer} tasks. */
+    private static List<Future<Boolean>> addToDexFutures =
+            new ArrayList<Future<Boolean>>();
+
+    /** Thread pool object used for multi-thread dex conversion (to byte array).
+     * Used in combination with multi-dex support, to allow outputing
+     * a completed dex file, in parallel with continuing processing. */
+    private static ExecutorService dexOutPool;
+
+    /** Futures for {@code dexOutPool} task. */
+    private static List<Future<byte[]>> dexOutputFutures =
+            new ArrayList<Future<byte[]>>();
+
+    /** Lock object used to to coordinate dex file rotation, and
+     * multi-threaded translation. */
+    private static Object dexRotationLock = new Object();
+
+    /** Record the number if method indices "reserved" for files
+     * committed to translation in the context of the current dex
+     * file, but not yet added. */
+    private static int maxMethodIdsInProcess = 0;
+
+    /** Record the number if field indices "reserved" for files
+     * committed to translation in the context of the current dex
+     * file, but not yet added. */
+    private static int maxFieldIdsInProcess = 0;
 
     /** true if any files are successfully processed */
     private static volatile boolean anyFilesProcessed;
@@ -290,7 +320,7 @@ public class Main {
         byte[] outArray = null;
 
         if (!outputDex.isEmpty() || (args.humanOutName != null)) {
-            outArray = writeDex();
+            outArray = writeDex(outputDex);
 
             if (outArray == null) {
                 return 2;
@@ -325,13 +355,14 @@ public class Main {
     private static int runMultiDex() throws IOException {
 
         assert !args.incremental;
-        assert args.numThreads == 1;
 
         if (args.mainDexListFile != null) {
             classesInMainDex = new HashSet<String>();
             readPathsFromFile(args.mainDexListFile, classesInMainDex);
         }
 
+        dexOutPool = Executors.newFixedThreadPool(args.numThreads);
+
         if (!processAllFiles()) {
             return 1;
         }
@@ -342,14 +373,31 @@ public class Main {
 
         if (outputDex != null) {
             // this array is null if no classes were defined
-            dexOutputArrays.add(writeDex());
+
+            dexOutputFutures.add(dexOutPool.submit(new DexWriter(outputDex)));
 
             // Effectively free up the (often massive) DexFile memory.
             outputDex = null;
         }
+        try {
+            dexOutPool.shutdown();
+            if (!dexOutPool.awaitTermination(600L, TimeUnit.SECONDS)) {
+                throw new RuntimeException("Timed out waiting for dex writer threads.");
+            }
 
-        if (args.jarOutput) {
+            for (Future<byte[]> f : dexOutputFutures) {
+                dexOutputArrays.add(f.get());
+            }
 
+        } catch (InterruptedException ex) {
+            dexOutPool.shutdownNow();
+            throw new RuntimeException("A dex writer thread has been interrupted.");
+        } catch (Exception e) {
+            dexOutPool.shutdownNow();
+            throw new RuntimeException("Unexpected exception in dex writer thread");
+        }
+
+        if (args.jarOutput) {
             for (int i = 0; i < dexOutputArrays.size(); i++) {
                 outputResources.put(getDexFileName(i),
                         dexOutputArrays.get(i));
@@ -369,7 +417,6 @@ public class Main {
                     closeOutput(out);
                 }
             }
-
         }
 
         return 0;
@@ -475,10 +522,14 @@ public class Main {
         anyFilesProcessed = false;
         String[] fileNames = args.fileNames;
 
-        if (args.numThreads > 1) {
-            threadPool = Executors.newFixedThreadPool(args.numThreads);
-            parallelProcessorFutures = new ArrayList<Future<Void>>();
-        }
+        // translate classes in parallel
+        classTranslatorPool = new ThreadPoolExecutor(args.numThreads,
+               args.numThreads, 0, TimeUnit.SECONDS,
+               new ArrayBlockingQueue<Runnable>(2 * args.numThreads, true),
+               new ThreadPoolExecutor.CallerRunsPolicy());
+        // collect translated and write to dex in order
+        classDefItemConsumer = Executors.newSingleThreadExecutor();
+
 
         try {
             if (args.mainDexListFile != null) {
@@ -491,13 +542,25 @@ public class Main {
                     processOne(fileNames[i], mainPassFilter);
                 }
 
-                if (dexOutputArrays.size() > 0) {
+                if (dexOutputFutures.size() > 0) {
                     throw new DexException("Too many classes in " + Arguments.MAIN_DEX_LIST_OPTION
                             + ", main dex capacity exceeded");
                 }
 
                 if (args.minimalMainDex) {
                     // start second pass directly in a secondary dex file.
+
+                    // Wait for classes in progress to complete
+                    synchronized(dexRotationLock) {
+                        while(maxMethodIdsInProcess > 0 || maxFieldIdsInProcess > 0) {
+                            try {
+                                dexRotationLock.wait();
+                            } catch(InterruptedException ex) {
+                                /* ignore */
+                            }
+                        }
+                    }
+
                     rotateDexFile();
                 }
 
@@ -518,35 +581,36 @@ public class Main {
              */
         }
 
-        if (args.numThreads > 1) {
-            try {
-                threadPool.shutdown();
-                if (!threadPool.awaitTermination(600L, TimeUnit.SECONDS)) {
-                    throw new RuntimeException("Timed out waiting for threads.");
-                }
-            } catch (InterruptedException ex) {
-                threadPool.shutdownNow();
-                throw new RuntimeException("A thread has been interrupted.");
-            }
+        try {
+            classTranslatorPool.shutdown();
+            classTranslatorPool.awaitTermination(600L, TimeUnit.SECONDS);
+            classDefItemConsumer.shutdown();
+            classDefItemConsumer.awaitTermination(600L, TimeUnit.SECONDS);
 
-            try {
-              for (Future<?> future : parallelProcessorFutures) {
-                future.get();
-              }
-            } catch (ExecutionException e) {
-                Throwable cause = e.getCause();
-                // All Exceptions should have been handled in the ParallelProcessor, only Errors
-                // should remain
-                if (cause instanceof Error) {
-                    throw (Error) e.getCause();
-                } else {
-                    throw new AssertionError(e.getCause());
+            for (Future<Boolean> f : addToDexFutures) {
+                try {
+                    f.get();
+                } catch(ExecutionException ex) {
+                    // Catch any previously uncaught exceptions from
+                    // class translation and adding to dex.
+                    int count = errors.incrementAndGet();
+                    if (count < 10) {
+                        DxConsole.err.println("Uncaught translation error: " + ex.getCause());
+                    } else {
+                        throw new InterruptedException("Too many errors");
+                    }
                 }
-            } catch (InterruptedException e) {
-              // If we're here, it means all threads have completed cleanly, so there should not be
-              // any InterruptedException
-              throw new AssertionError(e);
             }
+
+        } catch (InterruptedException ie) {
+            classTranslatorPool.shutdownNow();
+            classDefItemConsumer.shutdownNow();
+            throw new RuntimeException("Translation has been interrupted", ie);
+        } catch (Exception e) {
+            classTranslatorPool.shutdownNow();
+            classDefItemConsumer.shutdownNow();
+            e.printStackTrace(System.out);
+            throw new RuntimeException("Unexpected exception in translator thread.", e);
         }
 
         int errorNum = errors.get();
@@ -582,7 +646,11 @@ public class Main {
 
     private static void rotateDexFile() {
         if (outputDex != null) {
-            dexOutputArrays.add(writeDex());
+            if (dexOutPool != null) {
+                dexOutputFutures.add(dexOutPool.submit(new DexWriter(outputDex)));
+            } else {
+                dexOutputArrays.add(writeDex(outputDex));
+            }
         }
 
         createDexFile();
@@ -599,47 +667,16 @@ public class Main {
     private static void processOne(String pathname, FileNameFilter filter) {
         ClassPathOpener opener;
 
-        opener = new ClassPathOpener(pathname, false, filter,
-                new ClassPathOpener.Consumer() {
-
-            @Override
-            public boolean processFileBytes(String name, long lastModified, byte[] bytes) {
-                return Main.processFileBytes(name, lastModified, bytes);
-            }
+        opener = new ClassPathOpener(pathname, false, filter, new FileBytesConsumer());
 
-            @Override
-            public void onException(Exception ex) {
-                if (ex instanceof StopProcessing) {
-                    throw (StopProcessing) ex;
-                } else if (ex instanceof SimException) {
-                    DxConsole.err.println("\nEXCEPTION FROM SIMULATION:");
-                    DxConsole.err.println(ex.getMessage() + "\n");
-                    DxConsole.err.println(((SimException) ex).getContext());
-                } else {
-                    DxConsole.err.println("\nUNEXPECTED TOP-LEVEL EXCEPTION:");
-                    ex.printStackTrace(DxConsole.err);
-                }
-                errors.incrementAndGet();
-            }
-
-            @Override
-            public void onProcessArchiveStart(File file) {
-                if (args.verbose) {
-                    DxConsole.out.println("processing archive " + file +
-                            "...");
-                }
-            }
-        });
+        opener.process();
+    }
 
-        if (args.numThreads > 1) {
-            parallelProcessorFutures.add(threadPool.submit(new ParallelProcessor(opener)));
-        } else {
-            if (opener.process()) {
-                anyFilesProcessed = true;
-            }
-        }
+    private static void updateStatus(boolean res) {
+        anyFilesProcessed |= res;
     }
 
+
     /**
      * Processes one file, which may be either a class or a resource.
      *
@@ -648,6 +685,7 @@ public class Main {
      * @return whether processing was successful
      */
     private static boolean processFileBytes(String name, long lastModified, byte[] bytes) {
+
         boolean isClass = name.endsWith(".class");
         boolean isClassesDex = name.equals(DexFormat.DEX_IN_JAR_NAME);
         boolean keepResources = (outputResources != null);
@@ -702,42 +740,30 @@ public class Main {
             checkClassName(name);
         }
 
-        DirectClassFile cf =
-            new DirectClassFile(bytes, name, args.cfOptions.strictNameCheck);
+        try {
+            new DirectClassFileConsumer(name, bytes, null).call(
+                    new ClassParserTask(name, bytes).call());
+        } catch(Exception ex) {
+            throw new RuntimeException("Exception parsing classes", ex);
+        }
 
+        return true;
+    }
+
+
+    private static DirectClassFile parseClass(String name, byte[] bytes) {
+
+        DirectClassFile cf = new DirectClassFile(bytes, name,
+                args.cfOptions.strictNameCheck);
         cf.setAttributeFactory(StdAttributeFactory.THE_ONE);
-        cf.getMagic();
-
-        int numMethodIds = outputDex.getMethodIds().items().size();
-        int numFieldIds = outputDex.getFieldIds().items().size();
-        int constantPoolSize = cf.getConstantPool().size();
-
-        int maxMethodIdsInDex = numMethodIds + constantPoolSize + cf.getMethods().size() +
-                MAX_METHOD_ADDED_DURING_DEX_CREATION;
-        int maxFieldIdsInDex = numFieldIds + constantPoolSize + cf.getFields().size() +
-                MAX_FIELD_ADDED_DURING_DEX_CREATION;
-
-        if (args.multiDex
-            // Never switch to the next dex if current dex is already empty
-            && (outputDex.getClassDefs().items().size() > 0)
-            && ((maxMethodIdsInDex > args.maxNumberOfIdxPerDex) ||
-                (maxFieldIdsInDex > args.maxNumberOfIdxPerDex))) {
-            DexFile completeDex = outputDex;
-            rotateDexFile();
-            assert  (completeDex.getMethodIds().items().size() <= numMethodIds +
-                    MAX_METHOD_ADDED_DURING_DEX_CREATION) &&
-                    (completeDex.getFieldIds().items().size() <= numFieldIds +
-                    MAX_FIELD_ADDED_DURING_DEX_CREATION);
-        }
+        cf.getMagic(); // triggers the actual parsing
+        return cf;
+    }
 
+    private static ClassDefItem translateClass(byte[] bytes, DirectClassFile cf) {
         try {
-            ClassDefItem clazz =
-                CfTranslator.translate(cf, bytes, args.cfOptions, args.dexOptions, outputDex);
-            synchronized (outputDex) {
-                outputDex.add(clazz);
-            }
-            return true;
-
+            return CfTranslator.translate(cf, bytes, args.cfOptions,
+                    args.dexOptions, outputDex);
         } catch (ParseException ex) {
             DxConsole.err.println("\ntrouble processing:");
             if (args.debug) {
@@ -747,7 +773,14 @@ public class Main {
             }
         }
         errors.incrementAndGet();
-        return false;
+        return null;
+    }
+
+    private static boolean addClassToDex(ClassDefItem clazz) {
+        synchronized (outputDex) {
+            outputDex.add(clazz);
+        }
+        return true;
     }
 
     /**
@@ -797,7 +830,7 @@ public class Main {
      * @return {@code null-ok;} the converted {@code byte[]} or {@code null}
      * if there was a problem
      */
-    private static byte[] writeDex() {
+    private static byte[] writeDex(DexFile outputDex) {
         byte[] outArray = null;
 
         try {
@@ -836,7 +869,6 @@ public class Main {
             }
             return null;
         }
-
         return outArray;
     }
 
@@ -1552,12 +1584,6 @@ public class Main {
                 throw new UsageException();
             }
 
-            if (multiDex && numThreads != 1) {
-                System.out.println(NUM_THREADS_OPTION + " is ignored when used with "
-                    + MULTI_DEX_OPTION);
-                numThreads = 1;
-            }
-
             if (multiDex && incremental) {
                 System.err.println(INCREMENTAL_OPTION + " is not supported with "
                     + MULTI_DEX_OPTION);
@@ -1602,21 +1628,260 @@ public class Main {
         }
     }
 
-    /** Callable helper class to process files in multiple threads */
-    private static class ParallelProcessor implements Callable<Void> {
+    /**
+     * Callback class for processing input file bytes, produced by the
+     * ClassPathOpener.
+     */
+    private static class FileBytesConsumer implements ClassPathOpener.Consumer {
 
-        ClassPathOpener classPathOpener;
+        @Override
+        public boolean processFileBytes(String name, long lastModified,
+                byte[] bytes)   {
+            return Main.processFileBytes(name, lastModified, bytes);
+        }
 
-        private ParallelProcessor(ClassPathOpener classPathOpener) {
-            this.classPathOpener = classPathOpener;
+        @Override
+        public void onException(Exception ex) {
+            if (ex instanceof StopProcessing) {
+                throw (StopProcessing) ex;
+            } else if (ex instanceof SimException) {
+                DxConsole.err.println("\nEXCEPTION FROM SIMULATION:");
+                DxConsole.err.println(ex.getMessage() + "\n");
+                DxConsole.err.println(((SimException) ex).getContext());
+            } else {
+                DxConsole.err.println("\nUNEXPECTED TOP-LEVEL EXCEPTION:");
+                ex.printStackTrace(DxConsole.err);
+            }
+            errors.incrementAndGet();
         }
 
         @Override
-        public Void call() throws Exception {
-            if (classPathOpener.process()) {
-                anyFilesProcessed = true;
+        public void onProcessArchiveStart(File file) {
+            if (args.verbose) {
+                DxConsole.out.println("processing archive " + file + "...");
             }
-            return null;
+        }
+    }
+
+    /** Callable helper class to parse class bytes. */
+    private static class ClassParserTask implements Callable<DirectClassFile> {
+
+        String name;
+        byte[] bytes;
+
+        private ClassParserTask(String name, byte[] bytes) {
+            this.name = name;
+            this.bytes = bytes;
+        }
+
+        @Override
+        public DirectClassFile call() throws Exception {
+            DirectClassFile cf =  parseClass(name, bytes);
+
+            return cf;
+        }
+    }
+
+    /**
+     * Callable helper class used to sequentially collect the results of
+     * the (optionally parallel) translation phase, in correct input file order.
+     * This class is also responsible for coordinating dex file rotation
+     * with the ClassDefItemConsumer class.
+     * We maintain invariant that the number of indices used in the current
+     * dex file plus the max number of indices required by classes passed to
+     * the translation phase and not yet added to the dex file, is less than
+     * or equal to the dex file limit.
+     * For each parsed file, we estimate the maximum number of indices it may
+     * require. If passing the file to the translation phase would invalidate
+     * the invariant, we wait, until the next class is added to the dex file,
+     * and then reevaluate the invariant. If there are no further classes in
+     * the translation phase, we rotate the dex file.
+     */
+    private static class DirectClassFileConsumer implements Callable<Boolean> {
+
+        String name;
+        byte[] bytes;
+        Future<DirectClassFile> dcff;
+
+        private DirectClassFileConsumer(String name, byte[] bytes,
+                Future<DirectClassFile> dcff) {
+            this.name = name;
+            this.bytes = bytes;
+            this.dcff = dcff;
+        }
+
+        @Override
+        public Boolean call() throws Exception {
+
+            DirectClassFile cf = dcff.get();
+            return call(cf);
+        }
+
+        private Boolean call(DirectClassFile cf) {
+
+            int maxMethodIdsInClass = 0;
+            int maxFieldIdsInClass = 0;
+
+            if (args.multiDex) {
+
+                // Calculate max number of indices this class will add to the
+                // dex file.
+                // The constant pool contains at least one entry per method
+                // (name and signature), at least one entry per field (name
+                // and type), and at least per method/field reference (typed
+                // method ref).
+
+                int constantPoolSize = cf.getConstantPool().size();
+                maxMethodIdsInClass = constantPoolSize - cf.getFields().size()
+                        + MAX_METHOD_ADDED_DURING_DEX_CREATION;
+                maxFieldIdsInClass = constantPoolSize - cf.getMethods().size()
+                        + MAX_FIELD_ADDED_DURING_DEX_CREATION;
+                synchronized(dexRotationLock) {
+
+                    int numMethodIds;
+                    int numFieldIds;
+                    // Number of indices used in current dex file.
+                    synchronized(outputDex) {
+                        numMethodIds = outputDex.getMethodIds().items().size();
+                        numFieldIds = outputDex.getFieldIds().items().size();
+                    }
+                    // Wait until we're sure this class will fit in the current
+                    // dex file.
+                    while(((numMethodIds + maxMethodIdsInClass + maxMethodIdsInProcess
+                            > args.maxNumberOfIdxPerDex) ||
+                           (numFieldIds + maxFieldIdsInClass + maxFieldIdsInProcess
+                            > args.maxNumberOfIdxPerDex))) {
+
+                        if (maxMethodIdsInProcess > 0 || maxFieldIdsInProcess > 0) {
+                            // There are classes in the translation phase that
+                            // have not yet been added to the dex file, so we
+                            // wait for the next class to complete.
+                            try {
+                                dexRotationLock.wait();
+                            } catch(InterruptedException ex) {
+                                /* ignore */
+                            }
+                        } else if (outputDex.getClassDefs().items().size() > 0) {
+                            // There are no further classes in the translation
+                            // phase, and we have a full dex file. Rotate!
+                            rotateDexFile();
+                        } else {
+                            // The estimated number of indices is too large for
+                            // an empty dex file. We proceed hoping the actual
+                            // number of indices needed will fit.
+                            break;
+                        }
+                        synchronized(outputDex) {
+                            numMethodIds = outputDex.getMethodIds().items().size();
+                            numFieldIds = outputDex.getFieldIds().items().size();
+                        }
+                    }
+                    // Add our estimate to the total estimate for
+                    // classes under translation.
+                    maxMethodIdsInProcess += maxMethodIdsInClass;
+                    maxFieldIdsInProcess += maxFieldIdsInClass;
+                }
+            }
+
+            // Submit class to translation phase.
+            Future<ClassDefItem> cdif = classTranslatorPool.submit(
+                    new ClassTranslatorTask(name, bytes, cf));
+            Future<Boolean> res = classDefItemConsumer.submit(new ClassDefItemConsumer(
+                    name, cdif, maxMethodIdsInClass, maxFieldIdsInClass));
+            addToDexFutures.add(res);
+
+            return true;
+        }
+    }
+
+
+    /** Callable helper class to translate classes in parallel  */
+    private static class ClassTranslatorTask implements Callable<ClassDefItem> {
+
+        String name;
+        byte[] bytes;
+        DirectClassFile classFile;
+
+        private ClassTranslatorTask(String name, byte[] bytes,
+                DirectClassFile classFile) {
+            this.name = name;
+            this.bytes = bytes;
+            this.classFile = classFile;
+        }
+
+        @Override
+        public ClassDefItem call() {
+            ClassDefItem clazz = translateClass(bytes, classFile);
+            return clazz;
+        }
+    }
+
+    /**
+     * Callable helper class used to collect the results of
+     * the parallel translation phase, adding the translated classes to
+     * the current dex file in correct (deterministic) file order.
+     * This class is also responsible for coordinating dex file rotation
+     * with the DirectClassFileConsumer class.
+     */
+    private static class ClassDefItemConsumer implements Callable<Boolean> {
+
+        String name;
+        Future<ClassDefItem> futureClazz;
+        int maxMethodIdsInClass;
+        int maxFieldIdsInClass;
+
+        private ClassDefItemConsumer(String name, Future<ClassDefItem> futureClazz,
+                int maxMethodIdsInClass, int maxFieldIdsInClass) {
+            this.name = name;
+            this.futureClazz = futureClazz;
+            this.maxMethodIdsInClass = maxMethodIdsInClass;
+            this.maxFieldIdsInClass = maxFieldIdsInClass;
+        }
+
+        @Override
+        public Boolean call() throws Exception {
+            try {
+                ClassDefItem clazz = futureClazz.get();
+                if (clazz != null) {
+                    addClassToDex(clazz);
+                    updateStatus(true);
+                }
+                return true;
+            } catch(ExecutionException ex) {
+                // Rethrow previously uncaught translation exceptions.
+                // These, as well as any exceptions from addClassToDex,
+                // are handled and reported in processAllFiles().
+                Throwable t = ex.getCause();
+                throw (t instanceof Exception) ? (Exception) t : ex;
+            } finally {
+                if (args.multiDex) {
+                    // Having added our actual indicies to the dex file,
+                    // we subtract our original estimate from the total estimate,
+                    // and signal the translation phase, which may be paused
+                    // waiting to determine if more classes can be added to the
+                    // current dex file, or if a new dex file must be created.
+                    synchronized(dexRotationLock) {
+                        maxMethodIdsInProcess -= maxMethodIdsInClass;
+                        maxFieldIdsInProcess -= maxFieldIdsInClass;
+                        dexRotationLock.notifyAll();
+                    }
+                }
+            }
+        }
+    }
+
+    /** Callable helper class to convert dex files in worker threads */
+    private static class DexWriter implements Callable<byte[]> {
+
+        private DexFile dexFile;
+
+        private DexWriter(DexFile dexFile) {
+            this.dexFile = dexFile;
+        }
+
+        @Override
+        public byte[] call() throws IOException {
+            return writeDex(dexFile);
         }
     }
 }
diff --git a/dx/src/com/android/dx/dex/file/MixedItemSection.java b/dx/src/com/android/dx/dex/file/MixedItemSection.java
index 4edc6b62f..9053043f9 100644
--- a/dx/src/com/android/dx/dex/file/MixedItemSection.java
+++ b/dx/src/com/android/dx/dex/file/MixedItemSection.java
@@ -189,7 +189,7 @@ public final class MixedItemSection extends Section {
      * @param item {@code non-null;} the item to intern
      * @return {@code non-null;} the equivalent interned instance
      */
-    public <T extends OffsettedItem> T intern(T item) {
+    public synchronized <T extends OffsettedItem> T intern(T item) {
         throwIfPrepared();
 
         OffsettedItem result = interns.get(item);
diff --git a/dx/src/com/android/dx/dex/file/ProtoIdsSection.java b/dx/src/com/android/dx/dex/file/ProtoIdsSection.java
index 4b1303b15..b7df10cdd 100644
--- a/dx/src/com/android/dx/dex/file/ProtoIdsSection.java
+++ b/dx/src/com/android/dx/dex/file/ProtoIdsSection.java
@@ -86,7 +86,7 @@ public final class ProtoIdsSection extends UniformItemSection {
      * @param prototype {@code non-null;} the prototype to intern
      * @return {@code non-null;} the interned reference
      */
-    public ProtoIdItem intern(Prototype prototype) {
+    public synchronized ProtoIdItem intern(Prototype prototype) {
         if (prototype == null) {
             throw new NullPointerException("prototype == null");
         }
diff --git a/dx/src/com/android/dx/dex/file/StringIdsSection.java b/dx/src/com/android/dx/dex/file/StringIdsSection.java
index 7aff82ea9..6826c5a48 100644
--- a/dx/src/com/android/dx/dex/file/StringIdsSection.java
+++ b/dx/src/com/android/dx/dex/file/StringIdsSection.java
@@ -117,7 +117,7 @@ public final class StringIdsSection
      * @param string {@code non-null;} the string to intern
      * @return {@code non-null;} the interned string
      */
-    public StringIdItem intern(StringIdItem string) {
+    public synchronized StringIdItem intern(StringIdItem string) {
         if (string == null) {
             throw new NullPointerException("string == null");
         }
@@ -140,7 +140,7 @@ public final class StringIdsSection
      *
      * @param nat {@code non-null;} the name-and-type
      */
-    public void intern(CstNat nat) {
+    public synchronized void intern(CstNat nat) {
         intern(nat.getName());
         intern(nat.getDescriptor());
     }
diff --git a/dx/src/com/android/dx/dex/file/TypeIdsSection.java b/dx/src/com/android/dx/dex/file/TypeIdsSection.java
index c3380f4b8..35d8e661a 100644
--- a/dx/src/com/android/dx/dex/file/TypeIdsSection.java
+++ b/dx/src/com/android/dx/dex/file/TypeIdsSection.java
@@ -106,7 +106,7 @@ public final class TypeIdsSection extends UniformItemSection {
      * @param type {@code non-null;} the type to intern
      * @return {@code non-null;} the interned reference
      */
-    public TypeIdItem intern(Type type) {
+    public synchronized TypeIdItem intern(Type type) {
         if (type == null) {
             throw new NullPointerException("type == null");
         }
diff --git a/dx/tests/128-multidex-option-overflow/expected.txt b/dx/tests/128-multidex-option-overflow/expected.txt
index 3d7a649b8..ac448a63d 100644
--- a/dx/tests/128-multidex-option-overflow/expected.txt
+++ b/dx/tests/128-multidex-option-overflow/expected.txt
@@ -1,3 +1,2 @@
 classes2.dex
-classes3.dex
 classes.dex
diff --git a/dx/tests/129-numthread-deterministic/expected.txt b/dx/tests/129-numthread-deterministic/expected.txt
new file mode 100644
index 000000000..54183385d
--- /dev/null
+++ b/dx/tests/129-numthread-deterministic/expected.txt
@@ -0,0 +1 @@
+Yay!
diff --git a/dx/tests/129-numthread-deterministic/info.txt b/dx/tests/129-numthread-deterministic/info.txt
new file mode 100644
index 000000000..e4885fab3
--- /dev/null
+++ b/dx/tests/129-numthread-deterministic/info.txt
@@ -0,0 +1,2 @@
+Test that dx generates deterministic output when using --num-threads
+
diff --git a/dx/tests/129-numthread-deterministic/run b/dx/tests/129-numthread-deterministic/run
new file mode 100644
index 000000000..fdc050649
--- /dev/null
+++ b/dx/tests/129-numthread-deterministic/run
@@ -0,0 +1,54 @@
+#!/bin/bash
+#
+# Copyright (C) 2013 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# Stop if something fails.
+set -e
+
+# Write out classes
+mkdir src
+awk '
+BEGIN {
+    for (c = 1; c <= 500; c++) {
+        writeClass(c);
+    }
+}
+function writeClass(name) {
+    fileName = "src/Clazz" name ".java";
+    printf("public class Clazz%s {\n", name) > fileName;
+    for (i = 1; i <= 100; i++) {
+        printf("    int field%d;\n", i) > fileName;
+    }
+    for (i = 1; i <= 100; i++) {
+        printf("    void method%d(int param) { }\n", i) > fileName;
+    }
+    printf("}\n") > fileName;
+}'
+
+
+mkdir classes
+${JAVAC} -d classes `find src -name '*.java'`
+mkdir out
+dx -JXmx4g -JXms4g --dex --no-optimize --output=out classes
+mkdir out-multi
+dx -JXmx4g -JXms4g --dex --no-optimize --num-threads=4 --output=out-multi classes
+diff -r out out-multi > unit-out.txt
+
+if [ "$?" = "0" ]; then
+    echo "Yay!"
+else
+    cat unit-out.txt
+fi
+
diff --git a/dx/tests/130-numthread-multidex-deterministic/expected.txt b/dx/tests/130-numthread-multidex-deterministic/expected.txt
new file mode 100644
index 000000000..54183385d
--- /dev/null
+++ b/dx/tests/130-numthread-multidex-deterministic/expected.txt
@@ -0,0 +1 @@
+Yay!
diff --git a/dx/tests/130-numthread-multidex-deterministic/info.txt b/dx/tests/130-numthread-multidex-deterministic/info.txt
new file mode 100644
index 000000000..e4885fab3
--- /dev/null
+++ b/dx/tests/130-numthread-multidex-deterministic/info.txt
@@ -0,0 +1,2 @@
+Test that dx generates deterministic output when using --num-threads
+
diff --git a/dx/tests/130-numthread-multidex-deterministic/run b/dx/tests/130-numthread-multidex-deterministic/run
new file mode 100644
index 000000000..b43ba1f54
--- /dev/null
+++ b/dx/tests/130-numthread-multidex-deterministic/run
@@ -0,0 +1,54 @@
+#!/bin/bash
+#
+# Copyright (C) 2013 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# Stop if something fails.
+set -e
+
+# Write out classes
+mkdir src
+awk '
+BEGIN {
+    for (c = 1; c <= 1000; c++) {
+        writeClass(c);
+    }
+}
+function writeClass(name) {
+    fileName = "src/Clazz" name ".java";
+    printf("public class Clazz%s {\n", name) > fileName;
+    for (i = 1; i <= 100; i++) {
+        printf("    int field%d;\n", i) > fileName;
+    }
+    for (i = 1; i <= 100; i++) {
+        printf("    void method%d(int param) { }\n", i) > fileName;
+    }
+    printf("}\n") > fileName;
+}'
+
+
+mkdir classes
+${JAVAC} -d classes `find src -name '*.java'`
+mkdir out
+dx -JXmx4g -JXms4g --dex --no-optimize --multi-dex --output=out classes
+mkdir out-multi
+dx -JXmx4g -JXms4g --dex --no-optimize --multi-dex --num-threads=4 --output=out-multi classes
+diff -r out out-multi > unit-out.txt
+
+if [ "$?" = "0" ]; then
+    echo "Yay!"
+else
+    cat unit-out.txt
+fi
+
diff --git a/dx/tests/131-perf/ClassGen.java b/dx/tests/131-perf/ClassGen.java
new file mode 100644
index 000000000..c35bbcf82
--- /dev/null
+++ b/dx/tests/131-perf/ClassGen.java
@@ -0,0 +1,53 @@
+import java.io.File;
+import java.io.PrintWriter;
+
+public class ClassGen {
+
+    public static void main(String... args) {
+
+	int start = 1;
+        int end =   8024;
+	int fields =   4;
+        int methods =   6;
+	if (args.length > 0) {
+	    start = Integer.parseInt(args[0]);
+        }
+	if (args.length > 1) {
+	    end = Integer.parseInt(args[1]);
+        }
+	if (args.length > 2) {
+	    fields = Integer.parseInt(args[2]);
+        }
+	if (args.length > 3) {
+	    methods = Integer.parseInt(args[3]);
+        }
+
+	for (int file = start; file <= end; file++) {
+            try {
+	        File f = new File("src/Clazz" + file + ".java");
+	        PrintWriter pw = new PrintWriter(f);
+		pw.println("class Clazz" + file + " {");
+		for (int field = 1; field <= fields; field++) {
+		    pw.println("    public static int f" + field + ";");
+		}
+		for (int method = 1; method <= methods; method++) {
+		    pw.println("    boolean m" + method + "_" + (file%(end/2)) + "() {"
+);
+		    pw.println("      int max = Thread.MAX_PRIORITY;");
+		    pw.println("      for (int i = 0; i < max; i++) {");
+		    pw.println("        System.out.println(\"Hello from: \" + Clazz"
+                            + file + ".class + \".method" + method
+                            + "() \" + Clazz" + (end-file+1) + ".f1);");
+		    pw.println("        Thread.dumpStack();");
+		    pw.println("      }");
+		    pw.println("      return Thread.holdsLock(this);");
+		    pw.println("    }");
+		}
+		pw.println("}");
+                pw.close();
+            } catch(Exception ex) {
+		System.out.println("Ups");
+            }
+        }
+    }
+}
diff --git a/dx/tests/131-perf/expected.txt b/dx/tests/131-perf/expected.txt
new file mode 100644
index 000000000..54183385d
--- /dev/null
+++ b/dx/tests/131-perf/expected.txt
@@ -0,0 +1 @@
+Yay!
diff --git a/dx/tests/131-perf/info.txt b/dx/tests/131-perf/info.txt
new file mode 100644
index 000000000..f5b6a0cee
--- /dev/null
+++ b/dx/tests/131-perf/info.txt
@@ -0,0 +1,2 @@
+Script for --multi-dex --num-threads performance testing, default just test options can be used together
+
diff --git a/dx/tests/131-perf/run b/dx/tests/131-perf/run
new file mode 100644
index 000000000..e57545c03
--- /dev/null
+++ b/dx/tests/131-perf/run
@@ -0,0 +1,88 @@
+#!/bin/bash
+#
+# Copyright (C) 2013 The Android Open Source Project
+#
+# Licensed under the Apache License, Version 2.0 (the "License");
+# you may not use this file except in compliance with the License.
+# You may obtain a copy of the License at
+#
+#     http://www.apache.org/licenses/LICENSE-2.0
+#
+# Unless required by applicable law or agreed to in writing, software
+# distributed under the License is distributed on an "AS IS" BASIS,
+# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+# See the License for the specific language governing permissions and
+# limitations under the License.
+
+# Stop if something fails.
+set -e
+
+# Write out classes
+
+${JAVAC} ClassGen.java
+
+mkdir src
+mkdir classes
+
+# Heap size, min and max
+MEM=4g
+
+MULTIDEX="--multi-dex"
+THREADS="--num-threads=5"
+
+# Extra statistics, use to calibrate test.
+#EXTRA="--profile-concurrency"
+
+# Test smaller dex files
+#EXTRA="--set-max-idx-number=20000"
+
+# Test GC options
+#GC="-JXX:+UseConcMarkSweepGC"
+
+# Limit HW threads
+#TASKSET="taskset 0x00000fff
+
+# Number of classes, initial
+TEST_SIZE=1000
+
+# number of classes, max
+LIMIT=1000
+
+# Number of additional classes per test
+STEP=100
+
+# Number of fields per classes
+FIELDS=4
+
+# Number of methods per class
+METHODS=6
+
+
+first=1;
+while [ $TEST_SIZE -le $LIMIT ]; do
+  rm -rf out
+  mkdir out
+
+  sleep 2
+  java -classpath . ClassGen $first $TEST_SIZE $FIELDS $METHODS
+  first=`expr $TEST_SIZE + 1`
+
+  ${JAVAC} -d classes `find src -name '*.java'`
+  (cd classes; jar cf ../x.jar `find . -name '*.class'`)
+  sleep 3
+
+  start=`date +'%s%N'`
+  $TASKSET dx -JXmx$MEM -JXms$MEM $GC --dex $EXTRA --no-optimize $MULTIDEX $THREADS --output=out x.jar
+  end=`date +'%s%N'`
+  nsec=`expr $end - $start`
+  msec=`expr $nsec / 1000000`
+  echo "Classes/msec $TEST_SIZE $msec"
+
+  TEST_SIZE=`expr $TEST_SIZE + $STEP`
+done
+
+if [ "$?" = "1" ]; then
+    echo "Yay!"
+else
+    cat unit-out.txt
+fi