DEV Community: Alexander Drozdov

Tree traversal without recursion

Alexander Drozdov — Sun, 02 Feb 2025 17:45:27 +0000

So, you've got a pretty deep hierarchy, or maybe want to have a better debugging experience without seeing all the noise created by your recursive function on the call stack. You decide to convert it (such as one below) to using an explicit stack.

interface TreeNode {
    name: string;
    children: TreeNode[];
}

function walkTreeRecursive(node: TreeNode): void {
    console.log("begin", node.name); // Pre-order
    for (const child of node.children) {
        walkTreeRecursive(child);
        console.log("yield", node.name); // In-order
    }
    console.log("end", node.name); // Post-order
}

Traversal

Let's start with the naive approach, the one you've already thought of, or are likely to see on stackoverflow. The obvious downside of it is that we can't run any in-order or post-order code. For example, we can no longer increment the index of the next child element and fetch it from the array on demand. Instead, we have to queue them all at once.

function walkTreePreNaive(rootNode: TreeNode): void {
    const stack: TreeNode[] = [rootNode];

    while (stack.length > 0) {
        const node = stack.pop()!;

        console.log("begin", node.name); // Pre-order

        // NAIVE adds all children at once,
        // therefore uses more memory than the recursive approach.
        // Siblings from parent/current levels will sit on the stack
        // and wait their turn for quite a while.
        for (const child of node.children.reverse()) {
            stack.push(child);
        }
    }
}

If we started using a stack to mimic the function call stack, we should also know about stack frames. There, local variables can be saved before switching to process any child. By introducing an index variable, we will regain all the missing functionality.

class StackFrame {
    constructor(
        public node: TreeNode,
        public childIndex: number = 0,
    ) {}
}

function walkTreeWithIndex(rootNode: TreeNode): void {
    const stack: StackFrame[] = [new StackFrame(rootNode)];

    while (stack.length > 0) {
        const frame = stack.pop()!;
        const { node } = frame;

        if (frame.childIndex === 0) {
            console.log("begin", node.name); // Pre-order
        } else {
            console.log("yield", node.name); // In-order
        }

        if (frame.childIndex < node.children.length) {
            // add self for in-order
            frame.childIndex += 1;
            stack.push(frame);
            // add child for pre-order
            stack.push(new StackFrame(node.children[frame.childIndex - 1]));
        } else {
            console.log("end", node.name); // Post-order
        }
    }
}

That's it. It's more complicated, and less readable than using recursion, but it gets the job done.

Bonus: aggregate/reduce/transform

What if a recursive function needs a return value for the result of the aggregation? No problem, just add another "local variable" to the stack-frame and a place to store the return type so the caller can access it.

 class StackFrame {
     constructor(
         public node: TreeNode,
         public childIndex: number = 0,
+        public total: number = 0,
     ) {}
 }

 function transformTreeStack(rootNode: TreeNode): void {
     const stack: StackFrame[] = [new StackFrame(rootNode)];

+    let retValue!: number;
     while (stack.length > 0) {
         const frame = stack.pop()!;
         const { node } = frame;

         if (frame.childIndex === 0) {
             console.log("begin", node.name); // Pre-order
         } else {
+            frame.total += retValue;
         }

         if (frame.childIndex < node.children.length) {
             // add self for in-order
             frame.childIndex += 1;
             stack.push(frame);
             // add child for pre-order
             stack.push(new StackFrame(node.children[frame.childIndex - 1]));
         } else {
+            retValue = frame.total + node.name.length;
         }
     }
+    console.log("total", retValue);
 }

Once the loop exits, you'll have a final aggregation done by the root node, which is stored in retValue as well.

Considering the performance implications of converting recursion to an explicit stack - The Old New Thing

devblogs.microsoft.com

Don't use rAF with WebGPU (and canvas in general)

Alexander Drozdov — Mon, 11 Dec 2023 21:14:17 +0000

So you want a pixel perfect rendering. You do a little bit of research and discover the ResizeObserver (RO) API with device-pixel-content-box. This enables setting of an integer number of screen pixels for images in canvas "swapchain".

