bigO CIV: clarify_requirement means..

———- Forwarded message ———
Date: Tue, 9 Jul 2019 at 23:10

Big-O means “worst” case complexity. We need to be doubly sure what “worst” case data look like. (Note it doesn’t mean ridiculously rare data like integer overflow.)

On high-end coding interviews, these “worst data set” frequently shed light on the structure of the original problem, and often point to the correct direction for an efficient solution. (Note a nice-looking solution is not efficient if it exhibits poor time complexity in the face of a worst yet realistic data set. Such a system may not scale well in practice, given its Achilles’ heel.)

If interviewer wants a solution optimized for bigO time complexity, you can waste precious time tackling the wrong problem. The wrong problem is the problem defined by your idea of “worst data set”, but the real worst data set is very different.

Sometimes, the worst data is _subtly_ different but it points to a different algorithm direction. It may point to an iterative solution rather than recursion, for example.

The original interview question may not be that hard iFF we identify the worst data set early on, but sadly, we run out of time.

For some tough problems, the first (sometimes the only) challenge is quickly identifying worst data set. Interviewer always gives you the simple data set, NEVER the worst data set. It’s your job to identify the worst data set… often the key insight into the problem.

It’s no exaggeration to say — identifying the worst data set early or too late can make-or-break your chance at this employer. You may kiss good-bye to this job opportunity exactly because you are too slow to identify the worst data set. I know what this means. Other candidates probably got shot by this arrow on the heel, without knowing what happened.

Time is ticking as soon as the problem is presented to you. If interviewer says time is not a factor… take your time.. we want quality and thought process … I just ignore it. Our speed is always part of assessment. Therefore, a very common failure scenario is —

.. tractable problem but candidate runs out of time after wasting time on preliminaries like using incorrect worst data set to reason about the (wrong) problem.

Advertisements

UseSpinning jvm flag #pthr/kernel/c#

Hi XR,

Around 2011 I once said a java thread waiting for a lock would not keep grabbing the lock…. Wrong! Actually it does keep grabbing for a while. It runs some useless CPU instructions and checks the lock periodically. This is really spin locking inside the JVM.

Spin locking wastes CPU but frequently results in faster application performance (reducing context switches). Therefore, JVM use some policy to decide how long a thread would spin before placing the thread in some kind of “parking lot” (my terminology) so the thread doesn’t’ occupy CPU any more. This spin phase used to be configurable via the boolean UseSpinning JVM flag, but in java7 and beyond, this flag has no effect — JVM always has freedom to use spinning. This is described in [[javaPerf2014]]

Comparison 1 — Dotnet SpinWait() provides exactly the same spinlock feature, as described in https://docs.microsoft.com/en-us/dotnet/standard/threading/spinwait

Comparison 2 — In linux Kernel (not userland), 1) spinlock and 2) counting semaphore are the two locking primitives, as described in Page 164 [[understandingLinuxKernel]]. Both locks block a “grabbing” thread getting into a critical section until another thread leaves it. Similar to my 2011 description, the kernel semaphore remembers all sleeping threads and wakes one of them when the critical section is clear. I think this kernel semaphore is used by the scheduler in the kernel.

Comparison 3 — In linux pthreads (the basis of linux JVM), the locking constructs are implemented using system calls and userland C functions. Pthreads as a userland library probably can’t use the above two kernel constructs directly. Userland C function can implement spinlock, but to implement “parking” I assume (kernel support and) system calls are required. So far I assume the pthreads thread maps to native threads controlled by the kernel. This mapping is now the dominant usage.

The alternative mapping model is green threads, where userland threads are invisible to kernel. Parking has to be implemented in userland.  Nowadays it’s rare to see green threads.

Q: which thread/PID drains NicBuffer→socketBuffer

