6 ms·

This article uses inheritance in C++ to ensure the types line-up, but I have really taken a shine to algebraic data types for my firm's data feed handlers. Her

This article uses inheritance in C++ to ensure the types line-up, but I have really taken a shine to algebraic data types for my firm's data feed handlers. Here is an example in C++11 that implements a market-data spec line-for-line. #pragma pack(push,1) struct Quote { char symbol[16]; uint16_t bid; uint32_t bidsize; uint16_t ask uint32_t asksize; }; static_assert(sizeof(Quote) == 28, "Quote size wrong"); struct Trade { char symbol[16]; uint16_t price; uint32_t size; }; static_assert(sizeof(Trade) == 22, "Trade size wrong"); struct Data { enum class DataType : char { kTrade = 't', kQuote = 'q' }; uint64_t sequence_number; DataType data_type; union { Quote quote; Trade trade; }; }; #pragma pack(pop) Now because I've disabled padding in the structs, the types will map directly to the proper byte locations as specified by the data vendor. There is no need for me to manipulate bytes! And I can get away with a single cast: Data* data = reinterpret_cast<Data*>(raw_buffer); switch (data->data_type) { case Data::DataType::kTrade: { Trade& trade = data->trade; std::cout << trade.symbol << ' ' << trade.price << ' ' << trade.size << std::endl; break; } case Data::DataType::kQuote: { Quote& quote = data->quote; std::cout << quote.symbol << ' ' << quote.bid << ' ' << quote.ask << std::endl; } default: std::cerr << "Unknown message type: " << static_cast<char>(data->datatype) << std::endl; } So now the code resembles a match statement in OCaml, but will actually compile directly onto the underlying bytes. No data marshaling or anything like that.

lukego 13y ago
That's how I write LuaJIT code for networking and device drivers too. Very neat.
mlvljr 13y ago
What if your bytes are 16 bit on a given platform? ;)
fmap 13y ago
If I remember correctly there was even a special clause in the C standard definition of union types which allows you to write: struct A { Data header; ... } struct B { Data header; ... } union AB { Data header; A a; B b } and then access the header field in AB. If this is syntactically the first field in each of the constituent records the result is well-defined. This is a great solution if you need to map to a specific wire format. If you do not have that constraint and have code which uses algebraic data types a lot you should probably switch to OCaml or Haskell. There are specific optimizations to work with complex matches and for representing algebraic types in a compact and efficient way. In C++ the compiler has to work with reinterpret_casts and cannot change the representation of your data types (much). Doing the optimizations by hand is possible, but chances are that a simple-minded OCaml prototype will already perform reasonably well.
com2kid 13y ago
This is incredibly common in embedded programming. Lots of times you'll have some binary packet come over the wire, the first field is a packet type specifier, you can then just cast the rest of your byte buffer to the proper type. It is very unfortunate that C (and until recently C++) did not have a way to specify the size of enums. Basically this has resulted in crappy #defines being used for far too many years. I always called what you did above "tagged types". A number of type systems actually work like that under the covers, objects get a type ID, and then a lookup function figures out what that type ID maps to.
- jevinskie 13y ago
  I agree, this typed enum in C++11 made a MachO manipulation library much nicer.
- _pmf_ 13y ago
  > It is very unfortunate that C (and until recently C++) did not have a way to specify the size of enums. It had compiler specific switches to set the size of all enums globally, which helped exactly nobody.
- qznc 13y ago
  The more common term is "tagged union". http://en.wikipedia.org/wiki/Tagged_union http://en.wikipedia.org/wiki/Tagged_union
