white page / software / libdivsufsort / results

Benchmark results of suffix sorting algorithms

ACT/Executable
FileName	FileSize	archon3r3	bpr	dc32	divsufsort-1.0.2	dssort	ka	ks	MSufSort-2.2	MSufSort-3.0beta	qsufsort
total	4938680	1.054	4.487	4.713	1.401	1.197	8.348	15.979	2.109	1.505	3.942
101.EXE	438144	0.076	0.665	0.257	0.074	0.079	0.461	0.684	0.146	0.102	0.193
netscape.exe	2934336	0.672	2.546	3.059	0.922	0.772	5.588	11.128	1.341	0.957	2.529
pine.bin	1566200	0.306	1.276	1.397	0.405	0.346	2.299	4.167	0.622	0.446	1.220

ACT/Graphics
FileName	FileSize	archon3r3	bpr	dc32	divsufsort-1.0.2	dssort	ka	ks	MSufSort-2.2	MSufSort-3.0beta	qsufsort
total	12466304	2.918	12.333	11.248	2.696	3.486	15.720	24.373	4.808	3.021	10.071
clegg.tif	2149096	1.182	2.057	2.058	0.676	1.219	3.073	5.677	1.696	0.672	3.395
frymire.tif	3706306	0.624	1.483	4.099	0.643	0.635	3.608	6.744	1.285	0.735	3.199
lena.tif	786568	0.109	1.288	0.529	0.151	0.192	1.120	1.442	0.213	0.182	0.358
monarch.tif	1179784	0.187	1.539	0.892	0.239	0.285	1.748	2.045	0.318	0.281	0.633
peppers.tif	786568	0.102	1.218	0.507	0.133	0.172	1.051	1.375	0.206	0.169	0.330
sail.tif	1179784	0.222	1.658	1.050	0.326	0.321	1.979	2.844	0.372	0.323	0.725
serrano.tif	1498414	0.287	1.332	1.198	0.260	0.341	1.150	1.586	0.361	0.345	0.781
tulips.tif	1179784	0.205	1.758	0.915	0.268	0.321	1.991	2.660	0.357	0.314	0.650

ACT/Sound
FileName	FileSize	archon3r3	bpr	dc32	divsufsort-1.0.2	dssort	ka	ks	MSufSort-2.2	MSufSort-3.0beta	qsufsort
total	8702392	3.937	15.098	16.630	5.333	5.021	36.996	57.829	5.410	4.581	8.899
every.wav	6994092	3.483	13.168	15.040	4.571	4.585	33.282	53.649	4.641	3.915	7.639
mike.wav	1708300	0.454	1.930	1.590	0.762	0.436	3.714	4.180	0.769	0.666	1.260

ACT/Text
FileName	FileSize	archon3r3	bpr	dc32	divsufsort-1.0.2	dssort	ka	ks	MSufSort-2.2	MSufSort-3.0beta	qsufsort
total	4920286	1.548	3.200	6.038	1.875	1.738	8.917	17.627	2.224	1.984	6.106
1musk10.txt	1344739	0.390	0.739	1.438	0.489	0.426	2.201	3.969	0.561	0.503	1.475
anne11.txt	586969	0.106	0.239	0.435	0.157	0.125	0.753	1.169	0.200	0.161	0.446
world95.txt	2988578	1.052	2.222	4.165	1.229	1.187	5.963	12.489	1.463	1.320	4.185

Artificial Corpus
FileName	FileSize	archon3r3	bpr	dc32	divsufsort-1.0.2	dssort	ka	ks	MSufSort-2.2	MSufSort-3.0beta	qsufsort
total	300001	0.286	0.118	0.230	0.054	0.496	0.147	0.142	0.116	0.084	0.105
a.txt	1	0.009	0.006	0.012	0.007	0.008	0.011	0.006	0.018	0.014	0.006
aaa.txt	100000	0.014	0.013	0.078	0.014	0.015	0.025	0.038	0.027	0.019	0.035
alphabet.txt	100000	0.247	0.048	0.085	0.015	0.454	0.044	0.046	0.035	0.021	0.040
random.txt	100000	0.016	0.051	0.055	0.018	0.019	0.067	0.052	0.036	0.030	0.024

