Hexceptional Encoding: Mastering the Art of Hex Conversion in Rust
From micro-seconds to nano-seconds, we'll leave no byte unturned
Hex encoding is a widely used technique in the software industry for representing binary data in a human-readable format. It converts each byte of binary data into a two-character hexadecimal representation. Some of the use-cases of hex encoding are:
Data Storage and network Transmission: Hex encoding is essential for storing or sending binary data in formats like json, xml etc, which can't directly handle binary.
Checksums and Hash Digests: Hex encoding is commonly used to represent checksums and hash digests. Checksums are used to verify the integrity of data, ensuring that it has not been corrupted during storage or transmission. Hash digests, such as SHA-256 or MD5, are often used for data integrity checks, password storage, and digital signatures. By hex encoding checksums and hash digests, they can be easily compared, stored, and communicated as human-readable strings.
For this blog, I will take point 2 as an example to show various approaches as I recently contributed to optimising such a method in supabase edge-runtime where this hex encoding function is used to prepare cache keys, doing checksum on files etc. Here is the pull request link if you like to explore the changes there.
Encoding SHA256 Digest to hex using String Concatenation
Let's calculate the SHA256 digest of input data and returns the result as a hexadecimal string. Here's an implementation using string concatenation:
In this, we first create a new sha256 context using Context::new(&SHA256) of ring crate. Then, we iterate over the input slices feeding them to the context. Using ctx.finish() we obtain the digest. This part will be common to all our techniques. Lets focus on the part where we are converting the digest to hex encoding.
We iterate over each byte of the digest using digest.as_ref().iter() and format each byte as a two-character hexadecimal string using format!("{byte:02x}"). These are collected into the out vector. Finally, we join the vector using out.join("") and get hex encoded output.
To an untrained eye, this may look alright, but there are lot of memory allocations happening here. sha256 digest is 32 bytes and the corresponding hex string is 64 chars long. The code iter().map(|byte| format!("{byte:02x}")) iterates over every byte and since the digest consists of 32 bytes, there will be 32 formatted strings. Each string is a separate memory allocation. Therefore, this step performs 32 memory allocations. Collecting into a vector using collect is 1 separate memory allocation, and then out.join(““) is one another memory allocation to create the final string.
In total, there are atleast 34 separate memory allocations happening just to convert to hex encoding.
Lets see benchmarks (generated using criterion crate) how this string concatenation performs:
we get a mean time of 2.7 micro seconds. Let’s see how much of a difference can minimising memory allocations cause.
Encoding SHA256 Digest to hex using write! macro
Here is the code that uses rust’s write macro:
In this approach, instead of creating a vector of formatted strings and joining them, we use the write! macro to directly write the formatted bytes into a mutable String called out. We initialize out with a capacity of 64, which is the expected length of the hex-encoded digest string.
The write! macro allows us to write formatted text directly into a string, avoiding the need for intermediate allocations. By using for_each and write!, we iterate over each byte of the digest and write its formatted representation into out.
Compared to the string concatenation approach, with write!, we can use just one allocation by writing directly into a pre-allocated string. This reduces the number of allocations from 34 (in the previous approach) to just 1 for the out itself and no joining of strings after too.
Here is what the benchmark outcome looks now:
we get a mean time of 956 ns (~3x improvement). Nice, with this you learned in what order of time (us→ns) can avoiding memory allocations improve performance. Generally, for web servers performance bottlenecks come from network related calls (in the order of milliseconds) and these type of optimisations may not make much impact. However, for systems like databases, or batch processing applications, and real-time data processing, where millions of operations need to be done, these optimisations can make significant impact.
At last I want to show how fast are dedicated crates for hex encoding in rust
Encoding SHA256 Digest to hex using hex and faster-hex crate
Hex crate is pretty well known crate that uses simple bit operations and a static table lookup to convert a byte to hex character. A very simplistic representation of what the crate internally does to encode the bytes looks like this:
faster-hex crate does much more low level optimisations like simd vectorisation, etc to significantly speedup things. Using hex and faster hex crate in our code like this:
just a one line change for both. Let me show you the complete benchmark results now:
faster-hex is almost 10x faster than string concatenate. Wow! . All the benchmarking code is available here on github
Happy (en)Coding!!