Forem: Kyrylo Rud

PMR Beyond Performance: Deterministic POSIX Signals

Kyrylo Rud — Tue, 17 Feb 2026 07:15:00 +0000

PMR is usually perceived as a performance tool - something to address allocation and deallocation bottlenecks or to build memory models for RTOS-like environments. In practice, its scope is much broader. It has been part of the standard since C++17, yet it is rarely brought up in interviews or public discussions outside of HFT (high frequency trading) or gamedev.

When dealing with signal handling, especially in constrained environments, there are less obvious scenarios where PMR becomes useful. Not because it is faster, but because it provides explicit control over memory usage. Historically, similar problems were solved using C-style stack arenas or manually managed buffers. PMR offers the same idea, but expressed in standard C++ and integrated directly with STD containers, without dropping back to raw C-style memory management.

It brings controlled allocation semantics in places where heap interaction is either undesirable or outright forbidden.

Solution Framing

This technique is not a general recommendation for signal handling.

It is relevant only in environments where a signal handler with some minimal processing is architecturally unavoidable. The goal is not to make signal handling "safe", but to reduce fragility under constrained conditions.

This approach is justified only when:

Recovery or reporting must happen in-process;
External crash reporters or core dumps are unavailable or forbidden;
The required work is strictly bounded and deterministic.

Outside of these constraints, standard crash handling mechanisms remain the correct and preferable solution.

The problem

Here we start

During my career, I have encountered several situations where I had to implement custom SIGSEGV handlers and perform non-trivial work inside them. These were not ideal designs. In some cases, solutions were pragmatic rather than elegant, driven by constraints rather than preference.

In one case, I had to collect a backtrace using libunwind and then post-process it to produce meaningful diagnostic output written directly to stderr. Using something like libSegFault was not an option because additional libraries could not be shipped to the target system and because the required backtrace transformation logic was too specific.
In another project, SIGSEGV handling combined with jump was part of the legacy architecture. After recovering control flow, the system required additional string processing and some container manipulation to restore a consistent internal state. The architecture could not be redesigned, so the handler had to operate within those constraints.
There was no third case, and I hope there will not be. Signal handlers are not something I appreciate having in a binary, except for simple termination logic in service-style applications.

The common theme in these cases was not preference, but constraint.

POSIX constraints

What makes the situation more complex is that signal handlers themselves operate under strict POSIX requirements.
In practice, these constraints can be summarized as follows:

Only async-signal-safe functions may be called (list of functions):
- In practice this mostly means no dynamic memory allocation (new/delete and malloc/free are not permitted);
No dependency on shared mutable state:
- No locks;
- No reliance on global mutable objects;
- errno must be preserved;
- No stream flushing;
- The handler must not return into an undefined state, etc. These rules exist for good reasons, but they significantly narrow what can be done inside a handler.

Abstraction collapse

The practical consequence is that most idiomatic C++ becomes unusable. No standard containers, no convenient string processing, no algorithms, no higher-level abstractions. Everything must be reduced to manual C-style handling.

This is not only inconvenient. It increases complexity, introduces boilerplate, and makes the code harder to read and maintain. Engineers are forced to reimplement low-level logic even when well-tested C++ abstractions already exist. Over time, this creates fragile code paths in precisely the parts of the system that are already operating under failure conditions.

Here is where PMR comes

Some of the signal handler constraints are manageable. Streams & flushing can be replaced with a direct write call. The errno can be restored before exiting. Lock-free code is not particularly difficult when the handler logic is minimal.

The real difficulty appears when higher-level processing is required, especially string manipulation or limited container usage. In a signal context, the usual abstraction layers collapse. The heap cannot be trusted, global state may be inconsistent, and most idiomatic C++ becomes unusable. As a result, everything is pushed down to manual C-style handling with fixed buffers and defensive size calculations.

The core issue is not that C strings are inconvenient. The issue is that we lose a controlled allocation domain.

This is where PMR becomes interesting.

PMR allows us to define a small, bounded memory region - for example, backed by a stack buffer - and treat it as an isolated allocation environment. Containers and strings can operate inside this region without touching the global heap. Allocation becomes deterministic and locally scoped. No global allocator interaction, no hidden heap calls, no cross-boundary side effects.

In this context, PMR is not a performance tool. It is a way to create a controlled micro-environment inside an otherwise unstable execution state. By routing all container allocations through a stack-backed memory_resource, we regain limited use of C++ abstractions while following the fundamental restriction: no dynamic heap interaction.

Using PMR to allocate all container elements from a predefined stack buffer is often all that is required.

How big of a stack do we need?

On modern OSes, a typical thread stack is on the order of megabytes (often around 8 MB by default). For the kind of work we are discussing - bounded string formatting, a few small containers, some backtrace post-processing - this is usually plenty. For a rough mental model, even fairly large text payloads are tiny compared to megabytes (the plain text of LOTR is only tens of kilobytes). So, the default alternative stack sizes provided by modern systems are typically sufficient for the strictly limited and minimal processing expected inside such a handler.

