DEV Community: Eugene Ostroukhov

Open Source C++ Stack

Eugene Ostroukhov — Tue, 16 Jul 2024 21:00:00 +0000

C++ is often labeled as "unsafe" and "complex," but I find these critiques unjustified. My experience working on major projects like Chromium, Node, and gRPC — each a non-trivial codebase deployed on millions of devices, both virtual and physical, and subject to rigorous scrutiny—has shown me the true power and reliability of C++. Let's not forget the remarkable engineering feats made possible by C++, such as Unreal Engine. Even Linux and Git, both written in C (arguably even less "safe" than C++), stand as testaments to the robust potential of these languages.

There is a trick to writing C++ code in a scalable way. I would call it "write C++ the Google way". Google has been using C++ for decades and has accumulated a wealth of expertise in writing C++ code that is safe, performant, and maintainable. And that expertise is readily available on GitHub.

In this article, I want to introduce you to some open-source projects that make writing C++ code enjoyable. These projects are designed to work seamlessly together, yet you can pick and choose the ones that best fit your needs.

Google C++ Style Guide: Lingua Franca

Explore the Guide on GitHub

The Google C++ Style Guide explains how to make C++ code beautiful. This
comprehensive set of conventions ensures consistency across projects, making it easier for developers to dive into new codebases with confidence.

The guide goes beyond mere stylistic choices like indentation width (2 spaces) or file naming conventions (all lowercase, with underscores (_) or dashes (-)). It delves deep into language features and provides the rationale behind each decision, offering a clear path to writing high-quality, maintainable C++ code.

Perhaps the most controversial convention in the guide is the "ban" on exceptions. "We do not use C++ exceptions" is a rule that can be hard to accept for developers coming from other languages. Yet, exceptions are not as essential as they might seem. Languages like Go thrive without them, and C++ projects like Chromium and gRPC demonstrate that robust and efficient code can be written without exceptions.

I frequently recommend this guide to developers both inside and outside Google as the simplest way to elevate the quality of their C++ code. By adhering to these well-established conventions, anyone can write C++ "the Google way" and enjoy the benefits of safer, more maintainable, and performant code.

Bazel: If You Build It, They Will Come

Discover Bazel

Bazel is a build system inspired by Google's internal build system. Thousands of engineers at Google use Blaze daily to build countless projects, written not only in C++ but also in Java, Python, Go, other languages.

Bazel highlights:

Starlark Language: Bazel build files are written in Starlark, a language that is both extensible and easy to read. This simplicity makes it approachable for new users and powerful enough for complex build configurations.
Efficient Caching: One of Bazel's standout features is its efficient caching mechanism, which relies on checksums rather than timestamps. This results in significantly faster and more reliable builds, a feature I rely on daily for large C++ projects like gRPC.
Dependency Tracking: Bazel excels in dependency tracking, minimizing the size of build artifacts and speeding up the build process. This feature ensures that only the necessary components are rebuilt, saving valuable time and resources.
Powerful Query Language: Bazel includes a robust query language that allows developers to analyze the build graph, providing deep insights into the build process and helping to optimize it further.

Bazel makes it trivial to build Protobuf libraries, supports multiple
languages and most libraries I mention below are trivial to add to a Bazel project, just look at Uchen.ML module file:

'''
Uchen core - ML framework
'''
module(name = "uchen-core", version = "0.1", compatibility_level = 1)
bazel_dep(name = "abseil-cpp", version = "20240116.2")

bazel_dep(name = "googletest", version = "1.14.0")
git_override(
    module_name = "googletest",
    remote = "https://github.com/google/googletest.git",
    commit = "1d17ea141d2c11b8917d2c7d029f1c4e2b9769b2",
)

bazel_dep(name = "google_benchmark", version = "1.8.3")
git_override(
    module_name = "google_benchmark",
    remote = "https://github.com/google/benchmark.git",
    commit = "447752540c71f34d5d71046e08192db181e9b02b",
)

# Dev dependencies
bazel_dep(name = "hedron_compile_commands", dev_dependency = True)
git_override(
    module_name = "hedron_compile_commands",
    remote =
      "https://github.com/hedronvision/bazel-compile-commands-extractor.git",
    commit = "a14ad3a64e7bf398ab48105aaa0348e032ac87f8",
)

