💻 computer science

MapReplay: Trace-Driven Benchmark Generation for Java HashMap

The paper proposes MapReplay, a trace-driven benchmarking methodology that generates efficient, realistic workloads by replaying Java HashMap API sequences to overcome the limitations of both oversimplified microbenchmarks and costly application benchmarks in evaluating HashMap performance.

Original authors: Filippo Schiavio, Andrea RosÃ, Júnior Löff, Lubomír Bulej, Petr Tůma, Walter Binder

Published 2026-03-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Filippo Schiavio, Andrea RosÃ, Júnior Löff, Lubomír Bulej, Petr Tůma, Walter Binder

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine you are a mechanic trying to tune the engine of a Ferrari. The engine is the HashMap, a fundamental tool in Java that stores and retrieves data incredibly fast. You want to know: "If I change the size of the engine's intake valve, will the car go faster?"

The problem is, you can't just test the valve in isolation. If you take the valve out and run it on a workbench (a Microbenchmark), it might look perfect, but it doesn't know how it behaves when the whole car is driving through traffic. On the other hand, if you take the whole Ferrari out for a test drive on a highway (a Full Application Benchmark), the engine is only working hard for a tiny fraction of the time. The rest of the time, the car is idling, turning corners, or playing the radio. To see if your valve tweak actually helps the engine, you'd have to drive the car for hundreds of hours, and even then, the noise from the radio and the tires might drown out the engine's performance.

MapReplay is the solution to this dilemma. It's a "magic tape recorder" for the engine.

The Problem: The "Needle in a Haystack"

In the world of computer programming, HashMaps are like digital filing cabinets. They are used everywhere. But when you try to improve them, you face a choice:

The Toy Test (Microbenchmarks): You test the filing cabinet with fake, simple files. It's fast and easy, but it doesn't tell you how the cabinet handles a real office full of messy, complex paperwork.
The Real Office Test (Application Benchmarks): You watch a real office use the cabinet. It's realistic, but the cabinet is only open 1% of the time. The rest of the time, people are drinking coffee or talking. To see if your new filing system is better, you have to watch the office for days, and the results are often fuzzy because of all the "coffee drinking" (other computer tasks) happening around it.

The Solution: MapReplay (The "Engine-Only" Simulator)

The authors of this paper created MapReplay. Think of it as a device that records only the moments the filing cabinet is opened, closed, or searched.

The Recording Phase: They run a real application (like a web server or a database) with a special "ear" attached to the HashMap. This ear listens only to the filing cabinet. It writes down a script: "Open drawer 5, put file 'A' inside. Close drawer. Open drawer 5, look for file 'B'." It ignores everything else—no coffee drinking, no talking, no radio.
The Replay Phase: They take that script and play it back in a sterile, quiet room. They build a new, perfect filing cabinet and feed it only the script.
- The Magic: Even though they aren't running the whole office, the filing cabinet is in the exact same state as it was in the real office. The drawers are full of the same files, in the same order, with the same collisions.

Why This is a Game-Changer

The paper tested this by trying to find the "perfect" initial size for these filing cabinets.

The Microbenchmark said: "It depends! Sometimes big is good, sometimes small is good." It was too vague because it used fake files.
The Full Application said: "We ran the test for 72 hours, and the results were... maybe a tiny bit faster? We're not sure." It was too noisy and slow.
MapReplay said: "We ran the test for 8 hours. The filing cabinet is 4% faster with the new size." It was fast, clear, and accurate.

The Analogy: The "Cooking Show" vs. The "Restaurant"

Imagine you are a chef trying to perfect a specific sauce (the HashMap).

Microbenchmarks are like tasting the sauce on a spoon in a quiet kitchen. It's fast, but you don't know how it tastes when served with a giant, complex meal.
Full Application Benchmarks are like running a busy restaurant. You serve the sauce to thousands of customers. But the customers are also ordering steak, salad, and dessert. If the sauce tastes slightly better, you might never notice because the noise of the kitchen, the clinking of silverware, and the other dishes are so loud.
MapReplay is like taking a video of the sauce being poured and tasted only during the meal. Then, you play that video back in a silent lab. You can hear the sauce sizzling and tasting perfectly, isolated from the chaos of the restaurant, but you know it's the exact same sauce from the real meal.

The Result

The authors built a library called MapReplayBench. It's a collection of these "sauce-only" recordings taken from famous, real-world Java programs.

This allows developers to:

Save Time: Instead of waiting days for results, they get answers in hours.
See Clearly: They can spot tiny performance improvements that were previously hidden by the "noise" of the rest of the program.
Make Better Decisions: They can confidently change how the HashMap works in the Java language itself, knowing exactly how it will perform in the real world.

In short, MapReplay lets us study the engine of the car without having to drive the whole car, giving us the best of both worlds: the realism of a road trip with the clarity of a wind tunnel test.

1. Problem Statement

Hash-based maps, specifically java.util.HashMap, are fundamental to Java applications and the JVM itself. However, evaluating performance optimizations for these data structures is challenging due to a trade-off between existing benchmarking methodologies:

Microbenchmarks: While fast and repeatable, they often use synthetic, simplified workloads that fail to capture complex, realistic access patterns, key distributions, and resizing behaviors found in real applications.
Full Application Benchmarks (e.g., DaCapo, Renaissance): These provide realistic usage patterns but are expensive to run, prone to high measurement variability, and dominated by non-HashMap computations. Consequently, performance changes in the map implementation are often statistically insignificant or require hundreds of hours of execution to detect.

