Iteration consuming the heap is maybe too surprising

[jedwards1211]

It's good the changelog documents this behavior, but I had mistakenly assumed iterating Symbol.iterator would just read out the raw backing array in unsorted order.

My assumption had a significant consequence, I had a debug route for fetching the internal state of some algorithms out of my server, and I was including [...this.heap] in the response, and after awhile I realized that requesting this internal state was accidentally emptying the queues.

Making this library have an interface familiar to users of libraries in other languages is only convenient up to the point that it goes against the conventions JS users are used to. And I think iteration not consuming underlying data is one of those conventions in JS. I'm aware of async iteration that consumes underlying data (e.g. async iterating a ReadableStream) but not sync iteration. I don't think the Python heapq behavior should win over conventions.

[ignlg]

Thank you for your feedback, @jedwards1211.

You raise a valid point. I have never been entirely comfortable with it, as it can feel like a dark pattern.

This behavior occurs because it is not straightforward to consume a binary tree in the expected order without recalculating the new top after a pop operation. Recalculating the new top is the core of the behavior when popping the top value. For this reason, the iteration process functions similarly to using pop() in a for loop with an array.

At the moment, I don't have a solid solution. Some thoughts:

• Improving the documentation alerting more about this behavior.
• Forcefully cloning the heap before it is consumed is an even darker pattern, as the performance and memory impact are high.
• Removing the iterator would be a breaking change for projects using it, so this is not an option.

Typically, I don't need to maintain the binary tree structure since values are consumed and, in the event of a NACK or error, are pushed back into the tree. I believe this is the right approach. However, when it’s essential to keep the structure intact, I recommend cloning, which is why the .clone() method exists.

Do you have any ideas for an efficient way to create a more intuitive behavior?

[jedwards1211]

I guess my situation is kind of unique because I just needed to send a json array of queue entries over the wire (in an RPC method for debugging the internal state of the operations). I naively assumed the default iterator would just iterate over the internal array as is, without fully sorting it.

If I were designing a heap library from scratch my preference would probably be no default iterator method, and instead .unsortedIterator() and .consumingIterator() methods to make the behavior crystal clear.

Another option, which would be nice from an API perspective but more tricky to implement, would be to have [Symbol.iterator](options?: { consume?: boolean }) that always iterates in order, whether consuming or not. An optional argument doesn't conflict with the JS iterator protocol afaik. Sorting the heap in place without popping adds a bit of complexity though, since it's slightly different from the usual heap pop algorithm (if you're open to this I'm happy to code it up).

I can understand the goal of imitating familiar APIs from other languages though... at the time I was miffed that it clashed with JS expectations.

[jedwards1211]

As far as what might have made me more likely to notice the documented behavior when skimming, maybe a warnings section and a table of contents at the top of the readme, I could PR that

[ignlg]

Thank you for the great suggestion to add a warnings section and a table of contents to improve the visibility of important behaviors. I appreciate your detailed feedback.

Could you submit a pull request (PR) to implement these documentation improvements? Your experience would ensure the warnings are clear and easy for other developers to find.

I'm also interested in your suggestion for the optional consume parameter for iteration. I can review a PR for that as well if you wish to pursue it.

[jedwards1211]

@ignlg sure! I'm about to go on a trip so I could probably submit the documentation PR tomorrow but I'll have to wait until after the 8th to work on iterating in order without consuming. Feel free to bug me if I forget :)

[ericbstie]

Thank you for your feedback, @jedwards1211.

You raise a valid point. I have never been entirely comfortable with it, as it can feel like a dark pattern.

This behavior occurs because it is not straightforward to consume a binary tree in the expected order without recalculating the new top after a pop operation. Recalculating the new top is the core of the behavior when popping the top value. For this reason, the iteration process functions similarly to using pop() in a for loop with an array.

At the moment, I don't have a solid solution. Some thoughts:

• Improving the documentation alerting more about this behavior.
• Forcefully cloning the heap before it is consumed is an even darker pattern, as the performance and memory impact are high.
• Removing the iterator would be a breaking change for projects using it, so this is not an option.

