Showing posts with label cpp_note. Show all posts
Showing posts with label cpp_note. Show all posts

Dec 31, 2023

[Cppcon 2023] Expressing Implementation Sameness and Similarity - Polymorphism in Modern C++, Daisy Hollman

Reference:
https://youtu.be/Fhw43xofyfo?si=PcMFEsqb7NRiCmyX

Two different kinds of sameness

Interface sameness

  • Enables users to treat things the same way in their code(create their own sameness)
  • Cannot be removed later
    • You can't change your user's code(at least not easily)
    • Once you allow users to treat things as the same, it's very hard to change that later
  • When done well: low code coupling(the degree of interdependence between software modules)

Implementation sameness

  • Enables readers to understand and use existing sameness of similarity
  • Can be changed or removed at any point in the future when it stops being helpful
  • When done well: high code cohesion(the degree to which the elements inside a module belong together)
Let this concept sinks in.

Consider about 'type of T'; e.g. template<typename T> vector{};


Reusing customization points.

Mixin mixins.

template<class> struct CRTPMixin;
template<template <class> class Mixin, class Derived>
struct CRTPMixin<Mixin<Derived>> {
  consteval auto& self() { return static_cast<Derived&>(*this); }
  consteval auto const& self() const { return static_cast<Derived const&>(*this); }
};

template<typename Derived>
struct PrintableElementwise : CRTPMixin<PrintableElementwise<Derived>> {
 void print() const {
    auto const& e = self().elements();
    std::apply([](auto const&... el) {
      ([&]{ cout << el << "\n"; }(), ...);
      }, e);
    }
};


As stated by Sy Brand's C++23’s Deducing this can help with the above

https://devblogs.microsoft.com/cppblog/cpp23-deducing-this/
static_cast<Derived const&>(*this); 
part. But really? Consider code uses deduce this from C++23:
struct PrintableElementwise {
  void print(this auto const& self) {
    auto const& e = self.elements();
    std::apply([](auto const&... el) {
      ([&]{ count << el << "\n"; }(), ...);
    }, e);
  }
};

struct Foo : PrintableElementwise {
 int a;
 double b;
 std::string s;
 auto elements() const {
    return std::forward_as_tuple(x, y, z);
 }
};
Above has mixed interface sameness with implementation sameness; which causes error:
auto items = std::vector<PrintableElementwise>{/*...*/};
for (auto* i : items) {
    i->print(); // error if derived type has no memfn elements().
}
Use the idea of 'type of T'. Which indicates the type's embedded behavior.


Qualifier forwarding

e.g.
Perfect forwarding:
template<class T>
void foo(T&& t) {
    bar(std::forward<T>(t));
}
equivalent to:
template<class T>
void foo(T& t) {
 bar(t);
}

template<class T>
using not_forwarding_ref = T;

template<class T>
void foo(not_forwarding_ref<T>&& t) {
  bar(std::move(t));
}


Don't Repeat Yourself(DRY)

'Every piece of knowledge must have a single, unambiguous, authoritative representation within a system


