Merge `FallbackImmediate` and `Fixpoint` code paths by MichaReiser · Pull Request #1063 · salsa-rs/salsa

MichaReiser · 2026-01-11T10:23:48Z

Summary

This PR removes most special casing of FallbackImmediate and, instead, integrates it into the normal Fixpoint code. Not only should this fix the caching issues that FallbackImmediate has today, it also reduces overall complexity and makes it easier to make changes to how we handle cycles in Salsa (no need to update two completely different implementations).

This PR preserves the existing FallbackImmediate behavior where all heads participating in a query use their fallback value (and not just the cycle heads). I now believe that this behavior is essential for deterministic outputs, as pointed out by Carl in #798 (comment)

See

salsa/src/function/execute.rs

Lines 96 to 107 in b6398ec

    
           // If we're in the middle of a cycle and we have a fallback, use it instead. 
        
           // Cycle participants that don't have a fallback will be discarded in 
        
           // `validate_provisional()`. 
        
           let cycle_heads = std::mem::take(cycle_heads); 
        
           let active_query = 
        
               zalsa_local.push_query(database_key_index, IterationCount::initial()); 
        
           new_value = C::cycle_initial(db, id, C::id_to_input(zalsa, id)); 
        
           completed_query = active_query.pop(); 
        
           // We need to set `cycle_heads` and `verified_final` because it needs to propagate to the callers. 
        
           // When verifying this, we will see we have fallback and mark ourselves verified. 
        
           completed_query.revisions.set_cycle_heads(cycle_heads); 
        
           completed_query.revisions.verified_final = AtomicBool::new(false);

This PR is based on top of #1062

One difference worth mentioning is that we now overapproximate the dependencies for queries with cycle_result, keeping all dependencies rather than just those up to the initial cycle. This is fine as it is, and I'm not aware of an easy way to remember when we hit the cycle and which dependencies we've seen up to this point.

netlify · 2026-01-11T10:24:30Z

✅ Deploy Preview for salsa-rs canceled.

Name	Link
🔨 Latest commit	`df8855b`
🔍 Latest deploy log	https://app.netlify.com/projects/salsa-rs/deploys/6972232adfa53f000882cfa2

MichaReiser · 2026-01-11T10:54:36Z

src/function/execute.rs

+            // For Fixpoint, ask the recovery function what value to use and check convergence.
+            let value_converged = if C::CYCLE_STRATEGY == CycleRecoveryStrategy::FallbackImmediate {
+                // Use the fallback value instead of the computed value.
+                new_value = C::cycle_initial(db, id, C::id_to_input(zalsa, id));


I opted for calling C::cycle_initial here again because it is easier than Cloning (would require a new method on C that panics for all other recovery strategies or we make CycleRecoverStrategy a trait). But I (or someone else ;)) can look into cloning if that's desired or, what would even be better, adding an API that allows us to "take" a value from a Memo (which would also allow us to pass an owned value to recover_from_cycle)

Having a way to take the value would also be nice in fetch_cold_cycle where we need to call remove_all_except (requiring Atomics) to remove the cycle heads from the previous iteration because we can't create a new memo with the same value but slightly different metadata.

I tried to implement this once but it touches on Salsa parts that I'm not at all familiar with, which is why I ended up going for atomics

MichaReiser · 2026-01-11T10:55:08Z

src/function/fetch.rs

-        // check if there's a provisional value for this query
-        // Note we don't `validate_may_be_provisional` the memo here as we want to reuse an
-        // existing provisional memo if it exists
-        let memo_guard = self.get_memo_from_table_for(zalsa, id, memo_ingredient_index);


I moved this into the cycle handling branch to help the compiler eliminate it for queries without cycle handling

MichaReiser · 2026-01-11T10:58:08Z

CC: @ChayimFriedman2

MichaReiser · 2026-01-11T10:59:25Z

tests/cycle_fallback_immediate.rs

 }

-#[salsa::tracked]
+#[salsa::tracked(cycle_result=two_queries_cycle_result)]


The test works regardless of whether we add cycle handling here but adding cycle handling is "more correct" because two_queries2 requires cycle handling if it is called before two_queries1

codspeed-hq · 2026-01-21T14:21:42Z

Merging this PR will degrade performance by 6.91%

❌ 2 regressed benchmarks
✅ 11 untouched benchmarks

⚠️ Please fix the performance issues or acknowledge them on CodSpeed.

Performance Changes

	Benchmark	`BASE`	`HEAD`	Efficiency
❌	`amortized[InternedInput]`	2.2 µs	2.3 µs	-5.12%
❌	`new[InternedInput]`	4.3 µs	4.6 µs	-6.91%

_{Comparing MichaReiser:integrate-fallback-immediate-into-fixpoint (df8855b) with master (93f1c6a)}

carljm

Looks good to me, thank you.

ChayimFriedman2 · 2026-02-12T00:11:22Z

