cpp-ml-systems

Hand-written C++17 implementations of core Machine Learning, Computer Vision, and Robotics algorithms — built to understand what actually happens under the hood of PyTorch, OpenCV, and ROS. No Eigen, no OpenCV, no deep-learning framework: every tensor op, convolution, and filter is written from scratch so the data layout, cache behaviour, and numerical recipes are all in plain sight.

Each module ships with GoogleTest unit tests and a benchmark that names its Python/NumPy equivalent, so the performance story is reproducible.

---

Highlights

• 🧮 Matrix ops — six implementations of the same GEMM (naive → cache-friendly ikj → L1 blocked tiling → AVX2+FMA SIMD → register-blocked 6×16 micro-kernel → OpenMP multi-threaded) that make the memory hierarchy, vectorization, and threading visible; loop order buys 14×, the packed micro-kernel reaches 24× and beats the auto-vectorizer, and OpenMP pushes it past 30× / 110+ GFLOP/s.
• 🚀 CUDA matmul + conv — naive vs shared-memory tiled matmul (4.3 TFLOP/s on an RTX 4090, ~170× CPU) and an im2col conv2d on the GPU with a fused conv+bias+ReLU epilogue kernel (~100× the CPU). Optional build; self-skips at runtime where there's no GPU, so CI stays green.
• 📦 Inference graph — a minimal ONNX-style loader that parses a serialized sequential model (Linear/ReLU/Sigmoid) and runs its forward pass; the demo loads a hand-built MLP and solves XOR.
• 🤖 ROS 2 node — the Kalman filter wrapped as a rclcpp sensor-fusion node (/measurement → /estimate), reusing the exact filter the unit tests cover.
• 🖼️ Convolution — single-channel im2col + GEMM, plus multi-channel CNN conv with a benchmark that shows where im2col overtakes the naive loop (7.4× at 32→64 channels).
• 🧠 Tiny CNN — a full hand-written forward pass (conv → ReLU → maxpool → flatten → linear → softmax), the layers PyTorch hides behind nn.Sequential.
• 🎯 Non-Max Suppression — IoU-based greedy NMS matching production YOLO/torchvision post-processing, with optional class-aware suppression.
• 🧱 Tensor class — type-safe N-dimensional array with strides, reshape/transpose/slice, NumPy-style broadcasting, and a 2D dot().
• 🤖 Kalman Filter — Linear KF and Extended KF, demonstrated on 2D object tracking and range/bearing radar.
• 🎛️ PID controller — production-grade, with integral anti-windup and a low-pass-filtered derivative term.
• ⚡ Memory arena — O(1) bump allocator, the per-frame scratch strategy used in engines and inference runtimes.
• ☁️ Point cloud utils — voxel-grid downsampling + nearest-neighbour search (the PCL/Open3D preprocessing front-end).

---

Why C++

Python is great for prototyping, but production ML systems — inference engines, robotics middleware (ROS 2), autonomous-vehicle stacks — are written in C++. This repo is my effort to stay sharp at the systems level while working daily in Python: the same algorithms a framework hides behind one function call, written out so the cache misses, the strides, and the linear algebra are all explicit.

---

Performance Numbers

Single-threaded, -O3 -march=native, real numbers from make bench on a development machine (yours will differ — just re-run it).

Operation	C++ naive	C++ optimized	Notes
MatMul 512×512 (f32)	84.8 ms	5.0 ms (24×)	naive → ikj (14×) → AVX2 13× → register-blocked micro-kernel 24× / 54 GFLOP/s
MatMul 1024×1024 (GPU)	84 ms (CPU)	0.50 ms (170×)	RTX 4090, shared-memory tiled CUDA kernel, kernel-only time
Conv2D 512×512, k=3	1.7 ms	5.9 ms	single-channel im2col loses — see note below
Conv2D 64×64, 32→64 ch	46.7 ms	6.3 ms (7.4×)	multi-channel im2col + GEMM wins decisively
NMS 1000 boxes	—	2.2 ms	greedy IoU NMS, matches torchvision.ops.nms

The matmul progression (the headline story). Same C = A·B, five CPU implementations, each fixing what the last one left on the table:

kernel	time	GFLOP/s	vs naive	what changed
naive ijk	84.8 ms	2.3	1×	inner loop strides down a column of B
cache-friendly ikj	6.0 ms	44	14×	inner loop is unit-stride; auto-vectorizes
blocked (64 tile)	8.3 ms	32	10×	L1 tiling (helps more as N grows)
AVX2+FMA SIMD	8.8 ms	30	13×	explicit intrinsics — ties the auto-vectorized ikj
register micro-kernel	5.0 ms	54	24×	6×16 tile in 12 YMM regs + packed panels
OpenMP parallel	4.4 ms	61–110	30×+	micro-kernel across row-bands on 24 threads

