rust-lang / rust-lang/rust

Exponential compile time and high memory usage with nested const evaluation

Open
#150,061 5 comments 0 reactions 0 assignees View on GitHub

Nobody has claimed this yet.

A-const-eval C-bug I-compilemem I-compiletime needs-triage T-compiler
Dominant language
Rust
Stars
119k
Forks
16.1k
PR metrics pending

Description

I'm experimenting with ways to go from a nested arbitrary type tuple to a nested tuple only containing unique types. For example (u8, (u8, (u16,))) should be "converted" to (u8, (u16,)). The code below leads to exponential compile time and high memory usage.

I tried this code:

pub trait ConstTypeId {
    const TYPE_ID: u128;
}

impl ConstTypeId for u8 {
    const TYPE_ID: u128 = 0;
}

impl ConstTypeId for u16 {
    const TYPE_ID: u128 = 1;
}

pub trait Contained<T> {
    const CONTAINED: bool;
}

impl<T, U> Contained<T> for (U,)
where
    T: ConstTypeId,
    U: ConstTypeId,
{
    const CONTAINED: bool = <U as ConstTypeId>::TYPE_ID == <T as ConstTypeId>::TYPE_ID;
}

impl<T, U, V> Contained<T> for (U, V)
where
    T: ConstTypeId,
    U: ConstTypeId,
    V: Contained<T>,
{
    const CONTAINED: bool = {
        let a = <U as ConstTypeId>::TYPE_ID == <T as ConstTypeId>::TYPE_ID;
        let b = <V as Contained<T>>::CONTAINED;
        a | b
    };
}

pub trait Chained<T, const CONTAINED: bool> {
    type Result;
}

impl<T, U> Chained<T, true> for U {
    type Result = U;
}

impl<T, U> Chained<T, false> for U {
    type Result = (T, U);
}

#[macro_export]
macro_rules! unique_type_tuple {
    ($first_type:ty, $($rest:ty),* $(,)?) => {
        <$crate::unique_type_tuple!($($rest),*) as $crate::Chained<$first_type, { <$crate::unique_type_tuple!($($rest),*) as $crate::Contained<$first_type>>::CONTAINED }>>::Result
    };
    ($current_type:ty $(,)?) => {
        ($current_type,)
    };
}

fn main() {
    type Bar = unique_type_tuple!(
        u8, u16, u8, u8, u16, u8, u8, u16, u8, u8, u16, u8, u8, u16, u8, u8, u16, u8, u8,
        u16,
        //u8, u8, u16, u8, u8, u16, u8, u8, u16, u8, u8, u16, u8,
    );
    println!("Bar: {:#?}", std::any::type_name::<Bar>());
}

I expected to see this happen: Fast compilation, unremarkable memory usage.

Instead, this happened: Exponential compilation times and high memory usage.

Meta

rustc --version --verbose:

> rustc +nightly --version --verbose
rustc 1.94.0-nightly (21ff67df1 2025-12-15)
binary: rustc
commit-hash: 21ff67df15329dd7548ccba54b6c6ae9a562124f
commit-date: 2025-12-15
host: x86_64-unknown-linux-gnu
release: 1.94.0-nightly
LLVM version: 21.1.8

Using the next solver increases the compile time and memory usage.

> RUSTFLAGS="-Znext-solver -Ztime-passes" cargo +nightly build
   Compiling tuple_deduple_hangs_compiler v0.1.0 ([...])
