[C++] RCU

Reference:
[Kernel Doc] What is RCU? -- “Read, Copy, Update”
[NMI] Contents hide (Top) History See also Notes External links Non-maskable interrupt
[Kernel Doc] False Sharing with how to detect and analyze

Source code:
https://android.googlesource.com/kernel/common/+/refs/heads/android-mainline/kernel/rcu/rcu.h

Kernel doc has most concise details about RCU, here we jot down
main idea for fast fresh up the concept.

RCU(Read, Copy, Update) is a synchronization mechanism that was added to the Linux kernel during the 2.5 development effort that is optimized for read-mostly situations.

The basic idea behind RCU is to split updates into 

• “removal” and 
• “reclamation” phases.

The removal phase removes references to data items within a data structure (possibly by replacing them with references to new versions of these data items), and can run concurrently with readers. 

The reason that it is safe to run the removal phase concurrently with readers is the semantics of modern CPUs guarantee that readers will see either the old or the new version of the data structure rather than a partially updated reference.

The reclamation phase does the work of reclaiming (e.g., freeing) the data items removed from the data structure during the removal phase. Because reclaiming data items can disrupt any readers concurrently referencing those data items, the reclamation phase must not start until readers no longer hold references to those data items.

typical RCU update sequence goes something like the following: 

• a) Remove pointers to a data structure, so that subsequent readers cannot gain a reference to it. 
  This can be done due to writes to single aligned pointers are atomic on modern CPUs, allowing atomic insertion, removal, and replacement of data items in a linked structure without disrupting readers. This removal phase does not interrupt readers. It is just that the readers could read old values.
• b) Wait for all previous readers to complete their RCU read-side critical sections. 
  How the reader notify reclamation that they are done? A callback function.
• c) At this point, there cannot be any readers who hold references to the data structure, so it now may safely be reclaimed (e.g., kfree()d).

Should think a) and c) separately. c) can be run in different thread, although it is totally fine to have a) and c) run in same thread.

5 core APIs:

• rcu_read_lock()
• rcu_read_unlock()
• synchronize_rcu() / call_rcu()
• rcu_assign_pointer()
• rcu_dereference()

rcu_read_lock()

void rcu_read_lock(void);

This temporal primitive is used by a reader to inform the reclaimer that the reader is entering an RCU read-side critical section. It is illegal to block while in an RCU read-side critical section, though kernels built with CONFIG_PREEMPT_RCU can preempt RCU read-side critical sections. Any RCU-protected data structure accessed during an RCU read-side critical section is guaranteed to remain unreclaimed for the full duration of that critical section. Reference counts may be used in conjunction with RCU to maintain longer-term references to data structures.

Note that anything that disables bottom halves, preemption, or interrupts also enters an RCU read-side critical section. Acquiring a spinlock also enters an RCU read-side critical sections, even for spinlocks that do not disable preemption, as is the case in kernels built with CONFIG_PREEMPT_RT=y. Sleeplocks do not enter RCU read-side critical sections.

rcu_read_unlock()

void rcu_read_unlock(void);

This temporal primitives is used by a reader to inform the reclaimer that the reader is exiting an RCU read-side critical section. Anything that enables bottom halves, preemption, or interrupts also exits an RCU read-side critical section. Releasing a spinlock also exits an RCU read-side critical section.

Note that RCU read-side critical sections may be nested and/or overlapping.

synchronize_rcu()

void synchronize_rcu(void);

This temporal primitive marks the end of updater code and the beginning of reclaimer code. It does this by blocking until all pre-existing RCU read-side critical sections on all CPUs have completed. Note that synchronize_rcu() will not necessarily wait for any subsequent RCU read-side critical sections to complete.

Example:

https://gemini.google.com/share/6c8e0c362331

[C++] atomics wrap up

Reference:
https://www.youtube.com/watch?v=ZQFzMfHIxng

• Lock-free means 'FAST'
• Algorithm rules supreme
• 'Wait-free' has nothing to do with time
• Wait-free refers to the number of compute 'steps'
• Steps do not have to be of the same duration
• Atomic operations do not guarantee good performance

What types can be made atomic?

• Any trivially copyable type can be made atomic
• Continuous chunk of memory
• Copying the object means copying all bits(memcpy)
• No virtual functions, noexcept constructor
  

Operation:

std::atomic<int> x{0}; 
++x;
x++;
x += 1;
x |= 2;
int y = x * 2;
x = y + 1;

x *= 2; // no atomic multiply; not compile
x = x + 1; // not atomic; atomic read x store in the register follow by atomic write x
x = x * 2; // not atomic; atomic read x store in the register follow by atomic write x

 // same compiles to IR.