The core problem is the lack of a benchmarking approach that combines the realism of application workloads with the efficiency and control of microbenchmarks to reliably evaluate HashMap optimizations.

2. Methodology: MapReplay

The authors propose MapReplay, a trace-driven benchmarking methodology that extracts HashMap-specific behavior from real applications and replays it in a controlled, lightweight environment.

Core Architecture

MapReplay consists of three main components:

Tracer: Instruments the HashMap source code (via module patching at JVM launch) to capture relevant API events (e.g., put, get, remove, iteration). It records minimal data: operation type, target map identity, key identity, and hash codes.
Offline Trace Post-Processor: Sanitizes and compacts the raw trace. It removes incomplete traces, coalesces iterator operations, substitutes application keys with uniform mockup objects (preserving hash codes and identity-based equality), and encodes operations into a compact binary format.
Replay Infrastructure: A standalone harness (integrated with JMH) that interprets the processed trace. It reconstructs the internal state of the HashMaps (buckets, collision chains, resizing state) to ensure the replayed operations follow the exact same code paths as in the original application.

Key Design Decisions

State Equivalence: The replay ensures that the internal state of the map (bucket occupancy, collision chains) matches the traced execution, guaranteeing that performance-critical code paths (e.g., treeification, resizing) are exercised identically.
Key Abstraction: To reduce trace size and dependency on application logic, real keys are replaced with mockup keys. Crucially, the hash codes and equality relations (identity-based) are preserved to maintain collision patterns.
Single-Threaded Replay: Even if the original application was multi-threaded, the replay is single-threaded. For distinct map instances, operations are reordered safely; for shared mutable maps, the relative order within critical sections is preserved.
Exclusion of Values: Values stored in the map are ignored, as they rarely affect control flow and tracing them would require capturing arbitrary field writes.
Polymorphism Control: All maps in a replay workload are forced to be of the same type (monomorphic) to allow aggressive JIT inlining and reduce noise.

3. Key Contributions

MapReplay Tool: A novel system that records HashMap usage in applications and generates a replay workload that faithfully reproduces the sequence of operations and internal states without the surrounding application logic.
MapReplayBench: A new benchmark suite generated by applying MapReplay to the DaCapo-Chopin and Renaissance benchmark suites. It contains replay workloads for a wide range of applications, categorized by map intensity.
Empirical Evaluation: A comprehensive study comparing MapReplay against traditional microbenchmarks and full application benchmarks using a case study on determining the optimal Default Initial Capacity (DIC) for HashMap.

4. Evaluation Results

The authors evaluated the effectiveness of MapReplay by testing different DIC values (16, 32, 64, 128) across 30+ benchmarks.

Correlation with Application Benchmarks:
- There is a strong positive linear correlation ( $r = 0.870$ ) between performance trends observed in application benchmarks and MapReplay workloads.
- In 18 out of 21 comparisons, the direction of performance change (speedup or slowdown) was concordant between the two methods.
- MapReplay successfully confirmed performance changes identified by application benchmarks but often with higher statistical significance.
Sensitivity and Detection:
- Application Benchmarks: Only 7 out of 30 benchmarks showed measurable performance differences when varying DIC. Many were "map-minimal," where HashMap activity was too small a fraction of total execution time to detect changes.
- MapReplay: 27 out of 30 replay workloads showed statistically significant performance changes. By isolating HashMap activity, MapReplay amplified the signal, making it possible to detect trends even in applications that were not originally map-intensive.
Efficiency:
- Time Savings: Evaluating all replay workloads for one DIC configuration took approximately 8 hours (using 5 JMH runs). In contrast, the equivalent application benchmark evaluation required roughly 72 hours (30 runs per configuration) to achieve statistical significance.
- Insight Generation: MapReplay identified DIC=64 as the optimal configuration (yielding a 1.04x geometric mean speedup), a conclusion that neither microbenchmarks (too synthetic) nor application benchmarks (too noisy) could reliably provide.

5. Significance and Limitations

Significance:

Middle-Ground Solution: MapReplay bridges the gap between synthetic microbenchmarks and heavy application benchmarks, offering a practical tool for library developers to tune performance parameters (like initial capacity, load factor, or resizing strategies) under realistic conditions.
Actionable Insights: It enables rapid feedback loops for optimization, reducing experimentation time by an order of magnitude while maintaining high fidelity to real-world usage patterns.
Reproducibility: The generated workloads are self-contained and can be executed on any JVM, independent of the original application's external dependencies.

Limitations:

Representativeness: The replay is limited to the specific execution trace captured. If the trace does not cover all phases of an application, the replay may miss certain edge cases.
JIT and Callbacks: The replay uses monomorphic, trivial callbacks (mock keys) rather than the polymorphic user code found in real apps. This changes JIT inlining behavior but aligns with the goal of isolating library performance.
Concurrency: The current implementation is single-threaded. It assumes thread-safety in the original application but does not model fine-grained synchronization or lock-free mechanisms (e.g., ConcurrentHashMap).
Hardware Effects: It does not reproduce low-level architectural effects (cache locality, memory pressure) caused by the surrounding application code.

Conclusion

MapReplay represents a significant advancement in Java performance engineering. By decoupling HashMap behavior from the noise of full application execution, it provides a robust, efficient, and realistic methodology for evaluating hash map optimizations. The resulting MapReplayBench suite offers researchers and practitioners a powerful tool to make data-driven decisions on library implementations that were previously obscured by the complexity of full-scale benchmarks.