日記帳

日記です。

String#gsub() と String#gsub!() の速度比較

Ruby

同じ動作をする破壊的メソッドと非破壊的メソッドがある場合，一般的には新規にオブジェクトを生成しない破壊的メソッドの方が速いことが多い(はず)です．

「CGI::escapeHTML() って何をエスケープしてたっけ？」と思ってcgi.rbを眺めていると以下のようなコードでした．

def CGI::escapeHTML(string)
	string.gsub(/&/n, '&amp;').gsub(/\"/n, '&quot;').gsub(/>/n, '&gt;').gsub(/</n, '&lt;') 
end

漠然と期待していたのは以下のようなコードです．

def CGI::escapeHTML(string)
	result = string.gsub(/&/n, '&amp;')
	result.gsub!(/\"/n, '&quot;')
	result.gsub!(/>/n, '&gt;')
	result.gsub!(/</n, '&lt;')
	result
end

2つ目以降の置換を破壊的にすることで生成される String*1 オブジェクトの数が減って効率いいんじゃないかなってことなんですが…
実際どっちが速いのかしら？ってことで比べてみました．

ソースコード

require 'benchmark'

LOOP_COUNT = 200000
BASE_STRING = 'foo & "bar" & <baz> '
#BASE_STRING = 'foo + `bar` + (baz) '

def escapeHTML1(string)
	string.gsub(/&/n, '&amp;').gsub(/\"/n, '&quot;').
		gsub(/>/n, '&gt;').gsub(/</n, '&lt;');
end

def escapeHTML2(string)
	result = string.gsub(/&/n, '&amp;')
	result.gsub!(/\"/n, '&quot;')
	result.gsub!(/>/n, '&gt;')
	result.gsub!(/</n, '&lt;')
	result
end

puts "BASE_STRING   : #{BASE_STRING.inspect}"
puts "escapeHTML1() : #{escapeHTML1(BASE_STRING).inspect}"
puts "escapeHTML2() : #{escapeHTML2(BASE_STRING).inspect}"

Benchmark::bm(25){ |x|
	[1, 3, 5, 10].each(){ |repeat|
		string = BASE_STRING * repeat
		puts "string.length : #{string.length}"
		GC.start(); 
		x.report("escapeHTML1") {
			LOOP_COUNT.times(){ escapeHTML1(string) }
		}

		GC.start(); 
		x.report("escapeHTML2") {
			LOOP_COUNT.times(){ escapeHTML2(string) }
		}
	}
}

置換が発生する場合の結果

 BASE_STRING   : "foo & \"bar\" & <baz> "
 escapeHTML1() : "foo &amp; &quot;bar&quot; &amp; &lt;baz&gt; "
 escapeHTML2() : "foo &amp; &quot;bar&quot; &amp; &lt;baz&gt; "
                                user     system      total        real
 string.length : 20
 escapeHTML1                4.170000   0.120000   4.290000 (  4.294663)
 escapeHTML2                4.200000   0.150000   4.350000 (  4.357417)
 string.length : 60
 escapeHTML1                8.020000   0.140000   8.160000 (  8.165549)
 escapeHTML2                8.110000   0.080000   8.190000 (  8.196204)
 string.length : 100
 escapeHTML1               12.090000   0.170000  12.260000 ( 12.270974)
 escapeHTML2               12.190000   0.160000  12.350000 ( 12.343745)
 string.length : 200
 escapeHTML1               21.760000   0.200000  21.960000 ( 21.962078)
 escapeHTML2               21.980000   0.160000  22.140000 ( 22.146721)

文字列の長さによらず，非破壊的メソッドである String#gsub() の方がわずかに速いですね．

置換が発生しない場合の結果

BASE_STRING を置換の発生しない文字列に替えて再実行した結果です．

 BASE_STRING   : "foo + `bar` + (baz) "
 escapeHTML1() : "foo + `bar` + (baz) "
 escapeHTML2() : "foo + `bar` + (baz) "
                                user     system      total        real
 string.length : 20
 escapeHTML1                1.760000   0.070000   1.830000 (  1.828672)
 escapeHTML2                1.250000   0.070000   1.320000 (  1.317440)
 string.length : 60
 escapeHTML1                1.920000   0.130000   2.050000 (  2.050873)
 escapeHTML2                1.370000   0.130000   1.500000 (  1.502491)
 string.length : 100
 escapeHTML1                2.280000   0.040000   2.320000 (  2.313158)
 escapeHTML2                1.650000   0.070000   1.720000 (  1.716828)
 string.length : 200
 escapeHTML1                2.730000   0.140000   2.870000 (  2.872649)
 escapeHTML2                2.140000   0.070000   2.210000 (  2.212752)

今度は文字列の長さによらず，破壊的メソッドString#gsub!() の方が速いという結果でした．

考察っぽく

結果を踏まえて String#gsub() および String#gsub!() を実装を妄想…じゃなくて想像してみる．

  1. 正規表現にマッチするかどうかのチェック
  2. 置換結果を格納する String オブジェクト(あるいは相当の機能をもつ何かバッファとなるもの)の生成
  3. 置換結果を String オブジェクトに格納
  4. 結果を返す

1. から 3. までを共通にして，4の部分だけ処理を変えるという実装じゃなかろうか？

正規表現にマッチしない場合は，1. の後で

  • String#gsub() の場合 self.dup して返す
  • String#gsub!() の場合 nil を返す

という処理になるので String#dup() の分だけ String#gdub!() が速くなる．

正規表現にマッチしたときに，4.の部分で

  • String#gsub() の場合は結果を格納した String オブジェクトをそのまま返す
  • String#gsub!() の場合は self の内容を結果を格納した String オブジェクトで置き換え self を返す

という処理になり String#replace() 相当の処理の分だけ String#gsub!() の方が遅いのではないかと推測できる．

以上全部推測です．実際のところは Ruby のソースコードを読めば解るはずです．
めんどくさいから私は読んで確認してませんが…

まとめ

今日学んだこと!

  • 置換が発生する場合は String#gsub() の方がちょっと速い．
  • 置換が発生しない場合は String#gsub!() の方が速い．

普通は置換させるために使うわけで String#gsub() でよさそうですね．もし扱うデータが事前に解っていて置換が発生するようなデータが少いことが確定していれば String#gsub!() を選ぶのも通かもしれません．でも置換が発生しない場合を想定するならば以下のようなコードの方が速いです．

ESCAPE_TABLE = {
	'&' => '&amp;',
	'"' => '&quot;',
	'<' => '&lt;',
	'>' => '&gt;'
}
 
def escape(str)
	str.gsub(/[&"<>]/n) {|str| ESCAPE_TABLE[str] }
end

もちろんこの程度の差でアプリケーションの性能に影響することってほとんどないと思いますけど♪

*1:http://ruby-lang.org/ja/man/?cmd=view;name=String