Suffix Array Construction Benchmark

Last updated: 2008-03-02

Timing results on Pentium M:

ACT-Executable
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	4938680	0.817	3.014	4.194	1.027	1.125	5.007	12.610	1.360	3.231
101.EXE	438144	0.114	0.541	0.340	0.142	0.120	0.362	0.547	0.170	0.214
netscape.exe	2934336	0.477	1.550	2.630	0.587	0.693	3.261	8.568	0.789	1.947
pine.bin	1566200	0.226	0.923	1.224	0.298	0.312	1.384	3.495	0.401	1.070

ACT-Graphics
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	12466304	2.388	7.429	10.215	2.954	1.969	9.293	17.483	2.902	7.246
clegg.tif	2149096	1.042	1.142	1.821	0.989	0.545	2.161	3.851	0.645	2.239
frymire.tif	3706306	0.481	1.146	3.761	0.573	0.415	1.999	5.276	0.617	2.223
lena.tif	786568	0.094	0.773	0.505	0.162	0.118	0.725	0.935	0.212	0.278
monarch.tif	1179784	0.146	0.865	0.783	0.230	0.172	0.899	1.360	0.308	0.469
peppers.tif	786568	0.090	0.735	0.495	0.148	0.116	0.697	0.867	0.198	0.260
sail.tif	1179784	0.144	0.901	0.831	0.238	0.214	1.068	2.057	0.298	0.557
serrano.tif	1498414	0.252	0.953	1.236	0.375	0.200	0.699	1.442	0.314	0.753
tulips.tif	1179784	0.138	0.913	0.783	0.238	0.188	1.046	1.694	0.309	0.467

ACT-Sound
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	8702392	1.925	6.171	9.798	2.542	2.904	17.587	31.147	2.808	5.222
every.wav	6994092	1.632	5.065	8.500	2.209	2.367	15.743	28.519	2.345	4.326
mike.wav	1708300	0.292	1.106	1.298	0.332	0.537	1.845	2.628	0.463	0.895

ACT-Text
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	4920286	1.017	1.957	4.855	1.346	1.324	5.051	11.867	1.398	4.096
1musk10.txt	1344739	0.248	0.523	1.126	0.331	0.351	1.274	3.016	0.355	1.074
anne11.txt	586969	0.088	0.214	0.388	0.126	0.118	0.365	0.829	0.140	0.385
world95.txt	2988578	0.681	1.220	3.341	0.889	0.855	3.413	8.021	0.903	2.638

Artificial Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	300001	0.136	0.166	0.316	0.761	0.122	0.561	0.210	0.180	0.196
a.txt	1	0.026	0.024	0.030	0.026	0.024	0.030	0.024	0.034	0.024
aaa.txt	100000	0.030	0.030	0.098	0.030	0.026	0.411	0.072	0.040	0.072
alphabet.txt	100000	0.036	0.056	0.108	0.663	0.030	0.042	0.060	0.042	0.058
random.txt	100000	0.044	0.056	0.080	0.042	0.042	0.078	0.054	0.064	0.042

Calgary Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	3141622	0.831	2.356	2.474	0.943	0.871	2.177	3.503	1.074	1.827
bib	111261	0.052	0.074	0.094	0.048	0.044	0.092	0.070	0.064	0.050
book1	768771	0.148	0.274	0.521	0.200	0.184	0.543	1.264	0.182	0.525
book2	610856	0.098	0.222	0.401	0.130	0.120	0.395	0.881	0.158	0.393
geo	102400	0.036	0.387	0.082	0.036	0.036	0.078	0.060	0.054	0.046
news	377109	0.078	0.144	0.250	0.092	0.080	0.246	0.383	0.096	0.186
obj1	21504	0.026	0.343	0.040	0.028	0.026	0.044	0.030	0.040	0.030
obj2	246814	0.050	0.405	0.174	0.060	0.052	0.160	0.174	0.082	0.096
paper1	53161	0.034	0.050	0.058	0.036	0.034	0.058	0.042	0.042	0.034
paper2	82199	0.036	0.054	0.072	0.044	0.038	0.066	0.056	0.066	0.042
pic	513216	0.070	0.188	0.513	0.074	0.070	0.240	0.332	0.098	0.266
progc	39611	0.040	0.046	0.050	0.038	0.042	0.052	0.038	0.040	0.032
progl	71646	0.046	0.052	0.080	0.046	0.046	0.068	0.052	0.046	0.040
progp	49379	0.046	0.048	0.056	0.044	0.060	0.054	0.044	0.046	0.036
trans	93695	0.070	0.068	0.082	0.066	0.038	0.080	0.076	0.058	0.050

