centau · ernisto · Mar 15, 2025 · Mar 15, 2025 · Mar 15, 2025 · Mar 15, 2025
diff --git a/src/derive.luau b/src/derive.luau
@@ -10,6 +10,7 @@ local function derive<T>(source: () -> T): () -> T
     evaluate_node(node)
 
     return function()
+        evaluate_node(node)
         push_child_to_scope(node)
         return node.cache
     end

diff --git a/src/graph.luau b/src/graph.luau
@@ -1,4 +1,5 @@
 local flags = require "./flags"
+local update_id = 0
 
 export type SourceNode<T> = {
     cache: T,
@@ -8,8 +9,11 @@ export type SourceNode<T> = {
 export type Node<T> =  {
     cache: T,
     effect:  ((T) -> T) | false,
-    cleanups: { () -> () } | false,
 
+    higher_parent_update_id: number,
+    last_eval_update_id: number,
+
+    cleanups: { () -> () } | false,
     context: { [number]: unknown } | false,
 
     owned: { Node<T> } | false,
@@ -21,6 +25,10 @@ export type Node<T> =  {
 
 local scopes = { n = 0 } :: { [number]: Node<any>, n: number } -- scopes stack
 
+local function is_similar(a: any, b: any)
+	return a == b and (type(a) ~= 'table' or table.isfrozen(a))
+end
+
 local function efn(err: string)
     local trace = debug.traceback(err, 2)
 
@@ -31,7 +39,7 @@ local function efn(err: string)
     end
 
     trace ..= "\nsource update stacktrace:"
-return trace
+    return trace
 end
 
 local function ycall<T, U>(fn: (T) -> U, arg: T): (boolean, string|U)
@@ -53,6 +61,11 @@ local function get_scope(): Node<unknown>?
     return scopes[scopes.n]
 end
 
+local function bump_update_id()
+    update_id += 1
+    return update_id
+end
+
 local function assert_stable_scope(): Node<unknown>
     local scope = get_scope()
 
@@ -145,60 +158,50 @@ local function destroy_owned<T>(node: Node<T>)
 end
 
 local update_queue = { n = 0 } :: { n: number, [number]: Node<any> }
+local queue_children_for_update
 
 local function evaluate_node<T>(node: Node<T>)
-    if flags.strict then
-        local initial_value = node.cache
+    if node.higher_parent_update_id == node.last_eval_update_id then return end
+    node.last_eval_update_id = update_id
 
-        for i = 1, 2 do
-            local cur_value = node.cache
+    local cur_value = node.cache
 
-            flush_cleanups(node)
-            destroy_owned(node)
-
-            push_scope(node)
-            local ok, new_value = ycall(node.effect :: (T) -> T, cur_value)
-            pop_scope()
-
-            if not ok then
-                table.clear(update_queue)
-                update_queue.n = 0
-                error(`effect error stacktrace\n{new_value :: string}`, 0)
-            end
-
-            node.cache = new_value :: T
-        end
-
-        return initial_value ~= node.cache
-    else
-        local cur_value = node.cache
+    flush_cleanups(node)
+    destroy_owned(node)
 
-        flush_cleanups(node)
-        destroy_owned(node)
+    push_scope(node)
+    local ok, new_value = (if flags.strict then ycall else pcall :: any)(node.effect :: (T) -> T, node.cache)
+    pop_scope()
 
-        push_scope(node)
-        local ok, new_value = pcall(node.effect :: (T) -> T, node.cache)
-        pop_scope()
+    if not ok then
+        table.clear(update_queue)
+        update_queue.n = 0
+        error(`effect error:\n{new_value}`, 0)
+    end
 
-        if not ok then
-            table.clear(update_queue)
-            update_queue.n = 0
-            error(`effect error:\n{new_value}\n`, 0)
-        end
-
-        node.cache = new_value
-        return cur_value ~= new_value
+    node.cache = new_value
+    if not is_similar(cur_value, new_value) then
+        queue_children_for_update(node)
     end
 end
 
-local function queue_children_for_update<T>(node: SourceNode<T>)
-    local i = update_queue.n
-    while node[1] do
-        i += 1
-        update_queue[i] = node[1]
-        unparent(node[1])
-    end
-    update_queue.n = i
+function queue_children_for_update<T>(node: SourceNode<T>)
+    local queue_index = update_queue.n
+    local child_index = 1
+
+    repeat
+        local child = node[child_index]
+        if not child then break end
+
+        if child.last_eval_update_id == update_id then child_index += 1; continue end
+        child.higher_parent_update_id = update_id
+
+        queue_index += 1
+        update_queue[queue_index] = child
+        unparent(child)
+    until false
+
+    update_queue.n = queue_index
 end
 
 local function get_update_queue_length()
@@ -211,9 +214,7 @@ local function flush_update_queue(from: number)
         local node = update_queue[i]
         --assert(node.effect)
 
-        if node.owner and evaluate_node(node) then
-            queue_children_for_update(node)
-        end
+        if node.owner then evaluate_node(node) end
 
         update_queue[i] = false :: any
         i += 1
@@ -227,22 +228,7 @@ local function update_descendants<T>(root: SourceNode<T>)
     queue_children_for_update(root)
 
     if flags.batch then return end
-
-    local i = n0 + 1
-    while i <= update_queue.n do
-        local node = update_queue[i]
-        --assert(node.effect)
-
-        -- check if node is still owned in case destroyed after queued
-        if node.owner and evaluate_node(node) then
-            queue_children_for_update(node)
-        end
-
-        update_queue[i] = false :: any -- false instead of nil to avoid sparse
-        i += 1
-    end
-
-    update_queue.n = n0
+    flush_update_queue(n0)
 end
 
 local function push_child_to_scope<T>(node: SourceNode<T>)
@@ -257,9 +243,11 @@ local function create_node<T>(owner: false | Node<any>, effect: false | (T) -> T
         cache = value,
         effect = effect,
         cleanups = false,
-
         context = false,
 
+        higher_parent_update_id = update_id,
+        last_eval_update_id = -1,
+
         owner = owner,
         owned = false,
 
@@ -311,6 +299,7 @@ return table.freeze {
     flush_update_queue = flush_update_queue,
     get_update_queue_length = get_update_queue_length,
     set_context = set_context,
+    bump_update_id = bump_update_id,
     scopes = scopes,
 
     q = update_queue

diff --git a/src/maps.luau b/src/maps.luau
@@ -126,6 +126,7 @@ local function values<K, VI, VO>(input: () -> Map<K, VI>, transform: (VI, () ->
 
     local function update_children(data: Map<K, VI>)
         local cur_input_cache, new_input_cache = cur_input_cache_up, new_input_cache_up
+        cur_input_cache_up = new_input_cache
 
         if flags.strict then
             local cache = {}
@@ -208,6 +209,7 @@ local function values<K, VI, VO>(input: () -> Map<K, VI>, transform: (VI, () ->
     evaluate_node(node)
 
     return function()
+        evaluate_node(node)
         push_child_to_scope(node)
         return node.cache
     end

diff --git a/src/source.luau b/src/source.luau
@@ -21,6 +21,7 @@ local function source<T>(initial_value: T): Source<T>
         end
 
         node.cache = v
+        graph.bump_update_id()
         update_descendants(node)
         return v
     end

diff --git a/src/spring.luau b/src/spring.luau
@@ -1,3 +1,4 @@
+local batch = require "./batch"
 local graph = require "./graph"
 type Node<T> = graph.Node<T>
 type SourceNode<T> = graph.SourceNode<T>
@@ -263,30 +264,33 @@ local function step_springs(dt: number)
 end
 
 local function update_spring_sources()
-    for data, output in springs do
-        local x0_123, x1_123, v_123,
-        x0_456, x1_456, v_456 =
-            data.x0_123, data.x1_123, data.v_123,
-            data.x0_456, data.x1_456, data.v_456
-
-        local max_difference = vector.max(
-            vector.abs(x0_123 - x1_123 :: any),
-            vector.abs(x0_456 - x1_456 :: any),
-            vector.abs(v_123 :: any),
-            vector.abs(v_456 :: any),
-            TOLERANCE_VECTOR
-        )
-
-        if max_difference == TOLERANCE_VECTOR then
-            -- close enough to target, unshedule spring and set value to target
-            springs[data] = nil
-            output.cache = data.source_value
-        else
-            output.cache = vec6_to_type[typeof(data.source_value)](x0_123, x0_456)
+    graph.bump_update_id()
+    batch(function()
+        for data, output in springs do
+            local x0_123, x1_123, v_123,
+            x0_456, x1_456, v_456 =
+                data.x0_123, data.x1_123, data.v_123,
+                data.x0_456, data.x1_456, data.v_456
+
+            local max_difference = vector.max(
+                vector.abs(x0_123 - x1_123 :: any),
+                vector.abs(x0_456 - x1_456 :: any),
+                vector.abs(v_123 :: any),
+                vector.abs(v_456 :: any),
+                TOLERANCE_VECTOR
+            )
+
+            if max_difference == TOLERANCE_VECTOR then
+                -- close enough to target, unshedule spring and set value to target
+                springs[data] = nil
+                output.cache = data.source_value
+            else
+                output.cache = vec6_to_type[typeof(data.source_value)](x0_123, x0_456)
+            end
+
+            update_descendants(output)
         end
-
-        update_descendants(output)
-    end
+    end)
 end
 
 return function()

diff --git a/src/switch.luau b/src/switch.luau
@@ -53,6 +53,7 @@ local function switch<T, U>(source: () -> T): (map: Map<T, ((() -> U)?)>) -> ()
         evaluate_node(node)
 
         return function()
+            evaluate_node(node)
             push_child_to_scope(node)
             return node.cache
         end

diff --git a/test/benchmarks.luau b/test/benchmarks.luau
@@ -135,28 +135,45 @@ ROOT_BENCH("update 1->1->1->1...1000 graph", function()
     end
 end)
 
--- todo: why does it hang at 1k? it didn't before
-ROOT_BENCH("update 500->1 graph", function()
+ROOT_BENCH("update 1000->1 graph", function()
     local srcs = {}
-    for i = 1, 500 do
+    for i = 1, 1000 do
+        srcs[i] = source(0)
+    end
+
+    derive(function()
+        for i = 1, 1000 do
+            srcs[i]()
+        end
+        return false
+    end)
+
+    for idx = 1, START(1000) do
+        srcs[idx](idx)
+    end
+end)
+
+ROOT_BENCH("update all parents of 1000->1 graph", function()
+    local srcs = {}
+    for i = 1, 1000 do
         srcs[i] = source(0)
     end
 
     derive(function()
-        for i = 1, 500 do
+        for i = 1, 1000 do
             srcs[i]()
         end
         return false
     end)
 
     for i = 1, START(1) do
-        for idx = 1, 500 do
+        for idx = 1, 1000 do
             srcs[idx](i)
         end
     end
 end)
 
-ROOT_BENCH("update 1000->1 graph (batched)", function()
+ROOT_BENCH("update all parents of 1000->1 graph (batched)", function()
     local srcs = {}
     for i = 1, 1000 do
         srcs[i] = source(0)

diff --git a/test/debug-update-queue.patch b/test/debug-update-queue.patch