thread^process: lesser-known differences #IV

Popular IV question. Largely a QQ question.  Some may consider it zbs.

To the kernel, there are man similarities between the “thread” construct vs the “process” construct. In fact, a (non-kernel) thread is often referenced as a LightWeightProcess in many kernels such as Solaris and Linux.

  • context switching — is faster between threads than between processes. In linux, context switching between kernel-threads is even faster.
  • creation — some thread libraries can create threads without the kernel knowing. No such thing for a process.
  • socket — 2 threads in a process can access the same socket; two processes usually can’t access the same socket, unless … parent-child. See post on fork()
  • memory — thread AA can access all heap objects, and even Thread BB’s stack objects via pointers. Two processes can’t share these, except via shared memory.
  • a non-kernel thread can never exist without an owner process. In contrast, every process always has a parent process which could be long gone.

 

Advertisements

y FIX needs session seqNo over TCP seqNo #reset

My friend Alan said … Suppose your FIX process crashed or lost power, reloads (from disk) the last sequence received and reconnects (resetting tcp seq#). It would then receive a live seq # higher than expected. CME documentation states:

… a given system, upon detecting a higher than expected message sequence number from its counterparty, requests a range of ordered messages resent from the counterparty.

Major difference from TCP sequence number — FIX has no Ack. See Ack in FIX^TCP

— Sequence number reset policy:

After a logout, sequence numbers is supposed to reset to 1, but if connection is terminated ‘non-gracefully’ sequence numbers will continue when the session is restored. In fact a lot of service providers (eg: Trax) never reset sequence numbers during the day. There are also some, who reset sequence numbers once per week, regardless of logout.

ValueType default ctor needed in std::map[]

Gotcha — Suppose you define a custom Value type for your std::map and you call mymap[key] = Value(…). There’s an implicit call to the no-arg ctor of Value class!

If you don’t have a no-arg ctor, then avoid operator[](). Use insert(make_pair()) and find(key) methods.

Paradox — for both unordered_map and map, a lookup HIT also requires a no-arg ctro to be available. Reason is,

  • since your code uses map operator[], compiler will “see” the template member function operator[]. This function explicitly calls the ctor within a if-block.
    • If you have any lookup miss, this ctor is called at run time
    • If you have no lookup miss, this ctor is never called at run time
    • compiler doesn’t know if lookup miss/hit may happen in the future, so both branches are compiled into a.out
  • If your source code doesn’t use operator[], then at compile time, the template function operator[] is not included in a.out, so you don’t need the default ctor.

 

conflation: design question

I have hit this same question twice — Q: in a streaming price feed, you get IBM prices in the queue but you don’t want consumer thread AA to use “outdated” prices. Consumer BB needs a full history of the prices.

I see two conflicting requirements by the interviewer. I will point out to the interviewer this conflict.

I see two channels — in-band + out-of-band needed.

  1. in-band only — if full tick history is important, then the consumers have to /process/ every tick, even if outdated. We can have dedicated systems just to record ticks, with latency. For example, Rebus receives every tick, saves it and sends it out without conflation.
  2. dual-band — If your algo engine needs to catch opportunities at minimal latency, then it can’t afford to care about history. It must ignore history. I will focus on this requirement.
  3. in-band only — Combining the two, if your super-algo-engine needs to analyze tick-by-tick history and also react to the opportunities, then the “producer” thread alone has to do all work till order transmission, but I don’t know if it can be fast enough. In general, the fastest data processing system is single-threaded without queues and minimal interaction with other data stores. Since the producer thread is also the consumer thread for the same message, there’s no conflation. Every tick is consumed! I am not sure about the scalability of this synchronous design. FIFO Queue implies latency. Anyway, I will not talk further about this stringent “combo” requirement.

https://tabbforum.com/opinions/managing-6-million-messages-per-second?print_preview=true&single=true says “Many firms mitigate the data they consume through the use of simple time conflation. These firms throw data on the floor based solely on the time that data arrived.”

In the Wells interview, I proposed a two-channel design. The producer simply updates a “notice board” with latest prices for each of 999 tickers. Registered consumers get notified out-of-band to re-read the notice board[1], on some messaging thread. Async design has a latency. I don’t know how tolerable that is. I feel async and MOM are popular and tolerable in algo trading. I should check my book [[all about HFT]]…

In-band only — However, the HSBC manager (Brian?) seems to imply that for minimum latency, the socket reader thread must run the algo all the way and send order out to exchange in one big function.

Out-of-band only — two market-leading investment bank gateways actually publish periodic updates regardless how many raw input messages hit it. Not event-driven and not monitoring every tick!

  • Lehman eq options real time vol publisher
  • BofA Stirt Sprite publishes short-term yield curves on the G10 currencies.

[1] The notification should not contain price numbers. Doing so defeats conflation and brings us back to a FIFO design.

no overflow]TCP slow receiver #non-blocking sender

