folly::compression Namespace Reference

Namespaces
	detail
	instructions

Classes
struct	BitVectorCompressedListBase
struct	BitVectorEncoder
class	BitVectorReader
struct	EliasFanoCompressedListBase
struct	EliasFanoEncoderV2
class	EliasFanoReader

Typedefs
typedef BitVectorCompressedListBase< const uint8_t * >	BitVectorCompressedList
typedef BitVectorCompressedListBase< uint8_t * >	MutableBitVectorCompressedList
typedef EliasFanoCompressedListBase< const uint8_t * >	EliasFanoCompressedList
typedef EliasFanoCompressedListBase< uint8_t * >	MutableEliasFanoCompressedList

Functions
folly::Optional< instructions::Type >	instructionsOverride ()
template<class URNG >
std::vector< uint32_t >	generateRandomList (size_t n, uint32_t maxId, URNG &&g)
std::vector< uint32_t >	generateRandomList (size_t n, uint32_t maxId)
std::vector< uint32_t >	generateSeqList (uint32_t minId, uint32_t maxId, uint32_t step=1)
std::vector< uint32_t >	loadList (const std::string &filename)
template<class... Args>
void	maybeTestPreviousValue (Args &&...)
template<class Vector , class Reader , class Index >
auto	maybeTestPreviousValue (const Vector &data, Reader &reader, Index i) -> decltype(reader.previousValue(), void())
template<class... Args>
void	maybeTestPrevious (Args &&...)
template<class Vector , class Reader , class Index >
auto	maybeTestPrevious (const Vector &data, Reader &reader, Index i) -> decltype(reader.previous(), void())
template<class Reader , class List >
void	testNext (const std::vector< uint32_t > &data, const List &list)
template<class Reader , class List >
void	testSkip (const std::vector< uint32_t > &data, const List &list, size_t skipStep)
template<class Reader , class List >
void	testSkip (const std::vector< uint32_t > &data, const List &list)
template<class Reader , class List >
void	testSkipTo (const std::vector< uint32_t > &data, const List &list, size_t skipToStep)
template<class Reader , class List >
void	testSkipTo (const std::vector< uint32_t > &data, const List &list)
template<class Reader , class List >
void	testJump (const std::vector< uint32_t > &data, const List &list)
template<class Reader , class List >
void	testJumpTo (const std::vector< uint32_t > &data, const List &list)
template<class Reader , class Encoder >
void	testEmpty ()
template<class Reader , class Encoder >
void	testAll (const std::vector< uint32_t > &data)
template<class Reader , class List >
void	bmNext (const List &list, const std::vector< uint32_t > &data, size_t iters)
template<class Reader , class List >
void	bmSkip (const List &list, const std::vector< uint32_t > &, size_t logAvgSkip, size_t iters)
template<class Reader , class List >
void	bmSkipTo (const List &list, const std::vector< uint32_t > &data, size_t logAvgSkip, size_t iters)
template<class Reader , class List >
void	bmJump (const List &list, const std::vector< uint32_t > &data, const std::vector< size_t > &order, size_t iters)
template<class Reader , class List >
void	bmJumpTo (const List &list, const std::vector< uint32_t > &data, const std::vector< size_t > &order, size_t iters)
template<class F >
auto	dispatchInstructions (F &&f) -> decltype(f(std::declval< instructions::Default >()))

Variables
constexpr size_t	kCacheLineSize = 64

Typedef Documentation

typedef BitVectorCompressedListBase<const uint8_t*> folly::compression::BitVectorCompressedList

Definition at line 71 of file BitVectorCoding.h.

typedef EliasFanoCompressedListBase<const uint8_t*> folly::compression::EliasFanoCompressedList

Definition at line 89 of file EliasFanoCoding.h.

typedef BitVectorCompressedListBase<uint8_t*> folly::compression::MutableBitVectorCompressedList

Definition at line 72 of file BitVectorCoding.h.

typedef EliasFanoCompressedListBase<uint8_t*> folly::compression::MutableEliasFanoCompressedList

Definition at line 90 of file EliasFanoCoding.h.

Function Documentation

template<class Reader , class List >

void folly::compression::bmJump	(	const List &	list,
		const std::vector< uint32_t > &	data,
		const std::vector< size_t > &	order,
		size_t	iters
	)

Definition at line 385 of file CodingTestUtils.h.

References folly::doNotOptimizeAway(), and i.

                  {
  CHECK(!data.empty());
  CHECK_EQ(data.size(), order.size());

  Reader reader(list);
  for (size_t i = 0, j = 0; i < iters; ++i, ++j) {
    if (j == order.size()) {
      j = 0;
    }
    reader.jump(order[j]);
    folly::doNotOptimizeAway(reader.value());
  }
}