++x;
x += 1;
x = x + 1;

std::atomic<T>::load

std::atomic<T>::store

std::atomic<T>::exchange
std::atomic<T>::compare_exchange_{weak, strong}

What is so special about CAS? 

• Compare-and-swap (CAS) is used in most lock-free(not wait-free) algorithms

std::atomic x{0};
int x0 = x;

while(!x.compare_exchange_strong(x0, x0+1)){}

• even:

while(!x.compare_exchange_strong(x0, x0*2)){} // x0*2 is not atomic

Spinlock as using FUTEX with pause, slower if thread number > core number

std::atomic is not always lock free;

std::atomic<T>::is_always_lock_free; compile time

Judge at run-time due to runtime memory alignment.

Padding matters.

Cache line sharing

The size of cache-line matters.

Atomic operation do wait on each other,

• in particular, write operation do
• read-only operations can scale near-perfectly.

Be aware of NUMA architecture cache-line

Spurious wake up

https://vsdmars.blogspot.com/2024/03/c-compareexchangeweak.html

Atomic queue; lock free implement

and memory-barrier plays the role; only store and release issues memory barrier operation.

reference: 

https://vsdmars.blogspot.com/2019/06/c-c-concurrency-in-action-second.html

https://vsdmars.blogspot.com/2015/10/c-concurrent-notenote-ch5-study-note.html

https://vsdmars.blogspot.com/2018/06/c-regular-type.html

https://vsdmars.blogspot.com/2018/09/concurrency-c-wrap-up-2018.html

https://vsdmars.blogspot.com/2021/10/c-memory-model-in-depth.html

There are only 2 places need barrier:

• processing invalid queue (RMB)
• write store buffer to cache. (WMB) 

That's it, period!

CAS

Read is faster than write, keep this in mind. Thus the memory order setting is different.

For read, use more relax orders.

Default memory order

Consider memory barrier usage as a contract between engineers

[CMake] Modern CMake in style

Reference:
Modern CMake Modules - Bret Brown - CppCon 2021
CppCon 2017: Mathieu Ropert “Using Modern CMake Patterns to Enforce a Good Modular Design”

$ clang++ main.cpp -o vsdmars -Wreturn-type

is same as:

target_compile_options(
    vsdmars PRIVATE
    $<$<COMPILE_LANG_AND_ID:CXX,Clang,GNU>:-Werror=return-type>
)

Find Modules

Loaded by the find_package()
Find<PackageName>.cmake // can have find_library(...) command

Use Modern CMake

1. declare module with ADD_LIBRARY or ADD_EXECUTABLE
2. declare build flags with TARGET_xxx()
3. declare dependencies with TARGET_LINK_LIBRARIES
4. Specify what is PUBLIC and what is PRIVATE
5. Consider people are using your library through CMake

Don't

1. breaking cmake target model
2. breaking cmake features
   dev workflows
   functions
   standard modules
3. making changes in source directories
4. avoid version control operations
5. toolchain details
   linkers
   compiler
6. build requires magic flags like -DMAGIC_VAR
7. Hijacking CMake variables
8. Requiring special build targets
9. Expecting certain environments

$ cmake && cmake --build && ctest && cmake --install

Write a module

name the file

vsdmars.cmake // include(vsdmars)

FindVsdmars.cmake // find_package(vsdmars REQUIRED)

vsdmarsConfig.cmake // find_package(vsdmars REQUIRED) <--- Most powerful

e.g.

vsdmarsConfig.cmake

function(target_needs_news)
    cmake_parse_arguments(parsed
        ""             #   options
        "TARGET"       # one-value keywords
        ""             # multi-value keywords
        ${ARGN}        # strings to parse
    )
    # TODO: defensive argument parsing
    set(target ${parsed_TARGET})
    message(VERBOSE "done, ${target}")
endfunction()

Defensive argument parsing

if(parsed_UNPARSED_ARGUMENTS)
    message(FATAL_ERROR
        "BAD ARGUMENT: ${parsed_UNPARSED_ARGUMENTS}"
    )
endif()

if(parsed_KEYWORDS_MISSING_VALUES)
    message(...)
endif()

Essential for CMake modules

1. API documentation
   README
2. Testing the cmake module we just wrote
   https://crascit.com/2016/10/18/test-fixtures-with-cmake-ctest/
3. message() with verbosity

$ cmake --log-level=verbose

Installing a CMake modules

1. share/cmake/vsdmars/vsdmarsConfig.cmake
2. ship version files as well if needed

CMakeLists.txt for CMake modules

cmake_minimum_required(VERSION 3.21)
project(vsdmars LANGUAGES NONE) # if module is lang agnostic
enable_testing() # every CMakeLists.txt should have this

