folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType > Class Template Reference

#include <EliasFanoCoding.h>

Public Types
typedef Encoder	EncoderType
typedef Encoder::ValueType	ValueType

Public Member Functions
	EliasFanoReader (const typename Encoder::CompressedList &list)
void	reset ()
bool	previous ()
bool	next ()
bool	skip (SizeType n)
bool	skipTo (ValueType value)
void	prepareSkipTo (ValueType value) const
bool	jump (SizeType n)
bool	jumpTo (ValueType value)
ValueType	lastValue () const
ValueType	previousValue () const
SizeType	size () const
bool	valid () const
SizeType	position () const
ValueType	value () const

Private Member Functions
bool	setDone ()
ValueType	readLowerPart (SizeType i) const
void	iterateTo (ValueType value)

Private Attributes
detail::UpperBitsReader< Encoder, Instructions, SizeType >	upper_
const uint8_t *	lower_
SizeType	size_
ValueType	value_ = kInvalidValue
ValueType	lastValue_
uint8_t	numLowerBits_

Static Private Attributes
static constexpr ValueType	kInvalidValue
static constexpr size_t	kLinearScanThreshold = 8

Detailed Description

template<class Encoder, class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>
class folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >

Definition at line 576 of file EliasFanoCoding.h.

Member Typedef Documentation

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

typedef Encoder folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::EncoderType

Definition at line 578 of file EliasFanoCoding.h.

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

typedef Encoder::ValueType folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::ValueType

Definition at line 579 of file EliasFanoCoding.h.

Constructor & Destructor Documentation

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::EliasFanoReader ( const typename Encoder::CompressedList &  list )

inlineexplicit

Definition at line 581 of file EliasFanoCoding.h.

References folly::findLastSet(), and UNLIKELY.

      : upper_(list),
        lower_(list.lower),
        size_(list.size),
        numLowerBits_(list.numLowerBits) {
    DCHECK(Instructions::supported());
    // To avoid extra branching during skipTo() while reading
    // upper sequence we need to know the last element.
    // If kUnchecked == true, we do not check that skipTo() is called
    // within the bounds, so we can avoid initializing lastValue_.
    if (kUnchecked || UNLIKELY(list.size == 0)) {
      lastValue_ = 0;
      return;
    }
    ValueType lastUpperValue = ValueType(8 * list.upperSize() - size_);
    auto it = list.upper + list.upperSize() - 1;
    DCHECK_NE(*it, 0);
    lastUpperValue -= 8 - folly::findLastSet(*it);
    lastValue_ = readLowerPart(size_ - 1) | (lastUpperValue << numLowerBits_);
  }

Member Function Documentation

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

void folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::iterateTo ( ValueType  value )

inlineprivate

Definition at line 766 of file EliasFanoCoding.h.