template<class Reader , class List >

void folly::compression::bmJumpTo	(	const List &	list,
		const std::vector< uint32_t > &	data,
		const std::vector< size_t > &	order,
		size_t	iters
	)

Definition at line 404 of file CodingTestUtils.h.

References folly::doNotOptimizeAway(), i, and instructionsOverride().

                  {
  CHECK(!data.empty());
  CHECK_EQ(data.size(), order.size());

  Reader reader(list);
  for (size_t i = 0, j = 0; i < iters; ++i, ++j) {
    if (j == order.size()) {
      j = 0;
    }
    reader.jumpTo(data[order[j]]);
    folly::doNotOptimizeAway(reader.value());
  }
}

template<class Reader , class List >

void folly::compression::bmNext	(	const List &	list,
		const std::vector< uint32_t > &	data,
		size_t	iters
	)

Definition at line 324 of file CodingTestUtils.h.

References folly::doNotOptimizeAway(), i, and LIKELY.

                                                                             {
  if (data.empty()) {
    return;
  }

  Reader reader(list);
  for (size_t i = 0; i < iters; ++i) {
    if (LIKELY(reader.next())) {
      folly::doNotOptimizeAway(reader.value());
    } else {
      reader.reset();
    }
  }
}

template<class Reader , class List >

void folly::compression::bmSkip	(	const List &	list,
		const std::vector< uint32_t > &	,
		size_t	logAvgSkip,
		size_t	iters
	)

Definition at line 340 of file CodingTestUtils.h.

References folly::doNotOptimizeAway(), i, LIKELY, and folly::gen::skip().

                  {
  size_t avg = (size_t(1) << logAvgSkip);
  size_t base = avg - (avg >> 2);
  size_t mask = (avg > 1) ? (avg >> 1) - 1 : 0;

  Reader reader(list);
  for (size_t i = 0; i < iters; ++i) {
    size_t skip = base + (i & mask);
    if (LIKELY(reader.skip(skip))) {
      folly::doNotOptimizeAway(reader.value());
    } else {
      reader.reset();
    }
  }
}

template<class Reader , class List >

void folly::compression::bmSkipTo	(	const List &	list,
		const std::vector< uint32_t > &	data,
		size_t	logAvgSkip,
		size_t	iters
	)

Definition at line 361 of file CodingTestUtils.h.

References folly::doNotOptimizeAway(), i, and folly::gen::skip().

                  {
  size_t avg = (size_t(1) << logAvgSkip);
  size_t base = avg - (avg >> 2);
  size_t mask = (avg > 1) ? (avg >> 1) - 1 : 0;

  Reader reader(list);
  for (size_t i = 0, j = -1; i < iters; ++i) {
    size_t skip = base + (i & mask);
    j += skip;
    if (j >= data.size()) {
      reader.reset();
      j = -1;
    }

    reader.skipTo(data[j]);
    folly::doNotOptimizeAway(reader.value());
  }
}

template<class F >

auto folly::compression::dispatchInstructions

(

F &&

f

)

-> decltype(f(std::declval<instructions::Default>()))

Definition at line 425 of file CodingTestUtils.h.

References folly::compression::instructions::dispatch(), f, instructionsOverride(), and type.

Referenced by BENCHMARK(), Skip_ForwardQ128(), and SkipTo_SkipQ128().

                                                      {
  if (auto type = instructionsOverride()) {
    return instructions::dispatch(*type, std::forward<F>(f));
  } else {
    return instructions::dispatch(std::forward<F>(f));
  }
}

template<class URNG >

std::vector<uint32_t> folly::compression::generateRandomList	(	size_t	n,
		uint32_t	maxId,
		URNG &&	g
	)

Definition at line 39 of file CodingTestUtils.h.

References g(), uint32_t, and folly::value().

Referenced by BitVectorCodingTest::doTestAll(), EliasFanoCodingTest::doTestAll(), generateRandomList(), and bm::init().

                                                                           {
  CHECK_LT(n, 2 * maxId);
  std::uniform_int_distribution<> uid(1, maxId);
  std::unordered_set<uint32_t> dataset;
  while (dataset.size() < n) {
    uint32_t value = uid(g);
    if (dataset.count(value) == 0) {
      dataset.insert(value);
    }
  }

  std::vector<uint32_t> ids(dataset.begin(), dataset.end());
  std::sort(ids.begin(), ids.end());
  return ids;
}

std::vector<uint32_t> folly::compression::generateRandomList ( size_t  n, uint32_t  maxId  )