install(
    FILES vsdmarsConfig.cmake
    DESTINATION share/cmake/vsdmars
    COMPONENT vsdmars
)

Development Setup

CMAKE_GENERATOR=Ninja
CMAKE_TOOLCHAIN_FILE=path/to/ToolChain.cmake
CMAKE_BUILD_TYPE=Debug
DESTDIR=your/staging/dir

Development Workflow

$ git clone ...

$ cmake -B build -S vsdmars

$ cmake --build build

$ ctest --test-dir build

$ cmake --instal build \

    --prefix /opt/...

    --component vsdmars

Integration Workflow

$ git clone ...

$ cmake -B cxx-build \

    -S cxx-project \

    -DVSDMARS_DIR=./vsdmars/

$ cmake --build cxx-build

$ ctest --ctest-dir cxx-build

$ cmake --install cxx-build \

    --prefix /opt/vsdmars \

    --component cxx-project

Build flags don't scale

• every change in public flags has to be propagated upwards
• Most people give up and put every include director in a common/root build file.
• Correct way of doing so is to put all 3rd party
  my/include/namespace
  into
  ./include/my/include/namespace

Modern build systems

• Forbid/report circular and hidden dependencies
• Help developer reason at module level
• Do more than build as you are told

How?

• Define your module build flags
• Define your module dependencies
• Keep out of other modules internals
• Each module has a set of private flags
• Each module has a set of public flags(required to build against its interface)
• Build interfaces are transitive
• Private means .cpp includes other headers
• Public means .h includes other headers
• Build flags are not gone but encapsulated
• Can still with CPPFLAGS, CXXFLAGS and LDFLAGS, and external flags are not our concern anymore
• Declare module with ADD_LIBRARY or ADD_EXECUTABLE
• Declare build flags with TARGET_xxx()
• Declare dependencies with TARGET_LINK_LIBRARIES
• Specify what is PUBLIC and PRIVATE

Global setup

cmake_minimum_required(VERSION 3)
add_compile_options(-Wall -Werror etc.) // including flags effect ABI
add_library(vsdmarsLib src/xxx.cpp)

Declare flags

target_include_directories(vsdmarsLib PUBLIC include)
target_include_directories(vsdmarsLib PRIVATE src)

