Runtime Performance

In the following section, we assess the performance of wrenfold generated functions.

Caveats

As with any benchmarking results, there are some important caveats to consider:

  • Choice of compiler, compiler version, and CPU architecture may meaningfully alter results.

  • Compiler flags (for instance, enabling -march=native) can optimize or pessimize a given implementation, sometimes in unexpected ways.

  • Performance is a moving target, and results will evolve over time.

For the most accurate outcome, you should test your function in-context with a compiler and CPU architecture that reflect your production environment.

Overview

The results reported here were computed using the code in the wrenfold-benchmarks repository. We consider the performance of four functions of increasing complexity:

  • QuatLocalCoords: Computing the tangent-space difference between two orientations parameterized as quaternions. This is sometimes referred to as the local coordinates operation:

    \[f(\mathbf{q}_0, \mathbf{q}_1) = \text{log}\left(\bar{\mathbf{q}}_0 \cdot \mathbf{q}_1\right)\]

  • ImuIntegration: Performing a single step of IMU preintegration.

  • QuatInterpolation: Given an interpolation fraction \(\alpha\), compute the tangent-space interpolation between two quaternions:

    \[f(\mathbf{q}_0, \mathbf{q}_1, \alpha) = \mathbf{q}_0 \cdot \text{exp}\left( \text{log}\left(\bar{\mathbf{q}}_0 \cdot \mathbf{q}_1\right) \cdot \alpha\right)\]

  • RollingShutterCamera: This function projects a Euclidean point into a moving rolling-shutter camera. The camera uses a first-order (constant velocity) motion model, and the OpenCV intrinsic model with radial and tangential distortion coefficients.

These functions are plausible sub-expressions of a visual-inertial odometry (VIO) or visual-inertial navigation system (VINS) system, which is why they were selected for study. For each function we also compute the tangent-space Jacobians with respect to the input values.

Jacobian Computation

When computing Jacobians on manifolds (for example the rotation group \(SO\left(3\right)\)), there are two plausible approaches that are well suited to symbolic code generation:

  1. We can compute the Jacobians with respect to the group variables (for instance, the four variables \(\left[w, x, y, z\right]\) that make up a quaternion) and then chain them with the Jacobian of the retraction operation (see section II.D of [1]) evaluated around zero. We refer to this as the chain-rule method, which is detailed in section B.1 of the SymForce paper.

  2. Alternatively, we can first replace the retract operation with a first-order taylor series in the vector variable \(\delta \mathbf{x}\), substitute the series into the function, and then evaluate the result around \(\delta \mathbf{x} = 0\) after computing Jacobians with respect to \(\delta \mathbf{x}\). This method is detailed in section B.2 of the SymForce paper. We refer to this as the first-order method. This approach can produce fewer operations in certain instances.

Tip

See the section 3D Rotations for more details on tangent-space Jacobians.

SymForce provides an explicit interface for manifolds, and defaults to taking derivatives via the first-order method. In order to perform an apples-to-apples comparison, we apply the chain-rule method to both frameworks. There is nothing to prevent the user from applying the first-order approximation to wrenfold, if they so desire. The two code-generated implementations we evaluate are:

  • XXX_Wrenfold: wrenfold symbolic expressions with chain-rule method.

  • XXX_SymforceChain: SymForce symbolic expressions with chain-rule method. These are directly comparable to the _Wrenfold implementations.

Additionally, we compare to two additional implementations:

  • XXX_Handwritten: A handwritten implementation. Eigen is used to provide rotation and linear-algebra operations. Jacobians are computed “GTSAM style” by manually chaining together derivatives for each step of the function:

    \[\frac{\partial \mathbf{f}\left(\mathbf{g}\left(\mathbf{x}\right)\right)} {\partial \mathbf{x}} = \frac{\partial \mathbf{f}\left(\mathbf{u}\right)} {\partial \mathbf{u}} \biggr\rvert_{\mathbf{u} = \mathbf{g}\left(\mathbf{x}\right)} \frac{\partial \mathbf{g}\left(\mathbf{x}\right)} {\partial \mathbf{x}}\]

  • XXX_Ceres: A handwritten implementation that employs Ceres auto-diff to compute Jacobians.

In all likelihood, a reasonably diligent author can produce a handwritten implementation that surpasses the code-generated equivalent. We argue that the strength of code generation is the ability to produce a competitive implementation in short order, allowing for quicker development and evaluation in the context of a production system.

Results

The following results were last updated with wrenfold v0.0.5. We collect results for gcc 12.3.0-3 and clang 16.0.6 - both using optimization level -O3 and x86_64 architecture. The benchmark code can be found in the wrenfold-benchmarks repository.

We report resulting times as multiples of the wrenfold generated implementation (for the same compiler). A multiple > 1.0 indicates that the implementation under comparison is slower than wrenfold, while a multiple < 1.0 is faster. Plots are available below - a few observations follow:

  • code-generated functions are roughly comparable to the handwritten implementations. For example, QuatInterpolation and ImuIntegration are ~5-15% faster in handwritten form under gcc [2], and ~5-10% slower than wrenfold under clang.

  • When comparing wrenfold to SymforceChain, we find that:

    • For the three most complicated functions (ImuIntegration, QuatInterpolation, and RollingShutterCamera), wrenfold implementations are faster than SymForce.

    • For the QuatInterpolation test, the SymForce implementations require at least twice the time under both gcc and clang.

  • Auto-differentiated Ceres implementations are always slower than their code-generated equivalents, sometimes by multiples as high as 7x or 8x.

From our (evidently biased) perspective, the primary takeaway (with regards to performance) is that code-generated methods are a comparable substitute for hand-rolled implementations. They can be used to rapidly prototype mathematical functions while incurring a relatively small performance trade-off.




Footnotes