Implements a probabilistic counter [Morris 1978]. More...

Detailed Description

Implements a probabilistic counter [Morris 1978].

The major user is HCC's temperature field maintained in each page header.

[Morris 1987] Robert Morris, Counting large numbers of events in small registers, Commun. ACM 21, 10 (October 1978), 840-842.

Unlike the paper, we do much simpler thing. We just compare with power of two, so that we don't need exp/log. No information stored in static/global whatever.

Definition at line 37 of file prob_counter.hpp.

#include <prob_counter.hpp>

Public Member Functions
	ProbCounter ()

void	reset ()

void	increment (UniformRandom *rnd)

void	decrement_force ()

Public Attributes
uint8_t	value_
	Log arithmic counter of aborts. More...

Constructor & Destructor Documentation

foedus::assorted::ProbCounter::ProbCounter ( )

inline

Definition at line 45 of file prob_counter.hpp.

References ASSERT_ND.

                 : value_(0) {
     ASSERT_ND(sizeof(uint8_t) == sizeof(ProbCounter));
   }

Member Function Documentation

void foedus::assorted::ProbCounter::decrement_force ( )

inline

Definition at line 69 of file prob_counter.hpp.

References value_.

                                 {
     --value_;
   }

void foedus::assorted::ProbCounter::increment ( UniformRandom * rnd )

inline

Definition at line 51 of file prob_counter.hpp.

References foedus::assorted::UniformRandom::next_uint32(), and value_.

Referenced by foedus::xct::RwLockableXctId::hotter().

                                             {
     // We increment the value_ for exponentially smaller probability.
     // value_==0: always
     // value_==1: 50% chance
     // value_==2: 25% chance... etc
     // We can implement this by simple bit-shifts.
 
     // Extract middle 24-bits, which is typically done in hashing. This is kinda hashing too.
     // This also means the following makes sense only for value_<=24. Should be a reasonable assmp.
     const uint32_t int_val = rnd->next_uint32();
     const uint32_t int24_val = (int_val >> 4) & 0xFFFFFFU;
     const uint32_t threshold = 1U << (24 - value_);
     if (int24_val < threshold) {
       ++value_;
     }
   }