new Functionでパフォーマンス上げる

みなさん、`new Function`してますか？いかにも黒魔術的なんですが、使いどころを見誤らなければパフォーマンスアップに貢献してくれます。for文の展開とか配列のフィルター関数みたいに一回作って使いまくるケースは向いてるかと思います。

ちょっと一個具体例で説明したいと思います。

## 再帰的なフィルター

以下のようにオブジェクトで再帰的なフィルターを定義します。

```js
var tree = {
  type: 'and',
  children: [
    {
      type: 'or',
      children: [
        {fn: x => /abc/.test(x)},
        {fn: x => /bcd/.test(x)},
        {fn: x => /hoge/.test(x)},
        {fn: x => /fuga/.test(x)},
        {fn: x => /aaa/.test(x)},
        {fn: x => /fda/.test(x)},
      ]
    },
    {
      type: 'or',
      children: [
        {fn: x => /ABC/.test(x)},
        {fn: x => /DEF/.test(x)},
        {fn: x => /A/.test(x)},
        {fn: x => /D/.test(x)},
        {fn: x => /FFDA/.test(x)},
        {fn: x => /MFDAK/.test(x)},
      ]
    }
  }
}
```

この定義を使って愚直にフィルター関数を作ります。まぁ、読みやすいです。

```js
function filter1(tree, x) {
  switch (tree.type) {
    case 'and': return tree.children.every(t => filter1(t, x));
    case 'or':	return tree.children.some(t => filter1(t, x));
    default:  	return tree.fn(x);
  }
}
```


これは、再帰を論理演算子で書き換えることができます。`new Function`で再帰を取り除いた関数を作る関数を作ってみます。

```js
var BINARY_LOGICAL_OPERATORS_TABLE = {
  and: '&&',
  or: '||'
};

function createFilter(tree) {
  var i = 0;
  var fnNames = [];
  var fns = [];
  var fnBody;
  
  function create(tree) {
    var fnName;
    switch (tree.type) {
      case 'and':
      case 'or':
        return `(${tree.children.map(create).join(BINARY_LOGICAL_OPERATORS_TABLE[tree.type])})`;
      default:
        fnName = '$' + (++i).toString(32);
        fnNames.push(fnName);
        fns.push(tree.fn);
        return fnName + '(x)';
    }
  }
  fnBody = create(tree);
  return new Function(...fnNames, 'x', 'return ' + fnBody).bind(null, ...fns);
}
```

これ、具体的にどんなことをしているかというと、以下のような関数(一番上の木構造を使っています)を作ってフィルターに使っている関数たち(`fn`)をbindしたものを返しています。生成後の関数には再帰や条件分岐がなくなっているので速そうにみえますね。

```js
function foo($1,$2,$3,$4,$5,$6,$7,$8,$9,$a,$b,$c,x) {
  return (($1(x)||$2(x)||$3(x)||$4(x)||$5(x)||$6(x))&&($7(x)||$8(x)||$9(x)||$a(x)||$b(x)||$c(x)))
}
```

で、愚直パターンとnew Functionパターンでベンチを取ってみました。

愚直: https://jsfiddle.net/6c6t8z1e/3/

```
15 words
normal 1.0750000000000455
30 words
normal 3.410000000000082
60 words
normal 2.0349999999998545
120 words
normal 2.349999999999909
240 words
normal 11.375000000000227
480 words
normal 3.9149999999999636
960 words
normal 11.150000000000091
1920 words
normal 18.169999999999845
3840 words
normal 73.75499999999988
7680 words
normal 98.56500000000005
15360 words
normal 73.19000000000005
30720 words
normal 125.625
61440 words
normal 264.3700000000001
122880 words
normal 369.86999999999966
```

new Function: https://jsfiddle.net/6c6t8z1e/4/

```
15 words
new Function 1.7250000000000227
30 words
new Function 0.48500000000001364
60 words
new Function 0.49500000000000455
120 words
new Function 2.9400000000000546
240 words
new Function 2.865000000000009
480 words
new Function 2.175000000000068
960 words
new Function 5.244999999999891
1920 words
new Function 5.139999999999986
3840 words
new Function 10.31499999999994
7680 words
new Function 10.705000000000041
15360 words
new Function 62.684999999999945
30720 words
new Function 56.91000000000008
61440 words
new Function 86.46500000000015
122880 words
new Function 150.03500000000008
```

ちょっと計測方法が雑ですが速くなりました! new Functionはいいぞ。

## 追記：再帰的なフィルター2(文字列だけバージョン)

and, or+含む, 正規表現に一致等のオペレーターとテキストだけで構成される木構造(以下例)を使ったフィルターを作ってみます。

