Baobzi

基于树搜索的自适应快速函数逼近器。除了这个词汇混乱之外，baobzi是一个将非常CPU密集型函数计算转换为相对便宜的计算的工具（以内存为代价）。这类似于MATLAB中的chebeval函数，但可以快得多，因为多项式拟合的阶数可以低得多以满足相似的公差。它也不限于仅在MATLAB中使用。

在内部，baobzi通过一个由二叉/四叉/八叉/N树组成的网格来表示您的函数，其中叶子代表函数在其定义域的小子区域中的Chebyshev多项式。当您使用baobzi在某个点评估函数时，它会搜索包含该点的盒子，并使用此逼近器进行评估。

• 示例用例
• 局限性
• 功能
• 快速安装
• 构建/测试
• 输入参数
• 使用...
  • C
  • C++
  • Python
  • Julia
  • MATLAB
  • Fortran
• 环境
• 在您的CMake项目中包含
• 路线图
• 已知问题。重要，请阅读
• 为什么叫这个名字？

示例用例

• 在高级语言中构建复杂或计算成本高的函数。构建一个baobzi函数，并将其用作您函数的替换。享受速度带来的好处。
• 将先前函数导出，并在高性能语言中使用：生产或原型。
• 您喜欢的scipy函数尚未在numba中支持？使用baobzi代替移植该函数。

局限性

• 可以使用大量内存...尤其是在振荡或快速变化的函数中。如果您的函数是周期的，请在一个周期内拟合函数。如果需要，转换函数。
• 不适用于奇点。只是不要这样做。如果需要，在奇点周围使用多个baobzi对象。
• 不执行任何边界检查。用户必须自行清理输入。

功能

• 相对语言无关性。该库具有简单的C接口，然后将其绑定到多种语言（C/C++、Fortran、Python、Julia、MATLAB）。这意味着您可以在MATLAB中创建一个重型函数，在那里进行插值，然后从您选择的其他语言中调用它。
• CPU调度 -- baobzi会检测您的CPU并根据此运行优化的代码路径 -- 无需用户干预。
• 无库依赖。构建baobzi所需的所有代码都在baobzi中。支持构建不需要加载共享baobzi对象但希望直接将其放入二进制文件的可选静态库。有关如何在您的CMake项目中包含的信息，请参阅包含在您的CMake项目中。

快速安装

Python/Conda

目前没有轮子，这意味着conda/pip必须执行Baobzi的源构建（尽管希望这很快就能改变）。要进行标准的pip安装，首先请确保您的路径中有一个现代的gcc/g++，以及cmake >= 3.14。

# create a virtualenv, if you want
python3 -m venv --system-site-packages myenv
source myenv/bin/activate
pip install git+https://github.com/flatironinstitute/baobzi.git

python -c 'from baobzi import Baobzi'

如果您使用conda，您可以通过conda-forge存储库安装gcc、g++和cmake，然后使用pip安装baobzi。

conda create -y -n baobzi -c conda-forge gcc gxx cmake numpy
conda activate baobzi
pip install git+https://github.com/flatironinstitute/baobzi.git

python -c 'from baobzi import Baobzi'

构建/测试

Baobzi的唯一依赖项是cmake >= 3.14和一个C/C++17编译器（目前仅限gcc）。我现在从g++-11中获得了最佳性能。虽然有一个仅包含头文件的C++库，但它可能会相当挑剔。因此，为了获得最佳性能，我目前建议使用gcc的C共享/静态库接口，而不是直接使用C++头文件。请参阅examples/C/baobzi_timing.c示例。在我的Xeon Gold 6128上使用一个核心，这个示例在简单的2D示例中大约每秒进行20M次评估，在简单的3D示例中每秒进行3M次评估。

# 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

输入参数

Baobzi只有几个输入参数，但它们可以极大地影响性能，并且值得为您的特定函数进行尝试。

• func：您希望近似的函数

• dim：函数的独立变量数量。

• order：用于表示函数块的多项式阶数。阶数越高，速度越慢，尤其是在高维中。不考虑搜索/缓存问题，评估的时间复杂度为O(ORDER^DIM)。尽管搜索不是免费的，但baobzi通常需要较少的细分来满足更高的阶数，因此如果使用更高的阶数，您的函数可能既快又节省内存。

• data：此参数仅适用于C/C++/Fortran。如果您要拟合的函数需要参数，以某种方式打包它们，然后data就是指向该打包信息的指针。请参阅示例。

• tol：函数与近似之间希望的最大相对误差。无法保证所有函数评估都会满足此容差，因此重要的是在您感兴趣的区域测试结果，以确保结果令人满意。

