💻 computer science

JEDI: Java Evaluation of Declarative and Imperative Queries

This paper presents JEDI, an automatically generated benchmark suite that converts SQL queries into Java to evaluate and compare the performance of declarative Stream API implementations against imperative baselines, aiming to identify inefficient code patterns and guide the optimization of the Java Stream API.

Original authors: Filippo Schiavio, Walter Binder

Published 2026-05-25

📖 6 min read🧠 Deep dive

CC BY 4.0

Original authors: Filippo Schiavio, 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 have a massive warehouse full of boxes (data), and you need to find specific items, sort them, and count them. You have two ways to give instructions to your workers:

The "Manager" Approach (Imperative): You walk up to each worker individually and say, "Pick up this box. Check if it's red. If yes, put it in a pile. If no, throw it away. Now pick up the next one." This is very direct and fast, but it requires a lot of talking and can get messy if you have thousands of workers.
The "Foreman" Approach (Java Stream API): You write a single, elegant note: "Take all boxes, filter for red ones, sort them by size, and count them." You hand this note to a foreman who figures out how to get the workers to do it. This is much easier for you to write and read, but the foreman has to translate your note into actions, which sometimes takes extra time.

This paper, titled JEDI, is all about testing how well the "Foreman" (the Java Stream API) performs compared to the "Manager" (traditional code), and figuring out how to make the Foreman work faster.

The Problem

The Java Stream API is popular because it makes code look clean and easy to understand (like the note to the foreman). However, developers have suspected that this "clean" way of writing code is slower than the "messy" traditional way. The problem is, no one had a proper race track (a benchmark) to test this fairly. Without a race track, the people who build the Java language (the "mechanics") don't know exactly where the engine is sputtering, and developers don't know which instructions give the best speed.

The Solution: JEDI

The authors built JEDI (Java Evaluation of Declarative and Imperative Queries). Think of JEDI as a giant, automated factory that takes standard database questions (written in a language called SQL, which is like a universal request form) and instantly translates them into two different sets of instructions:

One set using the "Foreman" style (Streams).
One set using the "Manager" style (Imperative loops).

Because the factory translates the exact same question into both styles, the comparison is perfectly fair. It's like giving two runners the exact same path and timing them to see who is faster.

What They Discovered

1. Small Tweaks Make a Big Difference (The "Filter Fusion")
Sometimes, the Foreman gets confused if you give him three separate notes: "Check for red," "Check for big," "Check for heavy."

The Fix: The authors found that combining these into one big note ("Check for red AND big AND heavy") makes the Foreman much faster. It's like giving a worker one clear instruction instead of three confusing ones.
The Result: This simple change made the code run up to 2.6 times faster in some cases.

2. The "One-to-Many" Trick
Sometimes a single box contains many smaller items inside.

The Old Way: The Foreman would take the box, open it, pull out one item, put it in a pile, go back, pull out the next, and repeat.
The New Way: The authors found a special tool (called mapMulti) that lets the Foreman open the box and dump all the items out at once in one smooth motion.
The Result: This was even more effective than the first tip, often doubling the speed.

3. The Parallelism Puzzle (Using Many Workers)
When you have a huge warehouse, you want to use many workers at once (parallel processing). The paper tested four different ways to organize these workers:

The "Strict Order" Team: Everyone works in a line, passing boxes down. Good for keeping order, but slow.
The "Chaos" Team: Everyone grabs boxes randomly. Fast, but hard to manage.
The "Shared Board" Team: Everyone writes their results on one giant shared whiteboard.
The "Atomic" Team: Everyone uses a special, high-tech pen that never smudges, even if two people write at the same time.

The Verdict: There is no single "best" team.

If you have very few groups of items to sort (like sorting only 4 types of fruit), the "Strict Order" or "Chaos" teams are fastest because the "Shared Board" gets too crowded (too much arguing over who writes first).
If you have thousands of groups (like sorting 10,000 different fruit types), the "Shared Board" team wins because the arguing stops, and everyone can write their own section without bumping into others.

4. The Speed Gap
The big question: Is the "Foreman" (Stream) slower than the "Manager" (Imperative)?

