EliasFanoCodingTest.cpp File Reference

#include <algorithm>
#include <limits>
#include <numeric>
#include <random>
#include <vector>
#include <folly/Benchmark.h>
#include <folly/experimental/EliasFanoCoding.h>
#include <folly/experimental/Select64.h>
#include <folly/experimental/test/CodingTestUtils.h>
#include <folly/init/Init.h>

Go to the source code of this file.

Classes
class	EliasFanoCodingTest

Namespaces
	bm

Functions
	TEST (EliasFanoCoding, defaultNumLowerBits)
	TEST_F (EliasFanoCodingTest, Empty)
	TEST_F (EliasFanoCodingTest, Simple)
	TEST_F (EliasFanoCodingTest, SkipPointers)
	TEST_F (EliasFanoCodingTest, ForwardPointers)
	TEST_F (EliasFanoCodingTest, SkipForwardPointers)
	TEST_F (EliasFanoCodingTest, BugLargeGapInUpperBits)
void	bm::init ()
void	bm::free ()
	BENCHMARK (Next, iters)
size_t	Skip_ForwardQ128 (size_t iters, size_t logAvgSkip)
	BENCHMARK (Jump_ForwardQ128, iters)
	BENCHMARK_DRAW_LINE ()
size_t	SkipTo_SkipQ128 (size_t iters, size_t logAvgSkip)
	BENCHMARK (JumpTo_SkipQ128, iters)
	BENCHMARK (Encode_10)
	BENCHMARK (Encode)
	BENCHMARK (defaultNumLowerBits, iters)
	BENCHMARK (slowDefaultNumLowerBits, iters)
int	main (int argc, char **argv)

Variables
std::vector< std::pair< size_t, size_t > >	bm::numLowerBitsInput

Function Documentation

BENCHMARK	(	Next	,
		iters
	)

Definition at line 198 of file EliasFanoCodingTest.cpp.

References bm::data, folly::compression::dispatchInstructions(), and bm::list.

                       {
  dispatchInstructions([&](auto instructions) {
    bmNext<EliasFanoReader<bm::Encoder, decltype(instructions)>>(
        bm::list, bm::data, iters);
  });
}

BENCHMARK	(	Jump_ForwardQ128	,
		iters
	)

Definition at line 221 of file EliasFanoCodingTest.cpp.

References folly::BENCHMARK_DRAW_LINE(), bm::data, folly::compression::dispatchInstructions(), bm::list, and bm::order.

                                   {
  dispatchInstructions([&](auto instructions) {
    bmJump<EliasFanoReader<bm::Encoder, decltype(instructions)>>(
        bm::list, bm::data, bm::order, iters);
  });
}

BENCHMARK	(	JumpTo_SkipQ128	,
		iters
	)

Definition at line 246 of file EliasFanoCodingTest.cpp.

References folly::BENCHMARK_DRAW_LINE(), bm::data, folly::compression::dispatchInstructions(), bm::list, and bm::order.

                                  {
  dispatchInstructions([&](auto instructions) {
    bmJumpTo<EliasFanoReader<bm::Encoder, decltype(instructions)>>(
        bm::list, bm::data, bm::order, iters);
  });
}

BENCHMARK

(

Encode_10

)

Definition at line 255 of file EliasFanoCodingTest.cpp.

References folly::test::begin(), folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum >::encode(), bm::encodeSmallData, folly::test::end(), folly::compression::BitVectorCompressedListBase< Pointer >::free(), and bm::list.

                     {
  auto list = bm::Encoder::encode(
      bm::encodeSmallData.begin(), bm::encodeSmallData.end());
  list.free();
}

BENCHMARK

(

Encode

)

Definition at line 261 of file EliasFanoCodingTest.cpp.