Abseil: Utilities

abseil.io

Abseil provides a wide array of utilities across various categories. Some of these utilities, such as absl::string_view and absl::optional, have already been adopted into the standard C++ library, with Abseil seamlessly using the standard versions when available. Other utilities, like my favorite absl::Cleanup, seem to be on track to being standartize late (see std::scope_exit). Many utilities in Abseil remain beyond the current scope of the standard library, offering unique functionalities that enhance C++ development.

I heavily rely on the following parts of Abseil for my projects:

Command Line Flags: Simplifies the management of command line arguments.
Logging: Provides robust logging capabilities.
String Utilities: Includes utilities for string joining, formatting, and more.

Many classes in UchenML are augmented with AbslStringify which allows for very easy tracing and debugging.

I would also like to point out the C++ Tips section that I would consider an essential reading for any C++ developer, on par with the Google C++ Style Guide.

Google Test: Industry Standard

Google Test

My impression is that Google Test is the most popular C++ testing framework and I often see it used in projects outside Google. Not really much to add.

I would definitely recommend to also take a look at GMock. GMock provides some matchers that can also be used for regular assertions. E.g., this is how contents of the collection can be checked ignoring the order:

EXPECT_THAT(collection, ::testing::UnorderedElementsAre(1, 2, 3));

Benchmarking: Google Benchmark

GitHub

Writing benchmarks can be a fun and enlightening process, though it's easy to get caught up in the quest for better numbers. Despite this, benchmarks are crucial for performance-conscious development. Modern CPUs and compilers are highly complex, making performance reasoning anything but straightforward.

Linters

Linters keep the code base consistent and help to catch a lot of issues and even bugs way before the compiler is ran. Clang-Tidy is the one I am relying on. IWYU is really helpful in keeping the includes clean, reducing number of dependencies and reducing the build times.

Sanitizers

Sanitizers detect and troubleshoot issues that are difficult to debug, such as memory leaks, concurrency issues, and undefined behavior. ASAN is the one I am using the most. This is the contents of the .bazelrc set adds a special Bazel config so ASAN can be ran at any time on any target by adding --config=asan to the build command:

build:asan --strip=never
build:asan --copt=-fsanitize=address
build:asan --copt=-O0
build:asan --copt=-fno-omit-frame-pointer
build:asan --copt=-DGPR_NO_DIRECT_SYSCALLS
build:asan --copt=-DADDRESS_SANITIZER  # used by absl
build:asan --linkopt=-fsanitize=address
build:asan --action_env=ASAN_OPTIONS=detect_leaks=1:color=always

Other sanitizers worth mentioning are:

Serialization: Protobuf

protobuf.dev

This is a language-agnostic serialization library that is much faster than JSON and provides way more compact representation. There are several implementations with different features and trade offs. μpb is a very lightweight C++ implemantion that uses arena allocations.

Protobufs have a large number of features that are very useful in practice:

Reflection API
JSON serialization
Text serialization (makes it very tempting to use protobufs as a configuration format)

RPC: gRPC

grpc.io

Disclamer: I am working on gRPC full-time so I am biased.

gRPC is another open-source effort that was informed and inspired by Google internal architecture. It is a proven solution (most Google Cloud APIs are implemented in gRPC) and is used by projects like TensorFlow, Firebase and many others (e.g. Bazel uses it for distributed build support).

This is what gRPC offers that is not readily available in REST:

Strongly typed API with codegen support for most popular languages
Streaming support, including bi-directional streaming
Client and server side load balancing
Authentication and authorization support
A lot of configuration options for things like timeouts, retries, etc.
Built-in support for tracing and monitoring

Portable SIMD: Highway

GitHub

One can not utilize the full power of modern CPUs without using SIMD
instructions. Highway library provides a portable way to use SIMD instructions across different platforms, making leveraging SIMD much more practical.

Case Study - TDD in Node.js Inspector Server and Other Projects

Eugene Ostroukhov — Tue, 18 Jun 2024 21:00:00 +0000

Overview

Test Driven Development (TDD) is a software development methodology where tests are written before the actual code. The progress of implementation is then guided by the status of these tests.

There is often confusion between the terms "automated testing," "unit testing," and "TDD." To clarify:

Automated Testing refers to any testing performed by specialized software without requiring manual intervention. This includes various types of testing, depending on the scope (unit/integration) or the metrics being evaluated (correctness, security, load, benchmarking).
Unit Testing is a subset of automated testing that focuses on the smallest, independent logical units of code. These tests can be created at any stage of development, whether before or after the code is written.
Test Driven Development (TDD) is a practice where tests are designed and implemented before writing the actual code. While these tests are typically automated, they can also be manual in some cases. TDD can be applied at any level of granularity.

Node.js Inspector Server

Problem Statement

The goal was to transition Node.js to utilize a new V8 debugging API and expose a WebSocket endpoint compatible with the Chrome DevTools protocol. This required ensuring a smooth ecosystem transition and providing tools vendors with a clear migration path.

Challenges

The implementation needed to reside in the core Node.js binary, adhering to strict performance and security requirements.
The low-level C++ code had to run on all platforms supported by Node.js.
Rebuilding the Node.js binary is a time-consuming process that can significantly impact developer productivity.
I was initially unfamiliar with libuv and the internals of Node.js.

Approach

The initial focus was on creating a WebSocket server in C++ to run outside the V8 engine on a separate thread. This design ensured that the server would continue running even when V8 was paused at a breakpoint, and it also minimized the impact on profiling data of the user code.

To avoid a full rebuild of the Node.js binary during development, the server implementation was initially contained within the test code. As the codebase evolved, it was split into multiple source files and gradually integrated into the core Node.js code.

The current C++ test suite includes:

test_inspector_socket_server.cc: Tests the server, including socket listening, HTTP protocol support, and potential error states.
test_inspector_socket.cc: WebSocket protocol tests with a focus on edge cases and error handling.

One interesting aspect of libuv was that the tests were single-threaded, greatly simplifying the implementation of the test suite. This was a fun coding challenge and crucial for catching hard-to-reproduce bugs and regressions, especially those caused by differences in libuv behavior across platforms.

Once the server was stable and inspector integration began, tests were written in JavaScript using the WebSocket protocol. These tests were not strictly "unit tests," as V8 inspector already had significant testing coverage in the core V8, and duplicating it would have increased maintenance without adding much value.

Later, a JavaScript API was introduced by community demand, making it even easier to write tests in JavaScript, particularly to cover Node-specific protocol extensions such as tracing or workers.

Highlights

The transition to the new protocol was completed ahead of schedule, allowing the legacy protocol to be deprecated and removed altogether. The integration underwent several deep reworks without disrupting the ecosystem, including the addition of support for worker threads. In all cases, new test cases were added to ensure stability.

A significant flakiness in Inspector tests prompted a deep refactor (PR), improving the performance and stability of the entire DevTools protocol.

At least one test case was added to justify keeping code in the native C++ part after contributors proposed moving it to JavaScript.

The community identified several potential security vulnerabilities, leading to the addition of tests to prevent regressions.

Partner API Endpoint

Problem Statement

The task was to implement a REST API endpoint according to the specifications provided by a partner company. Their software would query this endpoint to obtain information from our systems, streamlining the customer experience.

Challenges

The specification required a large amount of the data points, raising concerns about whether we had all the required information or if it was in the expected format.
There were uncertainties about whether the requested access complied with our security and privacy policies.
The necessary information had to be sourced from multiple internal systems, and it was unclear how readily available this data was.

Approach

The service code implementing the API was divided into multiple layers and engineered into several components:

Response Packaging: A component to format the response according to the partner’s specifications.
Data Aggregation and Sanitization: An internal component to aggregate data and ensure it was sanitized (e.g., converting internal codes to the partner’s specifications, normalizing addresses).
Data Source Connectors: Independent components to connect to each internal data source.
Request Processing and Validation: A separate component to handle request validation and processing.

