STL map[k]=.. Always uses assignment@runtime

The focus is on the value2, of type Trade.

— someMap[key1] = value2; //uses default-ctor if needed. Then Unconditionally invokes Trade::operator=() for assignment! See P344 [[Josuttis]]

Without default-ctor or operator=, then Trade class probably won’t compile with this code.

— someMay.emplace(key1, value2); //uses some ctor, probably the copy-ctor, or the cv-ctor if value2 type is not Trade

Advertisements

move()doesn’t move..who does@@

(Note in this blogpost, when I say mv-ctor i mean move-ctor and move-assignment.)

As explained in other posts in this blog, move() is a compile time cast, no performing a physical “steal” at runtime, so

Q: what c++11 constructs performs a physical steal?
%%A: mv-ctor

  • move() ⇏ steal — std::move() may not trigger a physical steal — If you call myContainer.insert(std::move(myString)) but your custom String class has no mv-ctor, then copy-ctor is picked by compiler .. see P21 [[Josuttis]].
  • steal ⇏ move() — a physical steal may not require std::move() — if you have a naturally occurring rvalue object.
  • steal => mv-ctor

priorityQ: 2 advantages over RBtree#O(1)add #Part2

RBTree O(1) insert is quite common in coding questions.

[1] Contrary to popular belief, RBTree mass insert (including mass-construction) is O(logN) rather than O(1) per node in the general case. However, see link above.

See lecture notes https://courses.cs.washington.edu/courses/cse373/02au/lectures/lecture11l.pdf and SOF post on
https://stackoverflow.com/questions/6147242/heap-vs-binary-search-tree-bst

std::priority_queue phrasebook

Mostly based on [[Josuttis]]

  • #include <queue> // this class template is functionally closer to a regular queue
  • container adapter — based on other containers
    • defaults to vector, but deque fine.
  • random access — base container must provide random access iterator (to support fast sorting)
  • push and pop — both O(logN). https://en.cppreference.com/w/cpp/algorithm/push_heap shows individual insert and delete_max are both logN in worst case
  • make_heap() — linear in worst case, guaranteed:)

std::weak_ptr phrasebook

ALWAYS need to compare with raw ptr + shared_ptr, to understand the usage context, motivations and justifications

http://www.stroustrup.com/C++11FAQ.html#std-weak_ptr is concise.

— Based on the chapter in [[effModernC++]]:

#1 feature — detect dangle

  • use case — a subject that keeps track of its observers who might become dangling pointers
  • use case — objects A and B pointing to each other with ref count … leading to island. Using raw pointers exclusively is possible but requires explicit deletion, as pointed out on P 84 [[Josuttis]]
  • In both use cases, Raw ptr won’t work since dangle becomes unnoticed.
  • Achilles’ heel of the #1 feature — manual “delete” on the raw ptr is beneath the radar of reference counting, and leads to chaos and subversion of ownership control, as illustrated —
#include <iostream>
#include <memory>
using namespace std;

void f1(){
  auto p = new int(55);
  shared_ptr<int> sp(p);
  weak_ptr<int> wp(sp);

  cout<<"expired()? "<<wp.expired()<<endl; // false
  cout<<"deleting from down below\n";
  delete p; // sp.reset();
  cout<<"expired()? "<<wp.expired()<<endl; // still false!
  // at end of this function, shared_ptr would double-delete as the manual delete 
// is beneath the radar of reference counting:(
}
int main(){
  f1();
}

CAS cpu-instruction takes 3 inputs

A CVA interviewer asked me to explain the cmpxch cpu-instruction. I now believe it COMPARES two values (expected^current) and IIF matched, updates the memory location to a “newValue”.

Out of these 3 “inputs”, only the expected and newValue are inputs to the function. The 3rd item “current” is NOT an input parameter to the function, but discovered in the hardware.

See P1018 [[the c++StdLib]] by Josuttis

atomic{int} supports operator+=()

Background — on a machine with lock-free CPU…

My friend Shanyou asked me — with c++11 atomic data types, can we simply say

myAtomicInt ++; //without any mutex

A: Yes according to [[c++StdLib]]

Q: Is there some hidden CAS while-loop therein?
A: Yes I am 99% sure because other threads could be updating the same shared mutable object concurrently on other CPU cores.

Q: is there a CAS while-loop in a basic store/load operation?
A: I don’t think so

##functions(outside big4)using either rvr param or move()