10098 13y ago
My previous job involved dealing with financial data feeds, can confirm. We used that trick all the time.
greatsuccess 13y ago
Its clever but it doesnt scale to writing systems. Its just a hack.
- com2kid 13y ago
  Hmm? I disagree. I have built very large systems using exactly this technique. As I mentioned in a comment above, lots of on the wire binary protocols start with a type identifier byte (or word). You then have a wonderful switch statement based off of that. Heck I had an entire inter processor communication system running based on what was essentially this very idea. The switch actually had two layers, your first byte gave you a subsystem to jump to and the second byte was the command within that subsystem. You sent data down the wire connecting the two processors together (a UART connection in this case), read straight into a buffer, and just pop right into a switch statement. The main disadvantage is everything is set at compile time, but for a lot of uses that is a-ok.
- deleted 13y ago
  [deleted]
laureny 13y ago
> static_assert(sizeof(Quote) == 28, "Quote size wrong"); A good reminder that trying to "let the types do the work" in C++ is an oxymoron. If you're so keen on algebraic data types, there are languages much better suited to that than C++.
- vinkelhake 13y ago
  > If you're so keen on algebraic data types, there are languages much better suited to that than C++. Variants of this comment are often seen. For any given feature, there's going to be a language that shines in that particular area. However, choice of language rarely comes down to a specific feature. There's usually a multitude of aspects that needs to be considered - some of them aren't even technical.
- axman6 13y ago
  That seems like an orthogonal issue to me. The assert is to ensure that the data type matches some external requirement; a quote is a structure that as 28 bytes long, and if something changes to make a Quote not 28 bytes long, you'll be told. If it weren't there, the algebraic data stuff would still work fine. Edit: I say this as someone whose primary language is Haskell
- pjmlp 13y ago
  > If you're so keen on algebraic data types, there are languages much better suited to that than C++. Yes, you are quite right. However it only works when one works alone. Usually the choice of a language is driven by what the customer requires as technology, what the team members are capable of using or willing to learn, finally what the boss allows.
pbsd 13y ago
This is a neat trick, but it will segfault in architectures where alignment is enforced (like MIPS, ARM, etc) if the input buffer is not suitably aligned. One relatively cheap way to sidestep this is to memcpy into a stack-allocated struct: Data data; memcpy(&data, raw_buffer, sizeof data); switch(data.data_type) // ...
- signa11 13y ago
  well, there are 2 other options available: one is to use "--pointer_alignment=1" so that all accesses via the pointer are treated as unaligned OR use "--no_unaligned_access" flag to tell the compiler to not knowingly generate unaligned access
TorKlingberg 13y ago
Just make sure your systems native endianness is the same as in the raw buffer.
cpwright 13y ago
To make it even better, you can declare classes that are exactly the size of your primitive type, and do things like endianness conversion for you. I will often even make functions that convert, e.g., a bid into a specific price type. Having all of the numerical quantities in your trading system strongly typed makes working on it much easier. The strong type system that enables this, without sacrificing any runtime speed is my favorite part about C++.
judk 13y ago
That looks like an implementation of algebraic data types, written in a language that doesn't support them. "Union" ,"reinterpret_cast" -- I hope that's well tested, since the type system won't help you there!

lukego 13y ago

That's how I write LuaJIT code for networking and device drivers too. Very neat.

mlvljr 13y ago

What if your bytes are 16 bit on a given platform? ;)

fmap 13y ago

If I remember correctly there was even a special clause in the C standard definition of union types which allows you to write: struct A { Data header; ... } struct B { Data header; ... } union AB { Data header; A a; B b } and then access the header field in AB. If this is syntactically the first field in each of the constituent records the result is well-defined. This is a great solution if you need to map to a specific wire format. If you do not have that constraint and have code which uses algebraic data types a lot you should probably switch to OCaml or Haskell. There are specific optimizations to work with complex matches and for representing algebraic types in a compact and efficient way. In C++ the compiler has to work with reinterpret_casts and cannot change the representation of your data types (much). Doing the optimizations by hand is possible, but chances are that a simple-minded OCaml prototype will already perform reasonably well.

com2kid 13y ago

