rlogc

Documentation

Overview

A simple, non-synchronized RlogC implementation.

A simple, non-synchronized RlogC implementation.

Index

• func F(n float64) float64
• func GetDecayFromHalfLife(HL int64) float64
• type Element
  • func (e *Element) Evict()
  • func (e *Element) Promote()
• type HC
  • func (hc *HC) Access(now int64, decay float64)
  • func (a *HC) Compare(b *HC, decay float64) int
  • func (hc *HC) Enter(now int64, decay float64)
• type RlogcHeap
  • func (r *RlogcHeap) BorrowElements() []*Element
  • func (r *RlogcHeap) Enter(e *Element)
  • func (r *RlogcHeap) EvictNode() (e *Element)
  • func (r *RlogcHeap) Len() int
  • func (r *RlogcHeap) StealElements() []*Element
• type Timer

Functions

func F

func F(n float64) float64

This function increments n logarithmically.

This function computes (in a mathematical sense):

f(n) = log(exp(n)+1)

However, to prevent floating point overflows, this function, its implementation exploits the following rule:

f(n) = n + f(-n)

Which can be proven as follows:

f(n) = log(exp(n)+1)
f(n) = log(exp(n)+exp(0))
f(n) = log(exp(n-n)+exp(0-n))+n
f(n) = log(exp(0)+exp(-n))+n
f(n) = log(1+exp(-n))+n
f(n) = n + log(exp(-n)+1)
f(n) = n + f(-n)

The function is implemented as

f(n) = max(0,n) + log(exp(-abs(n))+1)

Which is correct because:

max(0,n) = 0 IF n<0
-abs(n)  = n IF n<0

max(0,n) = n IF n>0
-abs(n) = -n IF n>0

max(0,n) = -abs(n) = 0 IF n = 0

func GetDecayFromHalfLife

func GetDecayFromHalfLife(HL int64) float64

Calculates the decay value for a given Half-life time.

Half-life (symbol t½) is the time required for a quantity to reduce to half of its initial value. See also: https://en.wikipedia.org/wiki/Half-life

The time unit of HL is the same as the time unit of the Timer in use.

For example, if you want to have a Half-life time of one hour, and your Timer increments once every second - thus the time unit of your Timer is one second - you must specify the number of seconds of this hour: 3600. However, if your Timer's time unit is one millisecond, you must specify the number of milliseconds within an hour (3600000) in order to get a Half-life time of one hour.

Types

type Element

type Element struct {
	UserData [2]unsafe.Pointer
	// contains filtered or unexported fields
}

Cache-Element.

func (*Element) Evict

func (e *Element) Evict()

Evicts the node from the RlogcHeap containing it.

func (*Element) Promote

func (e *Element) Promote()

A cache-hit on this element.

type HC

type HC struct {
	LogC float64
	Time int64
}

func (*HC) Access

func (hc *HC) Access(now int64, decay float64)

Decays the counter and increments it.

If the decay factor is 0.9, then:

decay = log(0.9)

func (*HC) Compare

func (a *HC) Compare(b *HC, decay float64) int

Compares a and b and returns:

1  if a>b
-1 if a<b
0  otherwise

If the decay factor is 0.9, then:

decay = log(0.9)

func (*HC) Enter

func (hc *HC) Enter(now int64, decay float64)

Initializes the counter LogC = log(1) and the Time = now. Called, when an entry enters the cache.

If the decay factor is 0.9, then:

decay = log(0.9)

type RlogcHeap

type RlogcHeap struct {
	Decay float64
	Timer Timer
	// contains filtered or unexported fields
}

func (*RlogcHeap) BorrowElements

func (r *RlogcHeap) BorrowElements() []*Element

Borrows the priority queue. DANGEROUS! Handle with care!

func (*RlogcHeap) Enter

func (r *RlogcHeap) Enter(e *Element)

Enters a node to the heap.

func (*RlogcHeap) EvictNode

func (r *RlogcHeap) EvictNode() (e *Element)

Evicts the least recently/frequently used element and returns it.

func (*RlogcHeap) Len

func (r *RlogcHeap) Len() int

Returns the number of elements on the heap.

func (*RlogcHeap) StealElements

func (r *RlogcHeap) StealElements() []*Element

Borrows the priority queue. DANGEROUS! Handle with care!

type Timer

type Timer func() int64

A function that returns a monotinically increasing 64-bit integer.