foedus::storage::array::LookupRouteFinder Class Reference

Packages logic and required properties to calculate LookupRoute in array storage from offset. More...

Detailed Description

Packages logic and required properties to calculate LookupRoute in array storage from offset.

This class is completely header-only, immutable, and also a POD.

Optimization

This class uses efficient division to determine the route. We originally used simple std::lldiv(), which caused 20% of CPU cost in read-only experiment. wow. The code below now costs only 6%.

Definition at line 86 of file array_route.hpp.

#include <array_route.hpp>

Public Member Functions
	LookupRouteFinder ()
	LookupRouteFinder (uint8_t levels, uint16_t payload_size)
LookupRoute	find_route (ArrayOffset offset) const __attribute__((always_inline))
LookupRoute	find_route_and_switch (ArrayOffset offset, ArrayOffset *page_starts, ArrayOffset *page_ends) const __attribute__((always_inline))
	find_route() plus calculates where page switches. More...
uint8_t	get_levels () const __attribute__((always_inline))
uint16_t	get_records_in_leaf () const __attribute__((always_inline))

Constructor & Destructor Documentation

foedus::storage::array::LookupRouteFinder::LookupRouteFinder ( )

inline

Definition at line 88 of file array_route.hpp.

  : levels_(0),
    records_in_leaf_(0),
    leaf_fanout_div_(1),
    interior_fanout_div_(1) {
  }

foedus::storage::array::LookupRouteFinder::LookupRouteFinder ( uint8_t  levels, uint16_t  payload_size  )

inline

Definition at line 94 of file array_route.hpp.

    : levels_(levels),
      records_in_leaf_(to_records_in_leaf(payload_size)),
      leaf_fanout_div_(records_in_leaf_),
      interior_fanout_div_(kInteriorFanout) {
  }

Member Function Documentation

LookupRoute foedus::storage::array::LookupRouteFinder::find_route ( ArrayOffset  offset ) const

inline

Definition at line 134 of file array_route.hpp.

References ASSERT_ND, foedus::assorted::ConstDiv::div64(), foedus::storage::array::kInteriorFanout, foedus::storage::array::LookupRoute::route, and foedus::storage::array::LookupRoute::word.

Referenced by foedus::storage::array::ArrayStoragePimpl::lookup_for_read(), foedus::storage::array::ArrayStoragePimpl::lookup_for_read_batch(), foedus::storage::array::ArrayStoragePimpl::lookup_for_write(), and foedus::storage::array::ArrayStoragePimpl::lookup_for_write_batch().

                                                                         {
  LookupRoute ret;
  ret.word = 0;
  ArrayOffset old = offset;
  offset = leaf_fanout_div_.div64(offset);
  ret.route[0] = old - offset * records_in_leaf_;
  for (uint8_t level = 1; level < levels_ - 1; ++level) {
    old = offset;
    offset = interior_fanout_div_.div64(offset);
    ret.route[level] = old - offset * kInteriorFanout;
  }
  if (levels_ > 1) {
    // the last level is done manually because we don't need any division there
    ASSERT_ND(offset < kInteriorFanout);
    ret.route[levels_ - 1] = offset;
  }

  return ret;
}

Here is the call graph for this function:

Here is the caller graph for this function:

LookupRoute foedus::storage::array::LookupRouteFinder::find_route_and_switch ( ArrayOffset  offset, ArrayOffset *  page_starts, ArrayOffset *  page_ends  ) const

inline

find_route() plus calculates where page switches.

Parameters

[in]	offset	array offset
[out]	page_starts	minimal offset that belongs to the same page as the given offset
[out]	page_ends	minimal offset that belongs to a page different from the given offset

Invariant

page_starts <= offset < page_ends

(page_starts / records_in_leaf_) == (offset / records_in_leaf_)

(page_ends / records_in_leaf_) == (offset / records_in_leaf_) + 1

page_starts % records_in_leaf_ == 0 && page_ends % records_in_leaf_ == 0

Using the additional outputs, the caller can avoid re-calculating route if the offset is within page_starts and page_ends. This is currently used in ArrayComposer.

Definition at line 154 of file array_route.hpp.

References ASSERT_ND, foedus::assorted::ConstDiv::div64(), foedus::storage::array::kInteriorFanout, foedus::storage::array::LookupRoute::route, and foedus::storage::array::LookupRoute::word.

                                {
  LookupRoute ret;
  ret.word = 0;
  ArrayOffset old = offset;
  offset = leaf_fanout_div_.div64(offset);
  *page_starts = offset * records_in_leaf_;
  *page_ends = *page_starts + records_in_leaf_;
  ret.route[0] = old - (*page_starts);
  for (uint8_t level = 1; level < levels_ - 1; ++level) {
    old = offset;
    offset = interior_fanout_div_.div64(offset);
    ret.route[level] = old - offset * kInteriorFanout;
  }
  if (levels_ > 1) {
    // the last level is done manually because we don't need any division there
    ASSERT_ND(offset < kInteriorFanout);
    ret.route[levels_ - 1] = offset;
  }

  return ret;
}

Here is the call graph for this function:

uint8_t foedus::storage::array::LookupRouteFinder::get_levels ( ) const

inline

Definition at line 121 of file array_route.hpp.

{ return levels_; }

uint16_t foedus::storage::array::LookupRouteFinder::get_records_in_leaf ( ) const

inline

Definition at line 122 of file array_route.hpp.

Referenced by foedus::storage::array::ArrayComposeContext::ArrayComposeContext(), foedus::storage::array::ArrayComposer::construct_root(), foedus::storage::array::ArrayStoragePimpl::load_empty(), and foedus::storage::array::ArrayStoragePimpl::prefetch_pages_recurse().

{ return records_in_leaf_; }

Here is the caller graph for this function:

---

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

• /home/shino/foedus_code/foedus-core/include/foedus/storage/array/array_route.hpp