However, in a SIGSEGV scenario we must not rely on the current thread stack. If the signal was triggered due to stack corruption or overflow, that memory cannot be considered reliable. This is why the practical "stack budget" for PMR in a handler is not the normal thread stack, but the alternative signal stack configured via sigaltstack, which we will get to later. At least size order is clear for now.

The key point remains the same: the memory must already exist and be bounded, because the handler must not allocate dynamically. Heap allocation is not async-signal-safe under POSIX, so new/delete and malloc/free are off the table.

Basic setup

Conceptually, the setup is straightforward. We pre-allocate a fixed buffer in memory and construct a std::pmr::monotonic_buffer_resource on top of it. That resource becomes the allocation domain for all containers used inside the handler.

auto buf = std::array<std::byte, 1024>{}; // Stack-backed allocation buffer
auto res = std::pmr::monotonic_buffer_resource{
    buf.data(),
    buf.size(),
    std::pmr::null_memory_resource() // Forbid fallback to global heap
};

Note: A monotonic buffer resource performs linear allocation within a pre-defined memory region. It does not free individual objects. Memory is reclaimed only when the resource itself is destroyed. In the context of a signal handler, this behavior is desirable: the lifetime of all temporary objects is tied to the lifetime of the handler invocation itself.

The only parameter that requires deliberate consideration is the size of the buffer. It must be large enough to accommodate the worst-case amount of memory required by all containers and strings constructed inside the handler. Since the work performed in the handler must be strictly bounded and deterministic, the required size can and should be estimated conservatively.

Containers are then constructed using the memory resource explicitly. Any std::pmr container instantiated with this resource will allocate exclusively from the provided buffer and will not fall back to the global heap (this is guaranteed by std::pmr::null_memory_resource as an upstream allocator).

auto str = std::pmr::string{&res};
str = "some text buffer";

auto collection = std::pmr::vector<decltype(str)>{&res};
collection.emplace_back(str);

The result is limited but controlled use of C++ abstractions within a strictly bounded memory region.

Following the standard

The minimal example will work on most systems, but according to the standard, a std::pmr::memory_resource::allocate call must return storage that is properly aligned for the requested type. Otherwise, if the underlying buffer does not satisfy the required alignment - it is UB.

The buffer used to back the monotonic_buffer_resource must therefore be aligned at least to std::max_align_t, or to any stricter alignment that might be required by the types allocated within it.

alignas(std::max_align_t) auto buf = std::array<std::byte, 1024>{};

Allocates storage with a size of at least bytes bytes, aligned to the specified alignment.
Source

With correct alignment in place, the PMR containers can be safely instantiated on top of the resource.

Remaining risks on the table

Using PMR inside a signal handler does not make the handler POSIX-safe. It removes only one, but major failure source: heap interaction during an unstable runtime state.

Even with a stack-backed allocation domain, significant risks remain:

corrupted stack or registers;
undefined C++ runtime state;
library code that is not async-signal-safe.

With correct alignment in place, PMR containers can be safely instantiated on top of the resource. However, this only addresses allocation mechanics. It does not eliminate the broader execution risks inherent to signal handling.

Strict constraints must still be respected:

Avoid code paths that may throw exceptions. Unwinding through potentially corrupted state is undefined territory;
Avoid synchronization primitives or any form of parallelism. No locks, no hidden synchronization inside abstractions;
Keep the work strictly bounded and deterministic.

In the typical scenario discussed here - limited string formatting or small container manipulation - these constraints are technically manageable.
However, care must be taken to avoid accidental violations. Parallelism, for example, can be introduced indirectly through execution policies in standard algorithms.
Even without explicitly creating threads, such behavior may break the assumptions required for safe execution inside a signal handler.

Therefore, the real guarantee of this approach is limited to:

Reduced fragility under controlled assumptions - not absolute correctness.

Prepare stack for the PMR

One of the most important measures is configuring an alternative signal stack via sigaltstack. This addresses at least two of the previously mentioned risks:

It isolates the handler from a potentially corrupted or overflowed main thread stack.
It provides a predictable and explicitly controlled stack size for handler execution.

By running the handler on an alternative stack, we reduce dependency on the original execution context. If the signal was triggered due to stack overflow or memory corruption, continuing execution on the same stack would be unsafe. The alternative stack provides a separate, pre-allocated memory region dedicated to signal handling.

The setup itself is straightforward and based on SIGSTKSZ, which defines a minimal recommended stack size for signal handlers.

// main:
const auto size = static_cast<std::size_t>(SIGSTKSZ) * 4;

auto alt_stack = stack_t{};
alt_stack.ss_sp    = ::operator new(size);
alt_stack.ss_flags = 0;
alt_stack.ss_size  = size;

if (::sigaltstack(&alt_stack, nullptr) != 0) {
   throw std::runtime_error{
      std::string{"sigaltstack failed: "} + std::strerror(errno)
   };
}