What you also want is to run animations with a speed of screen refresh rate, using a familiar requestAnimationFrame(rAF).

Challenges arise in combining both APIs, each case presenting a downside:

Rendering in rAF while resizing in RO results in an undesirable black frame effect.
Rendering in rAF, resizing in RO, and rendering again resolves the issue but at the cost of rendering it twice!
Attempting to optimize by saving size in RO for the next rAF introduces a one-frame delay on resize. The canvas image appears stretched during resizing.

As we can see, layout phase in browsers happens after the rAF, therefore we can't know in advance that size will change and suspend the rendering in order to do it in the ResizeObserver callback instead.

Now, consider to stop using rAF for animations completely.
ResizeObserver has all the properties we want from rAF:

Operates at the screen refresh rate.
Pauses execution when the browser tab is invisible.
Allows queuing for subsequent runs within its callback, even when no resizing is occurring.

So instead of conventional loop

function rafLoop() {
  device.queue.submit([cmdBuffer.finish()]);
  requestAnimationFrame(rafLoop);
}
requestAnimationFrame(rafLoop);

Do a ResizeObserver based loop

const observer = new ResizeObserver(roLoop);

function roLoop(resizeEntries: ResizeObserverEntry[]) {
  if (canvasEl.size !== resizeEntries[0]) {
    canvasEl.size = resizeEntries[0];
    // resize depth texture, etc
  }

  device.queue.submit([cmdBuffer.finish()]);

  // unobserve to trigger the callback
  observer.unobserve(canvasEl);
  observer.observe(canvasEl, { box: "device-pixel-content-box" });
}
observer.observe(canvasEl, { box: "device-pixel-content-box" });

That's it. Now we have a perfect rendering during resizing.

Understanding Reactive Dataflow by making a Toy Implementation

Alexander Drozdov — Tue, 12 Sep 2023 18:41:30 +0000

Whenever you hear the word event you want to use reactive programming. Unlike the Observer pattern, there is no need to manage subscriptions in an imperative way. Simply by reading the variable, you subscribe to it. If the execution path changes and that variable is no longer in use, no worries, the runtime will automatically unsubscribe from it.

Let’s implement such a runtime in just 130 LOC.
To be more specific, implementations can choose the method of change propagation. A lazy, pull-based reactivity will be described here.

This is what it looks like in practice:

const ctx = new Context();
const a = Cell(ctx, 1);
const b = Cell(ctx, 2);
const sum = Computed(ctx, () => a.value + b.value);
const effect = MicrotaskEffect(ctx, () => {
    console.log(sum.value);
});

The reactivity graph is made up of nodes defined in source code, while edges are dynamic and determined at execution time.

Because we're dealing with data flow, nodes can function as a data Source, a Sink, or both. Compare this to Subject and Observer.

The edges (array of references) are bidirectional:

from Source to Sink to notify about changes;
from Sink to Source to unsubscribe.

A shared Context allows the Source to know which Sink is calling it in order to establish a bidirectional edge.

export class Context {
    currentSink: SinkLike | null = null;
}

interface SourceLike {
    removeSink(sink: SinkLike): void;
}

interface SinkLike {
    markDirty(): void;
    addSource(source: SourceLike): void;
}

Since prototype-based languages don't allow multiple inheritance, I'll use mixins to get around this.

const SourceMixin = (ctx: Context) => ({
    _ctx: ctx,
    _sinks: new Set<SinkLike>(),

    removeSink(sink: SinkLike): void {
        this._sinks.delete(sink);
    },

    _subscribeCaller(): void {
        const { currentSink } = this._ctx;
        if (currentSink) {
            this._sinks.add(currentSink);
            currentSink.addSource(this);
        }
    },

    _notifySinks(): void {
        for (const sink of this._sinks) {
            sink.markDirty();
        }
    },
});

