Technische Samenvatting: JEDI – Java Evaluation of Declarative and Imperative Queries

Probleemstelling

De Java Stream API, geïntroduceerd in Java 8, biedt een declaratieve syntaxis voor het verwerken van verzamelingen en oneindige gegevensbronnen, met als doel de productiviteit van ontwikkelaars, de leesbaarheid van code en het onderhoud te verbeteren ten opzichte van traditionele imperatieve loop-gebaseerde code. Hoewel de API parallelle berekening vereenvoudigt via hoog-niveau abstracties, geeft bestaande literatuur aan dat Stream-gebaseerde implementaties vaak last hebben van prestatieverliezen ten opzichte van equivalente imperatieve code.

Een kritieke lacune die in dit werk is geïdentificeerd, is het ontbreken van specifieke benchmark suites die gericht zijn op de Stream API. Zonder dergelijke benchmarks is het moeilijk voor:

1. Onderzoekers en Bibliotheekontwikkelaars: Om de implementatie van de Stream API binnen de Java Class Library (JCL) te optimaliseren.
2. Applicatieontwikkelaars: Om de prestatiekarakteristieken van verschillende stream-operaties en parallelisatiestrategieën te begrijpen om efficiënte code te schrijven.

Huidige benchmarks richten zich ofwel niet expliciet op de Stream API, ofwel vertrouwen ze op eenvoudige, synthetische pipelines die complexe, real-world gegevensverwerkingswerklasten niet weerspiegelen.

Methodologie

Om deze lacune aan te pakken, presenteren de auteurs JEDI (Java Evaluation of Declarative and Imperative Queries), een benchmark suite die automatisch wordt gegenereerd door SQL-query's om te zetten in Java-broncode.

Generatieproces

1. Bronmateriaal: De auteurs maken gebruik van de TPC-H benchmark, een veelgebruikte data-analyse benchmark bestaande uit complexe query's die diverse gegevensverwerkingsfuncties bestrijken (joins, aggregaties, filtering, sorting).
2. Codeconversie: De auteurs hebben een bestaand gereedschap, S2S (SQL to Stream), uitgebreid om SQL-query's om te zetten in meerdere semantisch equivalente Java-implementaties.
   • Schema-mapping: SQL-tabellen worden gemapt naar in-memory arrays van objecten.
   • Query-vertaling:
     • SELECT projecties $\rightarrow$ map(...)
     • WHERE predicaten $\rightarrow$ filter(...)
     • ORDER BY $\rightarrow$ sorted(...)
     • LIMIT $\rightarrow$ limit(...)
     • GROUP BY en Aggregaties $\rightarrow$ collect(...) met gegenereerde collectors.
     • JOIN $\rightarrow$ Geïmplementeerd via flatMap (bouwen van een hash-map voor de build-kant) of mapMulti.
3. Implementatievarianten: Voor een enkele SQL-query genereert JEDI meerdere varianten om verschillende coderingspatronen en uitvoeringsstrategieën te vergelijken:
   • Sequentiële Varianties:
     • O1 (Filter Fusion): Het combineren van meerdere predicaten in één filter-aanroep versus meerdere gekoppelde aanroepen.
     • O2 (Join-implementatie): Het gebruik van mapMulti versus flatMap voor join-operaties.
   • Parallelle Varianties (O3):
     • P: Gestructureerde parallelle streams (parallel()).
     • PU: Ongestructureerde parallelle streams (parallel().unordered()).
     • CG: Ongestructureerde parallelle streams met groupingByConcurrent (gedeelde staat met lock-gebaseerde synchronisatie).
     • CGCC: CG met thread-safe downstream collectors (lock-free atomaire operaties).
   • Imperatieve Baseline: Een loop-gebaseerde implementatie die exact dezelfde datastructuren en operationele volgorde gebruikt als de stream-versies om de "overhead van de Stream API" te meten.

Evaluatieopstelling

• Hardware: Twee verschillende architecturen: Intel Xeon Gold (16 cores) en ARM Neoverse-N1 (80 cores).
• JVM's: Oracle JDK 24 en GraalVM 24.
• Datasets: TPC-H schaalfactoren van 1 (1GB) voor sequentiële analyse en 10 (10GB) voor parallelle analyse.
• Tooling: Java Microbenchmark Harness (JMH) met warmup en gemeten iteraties om steady-state prestaties te garanderen.

Belangrijkste Bijdragen

1. JEDI Benchmark Suite: De release van een open-source benchmark suite afgeleid van TPC-H, die automatisch semantisch equivalente stream- en imperatieve implementaties genereert.
2. Code Generator: Een uitgebreide versie van S2S die meerdere implementatiestrategieën ondersteunt (sequentiële optimalisaties en diverse parallelle reductiepatronen).
3. Prestatierichtlijnen: Een set afgeleide best practices voor het efficiënt gebruiken van de Stream API op basis van empirische data.
4. Overheadanalyse: Een directe vergelijking van stream-gebaseerde versus imperatieve code met identieke datastructuren en operationele volgorde om de prestatiekost van de API-abstracties te isoleren.

