Closed Bug 398808 Opened 13 years ago Closed 12 years ago

Decompiler time is O(n^2) in number of variables

Categories

(Core :: JavaScript Engine, defect, minor)

defect
Not set
minor

Tracking

()

RESOLVED FIXED

People

(Reporter: igor, Assigned: igor)

References

Details

(Keywords: perf)

Attachments

(2 files)

Currently the decompiler uses a linear search to locate variable names based on its slot. This results in quadratic time complexity when decompiling scripts with large number of script variables. Here is an example:

~/m/trunk/mozilla/js/src $ cat ~/m/y.js
function prepare_src(n)
{
    var s, i;

    s = "";
    for (i = 0; i != n; ++i)
        s += "var v"+i+"=1;";
    s += "return ";
    for (i = 0; i != n; ++i)
        s += "v"+i+"+";
    s += "0;";
    return s;
}

function time_test(n)
{
    var f = new Function(prepare_src(n));
    var time = Date.now();
    uneval(f);
    time = Date.now() - time;
    return time;
}

var array = [];

for (var i = 1; i <= 5; ++i)
    array.push(time_test(1000 * i));
    
for (var i = 1; i != array.length; ++i)
    print("Relative time, i="+i+": "+(array[i] / array[0]).toFixed(2));
~/m/trunk/mozilla/js/src $ js ~/m/y.js
Relative time, i=1: 3.55
Relative time, i=2: 8.01
Relative time, i=3: 14.31
Relative time, i=4: 22.39
~/m/trunk/mozilla/js/src $ 

It would be nice to reduce the complexity to O(n) in number of variables.
Keywords: perf
I will address the issue in a new version of the patch for bug 398609.
Depends on: 398609
The checked in patch for bug 398609 addresses this issue.
Status: NEW → RESOLVED
Closed: 12 years ago
Resolution: --- → FIXED
possible testcase.
I can't really distinguish the before and after based on the results of BigO. There is definite improvement after the patch, but it looks like before and after are both still quadratic for low N and almost linear for high N.
Note js1_5/decompilation/regress-398808.js fails in opt browser mac|win32, and opt shell mac|win32.
Flags: in-testsuite-
Flags: in-litmus-
You need to log in before you can comment on or make changes to this bug.