Calgary Corpus
FileName	FileSize	archon3r3	bpr	dc32	divsufsort-1.0.2	dssort	ka	ks	MSufSort-2.2	MSufSort-3.0beta	qsufsort
total	3141622	0.551	2.731	2.235	0.713	0.640	3.259	4.635	1.126	0.844	1.915
bib	111261	0.020	0.047	0.064	0.022	0.023	0.081	0.066	0.041	0.031	0.036
book1	768771	0.169	0.331	0.642	0.240	0.193	1.077	1.707	0.270	0.235	0.617
book2	610856	0.112	0.255	0.440	0.160	0.130	0.790	1.277	0.206	0.170	0.449
geo	102400	0.017	0.503	0.057	0.020	0.019	0.077	0.057	0.045	0.034	0.033
news	377109	0.055	0.158	0.216	0.074	0.068	0.428	0.624	0.122	0.088	0.237
obj1	21504	0.010	0.446	0.021	0.009	0.011	0.022	0.014	0.024	0.020	0.010
obj2	246814	0.033	0.530	0.137	0.040	0.043	0.219	0.262	0.089	0.061	0.120
paper1	53161	0.013	0.040	0.034	0.014	0.014	0.040	0.025	0.027	0.021	0.017
paper2	82199	0.016	0.043	0.046	0.018	0.019	0.062	0.042	0.033	0.026	0.024
pic	513216	0.046	0.216	0.412	0.056	0.049	0.283	0.427	0.148	0.066	0.283
progc	39611	0.012	0.035	0.028	0.012	0.013	0.030	0.020	0.025	0.019	0.014
progl	71646	0.015	0.038	0.046	0.016	0.018	0.050	0.036	0.032	0.024	0.024
progp	49379	0.014	0.035	0.034	0.013	0.016	0.035	0.025	0.027	0.021	0.018
trans	93695	0.019	0.054	0.058	0.019	0.024	0.065	0.053	0.037	0.028	0.033

Canterbury Corpus
FileName	FileSize	archon3r3	bpr	dc32	divsufsort-1.0.2	dssort	ka	ks	MSufSort-2.2	MSufSort-3.0beta	qsufsort
total	2810784	0.475	2.071	1.883	0.544	0.666	2.502	3.364	0.913	0.688	1.569
alice29.txt	152089	0.023	0.055	0.081	0.028	0.030	0.128	0.123	0.050	0.038	0.062
asyoulik.txt	125179	0.021	0.044	0.066	0.024	0.025	0.100	0.087	0.042	0.034	0.041
cp.html	24603	0.011	0.028	0.022	0.011	0.012	0.024	0.014	0.023	0.019	0.011
fields.c	11150	0.010	0.028	0.017	0.009	0.010	0.017	0.010	0.021	0.016	0.008
grammar.lsp	3721	0.009	0.018	0.013	0.008	0.009	0.013	0.007	0.019	0.014	0.007
kennedy.xls	1029744	0.191	0.883	0.690	0.181	0.340	0.805	0.967	0.264	0.240	0.493
lcet10.txt	426754	0.064	0.162	0.248	0.093	0.077	0.490	0.744	0.140	0.105	0.292
plrabn12.txt	481861	0.079	0.188	0.296	0.113	0.092	0.601	0.959	0.159	0.121	0.353
ptt5	513216	0.046	0.216	0.409	0.057	0.049	0.281	0.426	0.148	0.066	0.280
sum	38240	0.012	0.431	0.028	0.012	0.013	0.030	0.020	0.027	0.021	0.015
xargs.1	4227	0.009	0.018	0.013	0.008	0.009	0.013	0.007	0.020	0.014	0.007

Large Canterbury Corpus
FileName	FileSize	archon3r3	bpr	dc32	divsufsort-1.0.2	dssort	ka	ks	MSufSort-2.2	MSufSort-3.0beta	qsufsort
total	11159482	4.978	9.010	16.817	5.028	5.152	21.376	50.909	6.666	6.479	14.281
bible.txt	4047392	1.669	3.766	6.018	1.805	1.841	8.129	18.816	2.107	2.201	5.933
E.coli	4638690	2.503	3.529	7.487	2.259	2.394	8.559	22.700	3.321	3.259	5.122
world192.txt	2473400	0.806	1.715	3.312	0.964	0.917	4.688	9.393	1.238	1.019	3.226

