8 ms·

I've got an implementation of a stock exchange that uses the LMAX disruptor pattern in C++ https://github.com/sneilan/stock-exchange https://github.com/sneilan/

I've got an implementation of a stock exchange that uses the LMAX disruptor pattern in C++ https://github.com/sneilan/stock-exchange https://github.com/sneilan/stock-exchange And a basic implementation of the LMAX disruptor as a couple C++ files https://github.com/sneilan/lmax-disruptor-tutorial https://github.com/sneilan/lmax-disruptor-tutorial I've been looking to rebuild this in rust however. I reached the point where I implemented my own websocket protocol, authentication system, SSL etc. Then I realized that memory management and dependencies are a lot easier in rust. Especially for a one man software project.

JedMartin 2y ago
It's not easy to get data structures like this right in C++. There are a couple of problems with your implementation of the queue. Memory accesses can be reordered by both the compiler and the CPU, so you should use std::atomic for your producer and consumer positions to get the barriers described in the original LMAX Disruptor paper. In the get method, you're returning a pointer to the element within the queue after bumping the consumer position (which frees the slot for the producer), so it can get overwritten while the user is accessing it. And then your producer and consumer positions will most likely end up in the same cache line, leading to false sharing.
- sneilan1 2y ago
  >> In the get method, you're returning a pointer to the element within the queue after bumping the consumer position (which frees the slot for the producer), so it can get overwritten while the user is accessing it. And then your producer and consumer positions will most likely end up in the same cache line, leading to false sharing. I did not realize this. Thank you so much for pointing this out. I'm going to take a look. >> use std::atomic for your producer Yes, it is hard to get these data structures right. I used Martin Fowler's description of the LMAX algorithm which did not mention atomic. https://martinfowler.com/articles/lmax.html https://martinfowler.com/articles/lmax.html I'll check out the paper.
  - hi_dang_ 2y ago
    I sincerely doubt the big HFT firms use anything of Fowler’s. Their optimizations are down to making their own hardware. LL is very context dependent and Amdahl’s law applies here.
  - 6keZbCECT2uB 2y ago
    Fowler's implementation is written in Java which has a different memory model from C++. To see another example of Java memory model vs a different language, Jon Gjengset ports ConcurrentHashMap to Rust
  - JedMartin 2y ago
    I have absolutely no idea how this works in Java, but in C++, there are a few reasons you need std::atomic here: 1. You need to make sure that modifying the producer/consumer position is actually atomic. This may end up being the same instruction that the compiler would use for modifying a non-atomic variable, but that will depend on your target architecture and the size of the data type. Without std::atomic, it may also generate multiple instructions to implement that load/store or use an instruction which is non-atomic at the CPU level. See [1] for more information. 2. You're using positions for synchronization between the producer and consumer. When incrementing the reader position, you're basically freeing a slot for the producer, which means that you need to make sure all reads happen before you do it. When incrementing the producer position, you're indicating that the slot is ready to be consumed, so you need to make sure that all the stores to that slot happen before that. Things may go wrong here due to reordering by the compiler or by the CPU [2], so you need to instruct both that a certain memory ordering is required here. Reordering by the compiler can be prevented using a compiler-level memory barrier - asm volatile("" ::: "memory"). Depending on your CPU architecture, you may or may not need to add a memory barrier instruction as well to prevent reordering by the CPU at runtime. The good news is that std::atomic does all that for you if you pick the right memory ordering, and by default, it uses the strongest one (sequentially-consistent ordering). I think in this particular case you could relax the constraints a bit and use memory_order_acquire on the consumer side and memory_order_release on the producer side [3]. [1] https://preshing.com/20130618/atomic-vs-non-atomic-operations/ https://preshing.com/20130618/atomic-vs-non-atomic-operation... [2] https://en.wikipedia.org/wiki/Memory_ordering https://en.wikipedia.org/wiki/Memory_ordering [3] https://en.cppreference.com/w/cpp/atomic/memory_order https://en.cppreference.com/w/cpp/atomic/memory_order
fooker 2y ago
You say it's easier in Rust, but you still have a complete C++ implementation and not a Rust one. :)
- deepsun 2y ago
  Linus said he wouldn't start Linux if Unix was ready at that time.
  - pjmlp 2y ago
    Minix....
  - deepsun 2y ago
    Don't know why so many downvotes, probably because I confused Unix with "GNU kernel". Here's the source (Jan 29, 1992): If the GNU kernel had been ready last spring, I'd not have bothered to even start my project: the fact is that it wasn't and still isn't. Linux wins heavily on points of being available now. https://groups.google.com/g/comp.os.minix/c/wlhw16QWltI/m/P8isWhZ8PJ8J https://groups.google.com/g/comp.os.minix/c/wlhw16QWltI/m/P8...
