Shard dedupe set locks.

We're seeing contention during compilation on the dedupe locks, sharding 4 ways
on an occam brings down contention by > 5x.
Improve dedupe hash function to have a FNV hash function at its heart.
Improve naming of dedupe locks.
Tidy portable JNI compiler paramters to be pointers, given that's their primary
use.

Change-Id: I95d905f2ca5fee4e83a0034926a5f6501b4aeb79

7 files changed, 65 insertions, 46 deletions

diff --git a/compiler/driver/compiler_driver.cc b/compiler/driver/compiler_driver.cc
index 31aec63b02..495458efab 100644
--- a/compiler/driver/compiler_driver.cc
+++ b/compiler/driver/compiler_driver.cc
@@ -355,7 +355,11 @@ CompilerDriver::CompilerDriver(CompilerBackend compiler_backend, InstructionSet
       jni_compiler_(NULL),
       compiler_enable_auto_elf_loading_(NULL),
       compiler_get_method_code_addr_(NULL),
-      support_boot_image_fixup_(true) {
+      support_boot_image_fixup_(true),
+      dedupe_code_("dedupe code"),
+      dedupe_mapping_table_("dedupe mapping table"),
+      dedupe_vmap_table_("dedupe vmap table"),
+      dedupe_gc_map_("dedupe gc map") {
 
   CHECK_PTHREAD_CALL(pthread_key_create, (&tls_key_, NULL), "compiler tls key");
 
diff --git a/compiler/driver/compiler_driver.h b/compiler/driver/compiler_driver.h
index cd6b5fab02..c5c53e387d 100644
--- a/compiler/driver/compiler_driver.h
+++ b/compiler/driver/compiler_driver.h
@@ -449,27 +449,39 @@ class CompilerDriver {
   class DedupeHashFunc {
    public:
     size_t operator()(const std::vector<uint8_t>& array) const {
-      // Take a random sample of bytes.
+      // For small arrays compute a hash using every byte.
       static const size_t kSmallArrayThreshold = 16;
-      static const size_t kRandomHashCount = 16;
-      size_t hash = 0;
-      if (array.size() < kSmallArrayThreshold) {
-        for (auto c : array) {
-          hash = hash * 54 + c;
+      size_t hash = 0x811c9dc5;
+      if (array.size() <= kSmallArrayThreshold) {
+        for (uint8_t b : array) {
+          hash = (hash * 16777619) ^ b;
         }
       } else {
-        for (size_t i = 0; i < kRandomHashCount; ++i) {
+        // For larger arrays use the first 4 bytes and then select a number of other values at
+        // random.
+        static const size_t kRandomHashCount = 16;
+        for (size_t i = 0; i < 4; ++i) {
+          uint8_t b = array[i];
+          hash = (hash * 16777619) ^ b;
+        }
+        for (size_t i = 4; i < kRandomHashCount; ++i) {
           size_t r = i * 1103515245 + 12345;
-          hash = hash * 54 + array[r % array.size()];
+          uint8_t b = array[r % array.size()];
+          hash = (hash * 16777619) ^ b;
         }
       }
+      hash += hash << 13;
+      hash ^= hash >> 7;
+      hash += hash << 3;
+      hash ^= hash >> 17;
+      hash += hash << 5;
       return hash;
     }
   };
-  DedupeSet<std::vector<uint8_t>, size_t, DedupeHashFunc> dedupe_code_;
-  DedupeSet<std::vector<uint8_t>, size_t, DedupeHashFunc> dedupe_mapping_table_;
-  DedupeSet<std::vector<uint8_t>, size_t, DedupeHashFunc> dedupe_vmap_table_;
-  DedupeSet<std::vector<uint8_t>, size_t, DedupeHashFunc> dedupe_gc_map_;
+  DedupeSet<std::vector<uint8_t>, size_t, DedupeHashFunc, 4> dedupe_code_;
+  DedupeSet<std::vector<uint8_t>, size_t, DedupeHashFunc, 4> dedupe_mapping_table_;
+  DedupeSet<std::vector<uint8_t>, size_t, DedupeHashFunc, 4> dedupe_vmap_table_;
+  DedupeSet<std::vector<uint8_t>, size_t, DedupeHashFunc, 4> dedupe_gc_map_;
 
   DISALLOW_COPY_AND_ASSIGN(CompilerDriver);
 };
diff --git a/compiler/jni/portable/jni_compiler.cc b/compiler/jni/portable/jni_compiler.cc
index 43408a7d64..0c14346ad8 100644
--- a/compiler/jni/portable/jni_compiler.cc
+++ b/compiler/jni/portable/jni_compiler.cc
@@ -50,9 +50,9 @@ using ::art::llvm::runtime_support::JniMethodStartSynchronized;
 using ::art::llvm::runtime_support::RuntimeId;
 
 JniCompiler::JniCompiler(LlvmCompilationUnit* cunit,
-                         CompilerDriver& driver,
+                         CompilerDriver* driver,
                          const DexCompilationUnit* dex_compilation_unit)
-    : cunit_(cunit), driver_(&driver), module_(cunit_->GetModule()),
+    : cunit_(cunit), driver_(driver), module_(cunit_->GetModule()),
       context_(cunit_->GetLLVMContext()), irb_(*cunit_->GetIRBuilder()),
       dex_compilation_unit_(dex_compilation_unit),
       func_(NULL), elf_func_idx_(0) {
diff --git a/compiler/jni/portable/jni_compiler.h b/compiler/jni/portable/jni_compiler.h
index d20c63bc1e..ffabfe61c2 100644
--- a/compiler/jni/portable/jni_compiler.h
+++ b/compiler/jni/portable/jni_compiler.h
@@ -54,7 +54,7 @@ class IRBuilder;
 class JniCompiler {
  public:
   JniCompiler(LlvmCompilationUnit* cunit,
-              CompilerDriver& driver,
+              CompilerDriver* driver,
               const DexCompilationUnit* dex_compilation_unit);
 
   CompiledMethod* Compile();
@@ -67,7 +67,7 @@ class JniCompiler {
 
  private:
   LlvmCompilationUnit* cunit_;
-  CompilerDriver* driver_;
+  CompilerDriver* const driver_;
 
   ::llvm::Module* module_;
   ::llvm::LLVMContext* context_;
diff --git a/compiler/llvm/compiler_llvm.cc b/compiler/llvm/compiler_llvm.cc
index fd440d5bf0..83b0c75e04 100644
--- a/compiler/llvm/compiler_llvm.cc
+++ b/compiler/llvm/compiler_llvm.cc
@@ -164,7 +164,7 @@ CompileNativeMethod(DexCompilationUnit* dex_compilation_unit) {
   UniquePtr<LlvmCompilationUnit> cunit(AllocateCompilationUnit());
 
   UniquePtr<JniCompiler> jni_compiler(
-      new JniCompiler(cunit.get(), *compiler_driver_, dex_compilation_unit));
+      new JniCompiler(cunit.get(), compiler_driver_, dex_compilation_unit));
 
   return jni_compiler->Compile();
 }
diff --git a/compiler/utils/dedupe_set.h b/compiler/utils/dedupe_set.h
index f3d35d728c..53c1afa698 100644
--- a/compiler/utils/dedupe_set.h
+++ b/compiler/utils/dedupe_set.h
@@ -18,62 +18,65 @@
 #define ART_COMPILER_UTILS_DEDUPE_SET_H_
 
 #include <set>
+#include <string>
 
 #include "base/mutex.h"
 #include "base/stl_util.h"
 
 namespace art {
 
-// A simple data structure to handle hashed deduplication. Add is thread safe.
-template <typename Key, typename HashType, typename HashFunc>
+// A set of Keys that support a HashFunc returning HashType. Used to find duplicates of Key in the
+// Add method. The data-structure is thread-safe through the use of internal locks, it also
+// supports the lock being sharded.
+template <typename Key, typename HashType, typename HashFunc, HashType kShard = 1>
 class DedupeSet {
   typedef std::pair<HashType, Key*> HashedKey;
 
   class Comparator {
    public:
     bool operator()(const HashedKey& a, const HashedKey& b) const {
-      if (a.first < b.first) return true;
-      if (a.first > b.first) return true;
-      return *a.second < *b.second;
+      if (a.first != b.first) {
+        return a.first < b.first;
+      } else {
+        return *a.second < *b.second;
+      }
     }
   };
 
-  typedef std::set<HashedKey, Comparator> Keys;
-
  public:
-  typedef typename Keys::iterator iterator;
-  typedef typename Keys::const_iterator const_iterator;
-  typedef typename Keys::size_type size_type;
-  typedef typename Keys::value_type value_type;
-
-  iterator begin() { return keys_.begin(); }
-  const_iterator begin() const { return keys_.begin(); }
-  iterator end() { return keys_.end(); }
-  const_iterator end() const { return keys_.end(); }
-
   Key* Add(Thread* self, const Key& key) {
-    HashType hash = HashFunc()(key);
-    HashedKey hashed_key(hash, const_cast<Key*>(&key));
-    MutexLock lock(self, lock_);
-    auto it = keys_.find(hashed_key);
-    if (it != keys_.end()) {
+    HashType raw_hash = HashFunc()(key);
+    HashType shard_hash = raw_hash / kShard;
+    HashType shard_bin = raw_hash % kShard;
+    HashedKey hashed_key(shard_hash, const_cast<Key*>(&key));
+    MutexLock lock(self, *lock_[shard_bin]);
+    auto it = keys_[shard_bin].find(hashed_key);
+    if (it != keys_[shard_bin].end()) {
       return it->second;
     }
     hashed_key.second = new Key(key);
-    keys_.insert(hashed_key);
+    keys_[shard_bin].insert(hashed_key);
     return hashed_key.second;
   }
 
-  DedupeSet() : lock_("dedupe lock") {
+  explicit DedupeSet(const char* set_name) {
+    for (HashType i = 0; i < kShard; ++i) {
+      lock_name_[i] = StringPrintf("%s lock %d", set_name, i);
+      lock_[i].reset(new Mutex(lock_name_[i].c_str()));
+    }
   }
 
   ~DedupeSet() {
-    STLDeleteValues(&keys_);
+    for (HashType i = 0; i < kShard; ++i) {
+      STLDeleteValues(&keys_[i]);
+    }
   }
 
  private:
-  Mutex lock_ DEFAULT_MUTEX_ACQUIRED_AFTER;
-  Keys keys_;
+  std::string lock_name_[kShard];
+  UniquePtr<Mutex> lock_[kShard];
+  std::set<HashedKey, Comparator> keys_[kShard];
+
   DISALLOW_COPY_AND_ASSIGN(DedupeSet);
 };
 
diff --git a/compiler/utils/dedupe_set_test.cc b/compiler/utils/dedupe_set_test.cc
index 9f5e292f53..03d8b961fa 100644
--- a/compiler/utils/dedupe_set_test.cc
+++ b/compiler/utils/dedupe_set_test.cc
@@ -38,7 +38,7 @@ class DedupeHashFunc {
 TEST_F(DedupeSetTest, Test) {
   Thread* self = Thread::Current();
   typedef std::vector<uint8_t> ByteArray;
-  DedupeSet<ByteArray, size_t, DedupeHashFunc> deduplicator;
+  DedupeSet<ByteArray, size_t, DedupeHashFunc> deduplicator("test");
   ByteArray* array1;
   {
     ByteArray test1;