inline

Definition at line 55 of file CodingTestUtils.h.

References generateRandomList().

                                                                        {
  std::mt19937 gen;
  return generateRandomList(n, maxId, gen);
}

std::vector<uint32_t> folly::compression::generateSeqList ( uint32_t  minId, uint32_t  maxId, uint32_t  step = 1  )

inline

Definition at line 61 of file CodingTestUtils.h.

References i, and uint32_t.

Referenced by BitVectorCodingTest::doTestAll(), and EliasFanoCodingTest::doTestAll().

                                                                   {
  CHECK_LE(minId, maxId);
  CHECK_GT(step, 0);
  std::vector<uint32_t> ids;
  ids.reserve((maxId - minId) / step + 1);
  for (uint32_t i = minId; i <= maxId; i += step) {
    ids.push_back(i);
  }
  return ids;
}

folly::Optional< instructions::Type > folly::compression::instructionsOverride

(

)

Definition at line 30 of file CodingTestUtils.cpp.

References folly::compression::instructions::DEFAULT, folly::compression::instructions::dispatch(), folly::FATAL, folly::compression::instructions::HASWELL, folly::compression::instructions::NEHALEM, folly::none, and type.

Referenced by bmJumpTo(), and dispatchInstructions().

                                                       {
  if (FLAGS_coding_test_utils_instructions.empty()) {
    return folly::none;
  }

  instructions::Type type;
  if (FLAGS_coding_test_utils_instructions == "Default") {
    type = instructions::Type::DEFAULT;
  } else if (FLAGS_coding_test_utils_instructions == "Nehalem") {
    type = instructions::Type::NEHALEM;
  } else if (FLAGS_coding_test_utils_instructions == "Haswell") {
    type = instructions::Type::HASWELL;
  } else {
    LOG(FATAL) << "Insupported instructions type "
               << FLAGS_coding_test_utils_instructions;
  }

  instructions::dispatch(
      type, [](auto instructions) { CHECK(instructions.supported()); });

  return type;
}

std::vector<uint32_t> folly::compression::loadList ( const std::string &  filename )

inline

Definition at line 72 of file CodingTestUtils.h.

References testing::Args(), and uint32_t.

                                                               {
  std::ifstream fin(filename);
  std::vector<uint32_t> result;
  uint32_t id;
  while (fin >> id) {
    result.push_back(id);
  }
  return result;
}

template<class... Args>

void folly::compression::maybeTestPrevious

(

Args &&

...

)

Definition at line 99 of file CodingTestUtils.h.

Referenced by testJump(), testNext(), testSkip(), and testSkipTo().

{}

template<class Vector , class Reader , class Index >

auto folly::compression::maybeTestPrevious	(	const Vector &	data,
		Reader &	reader,
		Index	i
	)		-> decltype(reader.previous(), void())

Definition at line 105 of file CodingTestUtils.h.

References folly::data(), EXPECT_EQ, EXPECT_FALSE, EXPECT_TRUE, and i.

                                           {
  auto r = reader.previous();
  if (i != 0) {
    EXPECT_TRUE(r);
    EXPECT_EQ(reader.value(), data[i - 1]);
  } else {
    EXPECT_FALSE(r);
  }
  reader.next();
  EXPECT_EQ(reader.value(), data[i]);
}

template<class... Args>

void folly::compression::maybeTestPreviousValue

(

Args &&

...

)

Definition at line 84 of file CodingTestUtils.h.

Referenced by testJump(), testNext(), testSkip(), and testSkipTo().

{}

template<class Vector , class Reader , class Index >

auto folly::compression::maybeTestPreviousValue	(	const Vector &	data,
		Reader &	reader,
		Index	i
	)		-> decltype(reader.previousValue(), void())

Definition at line 90 of file CodingTestUtils.h.

References testing::Args(), folly::data(), EXPECT_EQ, and i.

                                                {
  if (i != 0) {
    EXPECT_EQ(reader.previousValue(), data[i - 1]);
  }
}

template<class Reader , class Encoder >

void folly::compression::testAll

(

const std::vector< uint32_t > &

data

)

Definition at line 313 of file CodingTestUtils.h.

References folly::data(), encode(), and bm::list.

                                              {
  auto list = Encoder::encode(data.begin(), data.end());
  testNext<Reader>(data, list);
  testSkip<Reader>(data, list);
  testSkipTo<Reader>(data, list);
  testJump<Reader>(data, list);
  testJumpTo<Reader>(data, list);
  list.free();
}

template<class Reader , class Encoder >

void folly::compression::testEmpty

(

)