The first test involved directly calling the endpoint implementation with a mock request and checking the response. The initial implementation returned a hardcoded response, which was then gradually enhanced with more logic. E.g. a code that returns a hardcoded customer address would be replaced with a component that retrieved the address from the customer service. Unit tests were created for each component, focusing on mocking dependencies to verify logic, validation, and error propagation. For example, unit tests for the customer service connector mocked the network layer to directly check requests sent to the customer service, and mock responses were used to validate the connector’s logic, both in a happy path and in error scenarios.

Highlights

The project codebase was split into clear maintainable components, enabling parallel development, including discussions with the teams responsible for each data source.
Significant discussions with stakeholders (e.g., service developers, data owners, security, and privacy teams) were necessary, and we were able to start these discussions sooner which reduce the risk of delays.
Testing provided with plenty of examples that were really useful in communications. For example, when discussing the data format with the partner, we could provide examples of the data we were sending, which helped clarify the requirements.

The project was delivered on time and promptly accepted by the partner.

Uchen.ML

Problem Statement

This project began as an attempt to build deep learning models that could be easily deployed in specific scenarios. It was developed alongside learning the theory of deep neural network training. Both the external API and internal implementation were in constant flux, with significant rewrites anticipated.

Approach

Each component started as a test case. For example, each gradient calculator began in the test class, with all numbers verified against values returned by the PyTorch implementation. As the framework matured, the underlying math of the stacked components grew increasingly complex, making the tests essential for detecting subtle issues. Extensive rework often required benchmarks to justify code changes. Writing test cases helped refine the framework's API.

Highlights

The project continues to evolve, despite extended breaks in development. Test cases have been invaluable for catching new issues early, including identifying when new APIs are too cumbersome for unconsidered use cases.

Best Practices

Cleanup aggressively and avoid duplicate test cases. Do not test trivial code (such as getters and setters). Tests have maintanance code and can be a significant draw on engineer productivity and even team morale.
Test behaviors not the implementation. Use higher level APIs and data that mimics the real-world usage.
Use a tool that reruns the tests on file save, such as jest --watch or ibazel
Do not add TODO comments in the code. Add disabled or failing tests instead.

Conclusion

TDD is goes beyond just writing tests; it fundamentally shapes the design and architecture of the code. Tests help understand the requirements and constraints, leading to more robust and error-resistant code. Test cases also serve multiple purposes:

Tracking Implementation Progress: They provide a clear, incremental path of development, showing what features have been implemented and what remains to be done. Each passing test signifies a step forward in the project, offering a sense of accomplishment and a clear indicator of progress.
Onboarding New Team Members: For new developers joining the team, test cases offer a practical insight into the functionality and expected behavior of the software. They serve as an up-to-date documentation that new team members can use to understand the codebase more quickly and effectively.
Providing a Safety Net for Future Changes: One of the most significant benefits of TDD is the confidence it provides when making future modifications. As the software evolves, having a comprehensive suite of tests ensures that new changes do not introduce regressions. This safety net allows developers to refactor and improve the code with greater assurance.

By integrating TDD into the development process, teams can achieve a higher standard of software quality, foster a culture of continuous improvement, and reduce long-term maintenance costs.

Case Study - Optimizing Linear Layer

Eugene Ostroukhov — Mon, 22 Apr 2024 19:00:00 +0000

Overview

As Uchen.ml is heading towards the public announcement and first demos, some low-hanging fruit needs to be picked in terms of optimizations. The most often used piece of any ML library is the linear layer as it is the most basic building block for any neural net. This post details the process of optimizing the code.

Requirements

Uchen is designed for implementing ML solutions that can be easily
integrated into existing systems, with specific goals on Web Assembly, embedded and video games.

To maintain velocity and to avoid overcomplicating build and validation process, following constraints are in place:

Only the C++20 standard library is used. ABSL dependency is there (logging, asserts and some utilities) but it is under consideration if its inclusion will remain mandatory.
No compiler-specific optimizations, including pragmas, conditional compilations or intrinsics.
No CPU architecture-specific optimizations. Particularly, no optimizations for one architecture that may be detrimental for others. Apple M2 and Intel Core CPUs are used to inform and direct the optimization efforts.
Uchen is and will remain a CPU-only ML framework. There are no plans at this point to implement GPU or other acceleration support.