Too many kernel concepts here. I will use a phrasebook format. I have also separated some independent tips into hardware interrupt handler #phrasebook

  1. Scenario 1 : A single CPU. I start my parser which creates the multicast receiver socket but no data coming. My process (PID 111) gets preempted on timer interrupt. CPU is running unrelated PID 222 when my data wash up on the NIC.
  2. Scenario 2: pid111 is running handleInput() while additional data comes in on the NIC.

Some key points about all scenarios:

  • context switching — There’s context switch to interrupt handler (i-handler). In all scenarios, the running process gets suspended to make way for the interrupt handler function. I-handler’s instruction address gets loaded into the cpu registers and this function starts “driving” the cpu. Traditionally, the handler function would use the suspended process’s existing stack.
    • After the i-handler completes, the suspended “current” process resumes by default. However, the handler may cause another pid333 to be scheduled right away [1 Chapter 4.1].
  • no pid — interrupt handler execution has no pid, though some authors say it runs on behalf of the suspended pid. I feel the suspended pid may be unrelated to the socket (Scenario 2), rather than the socket’s owner process pid111.
  • kernel scheduler — In Scenario 1, pid111 would not get to process the data until it gets in the “driver’s seat” again. However, the interrupt handler could trigger a rescheduling and push pid111 “to the top of the queue” so to speak. [1 Chapter 4.1]
  • top-half — drains the tiny NIC ring-buffer into main memory (presumably socket buffer) as fast as possible [2] as NIC buffer can only hold a few packets — [[linux kernel]] P 629.
  • bottom-half — (i.e. deferrable functions) includes lengthy tasks like copying packets. Deferrable function run in interrupt context [1 Chapter 4.8], under nobody’s pid
  • sleeping — the socket owner pid 111 would be technically “sleeping” in the socket’s wait queue initially. After the data is copied into the socket receive buffer in user space, I think the kernel scheduler would locate pid111 in the socket’s wait queue and make pid111 the cpu-driver. This pid111 would call read() on the socket.
    • wait queue — How the scheduler does it is non-trivial. See [1 Chapter 3.2.4.1]
  • burst — What if there’s a burst of multicast packets? The i-handler would hog or steal the driver’s seat and /drain/ the NIC ring-buffer as fast as possible, and populate the socket receive buffer. When the i-handler takes a break, our handleInput() would chip away at the socket buffer.
    • priority — is given to the NIC’s interrupt handler as NIC buffer is much smaller than socket buffer.
    • UDP could overrun the socket receive buffer; TCP uses transmission control to prevent it.

Q: What if the process scheduler is triggered to run (on timer interrupt) while i-handler is busy draining the NIC?
A: Well, all interrupt handlers can be interrupted, but I would doubt the process scheduler would suspend the NIC interrupt handler.

One friend said the while the i-handler runs on our single-CPU, the executing pid is 1, the kernel process. I doubt it.

[1] [[UnderstandingLinuxKernel, 3rd Edition]]

[2] https://notes.shichao.io/lkd/ch7/#top-halves-versus-bottom-halves

mutex: serialize access to… data or code@@ #kernel

These are 2 ways to look at the basic mutex use case —
DD) you can use a mutex to serialize access to a piece of shared mutable data
CC) you can use a mutex to serialize passage through a code path — the so-called critical section

In the kernel, CC (not DD) is the main concern.

Many people intuitively cling on to the intuitive DD view and visualize the runtime using a mutex to regulate multiple threads’ access to shared Data, as if the mutex is a locker. However, I find CC a more realistic/accurate view.

DD is the “logical” view whereas CC is the physical view.

DD is achieved through CC.

The more low-level you go, the more you take the physical view and speak in terms of critical sections.

DD is more object oriented. For non-OO languages like C, DD is not as natural as in OO language. If a data item is passed by pointer, then any function running on any thread can modify it. It’s not enough to use a mutex on 99% of those functions and have one function access it directly.

In OO languages, that data item would Always be a private field, automatically restricting access to very few methods of the class. Now we understand why encapsulation is essential to threading.

