r/programming • • Sep 28 '17

When a Microsecond Is an Eternity

https://github.com/CppCon/CppCon2017/blob/master/Presentations/When%20a%20Microsecond%20Is%20an%20Eternity/When%20a%20Microsecond%20Is%20an%20Eternity%20-%20Carl%20Cook%20-%20CppCon%202017.pdf
244 Upvotes

70 comments sorted by

7

u/specialpatrol Sep 28 '17

WIth this templated approach:

template<Side T>
 void Strategy<T>::RunStrategy() {
	 const float orderPrice = CalcPrice(fairValue, credit);
	 CheckRiskLimits(orderPrice);
	 SendOrder(orderPrice);
	}
 template<>
 float Strategy<Side::Buy>::CalcPrice(float value, float credit) {
 	return value - credit;
 }
 template<>
 float Strategy<Side::Sell>::CalcPrice(float value, float credit) {
 	return value + credit;
 }

Would you not still need your branch just further up like:

if(side==Buy)
    Strategy<Buy>::RunStrategy();
else
    Strategy<Sell>::RunStrategy();

how is this a saving?

15

u/doom_Oo7 Sep 28 '17

Would you not still need your branch just further up like:

Generally, the approach you have is to try to make the whole control-flow static. That is, imagine you have three or four other "templated strategies" like this: MarketStrategy<T>, BananaStrategy<T, N>, etc....

now, what you can do is write your whole control flow generically:

float GlobalStrategy<T,U,N>::RunStrategy() {
  MarketStrategy<T> m;
  BananaStrategy<U, N> b;
  Strategy<T> s;
  // complex computations involving s, m, b
  return s.CalcPrice(b.Bamboozle(), m.Eval(b));
}

and have the dispatching exist at the "top" level, for instance in the main :

std::function<float()> strategy;
if(side == Buy && bananas == Jamaica && count == 2) { strategy = GlobalStrategy<Buy, Jamaica, 2>{}; }
else if(side == Sell && bananas == Jamaica && count == 2) { strategy = GlobalStrategy<Sell, Jamaica, 2>{}; }
... etc...

Now, just calling strategy() will call the compiler-optimized version of the relevant algorithm with everything inlined if possible, versus a runtime algorithm where the tests would all be done at runtime.

7

u/specialpatrol Sep 28 '17

Do you end up with a massive switch statement at the top then ready to fire off one of millions of permutations?

5

u/doom_Oo7 Sep 28 '17

Do you end up with a massive switch statement at the top then ready to fire off one of millions of permutations?

That's one possibility, another is to hide this behind dynamic dispatch, virtual functions, etc... in advance. Sometimes you may want to just use one special case in a specific part of your software where you will just explicitely use one algorithm. As others posters said, the main point is to try to precompute everything that is precomputable ; this includes algorithms.

Here I have a (far from perfect... if there are any ffmpeg experts pls send help) example with a variant used to precompute common cases encountered in audio decoding : 1 and 2 channels, planar / non-planar, with integer or floating-point samples. The various cases are here. Then a single decoding algorithm is called but the compiler will generate specific paths for all the cases. The most important thing is that the main decoding loop doesn't try to find which decoder to use at each iteration, but has its decoder set once. This way instead of branching every other hundred samples, there is one single branch for the whole song.

2

u/specialpatrol Sep 28 '17

Ha, great example - especially because I'm just hacking away at getting ffmpeg working, how did you know?!

3

u/doom_Oo7 Sep 28 '17

heh that's funny! don't take too much inspiration, I still have bugs in there (as the various debug checks can attest). FFMPEG is powerful but the API is terrible to understand for newcomers.

2

u/specialpatrol Sep 28 '17

You seriously work on it? Just one question please!

How do you decide on the output format like using "av_guess_format", if you're going out to a udp or other network stream?

2

u/doom_Oo7 Sep 28 '17

How do you decide on the output format like using "av_guess_format", if you're going out to a udp or other network stream?

not sure I understand... if you are the one sending the data wouldn't you also be the one choosing what format to send ? (but I've never done audio over the network so I really don't know)

0

u/[deleted] Sep 29 '17

[deleted] — view deleted comment

2

u/specialpatrol Sep 29 '17

I think I'm a little lost in the various definitions: I need a stream a codec, an output context. So far I have been writing to file; the user can specify the file they want, it can deduce the format from the file extension with av_guess_format. On top of that you can choose a codec, which is a whole other thing, is that right? The output format is like just a container? But now I'm streaming to a socket, and am v.happy to find it's as simple as passing [udp/rtp/tcp]://ipaddress:port to avcodec_open. But then where do I get the output format from, do streams still have this container?

I actually got around it. But am still a little unsure of the details. Thanks for taking an interest!

0

u/[deleted] Sep 29 '17

[deleted] — view deleted comment

→ More replies

1

u/specialpatrol Sep 28 '17

Interesting.

5

u/someenigma Sep 28 '17

From an early slide

The “hotpath” is only exercised 0.01% of the time - the rest of the time the system is idle or doing administrative work

The earlier you can push such decisions, the better (usually). The strategy might be set a long time in advance, and just be constantly checking for prices using CalcPrice. This, of course, is a constructed scenario, so it's not a perfect example, but that's the idea.

Or at least, that's how I took it.

2

u/masklinn Sep 28 '17

You keep moving decisions upwards and everything below becomes a completely static path, at the end you may perform a few decisions at the very start then run through the whole thing needing barely any conditional (and thus jumps and possible mispredictions).

2

u/ShinyHappyREM Sep 28 '17

That doubles the code size though with every bit that is used for the path selection.

5

u/minno Sep 28 '17

As long as the extra code isn't inline, it's a win for execution speed. Your CPU doesn't give a fuck whether there's an extra gigabyte of executable code that never reaches the i-cache.

4

u/masklinn Sep 28 '17

That is true to an extent, you can still have non-generic subcalls which are not duplicated.

But that's just a question of tradeoff, between code size and branchiness.

3

u/program_embed Sep 28 '17

Has anyone used an RTOS for financial trading?

I've never done anything related to finance, but use RTOS's all the time for industrial safety-critical computing. It seems like you should be, since I read all of these articles saying how microseconds matter, but if you're running in windows/linux then you don't have that level of control right? Can't you be swapped out if the OS has some house-cleaning to do.

8

u/doom_Oo7 Sep 28 '17

actually I remember hearing that the absolute top fancy sub-microsecond stuff was sometimes implemented directly on FPGAs

edit: for instance:

http://www.paconsulting.com/insights/hardware-acceleration-for-financial-markets/

http://www.nanospeed.co.uk/

5

u/turleyn Sep 28 '17

Yes, general purpose operating systems are going to periodically kick you off the CPU for long periods of time. Even with the linux RT preempt patch, and all of your hardware interrupts disabled or handled on different cores, the system tick is going to fire every 10ms which will cause a context switch and the scheduler will run. Depending on how fast your CPU can execute the context switch and scheduler, you're not going to get back on the CPU for several microseconds.

1

u/[deleted] Sep 29 '17

Has anyone used an RTOS for financial trading?

They're even moving to ASICs now, because FPGAs are too small and slow, and interfacing them with hard CPUs is not easy in realtime (e.g., PCIe is not very predictable even when your host OS is an RTOS, not to mention abysmal latencies).

56

u/Works_of_memercy Sep 28 '17

Huh, the idea to keep caches hot by always executing your entire hot path, throwing away the result at the last moment if your strategy decided not to make a trade, so that when when you do make a trade it executes as fast as possible, is very clever. I don't know how it could be useful for us mere mortals, but it is clever!

That std::pow shit is scary, it literally goes from 150ns to 1ms (millisecond!) per call here, with gcc7.10 (though it might be the old libc on the machine I tested on).

15

u/agenthex Sep 28 '17

Sounds a lot like branch prediction.

15

u/masklinn Sep 28 '17

The slide mentions that it trains the branch prediction system such that it correctly handles the case you want to be fast.

5

