Suffix Array Construction Benchmark

Benchmark results:

Timing results on Core 2 Duo
Corpus	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	1289730704	263.643	717.197	1044.819	955.447	181.437	650.916	1927.695	266.178	659.009
ACT-Executable	4938680	0.306	1.072	2.059	0.456	0.397	1.422	3.187	0.594	1.003
ACT-Graphics	12466304	1.144	2.747	5.184	1.388	0.822	2.965	4.459	1.356	2.422
ACT-Sound	8702392	0.916	2.319	4.428	0.934	0.937	4.956	12.275	1.297	1.872
ACT-Text	4920286	0.369	0.756	2.050	0.594	0.450	1.266	3.175	0.619	1.241
Artificial Corpus	300001	0.084	0.106	0.200	0.425	0.084	0.234	0.119	0.109	0.112
Calgary Corpus	3141622	0.409	0.997	1.438	0.503	0.453	0.900	1.022	0.566	0.722
Canterbury Corpus	2810784	0.337	0.759	1.222	0.516	0.350	0.672	0.781	0.503	0.587
Large Canterbury Corpus	11159482	0.981	1.638	4.947	1.419	1.175	3.319	10.372	1.565	2.953
Manzini's Corpus	896819039	186.047	278.297	769.319	323.347	132.866	501.503	1501.054	158.944	465.809
Maximum Compression Testfiles	53134726	7.131	12.647	34.512	10.625	5.200	17.769	49.391	6.747	16.366
Miscellaneous Corpus	1000000	0.078	0.153	0.347	0.122	0.106	0.200	0.328	0.122	0.128
Protein Corpus	7154401	0.572	1.500	2.834	0.893	0.822	2.391	6.447	0.881	1.362
Silesia Corpus	211938580	28.694	133.393	144.306	40.713	25.544	92.891	283.378	31.556	79.781
Testfiles	4194304	2.509	34.450	2.391	3.447	0.338	0.681	1.869	36.590	5.753
The Gauntlet	67050103	34.066	246.363	69.581	570.066	11.894	19.747	49.838	24.728	78.897

Timing results on Pentium M
Corpus	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	1289730704	675.813	7291.617	2363.258	1992.735	479.520	1939.927	9690.051	576.560	2406.991
ACT-Executable	4938680	0.817	3.014	4.194	1.027	1.125	5.007	12.610	1.360	3.231
ACT-Graphics	12466304	2.388	7.429	10.215	2.954	1.969	9.293	17.483	2.902	7.246
ACT-Sound	8702392	1.925	6.171	9.798	2.542	2.904	17.587	31.147	2.808	5.222
ACT-Text	4920286	1.017	1.957	4.855	1.346	1.324	5.051	11.867	1.398	4.096
Artificial Corpus	300001	0.136	0.166	0.316	0.761	0.122	0.561	0.210	0.180	0.196
Calgary Corpus	3141622	0.831	2.356	2.474	0.943	0.871	2.177	3.503	1.074	1.827
Canterbury Corpus	2810784	0.719	1.775	2.203	1.050	0.671	1.714	2.796	0.923	1.749
Large Canterbury Corpus	11159482	3.057	4.246	12.804	3.711	3.637	13.223	31.201	3.749	8.748
Manzini's Corpus	896819039	437.123	5891.914	1699.748	697.401	342.194	1467.454	8620.099	342.252	1825.437
Maximum Compression Testfiles	53134726	16.504	32.517	79.176	26.302	14.683	60.753	135.327	15.620	48.067
Miscellaneous Corpus	1000000	0.162	0.577	0.685	0.246	0.268	0.799	1.532	0.260	0.541
Protein Corpus	7154401	1.486	4.464	6.642	1.965	2.422	9.087	19.712	2.051	4.312
Silesia Corpus	211938580	68.140	381.357	323.212	89.472	68.657	281.136	651.020	69.628	219.511
Testfiles	4194304	26.712	119.181	12.953	23.051	1.450	3.010	7.865	80.047	18.232
The Gauntlet	67050103	114.797	834.494	193.983	1139.963	37.222	63.072	143.679	52.306	258.575

Timing results on PowerPC G5
Corpus	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	1289730704	1682.654	4737.826	5532.687	2935.568	1061.141	3077.291	9352.861	1007.517	4204.685
ACT-Executable	4938680	1.158	4.616	4.731	1.346	1.428	5.670	16.207	1.670	3.978
ACT-Graphics	12466304	3.506	12.614	11.241	3.697	2.507	11.000	24.511	3.434	10.184
ACT-Sound	8702392	4.293	15.427	16.561	5.148	5.118	26.133	58.116	4.249	8.806
ACT-Text	4920286	1.639	3.273	5.990	1.867	1.860	5.978	17.842	1.766	6.007
Artificial Corpus	300001	0.068	0.138	0.237	0.518	0.063	0.497	0.154	0.122	0.140
Calgary Corpus	3141622	0.686	2.875	2.282	0.761	0.762	2.365	4.744	1.013	1.968
Canterbury Corpus	2810784	0.580	2.175	1.904	0.773	0.567	1.616	3.451	0.851	1.634
Large Canterbury Corpus	11159482	5.198	9.113	16.392	5.453	5.158	16.158	51.371	5.340	14.213
Manzini's Corpus	896819039	1244.484	3026.693	4273.981	1540.585	782.664	2384.167	7294.444	729.719	2917.944
Maximum Compression Testfiles	53134726	33.098	78.928	143.646	46.523	25.209	72.457	215.716	25.861	82.271
Miscellaneous Corpus	1000000	0.316	0.908	0.881	0.335	0.421	1.024	2.078	0.339	0.713
Protein Corpus	7154401	2.806	9.968	8.445	2.914	4.090	12.570	33.457	3.085	7.211
Silesia Corpus	211938580	166.572	624.345	666.309	181.118	141.888	444.314	1344.418	130.561	464.288
Testfiles	4194304	11.059	100.097	17.184	21.558	1.982	3.251	6.742	7.392	13.726
The Gauntlet	67050103	207.191	846.655	362.902	1122.974	87.423	90.091	279.608	92.113	671.603