if (SOME_SETTING)
    target_compile_definitions(vsdmarsLIB
        PUBLIC WITH_SOME_SETTING
endif()

Declare dependencies

target_link_libraries(vsdmarsLib PUBLIC abc)
target_link_libraries(vsdmarsLib PRIVATE xyz)

Header only libraries

# nothing to build actually, just export headers during install/being pulled by other modules
add_library(vsdmarsLibHeaderOnly INTERFACE)
target_include_directories(vsdmarsLibHeaderOnly INTERFACE include)
target_link_libraries(vsdmarsLibHeaderOnly INTERFACE Boost::Boost)

Antipatterns

• Don't use macros that affect all targets
  INCLUDE_DIRECTORIES()
  ADD_DEFINITIONS()
  LINK_LIBRARIES()
• Don't use TARGET_INCLUDE_DIRECTORIES() with a path outside your module
• Don't use TARGET_LINK_LIBRARIES() without specifying PUBLIC, PRIVATE or INTERFACE
• Don't use TARGET_COMPILE_OPTIONS() to set flags that affect the ABI

3rd party

cmake_minimum_required(VERSION 3.5)
find_package(GTest)
add_executable(foo ...)
target_link_libraries(foo GTest::GTest GTest::Main)

find_library(XXX_LIB xxx HINTS ${XXX_DIR}/lib)
add_library(xxx SHARED IMPORTED LOCATION ${XXX_LIB})
target_include_directories(xxx INTERFACE ${XXX_DIR}/include)
target_link_libraries(xxx INTERFACE Boost::boost)

[C++][CPPCON] tips from 'High Performance Trading Systems'

Reference:
https://youtu.be/NH1Tta7purM

If you're not at all interested in performance, shouldn't you be in the Python room down the hall? - Scott Meyers

• the hot-path is only exercised 0.01% of the time = the rest of the time the system is idle or doing administrative work
• OS, networks and hardware are focused on throughput and fairness
• Jitter is unacceptable

What matters

• compiler(version)
• machine architecture
• 3rd party library
• build and link flags

Template-based configuration

Using template to remove branches, eliminates code that won't be executed, etc.

Lambda functions are fast and convenient.

template<typename T>
void sendMsg(T&& lambda) {
    lambda();
}

Memory allocation

• Allocations are costly
  Use a pool of preallocated objects
• Reuse objects instead of deallocating
  Intrusive container
• Delete large objects with another thread.
  beware of shared allocator

Exceptions is OK in (gcc, clang, msvc)

• Zero cost if don't throw
• Don't use exceptions for control flow, slow.

Multi-threading

Multi-threading is best avoided for latency-sensitive code

• sync of data via locking is expensive
• lock free code may still require locks at the hardware level
• mind-bendingly complex
• Easy for the producer to accidentally saturate the consumer

If multi-thread is a must

• keep shared data to an absolute minimum
• Multiple threads writing to the same cacheline will get expensive
• Consider passing copies of data rather than sharing. e.g. single writer, single reader
• lock free queue
• If have to share data, consider not using synchronization
  e.g. maybe live with out-of sequence updates.

When using map, 

consider using open addressing algorithm map,

e.g. google's dense_hash_map

A hybrid approach:

Something about 'inline'

• inline keyword mainly means: external linkage
• attribute always_inline and noinline  are a stronger hint to the compiler, measure before use.

Keeping the cache hot:

Don't share L3 cache

    disable all but 1 core (or lock the cache)

If you do have multiple cores enabled, choose your neighbours carefully:

    - Noisy neighbours should probably be move to a different physical CPU

std::pow can be slow.

Don't use system-calls.

Bottlenecks occur in surprising places, so don't try to second guess and put in a speed hack until you've proven that's where the bottleneck is. - Rob Pike

A language that doesn't affect the way you think about programming is not worth knowing. - Alan Perlis

[assembly][cppcon 2017] What Has My Compiler Done for Me Lately? -- Matt Godbolt

Slides:
https://goo.gl/Ljrg9m

Nice talk! Matt himself is really knowledgeable and easy going person, one of the best talk for 2017 CppCon.


Instruction:
lea  (load effective address)

struct Point
{
     int xcoord;
     int ycoord;
};

int y = points[i].ycoord;   // MOV EDX, [EBX + 8*EAX + 4]    ; right side is "effective address"
int *p = &points[i].ycoord; // LEA ESI, [EBX + 8*EAX + 4]  ; load the address in ESI

Reference:
http://vsdmars.blogspot.com/2017/11/assembly-note.html
http://www.jagregory.com/abrash-zen-of-asm/
https://www.amazon.com/Programming-Ground-Up-Jonathan-Bartlett/dp/1616100648

Tools:
http://quick-bench.com

[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
• Bounds checking
• Address sanitizers (with 'fuzzing')
  https://fuzzing-project.org/tutorial2.html
• -fsanitize=address

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 ()

[C++][CppCon 2017] Chandler Carruth “Going Nowhere Faster”

[2018]

Before tackling with Chandler's 2018 CppCon's talk,
review what he gave last year(2017)

CppCon 2017: Chandler Carruth “Going Nowhere Faster”

Make Code Fast:
1. Use efficient algorithms, fast data structure & idioms
2. Benchmark the code that matters, understand why
3. Use hybrid data structures to optimize allocations & cache locality

Only care about performance that you BENCHMARK.

Additional reference:

Mike Acton's 2014's talk:

https://vsdmars.blogspot.com/2017/11/cppcon-2014-data-oriented-design-mike.html

Read and write considered harmful - Hubert Matthews [ACCU 2018]

https://vsdmars.blogspot.com/2018/05/accu-2018-readwrite-thinking-would-be.html

Profiling:

Use counters to track cache miss rates.

Use Efficiency Sanitizer to optimize data structures.

Tools:

https://github.com/google/sanitizers

https://github.com/google/benchmark

CPU Register reference:

http://faydoc.tripod.com/cpu/

https://docs.microsoft.com/en-us/windows-hardware/drivers/debugger/x64-architecture

Cheatsheet:

https://cs.brown.edu/courses/cs033/docs/guides/x64_cheatsheet.pdf

%rax: 64 bits version of %eax

Clamp loop example:

int run(int a, int b) {
    return a >= b ? a : b;
}

$ gcc -O3 -masm=intel

.LFB0:
    .cfi_startproc
    cmp edi, esi
    mov eax, esi
    cmovge  eax, edi
    ret
    .cfi_endproc

[assembly] CMOVGE command is the prologue of this talk.

Example from the talk:

void run(){
   vector<int> v;
   # init. v
   for (auto &i : v)
 i = i > 255 ? 100 : i;

}

Keep in mind, most of the time branch isn't good for performance.


The idea of this talk is about cmovge should be faster then branches, but it's not.

Why CMOVGE is slower?

x86 runs microcode instead of assembly (more high level code).

"reorder buffer" captures the microcode, which unrolls the small loop,

i.e instead if branch out, but unrolling it into continuously microcodes,

and save the result back to 'reorder buffer'.

Since microcode unrolls the loops, register conflict happens,

since the same register is been used again and again.

So, x86 has this 'register renaming' concept.

register renaming

--quote:

Register renaming is a form of pipelining that deals with data dependences between instructions by renaming their register operands. An assembly language programmer or a compiler specifies these operands using architectural registers - the registers that are explicit in the instruction set architecture. Renaming replaces architectural register names by, in effect, value names, with a new value name for each instruction destination operand. This eliminates the name dependences (output dependences and antidependences) between instructions and automatically recognizes true dependences.

The recognition of true data dependences between instructions permits a more flexible life cycle for instructions. By maintaining a status bit for each value indicating whether or not it has been computed yet, it allows the execution phase of two instruction operations to be performed out of order when there are no true data dependences between them. This is called out-of-order execution.

After looking at the process of renaming operands we will look at the life cycle of an instruction in a register renaming architecture. Then we will look at a generic hardware organization for it and some possible performance enhancements. Finally, we will look at a brief history of the register renaming concept.

end quote--

Once unrolling the loop into microcode iteration sets, they can be

run 'concurrently' inside each set/forward compute from later sets,

iff there's no dependencies.

This is called "speculative execution". 

Refer to Patterson's Computer Organization and Design

For ALUs, there could be out of order executions.

So, why CMOVGE is slow?

CMOVGE act as a binary operator, it has to evaluate Both operants, which blocks and wait.

And branches thus faster then CMOV.

The init. example from Chandler's talk shows that a simple:

i = i > 100 ? 100 : i;

can be unrolled into if i <= 100 then branches to next loop.

Which is thus faster.

Live demo with tool 'perf'

As we can see, for CMOV, there's a high percentage of backend cycle idle.
As for unrolled microcode branches, it's even higher percentage of backend cycle idle.
Why? Because for each cycle it's storing to memory, and it should be stalled every
cycle due to it's trying to store to memory. For CMOV has lower backend cycle idle
is due to it's doing calculation for the CMOV's operants and waits for CMOV.

C++20 alert :-)

[[likely]] [[unlikely]] attributes _will_ turn CMOV into JUMPS :-)