We have reports (rust-lang/rust-analyzer#21610 (comment)) that this PR made rust-analyzer constantly use high CPU and emit Salsa warnings.

ibraheemdev · 2026-02-12T00:34:13Z

Micha is out until March, and I unfortunately am not very familiar with usage of FallbackImmediate. I believe #1061 depended on this PR, so it might not be very easy to revert.

MichaReiser changed the title ~~integrate fallback immediate into fixpoint~~ Merge FallbackImmediate and Fixpoint code paths Jan 11, 2026

MichaReiser mentioned this pull request Jan 11, 2026

Lower FallbackImmediate to Fixpoint #1064

Closed

MichaReiser marked this pull request as ready for review January 11, 2026 10:34

MichaReiser mentioned this pull request Jan 11, 2026

Use same locking mechanism for fallback immediate as for fixpoint cycles #1059

Closed

MichaReiser commented Jan 11, 2026

View reviewed changes

MichaReiser requested a review from Veykril January 11, 2026 10:57

MichaReiser commented Jan 11, 2026

View reviewed changes

MichaReiser force-pushed the integrate-fallback-immediate-into-fixpoint branch from a0ea2ed to 5b3b99b Compare January 19, 2026 14:32

MichaReiser requested a review from carljm January 19, 2026 14:32

MichaReiser mentioned this pull request Jan 20, 2026

Fix out-of-order verification of cycle head dependencies #1061

Merged

MichaReiser force-pushed the integrate-fallback-immediate-into-fixpoint branch from 5b3b99b to 5c376e2 Compare January 21, 2026 14:20

carljm reviewed Jan 21, 2026

View reviewed changes

MichaReiser added 3 commits January 22, 2026 14:12

Merge FallbackImmediate and Fixpoint code paths

13998a3

Add comment

296567f

Disable book worfklow for forks

e82b78e

MichaReiser force-pushed the integrate-fallback-immediate-into-fixpoint branch from 5c376e2 to e82b78e Compare January 22, 2026 13:12

Fix merge conflicts

df8855b

MichaReiser enabled auto-merge January 22, 2026 13:20

MichaReiser added this pull request to the merge queue Jan 22, 2026

Merged via the queue into salsa-rs:master with commit 186f83b Jan 22, 2026
13 of 14 checks passed

MichaReiser deleted the integrate-fallback-immediate-into-fixpoint branch January 22, 2026 13:34

github-actions bot mentioned this pull request Jan 22, 2026

chore: release v0.26.0 #1043

Merged

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Merge `FallbackImmediate` and `Fixpoint` code paths#1063

Merge `FallbackImmediate` and `Fixpoint` code paths#1063
MichaReiser merged 4 commits intosalsa-rs:masterfrom
MichaReiser:integrate-fallback-immediate-into-fixpoint

MichaReiser commented Jan 11, 2026 •

edited

Loading

Uh oh!

netlify bot commented Jan 11, 2026 •

edited

Loading

Uh oh!

MichaReiser Jan 11, 2026

Uh oh!

MichaReiser Jan 11, 2026

Uh oh!

MichaReiser Jan 11, 2026

Uh oh!

MichaReiser commented Jan 11, 2026

Uh oh!

MichaReiser Jan 11, 2026

Uh oh!

codspeed-hq bot commented Jan 21, 2026 •

edited

Loading

Uh oh!

carljm left a comment

Uh oh!

Uh oh!

ChayimFriedman2 commented Feb 12, 2026

Uh oh!

ibraheemdev commented Feb 12, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

	// If we're in the middle of a cycle and we have a fallback, use it instead.
	// Cycle participants that don't have a fallback will be discarded in
	// `validate_provisional()`.
	let cycle_heads = std::mem::take(cycle_heads);
	let active_query =
	zalsa_local.push_query(database_key_index, IterationCount::initial());
	new_value = C::cycle_initial(db, id, C::id_to_input(zalsa, id));
	completed_query = active_query.pop();
	// We need to set `cycle_heads` and `verified_final` because it needs to propagate to the callers.
	// When verifying this, we will see we have fallback and mark ourselves verified.
	completed_query.revisions.set_cycle_heads(cycle_heads);
	completed_query.revisions.verified_final = AtomicBool::new(false);

Conversation

MichaReiser commented Jan 11, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Summary

Uh oh!

netlify bot commented Jan 11, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

✅ Deploy Preview for salsa-rs canceled.

Uh oh!

MichaReiser Jan 11, 2026

Choose a reason for hiding this comment

Uh oh!

MichaReiser Jan 11, 2026

Choose a reason for hiding this comment

Uh oh!

MichaReiser Jan 11, 2026

Choose a reason for hiding this comment

Uh oh!

MichaReiser commented Jan 11, 2026

Uh oh!

MichaReiser Jan 11, 2026

Choose a reason for hiding this comment

Uh oh!

codspeed-hq bot commented Jan 21, 2026 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Merging this PR will degrade performance by 6.91%

Performance Changes

Uh oh!

carljm left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

ChayimFriedman2 commented Feb 12, 2026

Uh oh!

ibraheemdev commented Feb 12, 2026

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

4 participants

MichaReiser commented Jan 11, 2026 •

edited

Loading

netlify bot commented Jan 11, 2026 •

edited

Loading

codspeed-hq bot commented Jan 21, 2026 •

edited

Loading