time:   0.000; rss:   37MB ->   39MB (   +2MB)  parse_crate
time:   0.000; rss:   40MB ->   40MB (   +0MB)  incr_comp_prepare_session_directory
time:   0.000; rss:   40MB ->   40MB (   +0MB)  incr_comp_garbage_collect_session_directories
time:   0.000; rss:   45MB ->   45MB (   +0MB)  crate_injection
time:  12.525; rss:   45MB -> 3511MB (+3466MB)  expand_crate
time:   0.000; rss: 3511MB -> 3511MB (   +0MB)  check_unused_macros
time:  12.526; rss:   45MB -> 3511MB (+3466MB)  macro_expand_crate
time:   0.098; rss: 3511MB -> 3511MB (   +0MB)  AST_validation
time:   0.166; rss: 3511MB -> 3419MB (  -92MB)  finalize_macro_resolutions
time:   1.931; rss: 3419MB -> 3969MB ( +551MB)  late_resolve_crate
time:   0.098; rss: 3969MB -> 3970MB (   +0MB)  resolve_check_unused
time:   0.194; rss: 3970MB -> 3970MB (   +0MB)  resolve_postprocess
time:   2.390; rss: 3511MB -> 3970MB ( +459MB)  resolve_crate
time:   0.095; rss: 3795MB -> 3795MB (   +0MB)  write_dep_info
time:   0.098; rss: 3795MB -> 3795MB (   +0MB)  complete_gated_feature_checking
time:   0.241; rss: 4899MB -> 3803MB (-1097MB)  drop_ast
time:   0.057; rss: 3239MB -> 3240MB (   +0MB)  looking_for_entry_point
time:   0.000; rss: 3240MB -> 3240MB (   +0MB)  looking_for_derive_registrar
time:   0.000; rss: 3240MB -> 3240MB (   +0MB)  unused_lib_feature_checking
time:   0.412; rss: 3239MB -> 3240MB (   +0MB)  misc_checking_1
time:   0.002; rss: 3240MB -> 3244MB (   +4MB)  coherence_checking
time:   0.000; rss: 3244MB -> 3244MB (   +0MB)  emit_ast_lowering_delayed_lints
time:  47.638; rss: 3240MB -> 9020MB (+5780MB)  type_check_crate
time:   0.261; rss: 9020MB -> 9022MB (   +2MB)  MIR_borrow_checking
time:   0.189; rss: 9037MB -> 9037MB (   +0MB)  module_lints
time:   0.190; rss: 9037MB -> 9037MB (   +0MB)  lint_checking
time:   0.195; rss: 9037MB -> 9037MB (   +0MB)  privacy_checking_modules
time:   0.640; rss: 9022MB -> 9037MB (  +15MB)  misc_checking_3
time:   0.000; rss: 9037MB -> 9037MB (   +0MB)  monomorphization_collector_root_collections
time:   0.005; rss: 9037MB -> 9044MB (   +6MB)  monomorphization_collector_graph_walk
time:   0.000; rss: 9044MB -> 9044MB (   +0MB)  partition_and_assert_distinct_symbols
time:   0.000; rss: 9048MB -> 9050MB (   +2MB)  write_allocator_module
time:   0.076; rss: 9050MB -> 9167MB ( +117MB)  codegen_to_LLVM_IR
time:   0.100; rss: 9037MB -> 9167MB ( +130MB)  codegen_crate
time:   0.000; rss: 9167MB -> 9167MB (   +0MB)  assert_dep_graph
time:   0.000; rss: 9167MB -> 9167MB (   +0MB)  check_dirty_clean
time:   0.000; rss: 9167MB -> 9168MB (   +0MB)  incr_comp_persist_dep_graph
time:   0.078; rss: 9057MB -> 9167MB ( +110MB)  LLVM_passes
time:   0.979; rss: 9168MB -> 9370MB ( +202MB)  encode_query_results
time:   1.488; rss: 9168MB -> 9180MB (  +12MB)  incr_comp_serialize_result_cache
time:   1.488; rss: 9168MB -> 9180MB (  +12MB)  incr_comp_persist_result_cache
time:   1.488; rss: 9167MB -> 9180MB (  +13MB)  serialize_dep_graph
time:   0.000; rss: 2814MB -> 2814MB (   +0MB)  finish_ongoing_codegen
time:   0.000; rss: 2814MB -> 2814MB (   +0MB)  serialize_work_products
time:   0.000; rss: 2604MB -> 2604MB (   +0MB)  incr_comp_finalize_session_directory
time:   0.103; rss: 2605MB -> 2605MB (   +0MB)  run_linker
time:   0.103; rss: 2604MB -> 2605MB (   +1MB)  link_binary
time:   0.103; rss: 2604MB -> 2605MB (   +1MB)  link_crate
time:   0.110; rss: 2814MB -> 2605MB ( -209MB)  link
time:  71.065; rss:   27MB ->  108MB (  +81MB)  total
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 1m 11s

> RUSTFLAGS="-Ztime-passes" cargo +nightly build
   Compiling tuple_deduple_hangs_compiler v0.1.0 ([...])