This is incredibly common in embedded programming. Lots of times you'll have some binary packet come over the wire, the first field is a packet type specifier, you can then just cast the rest of your byte buffer to the proper type. It is very unfortunate that C (and until recently C++) did not have a way to specify the size of enums. Basically this has resulted in crappy #defines being used for far too many years. I always called what you did above "tagged types". A number of type systems actually work like that under the covers, objects get a type ID, and then a lookup function figures out what that type ID maps to.

jevinskie 13y ago
I agree, this typed enum in C++11 made a MachO manipulation library much nicer.
_pmf_ 13y ago
> It is very unfortunate that C (and until recently C++) did not have a way to specify the size of enums. It had compiler specific switches to set the size of all enums globally, which helped exactly nobody.
qznc 13y ago
The more common term is "tagged union". http://en.wikipedia.org/wiki/Tagged_union http://en.wikipedia.org/wiki/Tagged_union

10098 13y ago

My previous job involved dealing with financial data feeds, can confirm. We used that trick all the time.

greatsuccess 13y ago

Its clever but it doesnt scale to writing systems. Its just a hack.

com2kid 13y ago
Hmm? I disagree. I have built very large systems using exactly this technique. As I mentioned in a comment above, lots of on the wire binary protocols start with a type identifier byte (or word). You then have a wonderful switch statement based off of that. Heck I had an entire inter processor communication system running based on what was essentially this very idea. The switch actually had two layers, your first byte gave you a subsystem to jump to and the second byte was the command within that subsystem. You sent data down the wire connecting the two processors together (a UART connection in this case), read straight into a buffer, and just pop right into a switch statement. The main disadvantage is everything is set at compile time, but for a lot of uses that is a-ok.
deleted 13y ago
[deleted]

laureny 13y ago

> static_assert(sizeof(Quote) == 28, "Quote size wrong"); A good reminder that trying to "let the types do the work" in C++ is an oxymoron. If you're so keen on algebraic data types, there are languages much better suited to that than C++.

vinkelhake 13y ago
> If you're so keen on algebraic data types, there are languages much better suited to that than C++. Variants of this comment are often seen. For any given feature, there's going to be a language that shines in that particular area. However, choice of language rarely comes down to a specific feature. There's usually a multitude of aspects that needs to be considered - some of them aren't even technical.
axman6 13y ago
That seems like an orthogonal issue to me. The assert is to ensure that the data type matches some external requirement; a quote is a structure that as 28 bytes long, and if something changes to make a Quote not 28 bytes long, you'll be told. If it weren't there, the algebraic data stuff would still work fine. Edit: I say this as someone whose primary language is Haskell
pjmlp 13y ago
> If you're so keen on algebraic data types, there are languages much better suited to that than C++. Yes, you are quite right. However it only works when one works alone. Usually the choice of a language is driven by what the customer requires as technology, what the team members are capable of using or willing to learn, finally what the boss allows.

pbsd 13y ago

This is a neat trick, but it will segfault in architectures where alignment is enforced (like MIPS, ARM, etc) if the input buffer is not suitably aligned. One relatively cheap way to sidestep this is to memcpy into a stack-allocated struct: Data data; memcpy(&data, raw_buffer, sizeof data); switch(data.data_type) // ...

signa11 13y ago
well, there are 2 other options available: one is to use "--pointer_alignment=1" so that all accesses via the pointer are treated as unaligned OR use "--no_unaligned_access" flag to tell the compiler to not knowingly generate unaligned access

TorKlingberg 13y ago

Just make sure your systems native endianness is the same as in the raw buffer.

cpwright 13y ago

To make it even better, you can declare classes that are exactly the size of your primitive type, and do things like endianness conversion for you. I will often even make functions that convert, e.g., a bid into a specific price type. Having all of the numerical quantities in your trading system strongly typed makes working on it much easier. The strong type system that enables this, without sacrificing any runtime speed is my favorite part about C++.

judk 13y ago

That looks like an implementation of algebraic data types, written in a language that doesn't support them. "Union" ,"reinterpret_cast" -- I hope that's well tested, since the type system won't help you there!