Fastest way of processing a nested tree of promises in javascript?

Question

I'm trying to work out the fastest way of processing a nested tree of jobs that return promises in javascript. I have the following conditions:

1. The process should return a promise that only resolves when all of the nested jobs are complete.
2. Each job at the same level needs to be processed in sequence, but children can be processed in parallel.
3. I can't use await/async.

I have mocked up an example that sums a bunch of numbers and calls a public web service to simulate doing actual work (unfortunately I can't codepen this as the public web service is not available over https):

    function sumNumbers(numbersToSum) {
        return numbersToSum.reduce((p, current) => {
            return p.then(runningTotal => {
                return fetch(`http://numbersapi.com/${current.number}/`)
                    .then(result => {
                        var parentTotal = runningTotal + current.number;
                        if (current.children && current.children.length > 0) {
                            return sumNumbers(current.children)
                                .then(childrenTotal => {
                                    return childrenTotal + parentTotal;
                                });
                        }
                        else {
                            return parentTotal;
                        }
                    });
            });
        }, Promise.resolve(0));
    }

    var numbers = [
        {
            number: 2,
            children: [
                { number: 1 },
                {
                    number: 3,
                    children: [
                        { number: 2 },
                        {
                            number: 1,
                            children: [
                                { number: 1 },
                                { number: 2 }
                            ]
                        }
                    ]
                },
                { number: 2 }
            ]
        },
        { number: 4 },
        { number: 5 },
        {
            number: 3,
            children: [
                {
                    number: 1,
                    children: [
                        { number: 1 }
                    ]
                },
                { number: 2 }
            ]
        }
    ];

    (() => {
        var startTime = new Date();
        sumNumbers(numbers)
            .then(total => {
                var finishTime = new Date();
                console.log(`${total} (took ${((finishTime - startTime) / 1000)}s)`);
            });
    })();

When I run that in my web console i get the following result:

30 (took 2.839s)

This approach works but when a job has children to process the parent waits for the child jobs to finish before resolving and moving on to the next sibling job. I'm wondering whether it would be faster to process the child jobs in parallel?

Is this the case? If so how would you rewrite the example to take advantage of that approach? If not, is there a faster way of doing this in general?

Answer 1

Would it be faster to resolve the parent straight away after kicking off the child job, then summing the result later?

Yes, it would. If understand correctly, you would want only sibling nodes to be processed sequentially, and have each node wait for its predecessors before starting the work of its children, but not have a node wait for its children to finish.

Or being more explicit, the first fetch from the first level is executing at the same time as the first fetches from the second, third and fourth. That's 4 requests executing in parallel rather than in serial (as in the example code in the op) which would surely save significant time when scaled out to a bigger example.

Yes, that would be faster, but not significantly - a constant factor at most. You would still have to sequentially process all the leaves of the tree.

The code for this is trivial though - you'd just replace the fetch(node).then(processChildren) with a concurrent version:

return Promise.all([
    fetch(`http://numbersapi.com/${current.number}/`),
    current.children && current.children.length > 0
      ? sumNumbers(current.children)
      : 0
}).then(([result, childrenTotal]) => {
//        ^^^^^^
    var parentTotal = runningTotal + current.number;
    return childrenTotal + parentTotal;
});

I notice you never actually use the result, so I wonder why you're fetching anything at all :-)