uint8_t HotHashDetector::bumpHash()

in cachelib/common/hothash/HotHashDetector.cpp [28:82]

• 44 lines of code
• 12 McCabe index (conditional complexity)

uint8_t HotHashDetector::bumpHash(uint64_t hash) {
  if (UNLIKELY(++bumpsSinceMaintenance_ >= maintenanceInterval_)) {
    doMaintenance();
  };
  auto idx = l1HashFunction(hash);
  auto l1count = ++l1Vector_[idx];
  // Checking against threshold/2, hot index should pass after one decay
  if (l1count < (l1Threshold_ / 2)) {
    return 0;
  }
  uint8_t result = 0;
  // different hash for L2:
  auto idx2 = l2HashFunction(hash);

  // If L2 has a count, then there is a chance that the given hash is hot,
  // scan a few elements for this hash.
  uint32_t l2count = l2Vector_[idx2].count;
  if (l2count > 0) {
    for (unsigned i = 0; i < kScanLen; ++i) {
      auto& cell = l2Vector_[(idx2 + i) & bucketsMask_];
      if (cell.hash == 0) {
        break;
      }
      if (cell.hash == hash) {
        // Get a number between 1 and 255 for how much hot the L2 entry is.
        result = static_cast<uint8_t>(std::min<uint32_t>(
            255, std::max<uint32_t>(1, l2count / hotnessMultiplier_)));
        ++cell.hashHits;
        break;
      }
    }
  }

  // Proceed to bump L2 if the l1count is divisible by current L1 threshold.
  if (l1count % l1Threshold_ != 0) {
    return result;
  }
  if (++l2Vector_[idx2].count < hotnessMultiplier_) {
    return result;
  }
  for (unsigned i = 0; i < kScanLen; ++i) {
    auto& cell = l2Vector_[(idx2 + i) & bucketsMask_];
    if (cell.hash == 0) {
      cell.hash = hash;
      break;
    }
    if (cell.hash == hash) {
      break;
    }
    // NOTE: in the unlikely case that we scanned kScanLen entries, we will drop
    // the hash without inserting it.
  }

  return result;
}