最速のreplaceAll()を求めて

Javascriptでは文字を全置換するビルトイン関数が存在しないので、よりよい`replaceAll()`はどれか調べました。
`replaceAll()`の引数には文字列をとるものとします。
正規表現オブジェクトやエスケープされた文字列を渡すのは無しです。

この記事では`Foo.protoype.bar`は`Foo::bar`と表記します (例: `Array.prototype.join` -> `Array::join`)

# 前置き

[JavaScript で全置換(正規表現も使った)の速度比較 - Qiita](https://qiita.com/standard-software/items/d86a91dac6f7f317087c) という記事をこの前改めて見て、昔もった違和感の原因を思いついたので検証してみようと思いまして。
というのも`String::split() -> Array::join()`のほうが`String::replace(Reg(String::replace(before)), after)`よりも速いのは計算量的にしっくりこなかったのです。
この原因は追って説明していきます。

# `replaceAll()`をつくっていく

文字を全置換するには二つのアプローチが考えられます。
一つ目は、正規表現を利用する方法。
二つ目は、単純に文字列処理(`String::indexOf`など)を利用していく方法。
ここから一つ目は`replaceAllS`、二つ目は`replaceAllR`と名付けていきます。
比較のために現在よく使われる(?)、検索で出てくるものも`replaceAllD`と名付けていこうと思います。

## replaceAllD

### `replaceAllD1`
```javascript
var replaceAllD1 = (str, beforeReg, after) => {
  return str.replace(beforeReg, after);
};
```
おそらく一番使われているのはないかなと思います。
これは引数に正規表現オブジェクトを渡すので、
`replaceAll()`には当てはまりませんが比較のために使います。

### `replaceAllD2`
```javascript
var replaceAllD2 = (str, before, after) => {
  return str.split(before).join(after);
};
```
これは簡単にかけてとても楽ですね。
ただ見る感じ結構無駄な処理をしてそうではあります。

## replaceAllR

### `replaceAllR1`
```javascript
var replaceAllR1 = (str, before, after) => {
  return str.replace(new RegExp(
      before.replace(/[\\\*\+\.\?\{\}\(\)\[\]\^\$\-\|\/]/g, "\\$&")
    , 'g'), after);
};
```
前書きで書いた[JavaScript で全置換(正規表現も使った)の速度比較 - Qiita](https://qiita.com/standard-software/items/d86a91dac6f7f317087c)のコメント欄にあるものです。
beforeを正規表現オブジェクトに変換するために正規表現でエスケープして、`String::replace`を使うというものです。
ここからはこれをいじっていこうと思います。

### `replaceAllR2`
```javascript
var Replacer = function (before, after) {
  this.before = new RegExp(before
    .replace(/[\\\*\+\.\?\{\}\(\)\[\]\^\$\-\|\/]/g, "\\$&")
  , 'g')
  this.after = after;
};
Replacer.prototype.replace = function (str) {
  return str.replace(this.before, this.after);
};
  
var r = new Replacer("abc", "123");
var replaceAllR21 = (str) => {
  return r.replace(str);
};
  
var Replacer2 = class {
  constructor(before, after) {
    this.before = new RegExp(before
      .replace(/[\\\*\+\.\?\{\}\(\)\[\]\^\$\-\|\/]/g, "\\$&")
    , 'g');
    this.after = after;
  }
  replace(str) {
    return str.replace(this.before, this.after);
  }
};
  
var r2 = new Replacer2("abc", "123");
var replaceAllR22 = (str) => {
  return r2.replace(str);
};
```
`D1`は正規表現リテラルを使っているので予め正規表現がコンパイルされているのですが[^1]、`R1`では置き換えを実行するたびに正規表現オブジェクトを生成しているので`R2`ではそこを改善しました。
`str.replaceAll(before, after)`で`str`の値は変わっても`before`と`after`が変わることは多くはないのではないかということで固定しました。(そもそも一回しか実行しないならどの関数だろうが誤差レベルでしょうし、`before`を変えるなら正規表現で一つにまとめたほうが速そうですし…)
`prototype`を使ったものと`class`を使ったものの二つ書いてありますが、仕組みは変わりません。
ただ、もしかしたら`class`のほうはJavascriptエンジン側の最適化ができてないかもしれないって程度で書きました。

[^1]: [正規表現リテラルは早いのか？ - Qiita](https://qiita.com/kohashi/items/a5de5703ffdc03743311)

### `replaceAllR3`
```javascript
var regs = Object.create(null);
var replaceAllR31 = function (str, before, after) {
  var beforeReg;
  if (before in regs) {
    beforeReg = regs[before];
  } else {
    beforeReg = new RegExp(before
      .replace(/[\\\*\+\.\?\{\}\(\)\[\]\^\$\-\|\/]/g, "\\$&")
    , 'g');
    regs[before] = beforeReg;
  }
  return str.replace(beforeReg, after)
};
  
var regsM = new Map();
var replaceAllR32 = function (str, before, after) {
  var beforeReg;
  if (regsM.has(before)) {
    beforeReg = regsM.get(before);
  } else {
    beforeReg = new RegExp(before
      .replace(/[\\\*\+\.\?\{\}\(\)\[\]\^\$\-\|\/]/g, "\\$&")
    , 'g');
    regsM.set(before, beforeReg);
  }
  return str.replace(beforeReg, after)
};
```
一々`new`してというのはめんどくさいだろうなと思って`new`しなくてもいいようにしました。
ただ、先ほどのR2と違ってメモリ開放の手段がないので(R2は`ReplaceR = null`で解放できる)、一度しか使わないといった場合でメモリを食うかもしれません。(解放用の関数を作って`regs[before] = null`などすればできなくはない)
`Object`と`Map`の二種類用意してありますが、前の`prototype`と`class`と同じ理由です。

## replaceAllS

### `replaceAllS1`
```javascript
var replaceAllS1 = (str, before, after) => {
  var result = str;
  do {
    str = result;
    result = str.replace(before, after);
  } while (str !== result);
  return result;
};
```
先ほど取り上げた記事の前の記事の[JavaScript全置換(正規表現使わない)の速度比較 - Qiita](https://qiita.com/standard-software/items/7288f4ed008d0aefbe06)の冒頭にのっている関数です。
`String::replace`を繰り返すというものですね。

### `replaceAllS2`
```javascript
var replaceAllS2 = (str, before, after) => {
  var b = str.indexOf(before);
  if (b === -1) return str;
  return str.slice(0, b) + after + replaceAllS2(str.slice(b+before.length), before, after);
};
```
`String::replace`を繰り返すと既に走査済みのところも走査してしまうので`String::indexOf`と`String::slice`を利用するようにしました。
分割して見つかった場所より後ろの部分を分割して…と繰り返します。

### `replaceAllS3`
```javascript
var replaceAllS3 = (str, before, after) => {
  var i = 0;
  var result = "";
  while(true) {
    i = str.indexOf(before);
    if (i === -1) {
      result += str;
      break;
    }
    result += str.slice(0, i) + after;
    str = str.slice(i+before.length);
  }
  return result;
};
```
ただ`S2`の再帰呼び出しを`while`で書き直しました。
`S2`は末尾再帰最適化[^2]が効かない形[^3]なので、置き換え箇所が多数あると`Uncaught RangeError: Maximum call stack size exceeded`が発生します。
また、関数呼び出しは遅いというのもあります。

[^2]: [末尾再帰による最適化 - Qiita](https://qiita.com/pebblip/items/cf8d3230969b2f6b3132)
[^3]: 効く形でも現地点(2018/08/09)ではSafariしか対応していない

### `replaceAllS4`
```javascript
var replaceAllS4 = (str, before, after) => {
  var i = str.indexOf(before);
  if (i === -1) return str;
  var result = str.slice(0, i) + after;
  var j = str.indexOf(before, i+before.length);
  while (j !== -1) {
    result += str.slice(i+before.length, j) + after;
    i = j;
    j = str.indexOf(before, i+before.length);
  }
  return result + str.slice(i+before.length);
};
```
`S3`では`str`を書き換えていたので`str`を書き換えないようにしました。
文字列を書き換えるのと数値を書き換えるのだと数値を書き換えるほうが速いです。(割と違いました)

### `replaceAllS5`
```javascript
var replaceAllS5 = (str, before, after) => {
  var i = str.indexOf(before);
  if (i === -1) return str;
  var bLen = before.length;
  var result = str.slice(0, i) + after;
  i += bLen;
  var j;
  while ((j = str.indexOf(before, i)) !== -1) {
    result += str.slice(i, j) + after;
    i = j+bLen;
  }
  return result + str.slice(i);
};
```
いわゆる`人類には(早|速)すぎる高速化`ってやつです。
たぶん無駄にごちゃごちゃして意味不明になっただけです。
ほぼ変わらないと思います。

# 結果
ここまでたくさんの`replaceAll()`を書きましたがその計測結果を書きます。
jsPerfは偉大…

|replaceAll()|Chrome66(Win)|Canary70(Win)|Chrome68(Android)|
|:-----------|------------:|------------:|------------:|
| D1         |   571,467   |   551,045   |   211,071   |
| D2         |   358,059   |   333,419   |   176,312   |
| R1         |   414,472   |   422,145   |   164,451   |
| R2-1       |   513,877   |   493,442   |   171,090   |
| R2-2       |   496,295   |   499,116   |   172,678   |
| R3-1       |   496,193   |   495,639   |   178,892   |
| R3-2       |   501,193   |   495,095   |   162,004   |
| S1         |  *102,670*  |  *127,185*  |   *49,012*  |
| S2         |   457,978   |   450,517   |   201,365   |
| S3         |   497,030   |   505,375   |   219,658   |
| S4         | **654,655** | **716,908** | **269,525** |
| S5         | **656,770** | **729,293** | **270,619** |
単位は(Ops/sec)
[replaceAlls - jsPerf](https://jsperf.com/replacealls)

S1 << D2 < S2 < R2,R3 < S3 < D1 < S4 <= S5
こんな感じですかね。
計測結果から正規表現レテラルでもよいなら`D1`、使いたくないなら`R3`もしくは`S4`あたりがよさそうですかね。
ぱぱっと使うだけなら`D2`で十分だとは思います。

もっと速くなる！！！って方法がありましたら是非コメントを！！