Yes. The traditional "Manager" code is consistently faster, usually by about 30% to 40%.
Why? The "Foreman" has to spend time translating your elegant note into actions. The "Manager" just does the work immediately.
The Good News: The gap isn't as huge as people thought it might be in the past. The Java team has been improving the engine. However, for the absolute fastest performance, the "Manager" style still wins.

5. The Trade-off: Speed vs. Sanity
The paper also looked at how hard the code is to read.

The "Manager" code (fastest) is like a dense, confusing instruction manual. It's hard to read and easy to make mistakes in.
The "Foreman" code (slower) is like a clear, short story. It's much easier to understand and less likely to have errors.
The Lesson: You have to choose. Do you want the code to run 30% faster, or do you want it to be 2.5 times easier for humans to read and maintain? The paper suggests that for most people, the "Foreman" style is worth the small speed penalty because it saves time on debugging and maintenance.

Summary

JEDI is a new tool that helps developers understand the "cost" of using the modern, easy-to-read Java Stream API. It proves that while the easy-to-read code is slightly slower than the old-school code, you can make it much faster by using specific tricks (like combining filters). It also tells developers exactly how to organize their workers (parallel strategies) depending on how much data they have. Ultimately, it gives developers a roadmap to write code that is both readable and reasonably fast.

Technical Summary: JEDI – Java Evaluation of Declarative and Imperative Queries

Problem Statement

The Java Stream API, introduced in Java 8, offers a declarative syntax for processing collections and infinite data sources, aiming to improve developer productivity, code readability, and maintainability compared to traditional imperative loop-based code. While the API simplifies parallel computing through high-level abstractions, existing literature indicates that Stream-based implementations often suffer from performance penalties relative to equivalent imperative code.

A critical gap identified in this work is the lack of dedicated benchmark suites targeting the Stream API. Without such benchmarks, it is difficult for:

Researchers and Library Developers: To optimize the Stream API implementation within the Java Class Library (JCL).
Application Developers: To understand the performance characteristics of different stream operations and parallelization strategies to write efficient code.

Current benchmarks either do not explicitly target the Stream API or rely on simple, synthetic pipelines that do not reflect complex, real-world data processing workloads.

Methodology

To address this gap, the authors present JEDI (Java Evaluation of Declarative and Imperative Queries), a benchmark suite automatically generated by converting SQL queries into Java source code.

Generation Process

Source Material: The authors utilize the TPC-H benchmark, a widely used data-analytics benchmark composed of complex queries covering various data processing features (joins, aggregations, filtering, sorting).
Code Conversion: The authors extended an existing tool, S2S (SQL to Stream), to convert SQL queries into multiple semantically equivalent Java implementations.
- Schema Mapping: SQL tables are mapped to in-memory arrays of objects.
- Query Translation:
  - SELECT projections $\rightarrow$ map(...)
  - WHERE predicates $\rightarrow$ filter(...)
  - ORDER BY $\rightarrow$ sorted(...)
  - LIMIT $\rightarrow$ limit(...)
  - GROUP BY and Aggregations $\rightarrow$ collect(...) with generated collectors.
  - JOIN $\rightarrow$ Implemented via flatMap (building a hash-map for the build side) or mapMulti.
Implementation Variants: For a single SQL query, JEDI generates multiple variants to compare different coding patterns and execution strategies:
- Sequential Variants:
  - O1 (Filter Fusion): Combining multiple predicates into a single filter call versus multiple chained calls.
  - O2 (Join Implementation): Using mapMulti versus flatMap for join operations.
- Parallel Variants (O3):
  - P: Ordered parallel streams (parallel()).
  - PU: Unordered parallel streams (parallel().unordered()).
  - CG: Unordered parallel streams using groupingByConcurrent (shared state with lock-based synchronization).
  - CGCC: CG with thread-safe downstream collectors (lock-free atomic operations).
- Imperative Baseline: A loop-based implementation using the exact same data structures and operation order as the stream versions to measure the "overhead of the Stream API."

Evaluation Setup