• minimum_leaf_fraction：Baobzi在内部由树表示。然而，为了加快树查找速度，该树被划分为从某些深度开始的子树。默认情况下，该深度是一级以上具有“叶子”的级别。叶子是进行函数评估的终端盒子（其他节点仅包含指向其子节点的指针）。这种方案可能会在某些情况下对性能产生不利影响（例如，只有该级别的节点是叶子的节点）。此参数设置了一个要求，即当给定级别的叶子比例小于此阈值时，baobzi会继续细分整个级别。

  关于这个参数的思考方式很简单，如果参数是0.0，那么baobzi永远不会将叶子节点作为父节点，树将尽可能小（但不一定是平衡的）。如果参数是1.0，那么baobzi将确保树的最终深度完全由叶子节点填充。这种树是完全平衡的，因此是规则的网格。介于这两者之间的任何值都会在这两个极端之间变化。这个参数对性能影响极大，尤其是在1D树中。

• split_multi_eval：在评估点向量时，baobzi目前可以使用两种策略之一，这可能会根据树和计算机的性能产生显著影响。默认情况下，将点的评估分为两个阶段，第一阶段计算盒子，然后第二阶段用它们评估点。当节点数量很多时，这通常有助于提高缓存命中的机会，因为它不会加载额外的评估数据。然而，这需要创建一个临时数据结构来存储这些数据，这会花费时间和内存。

  第二种策略是直接根据目标顺序暴力评估点。这种方法在1D和树较小的情况下通常效果很好，但其他情况下性能较差。

  将此参数设置为1使用通常更快的'split'模型，而设置为0将使用直接模型。

使用...

所有示例都需要你的项目知道baobzi共享对象的位置。在上面的示例中，它位于$BAOBZI_ROOT/lib或$BAOBZI_ROOT/lib64目录中，具体取决于您的系统。

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

以下是一个比下面更复杂的示例：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
    };

    const double hl[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, hl);
    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++

以下是一个比下面更复杂的示例：examples/c++/baobzi_timing.cpp

// test_baobzi.cpp
#include <baobzi.hpp>
#include <cstdio>

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

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

    const double hl[2] = {1.0, 1.0};
    const double center[2] = {0.0, 0.0};
    const double x[2] = {0.25, 0.25};
    {
        Baobzi func_approx(&input, center, hl);
        printf("%g\n", func_approx(x));
        func_approx.save("func_approx.baobzi");
    }

    Baobzi func_approx("func_approx.baobzi");
    printf("%g\n", func_approx(x));

    return 0;
}

g++ -o test_baobzi.cpp -lbaobzi

Python

examples/python/simple2d.py

# simple2d.py
from baobzi import Baobzi

def py_test_func(x):
    return x[0] * x[1]

center = [0.0, 0.0]
hl = [1.0, 1.0]
point = [0.25, 0.25]
tol = 1E-8
minimum_leaf_fraction = 0.0 # optional/default
split_multi_eval = 1 # optional/default

test = Baobzi(py_test_func, 2, 6, center, hl, 1E-8, minimum_leaf_fraction, split_multi_eval)
test.save('test.baobzi')
print(test(point))
del test

test2 = Baobzi(filename='test.baobzi')
print(test2(point))
del test2

python3 simple2d.py

Julia

examples/julia/simple2d.jl

# simple2d.jl
import baobzi

function testfunc(xp::Ptr{Float64})::Cdouble
    x = unsafe_load(xp, 1)
    y = unsafe_load(xp, 2)
    return x * y
end

center = [0.0, 0.0]
hl = [0.5, 1.0]
test_point = [0.25, 0.25]
dim = 2
order = 6
tol = 1E-8
minimum_leaf_fraction = 0.0 # optional/default
split_multi_eval = 1 # optional/default
output_file = "simple2d.baobzi"

func_approx = baobzi.init(testfunc, dim, order, center, hl, tol, minimum_leaf_fraction, split_multi_eval)
println(baobzi.eval(func_approx, test_point) - testfunc(pointer(test_point)))

baobzi.save(func_approx, output_file)
baobzi.free(func_approx)

func_approx = baobzi.restore(output_file)
println(baobzi.eval(func_approx, test_point) - testfunc(pointer(test_point)))

julia simple2d.jl

MATLAB

MATLAB初始化对于匿名函数不起作用。您必须声明一个实际函数（在其自己的myfunc.m文件中）。

%% testfun.m
function [y] = testfun(x)
  y = x(1) * x(2);
end

%% simple2d.m
dim = 2;
order = 6;
center = [0.0, 0.0];
hl = [1.0, 1.0];
tol = 1E-8;
func_approx = baobzi('new', 'testfun', dim, order, center, hl, tol);
display(func_approx.eval([0.25, 0.25]))
func_approx.save('simple2d.baobzi');
clear func_approx
func_approx = baobzi('restore', 'simple2d.baobzi');
display(func_approx.eval([0.25, 0.25]))