Canterbury Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	2810784	0.719	1.775	2.203	1.050	0.671	1.714	2.796	0.923	1.749
alice29.txt	152089	0.064	0.062	0.112	0.072	0.042	0.092	0.086	0.056	0.068
asyoulik.txt	125179	0.066	0.056	0.094	0.068	0.048	0.082	0.074	0.052	0.062
cp.html	24603	0.044	0.040	0.042	0.040	0.046	0.040	0.032	0.038	0.034
fields.c	11150	0.044	0.042	0.036	0.050	0.026	0.038	0.028	0.038	0.032
grammar.lsp	3721	0.042	0.036	0.036	0.042	0.026	0.034	0.028	0.040	0.030
kennedy.xls	1029744	0.190	0.657	0.697	0.461	0.192	0.565	1.090	0.320	0.675
lcet10.txt	426754	0.066	0.152	0.280	0.092	0.080	0.242	0.465	0.108	0.242
plrabn12.txt	481861	0.072	0.172	0.323	0.108	0.094	0.292	0.621	0.114	0.300
ptt5	513216	0.060	0.188	0.501	0.060	0.056	0.244	0.310	0.080	0.246
sum	38240	0.038	0.337	0.048	0.030	0.030	0.052	0.038	0.040	0.034
xargs.1	4227	0.032	0.032	0.034	0.026	0.030	0.032	0.024	0.036	0.024

Large Canterbury Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	11159482	3.057	4.246	12.804	3.711	3.637	13.223	31.201	3.749	8.748
bible.txt	4047392	1.058	1.777	4.731	1.362	1.354	4.907	11.482	1.332	3.401
E.coli	4638690	1.474	1.486	5.426	1.660	1.606	5.732	13.431	1.724	3.223
world192.txt	2473400	0.525	0.983	2.648	0.689	0.677	2.584	6.287	0.693	2.125

Manzini's Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	896819039	437.123	5891.914	1699.748	697.401	342.194	1467.454	8620.099	342.252	1825.437
chr22.dna	34553758	13.443	14.853	53.725	15.617	14.569	50.479	112.620	14.395	28.507
etext99	105277340	48.548	614.383	176.744	69.300	47.344	209.215	1050.833	47.615	149.289
gcc-3.0.tar	86630400	33.116	54.476	143.915	77.155	27.075	115.714	410.422	31.295	107.973
howto	39422105	13.566	20.518	57.216	17.605	13.880	59.415	139.625	12.522	42.135
jdk13c	69728899	41.858	60.982	150.374	72.420	25.721	98.408	222.913	25.445	111.693
linux-2.4.5.tar	116254720	42.842	1410.915	188.928	56.387	37.798	181.998	1803.159	41.868	379.245
rctail96	114711151	79.805	1093.112	292.464	135.479	50.823	212.646	1284.914	46.016	195.016
rfc	116421901	46.631	1027.688	205.732	62.324	41.510	191.031	1490.547	38.868	456.484
sprot34.dat	109617186	50.863	760.289	214.941	68.038	45.902	191.810	1265.672	46.911	148.772
w3c2	104201579	66.452	834.698	215.708	123.077	37.572	156.739	839.395	37.318	206.323

Maximum Compression Testfiles
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	53134726	16.504	32.517	79.176	26.302	14.683	60.753	135.327	15.620	48.067
A10.jpg	842468	0.134	1.254	0.609	0.226	0.172	1.079	2.325	0.242	0.489
acrord32.exe	3870784	0.581	1.695	3.447	0.729	0.797	4.102	10.024	0.935	2.229
english.dic	4067439	0.707	1.308	3.317	3.980	0.791	3.143	7.473	0.863	2.077
FlashMX.pdf	4526946	0.919	2.792	4.629	1.294	1.278	7.481	15.815	1.512	2.676
fp.log	20617071	9.886	17.285	47.865	12.418	7.433	27.019	55.416	7.114	25.116
mso97.dll	3782416	0.629	1.891	3.511	0.815	0.903	4.833	10.854	0.993	2.297
ohs.doc	4168192	1.707	2.151	5.500	3.960	1.045	4.124	9.866	1.326	5.578
rafale.bmp	4149414	0.523	1.342	3.143	0.829	0.683	2.502	6.071	0.843	1.979
vcfiu.hlp	4121418	0.763	1.628	3.930	1.182	0.773	3.259	9.396	0.961	3.243
world95.txt	2988578	0.655	1.172	3.227	0.869	0.807	3.213	8.088	0.829	2.383

