PEG AST Evaluator benchmarks — Go, TypeScript (Node+Bun), C, Rust, Java (JVM+Android)

SUMMARY.md

PEG AST Evaluator — Java (JVM vs Android ART)

Tanggal: 8 Agustus 2026
Mesin: Apple M4 (arm64)
JVM: OpenJDK 17.0.19 (Zulu, HotSpot)
Android: Android 16 (Baklava) ARM64 emulator, ART runtime

---

1. Pendekatan

#	Label	File	Mekanisme
1	virtual	Virtual.java	Interface Expr + method override — vtable dispatch
2	sealed	Sealed.java	Sealed class + instanceof checks
3	tagged	Tagged.java	Enum Tag + switch — manual tagged union
4	visitor	Visit.java	Visitor interface + accept() — double dispatch

---

2. Struktur Proyek

java/
├── src/peg/
│   ├── Common.java      # Result, helper types
│   ├── Virtual.java     # ⚡ virtual dispatch (interface + classes)
│   ├── Sealed.java      # ⚡ sealed class + instanceof
│   ├── Tagged.java       # ⚡ enum tag + switch
│   ├── Visit.java        # ⚡ visitor pattern (double dispatch)
│   ├── Build.java       # 🏗️ construction
│   └── Bench.java       # 📊 benchmark runner
├── run_android.sh       # build + push + run on emulator
└── SUMMARY.md

---

3. Hasil Benchmark

3.1 JVM (HotSpot)

Skenario	virtual	sealed	tagged	visitor
DeepSeq (100)	477ns	594ns	664ns	388ns
HeavyChoice (50)	76ns	135ns	162ns	78ns
NestedChoice (20)	68ns	100ns	108ns	69ns
Repetition (500x)	2,333ns	2,790ns	2,987ns	2,245ns
SimpleLiteral	11ns	17ns	17ns	11ns
Realistic	76ns	89ns	115ns	76ns

🏆 JVM: virtual ≈ visitor >> sealed > tagged

Visitor menang di DeepSeq dan Repetition, imbang di skenario lain. HotSpot ng-inline accept() → visitXxx() sampai identik kayak virtual dispatch — bahkan bisa lebih cepet karena visitor method gak perlu interface dispatch (concrete method call langsung).

3.2 Android (ART)

Skenario	virtual	sealed	tagged	visitor
DeepSeq (100)	1,475ns	1,669ns	1,594ns	1,439ns
HeavyChoice (50)	175ns	189ns	203ns	113ns
NestedChoice (20)	132ns	135ns	150ns	123ns
Repetition (500x)	7,162ns	7,373ns	7,462ns	7,123ns
SimpleLiteral	27ns	28ns	27ns	22ns
Realistic	327ns	315ns	303ns	310ns

🏆 Android: visitor dominates — menang 5/6 skenario. Tagged cuma menang tipis di Realistic (303ns vs 310ns). ART nge-JIT accept() → visitXxx() chain jadi near-native, mirip polanya sama HotSpot.

3.3 JVM vs Android Head-to-Head (visitor)

Skenario	JVM (visitor)	Android (visitor)	JVM × faster
DeepSeq (100)	388ns	1,439ns	3.7×
HeavyChoice (50)	78ns	113ns	1.4×
NestedChoice (20)	69ns	123ns	1.8×
SimpleLiteral	11ns	22ns	2.0×
Realistic	76ns	310ns	4.1×

Visitor menutup gap JVM vs Android: dari 9× (virtual) jadi 2-4× (visitor). ART lebih optimal di visitor pattern dibanding virtual dispatch.

---

4. Analisis

Kenapa JVM virtual & visitor sama cepatnya?

HotSpot punya inline caching + CHA (Class Hierarchy Analysis). Di monomorphic call site, HotSpot:

1. Profile: "oh, expr selalu VLit"
2. Guard: tambahin type check (if (expr.getClass() != VLit.class) deopt)
3. Inline: method body langsung di-inline ke call site

Untuk visitor: accept() dipanggil dengan MatchVisitor terus-menerus → HotSpot sadar ini monomorphic → inline accept() → sadar visitLit() juga monomorphic → inline juga. Hasilnya 2 layer method call jadi 0 overhead.

Kenapa sealed kalah?

instanceof Sealed$SLit harus traverse sealed class hierarchy. HotSpot gak bisa nge-inline ini jadi branchless code. Tetep harus check type tag di header object. Ini mirip kayak switch — ada branching cost.

