white page / memo 3

07年版 Faster Suffix Sorting

2007/05/04

links の Suffix Arrays に "Faster Suffix Sorting" (2007) を追加しました。99年のTech. reportとの違いは実験結果くらいかな。

Jesper Larsson and Kunihiko Sadakane, Faster Suffix Sorting, Theoretical Computer Science, 2007.
[.ps (eprints.csce.kyushu-u.ac.jp)]

popcount

2007/05/03

32/64bit用の popcount をいくつか作って、PowerMac G5 1.8GHzで速度を測定してみました。

使用したアルゴリズムは以下の4つ。 (_32は32bit用、_64は64bit用、_32x2は64bit用だけど_32のコードを使う)

Sequential Shifting (SS)

static
int
_sequential_shifting_32(uint32_t number) {
  int counter = 0;
  while(number != 0) {
    counter += number & 1;
    number >>= 1;
  }
  return counter;
}
static
int
_sequential_shifting_32x2(uint64_t number) {
  return
    _sequential_shifting_32(number & 0xffffffff) +
    _sequential_shifting_32(number >> 32);
}

static
int
_sequential_shifting_64(uint64_t number) {
  int counter = 0;
  while(number != 0) {
    counter += number & 1;
    number >>= 1;
  }
  return counter;
}

Arithmetic Logic Counting (AL)

static
int
_arithmetic_logic_counting_32(uint32_t number) {
  int counter = 0;
  while(number != 0) {
    counter += 1;
    number &= number - 1;
  }
  return counter;
}

static
int
_arithmetic_logic_counting_32x2(uint64_t number) {
  return
    _arithmetic_logic_counting_32(number & 0xffffffff) +
    _arithmetic_logic_counting_32(number >> 32);
}

static
int
_arithmetic_logic_counting_64(uint64_t number) {
  int counter = 0;
  while(number != 0) {
    counter += 1;
    number &= number - 1;
  }
  return counter;
}

Emulated Popcount (Em. Popcount)

static
int
_emulated_popcount_32(uint32_t number) {
  /* type 4 */
  number = (number & 0x55555555) + ((number >>  1) & 0x55555555);
  number = (number & 0x33333333) + ((number >>  2) & 0x33333333);
  number = (number + (number >>  4)) & 0x0f0f0f0f;
  number =  number + (number >>  8);
  number =  number + (number >> 16);
  return (int)(number & 0x3f);
}

static
int
_emulated_popcount_32x2(uint64_t number) {
  return
    _emulated_popcount_32(number & 0xffffffff) +
    _emulated_popcount_32(number >> 32);
}

static
int
_emulated_popcount_64(uint64_t number) {
  /* type 4 */
  number = (number & 0x5555555555555555ULL) +
           ((number >>  1) & 0x5555555555555555ULL);
  number = (number & 0x3333333333333333ULL) +
           ((number >>  2) & 0x3333333333333333ULL);
  number = (number + (number >>  4)) & 0x0f0f0f0f0f0f0f0fULL;
  number =  number + (number >>  8);
  number =  number + (number >> 16);
  number =  number + (number >> 32);
  return (int)(number & 0x7f);
}

Lookup Table (Lookup)

static
const int
_popcount_table[256] = {
  0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
  4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};

static
int
_lookup_table_32(uint32_t number) {
  int counter = 0;
  counter += _popcount_table[ number        & 0xff];
  counter += _popcount_table[(number >>  8) & 0xff];
  counter += _popcount_table[(number >> 16) & 0xff];
  counter += _popcount_table[(number >> 24) & 0xff];
  return counter;
}

static
int
_lookup_table_32x2(uint64_t number) {
  return
    _lookup_table_32(number & 0xffffffff) +
    _lookup_table_32(number >> 32);
}

static
int
_lookup_table_64(uint64_t number) {
  int counter = 0;
  counter += _popcount_table[ number        & 0xff];
  counter += _popcount_table[(number >>  8) & 0xff];
  counter += _popcount_table[(number >> 16) & 0xff];
  counter += _popcount_table[(number >> 24) & 0xff];
  counter += _popcount_table[(number >> 32) & 0xff];
  counter += _popcount_table[(number >> 40) & 0xff];
  counter += _popcount_table[(number >> 48) & 0xff];
  counter += _popcount_table[(number >> 56) & 0xff];
  return counter;
}

測定方法とかはソースコードを見てくだされ。popcount_test.c

gcc (4.1.2) のコンパイルオプション '-O3 -m32' での結果

コンパイルオプション '-O3 -m64' での結果

まあ見ての通り、Lookup が速いという結果になりました。ちなみに、Lookup で最も良かったのは、 -m64 でコンパイルした 64bit用のものです。

MSufSort-3.1.1b

2007/04/22

