Is it possible to rewrite the following JavaScript recursive function to make it faster?

function clone_recursive(object) {
    var result = {};
    for (var key in object) {
        var value = object[key];
        if (typeof value === 'object') {
            result[key] = clone_recursive(value);
        } else {
            result[key] = value;
        }
    }
    return result;
}

I rewrote it in an iterative style but it doesn't gain any performance, in fact the speed dropped by ≈20%.

function clone_iterative(object) {
    var result = {};
    var queue = [{base: result, value: object}];
    var item;
    while (item = queue.shift()) {
        var current = item.value;
        var base = item.base;
        for (var key in current) {
            var value = current[key];
            if (typeof value === 'object') {
                var resultValue = base[key] = {};
                queue.push({base: resultValue, value: value});
            } else {
                base[key] = value;
            }
        }
    }
    return result;
}

Is it possible to rewrite the following JavaScript recursive function to make it faster?

function clone_recursive(object) {
    var result = {};
    for (var key in object) {
        var value = object[key];
        if (typeof value === 'object') {
            result[key] = clone_recursive(value);
        } else {
            result[key] = value;
        }
    }
    return result;
}

I rewrote it in an iterative style but it doesn't gain any performance, in fact the speed dropped by ≈20%.

function clone_iterative(object) {
    var result = {};
    var queue = [{base: result, value: object}];
    var item;
    while (item = queue.shift()) {
        var current = item.value;
        var base = item.base;
        for (var key in current) {
            var value = current[key];
            if (typeof value === 'object') {
                var resultValue = base[key] = {};
                queue.push({base: resultValue, value: value});
            } else {
                base[key] = value;
            }
        }
    }
    return result;
}

http://jsperf.com/clone-an-object/13

• javascript
• algorithm
• recursion
• tree
• iteration

• Well you can rewrite a recursive algorithm to use an iterative algorithm, which is sometimes necessary if the recursion is going too deep, but do you have a reason to want to move to continuation passing specifically? I think the existing recursive algorithm is going to be easier to follow... – nnnnnn Commented Nov 25, 2011 at 1:42
• I would like to see an iterative version as well. – NVI Commented Nov 25, 2011 at 2:04
• I changed the question. The only goal is to make it faster. – NVI Commented Nov 25, 2011 at 12:29
• What implementation of inheritance are you using? If anything other than extension (the actual name escapes me at the moment), then both implementations of clone_recursive are likely incorrect. – outis Commented Nov 25, 2011 at 13:10
• 1 outis, let's assume that the input object is a direct descendant of the Object and all its properties are own properties. – NVI Commented Nov 25, 2011 at 17:54

5 Answers 5

It's doubtable that an iterative version would truly be faster, as you're replacing a recursive call with multiple calls to queueing functions. Where a transformation to iteration helps is in preventing stack overflows (as call stacks tend to be smaller than heaps in interpreted languages), and with tail-recursion in languages without tail-call optimization.

The way you are storing (using your queue) in the iterative version is what's causing the slowdown. Use an array-stack and have an entry for each item instead of an object that holds both items (base & value).

function clone_iterative(object) {
    var result = {};
    var stack = [result, object];
    var curr, base;
    while (curr = stack.pop()) {
        var base = stack.pop();
        for (var key in curr) {
            var value = curr[key];
            if (typeof value === 'object') {
                stack.push(base[key] = {});
                stack.push(value)
            } else {
                base[key] = value;
            }
        }
    }
    return result;
}

Check out the clone function benchmark suite on JS Fiddle. On some runs the iterative version is faster than recursive, other times recursion wins out.

I tried using a linked list implementation of the queue to see what happens. I think your problems might have been the function call overhead and shift() not necessaroly being O(1)

Jsperf said it was the fastest this way (I tested on FF7): http://jsperf.com/clone-an-object/4 but then I'm not sure if I didn't mess up the benchmark as I'm not very used to the jsperf website.

Edit: I had a retarded bug in my code. It was actually just shallow copying

The following is the fixed version of the code I used. Its faster then the other imperative version but still loses to the recursive code:

function clone_iterative_linked_list(object) {
    var result = {};
    var queueHead = {base: result, value: object, next: null};
    var queueTail = queueHead;

   for(;queueHead; queueHead = queueHead.next){
        var item = queueHead;

        var current = item.value;
        var base = item.base;
        for (var key in current) {
            var value = current[key];
            if (typeof value === 'object') {
                var resultValue = base[key] = {};
                queueTail.next = {base: resultValue, value: value, next:null};
                queueTail = queueTail.next;
            } else {
                base[key] = value;
            }
        }
    }
    return result;
}

Well, this tried to use JSON replacer to have only one JSON traversal, but also not faster (see http://jsperf.com/clone-an-object/6):

function clone(x) {
var r = {}, lastSrc, lastDst = r, stack = [], v;
function replacer(key, value) {
    while (this !== lastSrc && stack.length) {
        lastDst = stack.pop();
        lastSrc = stack.pop();
    }
    if (typeof value === "object") {
        stack.push(lastSrc, lastDst);
        lastDst[key] = v = new value.constructor;
        lastDst = v;
        lastSrc = value;
        return value;
    } else {
        lastDst[key] = value;
        return undefined;
    }
}
JSON.stringify(x, replacer);
return r[""];
}

Iterative. 2 arrays, don't use pop()

function clone_iterative2(object) {
    var result = {};
    var bases = [result];
    var objects = [object];
    for (var i = 0, length = 1; i < length; ++i) {
        var current = objects[i];
        var base = bases[i];
        for (var key in current) {
            var value = current[key];
            if (typeof value === 'object') {
                bases.push(base[key] = {});
                objects.push(value);
                ++length;
            } else {
                base[key] = value;
            }
        }
    }
    return result;
}

It's the fastest iterative so far. In Chrome Canary (17.0.959.0) it's the fastest overall. Still slower than the recursive in all the other browsers.

http://jsperf.com/clone-an-object/13