When you need to parse data for downstream processing, the enthusiasm to get the processing outcome quickly might induce you to overlook one interesting nuance of the cost of how it’s parsed.
See this “parse me a u64” function for example:
fn parse_id(bytes: &[u8]) -> Result<u64, ParserError> {
if bytes.len() < 8 {
return Err(ParserError::InputTooShortForU64);
}
let owned = bytes[..8].to_vec();
Ok(u64::from_le_bytes(owned.try_into().map_err(ParserError::InvalidU64)?))
}
It checks the length, takes the right amount of bytes from the slice copying them into a Vec and uses it to parse it as u64. All looks short and safe.
Now let’s examine it more carefully.
For a data type as simple as a number the memory heap should be used or not? What about syscalls?
In Rust, a Vec always uses the heap. That allocation might or, if lucky, might not require a syscall. That would depend on whether the allocator already has a free block or has to ask the OS for more memory which can easily happen under heavy loads.
A lot of applications will not care about this detail but some need to care.
What happens when you care?
Since eight bytes in a buffer are already a u64 and from_le_bytes knows how to read them into a u64 is fair to say the Vec I allocated in that .to_vec() is accidental complexity for getting to the output of that function. A kind of internal complexity to achieve an end. But what if we find ways to not need that? If “making room” for the final result is not required, then we save time, effort runtime cost and code maintenance of that “making room”.
Let’s push design to read in place and see what happens.
We’re already receiving a reference &[u8] of where to read, so the next thing is know how much to read exactly into a u64. This “reading in place” technique is what you’ll hear being called as Zero-Copy because whatever you’re doing for the processing you are already not requiring a copy to start doing it (working on &[u8] is that contract).
These eight bytes still move to the stack for from_le_bytes but we skipped doing anything with the heap.
The strength that Rust has in its contracts (types) is used to produce in a program zero-cost abstractions. So when it reads the right types in data and has all error modes properly modeled and handled, what you get is all that strength in its runtime.
Let’s use abstractions that won’t copy now.
Here is the previous example but in a zero-copy implementation instead:
fn parse_id(bytes: &[u8]) -> Result<u64, ParserError> {
let raw: [u8; 8] = bytes.get(..8)
.ok_or(ParserError::InputTooShortForU64)?
.try_into().map_err(ParserError::InvalidU64)?;
Ok(u64::from_le_bytes(raw))
}
This time we read the bytes in whichever place they already are, validate we can read 8 valid bytes there and use them to infallibly produce a u64.
And what if a type is more complex than a u64?
A longer message is the same technique, repeated over a new contract shaped differently. After all, this reusability is what makes zero-copy a technique.
For example in the command codec I am writing for orderflow, a command is an enum. A limit order carries an account, a client order id and other details. A cancel by order id is two integers. A market order has no price field. The bytes in the buffer are a different width for each of engine command.
/// EngineCommand is a client request to change order state.
/// When a matching engine receives work, it uses this type so the variant is the
/// layout: NewLimit and NewMarket are separate, and New has no engine OrderId.
#[derive(Debug, Copy, Clone, PartialEq, Eq, Hash)]
pub enum EngineCommand {
/// Request to open a limit order.
NewLimit {
account_id: AccountId,
client_order_id: ClientOrderId,
instrument_id: InstrumentId,
side: Side,
price: Price,
quantity: Quantity,
},
/// Request to open a market order.
NewMarket {
account_id: AccountId,
client_order_id: ClientOrderId,
instrument_id: InstrumentId,
side: Side,
quantity: Quantity,
},
/// Request to cancel by engine OrderId.
CancelByOrder { order_id: OrderId },
...
For these commands, a kind byte says which layout I am looking at. Each layout has one length. I check that length, then I read fields into new types. Price is a count of ticks, an i64, quantity is a count of lots, and all of them are intentionally Copy. This makes commands not only very compact but together, they unlock something.
Notice the #[derive(Debug, Copy... in its definition?
Nothing in enum EngineCommand owns a buffer.
Their Copyness unlocks the full enum’s “copyness”.
It’s a very deliberate design choice to enable the engine to parse using the zero-copy technique. Now the processing of commands is done “in place”.
const NEW_LIMIT_LEN: usize = 57;
fn decode_new_limit(payload: &[u8]) -> Result<EngineCommand, DecodeError> {
if payload.len() != NEW_LIMIT_LEN {
return Err(DecodeError::Length);
}
Ok(EngineCommand::NewLimit {
account_id: AccountId::new(read_u64(payload, 8)),
client_order_id: ClientOrderId::new(read_u64(payload, 16)),
instrument_id: InstrumentId::new(read_u64(payload, 24)),
side: decode_side(payload[32])?,
price: Price::new(read_i64(payload, 33)),
quantity: Quantity::new(read_u128(payload, 41)),
})
}
As you can expect, these commands live in an envelope with a sequence number and a kind type that defines how they are read from the stream:
match kind {
Kind::NewLimit => decode_new_limit(payload),
Kind::NewMarket => decode_new_market(payload),
Kind::CancelByOrder => decode_cancel_by_order(payload),
Kind::CancelByClient => decode_cancel_by_client(payload),
Kind::Replace => decode_replace(payload),
}
NewLimit is 57 bytes. CancelByOrder is 16. Everything is determined how is to be read, and that’s guaranteed by the compiler. What’s left is making ingesting commands impossible to add invalid data which you do by handling extensibly each possible failure mode during ingestion.
And for the writes?
Well, we do the same design intent we used in the zero-copy technique but for writing. That is, the encoder writes those same offsets into a buffer the caller already owns. Every variant is a fixed pile of integers with the predictable fit in the data buffer. No intermediate allocations required while writing.
The journal frame and the datagram both hand over the payload region and share one write. Neither path grows a private copy of the command.
This enum is interesting because the variant changes the memory layout but it stays free of the heap because every variant is a fixed pile of integers with the predictable fit in the data buffer.
In the same way these eight bytes were already a number, a limit order is fifty-seven, in known places. The rest is getting them wrapped in an envelop with a sequence number and kind byte that tells me where to look for them safely, consistently and in the right order.
Then the Rust parser’s job is to answer the command from where the data is already sitting and give me these sweet hundreds of millions commands per second the engine can process downstream:
decode_frame/stream/cancel_by_order
time: [4.0990 ns 4.1100 ns 4.1243 ns]
thrpt: [242.46 Melem/s 243.31 Melem/s 243.96 Melem/s]
decode_frame/stream/new_limit
time: [4.1835 ns 4.1934 ns 4.2058 ns]
thrpt: [237.76 Melem/s 238.47 Melem/s 239.03 Melem/s]
decode_frame/stream/new_market
time: [4.0677 ns 4.0850 ns 4.1051 ns]
thrpt: [243.60 Melem/s 244.80 Melem/s 245.84 Melem/s]
*Melem/s: Mega elements per second
Verification Bonus
To collect first hand evidence on this, with Rust and Docker installed, make a new program with:
cargo new count-mem-syscalls-check
And try this:
fn parse_id(bytes: &[u8]) -> u64 {
let mut owned = bytes[..8].to_vec();
// glibc serves allocations above 128 KiB with mmap
// so we force a larger allocation by reserving more space
owned.reserve(1024 * 1024);
let id = u64::from_le_bytes(owned[..8].try_into().unwrap());
std::hint::black_box(owned);
id
}
fn zero_copy_parse_id(bytes: &[u8]) -> u64 {
u64::from_le_bytes(bytes[..8].try_into().unwrap())
}
fn main() {
let bytes = 0x0123_4567_89ab_cdefu64.to_le_bytes();
let id = parse_id(&bytes);
// let id_2 = zero_copy_parse_id(&bytes);
println!("{id}");
// println!("{id_2}");
}
Then measure system calls running strace 2 times, one with parse_id which allocates and later commenting parse_id and uncommenting zero_copy_parse_id which does not allocate.
Check each time the table that this measurement shows you:
docker run --rm \
-v "$PWD":/src \
-w /src \
-e CARGO_TARGET_DIR=/tmp/target \
-e DEBIAN_FRONTEND=noninteractive \
rust:1-slim \
sh -c 'apt-get update -qq && apt-get install -y -qq strace >/dev/null && cargo build --release --quiet && strace -c -e trace=memory /tmp/target/release/count-mem-syscalls-check && strace -e mmap,brk,munmap,write /tmp/target/release/count-mem-syscalls-check'
Here is mine when using parse_id (31 syscalls):
81985529216486895
% time seconds usecs/call calls errors syscall
------ ----------- ----------- --------- --------- ----------------
44.01 0.000136 9 14 mmap
31.07 0.000096 13 7 mprotect
18.77 0.000058 8 7 munmap
6.15 0.000019 6 3 brk
------ ----------- ----------- --------- --------- ----------------
100.00 0.000309 9 31 total
...
brk(NULL) = 0xaaaaf8b05000
brk(0xaaaaf8b26000) = 0xaaaaf8b26000
mmap(NULL, 20480, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_STACK, -1, 0) = 0xffff9571e000
mmap(NULL, 1052672, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS, -1, 0) = 0xffff953ef000
munmap(0xffff953ef000, 1052672) = 0
write(1, "81985529216486895\n", 18) = 18
munmap(0xffff9571e000, 20480) = 0
+++ exited with 0 +++
Here is mine when using zero_copy_parse_id (29 syscalls):
81985529216486895
% time seconds usecs/call calls errors syscall
------ ----------- ----------- --------- --------- ----------------
0.00 0.000000 0 3 brk
0.00 0.000000 0 6 munmap
0.00 0.000000 0 13 mmap
0.00 0.000000 0 7 mprotect
------ ----------- ----------- --------- --------- ----------------
100.00 0.000000 0 29 total
...
brk(NULL) = 0xaaaae88cb000
brk(0xaaaae88ec000) = 0xaaaae88ec000
mmap(NULL, 20480, PROT_READ|PROT_WRITE, MAP_PRIVATE|MAP_ANONYMOUS|MAP_STACK, -1, 0) = 0xffffb07d6000
81985529216486895
write(1, "81985529216486895\n", 18) = 18
munmap(0xffffb07d6000, 20480) = 0
+++ exited with 0 +++
| Column | Meaning |
|---|---|
| calls | How many times that syscall ran |
| errors | How many of those calls failed. Blank means zero |
| seconds | Total time spent inside that syscall |
| usecs/call | Average time per call, in microseconds |
| % time | That syscall’s share of the time in this table |
That tells us:
brk(NULL)asks for the current end of the heap.- The next
brkmoves that end forward, which is the allocator creating the heap during startup. - The
mmapof 20480 bytes is markedMAP_STACK, and its matchingmunmapis after the write, during exit.
Note munmap(0xffff953ef000, 1052672) is the drop of the Vec with reserved RAM that required the extra syscall in its corresponding mmap.