Q: Does TCP receiver ever overflow due to a fast sender?

A: See http://www.mathcs.emory.edu/~cheung/Courses/455/Syllabus/7-transport/flow-control.html

A: should not. When the receiver buffer is full, the receiver sends AdvertizedWindowSize to informs the sender. If sender app ignores it and continues to send, then sent data will remain in the send buffer and not sent over the wire. Soon the send buffer will fill up and send() will block. On a non-blocking TCP socket, send() returns with error only when it can’t send a single byte. (UDP is different.)

Non-block send/receive operations either complete the job or returns an error.

Q: Do they ever return with part of the data processed?
A: Yes they return the number of bytes transferred. Partial transfer is considered “completed”.

 

(Revisit) senior manager IV: what they watch out for

Common, non-trivial, perhaps hidden issues in a candidate, ranked:

  • twist and turn and not /candid/ about his past
  • not listening
    • jumping to conclusions
    • assuming too much
    • not waiting for a long-winded interviewer to finish, perhaps interrupting
    • jumping to the defensive, when deliberately provoked
  • desperate for the job and losing his perspective
  • opinionated
  • choosy on projects
  • conceited beyond “cool confidence”
  • —–secondary
  • impulsive answers ^ elusive, guarded answers
    • elusive answers? common
  • bad-mouth past managers
  • lack of humor? common
  • tensed up and not cool and calm, perhaps prone to workplace stress
  • exaggeration about his past? common
  • not articulate enough? common
  • poor eye contact? common

collection-of-abstract-shape: j^c++

In java, this usage pattern is simple and extremely common — Shape interface.

In c++, we need a container of shared_ptr to pure abstract base class 😦

  • pure abstract interface can support MI
  • shared_ptr supports reference counting, in place of garbage collection
  • pointer instead of nonref payload type, to avoid slicing.

This little “case study” illustrates some fundamental differences between java and c++, and showcases some of the key advantages of java.

SFINAE #sizeof#ptr2member as template param

https://jguegant.github.io/blogs/tech/sfinae-introduction.html is relatively simple, concise. Shows how to test T has method1()

https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/SFINAE is shorter and uses the same sizeof trick.

https://en.wikibooks.org/wiki/More_C%2B%2B_Idioms/Member_Detector is another illustration

–all 3 resource above use sizeof and function template (not class template) —

https://github.com/tiger40490/repo1/blob/cpp1/cpp/template/includes useful demo of my own code in production, powering the nyse+nyseAmerican real time market data parsers behind most of the biggest financial data sites.

When the compiler evaluates sizeof, which is a compile-time task, it would try one of the 3 func() overloads and check the winner’s return type[1] . Always exactly one of the 3 overloads can compile.

When T is AddRefreshOrderStruct, the compiler tries 1st overload, where AddRefreshOrderStruct needs a long field, and AddRefreshOrderStruct needs a sendTimeNS field. Pass! So the return type is int.