Definition at line 290 of file CodingTestUtils.h.

References folly::data(), encode(), EXPECT_EQ, EXPECT_FALSE, and bm::list.

                 {
  const typename Encoder::ValueType* const data = nullptr;
  auto list = Encoder::encode(data, data);
  {
    Reader reader(list);
    EXPECT_FALSE(reader.next());
    EXPECT_EQ(reader.size(), 0);
  }
  {
    Reader reader(list);
    EXPECT_FALSE(reader.skip(1));
    EXPECT_FALSE(reader.skip(10));
    EXPECT_FALSE(reader.jump(0));
    EXPECT_FALSE(reader.jump(10));
  }
  {
    Reader reader(list);
    EXPECT_FALSE(reader.skipTo(1));
    EXPECT_FALSE(reader.jumpTo(1));
  }
}

template<class Reader , class List >

void folly::compression::testJump	(	const std::vector< uint32_t > &	data,
		const List &	list
	)

Definition at line 234 of file CodingTestUtils.h.

References EXPECT_EQ, EXPECT_FALSE, EXPECT_TRUE, i, maybeTestPrevious(), and maybeTestPreviousValue().

                                                                 {
  std::mt19937 gen;
  std::vector<size_t> is(data.size());
  for (size_t i = 0; i < data.size(); ++i) {
    is[i] = i;
  }
  std::shuffle(is.begin(), is.end(), gen);
  if (Reader::EncoderType::forwardQuantum == 0) {
    is.resize(std::min<size_t>(is.size(), 100));
  }

  Reader reader(list);
  for (auto i : is) {
    EXPECT_TRUE(reader.jump(i));
    EXPECT_EQ(reader.value(), data[i]);
    EXPECT_EQ(reader.position(), i);
    maybeTestPreviousValue(data, reader, i);
    maybeTestPrevious(data, reader, i);
  }
  EXPECT_FALSE(reader.jump(data.size()));
  EXPECT_FALSE(reader.valid());
  EXPECT_EQ(reader.position(), reader.size());
}

template<class Reader , class List >

void folly::compression::testJumpTo	(	const std::vector< uint32_t > &	data,
		const List &	list
	)

Definition at line 259 of file CodingTestUtils.h.

References EXPECT_EQ, EXPECT_FALSE, EXPECT_TRUE, i, uint32_t, folly::value(), and values().

                                                                   {
  CHECK(!data.empty());

  Reader reader(list);

  std::mt19937 gen;
  std::uniform_int_distribution<> values(0, data.back());
  const size_t iters = Reader::EncoderType::skipQuantum == 0 ? 100 : 10000;
  for (size_t i = 0; i < iters; ++i) {
    const uint32_t value = values(gen);
    auto it = std::lower_bound(data.begin(), data.end(), value);
    CHECK(it != data.end());
    EXPECT_TRUE(reader.jumpTo(value));
    EXPECT_EQ(reader.value(), *it);
    EXPECT_EQ(reader.position(), std::distance(data.begin(), it));
  }

  EXPECT_TRUE(reader.jumpTo(0));
  EXPECT_EQ(reader.value(), data[0]);
  EXPECT_EQ(reader.position(), 0);

  EXPECT_TRUE(reader.jumpTo(data.back()));
  EXPECT_EQ(reader.value(), data.back());
  EXPECT_EQ(reader.position(), reader.size() - 1);

  EXPECT_FALSE(reader.jumpTo(data.back() + 1));
  EXPECT_FALSE(reader.valid());
  EXPECT_EQ(reader.position(), reader.size());
}

template<class Reader , class List >

void folly::compression::testNext	(	const std::vector< uint32_t > &	data,
		const List &	list
	)

Definition at line 119 of file CodingTestUtils.h.

References EXPECT_EQ, EXPECT_FALSE, EXPECT_TRUE, i, maybeTestPrevious(), and maybeTestPreviousValue().

                                                                 {
  Reader reader(list);
  EXPECT_FALSE(reader.valid());

  for (size_t i = 0; i < data.size(); ++i) {
    EXPECT_TRUE(reader.next());
    EXPECT_TRUE(reader.valid());
    EXPECT_EQ(reader.value(), data[i]);
    EXPECT_EQ(reader.position(), i);
    maybeTestPreviousValue(data, reader, i);
    maybeTestPrevious(data, reader, i);
  }
  EXPECT_FALSE(reader.next());
  EXPECT_FALSE(reader.valid());
  EXPECT_EQ(reader.position(), reader.size());
}

template<class Reader , class List >

void folly::compression::testSkip	(	const std::vector< uint32_t > &	data,
		const List &	list,
		size_t	skipStep
	)

