From 49b34183e3f2591c6e18d44689acb6fd70eab1bf Mon Sep 17 00:00:00 2001
From: Adam Joseph <adam@westernsemico.com>
Date: Tue, 14 Nov 2023 10:23:42 -0800
Subject: feat(tvix/eval): rewrite Thunk::force() in nonrecursive form

This commit rewrites Thunk::force() so that it is not (directly)
self-recursive.  It maintains a Vec of all the
previously-encountered thunks which point to the one it is currently
forcing, rather than recursively calling itself.

Benefits:

- Short term:

  This commit saves the cost of a round-trip through the generator
  machinery for the generators::request_force() which is removed by
  this commit.

- Medium term:

  Once a similar transformation has been applied to nix_cmp(),
  nix_add(), nix_eq(), and coerce_to_string(), those four functions,
  along with Thunk::force(), will make non-tail calls only to each
  other.  They can then be merged into a single tail-recursive
  function which does not use the generator machinery at all:

    enum Task { Cmp, Add, Eq, CoerceToString, Force};

    fn Value::walk(task:Task, v1:Value, v2:Value) {
      // ...

- Long term:

  The long-term goal here is to use generators **only for builtins**
  and [Marionette]-style remote control of the VM.  In other words:
  use `async` for things that actually involve concurrency.  Calls
  from the VM to builtins can then be blocking calls, because even
  cppnix will overflow the stack if you make a MAX_STACK_DEPTH-deep
  recursive call which passes through a builtin at every stack frame
  (e.g. `{ func = builtins.sort (a: b: ... func ...) ...}`).

  This way the inner "tight loop" of the interpreter doesn't pay the
  costs of `async` and generators.  These costs manifest in terms
  of: performance, complex nonlocal control flow, and language
  impediments (async Rust is a restricted subset of real Rust, and
  is missing things like traits).

[Marionette]: https://firefox-source-docs.mozilla.org/testing/marionette/Intro.html

Change-Id: I6179b8abb2ea0492180fcb347f37595a14665777
Reviewed-on: https://cl.tvl.fyi/c/depot/+/10039
Reviewed-by: tazjin <tazjin@tvl.su>
Tested-by: BuildkiteCI
---
 tvix/eval/src/vm/mod.rs | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

(limited to 'tvix/eval/src/vm/mod.rs')

diff --git a/tvix/eval/src/vm/mod.rs b/tvix/eval/src/vm/mod.rs
index 87ad50cda182..6aad8719e0e4 100644
--- a/tvix/eval/src/vm/mod.rs
+++ b/tvix/eval/src/vm/mod.rs
@@ -472,7 +472,7 @@ impl<'o> VM<'o> {
 
                         self.push_call_frame(span, frame);
                         self.enqueue_generator("force", gen_span.clone(), |co| {
-                            thunk.force(co, gen_span)
+                            Thunk::force(thunk, co, gen_span)
                         });
 
                         return Ok(false);
-- 
cgit 1.4.1