Baobzi

NOTE: I develop on main because I live dangerously. Documentation might be out of sync -- please use the release versions as the API is currently in a state of flux.

An adaptive fast function approximator based on tree search. Word salad aside, baobzi is a tool to convert very CPU intensive function calculations into relatively cheap ones (at the cost of memory). This is similar to functions like chebeval in MATLAB, but can be significantly faster since the order of the polynomial fit can be much much lower to meet similar tolerances. It also isn't constrained for use only in MATLAB.

Internally, baobzi represents your function by a grid of binary/quad/oct/N trees, where the leaves represent the function in some small sub-box of the function's domain with chebyshev polynomials. When you evaluate your function at a point with baobzi, it searches the tree for the box containing your point and evaluates using this approximant.

• Example use cases
• Limitations
• Features
• Quick install
• Building/testing
• Input parameters
• Running with...
  • C
  • C++
  • Python
  • Julia
  • MATLAB
  • Fortran
• Environment
• Including in your CMake project
• Roadmap
• Known Issues. IMPORTANT PLEASE READ
• Why the name?

Example use cases

• Build complicated or high computational cost function in higher level language. Build a baobzi function and use it as a drop in replacement to your function. Reap speed benefits.
• Take prior function, export it, and use it in a higher performance language: production or prototype.
• Your favorite scipy function not supported in numba yet? Use baobzi instead of porting that function.

Limitations

• Can use a lot of memory... especially on oscillatory or rapidly changing functions. If your function is periodic, fit your function on one period. Transform the function if necessary.
• Not suited around singularities. Just don't do it. Use multiple baobzi objects around your singularity if necessary.
• Doesn't do any bounds checking. It is up to the user to sanitize input.

Features

• Relative language agnosticism. The library has a simple C interface, which is then bound to multiple languages (C/C++, Fortran, Python, Julia, MATLAB). This means you can make a heavy duty function in MATLAB, interpolate it there, and then call it from another language of your choice.
• CPU dispatch -- baobzi will detect your CPU and run an optimized codepath based on that -- no intervention by the user.
• No library dependencies. All code necessary to build baobzi is in baobzi. There is an optional static library supported for building C/C++ codes where you don't want to load in the shared baobzi object, but would rather throw it right in your binary. See Including in your CMake project.

Quick install

Python/Conda

# create a virtualenv if you want
# I advise --system-site-packages when file quotas can a problem
python3 -m venv --system-site-packages myenv
source myenv/bin/activate
pip install baobzi

Or with conda

# create a conda environment, if you want
conda create -y -n baobzi
conda activate baobzi
pip install baobzi

Building/testing/other languages

Baobzi's only dependencies are cmake >= 3.14, and a C/C++17 compiler (gcc only really, currently). I get the best performance out of g++-11 right now. While there is a header only library for C++, it can be quite finicky. Therefore, for optimal performance, I currently suggest using the C shared/static library interface with gcc rather than the C++ header directly. See examples/C/baobzi_timing.c for an example. On my Xeon Gold 6128 using one core, this example gets roughly 20M evals/s on a simple 2D example, and 3M evals/s on a simple 3D example.

# At FI -- module load gcc cmake matlab
export BAOBZI_ROOT=$HOME/local/baobzi
git clone --recursive https://github.com/flatironinstitute/baobzi.git
cd baobzi
mkdir build
cd build
# Don't supply -march!!! Builds with CPU dispatch
cmake -DBAOBZI_BUILD_MATLAB=True -DCMAKE_INSTALL_PREFIX=$BAOBZI_ROOT ..
make -j $((2*$(nproc)))
make install

Input parameters

Baobzi only has a few input parameters, but they can greatly impact the performance and are worth playing with for your specific function.