Q: Any function(outside big4) with rvr param?
%%A: Such functions are rare. I don’t know any.
AA: [[effModernC++]] has a few functions taking rvr param, but fairly contrived as I remember.
AA: P544 [[c++primer]] says class methods could use rvr param
* eg: push_back()

 

Q: any function (outside big4) using std::move?

  • [[effModernC++]] has a few functions.
  • P544 [[c++primer]] says rarely needed
  • [[josuttis]] p20

 

Trex QnA IV #std::forward,noexcept

Q: how would a tcp consumer-client know the server process died rather than a quiet server?

Q: how would a tcp producer-server know a client process died? Signal?

Q: What’s perfect forwarding?

Q: std::forward() vs std::move()? See std::move=unconditional-cast #forward=conditional-cast

Q1: in c++03, a myVectorOfTrade.push_back( Trade(22, 0.7) ) uses how many ctor/dtor invocations?
A: regular ctor, copy-ctor, dtor of the temporary

Q1b: how about c++11?
A: regular ctor, mv-ctor, dtor of temporary. See P293…. We assume there’s a Trade mv-ctor and there’a some pointer field in Trade, otherwise the mv-ctor has nothing to steal and is probably same as copy-ctor

Q1c: what about something like emplace_back(22, 0.7)
A: in-place ctor using placement-new. P294 [[eff modern c++]] perfect forwarding eliminates temporaries

https://github.com/tiger40490/repo1/blob/cpp1/cpp1/rvrDemo.cpp is my illustration.

Q: how would “noexcept” improve runtime performance?
AA: P 91 [[effModernC++]] has a short paragraph explaining “noexcept” functions are more compiler-optimizable
AA: P 25 [[c++stdLib]] says noexcept functions don’t require stack unwinding.

Q: please implement a simple Stack class backed by a vector. Implement push(), pop(), top().

 

RVO^move : on return value

Let’s set the stage. A function returns a local Trade object “myTrade” by value. Will RVO kick in or move-semantic kicks in? Not both!

I had lots of confusions about these 2 features.[[effModernC++]] P176 has a long discussion and an advice — do not write std::move() hoping to “help” compiler on a local object being returned from a function

  • If the local object is eligible for RVO then all compilers would elide the copy. Your std::move() would hinder the compiler and back fire
  • if the local object is ineligible for RVO then compiler are required to return an rvalue object, often implicitly using st::move(), so your help is unneeded.
    • Note local object returned by clone is a naturally-occurring temp object.

P23 [[c++stdLib]] gave 2-line answer:

  1. if Trade class has a suitable copy or move ctor, then compiler may choose to “elide the copy”. This was long implemented as RVO optimization in most compilers before c++11. https://github.com/tiger40490/repo1/blob/cpp1/cpp/rvr/moveOnlyType_pbvalue.cpp is my experiment.
  2. otherwise, if Trade class has a move ctor, the myTrade object is robbed

So if condition for RVO is present, then most likely your move-ctor will NOT run.

