Efficient communication and collection with compact normal forms

Edward Z. Yang, Giovanni Campagna, Ömer S. Agacan, Ahmed El-Hassany, Abhishek Kulkarni, Ryan R. NewtonIcfp 2015 · DOI

TL;DR

This paper introduces Compact Normal Forms (CNFs), an API for Haskell that allows immutable heap objects to be placed in contiguous memory regions. This enables significantly faster network communication and more efficient garbage collection by treating the in-memory representation as the network representation, achieving up to 4x speedups on fast networks.

What Problem Does This Paper Address?

Modern programming languages, especially those with memory safety and rich data structures like Haskell, often represent data in non-contiguous ways across the heap. This poses a significant challenge for high-performance network communication, as network interface cards (NICs) perform best with contiguous data. The traditional solution involves serialization, which converts these scattered heap objects into a contiguous buffer. However, this serialization process is a major bottleneck, especially on fast networks where it becomes the limiting factor. Existing approaches often fail to achieve true zero-copy data transmission and struggle with mutable or higher-order data. The paper aims to bridge this gap by allowing direct transmission of heap data in a contiguous format, minimizing or eliminating serialization overhead.

Methods

The core innovation is the Compact Normal Form (CNF), an API that allows programmers to explicitly place immutable heap objects into contiguous memory regions. This is achieved through a Compactable type class, similar to Haskell's NFData, which ensures data is fully evaluated and then copied into a compact region.

Key aspects of the method include:

  • Compactable Type Class: Defines types that can be evaluated to normal form and copied into a compact region. This excludes mutable types.
  • mkCompact and appendCompact: Functions to create new compact regions and append evaluated data to existing ones. appendCompact intelligently shares already compacted subgraphs.
  • Referential Transparency (with caveats): While the core operations are referentially transparent, they are exposed via the IO monad to allow for performance-sensitive operational choices regarding sharing and allocation.
  • Region Invariants: Strict enforcement of immutability and no outgoing pointers within a compact region. This simplifies garbage collection and network transmission.
  • GHC Runtime Modification: The implementation involves modifications to the Glasgow Haskell Compiler's runtime system to manage these compact regions and efficiently test for object membership.
  • Network Communication: CNFs can be serialized as a list of blocks and a root pointer. The paper discusses both eager (push-based) and rendezvous (pull-based) RDMA protocols for zero-copy transfer.

Datasets

The paper evaluates their approach using three representative data types:

  • bintree: A binary tree with a single unboxed integer at each leaf, representing pointer-heavy data.
  • pointtree: A binary tree with four unboxed integers at each leaf, representing denser data.
  • Twitter Metadata: A dataset composed of URLs, hashtags, and user IDs from Twitter posts, used to evaluate performance on real-world, mixed data.

The authors note that they do not cover large unboxed arrays, as these are already handled efficiently by existing strategies.

Key Insights and Ideas

  • In-Memory = Network Representation: The most significant insight is that by making the in-memory representation of data the same as its network representation, serialization overhead can be drastically reduced or eliminated, leading to substantial performance gains.
  • Immutability is Key: The strict enforcement of immutability within compact regions is crucial. It simplifies garbage collection (no need to trace into regions) and makes data safe for network transmission and copying.
  • Amortized Copying: The cost of copying data into a compact region is amortized over multiple network transmissions or accesses, making it efficient for frequently used data.
  • Garbage Collection Benefits: CNFs can improve GC performance by allowing long-lived data to be excluded from tracing, reducing GC pauses and making them more predictable.
  • Zero-Copy RDMA is Achievable: The paper demonstrates that with careful design, true zero-copy network transfer using RDMA is feasible by leveraging CNFs and striped memory allocation.

Key Results

  • Serialization Speedup: CNFs achieve up to an order of magnitude faster copying into a compact region compared to traditional serialization methods for large data structures.
  • Network Latency: On fast local networks, CNFs provide significant end-to-end latency improvements, with speedups of up to 4x observed for large data structures.
  • Memory Overhead: While CNFs can sometimes lead to a space blow-up (up to 4x in the worst case) compared to highly optimized binary serialization, this is often offset by performance gains.
  • RDMA Performance: Zero-copy RDMA transfer using CNFs shows up to a 5x speedup over eager RDMA protocols that involve serialization and pointer fixups.
  • Key-Value Store Performance: A key-value store implemented using CNFs demonstrated increased request handling throughput compared to a standard binary serialization approach.
  • GC Performance: Experiments showed reduced GC pauses and improved CPU utilization for workloads involving long-lived data in compact regions.

Limitations and Future Work

  • Space Overhead: The paper acknowledges that CNFs can sometimes increase memory usage, especially for small data or when data is not reused.
  • Sharing Preservation: The default implementation does not preserve sharing for objects not already in a compact region, which can lead to duplicated data. While a hash-table based approach was explored, it incurred significant overhead. Future work could explore more efficient sharing preservation mechanisms.
  • Manual Automation: The decision to copy data into a new compact region after a certain number of updates is currently manual. Automating this process with heuristics is suggested for future work.
  • Trusted Instances: The Compactable type class relies on trusted instances to maintain safety. Runtime checks are used as a fallback, but ensuring safety through trusted instances is preferred.
  • Mutable Data: The API is not suitable for rapidly changing data structures, as it would lead to significant memory wastage.

Summary updated

BibTeX
@inproceedings{yang2015efficient,
  author = {Edward Z. Yang and Giovanni Campagna and Ömer S. Agacan and Ahmed El-Hassany and Abhishek Kulkarni and Ryan R. Newton},
  title = {{Efficient communication and collection with compact normal forms}},
  booktitle = {Icfp},
  year = {2015},
  doi = {10.1145/2784731.2784735},
}
Figure