6 ms·
> allocation free algorithms Do you have any good sources for information about this concept? I'm having trouble understanding how a algorithm could produce us
by willcipriano 7y ago
> 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.
- aliceryhl 7y agoAn algorithm might be: Take an array of integers as input and return their sum. Returning or adding integers does not require allocating memory.
- Frost1x 7y agoI 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 https://en.m.wikipedia.org/wiki/In-place_algorithm You still have to have memory and use it though, somewhere.
- aliceryhl 7y agoYes 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.
- phyalow 7y agoI used to write Java code which didn't have any objects, just byte arrays. It would never call GC and ran lightning fast.
- non-entity 7y agoIs there any particular reason you were using Java then? Seems like you could get the same effect with much more suitable languages.
- pjmlp 7y agoTooling, 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.
- pgwhalen 7y agoThe 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.
- FpUser 7y agoNever mind algo. I write decent size firmware every once in a while and the whole thing is allocation free.
- scott00 7y agoThe 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.
- jacoblambda 7y agoNot 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.
- realtalk_sp 7y agoExactly 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.
- imglorp 7y agoHere'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 https://martinfowler.com/articles/lmax.html
- dooglius 7y agoStartup/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.
- deleted 7y ago[deleted]
- zarkov99 7y agoYou use the stack or pre-allocate memory and work with that budget. You can also use custom allocators.
- xiphias2 7y agoYou 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).