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

Status: RESOLVED FIXED

(Core :: JavaScript Engine, defect)

Description

[Igor Bukanov]

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.

Comment 1

[Igor Bukanov]

I will address the issue in a new version of the patch for bug 398609.

Comment 2

[Igor Bukanov]

The checked in patch for bug 398609 addresses this issue.

Comment 3

[Bob Clary [:bc] (inactive)]

Attachment: js1_5/decompilation/regress-398808.js

possible testcase.

Comment 4

[Bob Clary [:bc] (inactive)]

Attachment: test comparison before|after patch (pdf)

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.

Comment 5

[Bob Clary [:bc] (inactive)]

Note js1_5/decompilation/regress-398808.js fails in opt browser mac|win32, and opt shell mac|win32.