# The time table

A time table is an in-memory structure that tracks the frequence of arbitrary
values across time. It does so by keeping counts in a static array where columns
are timestamp [lib/time] buckets and rows are keyed to those arbitrary values.

This table is designed to be static, which means that when there's not enough
space for a new keyed value, we need to pop one out.

This structure is mostly designed to be used in conjunction with [io/log].

The time buckets are:

* last minute
* last 10 minutes
* last hour
* last day
* last week
* all time

Except at exact "rollover" interval moments, it's not possible to have an exact
count for each buckets without having a complete list of occurrences (which we
don't keep around). Therefore, these statistics are an approximation, which
works as described below.

We keep two separate counts for each of those buckets. One for the "current
period" and one for the "previous period". Each time an event occurs, we
increase counts in all "current" buckets".

Each time that a particular period passes, we copy the current period's value to
the "previous period" bucket and reset the current period to 0. When comes the
time to display the value, we add the two values and divide it to the prorata of
the elapsed time. For example, if we're 30 seconds into the minute and "current"
has 8 hits and "previous" has 20, then we display (20+(8*2))/2, which is 18.

We keep track of rollover moments with two counters: initial timestamp and
rollover count. Before each counter increase or before we want to display stats,
we check the timestamp. If "now - timestamp / 60" is bigger than the rollover
count, then we rollover the "last minute" bucket, then increase the rollover
count.

Then is the time to check for the other buckets, which are all multiples of
minutes. Therefore, we check if the rollover count is divisible by that amount
(for example, "10" for "last 10 minutes" "60" for "last hour" etc.). When it is,
we rollover.

## What happens when the table is full

When we add a hit for a value that doesn't exist in the table at a time when the
table is already full, we locate the bucket with the smallest "all time" count
and we remove it in order to make space for the newcomer.

So far, so good, except that finding the lowest element in an unsorted bucket
list is a relatively expensive operation. If it happens once in a while, sure,
no problem, but if for example the table is stuck in a loop where multiple small
items "fight" for a spot, then each hit becomes expensive and it can slow down
the system as a whole.

One solution could be to maintain an index of buckets sorted by hits, but that
would be complex and also probably event more expensive (each hit has to check
if we change the index).

Instead, what we do is twofold: First, remember what the latest added element
is. Second, whenever we do the expensive "find lowest count" operation, we
remember what that count was.

Then, when comes the time to free some space, we check whether the count of the
latest element is smaller or equal to the "lowest count" figure. If it is, no
need for an expensive check, we already know what to pop out. Otherwise, do the
expensive check.

## Example usage

  needs mem/timetbl
  32 newtimetbl const mytbl \ 32 rows
  42 mytbl hit
  54 mytbl hit
  \ Add a whole lot of hits over a long time period
  mytbl .timetbl \ pretty print those stats

## API

### Constants

BUCKETCNT  6. The number of buckets in our time series (last minute, etc..)
INTERVAL   60. Base rollover interval, in seconds.
MUTIPLIERS Array of INTERVAL multipliers that represent the time inverval of
           each of the BUCKETCNT buckets.

### Structures

struct TimeTable {
  uint rowcnt ts rollovercnt lastidx lowesthits fmtvalwidth ;
  smethod fmtval ( n -- a u )
  [void,0] buf( ;
}

rowcnt       The number of rows in this tables.
ts           Timestamp of the last rollover.
rollovercnt  Number of rollovers that happened so far.
lastidx      Index of last item to be added to the table.
lowesthits   Lowest all times hits of the table when an item was last added.
fmtvalwidth  The maximum number of character that a given key can print in a
             table listing. Defaults to 8.
fmtval       The routine to call when printing a value in a listing.
             Defaults to "formathex"
buf(         Table data. First, an array of "rowcnt" uints for values, then
             the rows themselves, an array of uints each BUCKETCNT*8 bytes in
             size. That is, each bucket has a "current" and a "prev" counter.
             Each row is organized where all "current" uints come first, then
             all "prev" uints follow. A row is considered "free" when its all
             time count is 0.

### Words

newtimetbl ( nrows -- tbl )
  Create a new time table with the specified number of rows.

hitat ( value timestamp tbl -- )
  Add a count for specified value at a specified timestamp in specified table.
  Most of the time, you'll use "hit" instead of "hitat", but this word can be
  useful in tests or when "replaying" a log of previous hits.

  A time table expects "timestamp" to be equal or higher than the previous value
  it received

hit ( value tbl -- )
  Shortcut for "now swap hitat".

hitbucketat ( idx timestamp tbl -- )
  Same as "hit" except that we refer to a bucket index rather than a value.
  Using this word bypasses the value indexing mechanism.

hitbucket ( idx tbl -- )
  Shortcut for "now swap hitbucketat".

?rolloverat ( timestamp tbl -- )
  If we consider that the "now" time of the bucket list is "timestamp", do all
  necessary rollovers to bring the stats up to speed.

  This process is implicitely done in "hitat". The purpose of this word is to
  be called before printing stats.

?rollover ( tbl -- )
  Shortcut for "now swap ?rolloverat"

sorttbl ( colidx tbl -- ... n minhits )
  In a static buffer (allocated with [mem/reuse], so we always have enough space
  regardless of "tbl" size), sort buckets according to the hits in the specified
  column index (0=last minute, 5-all times).


  Then, yield the index of each bucket in that order, the biggest one on top of
  PS.

  On top of it all, yield the "hit" value of the bottom (lowest value) element.

.timetbl ( tbl -- )
  Do a pretty printing of the table, sorted by all time hits.

  Does not do a implicit rollover.

.sortedtimetbl ( ... n tbl -- )
  Like .timetbl, but instead uses the index order from "sorttbl".

### Private words

bucket ( idx tbl -- bucket )
  Yield the address of the bucket at specified index. Aborts if index is bigger
  than "rowcnt". The yielded address has the structure described in
  BucketList.buf(.

validx ( value tbl -- ?idx f )
  Yield the index of specified value in the table. f=1 and idx is present when
  value if found. f=0 and idx is absent when value is not found.

freebucket ( tbl -- idx bucket )
  Find a free bucket, pushing one out if necessary.

valbucket ( value tbl -- bucket )
  Yield a bucket for specified value. When value isn't in the table, find a free
  bucket for it. If the table is full, free the bucket with the least "all
  times" hit count, zero it out and yield it.

prorate ( value progress total -- n )
  Compute a pro-rated value according to the progress made in the specified
  scale of "total" units.

retrorate ( value progress total -- n )
  Reverse pro-rating, that is, the more progress is made, the less the value is.

progress ( columnidx tbl -- progress total )
  For a given column index (1="last 10 minutes", 4="last week"), yield the
  progress into the time period of table's rollovercnt for use with "retrorate".

  Note that for the "last minute" column, current timestamp should be used
  instead, otherwise we always get a progress of 100%.