```js
var tree = {
  type: 'or',
  children: [
    {
      type: 'and',
      children: [
        {
          type: 'rule',
          op: 'startsWith',
          text: 'ab'
        },
        {
          type: 'rule',
          op: 'endsWith',
          text: 'ef'
        },
        {
          type: 'rule',
          op: 'strictEqual',
          text: 'abcdef'
        },
        {
          type: 'rule',
          op: 'includes',
          text: 'bcde'
        },
        {
          type: 'rule',
          op: 'regexp',
          text: '^a.+f$'
        },
      ]
    },
    {
      type: 'and',
      children: [
        {
          type: 'rule',
          op: 'notStartsWith',
          text: 'aaa'
        },
        {
          type: 'rule',
          op: 'notEndsWith',
          text: 'bbb'
        },
        {
          type: 'rule',
          op: 'notStrictEqual',
          text: 'ccc'
        },
        {
          type: 'rule',
          op: 'notIncludes',
          text: 'ddd'
        },
        {
          type: 'rule',
          op: 'notRegexp',
          text: '^aa.+dd$'
        },
      ]
    },
    {
      type: 'or',
      children: [
        {
          type: 'rule',
          op: 'regexp',
          text: '^\s*[Jj]ava[Ss]cript\s*$'
        },
        {
          type: 'rule',
          op: 'regexp',
          text: '^\s*ジャ(ヴァ|バ)スクリプト\s*$'
        },
        {
          type: 'rule',
          op: 'regexp',
          text: '^\s*JS|js\s*$'
        },
      ]
    }
  ]
}
```

愚直パターン([bench](https://jsfiddle.net/ukyo/6vagjemm/3/))

```js
var filter1 = (tree, s) => {
  var i, n;
  switch (tree.type) {
    case 'and':
      for (var i = 0, n = tree.children.length; i < n; i++) {
        if (!filter1(tree.children[i], s)) return false;
      }
      return true;
    case 'or':
      for (var i = 0, n = tree.children.length; i < n; i++) {
        if (filter1(tree.children[i], s)) return true;
      }
      return false;
    case 'rule':
   	  switch (tree.op) {
        case 'startsWith': return s.startsWith(tree.text);
        case 'endsWith': return s.endsWith(tree.text);
        case 'strictEqual': return s === tree.text;
        case 'includes': return s.includes(tree.text);
        case 'regexp':
          try {
          	return new RegExp(tree.text).test(s);
          } catch (e) {
            return false;
          }
        case 'notStartsWith': return !s.startsWith(tree.text);
        case 'notEndsWith': return !s.endsWith(tree.text);
        case 'notStrictEqual': return s !== tree.text;
        case 'notIncludes': return !s.includes(tree.text);
        case 'notRegexp':
          try {
          	return !(new RegExp(tree.text).test(s));
          } catch (e) {
            return false;
          }
      }
  }
};
```

new Functionパターン([bench](https://jsfiddle.net/ukyo/chwcu4an/2/))

```js
var inlineValidators = {
  startsWith: s => `s.startsWith('${s}')`,
  endsWith: s => `s.endsWith('${s}')`,
  strictEqual: s => `(s === '${s}')`,
  includes: s => `s.includes('${s}')`,
  regexp: s => `/${s}/.test(s)`,
  notStartsWith: s => `!s.startsWith('${s}')`,
  notEndsWith: s => `!s.endsWith('${s}')`,
  notStrictEqual: s => `(s !== '${s}')`,
  notIncludes: s => `!s.includes('${s}')`,
  notRegexp: s => `!/${s}/.test(s)`
}

var escape = s => s.replace(/\\?(['"\/])/g, '\\$1').replace(/\\+$/, '');

var validateRegExp = s => {
  try {
    new RegExp(s);
    return true;
  } catch (e) {
    return false;
  }
};

var createFilter = tree => {
  var _create = ({op, type, children, text}) => {
    switch (type) {
      case 'and': return `(${children.map(_create).join('&&')})`;
      case 'or': return `(${children.map(_create).join('||')})`;
      case 'rule':
        switch (op) {
          case 'regexp':
          case 'notRegexp':
            if (validateRegExp(text)) {
              var s = escape(text);
              return s ? inlineValidators[op](s) : 'false';
            } else {
              return 'false';
            }
          default:
            return op ? inlineValidators[op](escape(text.toLowerCase())) : 'false';
        }
    }
  };

  var fnBody = (tree.type === 'rule' || tree.children.length) ? _create(tree) : 'false';
  return new Function('s', `return ${fnBody}`);
};
```

このケースだとインライン化の恩恵はかなり大きいです。特に、

* 大きめのswitch文が消える
* フィルター生成時に正規表現の正誤判定できる

が効いてるかと思われます。