time:   0.000; rss:   37MB ->   38MB (   +2MB)  parse_crate
time:   0.000; rss:   40MB ->   40MB (   +0MB)  incr_comp_prepare_session_directory
time:   0.000; rss:   40MB ->   40MB (   +0MB)  incr_comp_garbage_collect_session_directories
time:   0.000; rss:   45MB ->   45MB (   +0MB)  crate_injection
time:  13.523; rss:   45MB -> 3506MB (+3461MB)  expand_crate
time:   0.000; rss: 3506MB -> 3506MB (   +0MB)  check_unused_macros
time:  13.523; rss:   45MB -> 3506MB (+3461MB)  macro_expand_crate
time:   0.099; rss: 3506MB -> 3506MB (   +0MB)  AST_validation
time:   0.169; rss: 3506MB -> 3414MB (  -92MB)  finalize_macro_resolutions
time:   2.032; rss: 3414MB -> 3970MB ( +555MB)  late_resolve_crate
time:   0.096; rss: 3970MB -> 3970MB (   +0MB)  resolve_check_unused
time:   0.190; rss: 3970MB -> 3970MB (   +0MB)  resolve_postprocess
time:   2.487; rss: 3506MB -> 3970MB ( +464MB)  resolve_crate
time:   0.096; rss: 3795MB -> 3795MB (   +0MB)  write_dep_info
time:   0.100; rss: 3796MB -> 3796MB (   +0MB)  complete_gated_feature_checking
time:   0.266; rss: 4900MB -> 3764MB (-1135MB)  drop_ast
time:   0.068; rss: 3201MB -> 3201MB (   +0MB)  looking_for_entry_point
time:   0.000; rss: 3201MB -> 3202MB (   +0MB)  looking_for_derive_registrar
time:   0.000; rss: 3196MB -> 3196MB (   +0MB)  unused_lib_feature_checking
time:   0.435; rss: 3201MB -> 3196MB (   -5MB)  misc_checking_1
time:   0.001; rss: 3196MB -> 3198MB (   +2MB)  coherence_checking
time:   0.000; rss: 3198MB -> 3198MB (   +0MB)  emit_ast_lowering_delayed_lints
time:  35.452; rss: 3196MB -> 6715MB (+3519MB)  type_check_crate
time:   0.263; rss: 6715MB -> 6720MB (   +5MB)  MIR_borrow_checking
time:   0.184; rss: 6735MB -> 6741MB (   +6MB)  module_lints
time:   0.184; rss: 6735MB -> 6741MB (   +6MB)  lint_checking
time:   0.191; rss: 6741MB -> 6738MB (   -3MB)  privacy_checking_modules
time:   0.627; rss: 6720MB -> 6738MB (  +18MB)  misc_checking_3
time:   0.000; rss: 6738MB -> 6739MB (   +0MB)  monomorphization_collector_root_collections
time:   0.005; rss: 6739MB -> 6739MB (   +0MB)  monomorphization_collector_graph_walk
time:   0.000; rss: 6739MB -> 6739MB (   +0MB)  partition_and_assert_distinct_symbols
time:   0.000; rss: 6741MB -> 6743MB (   +2MB)  write_allocator_module
time:   0.002; rss: 6744MB -> 6758MB (  +14MB)  codegen_to_LLVM_IR
time:   0.024; rss: 6738MB -> 6758MB (  +20MB)  codegen_crate
time:   0.000; rss: 6758MB -> 6758MB (   +0MB)  assert_dep_graph
time:   0.000; rss: 6758MB -> 6758MB (   +0MB)  check_dirty_clean
time:   0.000; rss: 6758MB -> 6759MB (   +0MB)  incr_comp_persist_dep_graph
time:   0.003; rss: 6751MB -> 6756MB (   +5MB)  LLVM_passes
time:   0.747; rss: 6759MB -> 6921MB ( +162MB)  encode_query_results
time:   1.244; rss: 6759MB -> 6758MB (   -1MB)  incr_comp_serialize_result_cache
time:   1.244; rss: 6759MB -> 6758MB (   -1MB)  incr_comp_persist_result_cache
time:   1.245; rss: 6758MB -> 6758MB (   -1MB)  serialize_dep_graph
time:   0.000; rss: 2299MB -> 2299MB (   +0MB)  finish_ongoing_codegen
time:   0.000; rss: 2299MB -> 2299MB (   +0MB)  serialize_work_products
time:   0.097; rss: 2299MB -> 2299MB (   +0MB)  run_linker
time:   0.097; rss: 2299MB -> 2299MB (   +1MB)  link_binary
time:   0.097; rss: 2299MB -> 2299MB (   +1MB)  link_crate
time:   0.097; rss: 2299MB -> 2299MB (   +1MB)  link
time:  59.798; rss:   27MB ->  105MB (  +78MB)  total
    Finished `dev` profile [unoptimized + debuginfo] target(s) in 59.85s

Contributor guide

Open the contributing guide

First steps

  1. Read the whole issue, then the project's contributing guide.
  2. Comment on the issue to say you are picking it up — it saves two people doing the same work.
  3. Fork the repository and make your change on a branch.
  4. Open a pull request that references the issue number.

Research direction

Reproduce the supplied nested-tuple example with nightly rustc and collect the reported timing and memory data. Start by comparing the macro_expand_crate and type_check_crate stages, which show the largest costs in the logs. Done means the example no longer exhibits exponential compilation time or extreme memory growth, with a regression test covering the behavior.

Written by the indexing model from the issue text.

Assessment

Tech stack
rust
Domain
compilers, performance
Issue type
Bug
Difficulty
4/5
Estimated time
3-5 days
Activity status
Stale
Clarity
Mostly clear
Newbie friendliness
25/100

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.