no-bugs

2nd part of the 7-part MECHLOVE Blueprints. All the criticism is extremely welcome (hey, that's the point we're publishing it - to see if it stands).

This is Chapter 4 of the book; Latency vs throughput is discussed in Chapter 1.

> I recommend you stick a bone through your beard, pronounce yourself a performance guru, and make bank. Have fun.

:-) :-) I LOVE when my opponent has to resort to personal insults :-). Leaving aside any sarcastic remarks in this regard:

For Intel's sake I Really Hope that these "profundities" are indeed very well-known to you - and believe it or not, they're very well-known to me too for at least 10 years. However, this is not the point; the point is that there are LOTS of developers out there who do NOT know them - and the OP is intended for them (and not for "performance gurus").

It is actually THIS simple. Eliminating 90% of inefficiency does not really require black magic or "performance gurus" who know exactly how the pipeline of specific CPU works. And this is exactly what I'm arguing for - to educate app-level developers and architects about this low-hanging fruit of 10x+ inefficiencies; I can assure you that it is very far from being universal knowledge in app-level development circles.

> made millions of dollars of revenue... I'm not 100% sure you are well situated to lecture me about the 'real world' because you wrote an academic paper.

So, we're going to discuss millions of dollars instead, sigh... This way Trump should be one of the best programmers in the universe, I guess.

> Typically it will be inherently cheaper than 15-30 cycles - but lost opportunities for optimization may take you to numbers that are insanely higher than that.

And still, even from your own rant it follows that in vast majority of cases the estimate of 15-30 cycles will be well within "order of magnitude" (TBH, I didn't see millions myself, but it should be a really strange corner case).

> If you say 15-30 is the magic number you are creating folklore... We are burdened by folkloric stuff... that result in considerably worse designs.

And not having any such "folklore" results in even worse designs :-( (actually - MUCH worse ones). Using list instead of vector can easily give you 100x penalty for absolutely zero reason (actually, up to 780x was experimentally observed - and that's without swapping). Off-loading 100-cycle chunks (with a thread context switch back after calculating these 100 cycles) to a different thread will never work at least on a x64 (though I remember meeting some folks from Intel - I think they were representing an OpenMP team - who were seriously preaching otherwise, based on utterly silly "how many cores we managed to utilise" metric without realising that the whole thing became _slower_ after they parallelised it ;-( ). And so on and so forth.

Sure, the numbers are very rough. But trying to say that "hey, it is not precise so let's not even try to estimate" - is even worse than that.

> Honestly, it's a lot more complicated than that, and the article itself presents a pretty complicated (and flawed) model. There's no substituting for benchmarks.

Of course, all the models are inherently flawed, and in theory there is no substituting for benchmarks, but going along the lines of "all models out there are flawed, so we don't need ANY model and should do benchmarking instead" leads to the software which is badly architectured to start with (and then no benchmarking will be able heal it without throwing the whole thing away and rewriting it from scratch - and it is not going to happen for most of the projects for many practical reasons).

In other words, if we're already in the vicinity of the optimum (which BTW may happen to be a local one - but this is a very different story) - then benchmarking is the way to go (that is, if those 20% we're chasing, are worth the trouble - and TBH, they really are). However, at the earlier stages being able to realise the order of magnitude without spending time on trying really badly architectured things - is extremely important.

Just one example - no optimisation will save a (non-GPGPU) program which tries to split the load over multiple threads with chunks calculated on each thread (before it relinquishes control to another thread), being 100 cycles or so; I don't need to benchmark it to know that at least in 99.9999% of real-world projects it is a suicide from performance point of view - and this observation directly follows from the diagram.

Or another example - in most of practical cases (actually, pretty much always except for inserts into the middle without iterating through and specialized stuff such as merges), vectors have advantage over lists - and this advantage can easily reach over 100x(!) ( see, for example, https://accu.org/index.php/journals/2268 ). This, once again, follows from the diagram (it is a direct consequence of the main memory read being over 100 cycles and L1 read being 3-4 cycles).

This list of crazily inefficient things (which are still widely used in the industry for no reason) can go on and on. Of course, going into anywhere more detailed analysis than "order of magnitude" indeed doesn't make sense - and it is clearly stated in OP. But for initial estimates when making some architectural decisions (and to avoid premature pessimisation) - such "order of magnitude" analysis can be very useful.

> may be a handful of microoperations merged in with a stream of other instructions.

It may indeed in theory, but most of the time in real-world it won't. And BTW - let's not forget about implicit costs of being unable to inline (which can be huuuuuge). Speaking of the real-world - we've just got our article accepted, presenting supposedly the fastest universal hashing function as of today (in spite of math being more heavy compared to the existing ones) - and the numbers in the OP are consistent with our real-world experiences while we were optimising it (well, within an order of magnitude at least).

> but there is a tone of precision and certainty to them that is a bit deceptive.

OP: "Last but not least, a word of caution: all the estimates here are just indications of the order of magnitude".

> Talking about how much an operation costs is pointless; build things one way, measure that, then make the smallest change possible and measure that.

Sure. The problem is that almost-nobody has time to do it in real-world projects. Which leads to even cruder estimates (such as "virtual function calls costs are negligible, regardless of the number of times they're called") being used - causing lots of crazily inefficient programs. IMO, OP is a reasonable middle ground between an all-out quasi-stationary testing and even worse guesstimates ;-).

> My own benchmarks show costs that are nowhere near the ones cited.

This is heavily dependent on the benchmark. In the OP, there is a ref to an academic research showing these numbers - and from my own real-world experience (NOT artificial benchmarks), the costs of 10K-100K are very usual. From a completely different perspective - there should be reasons why nginx beats Apache performance-wise :-).

> The cost of virtual cals is usually due to missed optimizations and the possibility of misprediction.

Yep (plus one L1 read to get that VMT pointer). And the OP is pretty much consistent with this (at least within declared "indications of the order of magnitude" precision).

However, the address of this C call is calculated, which means that branch prediction (and the cost of potential misprediction) is involved. So additional cost we're talking about, is roughly a cost of L1 read (3-4 clocks by itself) - plus (0-<cost-of-branch-misprediction))

To be clear: I was NOT speaking of the first one :-). As for the second one:

