Base 64 and Binary Line Reader

-
Base64  is a standard to encode binary data into ASCII characters for easy transportation (such as email/SMTP and HTTP/MIME). People also often use Base64 as a storage format for sensor and computer log data because they can use line break characters as record boundary markers. 

To decode Base64 data, a common way in Java is to use BufferedReader's readLine method to read encoded records line by line and then decode them. The problem is, readLine returns a String object, which is fairly expensive if there are billions of records. Since the original data is in binary, the String objects are unnecessary. In Java, there are no JDK classes that can read bytes line by line. I implemented ByteLineReader  to fill the gap. Although the idea sounds simple, it was a little tricky to manage the buffers. On my 2 year old Macbook Pro, my implementation can reach 70 MB/s to saturate my HDD bandwidth. 

I found two Base64 decoder implementations to test my code. One is from Robert Harder and the other is from Mikael Grev. (There is no JDK Base64 utility class.) In order to benchmark the performance of these two decoders, I wrote DataGen code to generate some test data: 1M lines of 1KB, 4KB, and 8KB records. 

I ran each test five times and removed the first run from each test (this is an outlier due to the HotSpot JVM warming up). R was my first choice to analyze the data. The bar plot thus shows the average of four runtimes. For the smaller records, MiG's decoder is faster, but for the 8K records, it is slightly slower. I did not test MiG's faster decoder method because it has some assumptions about the encoded bytes. 

It was really fun to write the ByteLineReader, integrate it with the Base64 decoders, and use R to analyze the data (and not let the HotSpot warming up to pollute the actual data analysis)! 

Popular posts from this blog

Space Race: a simple Rust game built on the Bevy framework

-
Image
When I saw a post announcing the release of the Bevy framework  (an open source game engine written in Rust), I thought it'd be a fun way to learn Rust.  So I made Space Race , a 2 player game on top of the Bevy framework. How to Play The Astronaut moves around collecting jewels (using WASD keys). The Alien moves around trying to catch the Astronaut (using arrow keys).  The Astronaut wins if they collect at least 5 jewels and make it back to home base before the Alien catches them.  The Alien wins otherwise.  Things I learned about Rust  I had a lot of fun making & playing this game, and also got some hands on experience with Rust like working with structs enums vectors iterators traits dyn trait vs impl trait  dyn trait is used for trait objects, which are fat pointers made up of 1) a pointer to the value 2) a pointer to a vtable. A vtable is a table of methods, where each method points to its implementation, generated once at compile time. Each i...
Read more

Building a Toy Language Compiler in Go

-
Image
A follow-up to my previous post about building a toy language interpreter in Go. Throughout this post, I'll be referencing my repo . We'll go over a compiler which translates source code to machine code, and then a VM to execute this machine code. What is a compiler?  A compiler takes source code and translates it to executable machine code . (See my previous post for more details.) The figure below shows the high-level architecture of a simple compiler. Like the interpreter we built previously, our compiler has a lexer and a parser which turn our source code into an AST . This is our compiler's frontend . However, that's where a compiler diverges.  The compiler may translate the AST into at least one internal representation (IR) . The IR(s) may be represented using any data structure (even another AST!), but they should follow two rules: (1) be easy to produce, (2) be easy to translate into the target machine code. The IR can also be optimized...
Read more

tldr: Raft + Implementation Tips

-
Image
Part of the tldr series , which summarizes papers I'm currently reading. Inspired by the morning paper . Raft (Extended Version) + Implementation Tips [2014] Ongaro et al. Note: For implementation tips, see the end of this blog post.  Introduction Consensus algorithms The r eplicated state machine approach  is useful for providing fault-tolerance in distributed systems. It lets a cluster of unreliable machines continue operating even when some of its members fail. In this approach, machines   usually use a replicated log to stay in sync. As shown in the figure below, each server's log stores the same commands in the same order. Every state machine executes commands from its own log in order. State machines are deterministic, so each produces the same order of outputs. Once the majority of machines have responded, the command is done executing. Consensus algorithms ensure that the replicated log stays consistent. In the figure above, clients s...
Read more