The value of SIGSTKSZ is platform-dependent and defined in signal.h. In practice, it may range from relatively small values on lightweight systems to significantly larger defaults on desktop platforms. Because of this variability, it is reasonable to scale it conservatively or validate assumptions at compile time with static_assert, depending on the expected workload of the handler.

The important architectural point is that the alternative stack size must be sufficient not only for the PMR buffer but also for the execution overhead of the handler itself. The PMR buffer lives inside that stack context, so both data and control flow must fit within the allocated space.

While this does not eliminate all risks associated with signal handling, it allows us to control stack integrity and stack capacity explicitly, which removes two major sources of uncertainty.

Putting it together

With all components in place, the overall design becomes straightforward. The goal is to establish two controlled boundaries before the failure: a dedicated execution stack and a bounded allocation domain. Once those are prepared during normal program initialization, the handler itself becomes a small, deterministic unit operating inside explicitly defined limits.

The flow looks like this:

Allocate and register an alternative signal stack (sigaltstack) so the handler does not depend on the potentially corrupted thread stack;
Install a SIGSEGV handler with sigaction, enabling SA_ONSTACK so the handler runs on that alternative stack;
Inside the handler, create a fixed, aligned buffer and build a std::pmr::monotonic_buffer_resource on top of it, with std::pmr::null_memory_resource as the upstream. This ensures allocations stay local and never fall back to the heap;
Use PMR-backed types (for example, std::pmr::string) for minimal formatting, then emit output via an async-signal-safe API such as write, and terminate via _exit to avoid returning into an unknown runtime state.

#include <array>
#include <cerrno>
#include <charconv>
#include <cstddef>
#include <cstdlib>
#include <cstring>
#include <memory_resource>
#include <new>
#include <stdexcept>
#include <string>

#include <signal.h>
#include <unistd.h>

constexpr auto signal_exit_base = 0x80; // POSIX: 128 + signal number

static void handler(int sig) {
   alignas(std::max_align_t)
   auto buf = std::array<std::byte, 1024>{};
   auto res = std::pmr::monotonic_buffer_resource{
      buf.data(), buf.size(),
      std::pmr::null_memory_resource()
   };

   auto str = std::pmr::string{"Signal ", &res};
   auto num = std::pmr::string(16, '\0', &res);

   auto [ptr, _] = std::to_chars(num.data(), num.data() + num.size(), sig);
   num.resize(static_cast<std::size_t>(ptr - num.data()));

   str += num;
   str += " received!\n";

   ::write(STDOUT_FILENO, str.data(), str.size());
   ::_exit(signal_exit_base + sig);
}

auto main() -> int {
   const auto size = static_cast<std::size_t>(SIGSTKSZ) * 4;

   auto alt_stack = stack_t{};
   alt_stack.ss_sp    = ::operator new(size);
   alt_stack.ss_flags = 0;
   alt_stack.ss_size  = size;

   if (::sigaltstack(&alt_stack, nullptr) != 0) {
      throw std::runtime_error{
         std::string{"sigaltstack failed: "} + std::strerror(errno)
      };
   }

   struct sigaction sa{};
   sa.sa_handler = handler;
   sa.sa_flags   = SA_ONSTACK;
   ::sigemptyset(&sa.sa_mask);

   if (::sigaction(SIGSEGV, &sa, nullptr) != 0) {
      throw std::runtime_error{
         std::string{"sigaction failed: "} + std::strerror(errno)
      };
   }

   *static_cast<volatile int*>(nullptr) = 42; // trigger SIGSEGV
   return EXIT_SUCCESS;
}

If you compile and run this with ltrace (and optionally pipe through c++filt), you can observe the behavior when the signal is delivered:

the alternative stack setup happens during normal execution (before the crash);
inside the handler, PMR allocations stay within the provided buffer;
there is no interaction with the global heap allocator from within the handler path.

$ ltrace ./a.out some here  &>/dev/stdout | c++filt 
__libc_start_main(0xaaaac2042290, 3, 0xffffed93df28, 0xaaaac2041d18 <unfinished ...>
__register_frame_info(0xaaaac2046200, 0xaaaac2060018, 16, 0xffffb2baeab4) = 9
operator new(unsigned long)(0xc000, 0, 0xffffed93df48, 0xffffb2bae338) = 0xffffb2adf030
sigaltstack(0xaaaac2060048, 0, 0xffffffa0, 4044) = 0
sigemptyset(<>)                                  = 0
sigaction(SIGSEGV, { 0xaaaac20420c0, <>, 0, 0 }, nil) = 0
--- SIGSEGV (Segmentation fault) ---
memset(0xffffb2ae99a0, '\0', 1024)               = 0xffffb2ae99a0
std::pmr::null_memory_resource()(0xffffb2ae99a0, 0, -32, 0xffffb2ae9d40) = 0xffffb2ac0178
strlen("Signal ")                                = 7
memcpy(0xffffb2ae9968, "Signal ", 7)             = 0xffffb2ae9968
memset(0xffffb2ae99a0, '\0', 16)                 = 0xffffb2ae99a0
memcpy(0xffffb2ae996f, "11", 2)                  = 0xffffb2ae996f
strlen(" received!\n")                           = 11
memcpy(0xffffb2ae99b1, "Signal 11", 9)           = 0xffffb2ae99b1
memcpy(0xffffb2ae99ba, " received!\n", 11)       = 0xffffb2ae99ba
write(1, "Signal 11 received!\n", 20Signal 11 received!
)            = 20
_exit(139 <no return ...>
+++ exited (status 139) +++

The exit status is preserved, and it is clear that no heap allocation takes place inside the handler. This still does not make the handler "POSIX safe" in the absolute sense. It only demonstrates that, from the source code perspective, the handler avoids the most common contract violations (most notably: dynamic allocation and unsafe I/O abstractions).

One optional hardening step is to compile the handler in a separate translation unit with stricter flags (for example, disabling exceptions). This can reduce accidental violations, but it also increases build complexity and can make integration more fragile. In most cases, keeping the handler minimal and explicitly bounded is the more practical approach.

Takeaway

PMR has a place far beyond performance tuning. In certain constrained environments, it can serve as a controlled allocation boundary rather than an optimization tool.

Used carefully, it allows limited reintroduction of C++ abstractions into contexts where they would normally be forbidden, such as inside a signal handler. It does not make signal handling safe or eliminate UB. What it does is remove one significant failure vector - uncontrolled heap interaction - and reduce boilerplate compared to manual C-style buffer management.

As with anything related to POSIX signal safety, this approach must be applied conservatively and with a clear understanding of its limits, it can meaningfully improve clarity and robustness in otherwise fragile code paths.

When Big O Lies

Kyrylo Rud — Sun, 16 Nov 2025 15:38:57 +0000

Since the academy era and throughout documentation digging, the Big O has been a de-facto standard for evaluating algorithms: from sorting and look-up in a collection to insertion operations or even simple palindrome checks (especially in interview live-coding sessions).

However, efficiency is not the same as "best to use in this case".
What actually measures Big O, how it scales and what could it lie about? Let’s dive deeper to the roots of the Big O and what could help developers to choose algorithms smarter. Especially when it comes to implementation, maintainability and long-term support of algorithms written by hand and not fetched from the standard library.

Disclaimer
This article focuses on practical understanding of algorithmic complexity for real-world engineering.
The explanation of asymptotic notation is intentionally simplified and does not cover all formal mathematical details (Θ, Ω, ω, etc.).
All performance comparisons assume typical hardware behavior and ignore machine-specific optimizations unless stated.
The small-N "impossible cases" are illustrative and not meant as practical recommendations.

What the Big O measures?

Big O is, foremost, a mathematical notation, defined by German mathematicians Paul Bachmann, Edmund Landau, and others, normally called the “Bachmann-Landau notation” or simply "Big O". It exists for more than 100 years, already.

The "o" part comes from order of approximation, basically "how fast something [algorithm complexity] grows".
Grate, but where does the "big" come from? Actually, there are couple 'o' types.

Analysis of an algorithm can be done in various ways, and the "O" notation helps to classify them into:

Big O notation - the algorithm works at most this fast;
Little-o notation - the algorithm works always strictly slower than this;
Other notations such as Big Omega, Little Omega, etc. (not covered in this article).

Note: It is incorrect to state that the worst case of an algorithm is the same as the little-o notation. Little-o has nothing to do with worst-case vs. best-case.
While Big O allows the runtime to reach the upper bound, Little-o requires the runtime to eventually never reach the stated bound. These statements might look confusing right now, but they will become clear a bit later.
So, there is no practical way to express one in terms of the other, since they measure different metrics.

Note: However, to understand the Big O easier, it can be simply stated: the function does not grow faster than some constant multiplied by n.

Basically, the impracticality of the little-O (difficulty of proving that an algorithm would never reach a certain bound) led to the popularity, wide adoption, and everyday usage of the Big O in the programming world. However, this order of things is mostly relevant to software engineering; in mathematics the situation is different.

It allows to understand the rate at which an algorithm grows depending on the amount of input data. The key idea is: it is not a guarantee of actual algorithm speed, but rather a reference to how complex it becomes as the input size grows.

This is where the idea of time-complexity comes from: the scaling behavior of runtime as N increases.

Note: Big O hides constants, machine effects, memory patterns, branch prediction, etc. Some algorithms may execute (not work, but execute) faster despite the Big O analysis due to cache locality, compiler-level machine code optimizations, and similar factors.

Growth rate

Any article that explains the Big O usually references the following picture.

This picture shows multiple function graphs of the Big O growth rate. Any algorithm can be expressed through one of these common complexity classes (function graphs). However, it is not limited to them, and a more precise growth rate can be expressed with a custom equation.

The following functions are de-facto standards for most common algorithms. Their origin comes from mathematics and from "natural" algorithmic patterns (natural meaning: what you would intuitively expect from the algorithm's structure):

O(n!) - exploring all permutations;
O(2ⁿ) - exploring all subsets;
O(n²) - nested loops or matrix operations;
O(n log n) - divide-and-conquer patterns where data is split repeatedly and merged in linear time (e.g., merge sort, heapsort);
O(n) - effectively one pass over each item of the data;
O(√n) - geometric search spaces (e.g., 2-D grids);
O(log n) - halving work, where each iteration removes half of the remaining data (e.g. binary search).

Note: While O(log₂ n) a.k.a. O(ln n) and O(log₁₀ n) may differ in actual runtime, they belong to the same complexity class — O(log n). > But the distinction between them will be explained later.
Meanwhile, the O(n log n) is a different class altogether, combining linear and logarithmic growth.

But what would be faster: jump search or binary search?
The natural answer is: binary search, of course, since the growth rate of O(log n) is lower than that of O(√n).

The problem is that, apart from the "implementation quality" of the algorithm (how clean the code is, whether there are redundant checks, etc.), there is always the K-factor.

K-Factor and asymptotic analysis

When the Big O is mentioned, it is never bound to the context of input data (what is actually expected). Complexity of the input algorithm is discovered from the infinite POV (analyzed in the limit as input size approaches infinity).

Any algorithm with complexity class O(log n) would be faster than O(√n). Right?

It may sound obvious that one function's growth rate is expected to be much faster than another one.

Analyzing an algorithm's complexity growth rate as the input size increases is asymptotic analysis. There are two practical perspectives for the Big O:

asymptotic (infinite-N behavior) - basically what is represented in documentation for most algorithms (e.g. quicksort is O(n log n));
pre-asymptotic (finite-N behavior) - rarely documented (because context matters: which algorithms are being compared, and which N-range is relevant), although it can be useful when comparing algorithms on specific datasets or limited input sizes.

Asymptotically speaking (analysis of a function in the limit as N → ∞), the growth of function A can be faster than the growth of function B - this is the case with all the "standard" growth rates (complexity classes) usually compared on graphs.

But what would happen when the algorithm has constants? Well, here is where K-factor kicks in, as well as pre-asymptotics!

I’m using the old K-factor naming here - a little habit I carried from early C/C++ and embeded style guides, where K was the go-to marker (prefix) for constants like kConstantValue.
Also, using "C-factor" would sound confusingly close to the C programming language itself, so sticking with the traditional "K".

Let's take a look on O(√n) and O(log n) again, the same picture as before (apart from the negative time complexity for logarithms where N < 1 - this is impractical for algorithms, but a function graph is a function graph).

We can clearly see that O(log n) is unconditionally "faster" (grows more slowly asymptotically), which is great. However, if there were some factor that affects it with a small constant, let’s say K = 2, then we would see a very different picture.

This drastically changes the situation: these curves never intersect without the constant factor. Now, on the scale where N < 75, there are two cross-points, at approximately N ≈ 2 and N ≈ 74.
Therefore, in theory, on the range 2 < N < 74, the O(√n) algorithm would be more efficient than O(2 log n), regardless of the asymptotic analysis.
This is pre-asymptotic behavior.

Note: The constant is usually greater than 2, as it may depend on various extra comparisons or operations inside the algorithm that improve it asymptotically.

Asymptotically, the O(2 log n) is equal to O(log n) (have same growth rate = belong to the same class; this is one-way equation), since constants are not relevant in Big O analysis.

Such one-way equations (the naming is suggested by Donald Knuth), are basically an abuse of notation, but widely used and contextually & semantically clear. The more correct notation would be 2 log n ∈ O(log n).

From the Big O perspective: constants never move a function to a different complexity class - ever. And notation O(2 log n) is incorrect (extra constants are redundant asymptotically), but it is well-understandable.

Note: As mentioned earlier, O(log₂ n) and O(log₁₀ n) may differ in actual runtime but belong to the same complexity class.
This is exactly why, in asymptotic analysis, all logarithms are collapsed into the generic O(log n).
In the infinite-N limit, their differences reduce to constant factors, and constants disappear. This is why documentation almost always writes O(log n), even when the underlying behavior is specifically O(log₂ n), etc.

On the large scale it might not matter, but in applied programming it is actually important - especially in performance management.

In practice, knowing how high the N-scale is expected on average (or consistently) can significantly save precious CPU cycles, even if this is counter-intuitive from the Big O perspective. Even a subtle complexity difference can play its role.

Note: This particular example is for demonstration only; in practice there are no pure O(√n) algorithms. Some constant is always present, so it never behaves as a "real" O(√n).

Zooming too close

Let's zoom in, maybe too much, into the region where N < 10.
At this scale, the complexity curves behave very differently from what could be expected. Some functions dip below zero (for example, O(log n) becomes negative for 0 < n < 1), while others appear to cross each other or even briefly reverse their asymptotic complexity order. And, of course, O(log n) never has zero-cost even for small N.

For algorithms and Big O, N is always a positive integer, and meaningful values begin at N = 1, since it represents the size of the input data.

However, even though this small region is not practically relevant, it shows a trend: the shape of each curve hints at where crossover points may appear when constants (the K-factor) are introduced.

If the growth rates differ only slightly (for example, O(√n) vs O(log n)), a sufficiently big constant may shift the curves so that one algorithm becomes faster than the other for some realistic inputs, as we saw before. And even more, as we are going to see.

All pre-asymptotic behavior starts from this region. It is helpful to explore it in a graphical calculator to understand the trends better. The K-factor may be small, but experimenting with graphs makes it much easier to visualize and remember how constants shift the curves.

Practical example

Let's have a look at sorting algorithms again, and probably the most iconic example of them: quick sort vs. insertion sort.

Quick sort has a reputation as the most optimized and the fastest sorting algorithm for a common use-case (which does not exist, of course). The actual quirk, as we saw, is that: being faster from the asymptotic POV does not mean it is faster on the pre-asymptotic scale.

Let's implement the quick and insertion sort in the simplest reincarnation and see the pre-asymptotic in action.

Insertion Sort

The insertion sort algorithm is used in the loop-based version, not the recursive one, since the main difference between them is the extra stack frames in the recursive version. The loop version is better for a C++ use-case (not a pure functional language).

Note: C++ is not a pure functional language, so the compiler cannot guarantee automatic tail-call optimization. Therefore, recursive permutations create stack frames, while iterative permutations avoid this overhead.

Also, the shift variation is used in this particular case rather than swap, to reduce the number of assignments.

algorithm insertion_sort(A, lo, hi) is
  for i := lo + 1 to hi do
    x := A[i]
    j := i
    while j > lo and A[j - 1] > x do
      A[j] := A[j - 1]
      j := j - 1
    A[j] := x

Source

Note: pseudo-code slightly formatted and stylized to align with the general style of the article.

Literal translation to the C++ will look like:

void insertion_sort(std::span<int> A) {
    int i = 1;
    while (i < A.size()) {
        int x = A[i];
        int j = i;
        while (j > 0 && A[j - 1] > x) {
            A[j] = A[j - 1];
            j = j - 1;
        }
        A[j] = x;
        i = i + 1;
    }
}

Or slightly shorter and cleaner without changing the flow of the algorithm:

void insertion_sort(std::span<int> A) {
    for( auto size = A.size(), i = 1; i < size; ++i ) {
        int x = A[i];
        auto j = i;
        while( j > 0 && A[j - 1] > x ) {
            A[j] = A[j - 1]; // Note: shift right, not swap!
            --j;
        }
        A[j] = x; // Note: place saved value
    }
}

Note: using std::swap adds 2 extra assignments per inner-loop step compared to shifting, because:

swap = 3 writes / per inner loop;

shift = 1 write / per inner loop.

Quick Sort

To keep things fair with respect to insertion sort, the Hoare partition scheme variation of quick sort is used.
It is more efficient, since it performs fewer swaps. It uses recursion, but it can be used "as-is" in the C++ implementation, since the average depth of the call stack is O(log n), with the worst case being O(n), while insertion sort’s call stack depth is always O(n).

algorithm quick_sort(A, lo, hi) is
  if lo >= 0 && lo < hi then
    lt, gt := partition(A, lo, hi)
    quicksort(A, lo, lt - 1)
    quicksort(A, gt + 1, hi)

algorithm partition(A, lo, hi) is
  pivot := A[(lo + hi) / 2]
  lt := lo
  eq := lo
  gt := hi
  while eq <= gt do
    if A[eq] < pivot then
      swap A[eq] with A[lt]
      lt := lt + 1
      eq := eq + 1
    else if A[eq] > pivot then
      swap A[eq] with A[gt]
      gt := gt - 1
    else
      eq := eq + 1
  return lt, gt
Source

Note: pseudo-code slightly formatted and stylized to align with the general style of the article.

Note: the partition function used here is technically the three-way partitioning approach (also known as the DNF partition). I originally referred to it as "Hoare partition", but strictly speaking Hoare’s classic scheme uses only two pointers and does not form an explicit middle region. The 3-way version is simply a more practical refinement often used in modern quicksorts.

Direct C++ implementation has, virtually no difference from the pseudocode:

inline auto partition_span(std::span<int> A, int lo, int hi) {
  int pivot = A[(lo + hi) / 2];
  int lt = lo;
  int eq = lo;
  int gt = hi;

  while (eq <= gt) {
    if (A[eq] < pivot) {
      std::swap(A[eq], A[lt]);
      lt++; eq++;
    } else if (A[eq] > pivot) {
      std::swap(A[eq], A[gt]);
      gt--;
    } else {
      eq++;
    }
  }
  return std::make_pair{lt, gt};
}

inline void quick_sort_impl(std::span<int> A, int lo, int hi) {
  if (lo >= 0 && lo < hi) {
    auto [lt, gt] = partition_span(A, lo, hi);
    quick_sort_impl(A, lo, lt - 1);
    quick_sort_impl(A, gt + 1, hi);
  }
}

void quick_sort(std::span<int> A) {
  if (!A.empty()) {
    quick_sort_impl(A, 0, static_cast<int>(A.size() - 1));
  }
}

Benchmarking

The quick "toy" benchmark, sorting over ~300 arrays with random unique values (insertion and quick sort use the same input data), shows the following trend.

Adding the reference graphs to the picture shows the actual difference between real-life execution and the estimated Big O values. The difference is caused by the K-factor.

Note: The O(n²) and O(n log n) values shown are the average-case complexities of insertion sort and quick sort, respectively.

With an appropriate K-factor, the reference curves can be aligned closely with the empirical measurements. The constant is computed as K = med(Sₘ) / med(F[Sₘ]), where F[Sₘ] = { F(n) | n ∈ Sₘ }. The Sₘ denotes the set containing the last m empirical measurements (typically about 0.5% of the dataset is sufficient), and F is the corresponding Big O complexity function evaluated over the same subset.

The general trend is aligned with asymptotic analysis: O(n log n) is faster than O(n²), as expected.

However, if we zoom in to the scale of N <= 60, we can clearly see that suddenly insertion sort is faster than quick sort, and the trend has flipped.

Although, the theoretical crossover point is expected to appear around N ≈ 40, the empirical data shows it closer to N ≈ 45. This small shift is completely normal and can come from things like machine-level optimizations, cache locality effects, or simply the fact that insertion sort avoids recursion.

Ultimately, it doesn't change the bigger picture, but implementation details always affect the runtime performance.

Standard libraries are always moving in the direction of optimization. This is why so many of them almost never use pure quick sort.
Below is a part of the quick sort implementation in libc++ from the LLVM project v21.

// The main sorting function.  Implements introsort combined with other ideas:
//  - option of using block quick sort for partitioning,
//  - guarded and unguarded insertion sort for small lengths,
//  - Tuckey's ninther technique for computing the pivot,
//  - check on whether partition was not required.
// The implementation is partly based on Orson Peters' pattern-defeating
// quicksort, published at: <https://github.com/orlp/pdqsort>.
void __introsort(...) {
  // Upper bound for using insertion sort for sorting.
  _LIBCPP_CONSTEXPR difference_type __limit = 24;
  ...
  if (__len < __limit) {
    std::__insertion_sort(...);
  }
  ...
}

Source

The quick and insertion sort are, obviously, not the whole optimization. However, the selection logic (insertion vs. quick sort) is clearly there: use insertion sort for collections smaller than 24 elements.

Note: One of the reasons why, in simple benchmarking, insertion sort wins by such a large margin vs. quick sort (~45 vs. 24) is that the example does not include challenges like cache locality, non-unique elements, or partially sorted data. Changing the dataset or the data distribution may significantly reduce the gap between insertion and quick sort.
For a broader overview of some of these effects, check: Global Scientific Journal - "Comparison between Quicksort, MergeSort and Insertion Sort".

But why is insertion sort faster than quick sort? Well, this is not purely an asymptotic issue. There are other reasons for this, such as:

no recursion (as mentioned in the algorithm variation description);
contiguous memory;
extremely cache-friendly behavior;
stable branch prediction;
fewer instructions;
etc.

Note: The list of reasons why algorithm A can be faster than algorithm B is not limited to asymptotic/pre-asymptotic behavior, and is also influenced by the actual physical manifestation of the algorithm on specific hardware.

Key Takeaways

The Big O can evaluate the complexity growth rate for any algorithm used in code. However, the asymptotic essence of documented algorithms does not allow to be sure which algorithm will be "faster" at a specific scale.

Standard library algorithms are usually optimized very well. But when an algorithm is custom-written for a specific application, not only pre-asymptotic behavior but also hardware optimization levels, CPU characteristics, and instruction patterns may affect the performance management pretty much.

The best approach is not only to understand the K-factor of the algorithm, but also to understand where this algorithm is applied. This includes, but is not limited to, knowing the median/average/edge-case ranges of the N-scale.

But what is a "big enough" N? When will the asymptotics show the difference according to the Big O estimation? This purely depends on the specifics of the algorithm, the data distribution, and many other factors. As with the "quick/insertion sort" issue, the cross-point could be:

below N ≈ 45 in a simple benchmark;
below N ≈ 24 in the standard C++ library implementation;
above 10ᵐ, depending on the dataset, cache locality, machine code, etc.

The actual cross-point may vary noticeably - sometimes by several orders of magnitude.

Remember, Big O is neither a performance factor nor actual runtime. It is only the rate of complexity growth, always specified in the asymptotic sense (not from the pre-asymptotic POV). This requires in-depth analysis during optimization and may give relatively easy performance wins.

Optional Is Not Optional in C++ (and Definitely Not a Pointer)

Kyrylo Rud — Wed, 05 Nov 2025 17:59:25 +0000

Last week I had a chat with a few fellow C++ devs, and I was genuinely surprised; some still avoid using std::optional and std::expected. Reason?

This adds extra indirects while access as well as memory allocation.

Basically, there is a belief that they are implemented over pointers. It still pops up more often than you could guess, but it's simply wrong.
Neither std::optional nor std::expected use pointers or heap allocations to store data. Everything lives on the stack - lightweight, fast, and predictable.

Let's finally put that myth to rest.

The std::optional<T> is just a lightweight wrapper around a value of type T, plus a status flag that tells whether it's initialized. No heap or pointer usage at all; conceptually, it looks like:

template <typename T>
struct optional
{
  bool is_initialized_;
  typename aligned_storage<sizeof(T), alignof(T)>::type storage_;
};

When it is assigned or constructed, the object is placed in place inside storage. If it's empty, the storage just stays uninitialized.

Optional does not allocate memory. So it can do without allocators.

Standard says.

The std::expected<T, E> is very similar in spirit - a lightweight value wrapper, but with additional functionality. Instead of just saying "has value or not", it holds either a value of type T or an error of type E.
Again, no heap or pointer usage - just a union that lives on the stack:

template<class T, class E>
class expected {
  bool has_val;
  union
  {
    T val;
    E unex;
  };
};

When you construct it, either val or unex is placed in place inside the union. Switching between value and error only toggles which part of the union is active.

The std::expected also has another specification for void type; however, this is not relevant in this context and essentially goes pretty close to the std::optional implementation:

template<class T, class E>
class expected {
  bool has_val;
  union
  {
    E unex;
  };
};

Any object of expected<T, E> either contains a value of type T or a value of type E within its own storage. Implementations are not permitted to use additional storage, such as dynamic memory, to allocate the object of type T or the object of type E.

Standard says.

Let's summarize - the std::optional and the std::expected are stack-based, safe, and cheap - no hidden allocations.
They behave like any other value wrapper, just adding a status flag (normally 1 byte, rounded by padding).

Use them instead of raw pointers or C-style sentinels.
They're modern C++ tools - fast, expressive, and made for exactly this job.

Do NOT reinvent them with pointers;
Do NOT avoid them thinking they are one;
Do USE them if you need this functionality.

Historical reference, or at least my best guess, what was the origin of this everlasting myth, which finds us even after several new standards after the std::optional introduction.

I was curious what actually creates these misconceptions. Simple answer: we used pointers and NULL as std::nullopt in C code - didn't cut it for me.

During research, I found several articles and comments that summarize to pointers == optional even in the context of C++ and here are a few examples:

What makes an optional an optional?

It either contains a value or nothing.

We can query an optional whether it contains a value or not.

We can retrieve the value if there is any. Turns out: a ordinary pointer just like in C has exactly these properties ... pointers and optionals are quite similar

Source

Also another one:

Rule of thumb (for me) is pointer types are nullable and therefore inherently 'optional'

Source

Quick note regarding these quotes:
I trimmed some context from these quotes but tried not to distort their meaning. My main concern here - comparing pointers and optionals is fundamentally incorrect. The fact that you can use them for similar tasks doesn't make a mallet out of a microscope.

The nullptr is just a convention meaning "points to nothing", but that "nothing" is still something - which is why std::optional is a more precise and safer way to express absence.

Then I stumbled upon this C++ standards paper, and I think I finally saw where all the myths came from - beyond just "similar functionality."

Julius Caesar: "Et tu, Boost?"
Boost: "Not betrayal - legacy."

44 BC (~ -6.3 × 10¹⁰ Unix time)

In a comparison between boost::optional and the std::optional proposal, there's a line that says:

"explicit convert to ptr - no [proposal fror std], yes [boost::optional]"

Standard says.

In boost::optional there's a method documented as: "Returns a pointer to the value if this is initialized, otherwise, returns NULL."
This method is (are):

get_pointer method in v1.30 (introduction of boost::optional);
get_ptr method since v1.31 until nowadays.

Unfortunately, there's no paper or rationale explaining why fetching the value by pointer was considered necessary.

My guess is this ties directly to C-like design habits that still influence modern C++ developers through these myths. Boost's impact on C++ is hard to overstate - and those early interfaces continue to shape misunderstandings about std::optional and std::expected, often leading people to avoid them or, worse, recreate unsafe patterns from the past.

To my knowledge, none of the popular C++ libraries has ever implemented an optional utilizing pointers internally. However, the introduction of this rather confusing get_ptr by boost::optional could mislead some developers. Especially, while at the time of widelly used pointers to provide nulling values in C code-bases.

The naming alone was more than enough to reinforce the illusion of pointer-based implementation and keep this myth alive until today.

P.S. In modern C++, both std::optional and std::expected provide the indirection (operator*) and member access (operator->) operators to access their contained values. These operators express generalized value access rather than raw pointer semantics, making them a clearer and more natural choice than the old boost::optional::get_ptr() method.