ljust and rjust are slow

[clayton-shopify]

The implementations of String#ljust and String#rjust are slow (i.e. O(n^2) running time) when MRuby is built with MRB_UTF8_STRING. This is because they repeatedly call String#size, which calls utf8_strlen, which must iterate over the whole string.

$ echo '"".ljust(100000)' | time bin/mruby
       57.46 real        57.01 user         0.21 sys

$ echo '"".rjust(100000)' | time bin/mruby
       57.17 real        56.90 user         0.14 sys

This issue was reported by https://hackerone.com/ssarong

[texrg]

Please run more than one times your benchmark

very similar
57.46+57.01+0.21=114.68
57.17+56.90+0.14=114.21

[dabroz]

Also, these functions with an empty padding parameter will stay in an infinite loop.