This constraints will be lifted as the deployment targets and actual requirements are better understood.

Benchmark code

The benchmark runs inference through the linear layers of different configurations. Inputs are initialized to 0, parameters are initialized to random values outside the benchmark loop. Range of parameter values is between -1 and 1. Output values are not checked. float datatype is used for inputs and outputs

template <size_t Is, size_t Os, typename D = float>
static void BM_Linear(benchmark::State& state) {
  // Linear layer with Is inputs and Os outputs
  uchen::Linear<uchen::Vector<D, Is>, Os> layer;
  // zero-initialized input vector. This operation is O(n) to the number
  // of the inputs and may have a negligible impact on benchmark.
  uchen::Vector<D, Is> input;
  // Parameters are using the store filled with random values outside the loop.
  // This operation is O(1) to the number of parameters and has no impact
  // on benchmark.
  uchen::parameters_t<decltype(layer)> parameters(params->store());
  for (auto _ : state) {
    benchmark::DoNotOptimize(layer(input, parameters));
  }
}

Hardware

Regular PCs are used. Note that the numbers can not be compared across
the architectures and this paper is only concerned with the relative gains
and not the absolute values.

Apple M2 Pro
  10 Cores
  L1 Data 64 KiB
  L1 Instruction 128 KiB
  L2 Unified 4096 KiB (x10)

Intel(R) Core(TM) i7-10700KF CPU @ 3.80GHz   3.79 GHz
  L1 Data 32 KiB (x8)
  L1 Instruction 32 KiB (x8)
  L2 Unified 256 KiB (x8)
  L3 Unified 16384 KiB (x1)

Naive version

Linear layer runs the following operation to produce the output:

yj=bj+∑i = 0nwjixi

Which translated into the following C++ code:

  output_t operator()(const input_t& inputs,
                      const Parameters<parameter_count>& parameters) const {
    output_t outputs;
    constexpr size_t Is = input_t::elements;
    for (size_t output = 0; output < Outputs; ++output) {
      outputs[output] = parameters[output * (Is + 1) + Is];
      for (size_t input = 0; input < Is; ++input) {
        outputs[output] +=
            inputs[input] * parameters[output * (Is + 1) + input];
      }
    }
    return outputs;
  }

Given n inputs and m outputs, parameters layout is:
Parameters are a flat array in the following format (n is a number of inputs, m is the number of outputs):

{ w00 , ... ,w0n,b0,w10, ... ,wmn,bm}

Benchmark Results:

	Parameter Count	i7-10700KF	Apple M2 Pro
<100, 200>	20,200	13,645 ns	6882 ns
<2500, 8>	20,008	17,086 ns	16,307 ns
<8, 2500>	22,500	5032 ns	2177 ns

Note that the number of operations (memory reads, stores and arithmetic) is directly correlated to the number of parameters so all the models were set up to have roughly the same number of them.

Intel architecture shows approximately 3.4x spread between the best case scenario (number outputs drastically exceeds number of inputs) and worst case scenario (number of inputs is much greater then the number of outputs). Apple ARM implementation showed 7.5x spread.

Transposed iteration order

The first optimization is to change the iteration order. Instead of iterating over the outputs and then over the inputs, we iterate over the inputs and then over the outputs. This change allows for better cache utilization and reduces the number of cache misses.

  output_t operator()(
      const input_t& inputs,
      const Parameters<(Input::elements + 1) * Outputs>& parameters) const {
    auto it = parameters.begin();
    output_t outputs;
    for (size_t i = 0; i < outputs.size(); i++) {
      outputs[i] = *it++;
    }
    for (auto input : inputs) {
      for (auto& output : outputs) {
        output += (*it++) * input;
      }
    }
    return outputs;
  }

Note that the code uses a linear iteration over the parameters, making the memory
access pattern more predictable and cache-friendly.

Parameters layout is as follows (n is a number of inputs, m is the number of outputs):

{ b0, ... ,bm ,w00, ... ,w0n,w10, ... ,wm0}