However, be aware, benchmark to see if the static attribute hints really
agrees with your logic, or the opposite.
Read:
https://vsdmars.blogspot.com/2016/01/likely-or-unlikely-easy-misleading.html

Again, std::vector is gooooooood.... push_back guarantees vector grows.

Question from the audience:

1. Why can't CMOV to be translated to the same code as branches?
It sounds to me like:
can
---

return 42 + std::async([]{sleep(10);return 42;}).get()

---
returns early without waiting .get() ?


2. How about store buffer?
From Chandler: Store buffer doesn't help us here.
Agree that SB is used as another usage.
Reference:
http://vsdmars.blogspot.com/2018/09/concurrency-c-wrap-up-2018.html


3. total store order (TSO)
https://en.wikipedia.org/wiki/Memory_ordering


4. When CMOV is useful?
When dependencies are already being required.

Tools:

Intel® Architecture Code Analyzer
https://software.intel.com/en-us/articles/intel-architecture-code-analyzer


CMDs:
$ perf stat BINARY
$ perf list
$ perf stat -e L1-icache-loads
$ perf record BINARY
$ perf report
$ clang++ -MMD -MT file.o -MF file.o.d -std=c++17 -Wall -O3 -fno-exceptions -fvisibility=hidden -qmlt -fno-omit-frame-pointer -pthread files.cpp -S -o files.s -mllvm -x86-cmov-converter-threshold=0 -stats    # -qmlt debug info.

Reference:

How Computers Work [Jakob Stoklund Olesen]

[CPPCON2017] [Qt] Effective Qt (2017)

Effective Qt

CppCon 2017: Giuseppe D'Angelo “Effective Qt (2017 edition)”