- sneilan1 2y ago
  It took me about a year to build all of this stuff in C++. So I imagine since I've had to learn rust, it will probably take me the same amount of time if I can save time with dependencies.
  - fooker 2y ago
    In my experience, once you know the problem really well, yes you're right. If you are building a complex prototype from scratch, you'll usually spend more time fighting the Rust compiler than trying out alternate design decisions.
    - sneilan1 2y ago
      I do know the problem domain well. My second iteration in rust already almost has an order book implemented. Writing code in rust however is very fun! (At least so far lol)
temporarely 2y ago
fun fact: the original LMAX was designed for and written in Java. https://martinfowler.com/articles/lmax.html https://martinfowler.com/articles/lmax.html
- sneilan1 2y ago
  I think it made sense at the time. From what I understand, you can make Java run as fast as C++ if you're careful with it and use JIT. However, I have never tried such a thing and my source is hearsay from friends who have worked in financial institutions. Then you get added benefit of the Java ecosystem.
  - nine_k 2y ago
    From my hearsay, you absolutely can, given two things: fewer pointer-chasing data structures, and, most crucially, fewer or no allocations. Pre-allocate arrays of things you need, run ring buffers on them if you have to use a varying number of things. A fun but practical approach which I again heard (second-hand) to be used, is just drowning your code in physical RAM, and switch the GC completely off. Have enough RAM to run a trading day, then reboot. The cost is trivial, compared to spending engineering hours on different approaches.
    - sneilan1 2y ago
      So literally remove as much allocation as possible and then reboot each day. That makes a lot of sense to me!
    - ramchip 2y ago
      I worked in trading and we did the first one, in C++. We'd load all the instruments (stocks etc.) on startup to preallocate the "universe", and use ring buffers as queues. Instruments don't change during trading hours so restarting daily to pick up the new data is enough. I saw a Java team do the second one in an order router (a system that connects to various exchanges and routes+translates orders for each exchange's requirements), and they wrote an interesting retrospective doc where they basically said it wasn't worth it - it caused a lot of trouble without giving a significant edge in performance. YMMV! That was around 2012.
worstspotgain 2y ago
I briefly looked over your stock exchange code: - For memory management, consider switching to std::shared_ptr. It won't slow anything down and will put that concern to rest entirely. - For sockets, there are FOSS libraries that will outperform your code and save you a ton of headaches dealing with caveats and annoyances. For example, your looping through FD_ISSET is slower than e.g. epoll or kqueue. - For dependencies, C++ is definitely wilder than other languages. Dependencies are even harder to find than they are to manage. There's a lot of prospective library code, some of it hidden in little forgotten folds of the Internet. Finding it is basically a skill unto itself, one that can pay off handsomely.
- sneilan1 2y ago
  I did not know std::shared_ptr would not slow things down. I've learned something new today! :) Yes, I agree, epoll is a lot better than FD_ISSET. Maybe I can keep moving with my C++ code but do people still trust C++ projects anymore? My ideal use case is a hobbyist who wants a toy stock exchange to run directly in AWS. I felt that C++ has a lot of bad publicity and if I want anyone to trust/try my code I would have to rebuild it in rust.
  - shaklee3 2y ago
    That's not true. It does slow things down because it has an atomic access. How slow depends on the platform. unique_ptr does not slow things down.
  - worstspotgain 2y ago
    Here's how to maximize shared_ptr performance: - In function signatures, use const references: foo(const std::shared_ptr<bar> &p). This will prevent unnecessary bumps of the refcount. - If you have an inner loop copying a lot of pointers around, you can dereference the shared_ptr's to raw pointers. This is 100% safe provided that the shared_ptr continues to exist in the meantime. I would consider this an optimization and an edge case, though. I would say people trust C++ projects at least as much as any other professional language - more so if you prove that you know what you're doing.
pclmulqdq 2y ago
The LMAX disruptor is a great data structure when you have threads bound to cores and most/all of them are uncontended. It has some terrible pathologies at the tails if you aren't using this pattern. Threads getting descheduled at bad times can really hurt. SPSC ring buffers are going to be hard to beat for the system you are thinking of, and you can likely also implement work stealing using good old locks if you need it.
jstimpfle 2y ago
Instead of this: T *item = &this->shared_mem_region ->entities[this->shared_mem_region->consumer_position]; this->shared_mem_region->consumer_position++; this->shared_mem_region->consumer_position %= this->slots; you can do this. uint64_t mask = slot_count - 1; // all 1's in binary item = &slots[ pos & mask ]; pos ++; i.e. you can replace a division / modulo with a bitwise AND, saving a bit of computation. This requires that the size of the ringbuffer is a power of two. What's more, you get to use sequence numbers over the full range of e.g. uint64_t. Wraparound is automatic. You can easily subtract two sequence numbers, this will work without a problem even accounting for wraparound. And you won't have to deal with stupid problems like having to leave one empty slot in the buffer because you would otherwise not be able to discern a full buffer from an empty one. Naturally, you'll still want to be careful that the window of "live" sequence numbers never exceeds the size of your ringbuffer "window".
stargrazer 2y ago
I'll have to take a look at the code. Maybe I can integrate it into https://github.com/rburkholder/trade-frame https://github.com/rburkholder/trade-frame

JedMartin 2y ago

It's not easy to get data structures like this right in C++. There are a couple of problems with your implementation of the queue. Memory accesses can be reordered by both the compiler and the CPU, so you should use std::atomic for your producer and consumer positions to get the barriers described in the original LMAX Disruptor paper. In the get method, you're returning a pointer to the element within the queue after bumping the consumer position (which frees the slot for the producer), so it can get overwritten while the user is accessing it. And then your producer and consumer positions will most likely end up in the same cache line, leading to false sharing.

sneilan1 2y ago
>> In the get method, you're returning a pointer to the element within the queue after bumping the consumer position (which frees the slot for the producer), so it can get overwritten while the user is accessing it. And then your producer and consumer positions will most likely end up in the same cache line, leading to false sharing. I did not realize this. Thank you so much for pointing this out. I'm going to take a look. >> use std::atomic for your producer Yes, it is hard to get these data structures right. I used Martin Fowler's description of the LMAX algorithm which did not mention atomic. https://martinfowler.com/articles/lmax.html https://martinfowler.com/articles/lmax.html I'll check out the paper.
- hi_dang_ 2y ago
  I sincerely doubt the big HFT firms use anything of Fowler’s. Their optimizations are down to making their own hardware. LL is very context dependent and Amdahl’s law applies here.
- 6keZbCECT2uB 2y ago
  Fowler's implementation is written in Java which has a different memory model from C++. To see another example of Java memory model vs a different language, Jon Gjengset ports ConcurrentHashMap to Rust
- JedMartin 2y ago
  I have absolutely no idea how this works in Java, but in C++, there are a few reasons you need std::atomic here: 1. You need to make sure that modifying the producer/consumer position is actually atomic. This may end up being the same instruction that the compiler would use for modifying a non-atomic variable, but that will depend on your target architecture and the size of the data type. Without std::atomic, it may also generate multiple instructions to implement that load/store or use an instruction which is non-atomic at the CPU level. See [1] for more information. 2. You're using positions for synchronization between the producer and consumer. When incrementing the reader position, you're basically freeing a slot for the producer, which means that you need to make sure all reads happen before you do it. When incrementing the producer position, you're indicating that the slot is ready to be consumed, so you need to make sure that all the stores to that slot happen before that. Things may go wrong here due to reordering by the compiler or by the CPU [2], so you need to instruct both that a certain memory ordering is required here. Reordering by the compiler can be prevented using a compiler-level memory barrier - asm volatile("" ::: "memory"). Depending on your CPU architecture, you may or may not need to add a memory barrier instruction as well to prevent reordering by the CPU at runtime. The good news is that std::atomic does all that for you if you pick the right memory ordering, and by default, it uses the strongest one (sequentially-consistent ordering). I think in this particular case you could relax the constraints a bit and use memory_order_acquire on the consumer side and memory_order_release on the producer side [3]. [1] https://preshing.com/20130618/atomic-vs-non-atomic-operations/ https://preshing.com/20130618/atomic-vs-non-atomic-operation... [2] https://en.wikipedia.org/wiki/Memory_ordering https://en.wikipedia.org/wiki/Memory_ordering [3] https://en.cppreference.com/w/cpp/atomic/memory_order https://en.cppreference.com/w/cpp/atomic/memory_order

fooker 2y ago

You say it's easier in Rust, but you still have a complete C++ implementation and not a Rust one. :)

deepsun 2y ago
Linus said he wouldn't start Linux if Unix was ready at that time.
- pjmlp 2y ago
  Minix....
- deepsun 2y ago
  Don't know why so many downvotes, probably because I confused Unix with "GNU kernel". Here's the source (Jan 29, 1992): If the GNU kernel had been ready last spring, I'd not have bothered to even start my project: the fact is that it wasn't and still isn't. Linux wins heavily on points of being available now. https://groups.google.com/g/comp.os.minix/c/wlhw16QWltI/m/P8isWhZ8PJ8J https://groups.google.com/g/comp.os.minix/c/wlhw16QWltI/m/P8...
sneilan1 2y ago
It took me about a year to build all of this stuff in C++. So I imagine since I've had to learn rust, it will probably take me the same amount of time if I can save time with dependencies.
- fooker 2y ago
  In my experience, once you know the problem really well, yes you're right. If you are building a complex prototype from scratch, you'll usually spend more time fighting the Rust compiler than trying out alternate design decisions.
  - sneilan1 2y ago
    I do know the problem domain well. My second iteration in rust already almost has an order book implemented. Writing code in rust however is very fun! (At least so far lol)

temporarely 2y ago

fun fact: the original LMAX was designed for and written in Java. https://martinfowler.com/articles/lmax.html https://martinfowler.com/articles/lmax.html

sneilan1 2y ago
I think it made sense at the time. From what I understand, you can make Java run as fast as C++ if you're careful with it and use JIT. However, I have never tried such a thing and my source is hearsay from friends who have worked in financial institutions. Then you get added benefit of the Java ecosystem.
- nine_k 2y ago
  From my hearsay, you absolutely can, given two things: fewer pointer-chasing data structures, and, most crucially, fewer or no allocations. Pre-allocate arrays of things you need, run ring buffers on them if you have to use a varying number of things. A fun but practical approach which I again heard (second-hand) to be used, is just drowning your code in physical RAM, and switch the GC completely off. Have enough RAM to run a trading day, then reboot. The cost is trivial, compared to spending engineering hours on different approaches.
  - sneilan1 2y ago
    So literally remove as much allocation as possible and then reboot each day. That makes a lot of sense to me!
  - ramchip 2y ago
    I worked in trading and we did the first one, in C++. We'd load all the instruments (stocks etc.) on startup to preallocate the "universe", and use ring buffers as queues. Instruments don't change during trading hours so restarting daily to pick up the new data is enough. I saw a Java team do the second one in an order router (a system that connects to various exchanges and routes+translates orders for each exchange's requirements), and they wrote an interesting retrospective doc where they basically said it wasn't worth it - it caused a lot of trouble without giving a significant edge in performance. YMMV! That was around 2012.

worstspotgain 2y ago

I briefly looked over your stock exchange code: - For memory management, consider switching to std::shared_ptr. It won't slow anything down and will put that concern to rest entirely. - For sockets, there are FOSS libraries that will outperform your code and save you a ton of headaches dealing with caveats and annoyances. For example, your looping through FD_ISSET is slower than e.g. epoll or kqueue. - For dependencies, C++ is definitely wilder than other languages. Dependencies are even harder to find than they are to manage. There's a lot of prospective library code, some of it hidden in little forgotten folds of the Internet. Finding it is basically a skill unto itself, one that can pay off handsomely.

sneilan1 2y ago
I did not know std::shared_ptr would not slow things down. I've learned something new today! :) Yes, I agree, epoll is a lot better than FD_ISSET. Maybe I can keep moving with my C++ code but do people still trust C++ projects anymore? My ideal use case is a hobbyist who wants a toy stock exchange to run directly in AWS. I felt that C++ has a lot of bad publicity and if I want anyone to trust/try my code I would have to rebuild it in rust.
- shaklee3 2y ago
  That's not true. It does slow things down because it has an atomic access. How slow depends on the platform. unique_ptr does not slow things down.
- worstspotgain 2y ago
  Here's how to maximize shared_ptr performance: - In function signatures, use const references: foo(const std::shared_ptr<bar> &p). This will prevent unnecessary bumps of the refcount. - If you have an inner loop copying a lot of pointers around, you can dereference the shared_ptr's to raw pointers. This is 100% safe provided that the shared_ptr continues to exist in the meantime. I would consider this an optimization and an edge case, though. I would say people trust C++ projects at least as much as any other professional language - more so if you prove that you know what you're doing.

pclmulqdq 2y ago

The LMAX disruptor is a great data structure when you have threads bound to cores and most/all of them are uncontended. It has some terrible pathologies at the tails if you aren't using this pattern. Threads getting descheduled at bad times can really hurt. SPSC ring buffers are going to be hard to beat for the system you are thinking of, and you can likely also implement work stealing using good old locks if you need it.

jstimpfle 2y ago

Instead of this: T *item = &this->shared_mem_region ->entities[this->shared_mem_region->consumer_position]; this->shared_mem_region->consumer_position++; this->shared_mem_region->consumer_position %= this->slots; you can do this. uint64_t mask = slot_count - 1; // all 1's in binary item = &slots[ pos & mask ]; pos ++; i.e. you can replace a division / modulo with a bitwise AND, saving a bit of computation. This requires that the size of the ringbuffer is a power of two. What's more, you get to use sequence numbers over the full range of e.g. uint64_t. Wraparound is automatic. You can easily subtract two sequence numbers, this will work without a problem even accounting for wraparound. And you won't have to deal with stupid problems like having to leave one empty slot in the buffer because you would otherwise not be able to discern a full buffer from an empty one. Naturally, you'll still want to be careful that the window of "live" sequence numbers never exceeds the size of your ringbuffer "window".

stargrazer 2y ago

I'll have to take a look at the code. Maybe I can integrate it into https://github.com/rburkholder/trade-frame https://github.com/rburkholder/trade-frame