forpy 2

forpy

Elegant Decision Forests in Python. Fast, clean and clear C++14 implementation with no dependencies and with an easy to use interface in Python and C++.

## Principles

1. Easy to hack
   The library provides an object oriented implementation of parts of the theoretical framework of Criminisi et al.. This makes the library easy to understand and extend while maintaining full generality. Objects are easy to reuse and recombine.
2. Easy to compile
   There are no dependencies. The only build requirement is a C++14 compatible compiler (tested with GCC and clang). We use the CMake build system with pre-compiled headers for fast builds and compatibility to many platforms.
3. Easy to use
   The library exposes a Python and C++ interface that accepts numpy/Eigen arrays of many types. The interface follows the widely used Scikit-learn interface with `fit` and `predict` methods.
4. Fast
   The implementation of algorithms, while caring for readability and maintainability, is highly optimized for speed (benchmarks see below). We outperform scikit learn in all settings by notable margins at fit and predict time. For fitting, we enable fully deterministic parallelization even during node optimization, allowing to fully leverage modern CPUs with many cores.
5. Efficient
   We use the cereal C++ serialization library enabling binary persistence (C++, pickle) or JSON export. The binary models need only a fraction of space of the corresponding scikit learn models.

## Approach

We use modern C++14 to create highly flexible, highly efficient data structures and algorithm implementations. Core building blocks are:

- A highly efficient `variant` implementation for high efficiency w.r.t. datatype dependent storage and processing while maintaining an uncluttered interface and implementation. `glog` and `gperftools` integration is used for easy debugging and optimization. All dependency libraries don't need to be installed but are part of the repository and completely integrated into the build.
- CMake is used as a build system so that many platforms and compilers can be targeted easily. `cotire` is used for automatic fast pre-compiled header builds. The whole package is automatically `pip` installable even without an installed CMake thanks to `scikit-build`.
- We use standard `Eigen` datastructures wrapped in `variant` to provide an easy-to-use C++ interface. We create a small and sleek Python interface thanks to pybind11.
- Threading is implemented with cpptask to be efficient and cross-platform.

## Compilation & Installation

If you want to use it from python, a simple `python setup.py install` should do. If you want to use it from C++, you can rely on CMake and do `mkdir build; cd build; cmake ..; cmake --build . -- -j` for an out-of-source build.

## Development & Contributing

### Formatting and conventions

The code is formatted with clang-format according to the google C++ style guidelines (a `.clang-format` file is provided on project level). We use abbreviated CamCase class names. For library internal functions, assertions must be done using the `FASSERT` macro to selectively enable it, but should be disabled for performance reasons for release builds.

Error messages must be meaningful and provide additional information on what caused the error.

Design decisions are made according to the following priorities:: correctness & numerical stability >> speed >> in-memory efficiency >> storage efficiency.

#### Rough naming conventions

Raw pointer variable names end with `_p`, indicating (1) high performance element access and (2) special care. In performance relevant loops, only `_p` variables should be used. Variant variable names end with `_v`.

### Programming concepts

Lock-free parallelism:

Memory is allocated for the tree and leaf storage structures in before entering parallel regions in a pessimistic way. Since it is linear in the number of samples, this is not too much of an overhead. The pointer to where next nodes/leafs can be created is an `std::atomic<size_t>`. After training, the datastructures are resized to their proper size.

The Desk classes: this is a helper concept to simplify safe parallelism. A 'desk' contains all thread-local variables and pointers to the shared storage. Each thread has its own desk with sub-objects containing thread-local storage for the corresponding sub-functions. It is constructed with pointers to the memory for storing the results of the training.

## License

The library itself is available under the 2-clause BSD license. All libraries used are also available under open source licenses, for details see `build_support/external`.