foedus::assorted::ConstDiv Struct Reference

The pre-calculated p-m pair for optimized integer division by constant. More...

Detailed Description

The pre-calculated p-m pair for optimized integer division by constant.

This object implements the optimized integer division described in [HACKER] Chap 10. We assume the divisor is within 32bit and dividee is either 32bit or 64bit. This is a bit different assumption from existing library; libdivide.

Usecases

This is used in places where integer division by a constant integer is the bottleneck. So far the only such place is partitioning and array storage (Array Storage). In read-only experiments on array storage, we did observe more than 20% overhead in std::lldiv(). It's a division by fan-out, so of course we can afford to pre-calculate p and m. Hence, we added this object.

Example

For example, use it as follows.

ConstDiv div(254);  // to divide by constant 254. This object should be precalculated.
std::cout << "0x12345678/254=" << div.div32(0x12345678) << std::endl;
std::cout << "0x123456789ABCDEF/254=" << div.div64(0x123456789ABCDEFULL) << std::endl;

Etc

This object is totally header-only. This object is totally immutable, so . This object is POD and can trivially copy/move.

References

For more details, read the following:

• [HACKER] "Hacker's delight 2nd ed." If you don't own a copy, you are not a real programmer.
• [libdivide] https://github.com/ridiculousfish/libdivide
• [libdivide-pdf] http://ridiculousfish.com/files/faster_unsigned_division_by_constants.pdf

Definition at line 67 of file const_div.hpp.

#include <const_div.hpp>

Public Types
enum	Constants { kFlagPowerOfTwo = 0x01, kFlagAdd32 = 0x02, kFlagAdd64 = 0x04 }

Public Member Functions
	ConstDiv (uint32_t d)
	Pre-calculate the p-m pair for the given divisor. More...
	ConstDiv ()
void	init (uint32_t d)
uint32_t	div32 (uint32_t n) const
	32-bit integer division that outputs both quotient and remainder. More...
uint32_t	rem32 (uint32_t n, uint32_t d, uint32_t q) const
	Calculate remainder. More...
uint64_t	div64 (uint64_t n) const
	64-bit integer division that outputs both quotient and remainder. More...
uint32_t	rem64 (uint64_t n, uint32_t d, uint64_t q) const
	Calculate remainder. More...

Public Attributes
uint8_t	d_highest_bits_
	Highest bits to represent d. More...
uint8_t	shift32_
	"s" for 32 bit division. More...
uint8_t	shift64_
	"s" for 64 bit division. More...
uint8_t	flags_
	misc flags. More...
uint32_t	magic32_
	magic number for 32 bit division. More...
uint64_t	magic64_
	magic number for 64 bit division. More...
uint32_t	d_
	Oridinal divisor. More...
uint32_t	dummy_

Member Enumeration Documentation

enum foedus::assorted::ConstDiv::Constants

Enumerator
kFlagPowerOfTwo	Whether the divisor is a power of 2. When this flag is on, we just shift bits.
kFlagAdd32	Add inidicator for 32bit division.
kFlagAdd64	Add inidicator for 64bit division.

Definition at line 68 of file const_div.hpp.

                 {
    kFlagPowerOfTwo = 0x01,
    kFlagAdd32 = 0x02,
    kFlagAdd64 = 0x04,
  };

Constructor & Destructor Documentation

foedus::assorted::ConstDiv::ConstDiv ( uint32_t  d )

inlineexplicit

Pre-calculate the p-m pair for the given divisor.

Parameters

[in]

d

divisor

Definition at line 81 of file const_div.hpp.

References init().

                                {
    init(d);
  }

Here is the call graph for this function:

foedus::assorted::ConstDiv::ConstDiv ( )

inline

Definition at line 85 of file const_div.hpp.

References init().

             {
    init(1);
  }

Here is the call graph for this function:

Member Function Documentation

uint32_t foedus::assorted::ConstDiv::div32 ( uint32_t  n ) const

inline

32-bit integer division that outputs both quotient and remainder.

Parameters

[in]

n