The honest lesson: at -O3 -march=native the compiler already vectorizes the ikj loop, so naive intrinsics don't beat it — the win comes from register blocking + panel packing (the OpenBLAS skeleton), which maximizes data reuse the compiler can't express on its own. Threading with OpenMP adds another ~2.5× (sub-linear at 512² because the kernel is partly memory-bandwidth bound; it scales better as N grows). On the GPU, the same "reuse loaded data from fast memory" idea (shared-memory tiling) takes it another ~170×.

The point of the matmul/conv columns isn't to beat multithreaded BLAS — it's to show how much speed loop order and tiling recover on their own.

Honest note on im2col: for a single-channel, single-filter conv the unfold cost isn't amortized, so im2col is slower than the naive loop. The win shows up at the C_in × C_out channel counts of real CNN layers, where the unfolded matrix turns the whole layer into one large GEMM. The bench_conv_layers sweep makes the crossover explicit (64×64 map, 3×3, pad 1):

channels	naive	im2col	speedup
1→1	0.04 ms	0.04 ms	1.0× (break-even)
3→8	0.73 ms	0.16 ms	4.5×
8→16	3.83 ms	0.58 ms	6.7×
16→32	10.7 ms	1.58 ms	6.8×
32→64	46.7 ms	6.32 ms	7.4×

---

Getting Started

git clone https://github.com/USERNAME/cpp-ml-systems
cd cpp-ml-systems

make install-deps   # one-time: cmake, g++, libgtest-dev (Ubuntu/Debian)
make build          # Release build in ./build
make test           # run the GoogleTest suite via ctest
make bench          # run all benchmarks

# Runnable demos:
./build/src/03_inference/tensor_demo
./build/src/04_robotics/kalman_demo
./build/src/02_computer_vision/cnn_demo   # full tiny-CNN forward pass
./build/src/03_inference/graph_demo       # load a serialized MLP, solve XOR

Requires CMake ≥ 3.20 and a C++17 compiler. GoogleTest is used if installed (make install-deps); pass -DCPPML_FETCH_GTEST=ON to download it, or build offline against the bundled gtest_lite fallback (used automatically when no system GoogleTest is found).

CUDA (optional): the GPU matmul module builds automatically when the CUDA toolkit is present (CPPML_BUILD_CUDA=AUTO, the default) and is silently stubbed out otherwise — no GPU is needed to build, test, or pass CI. On a CUDA machine:

make build                                    # auto-detects nvcc, builds the .cu kernels
./build/benchmarks/bench_cuda_matmul          # CPU micro-kernel vs GPU naive vs GPU tiled
# force on/off:  cmake -B build -DCPPML_BUILD_CUDA=ON   (or OFF)

---

Module Details

• Foundations — matrix_ops.cpp walks through naive, cache-friendly, blocked, AVX2+FMA SIMD, a register-blocked 6×16 micro-kernel, and an OpenMP multi-threaded GEMM with the why behind each step (the SIMD/micro-kernel paths fall back to scalar on non-AVX2 targets, and the parallel path runs serial without OpenMP); memory_arena.cpp is a bump allocator (header: memory_arena.hpp).
• Computer Vision — convolution.cpp (single-channel naive vs im2col), conv_layers.cpp (multi-channel conv
  • ReLU/maxpool/flatten, with cnn_demo.cpp running a full forward pass), image_pipeline.cpp (bilinear resize, normalize, RGB→gray), and nms.cpp.
• Inference — tensor.hpp is the N-D array; linear_layer.cpp implements nn.Linear forward and backward with Xavier/He init; graph.cpp parses an ONNX-style serialized model (models/mlp_xor.txt) and runs its forward pass.
• Robotics — kalman_filter.cpp (KF + EKF), pid_controller.cpp, and pointcloud_utils.cpp.
• CUDA — cuda_matmul.cu (naive + shared-memory tiled GPU matmul, plus an im2col GPU conv2d) behind the GPU-agnostic cuda_matmul.hpp; a stub keeps it linkable without a toolkit.
• ROS 2 — ros2/cppml_kalman wraps the Kalman filter as an rclcpp node (/measurement → /estimate); an ament_cmake package built with colcon, outside the core build. See ros2/README.md.

---

What's Next

• Explicit SIMD (AVX2+FMA intrinsics) matmul kernel with scalar fallback
• Multi-channel convolution + a tiny CNN forward pass
• Register-blocked / packed GEMM that actually beats the auto-vectorizer (24×)
• CUDA kernels for matmul (naive + shared-memory tiled, ~170× on RTX 4090)
• CUDA convolution kernel (im2col + tiled GEMM, 67× on RTX 4090)
• ONNX-style graph loader for the inference module
• ROS 2 node wrapper around the Kalman filter
• Multi-threaded CPU GEMM (OpenMP, 30×+) and a fused conv+bias+ReLU GPU kernel
• Winograd / FFT convolution; INT8 quantized inference path

---

License

MIT — see LICENSE.