• input structure parameters

  • func: Function you want to be approximated

  • dim: Number of independent variables to your function.

  • order: Polynomial order used to represent a chunk of your function. Higher order is slower, especially in higher dimensions. An evaluation, ignoring search/cache issues, takes O(ORDER^DIM) time. Search isn't free though, and baobzi typically needs fewer subdivisions for higher orders, so your function might be faster and use less memory if you use a higher order.

  • data: This parameter is only relevant to C/C++/Fortran. If the function you're fitting takes parameters, pack that somehow, and data is simply a pointer to that packed info. See examples.

  • tol: The maximum desired relative error between your function and the approximant. It is impossible to guarantee that all function evaluations will meet this tolerance, so it's important to test the results on the domain you're interested in to ensure that results are to your satisfaction.

  • minimum_leaf_fraction: Baobzi internally is represented by a tree. However, to speed up tree lookups, that tree is divided into subtrees that start at some depth. That depth, by default, is one above the first level to have a "leaf." A leaf is a terminal box where the function evaluation happens (other nodes just contain pointers to their children). This scheme can adversely impact performance in some cases though (such as cases where only one node on a level is a leaf). This parameter sets a requirement that baobzi keeps subdividing entire levels when the fraction of leaves on a given level is less than this threshold.

    An easy way to think about this is if the parameter is 0.0, then baobzi will never make a leaf node a parent node, and the tree will be as small as possible (but not necessarily well balanced). If the parameter is 1.0, then baobzi will ensure that the final depth of the tree is entirely filled with leaves. This tree is perfectly balanced, and therefore exactly a uniform grid. Anything between will vary between these two extremes. This parameter can EXTREMELY impact performance, especially on 1D trees.

  • split_multi_eval: When evaluating a vector of points, baobzi can currently use one of two strategies which can dramatically impact performance, depending on the tree and computer. The default is to split the evaluation of the points into two stages, one where the boxes are calculated in one pass, and then the points are evaluated with them in a second. This tends to help when there are a large number of nodes, as it increases the chance of a cache hit by not ever loading in extra evaluation data. However it requires making a temporary data structure to hold this, which costs time/memory.

    The second is to just brute force evaluate the points as they appear in the target order. This typically works very well in 1D, for small trees, but otherwise has poor performance.

    Setting this parameter to 1 uses the typically faster 'split' model, while setting it to 0 will use the direct model.

  • max_depth: Maximum depth allowed for tree before interpolation considered failed.

• domain parameters (yes they're weird, I'm sorry)
  • center: N-dim array representing the center of the domain you're interested in
  • half_length: N-dim array representing half the length of your domain

Running with...

All examples require your project know where the baobzi shared object is located. In the example above, it's located in either the $BAOBZI_ROOT/lib or $BAOBZI_ROOT/lib64 directory, depending on your system.

export LD_LIBRARY_PATH=$LD_LIBRARY_PATH:$BAOBZI_ROOT/lib
export LIBRARY_PATH=$LIBRARY_PATH:$BAOBZI_ROOT/lib
export C_INCLUDE_PATH=$C_INCLUDE_PATH:$BAOBZI_ROOT/include
export CPLUS_INCLUDE_PATH=$CPLUS_INCLUDE_PATH:$BAOBZI_ROOT/include
export PYTHONPATH=$PYTHONPATH:$BAOBZI_ROOT/share/baobzi/python
export JULIA_LOAD_PATH=JULIA_LOAD_PATH:$BAOBZI_ROOT/share/baobzi/julia
export MATLABPATH=$MATLABPATH:$BAOBZI_ROOT/share/baobzi/matlab

C

A more complicated example than below: examples/C/baobzi_timing.c

// test_baobzi.c
#include <baobzi.h>
#include <stdio.h>

double testfunc(const double *x, const void *data) { return x[0] * x[1]; }

int main(int argc, char *argv[]) {
    baobzi_input_t input = {
        .func = testfunc,
        .data = NULL,
        .dim = 2,
        .order = 6,
        .tol = 1E-10,
        .minimum_leaf_fraction = 0.0,
        .split_multi_eval = 0,
        .max_depth = 50
    };

    const double half_length[2] = {1.0, 1.0};
    const double center[2] = {0.0, 0.0};
    const double x[2] = {0.25, 0.25};

    baobzi_t func_approx = baobzi_init(&input, center, half_length);
    printf("%g\n", baobzi_eval(func_approx, x));
    baobzi_save(func_approx, "func_approx.baobzi");
    func_approx = baobzi_free(func_approx);

    func_approx = baobzi_restore("func_approx.baobzi");
    printf("%g\n", baobzi_eval(func_approx, x));
    return 0;
}

gcc -o test_baobzi.c -lbaobzi
./test_baobzi

C++

A more complicated example than below: examples/c++/baobzi_timing.cpp

// test_baobzi.cpp