カタカタ
Java で、リフレクション経由でメソッドを呼ぶときにはちゃんと実引数の型チェックが行われるのだが、JNI からだと省略されるみたい。で、やってみたら Throwable じゃないオブジェクトも throw できたり。Mac での例。
$ cat Test.java public class Test { static { System.loadLibrary("Test"); } public static void main(String[] args) { try { throwObject(new Uncatchable()); } catch (Throwable e) { System.out.println("Caught " + e.getMessage()); } System.out.println("Exit"); } static native void throwObject(Object obj); } class Uncatchable { void hoge1() { System.err.println("<Uncatchable (1)>"); } void hoge2() { System.err.println("<Uncatchable (2)>"); } } $ cat Test.c #include <jni.h> JNIEXPORT void Java_Test_throwObject(JNIEnv *env, jclass cls, jobject obj) { if ((*env)->Throw(env, obj)) { (*env)->ThrowNew(env, (*env)->FindClass(env, "java/lang/RuntimeException"), "Cannot throw it!"); } } $ javac Test.java $ gcc -dynamiclib -m64 -o libTest.jnilib -I/System/Library/Frameworks/JavaVM.framework/Headers Test.c $ java Test Exception in thread "main" <Uncatchable (1)>
しれっと良からぬことになってしまった。(結果は環境によって異なるし、クラッシュする場合もある。)
Linux での実行例。
$ javac Test.java $ gcc -shared -fPIC -o libTest.so -I/usr/lib/jvm/java-6-sun/include{,/linux} Test.c $ java -Djava.library.path=. Test Exception in thread "main" <Uncatchable (2)>
副産物
Java 1.6。
$ cat Test.java import java.util.regex.*; public class Test { public static void main(String[] args) { String query = "Hello, world."; StringBuilder text = new StringBuilder(13 * 1024); for (int i = 0; i < 1024; i++) text.append("Hello, world!"); if (args[0].equals("String")) testString(text.toString(), query); else if (args[0].equals("Pattern")) testPattern(text.toString(), query); } private static void testString(String text, String query) { for (int i = 0; i < 100000; i++) text.contains(query); } private static void testPattern(String text, String query) { for (int i = 0; i < 100000; i++) { Pattern p = Pattern.compile(query, Pattern.LITERAL); p.matcher(text).find(); } } } $ javac Test.java $ time java Test String 4.59 real 4.53 user 0.04 sys $ time java Test Pattern 1.39 real 1.41 user 0.04 sys
テストケースがとても作為的ですが。後者は Boyer-Moore 法っぽい(前処理は単純な O(m2))。
idempotent
$ cat test.c #include <stdio.h> #include <string.h> size_t strlen(const char *p) { return (strchr(p, ',') - p); } char *f(char *p) { return strcat(p, ", World"); } int main() { char str[64] = "Hello"; puts(f(str)); puts(f(f(str))); puts(f(f(f(str)))); } $ gcc-4.0 -O3 test.c && ./a.out Hello, World Hello, World Hello, World続きを読む
あげいん
$ cat regex.pl $query = "b" x (1024 * 1024) . "x"; $pat = '^b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b$'; print ($query =~ $pat ? "yes\n" : "no\n"); $ $ time perl regex.pl no real 0m0.009s user 0m0.004s sys 0m0.005s
超速い。Perl すごい!
おもむろに、パターンの最後の b を [b] に変えてみる。
$ cat regex2.pl $query = "b" x (1024 * 1024) . "x"; $pat = '^b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*[b]$'; print ($query =~ $pat ? "yes\n" : "no\n"); $ $ time perl regex2.pl ^C real 60m0.461s user 59m47.757s sys 0m3.055s
超遅い。Perl すごい!
【追記】5.10.0 版(?)
^b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*[ab]$
^b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b(?:.*b|.*b)$
流行中の
正規表現ベンチ、もしくは文字列生成ベンチ。Python Challenge が一段落したのでやってみる。
ベースライン、速さに定評のある C。
$ gcc -O2 regex.c $ time ./a.out no real 0m0.737s user 0m0.734s sys 0m0.003s
なんか遅い。Mac だからか。
意外と古参 Ruby。
$ cat regex.rb query = "b" * (1024 * 1024) + "x"; pat = /^b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b$/; puts(query =~ pat ? "yes" : "no"); $ $ time ruby regex.rb ^Cregex.rb:3:in `=~': Interrupt from regex.rb:3 real 60m0.368s user 59m36.195s sys 0m4.325s
まさかの長考。
駿足ラクダ O'Caml。
$ cat regex.ml let query = String.make (1024 * 1024) 'b' ^ "x" and pat = Str.regexp "^b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b$" in print_endline (if Str.string_match pat query 0 then "yes" else "no") $ $ ocamlopt str.cmxa regex.ml $ time ./a.out ^C real 60m0.476s user 59m53.573s sys 0m1.797s
駄目でした。
純真無垢の怠け者 Haskell。
$ cat regex.hs import Text.Regex query = replicate (1024 * 1024) 'b' ++ "x" pat = mkRegex "^b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b$" main = putStrLn $ if matchRegex pat query == Nothing then "no" else "yes" $ $ ghc --make regex.hs 2> /dev/null $ time ./regex no real 0m0.913s user 0m0.883s sys 0m0.027s
これは全く怠けていないぞ。
何でも入ってる D 言語。
$ cat regex.d import std.stdio; import std.string; import std.regexp; void main() { auto query = repeat("b", 1024 * 1024) ~ "x"; auto pat = RegExp("^b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b$"); writefln(pat.test(query) ? "yes" : "no"); } $ $ gdc regex.d $ time ./a.out ^C real 60m0.415s user 59m37.156s sys 0m3.480s
たぶん初めて書いた。
探し物、あります grep。
$ perl -e 'print ("b" x (1024 * 1024) . "x")' > query $ time grep -c '^b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b$' query 0 real 0m3.295s user 0m3.193s sys 0m0.021s
このくらいが丁度いい速さなんじゃないか。
我らが LiLFeS。
$ cat regex.lil :- module("regex_bench"). query <- pred. query_sub <- pred. pat <- pred. main <- pred. query(Q) :- query_sub(20, Q1), strcat(Q1, "x", Q). query_sub(X, Q) :- X <= 0, !, Q = "b". query_sub(X, Q) :- X1 is X - 1, query_sub(X1, Q1), strcat(Q1, Q1, Q). pat("^b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b$"). main :- query(Q), pat(P), regex_match(P, Q). $ $ time lilfes -l regex.lil -e "?- main." 2> /dev/null no real 0m0.937s user 0m0.920s sys 0m0.015s
正規表現が使える時点で何かがすごいと思うのです。
孤独の lysh。
$ cat regex.lsh :let query := nth 20 (iter (:\x := x :++ x) b) :++ x :and pat := '^b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b.*b$' :in regex query pat |> :\x := println :@ ifte (nil? x) no yes $ $ time lysh regex.lsh no real 0m0.835s user 0m0.808s sys 0m0.019s
なんともコメントしづらい。