Packed Data Support in Haskell

Summary

This blog post aims to be a short and accessible summary of a paper that will be published at ECOOP 2025, titled Type-safe and portable support for packed data.Introduction: Packed DataWhen programs want to persist data or send it over the network, they need to serialise it (e.g. to JSON or XML). On the other hand, when a program receives data from the network or reads it from a file, data needs to be deserialised.flowchart LR Server(["Server"]) Server --> SD["Serialise"] SD -- Network --- RD["Deserialise"] RD --> Client(["Client"]) These de/serialisation steps are necessary because we cannot use the in-memory representation/layout of the data in a file or when sending it over the network, mainly because of the pointers it may contain.Consequently, de/serialising data has a cost: it takes time, and the serialised version of the data is usually bigger than its in-memory representation. In the context of systems that interact through the network, it leads to larger payloads to send, and thus slower transfer times.Now, what if we didn’t have to serialise the data before sending it to a client, and what if the client could use the data from the network as-is, without any marshalling steps? We could save some time, on both the server and client side.Introducing the ‘packed’ data format, a binary format that allows using data as it is, without the need for a deserialisation step. A notable perk of this format is that traversals on packed trees is proven to be faster than on ‘unpacked’ trees: as the fields of data structures are inlines, there are no pointer jumps, thus making the most of the L1 cache.To better understand how it looks like, here is a representation of a tree in memory that uses pointers. N represents nodes, and L represents leaves. Numbers are the tree’s data, and dots and arrows are pointers. Pointer-based tree layout in memoryHere is what a packed tree looks like in memory. Packed tree layout in memoryA few projects use or leverage this ‘packed’ approach...