I've been working on a MutationObserver es5 shim and would appreciate some feedback on my technique for identifying changes between a node and its clone from earlier state. The reason I'm asking for this code review is that this function is likely not perfect (i.e. will have to be updated in the future for missed/incorrect cases) and was the most difficult snippet of code I've ever written. I would like to know if how I've written the code is intuitive/commented enough for fresh eyes and if you have any suggestions for a couple things.

Here's the pseudocode I wrote that my actual code is based on:

findChildMutations ($node $oldnode, deep):
    mutations = []
    conflicts
    iterate each $node.childNodes as $node and $oldnode.childNodes as $old:
        if(sameNode($node, $old)):
            if(deep):
                check children of $node and $old
            resolveConflicts()
        else:
            if($node not checked):
                if($node in $oldnode.childNodes):
                    add addedNode MutationRecord to mutations
                else if($node at different index in $oldnode.childNodes)
                    add conflict
            #similarly for $old
    resolveConflicts()
    return mutations

The goals of the function is to acurately be able to identify addedNodes or removedNodes in the (optionally deep) childNodes of an element. The function should also notice when there is a change in order of nodes. Finally the function should of course be efficient as it will be running more than 20 times a second. Here's how the function will be used.

This is the best I've been able to get the function and here are my test cases:

//findChildMutations: array of mutations so far, element, element clone, bool => array of mutations
// dfs comparision search of two nodes
// perf and function tests: http://jsbin.com/uhoVibU/4
var findChildMutations = function(target, oldstate, deep) {
    var mutations = [];
    var add = function(node) {
        mutations.push(new MutationRecord({
            type: "childList",
            target: node.parentElement,
            addedNodes: [node]
        }));
        if(deep) $id_kids(node, deep);//ensure children of added ele have ids
    };
    var rem = function(node) {
        mutations.push(new MutationRecord({
            type: "childList",
            target: deep ? node.parentElement : target,//so target will appear correct on childList - more complicated on subtree
            removedNodes: [node]
        }));
    };

    var findMut = function(node, oldnode) {
        var $kids = node.childNodes;
        var $oldkids = oldnode.childNodes;
        var klen = $kids.length;
        var olen = $oldkids.length;
        
        //id to i and j search hash to prevent double checking an element
        var id;
        var map = {};

        //array of potention conflict hashes
        var conflicts = [];

        //offsets
        //var offset_add = 0;//nodes added since last resolve //we dont have to check added as these are handled before remove
        var offset_rem = 0;//nodes removed since last resolve
        /*
        * There is no gaurentee that the same node will be returned for both added and removed nodes
        * if the position has been shuffled
        */
        var resolver = function() {
            var counter = 0;//prevents same conflict being resolved twice
            var conflict;
            for (var i = 0, l = conflicts.length-1; i <= l; i++) {
                conflict = conflicts[i];
                //attempt to determine if there was node rearrangement... won't gaurentee all matches
                //also handles case where added/removed nodes cause nodes to be identified as conflicts
                if(counter < l && Math.abs(conflict.i - (conflict.j + offset_rem)) >= l) {
                    add($kids[conflict.i]);//rearrangment ie removed then readded
                    rem($kids[conflict.i]);
                    counter++;
                } else if(deep) {//conflicts resolved - check deep
                    findMut($kids[conflict.i], $oldkids[conflict.j]);
                }
            }
            offset_rem = conflicts.length = 0;
        };

        //iterate over both old and current child nodes at the same time
        for(var i = 0, j = 0, p; i < klen || j < olen; ) {
            if(sameNode($kids[i], $oldkids[j])) {//simple expected case
                if(deep) {//recurse
                    findMut($kids[i], $oldkids[j]);
                }

                //resolve conflicts
                resolver();

                i++;
                j++;
            } else {//lookahead until they are the same again or the end of children
                if(i < klen) {
                    id = getId($kids[i]);
                    //check id is in the location map otherwise do a indexOf search
                    if(!has.call(map, id)) {//not already found
                        if((p = findIndex($oldkids, $kids[i], j)) === -1) {
                            add($kids[i]);
                        } else {
                            conflicts.push(map[id] = {//bit dirty
                                i: i,
                                j: p
                            });
                        }
                    }
                    i++;
                }

                if(j < olen) {
                    id = getId($oldkids[j]);
                    if(!has.call(map, id)) {
                        if((p = findIndex($kids, $oldkids[j], i)) === -1) {
                            rem($oldkids[j]);
                            offset_rem++;
                        } else {
                            conflicts.push(map[id] = {
                                i: p,
                                j: j
                            });
                        }
                    }
                    j++;
                }
            }
        }
        resolver();
    };
    findMut(target, oldstate);
    return mutations;
};

Helper functions:

//Assigns a unique id to each node to be watched in order to be able to compare cloned nodes
//TODO find a cleaner way eg some hash represnetnation
var counter = 0;
var getId = function($ele) {
    var id = $ele.nodeType === 3 ? $ele.nodeValue ://text node id is the text content
                                    $ele.id || $ele.getAttribute("mut-id") || ++counter;
    if(id === counter) {
        $ele.setAttribute("mut-id", id);
    }
    return id;
};

var sameNode = function(node1, node2) {
    return node1 && node2 && getId(node1) === getId(node2);
};

var findIndex = function(set, node, from) {
    from = ~~from;
    for(var i = from,l=set.length; i<l; i++) {
        if(sameNode(node, set[i])) return i;
    }
    return -1;
};

//set the ids for all of an elements children
var $id_kids = function(ele, deep) {
    if(ele.nodeType !== 3) {
        foreach.call(ele.children, function(node) {//only iterate elements not text nodes
            getId(node);
            if(deep) $id_kids(node, deep);
        });
    }
    return ele;
};

Questions:

1. Is there a better way to be able to accurately compare a node to its clone than to assign a unique id to each element being watched (see getId helper function)? My concern with using .equalNode or parsing the HTML is being able to match the node if there are changes and handling two similarly appearing nodes such as a li. I wrote a gist describing the problem.
2. Can you give me some feedback and suggestions on my implementation?
3. Update another issue with this code is it can be unacceptably slow when I tested it on some mobile devices (runs some of these JSLitmus tests only 50 times a second). Can you give me some optimization tips for the snippet
4. Do you know of any research/papers discussing comparing two trees/graphs? I haven't found much on the topic.