gleam-lang/gleam

Optimise decision tree for bit arrays

Open

#4524 opened on Apr 29, 2025

View on GitHub
 (9 comments) (2 reactions) (0 assignees)Rust (21,417 stars) (960 forks)batch import
help wanted

Description

Right now when generating code for bit arrays we might end up doing something like this:

if (size > n) {
  if (size === n + 10) {
    // ...
  } else {
    // body_1
  }
} else {
  // body_1
}

If all else branches have the same body it would be really nice to make the tree shorter and skip the first check entirely:

if (size === n + 10) {
  // ...
} else {
  // body_1
}

This might be quite challenging and could require reading more on how to reduce the tree size: this could be a very good resource for that https://user.it.uu.se/~kostis/Papers/JFP_06.pdf

Contributor guide

Tech stack
rust
Domain
performance
Issue type
performance
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
4
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
3-5 days
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
active
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
clear
Prerequisites
Familiarity with decision tree optimizationGleam compiler internalsPaper on tree reduction (referenced)
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
20
Research direction
The issue describes an optimization opportunity when generating code for bit arrays. The goal is to reduce decision tree size by merging identical branches. The referenced paper (https://user.it.uu.se/~kostis/Papers/JFP 06.pdf) provides theory on tree reduction. To start, explore the code generation for bit arrays in the Gleam compiler, likely in files related to code generation or pattern matching compilation. Look for where the decision tree is built and attempt to implement the described merging.