MSufSort-3.1.1beta が公開されています。サフィックスのソートを一番大きい bucket から行うように変更されたみたいです。

                              Running times (in sec)
Program              test1     test2     test3    totals
-------           --------  --------  --------  --------
Archon3r3         1842.609    42.591  1205.943  3091.143
BPR                  6.449     1.852   771.879   780.180
DC32                 7.140     7.130     8.111    22.381
Deep-Shallow        20.829    20.849    11.696    53.374
DivSufSort-1.0.2     4.716     4.766     2.142    11.624
DivSufSort-1.2.0     1.801     1.110     1.471     4.382
KA                   2.343     2.273     2.022     6.638
KS                   5.237     5.227     5.237    15.701
MSufSort-3.1b       13.829     1.091  1625.036  1639.956
MSufSort-3.1.1b      2.600     6.071     2.316    10.987
qsufsort             8.121     8.061    10.074    26.256

昨日のファイルでテストをしたところ、3.1bとは全く違う結果になりました。 1 と 3 ではかなり(というかもの凄く)改善されてます。・・なぜ 2 だけ遅くなるのだろうか ?

Test 1

2007/04/21

サフィックスソートアルゴリズムの丈夫さをテストするためのファイルを3つほど作り、それぞれのアルゴリズムの Suffix Array の構築にかかった時間を計測してみた。

test1.gz, test2.gz, test3.bz2, generator.c.gz

                              Running times (in sec)
Program              test1     test2     test3    totals
-------           --------  --------  --------  --------
Archon3r3         1842.609    42.591  1205.943  3091.143
BPR                  6.449     1.852   771.879   780.180
DC32                 7.140     7.130     8.111    22.381
Deep-Shallow        20.829    20.849    11.696    53.374
DivSufSort-1.0.2     4.716     4.766     2.142    11.624
DivSufSort-1.2.0     1.801     1.110     1.471     4.382
KA                   2.343     2.273     2.022     6.638
KS                   5.237     5.227     5.237    15.701
MSufSort-3.1b       13.829     1.091  1625.036  1639.956
qsufsort             8.121     8.061    10.074    26.256

ふぅむ・・、O(n), O(n log n) time のアルゴリズムはそれなりに安定した結果になったけど、やはりそれ以外の O(n^2), O(n^2 log n) time のアルゴリズムは構築にかなりの時間がかかりますねえ。

--------------------

links にいくつか論文を追加しました。

Compressed Suffix Trees:
- Kunihiko Sadakane, Compressed Suffix Trees with Full Functionality, Theory of Comupting Systems, 2007.
  [.pdf (tcslab.csce.kyushu-u.ac.jp)]
Suffix Arrays:
- Rudolf Ahlswede, Bernhard Balkenhol, Christian Deppe and Martin Frohlich, A Fast Suffix-Sorting Algorithm, General Theory of Information Transfer and Combinatorics, LNCS 2676, Springer-Verlag, pp. 719-734, 2006.
  [.pdf (www.math.uni-bielefeld.de)]
Succinct Data Structures:
- Jeremy Barbay, J. Ian Munro, Meng He and S. Srinivasa Rao, Succinct Indexes for Strings, Binary Relations and Multi-labeled Trees, Proceedings of the 18th ACM-SIAM Symposium on Discrete Algorithms, pp. 680-689, 2007.
  [.pdf (www.cs.uwaterloo.ca)] [.ps (www.cs.uwaterloo.ca)] [.ppt (www.cs.uwaterloo.ca)] [.pdf (www.cs.uwaterloo.ca)] [.ps (www.cs.uwaterloo.ca)]
- Ankur Gupta, Wing-Kai Hon, Rahul Shah and Jeffrey Vitter, Compressed Data Structures: Dictionaries and Data-Aware Measures, Proceedings of the IEEE Data Compression Conference, Snowbird, Utah, 2006.
  [.pdf (www.cs.duke.edu)] [.pdf (www.cs.nthu.edu.tw)]
XBW:
- Paolo Ferragina, Fabrizio Luccio, Giovanni Manzini and S. Muthukrishnan, Compressing and indexing labeled trees, with applications, 2007.
  [.pdf (roquefort.di.unipi.it)]

libdivsufsort-1.2.0 (安定版) リリース

2007/04/14

libdivsufsort の安定版、libdivsufsort-1.2.0 をリリースしました。

1.0.2 からの主な変更点は以下の通りです。

ソートアルゴリズムの大幅な改良を行いました。
ライセンスを GNU Lesser General Public License から MIT/X11 License に変更しました。
デフォルトで構築するライブラリを共有ライブラリ(cygwin環境ではDLL)に変更しました。

<< 前のページ | home へ戻る | 次のページ >>

white page

[memo 3]

07年版 Faster Suffix Sorting

popcount

MSufSort-3.1.1b

Test 1

libdivsufsort-1.2.0 (安定版) リリース