In non-OO languages, it’s less natural to associate a mutex with a piece of data. If the shared data is passed by pointer, then the mutex must also be passed by pointer. The mutex-pointer must accompany the data-pointer.

##Just what are(not) part of Architecture (too-late-to-change)

Dogfight – When you develop a dogfight jet over 30 years, you stick to your initial design. You try to build on the strengths of your design and protect the weaknesses. You don’t suddenly abandon your design and adopt your rival’s design because you would be years behind on that path. Software architecture is similar.

Anyone with a few years experience can specify an architecture in some details, but those decisions are flexible and could be modified later on, so they aren’t make-or-break decisions, though they could waste time.

Q1: what Features define a given architecture? I’m a fellow architect. If you must describe in 10 phrases your system architecture and provide maximum Insight, which 10 aspects would you focus on?

Q2: (another side of the same coin) What technical Decisions must be made early when creating a system from scratch?
Q2b: in other words, what design decisions will be expensive to change later? Why expensive?

Disclaimer — In this context, “later” means somewhere during those pre-UAT phases, not LATE into the release process. Obviously after release any config/DB/code change requires regression test and impact analysis, but that’s not our topic here.

A colleague of mine liked to discuss in terms of layering. In OO architecture, A layer consists of a bunch of similar classes (or interfaces) dedicated to a logically coherent high-level task. 2 interacting layers can exist in the same OS process or (less common but very critical) across processes. Intra-process layering basically means the 2 interacting classes (belonging to 2 layers) have well-defined responsibilities and a well-defined contract between, where one is always a Service-provider (“dependency”) to the service-consumer. Though popular among architects, I’m not sure these are the most important architectural features.

Here are my answers to the question “Is the decision costly to change later in SDLC?”

? anything in the wsdl/schema of a web service? yes if i’m not the only developer of this web service’s clients. A change would need these fellow programmers to change their code and test, test, test
? fundamental data constraints like “if this is positive then that must be non-null”? Yes because other developers would assume that and design code flows accordingly.
? database schema, the ER between a bunch of tables? Yes since it usually requires code change “upstairs”. DB schema is usually a Foundation layer, often designed up front.
? choose a DB vendor? yes if you happen to have truly skillful database developers in the team. They will use proprietary vendor extensions behind the manager’s back when the temptation is too strong. Such non-portable business logic will be expensive to re-implement in another database.
? use MOM or RPC-style communication? yes
? Serialization format? yes. “Later” means implementation effort wasted
? XML or binary or free text format? yes probably
? make a bunch of objects immutable/read-only/const? yes. Adding this feature later can be hard. Look into C++ literature.
? shared vs unshared cache? yes. effort is non-trivial
? What logic to put into SQL vs java/C#? sometimes No. You can change things later on, but usually wasting sizable implementation effort
? Choose programming language? Yes. Implementation effort wasted if switching late in the game.
? make a batch task re-runnable? yes. Adding this feature later on can be hard

? MVC (the highest-level design pattern there is)? well… yes, though you can adjust this design later on
? where to implement authentication, entitlement? Many say yes, but I feel no. Make the damn system work first, then worry about securing it. On fast-paced trading floor, Business usually can tolerate this feature being not so perfect. Business and upper management worry more about ….. You got it — Functionality.

? Which commercial(or free) product to choose? sometimes NO. You can use mysql or activemq and then change to commercial products. In fast projects, We can often delay this decision. Start coding without this particular commercial product.

? make a module thread safe? no, even though adding this feature can be hard
? how many staging tables? no
? choose a decorator/factor/singleton (or any of the classic) design pattern? no. They are usually too  low-level to be among the “10 architectural features”. I don’t know why a lot of architect interview questions hit this area.

what is kernel space (vs userland)

(sound-byte: system calls — kernel space; standard library functions — userland, often wrappers over syscalls)