References LIKELY.

                                  {
    while (true) {
      value_ =
          readLowerPart(upper_.position()) | (upper_.value() << numLowerBits_);
      if (LIKELY(value_ >= value)) {
        break;
      }
      upper_.next();
    }
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

bool folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::jump ( SizeType  n )

inline

Definition at line 698 of file EliasFanoCoding.h.

References LIKELY.

                        {
    if (LIKELY(n < size_)) { // Also checks that n != -1.
      value_ = readLowerPart(n) | (upper_.jump(n + 1) << numLowerBits_);
      return true;
    }
    return setDone();
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

bool folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::jumpTo ( ValueType  value )

inline

Definition at line 706 of file EliasFanoCoding.h.

                               {
    if (!kUnchecked && value > lastValue_) {
      return setDone();
    }

    upper_.jumpToNext(value >> numLowerBits_);
    iterateTo(value);
    return true;
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

ValueType folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::lastValue ( ) const

inline

Definition at line 716 of file EliasFanoCoding.h.

                              {
    CHECK(!kUnchecked);
    return lastValue_;
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

bool folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::next ( )

inline

Definition at line 618 of file EliasFanoCoding.h.

References UNLIKELY.

              {
    if (!kUnchecked && UNLIKELY(position() + 1 >= size_)) {
      return setDone();
    }
    upper_.next();
    value_ =
        readLowerPart(upper_.position()) | (upper_.value() << numLowerBits_);
    return true;
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

SizeType folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::position ( ) const

inline

Definition at line 736 of file EliasFanoCoding.h.

                            {
    return upper_.position();
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

void folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::prepareSkipTo ( ValueType  value ) const

inline

Prepare to skip to value by prefetching appropriate memory in both the upper and lower bits.

Definition at line 679 of file EliasFanoCoding.h.

References addr.

                                            {
    // Also works when value_ == kInvalidValue.
    if (value != kInvalidValue) {
      DCHECK_GE(value + 1, value_ + 1);
    }

    if ((!kUnchecked && value > lastValue_) || (value == value_)) {
      return;
    }

    // Do minimal computation required to prefetch address used in
    // `readLowerPart()`.
    ValueType upperValue = (value >> numLowerBits_);
    const auto upperPosition = upper_.prepareSkipTo(upperValue);
    const auto addr = lower_ + (upperPosition * numLowerBits_ / 8);
    __builtin_prefetch(addr);
    __builtin_prefetch(addr + kCacheLineSize);
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

bool folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::previous ( )

inline

Definition at line 607 of file EliasFanoCoding.h.

References UNLIKELY.

                  {
    if (!kUnchecked && UNLIKELY(position() == 0)) {
      reset();
      return false;
    }
    upper_.previous();
    value_ =
        readLowerPart(upper_.position()) | (upper_.value() << numLowerBits_);
    return true;
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

ValueType folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::previousValue ( ) const

inline

Definition at line 721 of file EliasFanoCoding.h.

References folly::compression::EliasFanoCompressedListBase< Pointer >::size.

                                  {
    DCHECK_GT(position(), 0);
    DCHECK_LT(position(), size());
    return readLowerPart(upper_.position() - 1) |
        (upper_.previousValue() << numLowerBits_);
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

ValueType folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::readLowerPart ( SizeType  i ) const

inlineprivate

Definition at line 755 of file EliasFanoCoding.h.

References folly::assume(), ptr, and uint64_t.

                                            {
    DCHECK_LT(i, size_);
    const size_t pos = i * numLowerBits_;
    const unsigned char* ptr = lower_ + (pos / 8);
    const uint64_t ptrv = folly::loadUnaligned<uint64_t>(ptr);
    // This removes the branch in the fallback implementation of
    // bzhi. The condition is verified at encoding time.
    assume(numLowerBits_ < sizeof(ValueType) * 8);
    return Instructions::bzhi(ptrv >> (pos % 8), numLowerBits_);
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

void folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::reset ( )

inline

Definition at line 602 of file EliasFanoCoding.h.

               {
    upper_.reset();
    value_ = kInvalidValue;
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

bool folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::setDone ( )

inlineprivate

Definition at line 749 of file EliasFanoCoding.h.

                 {
    value_ = kInvalidValue;
    upper_.setDone(size_);
    return false;
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

SizeType folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::size ( ) const

inline

Definition at line 728 of file EliasFanoCoding.h.

                        {
    return size_;
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

bool folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::skip ( SizeType  n )

inline

Definition at line 628 of file EliasFanoCoding.h.

References i, and LIKELY.

                        {
    CHECK_GT(n, 0);

    if (kUnchecked || LIKELY(position() + n < size_)) {
      if (LIKELY(n < kLinearScanThreshold)) {
        for (SizeType i = 0; i < n; ++i) {
          upper_.next();
        }
      } else {
        upper_.skip(n);
      }
      value_ =
          readLowerPart(upper_.position()) | (upper_.value() << numLowerBits_);
      return true;
    }

    return setDone();
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

bool folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::skipTo ( ValueType  value )

inline

Definition at line 647 of file EliasFanoCoding.h.

References UNLIKELY.

                               {
    // Also works when value_ == kInvalidValue.
    if (value != kInvalidValue) {
      DCHECK_GE(value + 1, value_ + 1);
    }

    if (!kUnchecked && value > lastValue_) {
      return setDone();
    } else if (value == value_) {
      return true;
    }

    ValueType upperValue = (value >> numLowerBits_);
    ValueType upperSkip = upperValue - upper_.value();
    // The average density of ones in upper bits is 1/2.
    // LIKELY here seems to make things worse, even for small skips.
    if (upperSkip < 2 * kLinearScanThreshold) {
      do {
        upper_.next();
      } while (UNLIKELY(upper_.value() < upperValue));
    } else {
      upper_.skipToNext(upperValue);
    }

    iterateTo(value);
    return true;
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

bool folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::valid ( ) const

inline

Definition at line 732 of file EliasFanoCoding.h.

References folly::compression::EliasFanoCompressedListBase< Pointer >::size.

                     {
    return position() < size(); // Also checks that position() != -1.
  }

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

ValueType folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::value ( ) const

inline

Definition at line 739 of file EliasFanoCoding.h.

                          {
    DCHECK(valid());
    return value_;
  }

Member Data Documentation

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

constexpr ValueType folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::kInvalidValue

staticprivate

Initial value:

=
      std::numeric_limits<ValueType>::max()

Definition at line 746 of file EliasFanoCoding.h.

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

constexpr size_t folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::kLinearScanThreshold = 8

staticprivate

Definition at line 777 of file EliasFanoCoding.h.

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

ValueType folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::lastValue_

private

Definition at line 783 of file EliasFanoCoding.h.

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

const uint8_t* folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::lower_

private

Definition at line 780 of file EliasFanoCoding.h.

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

uint8_t folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::numLowerBits_

private

Definition at line 784 of file EliasFanoCoding.h.

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

SizeType folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::size_

private

Definition at line 781 of file EliasFanoCoding.h.

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

detail::UpperBitsReader<Encoder, Instructions, SizeType> folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::upper_

private

Definition at line 779 of file EliasFanoCoding.h.

template<class Encoder , class Instructions = instructions::Default, bool kUnchecked = false, class SizeType = size_t>

ValueType folly::compression::EliasFanoReader< Encoder, Instructions, kUnchecked, SizeType >::value_ = kInvalidValue

private

Definition at line 782 of file EliasFanoCoding.h.

---

The documentation for this class was generated from the following file:

• proxygen/folly/folly/experimental/EliasFanoCoding.h