gleam-lang/gleam

Use memory arena for types when type checking

Open

#2,250 opened on Jun 29, 2023

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

Description

Currently, we represent types using a nested tree structure in which nodes are reference counted. This is at times awkward to work with, not particularly well-suited to a multithreaded compilation, and potentially slower than using an arena due to the overhead of reference, counting and memory fragmentation. Use an id based memory arena instead.

It is only during type interference and checking that we need to mutate types and to have the various different kinds of type variables, so for all other parts of the compiler, we can have a different, simpler data structure with which to represent types. Related to https://github.com/gleam-lang/gleam/issues/865

Contributor guide

Tech stack
rust
Domain
performance
Issue type
refactor
DifficultyEstimated implementation difficulty for a new contributor, from 1 for very small changes to 5 for expert-level work.
5
Estimated timeA rough time range for an experienced contributor to investigate, implement, test, and prepare a pull request.
over 1 week
Activity statusHow available the issue appears right now: fresh, active, stale, blocked, or waiting on maintainer input.
fresh
ClarityHow clearly the issue explains the expected change, acceptance criteria, and next step.
clear
Prerequisites
Rustcompiler internalsmemory management conceptstype checking algorithms
Newbie friendlinessA 1-100 score estimating how approachable this issue is for first-time contributors.
15
Research direction
Examine the current type representation in the Gleam compiler source code (likely in compiler core/src/type .rs or similar). Understand the reference counted tree structure and how it is used during type inference and checking. Review the linked issue #865 for additional context. Investigate arena allocation libraries like bumpalo or typed arena to understand how an ID based arena could replace the current approach. The issue is large scale and requires deep knowledge of the compiler's type system.