Separating the ownership mechanism (typical pattern for a class template customization point

From:

template<class Thing>
class OwingCollection {
 private:
   vector<unique_ptr<Thing>> things_;
 protected:
   void for_each(/* concept */ std::invocable<Thing const&> auto&& f) const { /*...*/};
 public:
   void insert(unique_ptr<Thing>) {};
   unique_ptr<Thing> remove(unique_ptr<Thing>) {};
   bool contains(unique_ptr<Thing>) const {};
   void remove_if(invocable<Thing const&> auto&&) {};
};
To:
template<class Thing, template<class...> class Owner = unique_ptr>
class OwingCollection {
 private:
   vector<Owner<Thing>> things_;
 protected:
   void for_each(/* concept */ std::invocable<Thing const&> auto&& f) const { /*...*/};
 public:
   void insert(Owner <Thing>) {};
   Owner <Thing> remove(Owner <Thing>) {};
   bool contains(Owner <Thing>) const {};
   void remove_if(invocable<Thing const&> auto&&) {};
};


STD's example of separable pattern 

[C++14] unique_ptr with type erasure as shared_ptr 


C++20 Concepts

C++20 concepts extract interface sameness without your permission.

Concepts allow library users to accidentally create code coupling between unrelated modules based only on names.
e.g.
template<class T>
  requires requires(T&& t) { { t.clear() } -> convertible_to<bool>; }
void do_the_stuff(T&& t) { /*...*/ }
Those two types fit for above API. 
However; their meaning of memfn clear() is different.
struct Container {
  // returns true if the container was
  // non-empty before the clear
  bool clear();
};

struct Color {
  // returns true if opacity == 0
  bool clear();
};
Concepts does not differentiate namespace.


More places having the concept of 'sameness'

  • 'Normal' functions (C like)
  • Macros and Code generation
    • 'Gross' but sometimes better than repeating things.
  • Customization Point Objects(CPOs)
  • Type erasure
  • constexpr functions
    • 'Sameness' of compile-time and runtime implementations.
  • Dependency injection (needs reflection)
  • Aspect-oriented programming(needs reflection)
  • Decoration(needs reflection)

Nov 13, 2022

[C++] function overload resolution in one GIF (by Jeff Preshing)

While C++'s function overload resolution is perplex, Jeff Preshing had a way to explain it in one GIF.

Although there are sophisticated details (e.g. ADL, pointer to function;pointer to member function etc.) which should be known by seasoned C++ engineers, the GIF provides a quick look-up for code that hits ambiguous resolution state.

Reference:
https://preshing.com/20210315/how-cpp-resolves-a-function-call/


credit: Jeff Preshing



Jul 18, 2022

[C++][note] union tagging sample code

#include <new>
#include <string>

constexpr int TU_STRING = 0;
constexpr int TU_INT = 1;
constexpr int TU_FLOAT = 2;

struct TU {
  union my_union {
    struct i_type {
      int type;
      int i;
    } i;
    
    struct f_type {
      int type;
      float f;
    } f;
    
    struct s_type {
      int type;
      std::string s;
    } s;

    my_union(int i) : i{TU_INT, i} {}
    my_union(float f) : f{TU_FLOAT, f} {}
    my_union(std::string s) : s{TU_STRING, std::move(s)} {}
    my_union(my_union const &other) {
      // This is safe.
      switch (other.i.type) {
      case TU_INT:
        ::new (&i) auto(other.i);
        break;
      case TU_FLOAT:
        ::new (&f) auto(other.f);
        break;
      case TU_STRING:
        ::new (&s) auto(other.s);
        break;
      }
    }
    
    ~my_union() {
      // This is safe.
      if (TU_STRING == s.type) {
        s.~s_type();
      }
    }
  } u;

  TU(int i) : u(i) {}
  TU(float f) : u(f) {}
  TU(std::string s) : u(std::move(s)) {}
  TU(TU const &) = default;
  ~TU() = default;
};

Jun 20, 2022

[C++] ODR notes

ODR:
https://eel.is/c++draft/basic.def.odr


All definition across the program should be the same.

It's hard.


e.g.

// size of Person might be different inside the program.
class Person{
    std::string first_;
    std::string last_;
# if HAS_MIDDLE_NAME(VAR)
    std::string middle_;
#endif
};

ODRV can be embedded anywhere(DSO, static library, or executable)

  1. Multiple, conflicting definitions of the same symbol in more than one TU.
  2. Compiling a given header/source file with different compiler settings or #defines
    Debug/Release, (no-)RTTI, mismatched preprocessor values, etc.
  3. Overriding operator new/delete in a DSO, but hiding it from the rest of the program.
    The passing C++ objects across that DSO boundary.
  4. Multple varying copies of a dependency(e.g. Boost, JPEG, zlib, etc.)


ODRV Behaviors

  1. Hard to debug
  2. Hard to reproduce
  3. Exceptions failing to get caught
  4. Crashing in the destructor after passing an object across a DSO boundary.

Aug 1, 2021

[cli][note] design / Command Line Interface Guidelines

Reference:
https://github.com/cli-guidelines/cli-guidelines

Page:
https://clig.dev/


Basics

  • C++: 3rd party lib; e.g. https://github.com/CLIUtils/CLI11
  • Return zero exit code on success, non-zero on failure.
    • Beware of bash exit code 128.
  • Send output to stdout.
  • Send messaging to stderr.


Help

  • Display help text when passed no options, the -h flag, or the --help flag.
  • Display a concise help text by default.
  • Show full help when -h and --help is passed.
  • Provide a support path for feedback and issues.
  • Lead with examples.
  • Display the most common flags and commands at the start of the help text.
  • Use formatting in your help text.
  • *If the user did something wrong and you can guess what they meant, suggest it.
  • If your command is expecting to have something piped to it and stdin is an interactive terminal,
    display help immediately and quit.


Output

  • Human-readable output is paramount.
  • Have machine-readable output where it does not impact usability.
  • If human-readable output breaks machine-readable output, use
    --plain
    to display output in plain, tabular text format for integration with tools like grep or awk.
  • Display output as formatted JSON if --json is passed.
  • Display output on success, but keep it brief.
  • If you change state, tell the user.
  • Make it easy to see the current state of the system.
  • Suggest commands the user should run.
  • Actions crossing the boundary of the program’s internal world should usually be explicit. 
  • By default, don’t output information that’s only understandable by the creators of the software.
  • Don’t treat stderr like a log file, at least not by default.
  • Don’t print log level labels (ERR, WARN, etc.) or extraneous contextual information, unless in verbose mode.
  • Use a pager (e.g. less) if you are outputting a lot of text.


Errors

  • Catch errors and rewrite them for humans.
  • Signal-to-noise ratio is crucial.
  • Consider where the user will look first. 
  • If there is an unexpected or unexplainable error,
    provide debug and traceback information, and instructions on how to submit a bug.
  • Make it effortless to submit bug reports.


Arguments and flags

  • Prefer flags to args.
  • Have full-length versions of all flags. For example, have both -h and --help.
  • Only use one-letter flags for commonly used flags
  • If you’ve got two or more arguments for different things, you’re probably doing something wrong.
  • Make the default the right thing for most users.
  • Confirm before doing anything dangerous.
  • Do not read secrets directly from flags.
  • If possible, make arguments, flags and subcommands order-independent


Subcommands

  • Be consistent across subcommands. 
  • Use consistent names for multiple levels of subcommand.
  • Don’t have ambiguous or similarly-named commands. For example, having two subcommands called “update” and “upgrade” is quite confusing.


Robustness

  • Validate user input.
  • Responsive is more important than fast. Print something to the user in <100ms. If you’re making a network request, print something before you do it so it doesn’t hang and look broken.
  • Show progress if something takes a long time.
  • Do stuff in parallel where you can, but be thoughtful about it.
  • Make things time out.
  • Make it recoverable.
  • Make it crash-only.
  • This is the next step up from idempotence. If you can avoid needing to do any cleanup after operations, or you can defer that cleanup to the next run, your program can exit immediately on failure or interruption. This makes it both more robust and more responsive.


Future-proofing

  • Keep changes additive where you can. Rather than modify the behavior of a flag in a backwards-incompatible way.
  • Warn before you make a non-additive change.


Signals and control characters

  • If a user hits Ctrl-C (the INT signal), exit as soon as possible.
  • If a user hits Ctrl-C during clean-up operations that might take a long time, skip them. Tell the user what will happen when they hit Ctrl-C again, in case it is a destructive action.


Configuration
Environment variables
Naming

Distribution

  • If possible, distribute as a single binary.
  • Make it easy to uninstall.

Oct 11, 2018

[C++][Cppcon 2017] Louis Brandy: Curiously Recurring C++ Bugs at Facebook

CppCon 2017: Louis Brandy “Curiously Recurring C++ Bugs at Facebook”

Some wisdom extracted from writing production code..


ASan:
https://github.com/google/sanitizers


Bug 1:
std::vector::operator[]

1. No boundary check is performed (FAST)
2. Returns a reference

code:
--
return v[102];  // out of boundary.
--

mitigation:
  • Static analysis. Complicated, Hard, Expensive.
  • Improved abstractions (range-based operations)
  • Dynamic analysis

Bug 2:
std::map::operator[] 

If you are a fan of Scott Meyers and have read his book:
Effective STL (Too bad there's no update with modern C++ since now he's retired.) Bug 1 & 2 are mentioned in this book.

1. It's slow.
2. Why it's slow? It checks if the key exist, if not, insert the key with
default value type constructor constructed value instance.

But, even though it's slow, it makes the code elegant , somehow~:
--
map<char, int> occ;

for (auto c : str) {
    occ[c]++;
}
--

const correctness:
As a senior C++ engineer knows const can act as guardian against accidentally modify the internal state.


Bug 3:
folly::get_default

Same idea as Python's  dict().get(Key, DefaultValue)

Bugs comes from returning string as r-value and caller references it.
(emm~ yup, this talk is for junior C++ engineer :-) although not bad and pinpoint the issue instead of gibberish )

mitigation:
-fsanitize-address-use-after-scope


Bug 4:
volatile

When coming to atomic operation, find something under
header <atomic>

The famous paper about volatile + atomic could be:
C++ and the Perils of Double-Checked Locking -Scott Meyers and Andrei Alexandrescu


Bug 5:
std::shared_ptr  thread safe?

Yes for internal ref counting.
(Another saying is that shared_ptr is as thead-safe as a normal pointer~ duh~ Not precise and sometimes incorrect.)

However, the type instance it points to is definitely not thread-safe.
(Well, depends on the type).

i.e shared_ptr's control block itself is thread-safe.
Wanna speed? Use unique_ptr.

Reference:
Always consider function thread safeness drags performance in single thread code

Reference:
$ git bisect  // debugging~
http://vsdmars.blogspot.com/2016/01/git-concepts-and-commands.html#more

mitigation:
  • Thread sanitizer
  • Address Sanitizer often does, too
  • Use library:
    atomic<shared_ptr>


Bug 6:
This compiles:
#include <string>
void f()
{
    std::string(foo);  // Same as std::string foo;
}

Why?
Effective STL Item 6: Be alert for C++'s most vexing parse.

The insidious bug could be:
void obj::update() noexcept {
    unique_lock<mutex>(m_mutex);  // This one is truly insidious... Not locking at all.
    do_something();
}