• Understand the Qt containers
• Don't use the Qt containers (unless you have to)
• Qt containers are not actively being developed
• Datatypes held in Qt containers must be default constructible and copiable
• No exception safety guarantees
• Most C++11 APIs still missing
• All post-C++11 APIs missing
• No flexibility w.r.t. allocation, comparison, hashing, etc.
• Use Qt containers if there isn't a STL / Boost equivalent (unlikely)
• Use Qt containers when interfacing with Qt and Qt-based libraries
• using the Qt containers, rather than converting back/forth
• Every time you define a type that you may end up using in a Qt container, remember to declare its typeinfo Q_DECLARE_TYPEINFO.
• Adding a trait “after the fact” is possible, but it's a potential ABI break
• Type traits for Qt containers
• Qt uses type traits to optimize handling of data types in its own containers
• The most important optimization is:
• when growing an array of objects, is it OK to use realloc?
• Safe to do iff the type is relocatable
• Huge optimization gain over allocating a new buffer; moving elements; deallocating the old buffer
• Many types are relocatable and could benefit from this optimization
• E.g. most Qt value classes, thanks to pimpl
• Relocatability:
• The compiler cannot tell whether a type is relocatable or not
• Type authors must annotate relocatable types by using type traits
• Some libraries let authors add these traits:
• Qt → Q_DECLARE_TYPEINFO
• Q_PRIMITIVE_TYPE
• Q_MOVABLE_TYPE
• Q_COMPLEX_TYPE
• EASTL → EASTL_DECLARE_TRIVIAL_RELOCATE
• STL → *crickets*
• if a type has pimpl enabled, but, the pimpl has a pointer point back
  to the type instance itself, it's _not_ movable.
  Reason? Since the instance has been moved, the pointer pointing back
  is garbage.
• A type has pointer pointing to ifself(this type) is not relocatable.
• Beware, any pointer inside the type that is consider to be relocated should
  consider will it point to a valid address after type instance being relocated.
• Understand implicit sharing, and be careful about hidden detaches
• Implicit sharing: a double-edged sword
• STL is NOT using this, actually, forbidding it.
• the Qt way of ref counting.
• COW
• A Qt value class implementation is typically just a pointer to a pimpl, which contains the reference counter and the actual payload
• Reference counter is manipulated during an object's lifetime
• On object creation: refcount is 1
• Copying an object: refcount is incremented by 1
• Destroying an object: refcount is decremented by 1; if it reaches zero, deallocate the pimpl
• Calling a const member function: (nothing)
• Calling a non-const member function: if the refcount is greater than 1, then detach (= deep copy the the payload)
• where's the catch?
• Handing out references to data inside a container does not make the container unshareable
• It's easy to accidentally detach a container
• Accidental detaching can hide bugs
• Code polluted by (out-of-line) detach/destructor calls
• 小心不要將container內的data記憶體位置傳出。
  直接Update 其 data 不會trigger COW!!! 會造成其他
  Reference到此container instance產生錯誤，以為該位置的data
  仍是舊的data.
  Update data? Through container member function!
• Accidental detaches - 1
• “Innocent” code may hide unwanted detaches:
• QVector<int> calculateSomething();
  const int firstResult = calculateSomething().first();
• Calls: T& QVector<T>::first();
• Non-const, may detach and deep copy!
• Solution is easy: call constFirst()
• Accidental detaches - 2
• QMap<int, int> map;
  // ...
  if (map.find(key) == map.cend()) {
  std::cout << "not found" << std::endl;
  } else {
  std::cout << "found" << std::endl;
  }
• find(key) might detach after the call to cend(), returning an iterator pointing to a “different” end
• “found” is printed, even if the key isn't in the container
• Solution: use constFind(key), don't mix iterators and const_iterators
• Never use Qt's foreach / Q_FOREACH;
  use C++11's range-based for. (Be careful with Qt containers.)
• this actually applies to boost foreach as well...
• Disable its usage in your code base by defining QT_NO_FOREACH
• It will extremely likely be removed in Qt 6
• If you are not mutating the container, make the container const – 
• std::as_const(container) (C++17) 
• <utility> header
• qAsConst(container) (Qt 5.7) 
• Don't work with rvalues; capture a const-ref in that case
• 
• Run clazy on your code base, and fix its warnings
• Akin to clang-tidy
• Understand Qt string classes. Embrace QStringView.
• There hasn't been much development around QString / QByteArray in the last few years
• The only important change that happened is that since Qt 5.9 QStringLiteral / QByteArrayLiteral never allocate memory
• Ways to create string in Qt:
• “string”
• QByteArray(“string”)
• A sequence of bytes
• No encoding specified – Akin to std::string
• Implictly shared
• Its constructors allocate memory – QByteArray::fromRawData() to avoid (some) allocation
• QByteArrayLiteral(“string”) never allocates – Since Qt 5.9, this is true on all supported platforms
• Use it to store byte arrays (i.e. data)
• QByteArrayLiteral(“string”)
• QString(“string”)
• A UTF-16 encoded Unicode string – Support for Unicode-aware manipulations, unlike std::u16string 
• Implictly shared
• Its constructors allocate memory – Including QString::fromUtf8(), QString::fromLatin1()
• Clutch: QString::fromRawData() as non-allocating constructor – Prefer QStringView
• QStringLiteral(“string”) never allocates – Since Qt 5.9, this is true on all supported platforms – Data is stored UTF-16 encoded in the readonly data segment
• Use it to store Unicode strings
• QLatin1String(“string”)
• A literal type that wraps a const char * and a size – It doesn't manage anything
• Mostly used in overloads when there's a fast-path implementation possible for Latin-1 strings, and they come from string literals:
• E.g. substring search:
  int QString::startsWith(const QString &substring);
  int QString::startsWith(QLatin1String substring);
  QString str = "...";
  if (str.startsWith(QString("foo"))) // allocates a temp. QString
     doSomething();
  if (str.startsWith(QLatin1String("foo"))) // does not allocate + uses
  doSomething();  // optimized implementation