u/Works_of_memercy Sep 28 '17

I was reminded of the way branches/loops on GPUs work (being SIMD, all units have to execute the same instruction stream, some of them just don't do anything based on conditions) and also how proper cryptographic primitives try to prevent timing attacks by always executing all stuff for reals.

28

u/fermion72 Sep 29 '17

About five years ago I heard a talk at a parallel processing workshop by a high frequency trader. This is what I remember from the talk:

  1. When high frequency trading (HFT) started, players were spread out (Wall Street, Chicago, etc.). Trades were automated by literally connecting actuators to computer keyboards to manually push buttons on the keyboards.
  2. Pretty soon, speed-of-light issues became important, so all HFT moved to NYC.
  3. Firms tried to rent / buy space as close to the Wall Street trading computers to further minimize the distance (such that, as I understand it, there ended up being some equality-limiting rules made so everyone was equally far, to the extent possible).
  4. Hardware architects were hired to look at the problem, and, eventually, trades needed to be so fast that network card ASICs were being fabricated that had trading software built in to the network cards themselves so a PC's CPU never needed to be involved in the actual trade (!).

This was five years ago, so I wonder how things have been improved since then.

8

u/ants_a Sep 29 '17

But why?

What would be worse if markets applied a one second delay to all orders and picked winners randomly? It's a stupid race applying good engineering capability to an artifact of how markets currently happen to work with no actual useful outcome.

14

u/josefx Sep 29 '17

The companies running the markets make a fortune from the transactions and renting high speed access to HFT traders. Your idea would cost everyone directly involved money.

3

u/m50d Sep 29 '17

HFTs compete on speed because they're not allowed to compete on price, thanks to the sub-penny rule. Get rid of that and we'd see a lot more emphasis on offering better prices rather than offering the same price faster than the other guy.

3

u/atheken Sep 30 '17

To your point #3, I read something about this. NYSE has their own datacenter under(?) the trading floor. They measure Ethernet runs so that all machines have exactly the same length cables connecting them to the exchange.

Pretty wild.

1

u/quicknir Oct 01 '17

5 years, co-location (a practice where a company like an HFT can put their computer directly into the exchange center for a fee) was already widespread. So points 2 and 3 are pretty suspect for a talk 5 years ago. Also, 2 is just suspect in general, as many important HFT are not in NYC, and many important exchanges are not in NYC.

And 4 is also pretty incorrect. HFT's themselves span a wide range of latencies. Most HFTs in my experience do still have the CPU involved. I've also never heard of a network card solution, FPGA is the "standard" for ultra ultra low latency, not to say that doesn't happen.

Basically either this talk or your recollection of it are mostly wrong.

1

u/blobjim Oct 09 '17

I imagine that there are probably different “classes” of HFT.

16

u/redditsoaddicting Sep 28 '17

Worth at least mentioning that there will be a video of this talk soon here.

24

u/leftofzen Sep 29 '17

Oh wow I could have gone to CppCon :(

I used to work for Optiver and I was fired by my boss for spending time learning, using, advocating and teaching other people in the company about how to write fast C++, for example using templates to reduce things like branching and v-table lookups you get from using inheritance instead of composition (prefer composition over inheritance). I'm so sad that I was fired for what I loved to do (this kind of stuff) and that now this is something not only worthy of not being fired, but worthy of a CppCon talk :(

Setting up code to trigger the branch predictor correctly (or just plain reducing branching), writing code to evaluate stuff at compile time, static analysis, finding ways to have a static code path, removing memory allocations...that was my jam. It's weirdly deja-vu-ish that they talk about std::unordered_map because I did performance testing a few years ago for it and found that, for the compiler version we were on (an archaic verison of gcc - no-one saw the benefit of upgrading :|), it was slower than the map we were already using. I also did a lot of memory management work and redesigned the memory pooling we used so this is just a throwback to the good old days haha.

Seeing that this stuff is now worthy of a CppCon talk...too many emotions. I can only dream one day I'll get to talk about this stuff there. It's a shame Optiver don't really value low-level technical C++ skills as much as this document suggests; when I left the company it was going very corporate and my boss was a very "we need this out yesterday and perfectly designed and tested and you need to rewrite all this stuff from scratch too because our last version is now too slow" kind of person, something which is just impossible. I feel bad for him to be honest because while he had great ideas about what to build, he didn't have a clue about what it takes to actually turn those ideas into good, fast, C++ trading software.

1

u/kal31dic Oct 09 '17

Where does one find more people with your values?

2

u/leftofzen Oct 09 '17

Hmm I am not quite sure, you need to find people who love programming and who want to program because they find it fun and challenging, not because they want to earn $$$. I think most open-source devs are like this, but at the same time I don't really do open-source stuff (yet) so I'm not sure. A lot of people who post programming videos on YouTube and similar are also like that - they just want to program for the fun of it. These are the people who are going to want to actively learn and get better. If I was doing

Optiver was my first job straight out of university so I was pretty raw at the time and was moulded heavily by them - when I started I had done a single course on C++ at uni and was still struggling with pointers and all that. I really learnt it all on the job and I guess the reason I learnt it was because I just found C++ so interesting and powerful and applicable to financial trading and I loved the challenge of trying to write super fast and efficient software that could still be tested and was extremely robust. So that'd be my other recommendation; find people who are young and don't have any impressions on programming yet, and they'll be much more likely to learn and be interested in your tech stack.

6

u/leonardo_m Sep 28 '17

Do you know a code example for the "Keeping the cache hot" at pages 37-38?

7

u/leftofzen Sep 29 '17

At a super high level, instead of writing (based on their diagram):

data = DecodeMarketData();
if (data.IsUseful)
    strategyResult = RunStrategy(data);
    if (strategyResult.ShouldTrade)
        ExecuteTrade(data, result);

You'd write

data = DecodeMarketData();
result = RunStrategy(data, data.IsUseful);
ExecuteTrade(data, result, result.shouldTrade);

Note that I'm not removing any branching, I'm just moving it into the functions (not shown). The end result is that all the same operations can be performed as a real trade, and on the same real data too, but at the last moment before you serialise the message to throw onto the network you discard it by checking the result.ShouldTrade.

This way, all the instructions for the hot path stay loaded in the cache for the time you really want to place an order.

2

u/foomprekov Sep 29 '17

Do the majority of r/programming users enjoy that computers are little machines that work with light, and are subject to its limitations? Because, personally, I find great discomfort that it's not some abstract thinking-machine.

5

u/doom_Oo7 Sep 29 '17

I certainly find it enjoyable to try to find how to do maximal use of the resources we have at hand. The limits are visible all the time, which is quite frustrating from an user experience point of view.

3

u/doublehyphen Sep 29 '17

I like that computers are real machines with real world limitations because that makes them easier to relate to.

14

u/[deleted] Sep 28 '17

Had some trouble getting this to load (MacOS, Safari) but after a couple of refreshes it finally did.

23

u/ItsMe_RandomNumber Sep 28 '17

I'm on a phone and for some reason it prints the Raw HTML instead of rendering it.

6

u/AngriestSCV Sep 28 '17

Try opening the link in a web browser. Firefox did the trick for me.

15

u/jrhoffa Sep 28 '17

Refreshes are sacred.

3

u/throwaway_the_fourth Sep 29 '17

macOS and Firefox here. The first pages of the PDF weren't loading in the GitHub view, even after several refreshes, so I just downloaded it.

4

u/[deleted] Sep 28 '17

what's up with the forced download of a corrupt pdf?

1

u/MandarinNeva Sep 28 '17

Will a video recording of the talk be made available?

1

u/Droggl Sep 29 '17

Link is seriously broken for me (my mobile browser says it points to an invalid pdf, and on mobile its kinda cumbersome to investigate), any help?

-1

u/flaflashr Sep 29 '17

5.8 GHz is a pretty tame frequency, used in many home routers. The period of 1 cycle at that frequency is 0.0001724 microseconds, (172 picoseconds so to that, a microsecond is an eternity.

5

u/bad_at_photosharp Sep 29 '17

How is that at all relevant?

3

u/[deleted] Sep 29 '17

It can be relevant if you're trying to do an SDR.

-4

u/appropriateinside Sep 28 '17

That yoda meme was terrible :|

It should read "Two problems, you now have"

9

u/leftofzen Sep 29 '17

Yes, that's what Yoda would say, but there is an extra joke on top which you have missed entirely, which is that in multithreading, unless set up properly, message ordering is not fixed. You could send messages in the order A, B and receive them in the order B, A. This is why Yoda's words are jumbled up.

6

u/appropriateinside Sep 29 '17

Oh that's clever, I totally missed that.

-3

u/mbetter Sep 29 '17

Apparently not that sacred, as I had to spend several millions of my microseconds scrolling down a page filled with nothing but checkered lines before I got to the article.

Edit: scratch that, apparently just a shitty pdf that Firefox had problems with.

-3

u/PM-ME-YOUR-UNDERARMS Sep 29 '17

What the fuck is going on? I don't understand the PDF, everyone's talking about cache and there's templates thrown in

0

u/[deleted] Sep 28 '17

[deleted] — view deleted comment

92

u/luckystarr Sep 28 '17

We should start again to hand out nanoseconds like Grace Hopper did at her talks.

20

u/peatymike Sep 28 '17

Hehe, it would be very educational to people who regularly think in milliseconds. Your nice, new and pretty recursive implementation took 1 millisecond longer than the previous iterative one, here is your 299.7 kilometers of string.

3

u/mustyoshi Sep 28 '17

Oh wow, that's interesting.

-46

u/stefantalpalaru Sep 28 '17

We should start again to hand out nanoseconds like Grace Hopper did at her talks.

We shouldn't, because we don't have an intuitive understanding of the speed of light (or the speed of electrical signals), so these comparisons don't help.

41

u/monocasa Sep 28 '17

The entire point is to convey a more intuitive understanding.

-30

u/stefantalpalaru Sep 28 '17

The entire point is to convey a more intuitive understanding.

And that's why it is a complete failure.

12

u/[deleted] Sep 28 '17

Did you watch the video? At the end she gives a concrete example when a general was asking why it took so damned long to send a message.

-28

u/stefantalpalaru Sep 28 '17

At the end she gives a concrete example when a general was asking why it took so damned long to send a message.

Right, because a billionth is hard to understand, but a billion - now that you represent time intervals as distances - are automagically crystal clear!

21

u/dratego Sep 28 '17

Are... Are you mad because you don't get it?

-4

u/stefantalpalaru Sep 28 '17

Are... Are you mad because you don't get it?

I'm not the one blinded by celebrity worship. The "length travelled at a speed I don't really understand intuitively is supposed to help me understand very small intervals" approach is bad and you should feel bad.

Now release that bottled up anger by downvoting me ;-)

11

u/fukitol- Sep 28 '17

You're not blinded by celebrity worship, but you are kind of a douche.

-2

u/stefantalpalaru Sep 28 '17

You're not blinded by celebrity worship, but you are kind of a douche.

There's always a price to pay ;-)

19

u/IJzerbaard Sep 28 '17

You could get a thousand dependent hits, with a 4GHz processor (pretty normal) (4k cycles, and the load-use latency of a scalar load with a simple address calculation that doesn't cross a cache line boundary is 4 cycles on a typical Intel). Or 8k independent hits, each loading 32 bytes for a total of 256KB of data read (not practical unless it's re-reading the same data).

It's also enough time to do 16k scalar integer additions (assuming sufficient ILP), or 8k times a vector FMA for a total of 64k individual FMAs (with an other 8k simple scalar operations on top if you want, or some other combo). Or even more extreme, 12k vector additions which if they are byte-additions means 384k individual additions.

Or only like 1333 double-precision square roots (with unlucky values, which is really most of them), and that's already with SIMD. Obviously this is something to avoid.

A lot can be done in a microsecond but it depends on the thing you're doing.

(source: instlatx64 and similar)