Fix, simple name the unique_lock<mutex> g{m_mutext};
and use {} instead () _always_!

This kind of bug happens on types which have default constructor.

mitigation:
  • -Wshadow  // Why? Because it warns us if there's a re-declaration shadows outter scope variable.
    It's noisy, not a good mitigation, though.
  • Use {} instead of ()

Jun 26, 2018

[C++] Design the Write-only variables

reference:
https://mklimenko.github.io/english/2018/06/19/write-only-variables/

There are basically three types of registers:
  • Read-write
  • Read-only
  • Write-only
Read-write:
volatile auto &read_write = *reinterpret_cast&lt;std::uint32_t*>(register_address);
Read-only:
const volatile auto &read_only = *reinterpret_cast&lt;std::uint32_t*>(register_address);
Code:
https://godbolt.org/g/1ro2FN
constexpr std::size_t register_address = 123456;
const volatile auto &read_only = *reinterpret_cast<std::uint32_t*>(register_address);


void foo() {
    auto dst = read_only;
}
/// Disassembly:
foo():
  mov eax, DWORD PTR ds:123456
  ret

Wrap it:
https://godbolt.org/g/nbDYdo
class Register {
private:
    static volatile inline std::uint32_t &ref = *reinterpret_cast<std::uint32_t*>(register_address);
public:
    static std::uint32_t Get(){
        return ref;
    }

    static void Set(std::uint32_t val){
        ref = val;
    }
};


Final code:
https://godbolt.org/g/gQR1wd
#include <cstdint>
#include <type_traits>


template <std::size_t address> 
class Register {
    private:
    static volatile inline std::uint32_t &ref = *reinterpret_cast<std::uint32_t*>(address);

    public:
    Register& operator=(std::uint32_t val){
        ref = val;
        return *this;
    }

    template <typename T>
    operator T() const{
        static_assert(std::is_same_v<T, std::uint32_t>, "You should assign this register to the std::uint32_t value"); 
        return T();
    }

    operator std::uint32_t() const {
        return ref;
    }
};

Register<1234567> reg;

void RegGet() {
    auto dst = reg;
}

void RegSet(std::uint32_t val) {
    reg = val;
}


write-only:
template <std::size_t address> 
class Register {
private:
    static volatile inline std::uint32_t &ref = *reinterpret_cast<std::uint32_t*>(address);
public:
    static void Set(std::uint32_t val){
        ref = val;
    }

    Register& operator=(std::uint32_t val){
        ref = val;
        return *this;
    }
};


read-only:
template <std::size_t address> 
class Register {
private:
    static volatile inline std::uint32_t &ref = *reinterpret_cast<std::uint32_t*>(address);
public:
    static std::uint32_t Get(){
        return ref;
    }

    template <typename T>
    operator T() const{
        static_assert(std::is_same_v<T, std::uint32_t>, "You should assign this register to the std::uint32_t value"); 
        return T();
    }

    operator std::uint32_t() const {
        return ref;
    }

};

Jun 4, 2018

[C++][cppcon 2018][note] “C++17's std - -pmr Comes With a Cost" - David Sankel



What std::pmr trying to solve?
  • Allocation is slow
  • Fragmentation hurts performance
  • pre-C++17 allocator is overly complicated

Speed
The memory_resource should have global lifetime.
When passing pointer into function(including constructor), always consider the lifetime of the pointer it points to.


Ok, here's the tricky part.
Consider code below presented by David Sankel:
int main() {
    static Loggingresource memoryResource(
        std::pmr::new_delete_resource()}; // why static? why not local?
    
    std::pmr::set_default_resource(&memoryResource);
    
    std::pmr::vector<int> ints;
    ints.push_back(42);
}

The reason for why making memoryResource global variable? It's due to in different TU(translation unit), functions could have static variables as well, and the init. sequence of this static variable depends on when the function being called. If the static variable of a function from other TU using std::pmr::vector, the destruction sequence of it is later then local variable of main function.

This reminds us the well known article from Alexander Bernauer: RAII vs. exit()

ALWAYS CONSIDER VARIABLE CONSTRUCT/DESTRUCT SEQUENCE

Refer to Linking notes and How main() is executed on Linux
  1. starts up program threading
  2. call _init()
    __attribute__((constructor))
  3. **registers** the _fini() and _rtld_fini(). called after program terminiates.
    __attribute__((destructor))
  4. call main()
class Bar2 {
    std::string data{"data"};
};


class Foo2 {
    std::unique_ptr<Bar2, 
         polymorphic_allocator_delete /* our deleter taking memory_resource ptr */> 
             d_bar;
    
    public:
        Foo2() : d_bar(nullptr /* init. with null */, {{std::pmr::get_default_resource()}}) {
            std::pmr:polymorphic_allocator<bar2> alloc{
                std::pmr::get_default_resource()};
            Bar2 *const bar = alloc.allocate(1); // 1 as one Bar2 instance. Not sizeof(Bar2)
            // Be ware here, we should have a try/catch here
            // since Bar2 constructor can throw.
            // and manually call alloc.deallocate 
            // Remember Effective C++ Item 52, placement new
            // and placement delete should go in pairs.
            alloc.construct(bar);
            d_bar.reset(bar);        
        }
};
To the question from audience asking why using polymorphic allocator instead of using placement new?

Because, because...
operator new has scope...
there's deleting destructor...
Allocator gives us a uniform way to grab memory from heap.

Destructor should NOT throw.
It's hard, but take that into consideration, seriously.

Recap:
[C++11] destructor with noexcept
[C++] Exception in detail.


std::pmr::polymorphic_allocator::destroy noexcept(false)
std::pmr::polymorphic_allocator::deallocate noexcept(false)
class polymorphic_allocator_delete{
    public:
        polymorphic_allocator_delete(
            std::pmr::polymorphic_allocator<std::byte> allocator)
            : d_allocator(std::move(allocator) /* actually, a copy, not move */) 
            {}
        template<typename T>
        void operator() (T *ptr) {
            std::pmr::polymorphic_allocator<T>(d_allocator).destroy(ptr);
            std::pmr::polymorphic_allocator<T>(d_allocator).deallocate(ptr, 1);
        }
        
    private:
        std::pmr::polymorphic_allocator<std::byte> d_allocator;
};
std::pmr::polymorphic_allocator::polymorphic_allocator has no move constructor

With this implementation, the size being allocated is larger with extra 4 words due to unique_ptr has captured a pointer to deleter.

Try using type instead of using ptr to function, which prior has only 1 byte.
Ref: [C++14] unique_ptr with type erasure as shared_ptr

Most of the STL container has a std::pmr namespace version.

Do NOT change the default global memory_resource during the run time. It's dangerous.

We can use std::byte or void for polymorphic_allocator:
std::pmr::polymorphic_allocator<std::byte>
std::pmr::polymorphic_allocator<void>
By using void is align with 'new' operator, which returns void*


Strong exception safety

IFF value type's move constructor is noexcept, otherwise container will go back using value type's copy constructor instead. When? For std::vector, while it need's more slots.

class Foo {
    std::pmr::polymorphic_allocator<std::byte> d_allocator;
    std::unique_ptr<Bar2, 
        polymorphic_allocator_delete
           /* our deleter taking memory_resource ptr */> 
               d_bar;
    