When T is EmptyStruct, the compiler tries the 1st overload, where EmptyStruct needs a long field … failed:( Only the last overload, the default overload, passes.

[1] the size of the return type is used to initialize the static const field!

The asterisk at end of the func declarations is needed as the func() argument will be NULL pointer. NULL pointer can match a pointer to any type.

std::vector-of-containers: initializer list

Typical example: If you heavily use a vector of map, it’s tempting to use a vector of pointers to maps. The java way.

If you drop the “pointers to”, then when you retrieve the map from the vector, you often get a copy, unless you save the return value in a reference variable

By the way, here’s an initializer for std::map:

vec.push_back(map<int, int>{{32,1}} );

LD_LIBRARY_PATH ^ objdump RUNPATH

This is related to q[cannot open shared object file] abc.so

See https://amir.rachum.com/blog/2016/09/17/shared-libraries/#rpath-and-runpath for the RUNPATH

q(objdump) can inspect the binary file better than q(ldd) does.

q(ldd) shows the final, resolved path of each .so file, but (AFAIK) doesn’t show how it’s resolved. The full steps of resolution is described in http://man7.org/linux/man-pages/man8/ld.so.8.html

q(objdump) can shed some light … in terms of DT_RUNPATH section of the binary file.

blockchain #phrasebook

A blockchain is a peer-to-peer network that timestamps records by hashing them into an ongoing chain of hash-based proof-of-work, forming a record that cannot be changed without redoing the proof-of-work.

In contrast, a distributed ledger is a peer-to-peer network that uses a defined consensus mechanism to prevent modification of an ordered series of time-stamped records. All blockchains are distributed ledgers, but not all distributed ledgers are blockchains.

Keywords:

  • Peer-to-peer — no central single-point-of-failure
  • Immutable — records of past transactions
  • Ever-growing — the chain keeps growing and never shrinks. Is there some capacity issue in terms of storage, backup, search performance?
  • Double-spend — is a common error to be prevented by blockchain

MyType a=7: but conversion constructor is explicit@@

Background:

  explict MyType(int); // would disallow
  MyType a = 77;

http://en.cppreference.com/w/cpp/language/converting_constructor has a solution:

  MyType a = (MyType) 77; // Static cast would invoke the explicit conversion constructor!

In general, most custom types should make conversion constructors explicit to prevent hidden bugs, but smart pointer need an implicit conversion constructor, to support

  SmartPtr myPtr = new int(77);

–A real example from CFM quant code

 FwdCurve::const_iterator iter = find( key ); //non-const itr

 QL_ASSERT( iter != ((FwdCurve * const) this)->end(), "not found" ); // original code probably before "explicit". 

// I had to change it to
 FwdCurve_iterator endItr = ((FwdCurve * const) this)->end();
 QL_ASSERT( iter != FwdCurve_const_iterator(endItr), "not found" ); //call the conversion ctor explicitly

##c++good habits like java q[final]

  • Good habit — internal linkage
    • ‘static’ keyword on file-level static variables
    • anonymous namespace
  • if (container.end() ==itrFromLower_bound) {…}
  • use typedef to improve readability of nested containers
  • typedef — “typedef int FibNum” as source documentation
  • initialize local variables upon declaration.
  • use ‘const/constexpr’ whenever it makes sense. The c++11 constexpr is even better.
  • [c++11] – use ‘override’ or ‘final’ keywords when overriding inherited virtual methods. Compiler will break if there’s nothing to override.

how many degrees(upTo180)btw hr^min hands #Dilip

Dilip had an elegant solution by hand.

3:15 — MH is at 90 degrees; HH is slightly over 90. It’s 1/4 way towards 120 degrees i.e. 90+7.5 degrees. Therefore, the answer is 7.5 degrees

3.10 — MH is at 60 degrees; HH is slightly over 90. It’s 1/6 way towards 120 degrees, i.e. 95 degrees. Answer is 95 – 6 = 35 degrees.

Note the MH is always at an integer degree but HH can be at a xxx.5 degrees.

non-virtual dtor: some random scenarios tested #IV

Background — How important are these scenarios? First off, tech quizzes are extremely important since you are judged just over a few questions. Second, these scenarios pop up by accidents, rather than be design, all the time in real projects. You better learn to deal with a drunken driver while on the road.

Q1: what if Base and Derived dtor both non-virtual and an autoVar is destroyed?
AA: Tested — ~Derived() and then ~Base().  See post on DCBC.

Q2: What if Base dtor is non-virtual but Derived is virtual, and a Derived auto variable is destroyed on the stack?
AA: Same as Q1. For an autoVariable that’s not deleted via a ptr, Derived ctor (virtual or not) runs, followed by Base dtor. Same DCBC

Q3: Base dtor is non-virtual but Derived is virtual. Derived heap pointer is assigned to a B pointer and deleted?
AA: only ~Base runs , in my g++ test, though officially UB.

Q4: Base and Derived are virtual. Derived heap pointer is assigned to a B pointer and deleted?
AA: ~Derived() then ~Base(). DCBC + dynamic dispatch

Note the well-known __undefinedBehavior__ affects delete only, not stack variables or static variables.Note virtual keyword affects pointer variable. Non-ref variables aren’t affected.

The object to destruct is a Derived
~B ~D st? delete heap D via B* or D* test result notes
1 nv nv stack ~D~B DCBC + static dispatch
2 nv virtual stack ~D~B DCBC + static dispatch
3 nv virtual B*  ~B only static dispatch. “virtual” ignored
4 v virtual D*  ~D~B DCBC + dynamic dispatch
5 v implicitly v D*  ditto ditto
struct B{
  ~B(){ cout<<"~B\n";}
};
struct D: public B{
  virtual ~D(){ cout<<"~D\n";}
};
int main(){
  B* myD=new D();
  delete myD;
}

c++advanced IV questions – contributed by real interviewers

http://www.quora.com/Anyone-can-list-good-common-and-advanced-questions-for-testing-C++-STL-skill-during-interview

These authors are real interviewers. They really do care about the topics I mentioned to you Monday night. They are seeking c++ specialists who understand the low level details. They don't care about the high level, architecture, design, picking the right framework or library etc.
Victor

python pseudo constructors4everyday tasks

These Python builtin functions have something in common:

* pseudo [1] constructors — manufacture an object of the specified type
* conversion constructors — converting some input value into an object of the specified type

[1] Actually builtin functions rather than ctor. I guess the fine differences between builtin functions, keywords and operators are not that important at this stage.

P64 [[essential ref]] lists these and more, as “type conversion” functions.

– str()
– dict()
– list() — see py list initialize []^list()
– tuple()
– set()
– int()

– file() — very similar to open()

remain relevant(survival)to your team^global economy#localSys

When we feel job insecurity, we look around and see who’s more secure, more relevant, more current, and more in-demand. We may find some colleagues more relevant to your team or to the company. Maybe they are local system experts. Maybe they have deep expertise in the base vendor product (Tibco, Murex, LotusNotes, WebLogic…). We may want to _specialize_ like them.

Resist!

Job security derives from skill relevance, but relevant to who? The industry, not the local team, which could disappear if entire team becomes obsolete and irrelevant. I have seen people (including myself) specializing in DNS, VB.NET, Swing, Perl, EJB, let alone home-grown systems such as SecDB. These guys are (extremely) relevant but for a limited time only.

Have a long-term perspective — If you want job security through skill relevance, then invest in more permanent skills such as Math, algorithms, data structures, threading, SQL,…

Have a global perspective — Job security is a serious, almost life-and-death issue. You probably should look beyond your local industry. What skills are truly relevant on the global arena? Some skill (say Murex) might be more relevant locally but less globally.

Avoid niche domains unless it helps boost your mainstream skills.

pure virtual with/out implementation #IV

Item 44 in [[EffC++]] offers a summary that basically says

1) a pure virtual means only interface is inherited (since parent provides no implementation)
2) a simple virtual means interface plus a default implementation is inherited
3) a non-virtual means interface plus a mandatory implementation is inherited and subclasses are advised to keep the implementation. C++ actually allows subclass to /deviate/ by redefining and hiding the parent implementation. Java has a cleaner solution in the “final” keyword.