c++compiler select`move-ctor

This is a __key__ part of understanding move-semantics, seldom quizzed. Let’s set the stage:

  • you overload a traditional insert(Amount const &)  with a move version insert(Amount &&)
    • by the way, Derrick of TrexQuant introduced a 3rd alternative emplace()
  • without explicit std::move, you pass in an argument into insert()
  • (For this example, I want to keep things simple by avoid constructors, but the rules are the same.)

Q1: When would the compiler select the rvr version?

P22 [[c++stdLib]] has a limited outline. Here’s my illustration

  • if I pass in a temporary like insert(originalAmount + 15), then this argument is a rvalue obj so the rvr version is selected
  • if I pass in a regular variable like insert(originalAmount), then this argument is an lvalue obj so the traditional version is selected
  • … See also my dedicated blogpost in c++11overload resolution TYPE means..

After we are clear on Q1, we can look at Q2

Q2: how would std::move help?
A: insert(std::move(originalAmount)); // if we know the object behind originalAmount is no longer needed.

https://github.com/tiger40490/repo1/blob/cpp1/cpp1/rvrDemo.cpp shows when we need to use std::move() and when we don’t need.

c++11 atomic{int}^AtomicInteger.java #Bool can be half-written

The #1 usage of atomic<int> is load() and store(). I will use short form “load/store” or “l/s”.

The #2 usage is CAS.  Interviewers are mostly interested in this usage, though I won’t bother to remember the function names —
* compare_exchange_strong()
* compare_exchange_week()


The CAS usage is same as AtomicInteger.java, but the load/store usage is more like the thread-safety feature of Vector.java. To see the need for load/store, we need to realize the simple “int” type assignment is not atomic [1]:

  • P1012 [[c++ standard library]] shocked me by affirming that without locks, you can read a “half-written Boolean” [1].

To solve this problem, atomic<int> uses internal locks (just like Vector.java) to ensure load() and store() is always atomic.

[1] different from java. https://stackoverflow.com/questions/11459543/should-getters-and-setters-be-synchronized points out that 32-bit int in java is never “half-written”. If you read a shared mutable int in java, you can hit a stale value but never a c++ style half-written value. Therefore, java doesn’t need guarded load()/store() functions on an integer.

Q: are these c++ atomic types lock-free?
A: for load/store — not lock-free. See P 1013
A: for CAS — lock-free CPU instructions are used, if available.

wait()needs while-loop #spurious

Across all languages, I have never seen any exception. You must enclose wait() in a while-loop.

C++11 has a syntactic sugar — wait(myLock, myPredicate), hiding the while loop.

Q: why is spurious wake unavoidable? [[Josuttis]] P1004 has a concise answer:
A: thread library (not operating system) can’t reliably ensure to deliver the notification, so to play safe, the thread library wakes the waiting thread.

— I wrote about java:

Wait() is always awakened by a notification message sent to the monitor object.

Between the notification thread releasing the lock and the waking thread acquiring, a third thread can modify some shared data[1], and the condition you are waiting for disappears as a result.

Therefore the waking thread need to recheck the condition. if() won’t do[2]. while() is required.

If you know there is no 3rd thread messing with the condition, then the waking thread can assume the condition is still intact. However, this design unnecessarily weakens code extensibility and re-usability. It’s fairly easy to put a while() loop around a wait(). No good reason not to do it.

[2] This kind of bug is intermitten.
[1] in a database for example (a crude example)

returning RVR #Josuttis

My rule  of thumb is to avoid a RVR return type, even though Josuttis did NOT forbid it by saying anything like return type should never be rvr.

Instead of an rvr return type, I feel in most practical cases, we can achieve the same result using a nonref return type. I think such a function call usually evaluates to a nameless temp object i.e a naturally-occurring rvalue object.

[[Josuttis]] (i.e. the c++Standard library) P22 explains the rules about returning rval ref.

In particular, it’s a bad idea to return a newly-created stack object by rvr. This object is a nonstatic local and will be wiped out after the function returns.

(It’s equally bad to return this object by l-value reference.)

 

empty throw ^ missing throw before c++11

[[Josuttis]] P25 is concise on this topic, and explains why noexcept is superior.

Background – all exception specs beside these 2 are deprecated in c++11. Only these 2 forms proved useful. Let’s rephrase the question as “Real difference between 2 otherwise identical functions, one with empty throw() the other without throw”.

Short Answer — wrapping the empty-throw function call in try/catch is useless.

Short answer – empty throw means “should throw Nothing. Nothing expected“;
Short answer – missing throw means the opposite — “all exceptions expected

Long answer — suppose you wrap each function call in a try/catch (…) ie catch-all. For the function without throw, every single exception from it will fall into your catch(…). For the empty-throw function, every single exception always, always triggers unexpected(). Your try/catch is ignored by compiler — could be removed during compilation.

Now we are ready to look at a function with throw(A). According the ARM, if at runtime this function throws unlisted exceptions, it’s seen as a serious design fault, so serious that compiler will *disregard* your try/catch — paper over (huge) cracks.

Here’s a best practice from http://www.gotw.ca/publications/mill22.htm — Moral #1: Never write an exception specification. If you follow this advice, then your try/catch will work, ie won’t be stripped off by compiler

My advice — “Either don’t list the exceptions, or adhere to your list. If you bother to list the expected exceptions, then stick to it. Don’t throw anything else. ”

Note unexpected() is called always, always due to an explicit exception-spec i.e. an explicit throw suffix. “Unexpected” means “function author informed compiler to *expect* some exceptions, but something unexpected came out from the function“.

Let’s repeat the message — whenever you notice unexpected() invoked, there’s a function with a broken exception spec — No smoke without fire. No throw suffix then no “unexpected()”.

Further, these 2 conditions always lead to each other —

function has an exception list, but unlisted exceptions generated unexpected() invocation

What about terminate()? It’s somewhat peripheral in the story of exception-spec. I will just describe one of the causes — an expected (i.e. listed) exception is thrown but not caught. Also, unexpected() calls terminate() by default.