镜像站点 · 本页由第三方 GitHub 只读镜像提供,非 GitHub 官方站点,不接受任何登录或凭据输入。前往 github.com
Skip to content

Bound function chains cost quadratic memory: each bind flattens "bound " + the target's name #942

Closed

Description

@glennmichael123

Parent: #934 (robustness: deep structures crash instead of throwing RangeError)
Found while reproducing #940, where a 100,000-link bound chain exhausted a 3 GB ceiling before it could reach the stack defect.

Measured

var f = function g() {}; for (var i = 0; i < n; i++) f = f.bind(null); f.name.length, run with test262 --eval (ReleaseFast, 81b49b1) and node v24.4.1, peak RSS from /usr/bin/time -l:

binds zig-js result zig-js peak RSS node result node peak RSS
4,000 24001 60 MB 24001 42 MB
16,000 96001 755 MB 96001 48 MB
64,000 — >3 GB (killed) 384001 ~50 MB
100,000 — >3 GB (killed) 600001 ~50 MB

Both engines agree on the answer; only the storage differs. zig-js is quadratic, node is flat.

Cause

makeBound (src/interpreter.zig:9688) implements SetFunctionName eagerly against flat string storage:

const bound_name = try std.fmt.allocPrint(scratch.allocator(), "bound {s}", .{base_name});
try obj.setOwn(self.arena, self.root_shape, "name", try Value.strAlloc(self.arena, bound_name));

Each link's name is the previous name plus six bytes, materialized in full, so a chain of N binds stores sum(6i) = O(N^2) bytes — 96 KB of live name text at 16,000 links, but ~750 MB of arena traffic to build it. V8 keeps the concatenation as a rope and pays O(N).

Get(target, "name") is observable (step 9 of 20.2.3.2), so the read has to stay eager; what does not have to be eager is flattening the result. Options: a concatenated-string representation for this path, or storing the bound name lazily as (prefix count, base string) behind the name own property — it is { writable: false, enumerable: false, configurable: true }, and its value is only materialized when read.

Done

A chain of 100,000 binds reports the same name as node with memory linear in the chain length, pinned by a case that measures the growth rather than asserting a constant.

Activity

  1. chrisbbreuer commented on Sep 21, 2026

    @chrisbbreuer
    Member

    Implemented and pushed in 497eb4c2 (fix(function): keep bound name chains linear (#942)).

    The observable Get(target, "name") remains eager and in the same order. The resulting name is still a real flat immutable StringCell; repeated "bound " prefixes now use refcounted geometric prepend blocks. Each deeper bind consumes existing headroom, and block exhaustion copies once into the next power-of-two block. Branches reuse already-published bytes without rewriting them. Managed cells account for each shared block once and release it when the final referring string dies.

    ReleaseFast /usr/bin/time -l measurements on the issue workload:

    binds result peak RSS
    4,000 24,001 14.8 MB
    16,000 96,001 23.5 MB
    64,000 384,001 58.0 MB
    100,000 600,001 84.1 MB

    This replaces the prior 755 MB at 16,000 and >3 GB/killed at 64,000/100,000 with linear growth.

    Validation:

    • pinned 100,000-prefix allocator test: geometric backing below 4x final name length and total requested bytes below a fixed linear ceiling;
    • end-to-end 100,000-bind JS unit: exact 600,001-character name in 1.1 s (Debug);
    • GC lifecycle: live 10,000-link backing stays below 256 KiB and returns exactly to baseline after the last root is cleared;
    • allocation-failure rollback covers every new allocation boundary;
    • concurrent same-source derivation passes normally and under TSan;
    • forced tree-walker and VM probes preserve configurable-name, non-string-name, and descriptor behavior;
    • test/built-ins/Function/prototype/bind: 100 pass before -> 100 pass after, 0 flips;
    • full sharded unit suite: 2,442 passed, 1 skipped, 0 failed, 0 leaked. An initial run hit an unrelated NondeterministicMemoryUsage result in an existing allocation-failure test; that case passed twice alone, and the complete repeat was clean.
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    No labels
    No labels

    Type

    No type

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions