Comment by pjmlp | Hacker News Reader

Comment by pjmlp | Hacker News Reader

Basically Java, .NET and C++, with heavy focus on C++.

Being able to write allocation free algorithms, even on GC languages, lock free data structures and good knowledge of all multi-core programming paradigms and distributed computing.

Here are some talks that will give you a small overview into that world,

CppCon 2017: Carl Cook “When a Microsecond Is an Eternity: High Performance Trading Systems in C++”

https://www.youtube.com/watch?v=NH1Tta7purM

Core C++ 2019 :: Nimrod Sapir :: High Frequency Trading and Ultra Low Latency development techniques

https://www.youtube.com/watch?v=_0aU8S-hFQI

Open source Java HFT code from Chronicle Software, https://github.com/OpenHFT

"Writing and Testing High-Frequency Trading Engines", from Cliff Click

https://www.youtube.com/watch?v=iINk7x44MmM

However in these domains every ms counts, even how long cables are, so also expect Verilog, VHDL, and plenty of custom made algorithms running directly on hardware.

"A Low-Latency Library in FPGA Hardware for High-Frequency Trading"

https://www.youtube.com/watch?v=nXFcM1pGOIE

You can get an overview of the typical expectations here, https://www.efinancialcareers.com/

> allocation free algorithms

Do you have any good sources for information about this concept? I'm having trouble understanding how a algorithm could produce useful work without allocating anything.

An algorithm might be: Take an array of integers as input and return their sum. Returning or adding integers does not require allocating memory.

I presume you mean allocating new memory. You could sum an array and keep track of state/store cumulative sum in the existing array i.e. in-place algorithmic approaches: https://en.m.wikipedia.org/wiki/In-place_algorithm

You still have to have memory and use it though, somewhere.

Yes of course. If the algorithm operates on existing allocations, then it doesn't allocate any memory. Similarly the algorithm might operate on a fixed set of integers, which would not require allocations at all, even in Java.

I used to write Java code which didn't have any objects, just byte arrays. It would never call GC and ran lightning fast.

Is there any particular reason you were using Java then? Seems like you could get the same effect with much more suitable languages.

Tooling, productivity, developer pool.

Usually these are very niche use cases that can be packed into a special purpose library.

Check the openHFT repository from my original post.

The general thinking is that 99% of code at even an HFT doesn’t have to look that funny, so it might make sense to write funny looking java for the 1% that does so you don’t have to fragment your codebase and talent pool.

Never mind algo. I write decent size firmware every once in a while and the whole thing is allocation free.

Where can i find openHFT

OpenHFT is actually known as "Chronicle" now. Chronicle used to refer to a specific library under the OpenHFT umbrella, but a few years ago it was all rebranded to be Chronicle.

https://chronicle.software/

The goal is to prevent garbage collection from happening during fast path execution. So the program doesn't need to be literally allocation free, just free of heap allocations during the steady state of the program. So heap allocations during the initialization phase are okay, as are stack allocations at any time. And the no heap allocations during steady state isn't as bad as it sounds, as using an object pool that has preallocated objects in it is usually a reasonable replacement.

Not an expert by any means but another way to look at "allocation free" algorithms is by looking at them as "statically allocated".

They don't allocate any new memory but they do perform operations on an input and write it to an output. At least in the embedded world this is how this is often done. Considering the overlap between embedded software and HFT, I'd imagine most of these algorithms are going to be something along the lines of "Take in a massive but fixed size block of read only data and output a fixed size result." You can have allocated memory but it needs to be allocated at startup and be able to be consistently reused without need for reallocation.

If you want super low latency, the last thing you want is a memory allocator blocking in the middle of your highly optimised algorithm. Instead you allocate everything ahead of time and just reuse the memory over and over again.

Exactly this. It's annoying but also not as intractable as it sounds. NASA has a similar requirement for mission critical software operating under strict constraints.

Here's a good one by Fowler. They were trying to saturate a data channel with many simultaneous writers and didn't want locking or allocation. They ended up using a static ring buffer.

https://martinfowler.com/articles/lmax.html

Startup/initialization performance generally doesn't matter because that can be done outside of trading hours, so allocation is fine there; the important thing is performance after that.

You use the stack or pre-allocate memory and work with that budget. You can also use custom allocators.

You can learn Rust to get a good general understanding of implementing everything without allocations. The knowledge later transfers to other languages (though you'll miss the guarantees that Rust provides).

Thanks for sharing all this

Reply on news.ycombinator.com