Typically, I don't need to maintain the binary tree structure since values are consumed and, in the event of a NACK or error, are pushed back into the tree. I believe this is the right approach. However, when it’s essential to keep the structure intact, I recommend cloning, which is why the .clone() method exists.

Do you have any ideas for an efficient way to create a more intuitive behavior?

I just wanted to chime in with a suggestion regarding point 2. You could sort the underlying heap array and delegate the iterator yield to the underlying array:

*[Symbol.iterator]() {
    yield* this.heapArray.sort(this.comparator)
 }

This will not copy the array, nor consume the underlying array, and it maintains the heap invariant. The time complexity should be the same O(n log n) and running a benchmark shows a 3.71x - 2.65x speed improvement on a random array:

With the improvements introduced in PR #664, the performance of the pop() method is approximately identical to the sort + delegate method:

Here's the benchmark I used (the imported files are taken from the dist folder when building the project after making the changes that I'm comparing here).

import { lineplot, summary, bench, do_not_optimize, run } from "mitata";
import { Heap as OriginalHeap } from "./heap-js.umd";
import { Heap as OptimizedHeap } from "./heap-js-optimized.umd";
import { Heap as DelegatedHeap } from "./heap-js-delegated.umd"


function generateData(size: number) {
    return Array.from({length: size}, () => Math.random())
}

const data = generateData(1_000_000);

// Original implementation
const originalHeap = OriginalHeap.heapify(data.slice());
let sum1 = 0;  // Prevent optimization
const start1 = performance.now();
for (const value of originalHeap) {
    sum1 += value
}
const end1 = performance.now();
console.log(`Original consuming iteration over 1 million elements in heap: ${(end1 - start1).toFixed(2)}ms.`, sum1);

// Delegated implementation
const delegatedHeap = DelegatedHeap.heapify(data.slice());
let sum2 = 0;  // Prevent optimization
const start2 = performance.now();
for (const value of delegatedHeap) {
    sum2 += value
}
const end2 = performance.now();
console.log(`Delegated iteration over 1 million elements in heap: ${(end2 - start2).toFixed(2)}ms.`, sum2);

// Optimized implementation pop() method
const optimizedHeap = DelegatedHeap.heapify(data.slice());
let sum3 = 0;  // Prevent optimization
const start3 = performance.now();
for (const value of optimizedHeap) {
    sum3 += value
}
const end3 = performance.now();
console.log(`Optimized consuming iteration over 1 million elements in heap: ${(end3 - start3).toFixed(2)}ms.`, sum3);

summary(() => {
    lineplot(() => {
        bench("Using pop()", function* (ctx: any) {
            const size = ctx.get("size");
            yield {
                [0]() {
                    return OriginalHeap.heapify(generateData(size));
                },
                bench(heap: any) {
                    for (const value of heap) {
                        do_not_optimize(value);
                    }
                }
            }
        }).dense_range("size", 10, 100_000, 10_000);
        bench("Using pop() - optimized version from PR #664", function* (ctx: any) {
            const size = ctx.get("size");
            yield {
                [0]() {
                    return OptimizedHeap.heapify(generateData(size));
                },
                bench(heap: any) {
                    for (const value of heap) {
                        do_not_optimize(value);
                    }
                }
            }
        }).dense_range("size", 10, 100_000, 10_000);
        bench("Using delegated", function* (ctx: any) {
            const size = ctx.get("size");
            yield {
                [0]() {
                    return DelegatedHeap.heapify(generateData(size));
                },
                bench(heap: any) {
                    for (const value of heap) {
                        do_not_optimize(value);
                    }
                }
            }
        }).dense_range("size", 10, 100_000, 10_000);
    });
});

await run();

[ignlg]

Interesting approach! I think this change would require a major version update and new methods to manage expectations.

[jedwards1211]

@BeatsuDev I was imagining sorting as the iterator goes so that we wouldn't waste time sorting completely if the consumer doesn't iterate to completion, though maybe that's overcomplicating things...

[jedwards1211]

For people who frequently want to iterate a small head of the heap, sorting each time an iterator begins could be excessive