I’d like to add

1b) a pure virtual with an implementation tells the subclass author

      “Inherit this interface. By the way I also offer an implementation upon request, but uninheritable.”

This differs from (2). Both are illustrated in Item 36.

pipe, stream, pesudo file, tcp-socket#xLang

* Java has a family of IO classes;
* c++ has a family of stream classes derived from class ios;
* unix has various file-like things.

“pipe” and “stream” are 2 general terminologies for an input/output destination with sequential[1] access. A file is one subtype of stream. Therefore java and c++ access files using their family of classes above.

[1] c++ gives each sequential stream a get-ptr and a put-ptr.
A named pipe is an entity in the file system….

TCP (not UDP) socket is a stream-oriented protocol. Sockets, either unix domain or TCP (not udp), is also like a pipe/stream. In fact, Unix treats any socket as a file so you can read and write to a it like a file. Perl liberally “confuses” file handles and sockets, just as C uses the same type of file-descriptor-number for files and sockets.

TCP (not UDP) is ordered — if two messages are sent over a connection in sequence, the first message will reach the receiving application first. When data segments arrive in the wrong order, TCP buffers the out-of-order data until all data can be properly re-ordered and delivered to the application.

Python wraps the socket descriptor number in a socket object, but you can still get the underlying descriptor number by mySocket.fileno()–