Hardware: Two distinct architectures: Intel Xeon Gold (16 cores) and ARM Neoverse-N1 (80 cores).
JVMs: Oracle JDK 24 and GraalVM 24.
Datasets: TPC-H scale factors of 1 (1GB) for sequential analysis and 10 (10GB) for parallel analysis.
Tooling: Java Microbenchmark Harness (JMH) with warmup and measured iterations to ensure steady-state performance.

Key Contributions

JEDI Benchmark Suite: The release of an open-source benchmark suite derived from TPC-H, automatically generating semantically equivalent stream and imperative implementations.
Code Generator: An extended version of S2S that supports multiple implementation strategies (sequential optimizations and various parallel reduction patterns).
Performance Guidelines: A set of derived best practices for using the Stream API efficiently based on empirical data.
Overhead Analysis: A direct comparison of stream-based vs. imperative code using identical data structures and operation orders to isolate the performance cost of the API abstractions.

Results and Findings

RQ1: Sequential Optimizations (Filter Fusion & Join Implementation)

Filter Fusion (O1): Combining predicates into a single filter call improves performance, particularly when many predicates are present (e.g., 3.54x speedup on a microbenchmark with 7 predicates).
Join Implementation (O2): Using mapMulti instead of flatMap for joins yields significant improvements (geometric mean speedup of 1.38x on Intel JDK).
Conclusion: Developers should apply both O1 and O2 whenever possible.

RQ2: Parallelization Strategies

No Universal Winner: No single parallel strategy dominates all scenarios. Performance depends heavily on data characteristics, specifically the number of aggregated groups and the nature of the aggregation.
Scalar vs. Grouped Aggregations:
- For scalar aggregations (no grouping) or small numbers of groups, ordered (P) or unordered (PU) parallel streams outperform shared-state strategies (CG, CGCC) due to lower contention.
- For grouped aggregations with many groups, CG (using groupingByConcurrent) is generally the best strategy. As the number of groups increases, lock contention decreases, making lock-based synchronization efficient.
Lock-Free vs. Lock-Based: CGCC (lock-free) does not consistently outperform CG (lock-based) and introduces implementation complexity. However, CGCC is more robust for very small group counts where CG suffers from high contention.
Distinct Operations: While unordered streams (PU) are generally recommended for distinct, the study found that for streams with a low number of distinct elements, ordered parallel streams (P) can be up to 2x faster due to the overhead of managing a shared ConcurrentHashMap in unordered streams.

RQ3: Stream vs. Imperative Performance

Imperative Superiority: Imperative loop-based code consistently outperforms stream-based code.
Magnitude: The geometric mean speedup of imperative code over the best sequential stream implementation ranges from 1.28x to 1.41x across different JVMs and architectures.
Context: While this confirms previous findings, the authors note the gap is smaller than in some prior studies, suggesting improvements in the Stream API implementation over time. However, for performance-critical code, imperative code remains substantially faster.

RQ4: Code Complexity

Readability: Despite the performance gap, stream-based code exhibits significantly lower complexity metrics.
Metrics: Cognitive complexity of baseline stream code is 2.43x lower than imperative code. Even with optimizations (O1+O2), stream code remains 1.62x less complex than imperative code.
Trade-off: Optimizing stream code (e.g., fusing filters) increases its complexity metrics but keeps it below the complexity of imperative equivalents.

Significance and Claims

The paper positions JEDI as a vital tool for both the Java community and the JVM implementers:

For Developers: It provides data-driven guidelines to minimize the performance overhead of the Stream API, suggesting specific patterns (e.g., mapMulti, groupingByConcurrent for large groups) based on workload characteristics.
For Library Implementers: The benchmark suite and the identified "overhead" provide a baseline for optimizing the Stream API implementation to close the performance gap with imperative code.
For Researchers: It offers a reproducible, complex workload (TPC-H derived) to evaluate future optimizations, refactoring tools, or parallelization strategies.

The authors modestly acknowledge limitations, noting that JEDI currently focuses on array-based data sources and specific SQL-to-Stream translation patterns. They plan to extend the generator to cover more Stream API methods and vary data sources (e.g., Lists, Sets) in future work.