Benchmark Results:

	i7-10700KF	Apple M2 Pro
100, 200	1880 ns	1326 ns
2500, 8	5611ns	11,124 ns
8, 2500	2015 ns	1354 ns

Number of inputs has a significant negative impact on the performance as it
adds an extra memory load.

Compile for the specific CPU

By default, the compiler generates the code that works on most CPUs. This
precludes usage of some newer instructions that have a significant impact
on the performance. To test this, I pass -march=native to the compiler which
makes it target my current CPU. I am using Bazel, so the invocation looked like
this (-g is for including debugging symbols as I use gdb to look at
the assembly code):

bazel run -c opt --cxxopt="-g" --cxxopt="-march=native" //benchmark:linear

Benchmark Results (Intel only):

	i7-10700KF
100, 200	1203 ns
2500, 8	4871 ns
8, 2500	1080 ns

This "optimization" shows pretty solid across the board. Ultimately, it will be
up to embedders to decide the CPU target to compile for.

A bigger layer

With the numbers in single digit microseconds, it seems reasonable to increase
the size of the linear layer to see what impact it has on the performance.

Benchmark Results (Intel only):

	i7-10700KF
100, 200	1180 ns
2500, 8	5056 ns
8, 2500	1148 ns
4000, 2000	1496652 ns
1000000, 8	2986400 ns
8, 1000000	2185253 ns

The worst case is "only" 2x slower than the best case.

Using SIMD intrinsics directly

As mentioned above, SIMD intrinsics are not considered (i.e. Web Assembly still
has no support for them). However, it is still interesting to see what
the performance gains could be if we tried them. I did not use AVX as data
alignment is not supported yet, though this will change soon.

  output_t operator()(
      const input_t& inputs,
      const Parameters<(Input::elements + 1) * Outputs>& parameters) const {
    auto it = parameters.begin();
    output_t outputs;
    for (size_t i = 0; i < outputs.size(); i++) {
      outputs[i] = (*it++);
    }
    for (size_t i = 0; i < Input::elements; i += 4) {
      __m128 input = _mm_loadu_ps(&(*inputs.begin()) + i);
      for (size_t j = 0; j < Outputs; ++j) {
        // Parameters are accessed in the wrong order - this is a bug!
        // This code is for benchmark only.
        __m128 parameters = _mm_load_ps(&(*it));
        __m128 product = _mm_dp_ps(input, parameters, 0xf1);
        it += 4;
        outputs[j] += _mm_cvtss_f32(product);
      }
    }
    return outputs;
  }
};

Benchmark Results (Intel only):

	i7-10700KF
100, 200	5765 ns
2500, 8	5955 ns
8, 2500	5761 ns
4000, 2000	2783286 ns
1000000, 8	2964343 ns
8, 1000000	3214760 ns

"Good" cases worsened, which shows that the updated code is ran. Shape of
the data is known at compile time when using Uchen so the compilers make
informed decisions about vectorization and other optimizations and it looks
like competing with them is an unnecessary exercise.

Manually unrolling the loop yields similar results:

  output_t operator()(
      const input_t& inputs,
      const Parameters<(Input::elements + 1) * Outputs>& parameters) const {
    auto it = parameters.begin();
    output_t outputs;
    for (size_t i = 0; i < outputs.size(); i++) {
      outputs[i] = (*it++);
    }
    for (auto input : inputs) {
      for (size_t i = 0; i < Outputs; i++) {
        outputs[i++] += (*it++) * input;
        outputs[i++] += (*it++) * input;
        outputs[i++] += (*it++) * input;
        outputs[i] += (*it++) * input;
      }
    }
    return outputs;
  }

	i7-10700KF
100, 200	6523 ns
2500, 8	5088 ns
8, 2500	6763 ns
4000, 2000	3226969 ns
1000000, 8	2918274 ns
8, 1000000	3734533 ns

Conclusion

At this point it looks like the performance on this granularity is pretty close
to the practical limit for a single core. Next article will detail
multi-threading and the memory alignment (particularly, dealing with the number
of parameters not divisible by 8).

The backpropagation optimizations and Uchen's approach to the memory management
will also be detailed in the future articles.