gleam-lang/gleam

Optimise decision tree for bit arrays

Closed

#4,524 opened on Apr 29, 2025

 (9 comments) (2 reactions) (0 assignees)Rust (960 forks)batch import
help wanted

Repository metrics

Stars
 (21,417 stars)
PR merge metrics
 (Avg merge 10d 19h) (69 merged PRs in 30d)

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