13

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

NVI
  • 14,907
  • 16
  • 65
  • 104
  • 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 Nov 25 '11 at 01:42
  • I would like to see an iterative version as well. – NVI Nov 25 '11 at 02:04
  • I changed the question. The only goal is to make it faster. – NVI Nov 25 '11 at 12:29
  • What implementation of inheritance are you using? If anything other than [extension](http://ejohn.org/blog/simple-javascript-inheritance/) (the actual name escapes me at the moment), then both implementations of `clone_recursive` are likely incorrect. – outis Nov 25 '11 at 13:10
  • It is not possible to write a perfect clone method in JavaScript, but you should at least consider arrays. This one gets rather close: http://stackoverflow.com/questions/728360/copying-an-object-in-javascript/728694#728694 – user123444555621 Nov 25 '11 at 13:32
  • 1
    outis, let's assume that the input object is a direct descendant of the Object and all its properties are own properties. – NVI Nov 25 '11 at 17:54

5 Answers5

9

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.

outis
  • 75,655
  • 22
  • 151
  • 221
  • On FF3.6 the version I answered with was empirically faster than the recursive version. Using an object in the queue to hold the 2 values was the main bottleneck. – Louis Ricci Nov 29 '11 at 14:12
  • @LastCoder: Using your benchmark script on jsFiddle, running 10 trials of 10 runs each trial, where each function is called 100 times per run, I end up with a mean execution time of 19.331 ms (std dev: 0.2424) for the recursive version and 23.49 ms (std dev: 0.1749) for the iterative under FF 3.6. Under Chrome 15, the mean time for the recursive version is 6.268 ms (std dev 0.2291) and the iterative is 6.409 ms (std dev 0.2771). From my study, the recursive function is empirically faster than the iterative. If the -1 was you, I'll take it back now :-). – outis Nov 30 '11 at 01:33
  • "If the -1 was you", it wasn't... I test some modifications to the test object seeing if having more recursive objects embedded in each layer made any difference. The recursion is indeed faster 5% to 15% no matter the variance of the test object being copied. My initial reply was observation bias from my first three runs of the test code running FF in a virtual machine. – Louis Ricci Nov 30 '11 at 14:39
4

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.

outis
  • 75,655
  • 22
  • 151
  • 221
Louis Ricci
  • 20,804
  • 5
  • 48
  • 62
  • It's an improvement over the original iterative version. It runs in pair with the clone_recursive in Chrome, but still slower in all the other browsers. http://jsperf.com/clone-an-object/5 – NVI Nov 29 '11 at 19:52
2

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;
}
hugomg
  • 68,213
  • 24
  • 160
  • 246
  • http://jsperf.com/clone-an-object/3 the iterative version with a linked list still slower than the recursive one. Although, it is faster than an array in Safari, slower in Firefox and exactly the same in Chrome. – NVI Nov 26 '11 at 02:55
  • Your version doesn't do deep copy: clone_iterative_linked_list({a:{b:1}}) // {a:{}} – NVI Nov 26 '11 at 02:59
  • Oh shit, `quehead.next` happens before I have a chance to add items to the list. Now I wonder how the hell the test case I ran before I posted this even worked :D – hugomg Nov 26 '11 at 03:03
1

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[""];
}
1

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

NVI
  • 14,907
  • 16
  • 65
  • 104