• QStringLiteral(“string”)
• QString::fromLatin1(“string”)
• QString::fromUtf8(“string”) 
• tr(“string”)
• QStringView(u”string”)
• New in Qt 5.10
• as an interface type
• The primary use case for QStringView is for functions parameters
• If a function needs a Unicode string, and it doesn't store it, use QStringView
• Unicode safe
• Never allocates
• Can be built from a wide variety of sources
• as an alloc-free tokenizer
• To extract substrings, without allocating memory
• QString str = "...";
  QRegularExpression re("reg(.*)ex");
  QRegularExpressionMatch match = re.match(str);
  if (match.hasMatch()) {
    QStringView cap = match.capturedView(1); // no allocations
  // ...
  }
• A non-owning view over a UTF-16 encoded string:
• QString
• QStringView
• std::u16string
• Array and std::basic_string of QChar, ushort, char16_t, wchar_t (on Windows)
• Literal type; akin to C++17's std::u16string_view
• Offers the majority of the const QString APIs, without the need of constructing a QString first
• More APIs, QStringBuilder support etc. expected in 5.11
• Prefer the Standard Library ones.
• Qt containers was there for reasons:
• Qt needed to work on platforms without a STL
• Qt didn't want to expose Standard Library symbols from its ABI
• Qt containers used in Qt APIs, and available for applications
• Qt containers use camelCase
• STL use snake_case

Linear containers

• QVector std::vector
• QList -
• array-backed list
• Not a linked list
• Terribly inefficient if the the object stored are bigger than a pointer
•  Allocates every individual object on the heap
• Avoid using it (unless you have to)
• use QVector instead
• might simply become a typedef for QVector, and a new type (QArrayList?) introduced in Qt6
• QLinkedList std::list
• - std::forward_list
• QVarLengthArray -
• preallocates space for a given number of objects
• avoid hitting the heap
• a vector with SSO
• Similar: Boost's small_vector
• - std::deque
• - std::array

associative containers

• QMap std::map
• QMultiMap std::multimap
• QHash std::unordered_map
• QMultiHash std::unordered_multimap
• - std::set
• - std::multiset
• QSet std::unordered_set
• - std::unordered_multiset

Relocable means:

• Relocability is independent from being POD
• Relocatable types may have non-trivial constructors/destructors
• E.g. Qt pimpl'd value classes
• A trivial type may not be relocatable
• E.g. if the address of an object is its identity
• All C data types are trivial, but non necessarily relocatable

Dont' use deprecated Qt APIs

• Always define QT_DEPRECATED_WARNINGS
• Makes the compiler emit warnings if using deprecated APIs
• Define QT_DISABLE_DEPRECATED_BEFORE to the version of Qt you develop
  against
• Turns usage of deprecated APIs into hard errors, iff they have been deprecated in that Qt version or in a earlier one
• No “new” errors if you upgrade Qt
• E.g. in qmake:
  DEFINES += QT_DISABLE_DEPRECATED_BEFORE=0x050900

Never use QList for your own code

[C++][Cppcon 2017] Modern C++ Interfaces

Reference:
http://www.stevedewhurst.com/
https://www.youtube.com/watch?v=PFdWqa68LmA

Policy-based design: Modern C++ Design, Andrei Alexandrescu

SFINAE becomes more and more essential due to compile time meta-programming.

C++ has become so complex that we can use it easily.

Most good bugs are team efforts.

Increased language complexity is not an advantage in itself.
However, it leads to greater expressiveness than would a less complex language.
Simplicity is an emergent property.

Universal reference as copy constructor bug

http://ericniebler.com/2013/08/07/universal-references-and-the-copy-constructo/
https://eli.thegreenplace.net/2014/perfect-forwarding-and-universal-references-in-c/
https://akrzemi1.wordpress.com/2013/10/10/too-perfect-forwarding/

