Skip to main content Link Search Menu Expand Document (external link)

SACABench: Benchmarking Suffix Array Construction

DOI slides pdf code


We present a practical comparison of suffix array construction algorithms on modern hardware. The benchmark is conducted using our new benchmark framework SACABench, which allows for an easy deployment of publicly available implementations, simple plotting of the results, and straight forward support to include new construction algorithms. We use the framework to develop a construction algorithm running on the GPU that is competitive with the fastest parallel algorithm in our test environment.


  author    = {Johannes Bahne and Nico Bertram and Marvin Böcker and Jonas Bode and Johannes Fischer and Hermann Foot and Florian Grieskamp and Florian Kurpicz and Marvin Lbel and Oliver Magiera and Rosa Pink and David Piper and Christopher Poeplau},
  title     = {SACABench: Benchmarking Suffix Array Construction},
  booktitle = {SPIRE},
  series    = {Lecture Notes in Computer Science},
  volume    = {11811},
  pages     = {407–416},
  publisher = {Springer},
  doi       = {10.1007/978-3-030-32686-9 29},
  year      = {2019}