const SinkMixin = (ctx: Context, dirty: boolean) => ({
    _ctx: ctx,
    _dirty: dirty,
    _sources: new Set<SourceLike>(),

    addSource(source: SourceLike): void {
        this._sources.add(source);
    },

    markDirty(): void {
        throw new NotImplementedError();
    },

    _capture(): boolean {
        if (this._dirty) {
            for (const source of this._sources) {
                source.removeSink(this);
            }
            this._sources.clear();
            this._ctx.currentSink = this;
            return true;
        }
        return false;
    },
});

Let's define the input node of the graph, which is often referred to as Cell, Observable, Ref, or Signal. When it gets updated, it notifies Sinks, and this propagation occurs recursively.

export const Cell = <T>(ctx: Context, value: T) => ({
    ...SourceMixin(ctx),

    _value: value,

    get value(): T {
        this._subscribeCaller();
        return this._value;
    },

    set value(value: T) {
        this._value = value;
        this._notifySinks();
    },
});

In the middle we have acyclically-connected operation nodes, typically named Computed or Transform. Upon receiving a change notification it only marks itself as dirty, while actual recomputation is performed on read.

export const Computed = <T>(ctx: Context, transformFn: () => T) => ({
    ...SourceMixin(ctx),
    ...SinkMixin(ctx, true),

    _value: undefined as T,
    _transformFn: transformFn,

    get value(): T {
        const saved = this._ctx.currentSink;
        if (this._capture()) {
            this._value = this._transformFn();
            this._ctx.currentSink = saved;
            this._dirty = false;
        }
        this._subscribeCaller();
        return this._value;
    },

    markDirty(): void {
        if (!this._dirty) {
            this._dirty = true;
            this._notifySinks();
        }
    },
});

Finally, the output node, also known as Effect or Reaction, performs side-effects. It schedules itself to run upon receiving a notification.

export const MicrotaskEffect = (ctx: Context, effectFn: () => void) => ({
    ...SinkMixin(ctx, false),

    _effectFn: effectFn,

    _run(): void {
        if (this._capture()) {
            this._effectFn();
            this._ctx.currentSink = null;
            this._dirty = false;
        }
    },

    schedule(): void {
        this.markDirty();
    },

    markDirty(): void {
        if (!this._dirty) {
            this._dirty = true;
            queueMicrotask(this._run.bind(this));
        }
    },
});

Scheduling effects asynchronously creates a natural batching of changes to input nodes. And if an effect never gets to run, nothing is recomputed along the path to it (e.g., user closes a browser tab without returning to it first).

That’s all, the toy reactivity system is finished, but some bits are missing such as performance, disposal, cycle detection.

Lastly, a playground has been set up for you to experiment with https://tsplay.dev/WvyXQm

Super Charging Fine-Grained Reactive Performance

Milo ・ Dec 1 '22

#solidjs #webdev #reactivity #performance

The Evolution of Signals in JavaScript

Ryan Carniato for This is Learning ・ Feb 27

#webdev #javascript #reactivity #signals

Surprises when taking screenshots

Alexander Drozdov — Wed, 11 Jan 2023 20:34:31 +0000

I was recently generating data and storing it into image RGB channels. My favorite "debugging" tools for this task are Shift+Alt+S and paint.net. Feeding my despair, values in Color Picker were always off. After spending 3 hours triple checking my vector math that generated data, I decided to "Save images as...", opened it, and everything was correct. It was time to figure out what was going on with the rendering in the browser.

I created a completely green image, and in the table you can see what I expected when I took the screenshot and what I actually got.

	Image	CSS `background`
Expected (paint.net)	0, 255, 0	0, 255, 0
Chrome and Edge	34, 255, 42	34, 255, 42
Firefox	32, 255, 39	0, 255, 0
Windows Photos	32, 255, 39	n/a

It is quite simple, I have a custom ICC profile for the main screen. In my mental model, this kind of post-processing should be happening OS wide in compositor, so screenshots are not affected (similar to Night light).

The reality is, every application is responsible to be color space aware individually. Browsers are aware, although for some reason colors in Chrome are different, Firefox applies it only to images.

Right now, I'm using a flag that forces Chrome to render in sRGB.