Miscellaneous Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	1000000	0.162	0.577	0.685	0.246	0.268	0.799	1.532	0.260	0.541
pi.txt	1000000	0.162	0.577	0.685	0.246	0.268	0.799	1.532	0.260	0.541

Protein Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	7154401	1.486	4.464	6.642	1.965	2.422	9.087	19.712	2.051	4.312
hi	509519	0.082	0.326	0.316	0.108	0.106	0.346	0.721	0.118	0.228
hs	3295751	0.705	2.025	3.225	0.931	1.200	4.547	9.938	0.953	2.059
mj	448779	0.070	0.294	0.282	0.100	0.092	0.288	0.569	0.106	0.184
sc	2900352	0.629	1.819	2.818	0.825	1.023	3.906	8.484	0.873	1.841

Silesia Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	211938580	68.140	381.357	323.212	89.472	68.657	281.136	651.020	69.628	219.511
dickens	10192446	2.942	4.673	12.738	3.956	3.669	15.174	34.209	3.499	8.482
mozilla	51220480	11.511	26.590	69.910	16.536	14.575	73.339	171.963	14.817	48.930
mr	9970564	2.790	4.290	12.850	2.852	3.399	11.216	27.682	3.561	8.891
nci	33553445	20.091	274.118	78.315	25.981	11.418	28.739	89.060	12.340	52.684
ooffice	6152192	1.150	2.880	6.371	1.514	1.568	7.813	19.430	1.628	4.244
osdb	10085684	2.588	5.786	13.305	3.227	3.467	15.514	29.470	3.133	8.829
reymont	6627202	1.742	3.407	8.192	2.155	2.227	8.160	18.893	2.303	6.479
samba	21606400	6.133	9.494	28.443	7.961	5.660	25.330	66.253	7.603	22.348
sao	7251944	1.586	4.152	8.288	2.177	2.417	12.808	18.340	2.430	4.889
webster	41458703	14.671	39.208	70.317	18.927	16.392	65.045	142.068	14.218	42.749
x-ray	8474240	1.410	4.557	8.015	2.057	2.626	13.179	20.209	2.588	5.316
xml	5345280	1.526	2.201	6.467	2.129	1.238	4.817	13.441	1.508	5.670

Testfiles
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	4194304	26.712	119.181	12.953	23.051	1.450	3.010	7.865	80.047	18.232
test4	2097152	17.299	2.273	7.583	13.569	0.817	2.027	5.001	72.879	9.341
test5	2097152	9.414	116.908	5.370	9.482	0.633	0.983	2.864	7.168	8.891

The Gauntlet
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	67050103	114.797	834.494	193.983	1139.963	37.222	63.072	143.679	52.306	258.575
abac	200000	0.092	0.120	0.180	47.138	0.048	0.082	0.100	0.072	0.108
abba	10500600	8.797	13.744	32.763	60.773	5.518	7.899	23.400	7.523	43.897
book1x20	15375420	11.743	8.881	35.279	190.115	6.301	23.019	41.327	7.505	66.578
fib_s14930352	14930352	38.920	28.751	48.912	362.281	11.348	10.187	30.109	14.219	60.385
fss10	12078908	35.044	24.467	41.341	178.294	8.903	11.000	24.812	9.652	47.140
fss9	2851443	3.745	4.040	7.829	13.297	1.618	2.227	5.065	1.450	9.536
houston	3840000	0.823	2.133	5.812	226.920	0.324	1.312	2.494	0.767	3.990
paper5x80	981924	0.246	0.505	1.024	1.620	0.204	0.729	1.510	0.318	2.478
test1	2097152	3.219	6.161	6.621	23.115	1.296	2.289	4.939	2.540	7.457
test2	2097152	6.786	1.764	6.635	23.141	0.637	2.277	4.941	5.953	7.577
test3	2097152	5.382	743.928	7.585	13.267	1.024	2.051	4.981	2.307	9.431

totals
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

Back to main page

This page is maintained by Yuta Mori <yiv01157 at nifty dot com>, Copyright © 2005-2008.