Look-up tables
VSlib provides a functonality of a look-up table intended for all uses where trading memory consumption for execution time may be favourable. The prime use-case example are the relatively expensive trigonometrical functions, like sine or cosine. However, the look-up tables can be useful whenever the calculation time can be significant, and longer than the look-up time and interpolation, see the performance section.
General interface
VSlib has two Components implementing of the look-up table functionality: LookupTable and PeriodicLookupTable, and two helper Components based on the periodic type: SinLookupTable and CosLookupTable.
The LookupTable and PeriodicLookupTable are derived from the Components class and implement its interface.
They both have two template parameters, including one optional: IndexType and optional StoredType, defining the types
of the stored table types for indices and values, respectively. The StoredType is optional and does not need to be defined. By default
it will be the same type as the IndexType. All numerical scalar types are supported, e.g. double-precision float. The SinLookupTable
and CosLookupTable do not have a template parameter, and are by default double-precision float.
The LookupTable and PeriodicLookupTable require the table to be stored to be provided at construction time. To ease the interaction
with the look-up table functionality, two dedicated classes: SinLookupTable and CosLookupTable are provided for your convenience.
They internalize the function generation and only the number of points in the table has to be specified. A utility function in the VSlib is provided
to ease the equally-spaced function generation in the fgc4::utils namespace: generateFunction.
All of the Components implement a single access method: interpolate, taking one obligatory argument of the numerical scalar IndexType
with the x-value (\(input_{x}\)) of the function to be found in the stored table, with an optional boolean parameter denoting whether the access to the table
is random (true) or monotonic (false), and returns one value of numerical scalar type StoredType from the stored table.
For the highest performance, the interpolate method uses linear interpolation to calculate the returned value:
where: \(x_{input}\) is the user-defined input value, and \((x_{1}, y_{1})\) and \((x_{2}, y_{2})\) are the lower and upper edge pairs, respectively, of x-y values stored in the table, such that \(x_{1} < x_{input} < x_{2}\).
The edges, lower: \(x_{1}\) and upper: \(x_{2}\) of the so-called sector are found using one of the three methods: linear, binary,
or index-based search. The linear search uses the std::find function, with linear complexity, it is the default choice if your stored
table does not have equal-size binning and you intend to access the data in a monotonically increasing manner. The binary search is enabled
when the optional second parameter of the interpolate method is set to true. It uses the std::upper_bound binary-search
approach with logarithmic complexity. It is optimised for the case where your stored table does not have equal-size binning and you are accessing
the data in a random manner. Finally, the index search is the default if your stored table has equal binning. In that case, the optional parameter
for random access is ignored, as this approach is found to be the fastest (and deterministic) way to access the data.
Certain optimisations are undertaken, such as caching the previous sector edges and values, so that if the next requested \(x_{input}\) falls in the same sector, it does not need to be searched for again.
All classes implement a reset method that bring the objects to the initial state, resetting all cached data except for the stored table.
Look-up table
The LookupTable implements the basic look-up table functionality and the general interface described above. The constructor
accepts the vector of index-value pairs (of type std::vector<std::pair<IndexType, StoredType>>) as input, called further simply table,
and moves it to an internal structure. The table is expected to have sorted indices and is not mutable at runtime. The constructor has also
an optional boolean argument, a flag denoting whether the provided table has equal binning (true case) or not (false case).
If the flag is set to true, then the index search is always performed, regardless of the second parameter of the interpolate method.
The constant boundary conditions are enforced. That is, in case of the underflow, when the provided \(x_{input}\) is below the lowest \(x\) value of the stored table, the \(y\) value corresponding to the first element is returned, without interpolation or extrapolation. Analogically, in case of an overflow, the last \(y\) value of the table is returned.
The LookupTable provides a way to access the table’s \(y\) values by index by overriding operator[]:
RootComponent root;
LookupTable<int, double> lin_table("table", &root,
fgc4::utils::generateFunction<int, double>([](const auto x){return 2*x + 1.5;}, 0.0, 10.0, 100), true);
const auto y2 = lin_table[1]; // returns y of the second element
For more details regarding the API, see the API documentation for LookupTable.
Usage examples
#include <vector>
#include "lookupTable.h"
#include "rootComponent.h"
using namespace vslib;
void your_function(RootComponent& root)
{
// manually generated small table:
std::vector<std::pair<int, double>> values{{0, 0.5}, {2, 1.5}, {4, 2.5}, {6, 3.5}};
LookupTable<int32_t, double> table("small_table", root, std::move(values));
// interpolate inputs
auto output = table.interpolate(-1); // underflow, 0.5
output = table.interpolate(0); // 0.5
output = table.interpolate(2); // 1.5
output = table.interpolate(4); // 2.5
output = table.interpolate(7); // overflow, 3.5
// reset between not-connected uses to clear cached data
table.reset();
output = table.interpolate(1); // 1.0
output = table.interpolate(3); // 2.0
output = table.interpolate(5); // 3.0
table.reset();
// access values randomly using binary search:
output = table.interpolate(5, true); // 1.0
output = table.interpolate(3, true); // 2.0
output = table.interpolate(1, true); // 3.0
table.reset();
// access value by index:
output = table[3]; // 3.5
// access entire table by reference
const auto& table = table.getData();
return 0;
}
#include <vector>
#include "lookupTable.h"
#include "generateFunction.h"
#include "rootComponent.h"
using namespace vslib;
void your_function(RootComponent& root)
{
// automatially generated larger table in range 0 to 10.0, with 100 points:
LookupTable<double> lin_table("table", root,
fgc4::utils::generateFunction<int, double>([](const auto x){return 2*x + 1.5;}, 0.0, 10.0, 100), true);
// all access done using index-search:
auto output = lin_table.interpolate(-1); // underflow, 1.5
output = lin_table.interpolate(0, true); // flag has no effect, 1.5
output = lin_table.interpolate(11); // overflow, 21.5
// reset between not-connected uses to clear cached data
lin_table.reset();
return 0;
}
Example usage in a vloop:
#include "vslib.hpp"
namespace fgc::user
{
class Converter : public vslib::RootComponent
{
public:
Converter() noexcept
: vslib::RootComponent("example"),
interrupt_1("stg", *this, 128, vslib::InterruptPriority::high, RTTask),
table("function", *this, fgc4::utils::generateFunction<int, double>([](const auto x){return 2*x + 1.5;}, 0.0, 10.0, 100), true)
{
}
// Define your interrupts here
vslib::PeripheralInterrupt<Converter> interrupt_1;
// Define your public Components here
vslib::LookupTable<double> table;
void init() override
{
interrupt_1.start();
}
void backgroundTask() override
{
}
static void RTTask(Converter& converter)
{
// Read the input value:
const double data_x = converter.m_data[0];
const auto y = converter.table.interpolate(data_x);
// use the interpolated function value y at data_x
}
private:
// actual source of data omitted for simplicity
std::array<double, 1> m_data{0.0};
};
} // namespace fgc::user
Periodic look-up table
The PeriodicLookupTable class derives from the LookupTable and provides the same interface for all interactions, including template
parameters. All the assumptions regarding the provided table are the same as in the LookupTable class. The only difference is the behaviour
when under- and overflow is encountered. In that case, the periodic boundary conditions are enforced using standard library’s
std::fmod function. The code does not verify if the boundary conditions of the provided table are fulfilled.
This class is intended to be used with every periodic boundary condition function, for example trigonometrical functions.
For more details regarding the API, see the API documentation for PeriodicLookupTable.
Usage examples
#include <numbers>
#include "lookupTable.h"
#include "generateFunction.h"
using namespace vslib;
void your_function(RootComponent& root)
{
auto constexpr two_pi = 2.0 * std::numbers::pi;
// automatially generated larger table in range 0 to 2 PI, with 1000 points:
PeriodicLookupTable<double> sin_table("table", &root,
fgc4::utils::generateFunction<double, double>(std::sin, 0.0, two_pi, 1000), true);
// all access done using index-search:
auto output = sin_table.interpolate(0); // 0.0
output = sin_table.interpolate(std::numbers::pi * 0.5); // 1.0
output = sin_table.interpolate(std::numbers::pi, true); // flag has no effect, 0.0
output = sin_table.interpolate(-std::numbers::pi); // underflow, x equivalent to pi, 0.0
output = sin_table.interpolate(3.5 * std::numbers::pi); // overflow, x equivalent to 1.5 pi, -1.0
// reset between not-connected uses to clear cached data
sin_table.reset();
return 0;
}
Example usage in a vloop:
#include "vslib.hpp"
namespace fgc::user
{
class Converter : public vslib::RootComponent
{
public:
Converter() noexcept
: vslib::RootComponent("example"),
interrupt_1("stg", *this, 128, vslib::InterruptPriority::high, RTTask),
sin_table("function", *this, fgc4::utils::generateFunction<double, double>(std::sin, 0.0, two_pi, 1000), true);
{
}
// Define your interrupts here
vslib::PeripheralInterrupt<Converter> interrupt_1;
// Define your public Components here
vslib::PeriodicLookupTable<double> sin_table;
void init() override
{
interrupt_1.start();
}
void backgroundTask() override
{
}
static void RTTask(Converter& converter)
{
// Read the input value:
const double data_x = converter.m_data[0];
const auto y = converter.sin_table.interpolate(data_x);
// use the interpolated function value y at data_x
}
private:
// actual source of data omitted for simplicity
std::array<double, 1> m_data{0.0};
};
} // namespace fgc::user
Sine look-up table
SinLookupTable is a convenience Component for interacting with a look-up table containing a sine function.
Internally, it owns a PeriodicLookupTable holding a sine function with argument range from 0.0 to \(2\pi\).
The utility function, generateFunction, is used to generate the equally-spaced sine function
table with the desired number of points. The number of points for the internal table is a constructor parameter.
An additional convenience method allows to call the SinLookupTable object as if it was the standard-library function:
SinLookupTable sin_table(name, parent, 10000);
sin_table(std::numbers::pi * 3.5); // -1.0
For more details regarding the API, see the API documentation for SinLookupTable.
Usage examples
#include <array>
#include "sinLookupTable.h"
using namespace vslib;
void your_function(RootComponent& root)
{
SinLookupTable sin_table("sin_table", &root, 1000);
auto output = sin_table.interpolate(0); // 0.0
output = sin_table.interpolate(std::numbers::pi * 0.5); // 1.0
output = sin_table.interpolate(std::numbers::pi, true); // flag has no effect, 0.0
output = sin_table.interpolate(-std::numbers::pi); // underflow, x equivalent to pi, 0.0
output = sin_table.interpolate(3.5 * std::numbers::pi); // overflow, x equivalent to 1.5 pi, -1.0
// reset between not-connected uses to clear cached data
sin_table.reset();
// equivalent to:
output = sin_table(0); // 0.0
output = sin_table(std::numbers::pi * 0.5); // 1.0
output = sin_table(std::numbers::pi, true); // flag has no effect, 0.0
cos_table.reset();
output = sin_table(-std::numbers::pi); // underflow, x equivalent to pi, 0.0
output = sin_table(3.5 * std::numbers::pi); // overflow, x equivalent to 1.5 pi, -1.0
cos_table.reset();
return 0;
}
Cosine lookup table
Convenience Component for interacting with a look-up table containing a cosine function, with argument range from 0.0 to \(2\pi\).
Completely analogous to the SinLookupTable with all features except for the stored function.
For more details regarding the API, see the API documentation for CosLookupTable.
Usage examples
#include <array>
#include "cosLookupTable.h"
using namespace vslib;
void your_function(RootComponent& root)
{
CosLookupTable cos_table("cos_table", root, 1000);
auto output = cos_table.interpolate(0); // 1.0
output = cos_table.interpolate(std::numbers::pi * 0.5); // 0.0
output = cos_table.interpolate(std::numbers::pi, true); // flag has no effect, 1.0
output = cos_table.interpolate(-std::numbers::pi); // underflow, x equivalent to pi, 1.0
output = cos_table.interpolate(4.5 * std::numbers::pi); // overflow, x equivalent to 0.5 pi, 0.0
// reset between not-connected uses to clear cached data
cos_table.reset();
// equivalent to:
output = cos_table(0); // 1.0
output = cos_table(std::numbers::pi * 0.5); // 0.0
output = cos_table(std::numbers::pi, true); // flag has no effect, 1.0
cos_table.reset();
output = cos_table(-std::numbers::pi); // underflow, x equivalent to pi, 1.0
output = cos_table(3.5 * std::numbers::pi); // overflow, x equivalent to 1.5 pi, 0.0
cos_table.reset();
return 0;
}
Performance
The performance of each of the look-up Components depends mainly on the method the stored table
is accessed, its size, the distance between the points, and how often the same sector is accessed sequentially.
The table below gives a rough insight into the performance that can be expected from each of the Components:
Class |
Size |
Access type |
Access time [ns] |
Difference [%] |
|---|---|---|---|---|
LookupTable |
10 |
linear, 1 hit/section |
||
LookupTable |
100 |
linear, 1 hit/section |
||
LookupTable |
1000 |
linear, 1 hit/section |
||
LookupTable |
10000 |
linear, 1 hit/section |
||
LookupTable |
10000 |
linear, 10 hit/section |
||
LookupTable |
1000 |
random, 1 hit/section |
||
LookupTable |
100 |
index |
||
LookupTable |
1000 |
index |
||
LookupTable |
10000 |
index |
||
std::sin |
N/A |
random |
160 |
|
SinLookupTable |
1000 |
random |
140 |
-20% |