Hacker News Reader

Comment by willcipriano | Hacker News Reader

> 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.

View on HN

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.

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.

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.

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.

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

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).

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.

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/

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

Reply on news.ycombinator.com