// write this once and put it somewhere you can
// reuse it
template<typename A, typename B>
using disable_if_same_or_derived =
    typename std::enable_if<
        !std::is_base_of<A,typename
             std::remove_reference<B>::type
        >::value
    >::type;

template<typename T>
struct wrapper
{
    T value;
    template<typename U, typename X =
        disable_if_same_or_derived<wrapper,U>>
    wrapper( U && u )
      : value( std::forward<U>(u) )
    {}
};

The complexity of the language has forced us to become better programmers and designers

Use the force, <type_traits>

Syntax matters

template<typename T>
using IsMonad = typename enable_if<is_monad<T>::value>::type;

template<typename T, typename = IsMonad<T>>
void monad_input(T const& t);

Transparent function objects

e.g:

std::less<void>

Used by, e.g set::lower_bound

template<typename T, typename Comp, ...>
class set{
public:
    iter lower_bound(const T& key);
    template <typename Key,
                typename = typaneme Comp::is_transparent>
    iter lower_bound(const Key& key);
};

Distributed Organic Interfaces

The interface to set is modified based on self-identified properties of its comparator.

Who's in charge of the interface?

•     The set advertieses the availability of an augmented interface.
•     The comparator may choose to enable that interface.

Alternatively,

•     The comparator advertieses its transparency.
•     The set is designed to take advantage of that transparency.

Alternatively,

•     A user notices the potential combination and connects the components.

Compose (e.g:)

template<template<typename...> class ... Preds>
struct Compose {
    template<typename T>
    static constexpr auto eval() {
        auto results = {Preds<T>::value...};
        auto result = true;
        for ( auto el : results)
            result &= el;
        return result;
};

Or even neater (variable template):

template <typename T, template<typename> class... Ts>
inline constexpr auto staisfies_all = 
    (... && Ts<T>::value);

template <typename T, template<typename> class... Ts>
inline constexpr auto staisfies_some = 
    (... || Ts<T>::value);

template <typename T, template<typename> class... Ts>
inline constexpr auto staisfies_none = 
    (... && !Ts<T>::value);

And monoid:

template <typename T>
inline constexpr auto satisfies_my_needs
    = satisfies_all<T, is_signed, is_pod> &&
        satisfies_none<T, is_polymorphic, is_array>;

static_assert(satisfies_my_needs<T>, "Ha! Not satisfied!")

[c++][cppcon 2017] constexpr all the things

constexpr all the things

Reference:
cppcon2017 constexpr all the things
constexpr specifier
Constant expressions
std::variant

digress:
User-defined literals (From c++11 faq)

A literal operator can request to get its (preceding) literal passed ``cooked''
(with the value it would have had if the new suffix hadn't been defined) or ``uncooked'' (as a string).

constexpr complex<double> operator "" i(long double d) // imaginary literal
 {
  return {0,d}; // complex is a literal type
 }
 
std::string operator""s (const char* p, size_t n) // std::string literal
 {
  return string(p,n); // requires free store allocation
 }

To get an ``uncooked'' string, simply request a single const char* argument:

Bignum operator"" x(const char* p)
{
 return Bignum(p);
}

void f(Bignum);
f(1234567890123456789012345678901234567890x);

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.

Suffixes will tend to be short (e.g. s for string, i for imaginary, m for meter, and x for extended),
so different uses could easily clash. Use namespaces to prevent clashes:

namespace Numerics { 
  // ...
  class Bignum { /* ... */ }; 
  namespace literals { 
   operator"" X(char const*); 
  } 
 } 

 using namespace Numerics::literals; 

Benefit of constexpr

• Runtime efficiency
• Clearer code, fewer magic numbers
• Less cross-platform pain

Requirements for compile time types

• constexpr constructor
• std::is_trivially_destructible

constexpr allocator

template <class T, size_t Size>
struct ConstexprAllocator {
    typedef T value_type;
    consstexpr ConstexprAllocator(/*ctor args*/);
    template <class U>
    constexpr ConstexprAllocator(const ConstexprAllocator<U>& other);
    constexpr T* allocate(std::size_t n);
    constexpr void deallocate(T* p, std::size_t n);
    std::array<std::pair<bool, value_type>, Size> data; // bool for free flag
};

Currently any type with a non-trivial destructor cannot be used in constexpr context.
Reason:
    Run-time adjusting this pointer.

Solution to the constexpr destructor problem

struct Container {
    ~Container() {
    // this proposal allows for an empty destructor to be allowed
        if constexpr(something) {
        // do something
        }
    }
};

// OR
struct Container {
    ~Container() {
    // but why not treat it like any other constexpr code?
    // allow it as long as only constexpr allowed actions
    // happen at compile time?
        if (extra_data) {
            delete [] extra_data;
        }
    }
};