The current fastest three programs:

On Core 2 Duo:

1. divsufsort (1.2.3)        181.437 sec
2. Archon4r0                 263.643 sec
3. MSufSort (3.1.1 beta)     266.178 sec

On Pentium M:

1. divsufsort (1.2.3)        479.520 sec
2. MSufSort (3.1.1 beta)     576.560 sec
3. Archon4r0                 675.813 sec

On PowerPC G5:

1. MSufSort (3.1.1 beta)    1007.517 sec
2. divsufsort (1.2.3)       1061.141 sec
3. Archon4r0                1682.654 sec

Benchmark environments:


	Core 2 Duo	Pentium M	PowerPC G5
Processor	2.66 GHz Intel Core 2 Duo E6750	1.7 GHz Intel Pentium M	1.8 GHz PowerPC G5
L1 Cache	(32 Kb + 32 Kb) x 2	32 Kb + 32 Kb	(I)64 Kb + (D)32 Kb
L2 Cache	4 Mb	1 Mb	512 Kb
RAM	2 Gb main memory	1 Gb main memory	1 Gb main memory
Operating system	Windows XP Home SP 2	Windows XP Professional SP 2	Darwin 8.11.0
Compiler	gcc version 4.2.3	gcc version 4.2.3	gcc version 4.2.3

All programs were compiled with gcc/g++ using '-O3 -fomit-frame-pointer' optimization options. Times are the average of five runs, in seconds, and were measured using the standard Unix/Cygwin 'time' command. (user + system)

The suffix array construction programs:


Program	Author(s)	URL
Archon4r0	Dima Malyshev	http://forum.compression.ru/viewtopic.php?t=352
BPR	Klaus-Bernd Schürmann and Jens Stoye	http://bibiserv.techfak.uni-bielefeld.de/bpr/
DC32	Stefan Burkhardt and Juha Kärkkäinen	http://www.cs.helsinki.fi/juha.karkkainen/publications/cpm03.tar.gz
Deep-Shallow	Giovanni Manzini and Paolo Ferragina	http://www.mfn.unipmn.it/~manzini/lightweight/
divsufsort-1.2.3	Yuta Mori	http://homepage3.nifty.com/wpage/software/libdivsufsort.html
KA	Pang Ko	http://ko.pang.cn.googlepages.com/software2
KS	Juha Kärkkäinen and Peter Sanders	http://www.mpi-inf.mpg.de/~sanders/programs/suffix/
MSufSort-3.1.1 beta	Michael A. Maniscalco and Simon J. Puglisi	http://www.michael-maniscalco.com/msufsort.htm
qsufsort	Jesper Larsson and Kunihiko Sadakane	http://www.larsson.dogma.net/research.html

The test files:


Test files	URL
ACT - Test files	http://compression.ca/act/act-files.html
Artificial Corpus	http://corpus.canterbury.ac.nz/descriptions/#artificl
Calgary Corpus	http://corpus.canterbury.ac.nz/descriptions/#calgary
Canterbury Corpus	http://corpus.canterbury.ac.nz/descriptions/#cantrbry
Large Canterbury Corpus	http://corpus.canterbury.ac.nz/descriptions/#large
Manzini's Large Corpus	http://www.mfn.unipmn.it/~manzini/lightweight/corpus/
Maximum Compression - Test files	http://www.maximumcompression.com/data/files/index.html
Miscellaneous Corpus	http://corpus.canterbury.ac.nz/descriptions/#misc
Protein Corpus	http://www.data-compression.info/Corpora/ProteinCorpus/
Silesia Corpus	http://sun.aei.polsl.pl/~sdeor/silesia.html
Testfiles	http://homepage3.nifty.com/wpage/junk/generator2.c.bz2
The Gauntlet	http://www.michael-maniscalco.com/testset/gauntlet/

Recent updates:

2008-03-02: Added C2D results.
2008-03-02: Added divsufsort-1.2.3 (static lib).
2007-10-08: Added Archon4r0.
2007-07-16: Added divsufsort-1.2.1 (static lib).
2007-07-16: Updated MSufSort-3.1.1beta.
2007-07-16: Removed MSufSort-3.1beta, divsufsort-1.0.2, divsufsort-1.2.0 (shared and static libs).
2007-04-22: Added MSufSort-3.1.1b.
2007-04-14: Added divsufsort-1.2.0 (shared and static libs).
2007-02-17: Benchmarks moved to new location.
2007-02-10: Added new testfiles "The Gauntlet".
2007-02-05: Updated MSufSort-3.1beta.
2007-02-04: Added MSufSort-3.1beta.
2007-01-21: Added the new results (1.7GHz Pentium M).
2007-01-09: Added MSufSort-3.0beta.
2006-05-14: Replaced Archon with a new version (Archon3r3).
2006-05-06: Added Archon3r1.
2006-01-01: Added divsufsort-1.0.2.
2005-12-02: Replaced Archon with a new version.
2005-11-30: Added Archon2-pro.
2005-11-08: Added MSufSort-2.1, 2.2 and divsufsort-1.0.0, 1.0.1.