centipede/feature_test.cc

// Copyright 2022 The Centipede Authors.
//
// 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
//
//      https://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.

#include "./centipede/feature.h"

#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <cstring>
#include <numeric>
#include <thread>  // NOLINT.
#include <utility>
#include <vector>

#include "gtest/gtest.h"
#include "absl/base/const_init.h"
#include "absl/container/flat_hash_set.h"
#include "absl/log/check.h"
#include "absl/log/log.h"
#include "./centipede/concurrent_bitset.h"
#include "./centipede/concurrent_byteset.h"
#include "./centipede/hashed_ring_buffer.h"
#include "./centipede/int_utils.h"
#include "./centipede/logging.h"

namespace centipede {
namespace {

TEST(Feature, HashedRingBuffer) {
  HashedRingBuffer<32> rb16;  // used with ring_buffer_size == 16
  HashedRingBuffer<32> rb32;  // used with ring_buffer_size == 32
  rb16.Reset(16);
  rb32.Reset(32);
  absl::flat_hash_set<size_t> hashes16, hashes32;
  size_t kNumIter = 10000000;
  // push a large number of different numbers into rb, ensure that most of the
  // resulting hashes are different.
  for (size_t i = 0; i < kNumIter; i++) {
    hashes16.insert(rb16.push(i));
    hashes32.insert(rb32.push(i));
  }
  LOG(INFO) << VV(hashes32.size()) << " " << VV(hashes16.size());
  // No collisions.
  EXPECT_EQ(hashes16.size(), kNumIter);
  EXPECT_EQ(hashes32.size(), kNumIter);

  // Try all permutations of {0, 1, 2, ... 9}, ensure we have at least half
  // this many different hashes.
  std::vector<size_t> numbers(10);
  std::iota(numbers.begin(), numbers.end(), 0);
  hashes32.clear();
  size_t num_permutations = 0;
  while (std::next_permutation(numbers.begin(), numbers.end())) {
    ++num_permutations;
    rb32.Reset(32);
    for (const auto number : numbers) {
      rb32.push(number);
    }
    hashes32.insert(rb32.hash());
  }
  LOG(INFO) << VV(num_permutations) << " " << VV(hashes32.size());
  CHECK_GT(hashes32.size(), num_permutations / 2);
}

TEST(Feature, ConcurrentBitSet) {
  constexpr size_t kSize = 1 << 18;
  static ConcurrentBitSet<kSize> bs(absl::kConstInit);
  std::vector<size_t> in_bits = {0, 1, 2, 100, 102, 1000000};
  std::vector<size_t> expected_out_bits = {0, 1, 2, 100, 102, 1000000 % kSize};
  std::vector<size_t> out_bits;
  for (auto idx : in_bits) {
    bs.set(idx);
  }
  bs.ForEachNonZeroBit([&](size_t idx) { out_bits.push_back(idx); });
  EXPECT_EQ(out_bits, expected_out_bits);

  bs.clear();
  out_bits.clear();
  bs.ForEachNonZeroBit([&](size_t idx) { out_bits.push_back(idx); });
  EXPECT_TRUE(out_bits.empty());
  bs.set(42);
  bs.ForEachNonZeroBit([&](size_t idx) { out_bits.push_back(idx); });
  expected_out_bits = {42};
  EXPECT_EQ(out_bits, expected_out_bits);
  // Check that all bits are now clear.
  out_bits.clear();
  bs.ForEachNonZeroBit([&](size_t idx) { out_bits.push_back(idx); });
  EXPECT_TRUE(out_bits.empty());
}

TEST(Feature, ConcurrentBitGet) {
  constexpr size_t kSize = 1 << 18;
  static ConcurrentBitSet<kSize> bs(absl::kConstInit);
  constexpr size_t kInBit1 = 134217728;
  constexpr size_t kInBit2 = 134217732;
  ASSERT_EQ(bs.get(kInBit1), 0);
  ASSERT_EQ(bs.get(kInBit2), 0);
  bs.set(kInBit1);
  EXPECT_EQ(bs.get(kInBit1), 1);
  EXPECT_EQ(bs.get(kInBit2), 0);
}

TEST(Feature, ConcurrentByteSet) {
  static ConcurrentByteSet<1024> bs(absl::kConstInit);
  const std::vector<std::pair<size_t, uint8_t>> in = {
      {0, 1}, {1, 42}, {2, 33}, {100, 15}, {102, 1}, {800, 66}};

  for (const auto &idx_value : in) {
    bs.Set(idx_value.first, idx_value.second);
  }

  // Test ForEachNonZeroByte.
  std::vector<std::pair<size_t, uint8_t>> out;
  bs.ForEachNonZeroByte(
      [&](size_t idx, uint8_t value) { out.emplace_back(idx, value); });
  EXPECT_EQ(out, in);

  // Now bs should be empty.
  out.clear();
  bs.ForEachNonZeroByte(
      [&](size_t idx, uint8_t value) { out.emplace_back(idx, value); });
  EXPECT_TRUE(out.empty());

  // Test SaturatedIncrement.
  for (const auto &idx_value : in) {
    for (auto iter = 0; iter < idx_value.second; ++iter) {
      bs.SaturatedIncrement(idx_value.first);
    }
  }
  bs.ForEachNonZeroByte(
      [&](size_t idx, uint8_t value) { out.emplace_back(idx, value); });
  EXPECT_EQ(out, in);
}

// Test a thread_local object.
static thread_local TwoLayerConcurrentByteSet<(1 << 17)> two_layer_byte_set(
    absl::kConstInit);

TEST(Feature, TwoLayerConcurrentByteSet) {
  auto &bs = two_layer_byte_set;
  const std::vector<std::pair<size_t, uint8_t>> in = {
      {0, 1}, {1, 42}, {2, 33}, {100, 15}, {102, 1}, {800, 66}};

  for (const auto &idx_value : in) {
    bs.Set(idx_value.first, idx_value.second);
  }

  // Test ForEachNonZeroByte.
  std::vector<std::pair<size_t, uint8_t>> out;
  bs.ForEachNonZeroByte(
      [&](size_t idx, uint8_t value) { out.emplace_back(idx, value); });
  EXPECT_EQ(out, in);

  // Now bs should be empty.
  out.clear();
  bs.ForEachNonZeroByte(
      [&](size_t idx, uint8_t value) { out.emplace_back(idx, value); });
  EXPECT_TRUE(out.empty());

  // Test SaturatedIncrement.
  for (const auto &idx_value : in) {
    for (auto iter = 0; iter < idx_value.second; ++iter) {
      bs.SaturatedIncrement(idx_value.first);
    }
  }
  bs.ForEachNonZeroByte(
      [&](size_t idx, uint8_t value) { out.emplace_back(idx, value); });
  EXPECT_EQ(out, in);
}

// Tests ConcurrentBitSet from multiple threads.
TEST(Feature, ConcurrentBitSet_Threads) {
  static ConcurrentBitSet<(1 << 18)> bs(absl::kConstInit);
  // 3 threads will each set one specific bit in a long loop.
  // 4th thread will set another bit, just once.
  // The set() function is lossy, i.e. it may fail to set the bit.
  // If the value is set in a long loop, it will be set with a probability
  // indistinguishable from one (at least this is my theory :).
  // But the 4th thread that sets its bit once, may actually fail to do it.
  // So, this test allows two outcomes (possible_bits3/possible_bits4).
  auto cb = [&](size_t idx) {
    for (size_t i = 0; i < 10000000; i++) {
      bs.set(idx);
    }
  };
  std::thread t1(cb, 10);
  std::thread t2(cb, 11);
  std::thread t3(cb, 14);
  std::thread t4([&]() { bs.set(15); });
  t1.join();
  t2.join();
  t3.join();
  t4.join();
  std::vector<size_t> bits;
  std::vector<size_t> possible_bits3 = {10, 11, 14};
  std::vector<size_t> possible_bits4 = {10, 11, 14, 15};
  bs.ForEachNonZeroBit([&](size_t idx) { bits.push_back(idx); });
  if (bits.size() == 3) {
    EXPECT_EQ(bits, possible_bits3);
  } else {
    EXPECT_EQ(bits, possible_bits4);
  }
}

// Tests TwoLayerConcurrentByteSet from multiple threads.
TEST(Feature, TwoLayerConcurrentByteSet_Threads) {
  static TwoLayerConcurrentByteSet<(1 << 16)> bs(absl::kConstInit);
  // 3 threads will each increment one specific byte in a long loop.
  // 4th thread will increment another byte, just once.
  auto cb = [&](size_t idx) {
    for (size_t i = 0; i < 10000000; i++) {
      bs.SaturatedIncrement(idx);
    }
  };
  std::thread t1(cb, 10);
  std::thread t2(cb, 11);
  std::thread t3(cb, 14);
  std::thread t4([&]() { bs.SaturatedIncrement(15); });
  t1.join();
  t2.join();
  t3.join();
  t4.join();
  const std::vector<std::pair<size_t, uint8_t>> expected = {
      {10, 255}, {11, 255}, {14, 255}, {15, 1}};
  std::vector<std::pair<size_t, uint8_t>> out;
  bs.ForEachNonZeroByte(
      [&](size_t idx, uint8_t value) { out.emplace_back(idx, value); });
  EXPECT_EQ(out, expected);
}

// Global ConcurrentBitSet with a absl::kConstInit CTOR.
static ConcurrentBitSet<(1 << 20)> large_concurrent_bitset(absl::kConstInit);
// Test a thread-local object.
static thread_local ConcurrentBitSet<(1 << 20)> large_tls_concurrent_bitset(
    absl::kConstInit);

TEST(Feature, ConcurrentBitSet_Large) {
  for (auto *bs : {&large_concurrent_bitset, &large_tls_concurrent_bitset}) {
    const std::vector<size_t> in_bits = {0,   1,     2,     100,   102,
                                         800, 10000, 20000, 30000, 500000};

    for (size_t iter = 0; iter < 100000; ++iter) {
      for (auto idx : in_bits) {
        bs->set(idx);
      }
      std::vector<size_t> out_bits;
      bs->ForEachNonZeroBit([&](size_t idx) { out_bits.push_back(idx); });
      EXPECT_EQ(out_bits, in_bits);
    }
  }
}

TEST(Feature, FeatureArray) {
  FeatureArray<3> array;
  EXPECT_EQ(array.size(), 0);
  array.push_back(10);
  EXPECT_EQ(array.size(), 1);
  array.push_back(20);
  EXPECT_EQ(array.size(), 2);
  array.clear();
  EXPECT_EQ(array.size(), 0);
  array.push_back(10);
  array.push_back(20);
  array.push_back(30);
  EXPECT_EQ(array.size(), 3);
  array.push_back(40);  // no space left.
  EXPECT_EQ(array.size(), 3);
  EXPECT_EQ(array.data()[0], 10);
  EXPECT_EQ(array.data()[1], 20);
  EXPECT_EQ(array.data()[2], 30);
}

TEST(Feature, Hash64Bits) {
  // Run a large sample of small integers and verify that lower X bits
  // of Hash64Bits(), for X in 64, 48, 32, and 20, are unique.
  absl::flat_hash_set<uint64_t> set64;
  absl::flat_hash_set<uint64_t> set48;
  absl::flat_hash_set<uint64_t> set32;
  absl::flat_hash_set<uint64_t> set20;
  size_t num_values = 0;
  constexpr uint64_t kMaxIntToCheck = 1ULL << 28;
  constexpr uint64_t kMask48 = (1ULL << 48) - 1;
  constexpr uint64_t kMask32 = (1ULL << 32) - 1;
  constexpr uint64_t kMask20 = (1ULL << 20) - 1;
  for (uint64_t i = 0; i < kMaxIntToCheck; i += 101, ++num_values) {
    set64.insert(Hash64Bits(i));
    set48.insert(Hash64Bits(i) & kMask48);
    set32.insert(Hash64Bits(i) & kMask32);
    set20.insert(Hash64Bits(i) & kMask20);
  }
  EXPECT_EQ(set64.size(), num_values);
  EXPECT_EQ(set48.size(), num_values);
  EXPECT_EQ(set32.size(), num_values);
  EXPECT_EQ(set20.size(), 1 << 20);  // all possible 20-bit numbers.

  // For a large number of pairs of small integers {i, j} verify that
  // values of Hash64Bits(i) ^ (j) are unique.
  set64.clear();
  num_values = 0;
  for (uint64_t i = 0; i < kMaxIntToCheck; i += 100000) {
    for (uint64_t j = 1; j < kMaxIntToCheck; j += 100000) {
      set64.insert(Hash64Bits(i) ^ (j));
      ++num_values;
    }
  }
  EXPECT_EQ(set64.size(), num_values);
}

}  // namespace
}  // namespace centipede