> the architect is the guy that can sketch that reporting engine that will be nurtured and improved by the team,

Yes (in fact, I LOVE this definition ;-)).

> therefore he both codes and shares knowledge.

Not necessarily, and that's the whole point. Initial development (as noted in the article) is one of the exceptions - but "sketching a thing that will be improved" (which I agree with) is VERY different from "working day in and day out on improving it" (which I do NOT like). And this difference is the whole point of the article.

> by creating a God-like super-architect.

Interesting point of view, never thought along these lines. On the other hand, thinking a bit about it - I don't feel that this approach requires a super-architect; what it requires is a DECENT architect (which is a prerequisite for any successful project anyway).

In other words - sure, architect should be one of the best coders - but if he isn't, the project is doomed anyway (and having "the best of the bunch" is always possible - by definition).

> You can code and knowledge share also.

The problem with it is that there are only 24 hours in a day.

> how do you ensure that there are viable career paths for senior people who prefer to focus on code over "knowledge-sharing" kind of activities?

From what I've seen, those Senior and Really Strong people who prefer to code, do NOT even want to become architects (and to move their career beyond Really Really Really Senior Developer - whatever the name this position carries). But this is a different problem (at least in part related to too much responsibility and "comfort zones"), and I don't know of any solution for it...

Added it, THANKS!

THANKS! I've added it (not 100% sure how it would work in practice, but certainly looks interesting).

Statistically - yep. See http://ithare.com/facelift-for-no-bugs/ - only 10 out of 160 said that they don't like the cartoons.

BTW, there is a "very beta" way to turn them off - use http://ithare.com/visitor-settings/ (NB: "No!" option doesn't really work yet)...

> make a more efficient queue by using one-buffer-and-lock-per-thread.

How the reader would block on such a distributed queue when it's empty (without creating one single mutex, which would re-establish the single contention point)? If there is no way to block while waiting for input, it means polling, and polling is a Really Bad Thing...

> If this happens to you, you're doing it wrong.

Except for some corner cases - you're right, probably I should add a note about it...

From what I've seen (YMMV), chances of it happening are MUCH smaller than chances of getting context switch under the lock (with lots of threads running into this lock and having their own context switches), because of spending more time under the lock than it is really necessary (and ANY call, especially kernel call at 300+ clocks, is a LOT of time). Strictly speaking, it needs to be measured, but until that point - I'm keeping my mutex locks as small as possible.

> Additionally, when you unlock a mutex before signalling the condition, another thread may be scheduled in between that may invalidate the condition that was signalled. This may introduce a race condition.

And if you unlock the mutex after signalling the condition, another thread can be still scheduled in between the call to notify() and whatever-notified-thread-which-starts-to-run (and can still invalidate whatever-conditions-it-can-invalidate). There is absolutely no guarantee whatsoever that notified-thread gets to your mutex first (not that it really should matter for correctness in any sane program BTW).

> I signal my condition variables with mutexes locked because it's easier to guarantee correctness that way.

There is no difference in guarantees in practice whether you notify within or after; I'm not even sure that there is any difference in theory (exactly because the thread-which-was-notified is not guaranteed to get mutex first).

> Aren't most mutex/condition variable implementations optimized to avoid this case by deferring the condition signal to the mutex unlock?

Yes, _some_ but not _all_ implementations are doing it; however, as it is not really guaranteed (and actually is a workaround for poorly written programs) - standing recommendation is still to notify after the lock (which can be better, can be the same, but won't be worse than doing it within), see for example http://en.cppreference.com/w/cpp/thread/condition_variable/n...:

"The notifying thread does not need to hold the lock on the same mutex as the one held by the waiting thread(s); in fact doing so is a pessimization, since the notified thread would immediately block again, waiting for the notifying thread to release the lock. However, some implementations (in particular many implementations of pthreads) recognize this situation and avoid this "hurry up and wait" scenario by transferring the waiting thread from the condition variable's queue directly to the queue of the mutex within the notify call, without waking it up."

> Additionally, in the implementation of kill() in the latter examples, there should be notify_all() instead of notify_one().

In MOST cases, it didn't matter (as there was only one blocking thread - the one reading), but yes, there was one case when it was indeed important. Fixed now, THANKS!

Since IPv6 it is mandatory, but it still sucks :-(

BTW, when I've wrote about those "undetected network errors", I've meant those-network-errors-which-arise-in-UNENCRYPTED-packets (as 16-bit UDP checksum is certainly not enough for this purpose). And DTLS etc. take care of packet corruption themselves (actually, they consider it an attack).

> Sorry to nitpick but UDP seems like the wrong protocol for authentication.

While authentication over UDP is indeed a bit more difficult if implementing it yourself, fortunately there is DTLS which is a very official and well-recognised way to implement authentication over UDP (very briefly - DTLS does make a handshake, and it does have a session, but this session operates in a packet-oriented mode which supports reordering and packet loss).

You're right, I forgot about it. But is there a ready-to-use library doing it?

Last thing I've heard was that specifically CurveCP was separated from libsodium into libchlorium, and it is not maintained now.

> Shouldn't you be verifying a MAC before decrypting anyways? Relying on decrypting scrambled data, especially for a bitflip, seems like a bad idea.

Oh, we're going into the realm of MAC-then-encrypt vs Encrypt-then-MAC, which is waaaay out of scope of this book. As it's mentioned in some footnote, under "encryption" I've meant "the whole package, including encryption, integrity authentication, etc." (which is currently routinely done by some kind of AEAD for wired data). I certainly don't want to go into a deep crypto-level discussion of AEAD etc. in a book for app-level developers; what I'm aiming for here, is a simple recipe of "just do it this way, it will work".

> Why not just use TCP for sign-in and key establishment, and get 3-way handshake for free. That eliminates spoofing IPs. From there, just have monitors that determine when you're "under attack" and rate limit by IP address, just like any anti-DDoS does.

But then, for UDP (and you DO need UDP for fast-paced games) you will need your own protected protocol (probably using keys exchanged over TLS-over-TCP). There are many ways to do your own protocol wrong, and only a few to do it right; and if an average app-level developer will try doing it - it is much more often a disaster than not :-(. As a result, I am arguing for using standard security protocols wherever possible (and the anti-DDoS hack described there keeps DTLS security intact, this IS important).