Maximum Compression Testfiles
FileName	FileSize	archon3r3	bpr	dc32	divsufsort-1.0.2	dssort	ka	ks	MSufSort-2.2	MSufSort-3.0beta	qsufsort
total	53134726	31.146	75.123	142.003	25.489	44.443	106.010	212.898	31.626	36.142	82.017
A10.jpg	842468	0.188	1.634	0.790	0.256	0.272	1.515	2.510	0.443	0.295	0.499
acrord32.exe	3870784	0.837	3.416	4.041	1.153	1.001	7.404	14.461	1.646	1.174	3.129
english.dic	4067439	1.086	1.852	3.557	1.040	6.391	5.565	10.576	1.159	1.156	2.522
FlashMX.pdf	4526946	1.583	7.253	6.706	2.058	2.233	16.084	27.416	2.695	2.023	4.378
fp.log	20617071	19.915	44.902	101.256	14.236	22.506	42.726	94.048	16.250	24.509	48.557
mso97.dll	3782416	0.992	4.199	4.399	1.362	1.235	9.081	17.233	1.875	1.334	3.529
ohs.doc	4168192	3.730	5.094	9.339	2.124	7.439	7.579	14.190	3.265	2.083	8.436
rafale.bmp	4149414	0.779	1.876	3.333	0.972	0.932	4.783	7.892	1.164	1.075	2.730
vcfiu.hlp	4121418	0.983	2.667	4.419	1.062	1.248	5.304	12.049	1.661	1.172	4.129
world95.txt	2988578	1.053	2.230	4.163	1.226	1.186	5.969	12.523	1.468	1.321	4.108

Manzini's Corpus
FileName	FileSize	archon3r3	bpr	dc32	divsufsort-1.0.2	dssort	ka	ks	MSufSort-2.2	MSufSort-3.0beta	qsufsort
total	896819039	1082.065	2385.806	4237.875	865.685	1515.145	3054.700	6984.267	801.414	935.080	2919.138
chr22.dna	34553758	37.155	47.104	122.750	34.173	37.159	91.669	252.932	30.046	38.105	56.203
etext99	105277340	133.331	290.010	459.872	123.558	169.689	454.323	953.332	84.734	132.196	370.944
gcc-3.0.tar	86630400	95.998	158.940	281.673	60.619	119.520	243.357	613.038	61.228	68.196	214.871
howto	39422105	31.089	60.400	118.244	30.727	38.094	123.278	308.768	28.125	32.132	91.275
jdk13c	69728899	106.773	200.643	412.119	62.553	191.852	190.663	473.970	81.385	73.537	243.478
linux-2.4.5.tar	116254720	94.065	196.114	384.127	84.030	113.489	370.690	893.842	80.430	92.626	281.473
rctail96	114711151	199.802	465.723	821.563	134.823	323.123	416.104	919.995	131.358	150.607	460.231
rfc	116421901	110.361	289.645	477.644	102.502	136.304	404.105	918.116	97.435	111.461	361.423
sprot34.dat	109617186	136.805	375.457	604.647	121.300	171.632	433.008	897.780	107.106	133.157	369.527
w3c2	104201579	136.686	301.770	555.236	111.400	214.283	327.503	752.494	99.567	103.063	469.713

Miscellaneous Corpus
FileName	FileSize	archon3r3	bpr	dc32	divsufsort-1.0.2	dssort	ka	ks	MSufSort-2.2	MSufSort-3.0beta	qsufsort
total	1000000	0.289	0.891	0.904	0.420	0.308	1.412	2.093	0.428	0.363	0.721
pi.txt	1000000	0.289	0.891	0.904	0.420	0.308	1.412	2.093	0.428	0.363	0.721

Protein Corpus
FileName	FileSize	archon3r3	bpr	dc32	divsufsort-1.0.2	dssort	ka	ks	MSufSort-2.2	MSufSort-3.0beta	qsufsort
total	7154401	2.567	9.884	8.616	4.062	2.736	16.715	33.304	3.720	3.596	7.239
hi	509519	0.086	0.598	0.305	0.131	0.096	0.716	1.111	0.165	0.130	0.278
hs	3295751	1.290	4.595	4.330	2.070	1.370	8.306	17.112	1.827	1.816	3.570
mj	448779	0.071	0.506	0.246	0.107	0.081	0.590	0.890	0.146	0.109	0.236
sc	2900352	1.120	4.185	3.735	1.754	1.189	7.103	14.191	1.582	1.541	3.155

Silesia Corpus
FileName	FileSize	archon3r3	bpr	dc32	divsufsort-1.0.2	dssort	ka	ks	MSufSort-2.2	MSufSort-3.0beta	qsufsort
total	211938580	154.227	617.668	661.660	158.928	176.353	580.263	1332.105	155.102	159.811	462.523
dickens	10192446	7.181	14.147	24.187	7.410	8.185	28.890	70.355	6.483	8.059	19.272
mozilla	51220480	24.522	66.370	128.646	31.468	31.944	154.509	344.728	33.058	28.729	90.981
mr	9970564	6.509	11.149	22.425	6.701	5.395	24.427	51.986	7.219	7.889	21.487
nci	33553445	41.510	307.422	178.042	35.937	46.225	56.744	195.990	34.156	35.634	116.557
ooffice	6152192	2.006	6.790	9.027	2.729	2.525	15.413	33.621	3.417	2.518	7.215
osdb	10085684	6.708	17.824	26.798	8.498	7.737	36.679	64.313	9.329	6.904	20.254
reymont	6627202	3.828	11.460	13.882	4.097	3.873	15.035	34.827	4.298	4.854	13.345
samba	21606400	10.969	20.868	44.368	10.134	12.544	48.596	117.419	11.874	11.360	40.900
sao	7251944	3.533	11.848	15.001	4.987	4.604	28.609	36.641	4.899	4.415	10.034
webster	41458703	41.448	135.307	176.545	38.452	46.137	134.037	320.931	33.047	42.269	103.746
x-ray	8474240	3.956	10.714	14.382	6.697	4.639	28.895	43.206	4.589	5.025	10.465
xml	5345280	2.057	3.769	8.357	1.818	2.545	8.429	18.088	2.733	2.155	8.267

