« 2008年6月 | トップページ | 2008年8月 »

IS法 その4

そろそろ改良できる箇所が少なくなってきたと思うので、ソースコードを全面的に(といっても100行程度だけど・・)書き直して、プロジェクト名を「sais」に変更しました。 サイス・・古代エジプトの都市の名前だっけ?  他の変更点は、配列SAの未使用領域をなるべくバケット配列として利用させるようにしました。これで少しメモリ使用量が削減されます。あとは・・C++版の追加くらいかな。

CMake versionは少し複雑になってきたので、シンプルな GNU Make versionを作ってみました。

File: sais-lite.zip
Size: 13,154 bytes
SHA1: 904f22769fbc974f6b49c9f38d0cb38b9091cb89
Last update: 2008/12/25

CMake version

File: sais.zip
Size: 26,620 bytes
SHA1: c21bc6f1d3ece5485fb05604ca4bfaee388a73ab
Last update: 2008/12/25

Java language version

File: sais-java.zip
Size: 9,955 bytes
SHA1: b5b88324eabf5f308abd5704309ce981c5bc081f
Last update: 2009/01/10

追記 (2008/07/14): Makefile と suftest.c の誤りを修正。

追記 (2009/01/10): BWTとOpenMP用のコードを追加。Java言語版を追加。

IS1-3 & SAISなどの Suffix array 構築時間を測定した結果が以下になります。

  • DC - Difference-cover algorithm (v = 32)
  • DS - Deep-Shallow sorting algorithm
  • IS1 - ほぼオリジナルと同じ NZC Induced sorting algorithm
  • IS2 - 配列tを排除したIS法
  • IS3 - IS2のincudeSAを改良したIS法
  • SAIS - 今回のIS法
  • KA - Ko-Aluru algorithm
  • LS - Larsson-Sadakane algorithm
Time (in secs)
FilesSize DC DS IS1 IS2 IS3 SAIS KA LS
totals968,063,446 722.19 846.89 426.18 347.94 263.93 257.80 527.85 510.05
chr22.dna34,553,758 19.98 7.06 14.62 12.62 10.87 10.68 17.32 9.35
etext99105,277,340 73.08 32.45 62.05 48.96 39.54 38.26 74.75 51.50
gcc-3.0.tar86,630,400 54.96 34.14 32.06 26.76 20.77 20.31 41.65 36.80
howto39,422,105 22.64 7.82 16.47 13.81 11.27 11.08 21.03 14.81
jdk13c69,728,899 56.08 28.08 26.58 22.66 16.06 15.83 34.48 35.73
linux-2.4.5.tar116,254,720 74.18 24.24 45.51 37.62 29.69 28.88 59.60 49.05
rctail96114,711,151 110.30 56.05 57.23 46.19 33.13 32.52 70.84 63.63
rfc116,421,901 82.44 27.98 53.49 42.14 32.29 31.51 65.47 55.85
sprot34.dat109,617,186 85.72 29.69 57.52 45.21 34.25 33.19 69.04 51.63
w3c2104,201,579 81.75 48.62 40.88 34.68 25.01 24.57 53.34 70.90
abac200,000 0.06 26.48 0.01 0.00 0.00 0.00 0.02 0.02
abba10,500,600 9.89 29.51 2.47 2.25 1.39 1.38 2.51 12.48
book1x2015,375,420 13.07 95.35 6.03 5.53 3.84 3.79 7.44 18.68
fib_s1493035214,930,352 16.18 177.07 5.28 4.31 2.51 2.50 3.88 16.23
fss1012,078,908 13.45 82.75 3.94 3.53 2.02 1.98 3.53 13.06
fss92,851,443 1.44 4.82 0.44 0.38 0.28 0.28 0.58 2.50
houston3,840,000 1.81 114.11 0.30 0.22 0.18 0.18 0.50 1.08
paper5x80981,924 0.38 0.62 0.10 0.08 0.07 0.07 0.17 0.36
test12,097,152 0.94 8.06 0.24 0.18 0.15 0.16 0.33 2.04
test22,097,152 0.94 8.07 0.24 0.21 0.16 0.16 0.32 2.06
test32,097,152 1.02 1.34 0.23 0.20 0.14 0.16 0.39 0.77
test42,097,152 1.02 1.59 0.26 0.22 0.16 0.17 0.39 0.77
test52,097,152 0.86 0.99 0.23 0.18 0.15 0.14 0.27 0.75

構築にかかる時間は多少短くなっていますが・・、今までのような劇的な改善は難しいですねえ。

さて、今回はIS法のメモリ使用量がどれくらい改善したかを確認するために、memusage を使って各プログラムのピーク時のメモリ使用量を測定しました。結果は見ての通り。普通のデータなら、SAIS は Deep-Shallow よりもメモリ使用量が少なくすみます。しかし、最悪時のメモリ使用量は相変わらず 5n+max(2n,4k) bytes なので一長一短か。。