Executive summary — kernel is special source code written by kernel developers, to run in special kernel mode.

Q: But what distinguish kernel source code from application source code?
A: Kernel functions (like syscall functions) are written with special access to hardware devices. Kernel functions are the Gatekeepers to hardware, just like app developers write DAO class as gatekeepers to a DB.

Q: Real examples of syscall source code?
A: I believe glibc source code includes either syscall source code or kernel source code. I guess some kernel source code modules aren’t in glibc. See P364[[GCC]]
A: kernel32.dll ?
A: tcp/ip is implemented in kernel.
A: I feel device drivers are just like kernel source code, though RAM/CPU tend to be considered the kernel of kernel.

My 2-liner definition of kernel — A kernel can be thought of as a bunch of (perhaps hundreds of) API functions known as “syscalls”. They internally call additional (10,000 to 100,000) internal functions. Together these 2 bodies of source code constitutes a kernel. On an Intel platform, kernel and userland source code both compile to Intel instructions. At the individual instruction level, they are indistinguishable, but looking at the source code, you can tell which is kernel code.

There are really 2 distinct views (2 blind men describing an elephant) of a kernel. Let’s focus on run-time actions —
X) a kernel is seen as special runtime services in the form of syscalls, similiar to guest calls to hotel service desk. I think this is the view of a C developer.
Y) behind-the-scene, secret stream of CPU instructions executed on the CPU, but not invoked by any userland app. Example — scheduler [4]

I don’t think a kernel is “a kind of daemon”. Such a description is misleading. Various “regular” daemons provide services. They call kernel functions to access hardware. If a daemon never interacts with user processes, then maybe it would live in “kernel space”. I guess kernel thread scheduler might be among them.

I feel it’s unwise (but not wrong) to think of kernel as a process. Kernel services are used by processes. I guess it’s possible for a process to live exclusively in “kernel space” and never interact with user processes. http://www.thehackademy.net/madchat/sysadm/kern/kern.bsd/the_freebsd_process_scheduler.pdf describes some kernel processes.

P241 [[Pro .net performance]] describes how something like func3 in kernel32.dll is loaded into a c# application’s code area. This dll and this func3 are treated similar to regular non-kernel libraries. In a unix C++ application, glibc is linked in just like any regular library. See also http://www.win.tue.nl/~aeb/linux/lk/lk-3.html and http://www.win.tue.nl/~aeb/linux/lk/lk-3.html

[4] Scheduler is one example of (Y) that’s so extremely prominent that everyone feels kernel is like a daemon.

The term “kernel space” is misleading — it is not a special part of memory. Things in kspace don’t run under a privileged user.

— call stack view —
Consider a c# P/Invoke function calling into kernel32.dll (some kernel func3). If you were to take a snapshot of an average thread stack, top of the stack would be functions written by app developers; middle of the stack are (standard) library functions; bottom of the stack are — if hardware is busy — unfinished kernel syscalls. Our func3 would be in the last 2 layers.

All stack frames below a kernel API is “kernel space”. These stack frames are internal functions within the kernel_code_base. Beneath all the stack frames is possibly hardware. Hardware is the ultimate low-level.

Look at the bottom-most frame, it might be a syscall. It might be called from java, python, or some code written in assembly. At runtime, we don’t care about the flavor of the source code. The object code loaded into the “text” section of the Process is always a stream of assembly code, perhaps in intel or sparx InstructionSet

ANY process under any user can call kernel API to access hardware. When people say kernel has special privileges, it means kernel codebase is written like your DAO.

object, referent, and reference — intro to weak reference

see also post on pointer.

— physical explanation of the 3 jargons
A regular object (say a String “Hi”) can be the target of many references
* a regular strong reference String s=”Hi”;
* another regular strong reference String ss1=s; // remote control duplicated
* a weak ref WeakReference wr1 = new WeakReference(ss1);
* another wak ref wr2 = new WeakReference(s);