dividee

Returns

quotient

Calculation of remainder is separated below. If the caller calls the two functions in a row, I believe compiler is smart enough to get rid of extra multiplication.

Definition at line 228 of file const_div.hpp.

References d_highest_bits_, flags_, kFlagAdd32, kFlagPowerOfTwo, magic32_, and shift32_.

Referenced by div64(), and foedus::cache::HashFunc::get_bucket_number().

                                                {
  if (flags_ & kFlagPowerOfTwo) {
    return n >> d_highest_bits_;
  } else {
    uint64_t product = static_cast<uint64_t>(n) * magic32_;
    uint32_t quotient = static_cast<uint32_t>(product >> 32);
    if (flags_ & kFlagAdd32) {
      quotient += (n - quotient) >> 1;
    }
    return quotient >> shift32_;
  }
}

Here is the caller graph for this function:

uint64_t foedus::assorted::ConstDiv::div64 ( uint64_t  n ) const

inline

64-bit integer division that outputs both quotient and remainder.

Parameters

[in]

n

dividee

Returns

quotient

Definition at line 241 of file const_div.hpp.

References ASSERT_ND, d_highest_bits_, div32(), flags_, kFlagAdd64, kFlagPowerOfTwo, magic64_, and shift64_.

Referenced by foedus::storage::array::LookupRouteFinder::find_route(), foedus::storage::array::LookupRouteFinder::find_route_and_switch(), and foedus::storage::array::ArrayPartitioner::partition_batch().

                                                {
  if (flags_ & kFlagPowerOfTwo) {
    return n >> d_highest_bits_;
  }

  if (n < (1ULL << 32)) {
    // cheap case
    return div32(static_cast<uint32_t>(n));
  }

  ASSERT_ND(n >= (1ULL << 32));
  // At least GCC and clang supports __uint128_t
  __uint128_t product = static_cast<__uint128_t>(n) * magic64_;
  uint64_t quotient = static_cast<uint64_t>(product >> 64);
  if (flags_ & kFlagAdd64) {
    quotient += (n - quotient) >> 1;
  }
  return quotient >> shift64_;
}

Here is the call graph for this function:

Here is the caller graph for this function:

void foedus::assorted::ConstDiv::init ( uint32_t  d )

inline

Definition at line 137 of file const_div.hpp.

References ASSERT_ND, d_, d_highest_bits_, dummy_, flags_, kFlagAdd32, kFlagAdd64, kFlagPowerOfTwo, magic32_, magic64_, shift32_, and shift64_.

Referenced by ConstDiv().

                                     {
  // this one is inlined just to avoid multiple-definition, not for performance.
  ASSERT_ND(d);
  d_highest_bits_ = 31 - __builtin_clz(d);  // TASK(Hideaki): non-GCC support
#ifndef NDEBUG
  d_ = d;
  dummy_ = 0;
#endif  // NDEBUG

  // power of 2 is a bit special.
  if ((d & (d - 1)) == 0) {
    ASSERT_ND(d == (1U << d_highest_bits_));
    shift32_ = 0;
    shift64_ = 0;
    flags_ = kFlagPowerOfTwo;
    magic32_ = 0;
    magic64_ = 0;
    return;
  }

  flags_ = 0;

  // calculate 32bit/64bit magic numbers and add indicator, this part is based on [libdivide-pdf]
  // rather than [HACKERS] although it is also based on [HACKERS].
  {
    shift32_ = d_highest_bits_;
    uint32_t m = (1ULL << (32 + d_highest_bits_)) / d;
    uint32_t rem = (1ULL << (32 + d_highest_bits_)) % d;
    ASSERT_ND(rem > 0 && rem < d);
    uint32_t e = d - rem;
    if (e >= (1U << d_highest_bits_)) {
      // we have add indicator (2^W <= M < 2^(W+1), m = M - 2^W).
      // here is a nice idea in libdivide.
      // We let it overflow, but we do so for remainder too, thus even with overflow
      // we can correctly calculate the quotient!
      // We use the magic number for this case with divide-by-2 in div32 to account for this.
      flags_ |= kFlagAdd32;
      m *= 2;
      uint32_t twice_rem = rem * 2;
      if (twice_rem >= d || twice_rem < rem) {
        ++m;
      }
    }
    magic32_ = m + 1;
  }

  // then 64bit version.
  {
    shift64_ = d_highest_bits_;
    // At least GCC and clang supports __uint128_t
    __uint128_t numer = 1;
    numer <<= 64 + d_highest_bits_;
    uint64_t m = numer / d;
    uint32_t rem = numer % d;
    ASSERT_ND(rem > 0 && rem < d);
    uint32_t e = d - rem;
    if (e >= (1ULL << d_highest_bits_)) {
      flags_ |= kFlagAdd64;
      m *= 2;
      uint32_t twice_rem = rem * 2;
      if (twice_rem >= d || twice_rem < rem) {
        ++m;
      }
    }
    magic64_ = m + 1;
  }
}