Kenapa tagged paling bawah?

Switch int paling "jujur" — gak ada yang bisa di-inline. HotSpot meng-compile tableswitch jadi jump table, tapi tetep ada branch + table lookup overhead.

---

5. Ranking

JVM: 🥇 virtual = 🥇 visitor > 🥈 sealed > 🥉 tagged

Android ART: 🥇 visitor > 🥈 virtual ≥ sealed > 🥉 tagged

---

6. Cara Menjalankan

# JVM
javac -d out src/peg/*.java && java -cp out peg.Bench

# Android (pastikan emulator menyala)
./run_android.sh

SUMMARY_DEBUG.md

PEG AST Evaluator — 6 Pendekatan Dispatch di Go (Debug)

Tanggal: 8 Agustus 2026
Mesin: Apple M4 (arm64), Go 1.25.4
Mode: go test -bench=.

---

1. Pendekatan

#	Pendekatan	File	Mekanisme
1	Polymorphism	poly.go	Interface Expr + method Match() per tipe — itable dispatch O(1)
2	Type Switch (Expr)	switch.go	MatchSwitchExpr(e Expr, ...) — switch e.(type) pada interface value
3	*Type Switch (Expr)	switchptr.go	MatchSwitchPtr(e *Expr, ...) — switch (*e).(type) lewat pointer ke interface
4	Tagged Union (ptr)	tag.go	MatchTag(n *Node, ...) — switch int tag, rekursi via *Node
5	Tagged Union (copy)	tagcopy.go	MatchTagCopy(n Node, ...) — switch int tag, rekursi via copy 80-byte struct
6	Visitor Pattern	visitor.go	Interface Visitor + Accept() — double dispatch (Accept → VisitXxx)

---

2. Struktur Proyek

peg/
├── ast.go              # AST node types + Expr interface + Result
├── poly.go             # Polymorphic Match() methods
├── switch.go           # MatchSwitchExpr(Expr, ...)
├── switchptr.go        # MatchSwitchPtr(*Expr, ...)
├── tag.go              # Tagged union Node + MatchTag(*Node, ...)
├── tagcopy.go          # Tagged union Node + MatchTagCopy(Node, ...)
├── visitor.go          # Visitor interface + MatchVisitor + Accept methods
├── bench_helpers.go    # Tree builders (makeDeepSeq, makeHeavyChoice, dll)
├── benchmarks_export.go # Exported benchmark funcs (dipanggil main.go)
├── peg_test.go         # Tests + BenchmarkXxx stubs (delegasi)
├── cmd/bench/main.go   # Release binary runner
└── go.mod

---

3. Snippet Kunci

3.1 Polymorphism (poly.go)

func (l *Literal) Match(s string, pos Pos) (*Result, bool) {
    end := int(pos) + len(l.Val)
    if end > len(s) || s[int(pos):end] != l.Val {
        return nil, false
    }
    return &Result{Pos: Pos(end), Captures: []string{l.Val}}, true
}

func (ch *Choice) Match(s string, pos Pos) (*Result, bool) {
    for _, e := range ch.Exprs {
        if r, ok := e.Match(s, pos); ok {
            return r, true
        }
    }
    return nil, false
}

3.2 Type Switch (Expr) (switch.go)

func MatchSwitchExpr(e Expr, s string, pos Pos) (*Result, bool) {
    switch x := e.(type) {
    case *Literal:
        end := int(pos) + len(x.Val)
        if end > len(s) || s[int(pos):end] != x.Val {
            return nil, false
        }
        return &Result{Pos: Pos(end), Captures: []string{x.Val}}, true
    case *Choice:
        for _, sub := range x.Exprs {
            if r, ok := MatchSwitchExpr(sub, s, pos); ok {
                return r, true
            }
        }
        return nil, false
    }
}

3.3 Type Switch (*Expr) (switchptr.go)

func MatchSwitchPtr(e *Expr, s string, pos Pos) (*Result, bool) {
    switch x := (*e).(type) {
    case *Choice:
        for _, sub := range x.Exprs {
            // ⚠️ &sub = *Expr — interface boxing ulang + heap alloc
            if r, ok := MatchSwitchPtr(&sub, s, pos); ok {
                return r, true
            }
        }
    }
}

3.4 Tagged Union — pointer (tag.go)

type Tag int
const (
    TagLiteral Tag = iota
    TagSequence
    TagChoice
    // ...
)

type Node struct {
    Tag   Tag
    Val   string
    Exprs []*Node
    Expr  *Node
    Runes []rune
}

func MatchTag(n *Node, s string, pos Pos) (*Result, bool) {
    switch n.Tag {
    case TagChoice:
        for _, sub := range n.Exprs {   // sub = *Node (pointer)
            if r, ok := MatchTag(sub, s, pos); ok {  // pass pointer
                return r, true
            }
        }
    }
}

3.5 Tagged Union — copy (tagcopy.go)

func MatchTagCopy(n Node, s string, pos Pos) (*Result, bool) {
    switch n.Tag {
    case TagChoice:
        for _, sub := range n.Exprs {
            // ⚠️ *sub — copy 80 byte struct ke stack tiap rekursi
            if r, ok := MatchTagCopy(*sub, s, pos); ok {
                return r, true
            }
        }
    }
}

3.6 Visitor Pattern (visitor.go)

type Visitor interface {
    VisitLiteral(l *Literal, s string, pos Pos) (*Result, bool)
    VisitChoice(ch *Choice, s string, pos Pos) (*Result, bool)
}

func (ch *Choice) Accept(v Visitor, s string, pos Pos) (*Result, bool) {
    return v.VisitChoice(ch, s, pos)
}

type MatchVisitor struct{}

func (MatchVisitor) VisitChoice(ch *Choice, s string, pos Pos) (*Result, bool) {
    for _, e := range ch.Exprs {
        if r, ok := e.Accept(MatchVisitor{}, s, pos); ok {
            return r, true
        }
    }
    return nil, false
}

---

4. Skenario Benchmark

Skenario	Deskripsi
DeepSeq (100)	Sequence 100 level, semua match — minim backtracking
HeavyChoice (50)	Choice 50 cabang, cabang terakhir yang match — backtracking berat
NestedChoice (20)	Choice bersarang 20 level dalam — rekursi dalam + backtracking
Repetition (500x)	(ab)* di string ab × 500 — loop 500 iterasi
SimpleLiteral	Literal "hello" — leaf node, gak ada rekursi
Realistic	(if|while)([a-dxy]+) — grammar campuran 5 tipe node

---

5. Hasil Benchmark (Debug)

Skenario	Poly	Switch Expr	Switch *Expr	Tag	TagCopy	Visitor
DeepSeq (100)	2,789ns	2,895ns	3,868ns	2,974ns	3,141ns	2,960ns
HeavyChoice (50)	149ns	175ns	699ns	159ns	262ns	201ns
NestedChoice (20)	94ns	108ns	508ns	105ns	214ns	328ns
Repetition (500x)	13,821ns	14,109ns	14,236ns	14,094ns	14,631ns	17,743ns
SimpleLiteral	26ns	24ns	23ns	24ns	24ns	23ns
Realistic	457ns	467ns	518ns	470ns	491ns	477ns

Tag vs TagCopy Head-to-Head (Debug)

Skenario	Tag (pointer)	TagCopy (value)	Pelambatan
DeepSeq (100)	2,974ns	3,141ns	+5.6%
HeavyChoice (50)	159ns	262ns	+65% 🔥
NestedChoice (20)	105ns	214ns	+104% 🔥🔥
Repetition (500x)	14,094ns	14,631ns	+3.8%
SimpleLiteral	24ns	24ns	0%
Realistic	470ns	491ns	+4.5%

---

6. Ranking Akhir

🥇 Polymorphism    — itable dispatch, O(1), gak ada boxing ulang
🥈 Tagged Union    — switch int murni, pass pointer, nyaris setara Poly
🥉 Switch (Expr)   — type switch pada interface, overhead dikit
4️⃣ Visitor         — double dispatch, lumayan buat grammar pipih
5️⃣ TagCopy         — copy 80B struct tiap rekursi, lumayan buat tree dangkal
💀 Switch (*Expr)  — interface boxing + heap alloc tiap rekursi, brutal

---

7. Analisis

Kenapa Polymorphism Juara?

Go menggunakan itable (interface table) untuk method dispatch. Ketika kamu panggil e.Match(...), runtime tinggal lookup tabel vtable sekali lalu lompat. Gak ada branching switch, gak ada alokasi tambahan.

Kenapa Tag (pointer) Nempel Ketat?

MatchTag(n *Node, ...) switch pada n.Tag yang bertipe int. Go compiler bisa mengoptimalkan switch int menjadi jump table. Ditambah tipe *Node langsung (tanpa interface boxing), overhead dispatch hampir nol.

TagCopy vs Tag: Kenapa Copy 80 Byte Lumayan Sakit?

Tiap rekursi MatchTagCopy(*sub, ...):

• sub = *Node (8 byte pointer)
• *sub = deref pointer → copy 80 byte struct ke stack argument function
• NestedChoice 20 level = 20 × 80 byte = 1.6KB copy per path — semua di stack sih (gak heap alloc), tapi lumayan

Tetep *jauh lebih baik dari Switch(Expr) yang bikin heap alloc tiap rekursi. TagCopy "cuma" 2× lebih lambat di NestedChoice vs Switch(*Expr) yang 5×.

Kenapa Switch (*Expr) Paling Hancur?

Ini double whammy:

1. Tiap rekursi MatchSwitchPtr(&sub, ...) — sub adalah Expr (interface), &sub adalah *Expr. Go harus bikin interface baru di heap.
2. (*e).(type) — dereference pointer dulu, baru type-switch.

Akibatnya di HeavyChoice (50 cabang): 52 alloc vs 2 alloc untuk semua pendekatan lain.

Kenapa SimpleLiteral Semua Sama?

Gak ada rekursi. Compiler Go meng-inline semuanya. Hasilnya identik.

---

8. Rekomendasi

Use case	Pilih
Performa maksimal, grammar production	Polymorphism
Ingin 1 jenis struct, mudah serialisasi	Tagged Union (pointer)
Operasi terpisah per file, clean architecture	Polymorphism
Ingin ekstensibilitas (tambah operasi tanpa ubah node)	Visitor
Prototype cepet, kode sedikit	Switch (Expr)
JANGAN	*Switch (Expr)

---

9. Cara Menjalankan

# Test semua pendekatan
go test -v -run Test ./...

# Benchmark semua
go test -bench=. -benchmem -benchtime=1s -count=5 ./...

# Benchmark spesifik
go test -bench=HeavyChoice -benchmem ./...

SUMMARY_RELEASE.md

PEG AST Evaluator — Release Build Benchmark

Tanggal: 8 Agustus 2026
Mesin: Apple M4 (arm64), Go 1.25.4
Build: go build -ldflags="-s -w"
Binary: cmd/bench/peg-bench (1.8MB stripped, Mach-O arm64)

---

1. Pendekatan

#	Label	File	Mekanisme
1	Poly	poly.go	Interface Expr + method Match() per tipe, itable dispatch
2	Switch(Expr)	switch.go	MatchSwitchExpr(e Expr, ...), type switch pada interface
3	*Switch(Expr)	switchptr.go	MatchSwitchPtr(e *Expr, ...), deref pointer ke interface
4	Tag	tag.go	MatchTag(n *Node, ...), switch int, pass pointer
5	TagCopy	tagcopy.go	MatchTagCopy(n Node, ...), switch int, pass 80-byte struct by value
6	Visitor	visitor.go	Interface Visitor + Accept(), double dispatch

---

2. Hasil Release Build

Dijalankan sebagai binary mandiri via testing.Benchmark():

Skenario	Poly	Switch(Expr)	Switch(*Expr)	Tag	TagCopy	Visitor
DeepSeq (100)	2,742ns	2,768ns	3,734ns	2,793ns	2,984ns	2,834ns
HeavyChoice (50)	135ns	161ns	645ns	149ns	251ns	192ns
NestedChoice (20)	91ns	105ns	486ns	101ns	213ns	314ns
Repetition (500x)	12,973ns	13,277ns	13,181ns	13,112ns	14,046ns	13,395ns
SimpleLiteral	22ns	22ns	23ns	22ns	22ns	22ns
Realistic	432ns	447ns	497ns	444ns	464ns	453ns

Tag vs TagCopy (Release)

Skenario	Tag (ptr)	TagCopy (value)	Pelambatan
DeepSeq (100)	2,793ns	2,984ns	+6.8%
HeavyChoice (50)	149ns	251ns	+68%
NestedChoice (20)	101ns	213ns	+111%
Repetition (500x)	13,112ns	14,046ns	+7.1%
SimpleLiteral	22ns	22ns	0%
Realistic	444ns	464ns	+4.5%

Semakin dalem rekursi, TagCopy makin jeblok. Tiap MatchTagCopy(*sub, ...) copy 80 byte struct ke stack. NestedChoice 20 level = 1.6KB copy per call path. Alloc gak nambah (tetep stack, bukan heap).

Alloc Comparison

Skenario	Poly/Expr/Tag/TagCopy/Visitor	Switch(*Expr)
DeepSeq	9,296 B / 209 alloc	10,896 B / 309 alloc
HeavyChoice	48 B / 2 alloc	848 B / 52 alloc
NestedChoice	48 B / 2 alloc	688 B / 42 alloc

TagCopy gak nambah alloc — copy 80 byte tetap di stack. Bandingin Switch(*Expr) yang interface boxing = heap alloc.

---

3. Ranking

🥇 Poly          2,741ns avg  — indisputable champion
🥈 Tag(ptr)      2,774ns avg  — ~1% slower, zero overhead
🥉 Switch(Expr)  2,822ns avg  — ~3% slower, solid
4️⃣ Visitor       2,838ns avg  — ~3.5% slower
5️⃣ TagCopy       3,003ns avg  — ~9.6% slower, copy tax
💀 Switch(*Expr) 3,381ns avg  — ~23% slower, alloc kebakaran

---

4. Debug vs Release

Debug: go test -bench=. (lihat SUMMARY_DEBUG.md)
Release: go build -ldflags="-s -w" + ./peg-bench

Perbandingan Poly (ns/op)

Skenario	Debug	Release	Δ
DeepSeq (100)	2,789ns	2,742ns	−1.7%
HeavyChoice (50)	149ns	135ns	−9.4%
NestedChoice (20)	94ns	91ns	−3.2%
Repetition (500x)	13,821ns	12,973ns	−6.1%
SimpleLiteral	26ns	22ns	−15.4%
Realistic	457ns	432ns	−5.5%

Perbandingan Tag vs TagCopy (Debug vs Release)

Skenario	Tag Debug	Tag Release	TagCopy Debug	TagCopy Release
DeepSeq (100)	2,974ns	2,793ns	3,141ns	2,984ns
HeavyChoice (50)	159ns	149ns	262ns	251ns
NestedChoice (20)	105ns	101ns	214ns	213ns
Repetition (500x)	14,094ns	13,112ns	14,631ns	14,046ns
SimpleLiteral	24ns	22ns	24ns	22ns
Realistic	470ns	444ns	491ns	464ns

TagCopy vs Tag ratio stabil di debug maupun release (~2× di NestedChoice, ~68% di HeavyChoice). Overhead copy 80-byte murni dari stack, gak terpengaruh mode build.

Perbandingan Alloc (identik semua)

Skenario	Debug	Release
DeepSeq	9,296 B / 209 alloc	9,296 B / 209 alloc
HeavyChoice	48 B / 2 alloc	48 B / 2 alloc
NestedChoice	48 B / 2 alloc	48 B / 2 alloc

---

5. Cara Build & Run

# Build release binary
cd cmd/bench && go build -ldflags="-s -w" -o peg-bench .

# Run
./peg-bench

# Binary size
ls -lh peg-bench
# 1.8MB stripped

# Alternative: go test benchmark (debug mode)
go test -bench=. -benchmem -benchtime=1s -count=5 ./...

---

6. Insight

• Debug vs Release selisih <10% — compiler Go udah optimal. Build release lebih cepet dikit dari overhead test runner.
• TagCopy overhead murni dari struct copy (stack) — gak ada alloc tambahan. NestedChoice 20 level: 20 × 80 byte = 1.6KB copy. Beda sama Switch(*Expr) yang bikin heap alloc.
• *TagCopy vs Switch(Expr) beda root cause:
  • Switch(*Expr): interface boxing → heap alloc → 52 alloc di HeavyChoice
  • TagCopy: struct copy → stack only → 2 alloc (sama kayak Tag)
• SimpleLiteral semua identik — gak ada rekursi, compiler Go ng-inline semua jadi assembly yang sama.
• Tag vs Poly di Realistic: Tag (444ns) kadang menang tipis dari Poly (432ns). Switch int murni emang lebih enteng buat tree pipih.
• Binary 1.8MB stripped — semua AST (9 node type), 6 pendekatan dispatch, benchmark runner.