Space (in MiBytes)
FilesSize DC32 DS IS1 IS2 IS3 SAIS KA LS
totals968,063,446 5,423.92 4,630.57 4,890.55 4,691.51 4,691.51 4,616.34 8,226.06 7,385.76
mean- 5.88 5.02 5.30 5.08 5.08 5.00 8.91 8.00
chr22.dna34,553,758 193.60 165.18 178.09 170.40 170.40 164.77 289.97 263.62
etext99105,277,340 589.85 503.23 542.17 514.65 514.65 502.00 907.34 803.20
gcc-3.0.tar86,630,400 485.38 415.87 438.44 420.14 420.14 413.09 709.50 660.94
howto39,422,105 220.88 188.45 203.16 193.03 193.03 187.98 331.54 300.77
jdk13c69,728,899 390.68 333.40 347.01 334.57 334.57 332.49 609.71 531.99
linux-2.4.5.tar116,254,720 651.36 555.76 590.55 565.98 565.98 554.35 977.81 886.95
rctail96114,711,151 642.71 548.32 575.46 553.45 553.45 546.99 1,004.98 875.18
rfc116,421,901 652.29 556.53 588.69 564.35 564.35 555.14 956.52 888.23
sprot34.dat109,617,186 614.17 524.03 554.58 534.37 534.37 522.70 930.06 836.31
w3c2104,201,579 583.82 498.09 519.41 500.36 500.36 496.87 912.00 795.00
abac200,000 1.12 0.98 0.99 0.95 0.95 0.95 1.75 1.53
abba10,500,600 58.83 50.21 51.83 50.09 50.09 50.07 86.20 80.11
book1x2015,375,420 86.15 73.52 76.23 73.51 73.51 73.32 132.42 117.31
fib_s1493035214,930,352 83.65 71.71 74.07 71.19 71.19 71.19 117.16 113.91
fss1012,078,908 67.68 58.05 59.86 57.60 57.60 57.60 107.05 92.16
fss92,851,443 15.98 13.71 14.13 13.60 13.60 13.60 25.27 21.76
houston3,840,000 21.52 18.46 18.88 18.33 18.33 18.31 28.79 29.30
paper5x80981,924 5.50 4.72 4.85 4.69 4.69 4.68 8.59 7.49
test12,097,152 11.75 10.10 10.38 10.00 10.00 10.00 18.34 16.00
test22,097,152 11.75 10.10 10.38 10.00 10.00 10.00 18.34 16.00
test32,097,152 11.75 10.05 10.50 10.12 10.12 10.12 18.34 16.00
test42,097,152 11.75 10.05 10.50 10.12 10.12 10.12 18.34 16.00
test52,097,152 11.75 10.05 10.39 10.01 10.01 10.00 16.04 16.00

とりあえず、IS法の改良はこれにて終了。しばらくは更新しないと思います。

| | コメント (0) | トラックバック (0)

CMake: uninstall target

GNU autotools と違って、 CMake が生成した Makefile には uninstall するためのターゲットがない。 そのため、わざわざ追加しなければいけないのだが、wiki に載っている方法だとインストールされたシンボリックリンクが削除されないことがあったりする。

なので、cmake_uninstall.cmake.in を以下のように変更してみた。

IF(NOT EXISTS "@CMAKE_CURRENT_BINARY_DIR@/install_manifest.txt")
  MESSAGE(FATAL_ERROR "Cannot find install manifest: \"@CMAKE_CURRENT_BINARY_DIR@/install_manifest.txt\"")
ENDIF(NOT EXISTS "@CMAKE_CURRENT_BINARY_DIR@/install_manifest.txt")

FILE(READ "@CMAKE_CURRENT_BINARY_DIR@/install_manifest.txt" files)
STRING(REGEX REPLACE "\n" ";" files "${files}")

SET(NUM 0)
FOREACH(file ${files})
  IF(EXISTS "$ENV{DESTDIR}${file}")
    MESSAGE(STATUS "Looking for \"$ENV{DESTDIR}${file}\" - found")
    SET(UNINSTALL_CHECK_${NUM} 1)
  ELSE(EXISTS "$ENV{DESTDIR}${file}")
    MESSAGE(STATUS "Looking for \"$ENV{DESTDIR}${file}\" - not found")
    SET(UNINSTALL_CHECK_${NUM} 0)
  ENDIF(EXISTS "$ENV{DESTDIR}${file}")
  MATH(EXPR NUM "1 + ${NUM}")
ENDFOREACH(file)

SET(NUM 0)
FOREACH(file ${files})
  IF(${UNINSTALL_CHECK_${NUM}})
    MESSAGE(STATUS "Uninstalling \"$ENV{DESTDIR}${file}\"")
    EXEC_PROGRAM(
      "@CMAKE_COMMAND@" ARGS "-E remove \"$ENV{DESTDIR}${file}\""
      OUTPUT_VARIABLE rm_out
      RETURN_VALUE rm_retval
      )
    IF(NOT "${rm_retval}" STREQUAL 0)
      MESSAGE(FATAL_ERROR "Problem when removing \"$ENV{DESTDIR}${file}\"")
    ENDIF(NOT "${rm_retval}" STREQUAL 0)
  ENDIF(${UNINSTALL_CHECK_${NUM}})
  MATH(EXPR NUM "1 + ${NUM}")
ENDFOREACH(file)

FILE(REMOVE "@CMAKE_CURRENT_BINARY_DIR@/install_manifest.txt")

面倒だけど、インストールしたファイルの存在を全てチェックしてから削除しています。まあ、存在しないファイルを削除しようとしてもエラーは発生しないので、いちいちチェックしなくてもいいのかもしれませんが・・。

| | コメント (0) | トラックバック (0)

« 2008年6月 | トップページ | 2008年8月 »