高速化を試みた

実際に実装してみて、表示結果は希望通りになったのですが、レーベンシュタイン距離の計算がとにかく遅い！！
10000行程度のファイルどうしを比較すると数分以上待たされてしまったので、何とか高速化することにします。
行どうしの類似度は、文字列どうしが似ているかどうかだけ分かればよいので、似ていないと分かった時点でスコア計算を打ち切るようにしました。
また、ファイル内でユニークな内容を持つ行(＝同じ内容の行は他に存在しない)について、比較対象のファイルにも同じ内容でユニークな行が存在すれば、そこで行どうしのペアが確定するため、レーベンシュタイン距離の計算対象から外します。行のハッシュ値を生成した直後の処理で、ユニークな行どうしでペアが作れるかを調べて記録しています。

JavaScript で関数を入れ子にするとものすごく遅かったので、インライン展開できるところはなるべくインライン展開するようにしています。内側の関数から外側の変数を参照すると遅いようです。

あとはループ自体の最適化、計算結果をキャッシュできるところはなるべくキャッシュする、などの地味な最適化を行っています。
実際に両方試さないとわからないところは、両方実装して実験しました。（配列の処理をmapで回すのとforで回すのとの比較とか）
いわゆるsnake関数のメインループにあたるところは、教科書にあるような説明的なループからカリカリにチューンナップしたので、原形はかろうじてとどめている感じになりました。

Diff_(len1, len2, bReverse) {
    const bStrict = !this.bDetectSimilarLine, threshold = this.threshold, _max = Math.max;
    let n = len1 + len2 + 3, fp = (new Int32Array(n)).fill(-1), ed = (new Array(n)).fill(null);
    for (let p = 0; fp[len2 + 1] != len2; p++) {
        for (let k = len1 - p; k < len2; k++) {
            let y = _max(fp[k] + 1, fp[k + 2]), x = y - k + len1, bIsBlank, y0, org, score;
            let [x1, y1, k_plus, k_minus] = (bReverse ? [y, x, k + 2, k] : [x, y, k, k + 2]);
            if (bReverse ? (y == fp[k + 2]) : ((y == (fp[k] + 1)) && (fp[k + 2] != 0))) {
                if (y1 > 0) { ed[k + 1] = {op:'+', x:-1, y:y1 - 1, prev:ed[k_plus]}; }
            } else {
                if (x1 > 0) { ed[k + 1] = {op:'-', x:x1 - 1, y:-1, prev:ed[k_minus]}; }
            }
            for (bIsBlank = true, y0 = y, org = ed[k + 1]; x < len1; x1++, y1++, x++, y++) {
                if ((score = this.CompareStr(x1, y1, bStrict)) <= threshold) { break; }
                if (!this.vInfo_L[x1].isBlank) { bIsBlank = false; }
                ed[k + 1] = {op:((score > 1) ? '=' : '*'), x:x1, y:y1, prev:ed[k + 1]};
            }
            if (bIsBlank && !((x >= (len1 - 1)) && (y >= (len2 - 1)))) { [y, ed[k + 1]] = [y0, org]; }
            fp[k + 1] = y;
        }
        for (let k = len2 + p; k >= len2; k--) {
            let y = _max(fp[k] + 1, fp[k + 2]), x = y - k + len1, bIsBlank, y0, org, score;
            let [x1, y1, k_plus, k_minus] = (bReverse ? [y, x, k + 2, k] : [x, y, k, k + 2]);
            if (bReverse ? (y == fp[k + 2]) : ((y == (fp[k] + 1)) && (fp[k + 2] != 0))) {
                if (y1 > 0) { ed[k + 1] = {op:'+', x:-1, y:y1 - 1, prev:ed[k_plus]}; }
            } else {
                if (x1 > 0) { ed[k + 1] = {op:'-', x:x1 - 1, y:-1, prev:ed[k_minus]}; }
            }
            for (bIsBlank = true, y0 = y, org = ed[k + 1]; y < len2; x1++, y1++, x++, y++) {
                if ((score = this.CompareStr(x1, y1, bStrict)) <= threshold) { break; }
                if (!this.vInfo_L[x1].isBlank) { bIsBlank = false; }
                ed[k + 1] = {op:((score > 1) ? '=' : '*'), x:x1, y:y1, prev:ed[k + 1]};
            }
            if (bIsBlank && !((x >= (len1 - 1)) && (y >= (len2 - 1)))) { [y, ed[k + 1]] = [y0, org]; }
            fp[k + 1] = y;
        }
    }
    return ed[len2 + 1];
},

なんとか、10000行くらいのファイルを数秒から10秒くらいで比較できるようになったのですが、基本アルゴリズムがO(N^2)なので、リアルタイムで表示を更新するのはあきらめました。(このへんがdiff_orzの名前の由来だったり………)

Javascript で diff (内部仕様についての補足７)

高速化を試みた