Here is the caller graph for this function:

uint32_t foedus::assorted::ConstDiv::rem32 ( uint32_t  n, uint32_t  d, uint32_t  q  ) const

inline

Calculate remainder.

Definition at line 205 of file const_div.hpp.

References ASSERT_ND, d_, d_highest_bits_, flags_, and kFlagPowerOfTwo.

Referenced by foedus::cache::HashFunc::get_bucket_number().

                                                                        {
#ifndef NDEBUG
  ASSERT_ND(d == d_);
#endif  // NDEBUG
  ASSERT_ND(n / d == q);
  if (flags_ & kFlagPowerOfTwo) {
    return n & ((1 << d_highest_bits_) - 1);
  } else {
    return n - d * q;
  }
}

Here is the caller graph for this function:

uint32_t foedus::assorted::ConstDiv::rem64 ( uint64_t  n, uint32_t  d, uint64_t  q  ) const

inline

Calculate remainder.

Definition at line 216 of file const_div.hpp.

References ASSERT_ND, d_, d_highest_bits_, flags_, and kFlagPowerOfTwo.

                                                                        {
#ifndef NDEBUG
  ASSERT_ND(d == d_);
#endif  // NDEBUG
  ASSERT_ND(n / d == q);
  if (flags_ & kFlagPowerOfTwo) {
    return n & ((1ULL << d_highest_bits_) - 1ULL);
  } else {
    return n - d * q;
  }
}

Member Data Documentation

uint32_t foedus::assorted::ConstDiv::d_

Oridinal divisor.

For sanity check.

Definition at line 132 of file const_div.hpp.

Referenced by init(), rem32(), and rem64().

uint8_t foedus::assorted::ConstDiv::d_highest_bits_

Highest bits to represent d.

2^(d_highest_bits_) <= d < 2^(d_highest_bits_+1).

Definition at line 113 of file const_div.hpp.

Referenced by div32(), div64(), init(), rem32(), and rem64().

uint32_t foedus::assorted::ConstDiv::dummy_

Definition at line 133 of file const_div.hpp.

Referenced by init().

uint8_t foedus::assorted::ConstDiv::flags_

misc flags.

Definition at line 122 of file const_div.hpp.

Referenced by div32(), div64(), init(), rem32(), and rem64().

uint32_t foedus::assorted::ConstDiv::magic32_

magic number for 32 bit division.

Definition at line 125 of file const_div.hpp.

Referenced by div32(), and init().

uint64_t foedus::assorted::ConstDiv::magic64_

magic number for 64 bit division.

Definition at line 128 of file const_div.hpp.

Referenced by div64(), and init().

uint8_t foedus::assorted::ConstDiv::shift32_

"s" for 32 bit division.

Definition at line 116 of file const_div.hpp.

Referenced by div32(), and init().

uint8_t foedus::assorted::ConstDiv::shift64_

"s" for 64 bit division.

Definition at line 119 of file const_div.hpp.

Referenced by div64(), and init().

---

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

• /home/shino/foedus_code/foedus-core/include/foedus/assorted/const_div.hpp