1) First, distinguish a regular object “Hi” from a regular strong reference ss1.
* The object “Hi” is a “cookie” made from a “cookie cutter” (ie a class), with instance and static methods defined for it.
** like all objects, this one is created on the heap. Also, think of it as an onion — see other posts.
** “Hi” is nameless, but with a physical address. The address is crucial to the “pointer” below.

* strong reference ss1 is a “remote control” of type String. See blog post [[an obj ref = a remote control]]
** People don’t say it but ss1 is also a real thingy in memory. It can be duplicated like a remote control. It has a name. It’s smaller than an object. It can be nullified.
** It can’t have methods or fields. But it’s completely different from primitive variables.
** method calls duplicate the remote control as an argument. That’s why java is known for pass-by-value.

2) Next, distinguish a strong reference from a pointer.
* a regular strong reference ss1 wraps a pointer to the object “Hi”, but the pointer has no technical name and we never talk about the pointer inside a strong reference.
** the pointer uses the “address” above to locate the object
** when you duplicate a remote control, you duplicate the pointer. You can then point the old remote control at another object.
** when no pointers point to a given object, it can be garbage collected.

Summary — a pointer points to the Object “Hi”, and a Strong reference named ss1 wraps the pointer. Note among the 3, only the strong ref has a name ss1. The other strong ref s is another real thingy in memory.

3) Now, weak reference. A weakref wr1 wraps a pointer to an obj (ie an onion/cookie), just like a strong ref. In a weak reference (unlike strong reference) the pointer is known as a “referent in the reference”. Note wr1’s referent is not ss1, but the object “Hi” referenced by ss1. That’s why “Hi” is target of 4 pointers (4 reference). This object’s address is duplicated inside all 4 variables (4 references).

“Referent in a reference” is the pointer to object “Hi”. If you “set the referent to null” in wr1, then wr1 doesn’t point to any object in memory.

Unlike strong references, a weak reference is sometimes mentioned like an object, which is misleading.

Q: Is the weak ref wr1 also an object? We explained a strong ref ss1 differs completely from the object “Hi”.

A: Yes and no. you create it with new weakReference(..) but Please don’t treat it like a regular object like “Hi”. In our discussion, an object means a regular object, excluding reference objects. [[Hardcore Java]] page 267 talks about “reference object” and “referenced object” — confusing.
A: java creators like to dress up everything in OO, including basic programming constructs like a thread, a pointer, the VM itself, a function (Method object), or a class (Class object). Don’t overdo it. It’s good to keep some simple things non-OO.

A: functionally, wr1 is comparable to the remote control ss1. Technically, they are rather different

portions@secDB – created by quants, for quants@@

I feel Quants and others around them don’t always point out the real difference between Traders, Coders and Quants aka strategists. In this context we have to.

Once secDB core is built, SecDB is “programmed” in each desk by regular software developers, not  secDB core team. Business end-users are risk managers and traders, majority of whom are probably not trained for or fascinated by Slang or python.

In terms of formal training, regular software developers are trained in engineering; quants in math; traders in investment. (Think of prop trading, to keep things simple.)

However, some quants qualify as software developers. (Actually, most c++ analytic libraries are owned by these part-time developers:-). Some sharp minds in the camp eventually realize 1) the inherent dependency graph in this world, and then rediscover 2) OODB. Put the customized quantitative dependency-graph-aware objects into an OODB and SecDB is born. Grossly oversimplified, but at this juncture we have to swallow that in order to wrap our mind around a monstrous concept, step back and see the big picture. (signal/noise ratio and focus badly needed.)

Another article said secDB “allows Goldman’s sales force and traders to model, value and book a transaction”, confirming that model and valuation are among the first goals of secDB.

Quants create this platform for themselves (ie for quantitative research, back testing, model tuning…), and then persuade developers to adopt. In such a world, quants are the law-makers. Power shifts from traders and IT to quants. In the traditional world, IT resembles the powerful equipment manufacturers of the dotcom era.