References folly::test::begin(), folly::BENCHMARK_DRAW_LINE(), folly::compression::BitVectorEncoder< Value, SkipValue, kSkipQuantum, kForwardQuantum >::encode(), bm::encodeLargeData, folly::test::end(), folly::compression::BitVectorCompressedListBase< Pointer >::free(), and bm::list.

                  {
  auto list = bm::Encoder::encode(
      bm::encodeLargeData.begin(), bm::encodeLargeData.end());
  list.free();
}

BENCHMARK	(	defaultNumLowerBits	,
		iters
	)

Definition at line 269 of file EliasFanoCodingTest.cpp.

References folly::doNotOptimizeAway(), i, bm::numLowerBitsInput, and folly::size().

                                      {
  using Encoder = EliasFanoEncoderV2<size_t>;

  size_t i = 0;
  while (iters--) {
    const auto& p = bm::numLowerBitsInput[i];
    folly::doNotOptimizeAway(Encoder::defaultNumLowerBits(p.first, p.second));
    if (++i == bm::numLowerBitsInput.size()) {
      i = 0;
    }
  }
}

BENCHMARK	(	slowDefaultNumLowerBits	,
		iters
	)

Definition at line 282 of file EliasFanoCodingTest.cpp.

References folly::doNotOptimizeAway(), i, bm::numLowerBitsInput, s, folly::size(), Skip_ForwardQ128(), SkipTo_SkipQ128(), and folly::detail::distributed_mutex::time().

                                          {
  size_t i = 0;
  while (iters--) {
    const auto& p = bm::numLowerBitsInput[i];
    folly::doNotOptimizeAway(slowDefaultNumLowerBits(p.first, p.second));
    if (++i == bm::numLowerBitsInput.size()) {
      i = 0;
    }
  }
}

BENCHMARK_DRAW_LINE

(

)

int main	(	int	argc,
		char **	argv
	)

Definition at line 327 of file EliasFanoCodingTest.cpp.

References bm::free(), folly::init(), bm::init(), testing::InitGoogleTest(), RUN_ALL_TESTS(), and folly::runBenchmarks().

                                {
  testing::InitGoogleTest(&argc, argv);
  folly::init(&argc, &argv);
  gflags::ParseCommandLineFlags(&argc, &argv, true);

  auto ret = RUN_ALL_TESTS();
  if (ret == 0 && FLAGS_benchmark) {
    bm::init();
    folly::runBenchmarks();
    bm::free();
  }

  return ret;
}

size_t Skip_ForwardQ128	(	size_t	iters,
		size_t	logAvgSkip
	)

Definition at line 205 of file EliasFanoCodingTest.cpp.

References BENCHMARK_NAMED_PARAM_MULTI, bm::data, folly::compression::dispatchInstructions(), and bm::list.

Referenced by BENCHMARK().

                                                         {
  dispatchInstructions([&](auto instructions) {
    bmSkip<EliasFanoReader<bm::Encoder, decltype(instructions)>>(
        bm::list, bm::data, logAvgSkip, iters);
  });
  return iters;
}

size_t SkipTo_SkipQ128	(	size_t	iters,
		size_t	logAvgSkip
	)

Definition at line 230 of file EliasFanoCodingTest.cpp.

References BENCHMARK_NAMED_PARAM_MULTI, bm::data, folly::compression::dispatchInstructions(), and bm::list.

Referenced by BENCHMARK().

                                                        {
  dispatchInstructions([&](auto instructions) {
    bmSkipTo<EliasFanoReader<bm::Encoder, decltype(instructions)>>(
        bm::list, bm::data, logAvgSkip, iters);
  });
  return iters;
}

TEST	(	EliasFanoCoding	,
		defaultNumLowerBits
	)

Definition at line 43 of file EliasFanoCodingTest.cpp.

References a, b, folly::gen::batch(), EXPECT_EQ, i, max, min, and folly::size().

                                           {
  // Verify that slowDefaultNumLowerBits and optimized
  // Encoder::defaultNumLowerBits agree.
  static constexpr size_t kNumIterations = 2500;
  auto compare = [](size_t upperBound, size_t size) {
    using Encoder = EliasFanoEncoderV2<size_t>;
    EXPECT_EQ(
        int(slowDefaultNumLowerBits(upperBound, size)),
        int(Encoder::defaultNumLowerBits(upperBound, size)))
        << upperBound << " " << size;
  };
  auto batch = [&compare](size_t initialUpperBound) {
    for (size_t upperBound = initialUpperBound, i = 0; i < kNumIterations;
         ++i, --upperBound) {
      // Test "size" values close to "upperBound".
      for (size_t size = upperBound, j = 0; j < kNumIterations; ++j, --size) {
        compare(upperBound, size);
      }
      // Sample "size" values between [0, upperBound].
      for (size_t size = upperBound; size > 1 + upperBound / kNumIterations;
           size -= 1 + upperBound / kNumIterations) {
        compare(upperBound, size);
      }
      // Test "size" values close to 0.
      for (size_t size = 0; size < kNumIterations; ++size) {
        compare(upperBound, size);
      }
    }
  };
  batch(std::numeric_limits<size_t>::max());
  batch(kNumIterations + 1312213123);
  batch(kNumIterations);

  std::mt19937 gen;
  std::uniform_int_distribution<size_t> distribution;
  for (size_t i = 0; i < kNumIterations; ++i) {
    const auto a = distribution(gen);
    const auto b = distribution(gen);
    compare(std::max(a, b), std::min(a, b));
  }
}

TEST_F	(	EliasFanoCodingTest	,
		Empty
	)

Definition at line 109 of file EliasFanoCodingTest.cpp.

                                   {
  doTestEmpty();
}

TEST_F	(	EliasFanoCodingTest	,
		Simple
	)

Definition at line 113 of file EliasFanoCodingTest.cpp.

                                    {
  doTestAll<0, 0, uint32_t>();
  doTestAll<0, 0, size_t>();
}

TEST_F	(	EliasFanoCodingTest	,
		SkipPointers
	)

Definition at line 118 of file EliasFanoCodingTest.cpp.

                                          {
  doTestAll<128, 0, uint32_t>();
  doTestAll<128, 0, size_t>();
}

TEST_F	(	EliasFanoCodingTest	,
		ForwardPointers
	)

Definition at line 123 of file EliasFanoCodingTest.cpp.

                                             {
  doTestAll<0, 128, uint32_t>();
  doTestAll<0, 128, size_t>();
}

TEST_F	(	EliasFanoCodingTest	,
		SkipForwardPointers
	)

Definition at line 128 of file EliasFanoCodingTest.cpp.

                                                 {
  doTestAll<128, 128, uint32_t>();
  doTestAll<128, 128, size_t>();
}

TEST_F	(	EliasFanoCodingTest	,
		BugLargeGapInUpperBits
	)

Definition at line 133 of file EliasFanoCodingTest.cpp.

References ASSERT_EQ, ASSERT_TRUE, folly::data(), encode(), bm::encodeLargeData, bm::encodeSmallData, folly::compression::BitVectorCompressedListBase< Pointer >::free(), i, bm::list, order, and uint32_t.

                                                    { // t16274876
  typedef EliasFanoEncoderV2<uint32_t, uint32_t, 2, 2> Encoder;
  typedef EliasFanoReader<Encoder, instructions::Default> Reader;
  constexpr uint32_t kLargeValue = 127;

  // Build a list where the upper bits have a large gap after the
  // first element, so that we need to reposition in the upper bits
  // using skips to position the iterator on the second element.
  std::vector<uint32_t> data = {0, kLargeValue};
  for (uint32_t i = 0; i < kLargeValue; ++i) {
    data.push_back(data.back() + 1);
  }
  auto list = Encoder::encode(data.begin(), data.end());

  {
    Reader reader(list);
    ASSERT_TRUE(reader.skipTo(kLargeValue - 1));
    ASSERT_EQ(kLargeValue, reader.value());
    ASSERT_EQ(0, reader.previousValue());
  }

  list.free();
}