文字列の先頭への追加に対する最適化を期待していいか？

paulownia.hatenablog.com

文字列型が immutable な言語では、文字列にループで文字を追加していくようなコードは、 Java でいえば StringBuilder などの方法を使えというのが昔から言われていた。しかし、 Java でも Python でも、文字列の右側に追加していくコードは最適化されるようになっており、現代では処理系の最適化を前提に出来るなら、読みやすくなる方が良いという風に常識が変わってきていると思う。

しかし、今回クソコード呼ばわりした left-pad のループは、文字列の左側への追加だ。静的型を元にコンパイル時に最適化出来る言語ならともかく、実行時に振る舞いを見ながら最適化するような言語で、処理系が文字列の先頭への追加を最適化してくれることを前提にして良いものだろうか？少なくとも Python はそこまではやってくれない。node.jsではどうだろう？

追記：記事を公開した時に書いていたコードにバグがあり、結論が180度変わりました！

'use strict';

function leftpad1(str, len, ch) {
  //str = String(str);

  var i = -1;

  if (!ch && ch !== 0) ch = ' ';

  len = len - str.length;

  while (++i < len) {
    str = ch + str;
  }

  return str;
}

function leftpad2(str, len, ch) {
  str = String(str);
  if (!ch && ch !== 0) ch = ' ';

  len -= str.length;
  if (len < 1) {
    return str;
  }
  var pad = "";
  for (var i=0; i<len; i++) {
    pad += ch;
  }
  return pad + str
}

function leftpad_repeat(str, len, ch) {
  str = String(str);
  ch = String(ch);
  if (!ch && ch !== 0) ch = ' ';

  len -= str.length;
  if (len < 1) {
    return str;
  }
  return ch.repeat(len) + str;
}

const count = 1000000;

for (var len=4; len<=128; len*=2) {
  console.log("pad length", len);

  console.log("leftpad1", leftpad1('aaaa', len, 0));
  console.log("leftpad2", leftpad2('aaaa', len, 0));
  console.log("repeat  ", leftpad_repeat('aaaa', len, 0));

  console.time('leftpad1');
  for (let i = 0; i < count; i++) {
    leftpad1('aaaa', len, 0);
  }
  console.timeEnd('leftpad1');

  console.time('leftpad2');
  for (let i = 0; i < count; i++) {
    leftpad2('aaaa', len, 0);
  }
  console.timeEnd('leftpad2');

  console.time('leftpad_repeat');
  for (let i = 0; i < count; i++) {
    leftpad_repeat('aaaa', len, 0);
  }
  console.timeEnd('leftpad_repeat');
}

結果 [ms]

padding len	4	8	16	32	64	128
left-pad	21	118	265	491	959	1755
左追加除去版	19	81	273	483	875	1623
repeat	38	98	145	171	197	215

結論: やはり左追加を最適化してくれることを前提にするのは間違っている。

結論: 元の実装でも十分速い。JS処理系の文字列処理最適化は相当賢い。クソコードとか言ってごめんなさい。