Definition at line 137 of file CodingTestUtils.h.

References EXPECT_EQ, EXPECT_FALSE, EXPECT_TRUE, i, maybeTestPrevious(), and maybeTestPreviousValue().

                     {
  CHECK_GT(skipStep, 0);
  Reader reader(list);

  for (size_t i = skipStep - 1; i < data.size(); i += skipStep) {
    EXPECT_TRUE(reader.skip(skipStep));
    EXPECT_TRUE(reader.valid());
    EXPECT_EQ(reader.value(), data[i]);
    EXPECT_EQ(reader.position(), i);
    maybeTestPreviousValue(data, reader, i);
    maybeTestPrevious(data, reader, i);
  }
  EXPECT_FALSE(reader.skip(skipStep));
  EXPECT_FALSE(reader.valid());
  EXPECT_EQ(reader.position(), reader.size());
  EXPECT_FALSE(reader.next());
}

template<class Reader , class List >

void folly::compression::testSkip	(	const std::vector< uint32_t > &	data,
		const List &	list
	)

Definition at line 159 of file CodingTestUtils.h.

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

                                                                 {
  for (size_t skipStep = 1; skipStep < 25; ++skipStep) {
    testSkip<Reader, List>(data, list, skipStep);
  }
  for (size_t skipStep = 25; skipStep <= 500; skipStep += 25) {
    testSkip<Reader, List>(data, list, skipStep);
  }
}

template<class Reader , class List >

void folly::compression::testSkipTo	(	const std::vector< uint32_t > &	data,
		const List &	list,
		size_t	skipToStep
	)

Definition at line 169 of file CodingTestUtils.h.

References EXPECT_EQ, EXPECT_FALSE, EXPECT_TRUE, maybeTestPrevious(), maybeTestPreviousValue(), uint32_t, and folly::value().

                       {
  CHECK_GT(skipToStep, 0);
  Reader reader(list);

  const uint32_t delta = std::max<uint32_t>(1, data.back() / skipToStep);
  uint32_t value = delta;
  auto it = data.begin();
  while (true) {
    it = std::lower_bound(it, data.end(), value);
    if (it == data.end()) {
      EXPECT_FALSE(reader.skipTo(value));
      break;
    }
    EXPECT_TRUE(reader.skipTo(value));
    EXPECT_TRUE(reader.valid());
    EXPECT_EQ(reader.value(), *it);
    EXPECT_EQ(reader.position(), std::distance(data.begin(), it));
    value = reader.value() + delta;
    maybeTestPreviousValue(data, reader, std::distance(data.begin(), it));
    maybeTestPrevious(data, reader, std::distance(data.begin(), it));
  }
  EXPECT_FALSE(reader.valid());
  EXPECT_EQ(reader.position(), reader.size());
  EXPECT_FALSE(reader.next());
}

template<class Reader , class List >

void folly::compression::testSkipTo	(	const std::vector< uint32_t > &	data,
		const List &	list
	)

Definition at line 199 of file CodingTestUtils.h.

References folly::data(), EXPECT_EQ, EXPECT_FALSE, EXPECT_TRUE, bm::list, max, and shell_builder::steps.

                                                                   {
  for (size_t steps = 10; steps < 100; steps += 10) {
    testSkipTo<Reader, List>(data, list, steps);
  }
  for (size_t steps = 100; steps <= 1000; steps += 100) {
    testSkipTo<Reader, List>(data, list, steps);
  }
  testSkipTo<Reader, List>(data, list, std::numeric_limits<size_t>::max());
  {
    // Skip to the first element.
    Reader reader(list);
    EXPECT_TRUE(reader.skipTo(data[0]));
    EXPECT_EQ(reader.value(), data[0]);
    EXPECT_EQ(reader.position(), 0);
  }
  {
    // Skip past the last element.
    Reader reader(list);
    EXPECT_FALSE(reader.skipTo(data.back() + 1));
    EXPECT_FALSE(reader.valid());
    EXPECT_EQ(reader.position(), reader.size());
    EXPECT_FALSE(reader.next());
  }
  {
    // Skip to maximum integer.
    Reader reader(list);
    using ValueType = typename Reader::ValueType;
    EXPECT_FALSE(reader.skipTo(std::numeric_limits<ValueType>::max()));
    EXPECT_FALSE(reader.valid());
    EXPECT_EQ(reader.position(), reader.size());
    EXPECT_FALSE(reader.next());
  }
}

Variable Documentation

constexpr size_t folly::compression::kCacheLineSize = 64

Definition at line 50 of file EliasFanoCoding.h.