Now I feel the creators of SecDB may not be the typical desk quant, risk quant or strategist. He or she might be a quant developer
———–

I guess Quants’ job is to analyze 1) financial instruments and 2) markets, and try to uncover the quantitative “invisible hands”. (In http://bigblog.tanbin.com/2011/11/more-information-you-have-less.html, I question the value of this endeavor.) They _numerically_ analyze real time market data, positions, recent market data (all fast changing), historical data, product data…. Too much data to be digestible by business, so they condense them into mathematical “models” that attempt to explain how these numbers change in relation to each other. Classic example is the term structure and the BS diffusion model. A proven model acquires a life of its own —

– become part of a trading strategy
– sell-side often offer these models as value-added services to hedge funds. I guess they can send trading signals or digested, derived data to hedge funds.
– risk mgr are often the #1 user of these models. Risk mgr and quants validate models by back testing.

OutOfMemory ≠ allocation failure

IBM says —
Q: I am getting an OutOfMemoryError. Does this mean that the Java heap is exhausted?
A: Not necessarily. Sometimes the Java heap has free space but an OutOfMemoryError can occur. The error could occur because of
* out of memory but not due to a call to new()
* Excessive memory allocation in other parts of the application, unrelated to the JVM, if the JVM is just a part of the process, rather than the entire process (JVM through JNI, for instance).

Q: How can I confirm if the OutOfMemoryError was caused by the Java heap becoming exhausted?
A: Run with the -verbosegc option. VerboseGC will show messages such as “Insufficient heap space to satisfy allocation request”

Q: When I see an OutOfMemoryError, does that mean that the Java program will exit?
A: No. My experiments below show you can continue even after new() failed.
    static ArrayList list = new ArrayList();
    public static void main(String[] kkkj) throws InterruptedException {
        byte[] array = null;
        for (;;) {
            Sizeof.printHeapSegments4JDK6();
            out.println(Sizeof.total_ie_Committed() + “\t>  ” + Sizeof.used()
                    + ” <– bytes in use. Trying to new up….");
            try {
                array = new byte[20 * 1000 * 1000];
            } catch (OutOfMemoryError e) {
                StringBuilder stat = Sizeof.printHeapSegments4JDK6();
                System.err.println(stat);
                e.printStackTrace();
            }
            list.add(array);
        }
    }

financial app testing – biz scenario^implementation error

Within the domain of _business_logic_ testing, I feel there are really 2 very different targets/focuses – Serious Scenario (SS) vs Implementation Imperfections (II). This dichotomy cuts through every discussion in financial application testing.

* II is the focus of junit, mock objects, fitnesse, test coverage, Test-driven-development, Assert and most of the techie discussions
* SS is the real meaning of quality assurance (QA) and user acceptance (UA) test on Wall St. In contrast II doesn’t provide assurance — QA or UA.

SS is about real, serious scenario, not the meaningless fake scenarios of II.

When we find out bugs have been released to production, in reality we invariably trace root cause to incomplete SS, and seldom to II. Managers, users, BA, … are concerned with SS only, never II. SS requires business knowledge. I discussed with a developer (Mithun) in a large Deutsche bank application. He pointed out their technique of verifying intermediate data in a workflow SS test. He said II is simply too much effort and little value.

NPE (null pointer exception) is a good example of II tester’s mindset. Good scenario testing can provide good assurance that NPE doesn’t happen in any acceptable scenarios. If a scenario is not within scope and not in the requirement, then in that scenario system behavior is “undefined”. Test coverage is important in II, but if some execution path (NPE-ridden) is never tested in our SS, then that path isn’t important and can be safely left untested in many financial apps. I’m speaking from practical experience.

Regression testing should be done in II testing and (more importantly) SS testing.

SS is almost always integrated testing, so mock objects won’t help.