import socket
mySocket = socket.socket(socket.AF_INET, socket.SOCK_STREAM)
print mySocket.fileno()

const nonref variable: reasonably immutable

Reading the c++ FAQ 18.10, I got the impression that most const variables are ptr or ref.

const nonref primitive is like a java constant or java immutable.

Q: are there const nonref class object? Are they immutable?
A: Yes according to http://www.learncpp.com/cpp-tutorial/810-const-class-objects-and-member-functions/

Once a const class object has been initialized via constructor, any 
attempt to modify the member variables of the object is disallowed, as it 
would violate the constness of the object.

Just like the built-in data types (int, double, char, etc…), class objects 
can be made const by using the const keyword.

Q: can you cast away its constness?
A: very tricky.  See effC++ and the IBM arcitlce.  Short answer is no.

up and down casting non-ref/ref/ptr

Primary usage of dynamic_cast is down-cast
* base/derived class must have vptr, or you get compile-time error
* original and target types must be ptr/ref, or you get compile-time error [1]
* there’s just one object involved, not 2
** That one object must be a complete and full[2] Derived object, otherwise you get runtime (not compile time) failure, indicated by 1) null ptr or 2) exception (during reference down-cast)
*** boost polymorphic_cast adds uniformity by throwing exception for both

[1] static_cast can cast nonref.
[2] static_cast doesn’t incur the overhead to check that

Q: up-casting a nonref??
A: no casting operator required, but you get sliced. qq/ myB = myD; /
A: by the way, no such thing in java, since java doesn’t use “nonref”

Q: down-casting a nonref??
A: impossible in dynamic_cast. “dynamic_cast can be used only with pointers and references to objects”

Q: down-casting a ptr (to a polymorphic object only)?
A: dynamic_cast. May return NULL. java has a similar feature.
A: see also boost polymophic_cast
Q: down-casting a ref (to a polymorphic object only)?
A: dynamic_cast. Never returns NULL. See post on new-and-dynamic_cast-exceptions
A: see also boost polymophic_cast

Q: down-cast a base ptr/ref to a derived object but no vtbl/vptr no virt func?
A: impossible. dynamic_cast won’t compile.

Q: up-cast a ptr?
A: common in c++ and java. everyday virtual function scenario. no operator required.

Q: up-cast a ref?
A: legit but less common than ptr. See post on virtual^redefining

best way2report bad arguments #java

Say you are writing a utility Class1.getByIndex(int arrayIndex). Best way to enforce that arrayIndex is positive?

  • throw an unchecked error and crash the jvm? Recommended by many experts. I guess the downside is tolerable, and there are no better candidates as a standard, universal solution.
    • What if too often? Caller code needs a fix!
  • throw a checked exception and force other programmers to try-catch? I think the overhead grows when you set this as standard practice.
  • return a boolean result? Many methods/constructors can’t.

Ideally, you want to remind other programmers to check their input first, but not force them to put up a useless try-catch.

O(n) sort – radix sort

The principles are relevant to pure-algo interviews.

Q: quicksort is universally usable. How about radix sort?
A: not widely mentioned as a drawback against quicksort. (In contrast, I think Counting-sort is not universally usable…)
A: wikipedia says integers could [1] represent limited-length strings of characters (e.g., names or dates) and specially formatted floating point numbers, radix sort is not limited to integers.

Radix sort is good for parallel computing. See http://www.drdobbs.com/parallel/parallel-in-place-radix-sort-simplified/229000734

Radix-sort Expected running time is faster than quicksort? Could be but….
… but the hidden constant factor in O() is much worse than quicksort.

[1] It’s hard to prove “cannot”