Resultaten en Bevindingen

RQ1: Sequentiële Optimalisaties (Filter Fusion & Join-implementatie)

• Filter Fusion (O1): Het combineren van predicaten in één filter-aanroep verbetert de prestaties, met name wanneer veel predicaten aanwezig zijn (bijvoorbeeld 3,54x snelheidswinst op een microbenchmark met 7 predicaten).
• Join-implementatie (O2): Het gebruik van mapMulti in plaats van flatMap voor joins levert aanzienlijke verbeteringen op (geometrische gemiddelde snelheidswinst van 1,38x op Intel JDK).
• Conclusie: Ontwikkelaars moeten O1 en O2 waar mogelijk toepassen.

RQ2: Parallelisatiestrategieën

• Geen Universele Winnaar: Geen enkele parallelle strategie domineert alle scenario's. De prestaties hangen sterk af van de gegevenskarakteristieken, specifiek het aantal gegroepeerde groepen en de aard van de aggregatie.
• Scalar versus Gegroepeerde Aggregaties:
  • Voor scalar aggregaties (zonder groepering) of kleine aantallen groepen presteren gestructureerde (P) of ongestructureerde (PU) parallelle streams beter dan gedeelde-staat strategieën (CG, CGCC) vanwege lagere concurrentie.
  • Voor gegroepeerde aggregaties met veel groepen is CG (met groupingByConcurrent) over het algemeen de beste strategie. Naarmate het aantal groepen toeneemt, neemt de lock-concurrentie af, waardoor lock-gebaseerde synchronisatie efficiënt wordt.
• Lock-Free versus Lock-Based: CGCC (lock-free) presteert niet consequent beter dan CG (lock-based) en introduceert implementatiecomplexiteit. Echter, CGCC is robuuster voor zeer kleine groepenaantallen waarbij CG last heeft van hoge concurrentie.
• Distinct-operaties: Hoewel ongestructureerde streams (PU) over het algemeen worden aanbevolen voor distinct, vond de studie dat voor streams met een laag aantal unieke elementen, gestructureerde parallelle streams (P) tot 2x sneller kunnen zijn vanwege de overhead van het beheren van een gedeelde ConcurrentHashMap in ongestructureerde streams.

RQ3: Stream versus Imperatieve Prestaties

• Imperatieve Superioriteit: Imperatieve loop-gebaseerde code presteert consequent beter dan stream-gebaseerde code.
• Omvang: De geometrische gemiddelde snelheidswinst van imperatieve code ten opzichte van de beste sequentiële stream-implementatie varieert van 1,28x tot 1,41x over verschillende JVM's en architecturen.
• Context: Hoewel dit eerdere bevindingen bevestigt, merken de auteurs op dat de kloof kleiner is dan in sommige eerdere studies, wat wijst op verbeteringen in de implementatie van de Stream API door de tijd heen. Echter, voor prestatie-kritieke code blijft imperatieve code aanzienlijk sneller.

RQ4: Codecomplexiteit

• Leesbaarheid: Ondanks het prestatiekloof vertoont stream-gebaseerde code significant lagere complexiteitsmaten.
• Maten: De cognitieve complexiteit van baseline stream-code is 2,43x lager dan imperatieve code. Zelfs met optimalisaties (O1+O2) blijft stream-code 1,62x minder complex dan imperatieve code.
• Trade-off: Het optimaliseren van stream-code (bijvoorbeeld het fuseren van filters) verhoogt de complexiteitsmaten, maar houdt deze onder de complexiteit van imperatieve equivalenten.

Betekenis en Claims

Het artikel positioneert JEDI als een vitaal hulpmiddel voor zowel de Java-community als de JVM-implementators:

• Voor Ontwikkelaars: Het biedt datagedreven richtlijnen om de prestatieoverhead van de Stream API te minimaliseren, met specifieke patronen (bijvoorbeeld mapMulti, groupingByConcurrent voor grote groepen) gebaseerd op werklastkarakteristieken.
• Voor Bibliotheekimplementators: De benchmark suite en de geïdentificeerde "overhead" bieden een basislijn voor het optimaliseren van de Stream API-implementatie om de prestatiekloof met imperatieve code te dichten.
• Voor Onderzoekers: Het biedt een reproduceerbare, complexe werklast (afgeleid van TPC-H) om toekomstige optimalisaties, refactoring-tools of parallelisatiestrategieën te evalueren.

De auteurs erkennen nederig beperkingen, met de opmerking dat JEDI momenteel focust op array-gebaseerde gegevensbronnen en specifieke SQL-naar-Stream vertaalpatronen. Ze plannen om de generator uit te breiden om meer Stream API-methoden te dekken en gegevensbronnen te variëren (bijvoorbeeld Lijsten, Sets) in toekomstig werk.