matlab -batch simple2d

Fortran

examples/fortran/fortran_example.f90

program main
  use baobzi
  implicit none
  real(kind=c_double) :: center(2), half_length(2), tol
  real(kind=c_double) :: x(2)
  real(kind=c_double), target :: scale_factor
  type(c_ptr) :: func_approx
  character(len=64) :: fname
  type(baobzi_input_t) :: input

  input%func = c_funloc(testfun)
  input%data = c_loc(scale_factor)
  input%dim = 2
  input%order = 6
  input%tol = 1E-8
  input%minimum_leaf_fraction = 0.0
  input%split_multi_eval = 0

  center(:) = 0.0
  half_length(:) = 1.0
  x(:) = 0.25

  fname = trim(adjustl('fortran.baobzi'))//char(0)

  func_approx = baobzi_init(input, center, half_length)
  print *, baobzi_eval(func_approx, x) - testfun(x, scale_factor)

  call baobzi_save(func_approx, fname)
  func_approx = baobzi_free(func_approx)

  func_approx = baobzi_restore(fname)
  print *, baobzi_eval(func_approx, x) - testfun(x, scale_factor)

contains
  function testfun (x, scale_factor) bind(c) result(y)
    use, intrinsic :: iso_c_binding
    implicit none
    real(kind=c_double), dimension(*) :: x
    real(kind=c_double) :: scale_factor
    real(kind=c_double) :: y

    y = scale_factor * x(1) * x(2)
  end function testfun

end program main

gfortran -o fortran_example -I$BAOBZI_ROOT/share/baobzi/fortran fortran_example.f90 -lbaobzi

环境

Baobzi的大多数控制流都是通过输入结构来处理的，但有一个单独的环境变量：BAOBZI_ARCH。这个环境变量允许您手动设置评估使用的指令集。通常没有理由使用它，但在某些情况下，AVX2可能会比AVX512表现更好，或者您可能想测试指令集的影响。有效的值（不区分大小写）是GENERIC、AVX、AVX2和AVX512。

在您的CMake项目中包含

我在extern/baobzi中添加了一个git子模块，并构建和链接了静态库。您也可以设置共享库并关闭静态库，尽管您需要确保共享库与您的项目一起安装。可能最好是使用静态库。在这个例子中，它使我的测试可执行文件大小增加了23MB。

set(BAOBZI_BUILD_SHARED OFF CACHE BOOL "")
set(BAOBZI_BUILD_STATIC ON CACHE BOOL "")
set(BAOBZI_BUILD_EXAMPLES OFF CACHE BOOL "")
set(BAOBZI_BUILD_TESTS OFF CACHE BOOL "")
add_subdirectory(extern/baobzi)

add_executable(baobzi_test src/test.cpp)
target_include_directories(baobzi_test PUBLIC extern/baobzi/include)
target_link_libraries(baobzi_test PUBLIC baobzi_static)

路线图

请参阅问题或项目跟踪器。

已知问题。重要，请阅读

• 完全没有越界处理。如果您调用越界，您的程序可能会崩溃或更糟。只有您才能防止段错误（或者更糟，错误的答案）。请注意，baobzi的维度是在半开区间[x0, x1)上定义的。调用上边界会导致段错误或给出错误的答案。
• Baobzi无法处理奇点或类似sin(1/x)的病态函数。它会消耗您的内存并崩溃。我打算处理这些问题，但我想要开发一个API，允许有更多选项来处理这些问题。这将需要时间。
  • 解决方案：目前，只需将多个baobzi函数分段，以绕过奇点。我希望添加一个选项来添加排除域，或者添加多个域以表示单个函数。
• 在一维和二维中，baobzi将通过查看某些切比雪夫系数的值来确定公差匹配。这往往会低估拟合程度，从而导致比预期的精度更高（尽管也有一些例外）。在三维中，它使用采样技术。这实际上将拟合时间加倍，但会给出更接近预期公差的结果。从低开始，逐步增加，直到找到适合您的拟合。最终，这将成为API中的一个选项。
• MATLAB初始化对于匿名函数不起作用。您必须声明一个实际函数（在其自己的myfunc.m文件中）。
• 不支持4+维（尽管可能，我还没有制定出拟合程序）。可能不想超过5维，因为每个节点需要O(8 * ORDER^D)字节的内存。

为什么叫这个名字？

这是一个可爱的baobab版本，或者说是生命之树，这已经是一个非常流行的项目名称。baobab寿命极长，这个插值器就是为了这一点而设计的。种植它（它是一棵树！），并且反复使用它。这就是比喻的极限——尽量别想太多。