totals
CorpusName	CorpusSize	archon3r3	bpr	dc32	divsufsort-1.0.2	dssort	ka	ks	MSufSort-2.2	MSufSort-3.0beta	qsufsort
total	1218486297	1286.041	3138.420	5110.852	1072.228	1757.381	3856.365	8739.525	1015.662	1154.178	3518.526
ACT/Executable	4938680	1.054	4.487	4.713	1.401	1.197	8.348	15.979	2.109	1.505	3.942
ACT/Graphics	12466304	2.918	12.333	11.248	2.696	3.486	15.720	24.373	4.808	3.021	10.071
ACT/Sound	8702392	3.937	15.098	16.630	5.333	5.021	36.996	57.829	5.410	4.581	8.899
ACT/Text	4920286	1.548	3.200	6.038	1.875	1.738	8.917	17.627	2.224	1.984	6.106
Artificial Corpus	300001	0.286	0.118	0.230	0.054	0.496	0.147	0.142	0.116	0.084	0.105
Calgary Corpus	3141622	0.551	2.731	2.235	0.713	0.640	3.259	4.635	1.126	0.844	1.915
Canterbury Corpus	2810784	0.475	2.071	1.883	0.544	0.666	2.502	3.364	0.913	0.688	1.569
Large Can. Corpus	11159482	4.978	9.010	16.817	5.028	5.152	21.376	50.909	6.666	6.479	14.281
Max. Comp. Testfiles	53134726	31.146	75.123	142.003	25.489	44.443	106.010	212.898	31.626	36.142	82.017
Manzini's Corpus	896819039	1082.065	2385.806	4237.875	865.685	1515.145	3054.700	6984.267	801.414	935.080	2919.138
Misc. Corpus	1000000	0.289	0.891	0.904	0.420	0.308	1.412	2.093	0.428	0.363	0.721
Protein Corpus	7154401	2.567	9.884	8.616	4.062	2.736	16.715	33.304	3.720	3.596	7.239
Silesia Corpus	211938580	154.227	617.668	661.660	158.928	176.353	580.263	1332.105	155.102	159.811	462.523

Timing measurements were made on a 1.8 GHz PowerPC G5 processor, with 1GB main memory running Darwin 8.8.0.
Programs were compiled with gcc/g++ version 4.1.1, with optimization options '-O3 -fomit-frame-pointer'.
Running times are the average of five runs. Times were measured using standard Unix 'time' command. (user + system)

Corpora:

Programs:

archon3r3 by Dima Malyshev.
bpr by Klaus-Bernd Schürmann and Jens Stoye.
dc32 (.tar.gz) by Stefan Burkhardt and Juha Kärkkäinen.
divsufsort-1.0.2 by Yuta Mori.
dssort by Giovanni Manzini and Paolo Ferragina.
ka by Pang Ko.
ks by Juha Kärkkäinen and Peter Sanders.
MSufSort-2.2 by Michael Maniscalco.
MSufSort-3.0beta by Michael Maniscalco and Simon J. Puglisi.
qsufsort by Jesper Larsson and Kunihiko Sadakane.

ChangeLog:

2007-01-09: Added MSufSort-3.0beta.
2006-05-14: Replaced Archon with a new version (archon3r3).
2006-05-06: Added archon3r1.; Upgraded gcc to version 4.1.0.; Upgraded Darwin to version 8.6.0.
2006-01-01: Added divsufsort-1.0.2.; Upgraded gcc to version 4.0.2.; Changed the optimization option.
2005-12-02: Replaced Archon with a new version.
2005-11-30: Added Archon2-pro.
2005-11-08: Added MSufSort-2.1 and MSufSort-2.2.; Added divsufsort-1.0.0 and divsufsort-1.0.1.

white page

[results]

Benchmark results of suffix sorting algorithms