    public:
        // Let's focus on move constructor

        // passing in new allocator
        Foo(Foo&& rhs, std::pmr::polymorphic_allocator<std::byte> allocator);
        Foo(Foo&& rhs) noexcept : 
        d_allocator(other.d_allocator /* no need move because it's copy ptr anyway */), 
        d_bar(nullptr, {d_allocator /* Make sure d_allocator is declared before d_bar*/})
        {
            d_bar.reset(other.d_bar.release());
        }
};
So, can we get rid of d_allocator? Since it's just a placeholder for global memory_resource.

Yes, we can.

How? The data member has the memory_resource which shares it. We can grab it from there.

Sum up

Excerpt from the talk, allocator awareness best practices:
  • Fix allocator at construction
  • Allocator argument to constructor, copy constructor, move constructor, and move copy constructor passing allocator to data members(containers)
  • move constructor takes extra new allocator argument
  • A member type of std::pmr::polymorphic_allocator<std::byte>
  • get_allocator call from data member to get the shared memory_resource
  • Always use global storage for the default allocator(arguable..)
  • Set the default allocator only in main(reasoning due to static namespace variable in different TU init. sequence isn't guaranteed.
It's becoming complicated...
The doctrine to keep in mind is that, fix allocator in the code path. If it's not, there is a problem.

I do not think this pmr adding is mature enough for all data type instances since it's not being supported by all std:: datatypes and corner cases needs to be concerned. Yet, it could; however, being used in scope to tackle with certain problems.
i.e memory pool

Reference:
How tcmalloc Works
jemalloc

Jun 3, 2018

[C++][Cppcon 2018][note] An Allocator is a Handle to a Heap - Arthur O'Dwyer


Headers:
<memory_resource>
<memory>


Tools:
std::allocator_traits , use as  std::allocator_traits<allocator<T>>
std::is_empty , test if a type can be used with [no_unique_address] (reference: http://vsdmars.blogspot.com/2018/05/caccu2018-tricks-library-implementation.html)


Concept (must read):
C++ concepts: Allocator

excerpt from Howard Hinnant' Allocator Boilerplate

Refresh:
Effective STL, Item 10, 11

Reference:
http://vsdmars.blogspot.com/2017/10/c-allocator-template-code.html


Back to the main topic:

std::pmr i.e <memory_resource>
std::pmr::polymorphic_allocator (value type)

By skimming through the
polymorphic_allocator constructor signature, there's no move constructor, indicates that, it shares resources.
Unlike stateless allocator, polymorphic_allocator doesn't have 'state', but value, which is the value of pointer point to the shared resource. It has state, but immutable state, which is that the pointer to resource is const.
'allocate'/'deallocate' can be marked as 'const', which the data member pointer point's to the shared resource shouldn't be changed.

That is to say, polymorphic_allocator is a Regular type.

Be ware about who owns the memory resource(std::pmr::memory_resource, NOT a value type)?

We can call std::pmr::get_default_resource to get the underneath memory_resource ptr.

--------------------------------------------------------
For stateless allocator:
An allocator object represents a source of memory.

Now for valued allocator:
An allocator value(aka. ptr to memory_resource) represents a handle to a source of memory.

e.g (hell, simple. Now we can even _not_ consider making UDT destructor virtual, deleting destructor issues etc.)
class My_Resource : public memory_resource{
    // non-const since change states
    void *do_allocate(size_t bytes, size_t align) override {
        return ::operator new(bytes, std::align_val_t(align));
    }
    // non-const since change states    
    void do_deallocate(void *p, size_t bytes, size_t align) override {
        ::operator delete(p, bytes, std::align_val_t(align));
    }
    
    bool do_is_equal(const memory_resource& rhs) const noexcept override {
        return (this == &rhs); // God, no dynamic_cast for '==', never!
    }
};


inline memory_resource *get_my_resource() noexcept {
    static My_Resource instance; // thread safe
    return &instance;
}


std::pmr::polymorphic_allocator internally will store the value of a pointer point to memory_resource, which is a word(64 bits) in 64bit machine, which means there are as much as 2^64 distinct memory_resource can be used.

Why std::pmr::polymorphic_allocator taking memory_resource as pointer instead of reference?
Be careful that if passing a local resource by reference, it dangerous. It's hard to see inside the callee that the reference it's lifetime/ownership. However, if passing as pointer, the engineer should know to be aware that it's lifetime/ownership.


Getting the traditional ::operator new/delete memory_resource:
std::pmr::new_delete_resource

Thus, can we make our own stateless std::pmr::polymorphic_allocator?
Of course! Just by default using std::pmr::new_delete_resource as std::memory_resource.


Excerpt from the talk sub-sum up:
  • Allocator types should be copyable, just like pointers.
    • Always true but in C++17 it's more obvious.
  • Allocator types should be cheaply copyable, like pointers.
    • Not necessarily trivially copyable.
  • Memory_resource types should generally be immobile(with the same virtual memory address)
    • A memory resource might allocate chunks out of a buffer stored inside itself as a data member.
-------
std::pmr::synchronized_pool_resource Alike Herb Sutter's talk in Cpp 2015? A centralized heap memory management.

std::pmr::unsynchronized_pool_resource Unthread safe version of std::pmr::synchronized_pool_resource
-------
Allocators are 'rebindable family' types.

Why? From Effective STL, Item 10, due to associate containers that the type instance stored is not the 'type instance' but internal data structure inside the container.
i.e
Containers take this type inside:
rebind_alloc<T> from std::allocator_traits


std::array does not use allocator, it's allocated on stack.
std::vector is the only sequential container which doesn't use rebind.
---------
Other 'rebindable families' in C++:
----------

Each 'rebindable family' has a prototype:
  • Pointer and smart-pointer families have a 'void pointer' type
    • Ptr<void>, Sptr<void>
  • Allocator families have a 'proto-allocator' type
    • Alloc<void>
  • Promise and future types have a 'future of void' type
    • future<void>
----------
Fancy pointer:

i.e
std::allocator_traits::allocate could return a pointer points to either:
----------

Reference:
[reddit] Q: How should C++ support persistent memory?
http://vsdmars.blogspot.com/2018/06/cproposalnote-implicit-creation-of.html

Jun 2, 2018

[C++][book][elements of programming][note] regular type

Reference:
Fundamentals of Generic Programming - Alex Stepanov
[C++11] C++11 Library Design

Reading notes for:
Titus Winters - Revisiting Regular Types

Define Regular types (quoted):
The term Regular is meant to describe the syntax and semantics of built-in types in a fashion that allows user-defined types to behave sensibly.

The C++ programming language allows the use of built-in type operator syntax for user-defined types.
This allows us to make our user-defined types look like built-in types.
Since we wish to extend semantics as well as syntax from built-in types to user types, we introduce the idea of a Regular type, which matches the built-in type semantics, thereby making our user-defined types behave like built-in types as well.

Thus, define customize type as 'do as the ints do'.

Regular definition:
Both definitions focus heavily on semantics not just syntax.


The reasoning about code is much easier if the code consists of Regular types, instead of non-Regular ones, using the existing understanding of how built-in types work.


Four of the most basic semantic requirements on Regular types from Stepanov's early paper:
// comparison follows from copy
T a = b; assert(a==b);

// copy and assignment are the same
T a1; a1 = b; T a2 = b; assert(a1 == a2);

// copy/assignment is by value, not reference
T a = c; T b = c; a = d; assert(b==c);

// zap always mutates, unmutated values are untouched
T a = c; T b = c; zap(a); assert(b==c && a!=b);


Reference:
Identity of indiscernibles : https://en.wikipedia.org/wiki/Identity_of_indiscernibles

Logicians might define equality via the following equivalence:
x == y ⇔ ∀ predicate P, P(x) == P(y)

This is true:
x == y ⇒ ∀ predicate P, P(x) == P(y)

But reverse might not be true:
∀ predicate P, P(x) == P(y) ⇒ x == y


Programming languages inherently contain predicates that don't exist in pure math, because the execution on computing hardware is a somewhat leaky abstraction.
(Consider X, Y refer to same memory address but might has it's value changed.)

In general, we focus on predicates that observe 'the value' rather than the identity of the instance.

Objects which are naturally variable sized must be constructed in C++ out of multiple simple structs, connected by pointers. In such cases, we say that the object has remote parts. For such objects, the equality operator must compare the remote parts...


Definition of equality:
Two objects are equal if their corresponding parts are equal (applied recursively), including remote parts (but not comparing their addresses), excluding inessential components, and excluding components which identify related objects.

When designing our own Regular type:
  • how to compare two instances of our type (by value, focusing on the logical state, not comparing by identity/memory location)
  • If our type implements all the syntactic/semantic requirements for Regular

P0898(r2) Standard Library Concepts
Definition of concept (in general, including philosophy)

UDT considered Regular type iff has these member functions:
  • DefaultConstructible, 
  • CopyConstructible, 
  • Destructible,
  • Movable, 
  • Swappable,
  • Assignable, 
  • EqualityComparable

Consider const member function thread safe.
i.e
  • concurrent (non-synchronized) calls to const methods are allowed,
  • if any concurrent call is made to a non-const method, there is the chance for a data race.
(ref CppCon 2014: Herb Sutter "Lock-Free Programming note )
  • On the C++ abstract machine there is no such thing as a safe data race. 
  • The C++ standard specifically calls this out: data races are undefined behavior. 
  • No correct program has undefined behavior. 
  • const means const contract. If internal state changes, violates the const contract.

Classify types as either 'thread-safe', 'thread-compatible', or 'thread-unsafe', based on the conditions under which use of its API may result in a data race.
  • Thread-safe:
    No concurrent call to any API of this type causes a data race.
    This is useful for things like a Mutex.
    Generally speaking, thread-safe types are easiest to work with, but you pay for some of that usability in performance or API restrictions or both.
    (Reference[C++] Always consider function thread safeness drags performance in single thread code. )
  • Thread-compatible:
    No concurrent call to any const operation on this type causes a data race.
    Any call to a non-const API means that instance must be used with external synchronization.
    C++ guarantees that standard library types are at least thread-compatible.
    This follows from the general pattern of Regular design, and 'do as the ints do' as int is thread-compatible.
    In most cases, this is in-line with the philosophy of C++ - you do not pay for what you do not use.
    If you operate on an optional<int>, you can be sure that it isn't grabbing a mutex.
    On the other hand, thread-compatible may have overhead in some cases: shared_ptr<> is unnecessarily expensive in cases where there is no sharing between threads, because of the use of atomics to synchronize the reference count.
    (GCC's shared_ptr detects whether the executable is linked to libpthread and uses non-atomic updates when possible.)
  • Thread-unsafe: Even concurrent calls to const APIs on this type may cause data races - use of an instance of such a type requires external synchronization or knowledge of some form to be used safely.
    These are generally either used with a mutex or are used with knowledge like 'I know that this instance is only accessed from this thread' or 'I know that my whole program is only single threaded.'
    Types like this may be because of mutable members, or because of non-thread-safe data that is shared between instances.


When using a function, or a Regular type instance, ALWAYS consider precondition.

Consider about int* type instance.
It's precondition can only be checked during run-time,
and there's no member function of int* type can check the precondition of int* type instance.
i.e
Invoking int* operation safely requires structural knowledge of the program. A type that has dependent preconditions has one or more such APIs; these are often (but not always) about properties of non-owned objects/external memory/etc.

APIs that have dependent preconditions are more complicated to use - they fundamentally require knowledge about the rest of the program in order to use safely.


Race-Free + Regular

When operates on a type instance, consider it race-free iff:
  • Thread-compatible and not shared with other threads for writing.
    If been handed a (non-racing) const T& you can operate on this in const fashion.
    If necessary, you can copy it to ensure there are no lurking references and perform any computation / mutation safely (but inefficiently).
    With minor knowledge (the instance isn't shared), a T& can be used safely as if it were T.
  • It has dependent-preconditions, but for a particular instance + any dependent data, the program structure guarantees safe usage.
  • Single-threaded usage - There is only one thread in the program and thus all instances of the type are safe to use, or a given instance is known to not be shared among threads.

With above 3 options, we have these definitions:
  • Thread-compatible + Regular is what we really want for user-defined types that mimic built-ins.
    This lets us reason about an instance in the expected fashion and use it efficiently in conjunction with generic algorithms.
    Types that have mutable data may have some overhead to support this.
  • Dependent-preconditions with knowledge that an instance + its dependent data are safe to use.
    This is the common usage for string_view when we use it as a non-owning parameter type: the underlying buffer will outlive the function call and is immutable for the duration of the call. (reference: https://github.com/jeaye/value-category-cheatsheet/blob/master/value-category-cheatsheet.pdf)
    Given that external knowledge of that underlying buffer, string_view behaves as if it were Regular. This makes sense, given that string_view was designed to be a drop-in replacement for const string&, and although references are not Regular types (Reference: [C++] Union/StandardLayoutType can not have reference data member), std::string types are.
  • Single-threaded usage - This is easy to misuse, but can be an important area for optimization.
    Consider the discussions to provide a shared_ptr analogue that does not synchronize its reference count - if we know something about program structure, or can guarantee particular usage for an instance, we can design a more efficient type in this fashion. Given that knowledge, such a shared_ptr can still behave as if it were Regular.
Use this to verify if the type is regular type:
using T = UDT;
void DoSomething(const T& t);

const T a = SomeT();  // Assume SomeT() is providing a
                      // long-lived and stable buffer.
const T b = SomeT();

if (a == b) {
  DoSomething(a);
  assert(a == b);
}

//Stepanov’s axioms about assignment and comparison.
// comparison follows from copy
T a = b; assert(a==b);

// copy and assignment are the same
T a1; a1 = b; T a2 = b; assert(a1 == a2);

// copy/assignment is by value, not reference
T a = c; T b = c; a = d; assert(b==c);

// zap always mutates, unmutated values are untouched
T a = c; T b = c; zap(a); assert(b==c && a!=b);


The point of having string_view, std::span is to make the API interface consistent, which is,
instead of using
  • const char* 
  • const string& // reference itself is NOT regular type, which is not owning.


We could simply use
  • const std::span  // using const to ensure it's member function called is thread safe.
  • const std::string_view  // using const to ensure it's member function called is thread safe.

Nov 25, 2017

[C++][Book read] C++ concurrency in Action, 2nd edition

std::thread::native_handle
std::thread::hardware_concurrency()

Aware of thread constructor:
It's passing argument to callable function as rvalue through std::decay_t<T>.
Thus, if callable function is taking an l-value reference, compile fails.

std::thread::id offer the complete set of comparison operators,
which provide a total ordering for all distinct values.

The Standard Library provides std::hash<std::thread::id> so that values of
type std::thread::id can be used as keys in the new unordered associative containers.

FP like functions:



Before calling thread.join(), things have to be considered all code path with:
  • Will the callable function throw?
  • If the caller thread throws, what happen if thread.join() not called.
  • Using RAII
For thread's callable function's arguments:
by default the arguments are copied into internal storage,
where they can be accessed by the newly created thread of execution,
and then passed to the callable object or function as rvalues as if they were temporaries.
Thus, use
std::ref

reference boost::bind:
http://vsdmars.blogspot.com/2013/06/cboost-lambda-note.html
mem_fn

Sharing data between threads:
If all shared data is read-only, there's no problem, because
the data read by one thread is unaffected by whether or not another thread is reading the
same data.
i.e
a const member function implies thread safe.


Sharing data between threads:
mutex:

std::mutex some_mutex;
std::lock_guard<std::mutex> guard(some_mutex);
std::lock(lhs.m,rhs.m);
# instance of std::adopt_lock_t http://en.cppreference.com/w/cpp/thread/lock_tag_t
std::lock_guard<std::mutex> lock_a(lhs.m,std::adopt_lock);
std::lock_guard<std::mutex> lock_b(rhs.m,std::adopt_lock);

std::lock
std::scoped_lock RAII style.

Race conditions:
Avoiding problematic race conditions:
  1. Wrap data structure with a protection mechanism, to ensure that only the thread actually performing a modification can see the intermediate states where the invariants are broken.
  2.  Modify the design of your data structure and its invariants so that modifications are done as a series of indivisible changes, each of which preserves the invariants. This is generally referred to as lock-free programming.
  3. Handle the updates to the data structure as a transaction, just as updates to a database are done within a transaction. The required series of data modifications and reads is stored in a transaction log and then committed in a single step. If the commit can’t proceed because the data structure has been modified by another thread, the transaction is restarted. This is termed software transactional memory (STM), and it’s an active research area at the time of writing.
Aware of constructo might throw, which makes the container's data loss.
Thus solution:
  • PASS IN A REFERENCE
  • REQUIRE A NO-THROW COPY CONSTRUCTOR OR MOVE CONSTRUCTOR
  • RETURN A POINTER TO THE POPPED ITEM
  • PROVIDE BOTH OPTION 1 AND EITHER OPTION 2 OR 3

The class unique_lock is a general-purpose mutex ownership wrapper allowing deferred locking,
time-constrained attempts at locking, recursive locking, transfer of lock ownership,
and use with condition variables.

RWLock:
The class shared_lock is a general-purpose shared mutex ownership wrapper allowing deferred locking, timed locking and transfer of lock ownership. Locking a shared_lock locks the associated shared mutex in shared mode (to lock it in exclusive mode, std::unique_lock can be used)

std::unique_lock<std::mutex> lock_a(lhs.m,std::defer_lock); // http://en.cppreference.com/w/cpp/thread/unique_lock
std::unique_lock<std::mutex> lock_b(rhs.m,std::defer_lock);
std::lock(lock_a,lock_b); // http://en.cppreference.com/w/cpp/thread/lock


mutex:

has two levels of access:
  • shared - several threads can share ownership of the same mutex.
  • exclusive - only one thread can own the mutex.
Shared mutexes are usually used in situations when multiple readers can access the same resource at the same time without causing data races, but only one writer can do so.


Most of the time, if you think you want a recursive mutex, you probably need to change
your design instead. A common use of recursive mutexes is where a class is designed to be
accessible from multiple threads concurrently, so it has a mutex protecting the member data.



Ch. 4

Synchronizing concurrent operations:

header
<condition_variable>

std::condition_variable is preferred then std::condition_variable_any.

Pattern:

Producer:

std::lock_guard

modify data.
unlock mutex.
std::condition_variable notify_one 

Waiter:

std::unique_lock
std::condition_variable wait 
modify data.
unlock mutex.

header
<future>

std::async
Just as with std::thread, if the arguments are rvalues,
the copies are created by moving the originals.
This allows the use of move-only types as both the function
object and the arguments.

#include <string>
#include <future>

struct X
{
void foo(int,std::string const&);
std::string bar(std::string const&);
};

X x;

auto f1=std::async(&X::foo,&x,42,"hello");  // Calls p->foo(42,"hello") where p is &x
auto f2=std::async(&X::bar,x,"goodbye");    // Calls tmpx.bar("goodbye") where tmpx is a copy of x

struct Y
{
double operator()(double);
};
Y y;

auto f3=std::async(Y(),3.141);  // Calls tmpy(3.141) where tmpy is move-constructed from Y()
auto f4=std::async(std::ref(y),2.718);  // Calls y(2.718)

X baz(X&);

std::async(baz,std::ref(x));    // Calls baz(x)

class move_only
{
public:
move_only();
move_only(move_only&&)
move_only(move_only const&) = delete;
move_only& operator=(move_only&&);
move_only& operator=(move_only const&) = delete;
void operator()();
};

auto f5=std::async(move_only());    // Calls tmp() where tmp is constructed from std::move(move_only())

std::packaged_task

The std::packaged_task object is thus a callable object, and it can be wrapped in a
std::function object, passed to a std::thread as the thread function, passed to another
function that requires a callable object, or even invoked directly.

std::promise

some_promise.set_exception(std::make_exception_ptr(std::logic_error("foo ")));

Another way to store an exception in a future is to destroy the std::promise or
std::packaged_task associated with the future without calling either of the set functions on
the promise or invoking the packaged task.
In either case, the destructor of the std::promise or std::packaged_task will store a
std::future_error exception with an error code of std::future_errc::broken_promise
 in the associated state if the future isn’t already ready;

std::future


// get shared_future
std::promise< std::map< SomeIndexType, SomeDataType, SomeComparator,
SomeAllocator>::iterator> p;
auto sf=p.get_future().share();

C++ time class:

namespapce
std::literals::chrono_literals 
contains literals and chrono_literals
std::ratio has predefined type.
using namespace std::literals::chrono_literals
using namespace std::literals
using namespace std::chrono_literals
Fixed width integer types

Duration literals
user defined literals from cppref and c++11 faq
 
There are four kinds of literals that can be suffixed to make a user-defined literal:
  • integer literal: accepted by a literal operator taking a single unsigned long long or const char* argument.
  • floating-point literal: accepted by a literal operator taking a single long double or const char* argument.
  • string literal: accepted by a literal operator taking a pair of (const char*, size_t) arguments.
  • character literal: accepted by a literal operator taking a single char argument.

using namespace std::chrono_literals;
auto one_day=24h;
auto half_an_hour=30min;
auto max_time_between_messages=30ms;

Explicit conversions can be done with std::chrono::duration_cast<>
std::chrono::milliseconds ms(54802);
std::chrono::seconds s;
std::chrono::duration_cast<std::chrono::seconds>(ms);

Time points

std::chrono::time_point<>


header:

<experimental/future> 

std::experimental::when_all
std::experimental::when_any

std::experimental::latch
std::experimental::barrier
more basic, and potentially therefore has lower overhead

std::experimental::flex_barrier
more flexible, but potentially has more overhead.

Nov 22, 2017

[C++] error_code usage and design

Reference:
https://akrzemi1.wordpress.com/2017/07/12/your-own-error-code/
https://akrzemi1.wordpress.com/2017/08/12/your-own-error-condition/
https://akrzemi1.wordpress.com/2017/09/04/using-error-codes-effectively/

Header <system_error>

tl;dr;
std::error_code
  • provides value (int)  and catagory (std::error_category)
  • It's platform-dependent.
  • used for storing and transmitting error codes as they were produced by originating library, unchanged;


std::error_category
  • used to differentiate the error_code/error_condition's domain.
  • As a bridge, has member function equivalent to test out error_code and error_condition are in the same domain or not.
  • Has member function default_error_condition to provide error_condition base on error_code.


std::error_condition
  • provides value (int)  and category (std::error_category)
  • It's not platform-dependent.
  • used for performing queries on error_codes, for the purpose of grouping or classification or translation.

Design

  • One exception contains error_code present different meaning.
  • Make sure error_code.value has success value equals to 0.
  • enums in C++: we can create values from outside the enumerated range.
    It is for this reason that compilers issue a warning in switch-statement that
    “not all control paths return value” even though you have a case label for every enumeration.
  • std::is_error_code_enum<Errc>::value returns true, 
    If it's true, the enum type can be used to construct error_code.
  • Function make_error_code taking error_code is defined and accessible through
    argument-dependent lookup.
  • std::errc (enum) 
  • std::is_error_condition_enum
  • If it's true, the enum type can be used to construct error_condition.

Sep 15, 2017

[C++] Using Surrogate Call Function for speed up member function name resolution.

[C++] Value vs. Reference type conversion overload ranking tie breaker rule.

Surrogate Call Function:
http://en.cppreference.com/w/cpp/language/overload_resolution#Call_to_a_class_object

sample code:
template <typename Head, typename... Tail>
struct FUN;

// Base case.
template <typename Head>
struct FUN<Head> {
  using F = Head (*)(Head);
  operator F() const;
};

// Recursive case.
template <typename Head, typename... Tail>
struct FUN : FUN<Tail...> {
  using F = Head (*)(Head);
  operator F() const;
};


or just:
template <typename T>
struct FUN_leaf {
  using F = T (*)(T);
  operator F() const;
};

template <typename... Ts>
struct FUN : FUN_leaf<Ts>... {};


Originally(SLOW) using inheritance introduce function name overloading for avoiding hidden ancestor type's function name:
template <typename Head, typename... Tail>
struct FUN;

// Base case.
template <typename Head>
struct FUN<Head> {
  Head operator()(Head) const;
};

// Recursive case.
template <typename Head, typename... Tail>
struct FUN : FUN<Tail...> {
  using FUN<Tail...>::operator();
  Head operator()(Head) const;
};


Surrogate function example:
int f1(int);
int f2(float);

typedef int (*fp1)(int);
typedef int (*fp2)(float);

struct A {
  operator fp1() { return f1; }
  operator fp2() { return f2; }
} a;

int i = a(1);  // calls f1 via pointer returned from conversion function

Sep 3, 2017

[c++][memo] cast char* to T* violates memory alias.


Casting a pointer to some type T to a pointer to a char type does not violate strict aliasing.
Casting a pointer to a char type to a pointer to an unrelated type does break strict aliasing.

Jun 15, 2017

[C++][note] Can Reordering of Release/Acquire Operations Introduce Deadlock?

preshing's article:
Can Reordering of Release/Acquire Operations Introduce Deadlock?

C++17 working draft:
http://www.open-std.org/jtc1/sc22/wg21/docs/papers/2017/n4659.pdf

excerpt:
N4659, section 4.7.2:18 states:
An implementation should ensure that the last value (in modification order) assigned by an atomic or synchronization operation will become visible to all other threads in a finite period of time.


Refer to this note:
http://vsdmars.blogspot.in/2015/10/c-concurrent-notenote-ch5-study-note.html
RELAXED ORDERING:
Operations on atomic types performed with relaxed ordering don’t participate in synchronizes-with relationships.

Operations on the same variable within a single
thread still obey happens-before relationships, but there’s almost no requirement on ordering relative to other threads.

The only requirement is that accesses to a single
atomic variable from the same thread can’t be reordered; once a given thread has seen a particular value of an atomic variable, a subsequent read by that thread can’t retrieve an earlier value of the variable.

1. 同一個thread仍有同一個 variable 的 happen before relationship
2. 同一個thread同一個variable不能被either compiler reordered or memory reordering.
3. 同一個thread但不同variable,compiler仍能做reordering!!

----
RMW operations had to see the latest value in the object's modification order;
even 32.4:11 in the standard says so, quote:
Atomic read-modify-write operations shall always read the last value (in the modification order) written before the write associated with the read-modify-write operation.

May 9, 2016

[C][C++][UB] in details.

Reference:
Both true and false: a Zen moment with C

asm: test instruction:
https://web.itu.edu.tr/kesgin/mul06/intel/instr/test.html

asm: SETNE instruction :
https://web.itu.edu.tr/kesgin/mul06/intel/instr/setne_setnz.html

code:

#include <stdio.h>
#include <stdbool.h>

int main(int argc, char *argv[])
{
    volatile bool p;

    if ( p )
        puts("p is true");
    else
        puts("p is not true");

    if ( ! p )
        puts("p is false");
    else
        puts("p is not false");

    return 0;
}
asm code:
 .file   "bool1.c"
        .intel_syntax noprefix
        .section        .rodata
.LC0:
        .string "p is true"
.LC1:
        .string "p is not true"
.LC2:
        .string "p is false"
.LC3:
        .string "p is not false"
        .text
        .globl  main
        .type   main, @function
main:
.LFB0:
        push    rbp
.LCFI0:
        mov     rbp, rsp
.LCFI1:
        sub     rsp, 32
.LCFI2:
        mov     DWORD PTR [rbp-20], edi
        mov     QWORD PTR [rbp-32], rsi
        movzx   eax, BYTE PTR [rbp-1]
        test    al, al
        je      .L2
        mov     edi, OFFSET FLAT:.LC0
        call    puts
        jmp     .L3
.L2:
        mov     edi, OFFSET FLAT:.LC1
        call    puts
.L3:
        movzx   eax, BYTE PTR [rbp-1]
        xor     eax, 1  // HERE, since local variable isn't init., the value could be other value than 1.
                        // Thus, an XOR will always produce True.
        test    al, al
        je      .L4
        mov     edi, OFFSET FLAT:.LC2
        call    puts
        jmp     .L5
.L4:
        mov     edi, OFFSET FLAT:.LC3
        call    puts
.L5:
        mov     eax, 0
        leave
.LCFI3:
        ret
 
Reference:
Undefined behavior can result in time travel

If there's an UB in code path, compiler could consider all code paths go to one code path.

code:
int table[4];
bool exists_in_table(int v)
{
    for (int i = 0; i <= 4; i++) {
        if (table[i] == v) return true;
    }
    return false;
}

inference:
A post-classical compiler, on the other hand, might perform the following analysis:
  • The first four times through the loop, the function might return true.
  • When i is 4, the code performs undefined behavior.
  • Since undefined behavior lets me do anything I want, I can totally ignore that case and proceed on the assumption that i is never 4. (If the assumption is violated, then something unpredictable happens, but that’s okay, because undefined behavior grants me permission to be unpredictable.)
  • The case where i is 5 never occurs, because in order to get there, I first have to get through the case where i is 4, which I have already assumed cannot happen.
  • Therefore, all legal code paths return true.


to code:
bool exists_in_table(int v)
{
    return true;
}

Reference:
What Every C Programmer Should Know About Undefined Behavior #1/3
What Every C Programmer Should Know About Undefined Behavior #2/3
What Every C Programmer Should Know About Undefined Behavior #3/3
A Guide to Undefined Behavior in C and C++, Part 1
A Guide to Undefined Behavior in C and C++, Part 2
A Guide to Undefined Behavior in C and C++, Part 3

  • Interacting Compiler Optimizations Lead to Surprising Results
  • Undefined Behavior and Security Don't Mix Well
  • Debugging Optimized Code May Not Make Any Sense.
  • "Working" code that uses undefined behavior can "break" as the compiler evolves or changes
  • There is No Reliable Way to Determine if a Large Codebase Contains Undefined Behavior


UBs:
  • Use of an uninitialized variable
  • Signed integer overflow
  • Oversized Shift Amounts
  • Dereferences of Wild Pointers and Out of Bounds Array Accesses
  • Dereferencing a NULL Pointer
  • Violating Type Rules
  • It is undefined behavior to cast an int* to a float* and dereference it (accessing the "int" as if it were a "float").


Reference:
Adventures in undefined behavior: The premature downcast

"If a nonstatic member function of a class X is called for an object that is not of type X, or of a type derived from X, the behavior is undefined."
In other words, if you are invoking a method on an object of type X, then you are promising that it really is of type X, or a class derived from it.

code:
class Shape
{
public:
    virtual bool Is2D() { return false; }
};

class Shape2D : public Shape
{
public:
    virtual bool Is2D() { return true; }
};

Shape *FindShape(Cookie cookie);

void BuyPaint(Cookie cookie)
{
    Shape2D *shape = static_cast<Shape2D *>(FindShape(cookie));
    if (shape->Is2D()) {  // ALWAYS TRUE! Since it's the type of Shape2D
       .. do all sorts of stuff ...
    }
}

Reference:
A static_cast is not always just a pointer adjustment

The rule for null pointers is that casting a null pointer to anything results in another null pointer.

Reference:
A bit of background on compilers exploiting signed overflow


------------
For infinite loop, compiler should not opt out in these conditions:
The implementation may assume that any thread will eventually do one of the following:
  • terminate,
  • make a call to a library I/O function, 
  • access or modify a volatile object, 
  • or perform a synchronization operation or an atomic operation.

Empty infinite loops are UB in C++11 and later.

Reference:
Compilers and Termination Revisited
Is this infinite recursion UB?
Optimizing away a “while(1);” in C++0x
is C implementation allowed to terminate an infinite loop?
[rust] LLVM loop optimization can make safe programs crash

--
Principles for Undefined Behavior in Programming Language Design - John Regehr

Jan 11, 2016

[C++] Writing Fast Code II

[C++] Writing Fast Code I

Video: https://www.youtube.com/watch?v=3_FXy3cT5C8

Baseline:
Choose a baseline for measuring!

e.g:
  • std::sort
  • iostream
  • scanf
Differential timing:
Differential:
  • Run baseline 2n times, measure t(2a)
  • Run baseline n times and contender n times, measure t(a+b)
  • Relative improvement:
    r = t(2a) / (2*(t(a+b)) - t(2a))Some overhead noises canceled.

Common benchmarking pitfalls:
  • No Debug builds.
  • Different setup for baseline and measured.
  • Including ancillary work in measurement
    malloc, printf etc.
  • Mixtures: measure t(a) + t(b) , improve t(a),
    conclude t(b) got improved.
  • Optimize rare cases, pessimism others.
Generalities:
  • Prefer static linking and PDC
  • Prefer 64-bit code, 32-bit data, e.g 2 32-bit int instead of 1 64-bit int.
  • Prefer 32-bit array indexing to pointers.
  • Prefer a[i++] to a[++i] # I am gooood :-) Data dependancy.
    # a[i++] simultaneously access the array element
    # and increase i.
    # PREFETCH!!! Man, i am really good…
  • Prefer regular memory access patterns
  • Minimize flow, avoid data dependencies
Storage pecking order:
  • Use static const for all immutable, constexpr in C++11 and beyond.
    Beware cache issues.
  • Use stack for most variables
    Hot
    0-cost addressing, like struct/class data members
  • Globals: aliasing issues
  • thread_local slowest, use local caching.
    1 instruction in Windows, Linux
    3-4 in OSX
Integrals:
  • Prefer 32-bit int to all other sizes
    (because cache load alignment? Neh, because CPU ALU can
    process as long as 64 bit of data.
    i.e if is 2 32-bit int, it can process in parallel,
    if it’s 1 64-bit, it can only process 1 op.)
    64 bit may make some code 20x slower
    8, 16-bit computations use conversion to 32 bits and back
  • Use small ints in arrays
  • Prefer unsigned to signed (opposite with google coding standard) https://google.github.io/styleguide/cppguide.html
    Except when converting to floating point
  • Most numbers are small

Floating point:
  • Double precision as fast as single precision
  • Extended precision just a bit slower
    Do not mix the three.
  • 1-2 FP add/sub units
  • 1-2 FP mul/div units
  • SSE accelerates throughput for certain computation kernels
  • ints -> FPs cheap, Fps -> ints expensive

Strength reduction:
  • Don’t waste time replacing a/=2 with a>>1
  • Speed hierarchy:
    comparisons
    • (u)int add, sub, bits, shift
    • FP add, sub (separate unit!)
    • (u)int32 mul, FP mul
    • FP division, remainder (for exp, just a minus)
    • (u)int division(only div by 2 is fast. it’s a search op.), remainder

Ok, if really need to do (u)int division, look:


Also, above code is measured!
With 4, it’s because of the cache line.
Remember, comparisons are CHEAP!

Even better: (Using LIKELY)

When write a loop, always start with writing an infinite loop!
With inside, use conditional return!

Minimize indirect writes: Why??
  • Diables enregistering
  • A write is really a read and a write.
    • Transfer 64bytes from memory to cache-line.
    • First load a cache-line, i.e 64 bytes, modify it, and write back to the cache-line.
    • If, write a 64bytes data, than it’s going to be FAST, since there’s no need a load, it just directly write to the cache-line(full 64bytes).
    • i.e PADDING is a performance trick!!!
  • Maculates the cache
Summary:
  • Fewer indirect writes
  • Regular access pattern
  • Fast on small numbers
  • Data dependencies reduced

Checkpoint:
  • We can’t improve what we can’t measure
  • Always choose good baselines
  • Optimize code judiciously for today’s dynamics

Reference: