Showing posts with label cpp_code_design. Show all posts
Showing posts with label cpp_code_design. Show all posts

Jan 3, 2026

[C++] Equality preservation

Reference:
Equality preservation

Equality Preservation is a rule that says a function (or expression) must be "well-behaved" and "predictable."

It essentially means: If you give it the same inputs, you should get the same outputs.

  • The Core Idea: "No Surprises"
If we have two objects, a and b, and they are equal (a == b), then doing the same thing to both of them should result in the same outcome.

Equal Inputs -> Equal Results: If f(a) returns 5, and a == b, then f(b) must also return 5.
Equal Inputs -> Equal Side Effects: If calling f(a) changes a to 10, then calling f(b) must change b to 10.
  • The Requirement of "Stability"
The standard also requires equality-preserving expressions to be stable. This means if we haven't changed the object ourselves, calling the function twice on the same object must give the same result both times.

Example of something NOT stable:
A function that returns a random number or a function that uses a global counter that increments every time you call it. i.e. has no Referential transparency
    int counter = 0;
    int bad_function(int x) { return x + (counter++); } // NOT equality-preserving


By requiring concepts to be equality-preserving, C++ guarantees that:
  • The algorithm can trust the values it reads.
  • The algorithm can safely make copies of objects and expect the copies to behave exactly like the originals.

Unless noted otherwise, every expression used in a requires expression of the standard library concepts is required to be equality preserving, and the evaluation of the expression may modify only its non-constant operands. Operands that are constant must not be modified.

In the standard library, the following concepts are allowed to have non equality-preserving requires expressions:
  • output_iterator
  • indirectly_writable
  • invocable
  • weakly_incrementable
  • range

Nov 25, 2025

[ACCU 2005] Learning To Stop Writing C++ Code minute

Learning To Stop Writing C++ Code (and Why You Won’t Miss It) - Daisy Hollman - ACCU 2025
https://www.youtube.com/watch?v=mpGx-_uLPDM&t=870s

Best Practices for coding with LLMs

  • Use smaller files
  • Over-test everything.
  • LLMs are pretty good at generating tests for existing code
    • But they also pretty decent at helping you with Test-Driven Development
  • Well-contained unit tests are much easier for LLMs to reason about
  • Encapsulation is critical!

LLMs currently struggle with "long-term learning"
Whereas a human working on the same project for weeks or months can abstract away the details of a complicated workflow and "learn" which poorly encapsulated sharp edges are ignorable, LLMs currently struggle with this kind of thing. (early 2025)

In other words, code coupling is bad—don't connect dissimilar things from different units of encapsulation in unintuitive ways.

  • Naming is more important than ever
  • Intuitive abstraction design goes a long ways
  • Agents often don't know to "check" for unintuitive behavior
    ...or they might "check" sometimes and not other times
  • Writing abstractions that are easy to correctly "guess" how they work is important
  • Write better (but still concise!) comments and documentation
    QUOTE
    The compiler does not read comments and neither do I — Bjarne Stroustrup
    Maybe it's time to revise this? LLMs do read comments


High cohesion is good
  • This is the opposite of code coupling—similar things within a given unit of encapsulation should be grouped together.
  • "Don't Repeat Yourself" (DRY) coding helps make efficient use of the LLM's context window
  • Don't do unexpected things
  • Especially if those things often don't have syntax (e.g., copy constructors in C++, auto-dereferencing in Rust, non-idiomatic __getattribute__ in Python, etc.)
  • In C++, use regular types whenever possible. (read my note about regular type: https://vsdmars.blogspot.com/2018/06/c-regular-type.html , basically, design by contract, precondition)
  • Don't mix owning and non-owning semantics in the same type or template
  • Don't mix value and reference semantics in the same type or template

KEY TAKEAWAY
Writing code that LLMs will understand is not that different from writing code that humans will understand, except that we can start to understand and quantify why these best practices increase understandability.


Design by contract
  • Both contracts and effects systems are ways of encapsulating information and reducing code coupling.
  • Encapsulation is key to effectively working with LLMs because of the context window size constraints.
  • But also, it's a lot easier to train LLMs on small, well-contained problems.
  • Contracts promote Liskov Substitutability, allowing LLMs to infer behavior of a broader category of types.

An "Effects System" is a way for a programming language to track what a function does (its side effects), not just what it returns (its data type).

While C++ doesn't have a full academic effects system (like the research language Koka), it has a "pragmatic" one built into keywords you use every day.

Here is how const and noexcept act as an Effects System to help both the Compiler and LLMs.

The Concept: Labeling the "Black Box"

Without an effects system, a function signature void process(T& data) is a black box. It could do anything: write to disk, throw an error, modify global state, or format your hard drive.

An effects system puts warning labels on the box.

Why LLMs Love This (The "Context" Win)
The slide mentioned "Context Window Constraints." This is where effects systems shine for AI.

If you give an LLM this code:

C++
// Case A: No "Effects"
void transform(Data& d);

The LLM has to "hallucinate" or guess: Does this function throw? Do I need a try-catch block? Does it invalidate my iterators? It has to consider all possibilities, which wastes "reasoning tokens."

If you give it this:

C++
// Case B: Constrained Effects
void transform(Data& d) noexcept;

The search space collapses. The LLM immediately knows: No exception handling logic is needed here. It can focus its limited attention on the actual logic rather than defensive coding.


Nov 13, 2025

[C++][concepts] compound requirements trick

won't work after clang 16.0.0 which its more stricter, which using greedy deduction for `Any<Idxs> auto... _`
However, due to this kind of usage, C++ 26 has pack_indexing

#include <utility> // index sequence
#include <iostream> // for demo only

template<typename, size_t> concept Any = true;

auto invoke_with_last_arg(auto f, auto... args) {

    return [&]<size_t... Idxs>(std::index_sequence<Idxs...>) {
        // compound requirements, Any<Idxs> is assigned as: 
        // Any<decltype(_), size_t>
        return [&](Any<Idxs> auto... _, auto last) {
            return f(last);
        }(args...);
    }(std::make_index_sequence<sizeof...(args)-1>{});

}

void demo(auto... args) {
    invoke_with_last_arg(
        [](auto last_arg) { std::cout << last_arg << std::endl; },
        args...
    );
}

int main() { demo(3.14, 42, "hello world"); }

[system design] Lesson learned from Optimising Data Building In Game Development

Optimising Data Building In Game Development - Dominik Grabiec - ACCU 2025
https://www.youtube.com/watch?v=KNAyUjeNewc

As for GPU resource clean up:

i.e. CUDA: cudaDeviceReset()



Nov 9, 2025

[C++] Use string_view _sv over raw char string

Reference:
https://youtu.be/jXQ6WtYmfZw?si=B_C-UXBVCFpAODVh&t=4428


std:: string s("the foo and the bar");
std:: println("{}", std::ranges::contains_subrange(s, "foo" ));
This won't work due to C-style string literal "foo" is actually a range of four characters: 
['f', 'o', 'o', '\0'] 

Easy fix:
#include <iostream>
#include <string>
#include <string_view>
#include <ranges>
#include <print> // C++23 for std::println

int main() {
    using namespace std::literals; // Enables the "sv" suffix

    std::string s("the foo and the bar");
    
    // "foo"sv creates a std::string_view of length 3.
    // This will now print "true".
    std::println("{}", std::ranges::contains_subrange(s, "foo"sv)); 
}

or C++23:
std::string s("the foo and the bar");

// This is the simplest way and does what you expect.
// It will print "true".
std::println("{}", s.contains("foo"));

Nov 6, 2025

[software design][functional programming] Referential transparency

Referential transparency

An expression is referentially transparent if it can be replaced with its corresponding value without changing the program's behavior.

This means that for a function to be referentially transparent, it must be a pure function, which has two key properties:

  • It always returns the same output for the same inputs.
  • It has no side effects. (It doesn't modify global variables, print to the console, read from a file, make a network request, etc.)


Oct 17, 2025

[C++][template] Double checked Stop technique

godbolt:
https://godbolt.org/z/Yenv16xzj

#include <functional>
#include <iostream>
#include <optional>


template <size_t I, typename F>
constexpr std::optional<int> ApplyIndexForOverflow(F f) {
    return ApplyIndexForOverflow<I - 1>(f);
}

template <size_t I, typename F>
constexpr std::optional<int> ApplyIndexFor(F f) {
    if (I == 0) {
        return std::nullopt;
    }
    // double checked stop; otherwise introduced stack overflow
    // from the compiler runtime due to has to instantiate
    // unbounded template instance, like above `ApplyIndexForOverflow`
    return ApplyIndexFor<(I == 0 ? 0 : I - 1 )>(f);
}

template <size_t I, typename F>
constexpr std::optional<int> ApplyIndexForConstexpr(F f) {
    if constexpr(sizeof(F) == 1){
        return I;
    }
    if constexpr(I - 1 == 0){
        return std::nullopt;
    } else {
        return ApplyIndexForConstexpr<I-1>(f);
    }
}

int main() {
 auto run = []{};
 ApplyIndexForOverflow<100>(run);
 ApplyIndexFor<100>(run);
 ApplyIndexForConstexpr<100>(run);
}

Oct 4, 2025

[alrotighm] trampoline pattern

using trampoline to deal with recursive stack overflow situation(while tail-call is not applicable):
#include <iostream>
#include <vector>
#include <numeric>
#include <variant>
#include <functional>
#include <utility>

// --- (Paste the Bounce, Step, and trampoline definitions from above here) ---

template<typename T>
struct Bounce;

template<typename T>
using Step = std::variant<T, Bounce<T>>;

template<typename T>
struct Bounce {
    std::function<Step<T>()> thunk;
};

template<typename T>
T trampoline(Step<T> first_step) {
    Step<T> current_step = std::move(first_step);
    while (std::holds_alternative<Bounce<T>>(current_step)) {
        current_step = std::get<Bounce<T>>(current_step).thunk();
    }
    return std::get<T>(current_step);
}

// --- (Paste the sum_trampolined function from above here) ---

Step<long> sum_trampolined(const std::vector<long>& data, size_t index, long current_sum) {
    if (index == data.size()) {
        return current_sum;
    }
    return Bounce<long>{
        [=]() {
            return sum_trampolined(data, index + 1, current_sum + data[index]);
        }
    };
}


int main() {
    // This will now work without crashing!
    std::vector<long> large_vec(200000, 1);

    // To start the process, we create the very first step.
    Step<long> first_step = sum_trampolined(large_vec, 0, 0);

    // The trampoline function runs the computation to completion.
    long total = trampoline(first_step);

    std::cout << "Trampolined sum of large vector: " << total << std::endl;
    std::cout << "The program finished successfully." << std::endl;

    return 0;
}

Oct 2, 2025

[Algorithm] branchless binary search

template <class ForwardIt, class T, class Compare>
ForwardIt branchless_lower_bound(ForwardIt first, ForwardIt last, const T& value, Compare comp)
{
    auto length = last - first;

    while (length > 0)
    {
        auto half = length / 2;
        // multiplication (by 1) is needed for GCC to generate CMOV
        // comp returns 1 if value > first[half], returns 0 otherwise
        first += comp(first[half], value) * (length - half); 
        length = half;
    }

    return first;
}

Dec 1, 2024

[C++][cpponsea 2024] C++ Cache Friendly Data + Functional + Ranges summary

Reference:
https://www.youtube.com/watch?v=XJzs4kC9d-Y
https://github.com/rollbear/columnist

https://godbolt.org/z/a8P7oTjoh

#include <functional>
#include <iostream>
#include <tuple>
#include <vector>

template<typename... Ts>
class Table {
 public:
  using row = std::tuple<Ts&...>;
  row operator[](size_t i) {
    auto access = [&]<size_t... Is>(std::index_sequence<Is...>) {
      return row{std::get<Is>(data_)[i]...};
    };
    return std::invoke(access, indexes);
  }

  Table() {
    init(indexes);
  }

 private:
  static constexpr std::index_sequence_for<Ts...> indexes{};
  std::tuple<std::vector<Ts>...> data_;

 private:
  template<size_t... I>
  constexpr void init(std::index_sequence<I...>) {
    ((std::get<I>(data_).push_back({42}),...));
  }
};

struct Data1 {
 int value;
};

struct Data2 {
 int value;
};

int main() {

  Table<Data1, Data2> table;
  auto row = table[0];
  std::cout << std::get<0>(row).value << '\n'; // print 42
};


Iterator

Use sentinal pattern.
struct sentinel {}; // or using sentinal = void;

struct iterator {
  using value_type = row;
  using difference_type = ssize_t;

  value_type operator*() const {
    return std::invoke([&]<size_t... Is>(std::index_sequence<Is...>) {
      return value_type{std::get<Is>(t->data_)[offset]...};
    }, t->indexes);
  }

  iterator& operator++() { ++offset; return *this;}
  iterator operator++(int) { auto copy = *this; ++*this; return copy;}
  bool operator==(const iterator&) const = default;
  bool operator==(sentinel) const { return offset == t->size(); }
  table* t;
  size_t offset;
};

Plug in
template<typename... Ts>
class Table {
 public:
  friend class iterator;
  iterator begin() { return {this, 0}; }
  sentinel end() { return {}; }
...
};

Reference:
https://en.cppreference.com/w/cpp/utility/integer_sequence
template<typename...>
struct Table;

template<typename, typename>
struct Row;


template <typename... Ts, size_t... Cs>
struct Row<Table<Ts...>, std::index_sequence<Cs...>> {
  using row_id = typename Table<Ts...>::row_id;

  // Indirection to make std::index_sequence<0, 2, 4> -> I==1 means std::get<2>(...)
  template<size_t I>
  friend auto& get(const Row& r) {
    static constexpr std::array columns{Cs...};
    return std::get<columns[I]>(r.t->data_)[r.offset];
  }

  ...
  Table<Ts...>* t;
  size_t offset;
};


template<typename Table, size_t... Cs>
struct std::tuple_size<Row<Table, std::index_sequence<Cs...>>>
 : std::integral_constant<size_t, sizeof...(Cs)> {};


template <size_t I, typename... Ts, size_t... Cs>
struct std::tuple_element<I, Row<Table<Ts...>, std::index_sequence<Cs...>>> {
  static constexpr std::array indexes = { Cs... };
  using type = Ts...[indexes[I]]&;
};

Select:
template<size_t... Is, typename Table, size_t... Cs>
auto select(const Row<Table, std::index_sequence<Cs...>>& r) {
  static constexpr size_t columns[] { Cs... };
  return Row<Table, std::index_sequence<columns[Is]...>>(r);
}

Usage:
drop_if(values, [](auto r){ auto [x,z] = select<0, 2>(r); return x < z; });
template<typename R, size_t... Cs>
struct range_selector {
  using r_iterator = decltype(std::declval<R&>().begin());
  struct iterator : r_iterator {
    using difference_type = ssize_t;
    using value_type = decltype(select<Cs...>(*std::declval<r_iterator>()));
    
    iterator(const r_iterator& i) : r_iterator(i) {}
    auto operator*() const {
      const r_iterator& i = *this;
      return select<Cs...>(*i);
    }
  };

  iterator begin() { return iterator{ r.begin() }; }
  auto end() { return r.end(); }

  R& r;
};
template<size_t... Cs>
struct range_selector_maker {
  template<typename R>
  friend range_selector<R, Cs...> operator|(R& r, range_selector_maker) {
    return { r };
  }
};

template<size_t... Cs>
range_selector_maker<Cs...> select() { return {}; }

Usage:
for (auto [x, d] : values | select<0, 3>()) {
  std::println("d={} x={}", d, x);
}

Concepts:
template<typename>
inline constexpr bool row_type_v = false;

template<typename T, typename Cs>
inline constexpr bool row_type_v<Row<T, Cs>> = true;

template<typename T>
concept row_type = row_type_v<T>;

Select:
template<size_t... Cs, typename F>
auto select(F&& f) 
  requires (! row_type<std::remove_cvref_t<F>>)
{
  return [f = std::forward<F>(f)]<typename T, typename Is>(row<T, Is> r) {
    return f(select<Cs...>(r));
  };

}
template<typename F>
auto apply(F&& f) {
  return [f = std::forward<F>(f)]<row_type R>(R r) {
    return std::invoke([&]<size_t... Cs>(std::index_sequence<Cs...>) {
      return f(get<Cs>(r)...);
    }, std::make_index_sequence<std::tuple_size_v<R>>{});
  };
}


Usage:
drop_if(values, select<0, 2>(apply([](auto x, auto z) { return x < z; })));

or just:
drop_if(values, select<0, 2>(apply(std::less{})));

Aug 11, 2024

[C++] use surrogate pattern instead of function overloading

https://en.cppreference.com/w/cpp/utility/variant/visit

#include <iomanip>
#include <iostream>
#include <string>
#include <type_traits>
#include <variant>
#include <vector>
 
// the variant to visit
using var_t = std::variant<int, long, double, std::string>;
 
// helper type for the visitor #4
template<class... Ts>
struct overloaded : Ts... { using Ts::operator()...; };
// explicit deduction guide (not needed as of C++20)
template<class... Ts>
overloaded(Ts...) -> overloaded<Ts...>;
 
int main()
{
    std::vector<var_t> vec = {10, 15l, 1.5, "hello"};
 
    for (auto& v: vec)
    {
        // 1. void visitor, only called for side-effects (here, for I/O)
        std::visit([](auto&& arg){ std::cout << arg; }, v);
 
        // 2. value-returning visitor, demonstrates the idiom of returning another variant
        var_t w = std::visit([](auto&& arg) -> var_t { return arg + arg; }, v);
 
        // 3. type-matching visitor: a lambda that handles each type differently
        std::cout << ". After doubling, variant holds ";
        std::visit([](auto&& arg)
        {
            using T = std::decay_t<decltype(arg)>;
            if constexpr (std::is_same_v<T, int>)
                std::cout << "int with value " << arg << '\n';
            else if constexpr (std::is_same_v<T, long>)
                std::cout << "long with value " << arg << '\n';
            else if constexpr (std::is_same_v<T, double>)
                std::cout << "double with value " << arg << '\n';
            else if constexpr (std::is_same_v<T, std::string>)
                std::cout << "std::string with value " << std::quoted(arg) << '\n';
            else 
                static_assert(false, "non-exhaustive visitor!");
        }, w);
    }
 
    for (auto& v: vec)
    {
        // 4. another type-matching visitor: a class with 3 overloaded operator()'s
        // Note: The `(auto arg)` template operator() will bind to `int` and `long`
        //       in this case, but in its absence the `(double arg)` operator()
        //       *will also* bind to `int` and `long` because both are implicitly
        //       convertible to double. When using this form, care has to be taken
        //       that implicit conversions are handled correctly.
        std::visit(overloaded{
            [](auto arg) { std::cout << arg << ' '; },
            [](double arg) { std::cout << std::fixed << arg << ' '; },
            [](const std::string& arg) { std::cout << std::quoted(arg) << ' '; }
        }, v);
    }
}

the overload type can replace function overload with surrogate calls. 
Ref:

Mar 24, 2023

[Ray][Notes] Papers and Design Doc

Reference:
Distributed ref counting protocol
Ownership: A Distributed Futures System for Fine-Grained Tasks


Ownership: A distributed Futures System for Fine-Grained Tasks

Focus on providing solutions to solve remote fine-grained tasks execution with:

  1. Remote/Distributed Futures based on concept of Rust's OwnerShip idea with C++'s Ref counting.
  2. Schedule Fine-Grained tasks which provides fault tolerance without sacrificing performance.
  3. OwnerShip with leader without consensus(better performance, low latency).
  4. Horizontal scaling based on leader concept(with meta data), localized storage(apart from leader, consider remote storage to the leader)


First, focus on remote futures.

  1. An object and its metadata are shared by its reference holders,
  2. The RPC executor that creates the object,
  3. Physical locations(that deference the data and processing it).
We use rpc(gPRC) as carrier for the network communication.
Basically, gRPC work with copy by value; however, in Ray, the 'value'
can be re-defined as metadata, ref counting, IP location information, etc.
Not the true 'value'.

Idea is straight, the caller who issues the remote execute owns the future's
metadata, i.e., the caller has the 'ownership' of the remote executed task's
returned 'future'.

Inside the 'returned' future 'value' should contain remote IP address/port, object ID, ref cnt, etc. metadata.




Second, focus on recovery.

  1. The design guarantees if the owner of a future is alive, any task that holds a reference to the future can eventually dereference the value. What if owner fails?
  2. Concept of 'lineage reconstruction'. Task who held the reference of the 'future' shares same lineage of Father ownership.
  3. Thus, if task fails, it can be recreated by it's remote owner, and the task will be fire-up on it's node again.
  4. Thus, it's safe to 'fate-share' the remote future with the remote task which both have the same owner.




API:

  • All objects in Ray system are immutable.
  • Concept of Rust's 'Borrower'. i.e Borrow's the future (not copy it, which increase ref count).
  • Borrower temporarily own's the future; in Ray, borrower has the signature called "sharedDFut".
  • DFut; aka. Distributed Future.



Failure detection:

  1. Automatic memory management through ref counting.
  2. System detects when a DFut  cannot be dereferenced due to worker/node failure.
  3. System has to record the locations of all tasks(that creates the DFut; while the value might not even exist yet), pending objects.

Failure recovery:

  1. Recover from a failed DFut. (At least throws when dereference DFut failed, it's not 'get' the value, but 'deref' the DFut)
  2. If passing DFut as by reference, during failure, the recovery should based on the runtime building each object's lineage, or the subgraph that produced the object. Using subgraph as event source thus the runtime could 'replay' it by recreating the objects that are needed. Subgraph is more light-weighted than logging.
  3. Multiple technique used for recovery: 1. read-only state, 2. checkpointable, 3. transient state.

Metadata:

  1. location, if using TCP/IP, than IP/Port/Host domain name(DNS cache)
  2. Object is still reference(ref cnt)
  3. location of pending object (i.e. task location)
  4. object lineage
  5. Stored on local node SSD(cachelib, mmap).


Use with Actor Model 


Schedule with ownership.


Memory management:

  1. Small object copy by value(Same as in system language, C++, Rust etc.)
  2. Large object known as primary, pinned on created host until owner release it.
    (Store on cachelib for example)


Dec 7, 2022

[C++] ADL triggers template type being instantiated.

Reference:
Eric Niebler raised a question:

Answer is elaborated in book "C++ Templates The Complete Guide Second Edition"
13.2.1 Argument-Dependent Lookup
14.3.1 Two-Phase Lookup

i.e.
for first fn call is an ADL call, thus (quoted from @Lewis Baker)
"When passing an argument to an ADL call the compiler needs to build a list of associated entities. This includes looking at associated entities of all template args, which includes inspecting the base classes of those template args, which requires instantiating those types."
 
template <bool B>
struct S {
  static_assert(B);
};

template <class>
struct T {};

template <class U>
void fn(T<U>&&) {}

int main() {
  fn(T<S<false>>{});   // static assert ERROR, why?
  ::fn(T<S<false>>{}); // OK
}

[C++] pointer-compression; from v8 oilpan-library point of view.

Reference:

Pointer compression has been used in many opensource projects (e.g. cachelib, chrome);
the idea is to use less bits in 64-bit arch (usually 1 word/8 bytes for pointer, 2-words for pointer to member function) to present virtual memory address.

Thus the pointer size compression implementation design can be done as follows:
  1. cage' (or slab) a range of heap memory block
  2. The size of a heap cage is limited by the available bits for the offset. e.g., a 4GB heap cage requires 32-bit offsets.
    The compressed pointer contains only the offset index from the base address of the 'cage' heap virtual memory.
  3. the 'cage' continuously heap virtual memory base address is per thread, thus, thread_local base pointer can be used here. However, thread local storage (TLS) is slow; thus Oilpan uses single caged heap memory per process.




Oilpan design requirements:
'Member' type instance(i.e. ref counted smart pointer) can take:
  1. A valid heap pointer to an object;
  2. The C++ nullptr (or similar);
  3. A sentinel value which must be known at compile time. The sentinel value can e.g. be used to signal deleted values in hash tables that also support nullptr as entries.
nullptr has its own type domain; what 's value of compress(nullptr) ?
Is it nullptr means deleted object or just pointing to null?

Extra requirements:
  1. Compress/decompress should be inlined at call site. (i.e. __attribute__((always_inline)) )
  2. Fast and compact instruction sequence to minimize i-cache misses.
  3. Branchless instruction sequence to avoid using up branch predictors.
  4. Consider read/write separately. Read > Write counts; thus:
    Fast decompression is preferred.
The main idea for the scheme that is implemented as of today is to separate regular heap pointers from nullptr and sentinel by relying on alignment of the heap cage.

Thus, for cage heap memory, allocated it with alignment such that the least significant bit
of the upper half-word is always set.

cage heap memory allocated with alignment as base address:
0x00 00 00 01  |  00 00 00 00

nullptr:
0x00 00 00 00  |  00 00 00 00

sentinel:
0x00 00 00 00  |  00 00 00 02

Compression generates a compressed value by merely right-shifting by one and truncating away the upper half of the value. In this way, the alignment bit (which now becomes the most significant bit of the compressed value) signals a valid heap pointer.

e.g.
original heap memory:
00000000 00000000 00000000 00000001 00000000 11111111 00000000 00000000
compressed:
00000000 00000000 00000000 00000000 10000000 01111111 10000000 00000000
and truncating away the upper half:
10000000 01111111 10000000 00000000 (half word, the msb 1 indicates a valid heap memory address)

With this implementation, compressed nullptr become:
00000000 00000000 00000000 00000000

With this implementation, compressed sentinel become:
00000000 00000000 00000000 00000001



Note that this allows for figuring out whether a compressed value represents a heap pointer, nullptr, or the sentinel value, which is important to avoid useless decompressions in user code.


Decompression relies on a specifically crafted base pointer, in which the least significant 32 bits are set to 1.
Base:
0x00 00 00 01  |  FF FF FF FF

The decompression operation first sign extends the compressed value and then left-shifts to undo the compression operation for the sign bit.
And  the decompressed pointer is just the result of a bitwise and between this intermediate value and the base pointer. 

Heap pointer:
10000000 01111111 10000000 00000000 to
00000000 00000000 00000000 00000000 10000000 01111111 10000000 00000000 to
00000000 00000000 00000000 00000001 00000000 11111111 00000000 00000000 (first stage decompressed)
00000000 00000000 00000000 00000001 11111111 11111111 11111111 11111111 &
----------------------------------------------------------------------------------------------------------------
00000000 00000000 00000000 00000001 00000000 11111111 00000000 00000000 (decompressed)

nullptr:
00000000 00000000 00000000 00000000 000000000 00000000 00000000 00000000
00000000 00000000 00000000 00000001 111111111 11111111 11111111 11111111 &
----------------------------------------------------------------------------------------------------------------
00000000 00000000 00000000 00000000 000000000 00000000 00000000 00000000 (decompressed)

sentinel:
00000000 00000000 00000000 00000000 000000000 00000000 00000000 00000010
00000000 00000000 00000000 00000001 111111111 11111111 11111111 11111111 &
----------------------------------------------------------------------------------------------------------------
00000000 00000000 00000000 00000000 000000000 00000000 00000000 00000010 (decompressed)


Several gotcha in the article mentioned worth noted here:
  1. Optimizing cage base load, the cage base pointer an't constexpr at runtime thus impedes compilter to reason for generating faster code. The Oilpan team tackle this with clang's attributes; i.e. using 
    __attribute__((require_constant_initialization));
    (https://chromium-review.googlesource.com/c/v8/v8/+/2739979/17/include/cppgc/member.h#38
    https://chromium.googlesource.com/chromium/src/+/f47da96363899cbe1b3b851119bb3409eac253e1/base/allocator/partition_allocator/pcscan.h#17
    https://clang.llvm.org/docs/AttributeReference.html#require-constant-initialization-constinit-c-20)
  2. Avoiding decompression at all;
    1. decompress nullptr to check if it's null
    2. constructing or assigning a Member from another Member needs no decompression/compression
    3. Comparison of pointers is preserved by compression, so we can avoid transformations for them as well.
    4. Hashing can be sped up with compressed pointers. Decompression for hash calculation is redundant, because the fixed base does not increase the hash entropy. Instead, a simpler hashing function for 32-bit integers can be used.
      Blink has many hash tables that use Member as a key; the 32-bit hashing resulted in faster collections!
  3. Helping clang where it fails to optimize; remove unnecessary decompression in memory barriar blocks.
  4. While now the pointer has been compressed, be ware of padding since pointer is now size of int_32; using compressed pointer inside the structure should be padding considered.


TBD:
oilpan-library code dig. 

Jun 13, 2022

[C++][C++20] compile time heap allocate

Reference:

Compile-time functions can allocate memory provided the memory is also released at compile time.

For this reason, you can now use strings or vectors at compile time. 
However, you cannot use the compile-time created strings or vectors at runtime because memory allocated at compile time has to be released at compile time.
#include <vector>
#include <ranges>
#include <algorithm>
#include <numeric>

template<std::ranges::input_range T>
constexpr auto modifiedAvg(const T& rg) {
    using elemType = std::ranges::range_value_t<T>;
    // initialize compile-time vector with passed elements:
    std::vector<elemType> v{std::ranges::begin(rg),
    std::ranges::end(rg)};
    // perform several modifications:
    v.push_back(elemType{});
    std::ranges::sort(v);
    auto newEnd = std::unique(v.begin(), v.end());

    // return average of modified vector:
    auto sum = std::accumulate(v.begin(), newEnd, elemType{});
    return sum / static_cast<double>(v.size());
}

// 注意,要用constexpr不然modifiedAvg為runtime.
constexpr auto avg = modifiedAvg(orig);


// use concept
// initialize compile-time vector with passed elements
template<std::ranges::input_range T>
consteval auto modifiedAvg(T rg) {
    using elemType = std::ranges::range_value_t<T>;
    std::vector<elemType> v{std::ranges::begin(rg), std::ranges::end(rg)};
}

However, note that we still cannot declare and initialize a vector at compile time that is usable at runtime:
int main() {
    constexpr std::vector orig{0, 8, 15, 132, 4, 77}; // ERROR
}

For the same reason, a compile-time function can only return a vector to the caller when the return value is used at compile time:
#include <vector>

constexpr auto returnVector() {
    std::vector<int> v{0, 8, 15};
    v.push_back(42);
    return v;
}

constexpr auto returnVectorSize() {
    constexpr auto coll = returnVector();
    return coll.size();
}

int main() {
    // constexpr auto coll = returnVector(); // ERROR
    constexpr auto tmp = returnVectorSize();
}
#include <vector>
#include <ranges>
#include <algorithm>
#include <array>

template<std::ranges::input_range T>
consteval auto mergeValuesSz(T rg, auto... vals) {
// create compile-time vector:
std::vector<std::ranges::range_value_t<T>> v{
    std::ranges::begin(rg), std::ranges::end(rg)};

    (... , v.push_back(vals)); // and merge passed values
    std::ranges::sort(v);

    constexpr auto maxSz = rg.size() + sizeof...(vals);
    std::array<std::ranges::range_value_t<T>, maxSz> arr{};
    auto res = std::ranges::unique_copy(v, arr.begin());

    return std::pair{arr, res.out - arr.begin()};
}

Using Strings at Compile Time:
Rule of thumb: cannot use a compile-time string at runtime.
String SSO implement also take into account. (https://godbolt.org/z/eTYfcfMc5)



constexpr Language Extensions

Since C++20, the following language features are possible to be used in compile time functions (whether declared with constexpr or consteval):
  • You can now use heap memory at compile time.
  • Runtime polymorphism is supported:
    • You can now use virtual functions.
    • You can now use dynamic_cast.
    • You can now use typeid.
  • You can have try-catch blocks now (but you are still not allowed to throw).
  • You can now change the active member of a union.
  • Note that you are still not allowed to use static in constexpr or consteval functions.


lamdba

template<typename... Args>
void foo(Args... args) {
    // OK since C++20
    auto l4 = [...args = std::move(args)] {
        bar(args...); // OK
    };
}

template<typename... Args>
void foo(Args... args) {
    auto l4 = [&...fooArgs = args] {
        bar(fooArgs...); // OK
    };
}



new type:
char8_t
std::u8string
std::u8string_view

char8_t c = u8'@';      // character with UTF-8 encoding for character @
const char8_t* s = u8"K\u00F6ln";       // character sequence with UTF-8 encoding for Köln



#include <iostream>
#include <cmath>
#include <thread>
#include <syncstream>

void squareRoots(int num) {
    for (int i = 0; i < num ; ++i) {
        std::osyncstream coutSync{std::cout};
        coutSync << "squareroot of " << i << " is "
            << std::sqrt(i) << '\n';
    }
}

int main() {
    std::jthread t1(squareRoots, 5);
    std::jthread t2(squareRoots, 5);
    std::jthread t3(squareRoots, 5);
}


For writing to file:
#include <fstream>
#include <cmath>
#include <thread>
#include <syncstream>

void squareRoots(std::ostream& strm, int num) {

    std::osyncstream syncStrm{strm};

    for (int i = 0; i < num ; ++i) {
        syncStrm << "squareroot of " << i << " is "
            << std::sqrt(i) << '\n' << std::flush_emit;
    }
}


int main() {
    std::ofstream fs{"tmp.out"};
    std::jthread t1(squareRoots, std::ref(fs), 5);
    std::jthread t2(squareRoots, std::ref(fs), 5);
    std::jthread t3(squareRoots, std::ref(fs), 5);
}
or:
#include <fstream>
#include <cmath>
#include <thread>
#include <syncstream>

void squareRoots(std::ostream& strm, int num) {
    for (int i = 0; i < num ; ++i) {
        strm << "squareroot of " << i << " is "
        << std::sqrt(i) << '\n' << std::flush_emit;
    }
}

int main() {
    std::ofstream fs{"tmp.out"};
    std::osyncstream syncStrm1{fs};
    std::jthread t1(squareRoots, std::ref(syncStrm1), 5);

    std::osyncstream syncStrm2{fs};
    std::jthread t2(squareRoots, std::ref(syncStrm2), 5);

    std::osyncstream syncStrm3{fs};
    std::jthread t3(squareRoots, std::ref(syncStrm3), 5);
}

Apr 28, 2022

[C++][Algorithm][design] predicate callable logic for sorting (and any of the ordering function/algorithm call)

Reference:
https://danlark.org/2022/04/20/changing-stdsort-at-googles-scale-and-beyond/
https://vsdmars.blogspot.com/2018/06/c-regular-type.html

Concept:

Type:


Design by contract (link to defensive programming)

P: precondition
Q: operation
R: postcondition


Domain (as in math)

Domain of operation is used in the ordinary math sense to denote the set of values over which an operation is (required to be) defined.

This set can change over time. Each component may place additional requirements on the domain of an operation.

These requirements can be inferred from the uses that a component makes of the operation and are generally constrained to those values accessible through the operation's arguments.

Domain of the operation is NOT the types of the arguments.

 

Safety & Correctness

  • An operation is safe if it cannot lead to UB
    • directly or indirectly
    • even if the operation preconditions are violated
  • An unsafe operation may lead to UB if preconditions ever are violated
    • Either directly or during subsequent operations, safe or not
Code that violates preconditions is incorrect.


Requirements for correctness

  • A correctly implemented operation guarantees that:
    • If preconditions are satisfied
      • The operation will either succeed, result matches post conditions
      • Or report failure, return an error, thrown an exceptions, set errno etc.
      • Any objects being mutated by the operations must be left in a "known or determinable state"
        • A weaker requirement than valid
    • If preconditions is not satisfied
      • If the operation is safe
        • The result is unspecified which could include:
          • Failure
          • Trapping
          • Leaving any object being mutated by the operations in an unspecified, possibly invalid state.
      • If the operations is unsafe
        • The behavior is undefined(Full STOP)
Compiler can do /anything/ if there's an UB(stripping expressions etc.)

We could exploit contract to work for us; e.g. unsigned (contracted with mod(2^b))


Strong preconditions

  • Pros
    • flexibility of implementation
    • ascribe meaning and intent to an operation
    • simplify requirements and reasoning about code
  • Cons
    • limit clever uses that exploit otherwise defined behavior
    • allow for variance in behavior between implementations

ALWAYS refer to C++ ISO for contract of std::


A tl;dr take away for predicator of sorting

When calling any of the ordering functions including
  • std::sort
  • std::find
compare functions(aka predicate) much comply with the strict weak ordering which formally means the following:
  • Irreflexivity: x < x is false (strict partial order rule)
  • Asymmetry: x < y and y < x cannot be both true (strict partial order rule)
  • Transitivity: x < y and y < z imply x < z (strict partial order rule)
  • Transitivity of incomparability: x == y and y == z imply x == z, where x == y means x < y and y < x are both false (equivalence relations on incomparable elements rule)
Above conditions are used for optimization purposes and an abide by is a must for code correctness.



Feb 14, 2022

[C++][book review] Beautiful C++

Reference:
[Book] https://www.amazon.com/Beautiful-Core-Guidelines-Writing-Clean/dp/0137647840
[Cpp core guideline] https://isocpp.github.io/CppCoreGuidelines/CppCoreGuidelines#main



F.51: Where there is a choice, prefer default arguments over overloading

C.45: Don’t define a default constructor that only initializes data members; use in-class member initializers instead

C.131: Avoid trivial getters and setters

ES.10: Declare one name (only) per declaration

NR.2: Don’t insist to have only a single return-statement in a function

P.11: Encapsulate messy constructs, rather than spreading through the code

I.23: Keep the number of function arguments low

Do as little as possible, but no less
x64 ABI, there is a four-register fast-call calling convention by default.
A four-parameter function will execute slightly faster than a function taking a class by reference.

I.26: If you want a cross-compiler ABI, use a C-style subset

C.47: Define and initialize member variables in the order of member declaration

CP.3: Minimize explicit sharing of writable data

CP.22: Never call unknown code while holding a lock (e.g., a callback)
"Don’t communicate by sharing memory; share memory by communicating"

T.120: Use template metaprogramming only when you really need to

Meta-programming techniques, while useful, have been adopted into the lan- guage more explicitly.
consider using concept in C++20.

I.11: Never transfer ownership by a raw pointer (T*) or reference (T&)

Your default choice for holding objects with dynamic storage duration should be a std::unique_ ptr.
You should only use std::shared_ptr where reasoning about lifetime and ownership is impossibly hard, and even then, you should treat it as a sign of impending technical debt caused by a failure to observe the appropriate abstraction.

Use GSL:
http://github.com/Microsoft/GSL

I.3: Avoid singletons

C.90: Rely on constructors and assignment operators, not memset and memcpy

ES.50: Don’t cast away const

ES.5: Keep scopes small

CP.43: Minimize time spent in a critical section

E.28: Avoid error handling based on global state (e.g. errno)

You do not know how your calling code is going to respond to errors.
You cannot rely on your caller handling the error.

SF.7: Don’t write using namespace at global scope in a "header file"

F.21: To return multiple “out” values, prefer returning a struct or tuple

Enum.3: Prefer class enums over “plain” enums

ES.5: Keep scopes small

only declare auto-variables that is close to its use. (Golang)

Con.5: Use constexpr for values that can be computed at compile time

T.1: Use templates to raise the level of abstraction of code

T.10: Specify concepts for all template arguments (C++20)

P.4: Ideally, a program should be statically type safe

Problem areas:

  • unions - use variant (in C++17)
  • casts - minimize their use; templates can help
  • array decay - use span (from the GSL)
  • range errors - use span
  • narrowing conversions - minimize their use and use narrow or narrow_cast (from the GSL) where they are necessary
If you are doing any arithmetic, including comparison, use a signed type. If you are using an unsigned type to get an extra bit of representation, you are using the wrong type and you should go wider or recognize that you are performing a very risky optimization.


P.10: Prefer immutable data to mutable data

I.30: Encapsulate rule violations

ES.22: Don’t declare a variable until you have a value to initialize it with

Declaring at point of use improves readability of code, and not declaring state at all improves things even further. Reasoning about state requires a comprehensive memory, which is a diminishing asset as codebases expand.

Per.7: Design to enable optimization

E.6: Use RAII to prevent leaks

Feb 12, 2022

[C++][notes] Branchless Programming in C++ - Fedor Pikus - CppCon 2021

Reference:
Branchless Programming in C++ - Fedor Pikus - CppCon 2021
Computer Architecture - A quantitative approach (Hennessy, Patterson) Appendix-C 
https://vsdmars.blogspot.com/2016/01/likely-or-unlikely-easy-misleading.html


What determines performance?

  • Optimal algorithm
    Get the result with minimal work.
  • Efficient use of language
    do not do any unnecessary work
  • Efficient use of hardware
    use all available resources
    at the same time
    all the time


Hazards

  • Structural; use stall/bubble
  • Data; forwarding, stall/bubble in the middle of pipeline
  • Branch;
    Freeze/flush; holding or deleting any instructions after the branch until the branch destination is known.
    Treat every branch as not taken.
    Treat every branch as taken.
    Delayed branch.
As for branch hazards, we usually use static branch prediction by profiling.
A branch is usually bimodally distributed.
As for dynamic branch prediction; we use branch history table.


Tools

Google benchmark is our friend https://github.com/google/benchmark
$ perf stat our_binary  // shows branch-misses

When do benchmark like this(branch mis-predicting), we should avoid the predicting is done by the compiler, which is damn smart to generate efficient code.
  • Optimizing away branches almost always results in doing more work.
  • CPU usually has idle compute resources which it can handle a bit of extra work.
  • Branch mis-prediction is very expensive.
  • Trade off between the extra work vs. the code of the branch is usually impossible to predict; must be measured.


Less branch means better

Tricks:
use hashmap[] as branches. hashmap is O(1).
However; keep in mind this cause extra memory thus use iff branch is poorly predicted and the extra hashmap computations are small.
  • Sometimes the compiler will do a branchless transformation for you. (conditional move instruction)
  • Compiler's branchless optimization is usually better than ours'.
  • This is almost always branchless in reality:
    return cond ? x : y;
  • Never optimize code preemptively.
  • Optimize only if the profiler shows high mis-prediction rate.
  • Optimizations depend on the compiler.
 if (b) s += x;
 //vs.
 s += b * x;
  • Sometimes branchless code is not really branchless
  • Indirect function calls are similar to branches
    if (cond) f1(); else f2();
  • Can be converted to branchess:
    funcptr f[2] = {&f2, &f1};
    (f[cond])();
  • Above code almost never works.
    If f1 and f2 were inlined..
  • Always measure


Lessons learned

  • Predicted branches are cheap
  • Mis-predicted branches are very expensive - pipeline flush
  • Optimization - user fewer(or zero) branches
  • Always use profiler to detect and validate optimization locations
  • Don't fight with the compiler - sometimes it does the job for you

Jul 23, 2021

[C++] consteval in C++17

Reference:
https://andreasfertig.blog/2021/07/cpp20-a-neat-trick-with-consteval/

What consteval does:
As the name of the keyword tries to imply, it forces a constant evaluation.
In the standard, a function that is marked as consteval is called an immediate function.
The keyword can be applied only to functions/function template.
Immediate here means that the function is evaluated at the front-end, yielding only a value, which the back-end uses.
Such a function never goes into your binary.
A consteval-function must be evaluated at compile-time or compilation fails.
With that, a consteval-function is a stronger version of constexpr-functions.



template <auto value>
inline constexpr auto as_constant = value;

constexpr int Calc(int x) { return 4 * x; }

int main() {
    auto res = as_constant<Calc(2)>;
    ++res;
}