foedus::cache::HashFunc Struct Reference

A simple hash function logic used in snasphot cache. More...

Detailed Description

A simple hash function logic used in snasphot cache.

The hash key is SnapshotPagePointer, whose least significant bits are local page IDs, which are sequnetial. To avoid placing adjacent page IDs in adjacent hash buckets, we use byte-swap and a few bit shifts, then divide by logical table size which is adjusted to an almost-prime number.

Definition at line 90 of file cache_hashtable.hpp.

#include <cache_hashtable.hpp>

Collaboration diagram for foedus::cache::HashFunc:

Public Member Functions
	HashFunc (BucketId physical_buckets)
BucketId	get_bucket_number (storage::SnapshotPagePointer page_id) const __attribute__((always_inline))
	Returns a bucket number the given snapshot page ID should belong to. More...

Static Public Member Functions
static uint32_t	get_hash (storage::SnapshotPagePointer page_id) __attribute__((always_inline))
	Returns a hash value for the given snapshot page ID. More...
static PageIdTag	get_tag (storage::SnapshotPagePointer page_id) __attribute__((always_inline))
	Returns another hash value used to differentiate IDs with similar hash values. More...

Public Attributes
const BucketId	logical_buckets_
	Number of logical (actually used) buckets in this table. More...
const BucketId	physical_buckets_
	Number of buckets that are physically allocated, at least kHopNeighbors more than logical. More...
const assorted::ConstDiv	bucket_div_
	to efficiently divide a number by bucket_div_. More...

Friends
std::ostream &	operator<< (std::ostream &o, const HashFunc &v)

Constructor & Destructor Documentation

foedus::cache::HashFunc::HashFunc ( BucketId  physical_buckets )

explicit

Definition at line 60 of file cache_hashtable.cpp.

  : logical_buckets_(determine_logical_buckets(physical_buckets)),
    physical_buckets_(physical_buckets),
    bucket_div_(logical_buckets_) {
}

Member Function Documentation

BucketId foedus::cache::HashFunc::get_bucket_number ( storage::SnapshotPagePointer  page_id ) const

inline

Returns a bucket number the given snapshot page ID should belong to.

Definition at line 110 of file cache_hashtable.hpp.

References ASSERT_ND, foedus::assorted::ConstDiv::div32(), get_hash(), and foedus::assorted::ConstDiv::rem32().

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

                                                                                     {
    uint32_t seed = get_hash(page_id);
    uint32_t quotient = bucket_div_.div32(seed);
    uint32_t bucket = bucket_div_.rem32(seed, logical_buckets_, quotient);
    ASSERT_ND(bucket == seed % logical_buckets_);
    return bucket;
  }

Here is the call graph for this function:

Here is the caller graph for this function:

uint32_t foedus::cache::HashFunc::get_hash ( storage::SnapshotPagePointer  page_id )

inlinestatic

Returns a hash value for the given snapshot page ID.

This needs no member variables.

Definition at line 384 of file cache_hashtable.hpp.

References foedus::storage::extract_local_page_id_from_snapshot_pointer(), foedus::storage::extract_numa_node_from_snapshot_pointer(), and foedus::storage::extract_snapshot_id_from_snapshot_pointer().

Referenced by get_bucket_number().

                                                                     {
  uint16_t snapshot_id = storage::extract_snapshot_id_from_snapshot_pointer(page_id);
  uint8_t numa_node = storage::extract_numa_node_from_snapshot_pointer(page_id);
  uint64_t local_page_id = storage::extract_local_page_id_from_snapshot_pointer(page_id);
  // snapshot_id is usually very sparse. and has no correlation with local_page_id.
  // numa_node too. thus just use them as seeds for good old multiplicative hashing.
  uint32_t seed = snapshot_id * 0x5a2948074497175aULL;
  seed += numa_node * 0xc30a95f6e63dd908ULL;

  // local_page_id is 40 bits. 32-40 bits are very sparse, and it has no correlation with
  // other bits (how come 4kb-th page and 16Tb+4kb-th page has anything in common..).
  // so, let's treat it with another multiplicative.
  uint8_t highest_bits = static_cast<uint8_t>(local_page_id >> 32);
  uint32_t folded_local_page_id = local_page_id + highest_bits * 0xd3561f5bedac324cULL;

  // now, we don't want to place adjacent pages in adjacent hash buckets. so, let's swap bytes.
  // this benefits hop-scotch hashing table.
  uint32_t swaped_page_id = __builtin_bswap32(folded_local_page_id);
  seed ^= swaped_page_id;
  return seed;
}

Here is the call graph for this function:

Here is the caller graph for this function:

PageIdTag foedus::cache::HashFunc::get_tag ( storage::SnapshotPagePointer  page_id )

inlinestatic

Returns another hash value used to differentiate IDs with similar hash values.

Definition at line 406 of file cache_hashtable.hpp.

Referenced by foedus::cache::CacheHashtable::find(), foedus::cache::CacheHashtable::find_batch(), and foedus::cache::CacheHashtable::install().

                                                                     {
  PageIdTag high_bits = static_cast<PageIdTag>(page_id >> 32);
  PageIdTag tag = high_bits * 0x8e1d76486c3e638dULL + static_cast<PageIdTag>(page_id);
  if (tag == 0) {
    tag = 1;  // we avoid 0 as a valid value. this enables sanity checks.
  }
  return tag;
}

Here is the caller graph for this function:

Friends And Related Function Documentation

std::ostream& operator<< ( std::ostream &  o, const HashFunc &  v  )

friend

Definition at line 332 of file cache_hashtable.cpp.

                                                         {
  o << "<HashFunc>"
    << "<logical_buckets_>" << v.logical_buckets_ << "<logical_buckets_>"
    << "<physical_buckets_>" << v.physical_buckets_ << "<physical_buckets_>"
    << "</HashFunc>";
  return o;
}

Member Data Documentation

const assorted::ConstDiv foedus::cache::HashFunc::bucket_div_

to efficiently divide a number by bucket_div_.

Definition at line 96 of file cache_hashtable.hpp.

const BucketId foedus::cache::HashFunc::logical_buckets_

Number of logical (actually used) buckets in this table.

Definition at line 92 of file cache_hashtable.hpp.

Referenced by foedus::cache::CacheHashtable::get_logical_buckets(), and foedus::cache::operator<<().

const BucketId foedus::cache::HashFunc::physical_buckets_

Number of buckets that are physically allocated, at least kHopNeighbors more than logical.

Definition at line 94 of file cache_hashtable.hpp.

Referenced by foedus::cache::CacheHashtable::get_physical_buckets(), and foedus::cache::operator<<().

---

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

• /home/shino/foedus_code/foedus-core/include/foedus/cache/cache_hashtable.hpp
• /home/shino/foedus_code/foedus-core/src/foedus/cache/cache_hashtable.cpp