Suffix Array Construction Benchmark

Last updated: 2008-03-02

Timing results on PowerPC G5:

ACT-Executable
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	4938680	1.158	4.616	4.731	1.346	1.428	5.670	16.207	1.670	3.978
101.EXE	438144	0.085	0.697	0.295	0.104	0.093	0.409	0.704	0.197	0.213
netscape.exe	2934336	0.737	2.613	3.039	0.875	0.933	3.754	11.306	0.990	2.550
pine.bin	1566200	0.336	1.307	1.397	0.367	0.401	1.506	4.196	0.484	1.215

ACT-Graphics
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	12466304	3.506	12.614	11.241	3.697	2.507	11.000	24.511	3.434	10.184
clegg.tif	2149096	1.503	2.113	2.051	1.258	0.655	2.371	5.683	0.748	3.558
frymire.tif	3706306	0.708	1.530	4.058	0.688	0.540	2.306	6.792	0.732	3.168
lena.tif	786568	0.135	1.321	0.539	0.212	0.156	0.943	1.444	0.245	0.358
monarch.tif	1179784	0.215	1.572	0.901	0.307	0.241	1.071	2.052	0.346	0.628
peppers.tif	786568	0.122	1.241	0.509	0.190	0.131	0.886	1.383	0.253	0.332
sail.tif	1179784	0.249	1.685	1.055	0.345	0.304	1.484	2.874	0.400	0.720
serrano.tif	1498414	0.340	1.367	1.210	0.359	0.206	0.647	1.601	0.327	0.774
tulips.tif	1179784	0.235	1.786	0.918	0.340	0.274	1.291	2.682	0.384	0.648

ACT-Sound
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	8702392	4.293	15.427	16.561	5.148	5.118	26.133	58.116	4.249	8.806
every.wav	6994092	3.794	13.420	14.952	4.679	4.338	23.749	53.885	3.656	7.548
mike.wav	1708300	0.499	2.007	1.609	0.468	0.780	2.384	4.231	0.593	1.258

ACT-Text
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	4920286	1.639	3.273	5.990	1.867	1.860	5.978	17.842	1.766	6.007
1musk10.txt	1344739	0.416	0.759	1.429	0.460	0.501	1.476	4.012	0.451	1.467
anne11.txt	586969	0.129	0.252	0.422	0.143	0.160	0.468	1.184	0.164	0.449
world95.txt	2988578	1.094	2.261	4.140	1.264	1.200	4.034	12.647	1.150	4.091

Artificial Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	300001	0.068	0.138	0.237	0.518	0.063	0.497	0.154	0.122	0.140
a.txt	1	0.012	0.011	0.017	0.013	0.010	0.017	0.010	0.025	0.010
aaa.txt	100000	0.018	0.018	0.075	0.020	0.015	0.395	0.039	0.027	0.038
alphabet.txt	100000	0.016	0.053	0.088	0.462	0.017	0.023	0.048	0.030	0.064
random.txt	100000	0.021	0.057	0.056	0.024	0.021	0.062	0.057	0.040	0.028

Calgary Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	3141622	0.686	2.875	2.282	0.761	0.762	2.365	4.744	1.013	1.968
bib	111261	0.025	0.052	0.066	0.028	0.024	0.063	0.072	0.040	0.040
book1	768771	0.189	0.348	0.646	0.217	0.246	0.728	1.725	0.228	0.616
book2	610856	0.134	0.267	0.448	0.146	0.163	0.489	1.293	0.176	0.450
geo	102400	0.023	0.520	0.058	0.025	0.024	0.065	0.060	0.056	0.036
news	377109	0.069	0.166	0.220	0.077	0.073	0.289	0.640	0.099	0.236
obj1	21504	0.014	0.462	0.023	0.015	0.014	0.030	0.018	0.033	0.014
obj2	246814	0.051	0.551	0.146	0.055	0.045	0.164	0.268	0.088	0.127
paper1	53161	0.018	0.045	0.037	0.020	0.018	0.043	0.030	0.032	0.021
paper2	82199	0.021	0.049	0.050	0.024	0.022	0.046	0.052	0.036	0.029
pic	513216	0.058	0.230	0.406	0.062	0.059	0.257	0.425	0.087	0.294
progc	39611	0.016	0.040	0.031	0.018	0.016	0.037	0.027	0.030	0.018
progl	71646	0.021	0.044	0.048	0.023	0.019	0.047	0.044	0.036	0.028
progp	49379	0.019	0.042	0.037	0.020	0.017	0.042	0.030	0.035	0.022
trans	93695	0.027	0.060	0.066	0.029	0.023	0.068	0.061	0.039	0.037

Canterbury Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	2810784	0.580	2.175	1.904	0.773	0.567	1.616	3.451	0.851	1.634
alice29.txt	152089	0.030	0.061	0.083	0.035	0.030	0.074	0.135	0.054	0.067
asyoulik.txt	125179	0.029	0.052	0.069	0.036	0.030	0.064	0.092	0.042	0.052
cp.html	24603	0.015	0.033	0.025	0.017	0.015	0.025	0.019	0.028	0.015
fields.c	11150	0.014	0.032	0.019	0.015	0.013	0.021	0.014	0.025	0.013
grammar.lsp	3721	0.013	0.023	0.016	0.014	0.012	0.017	0.012	0.024	0.011
kennedy.xls	1029744	0.217	0.908	0.685	0.369	0.176	0.458	0.983	0.292	0.498
lcet10.txt	426754	0.078	0.170	0.252	0.084	0.089	0.279	0.748	0.112	0.293
plrabn12.txt	481861	0.095	0.203	0.304	0.105	0.117	0.362	0.982	0.129	0.364
ptt5	513216	0.053	0.223	0.400	0.064	0.049	0.251	0.427	0.081	0.287
sum	38240	0.023	0.448	0.035	0.019	0.023	0.047	0.028	0.039	0.023
xargs.1	4227	0.013	0.022	0.016	0.014	0.013	0.017	0.012	0.025	0.011

Large Canterbury Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	11159482	5.198	9.113	16.392	5.453	5.158	16.158	51.371	5.340	14.213
bible.txt	4047392	1.712	3.804	5.907	1.944	1.822	5.971	18.990	1.818	5.873
E.coli	4638690	2.643	3.561	7.202	2.532	2.398	7.088	22.857	2.624	5.149
world192.txt	2473400	0.843	1.748	3.282	0.976	0.938	3.098	9.525	0.899	3.191

Manzini's Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	896819039	1244.484	3026.693	4273.981	1540.585	782.664	2384.167	7294.444	729.719	2917.944
chr22.dna	34553758	40.199	47.345	119.141	37.960	32.681	84.650	253.095	28.359	55.465
etext99	105277340	147.580	322.899	452.482	171.767	113.106	387.010	986.515	94.068	366.546
gcc-3.0.tar	86630400	77.388	161.448	280.892	123.150	52.006	180.727	621.236	59.096	212.918
howto	39422105	33.984	61.006	117.336	38.886	28.165	101.138	310.708	24.883	89.790
jdk13c	69728899	145.330	204.132	420.566	193.833	58.739	146.402	479.262	60.308	242.391
linux-2.4.5.tar	116254720	105.092	410.134	384.984	116.262	74.979	272.027	955.020	72.865	281.623
rctail96	114711151	253.344	592.453	841.794	328.589	131.812	330.573	975.582	123.231	459.307
rfc	116421901	121.796	408.672	480.268	139.242	93.955	312.167	997.881	84.038	361.024
sprot34.dat	109617186	154.031	436.022	611.400	175.010	115.307	342.350	943.991	100.680	369.799
w3c2	104201579	165.739	382.582	565.117	215.887	81.913	227.122	771.154	82.191	479.082

Maximum Compression Testfiles
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	53134726	33.098	78.928	143.646	46.523	25.209	72.457	215.716	25.861	82.271
A10.jpg	842468	0.207	1.806	0.785	0.288	0.265	1.136	2.536	0.389	0.508
acrord32.exe	3870784	0.912	3.582	3.999	1.066	1.135	4.956	14.592	1.232	3.140
english.dic	4067439	1.155	1.959	3.498	6.790	1.001	3.637	10.690	1.085	2.526
FlashMX.pdf	4526946	1.788	7.560	6.679	2.325	2.069	10.247	27.569	2.154	4.451
fp.log	20617071	21.995	47.289	103.340	23.512	14.550	31.114	96.152	14.237	48.973
mso97.dll	3782416	1.065	4.377	4.345	1.302	1.372	6.270	17.320	1.360	3.551
ohs.doc	4168192	2.892	5.327	9.213	7.699	1.672	4.788	14.300	2.091	8.383
rafale.bmp	4149414	0.890	1.930	3.323	0.984	0.964	2.910	7.884	1.021	2.620
vcfiu.hlp	4121418	1.104	2.787	4.342	1.299	0.983	3.393	12.083	1.132	4.090
world95.txt	2988578	1.090	2.310	4.121	1.257	1.198	4.007	12.590	1.161	4.029

Miscellaneous Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	1000000	0.316	0.908	0.881	0.335	0.421	1.024	2.078	0.339	0.713
pi.txt	1000000	0.316	0.908	0.881	0.335	0.421	1.024	2.078	0.339	0.713

Protein Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	7154401	2.806	9.968	8.445	2.914	4.090	12.570	33.457	3.085	7.211
hi	509519	0.101	0.604	0.307	0.108	0.129	0.471	1.109	0.130	0.272
hs	3295751	1.387	4.645	4.241	1.449	2.085	6.355	17.232	1.516	3.568
mj	448779	0.084	0.511	0.253	0.091	0.105	0.385	0.880	0.115	0.234
sc	2900352	1.234	4.209	3.644	1.266	1.771	5.360	14.236	1.323	3.137

Silesia Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	211938580	166.572	624.345	666.309	181.118	141.888	444.314	1344.418	130.561	464.288
dickens	10192446	7.515	14.324	24.055	8.512	7.070	23.940	71.035	6.193	19.311
mozilla	51220480	25.850	67.316	128.933	32.846	28.251	114.804	348.177	24.475	91.517
mr	9970564	6.845	11.328	22.394	5.651	6.366	17.213	52.505	6.703	21.460
nci	33553445	46.642	310.020	180.455	46.946	25.215	45.599	197.026	29.414	117.007
ooffice	6152192	2.137	6.890	8.955	2.637	2.649	10.377	33.876	2.330	7.261
osdb	10085684	6.953	18.007	27.156	8.002	8.079	28.020	65.049	5.800	20.327
reymont	6627202	3.936	11.541	14.025	4.040	4.043	11.583	35.087	3.912	13.424
samba	21606400	12.081	21.314	44.459	12.969	9.279	34.305	118.594	9.733	41.100
sao	7251944	3.731	11.992	15.038	4.734	4.738	19.822	37.063	3.955	10.104
webster	41458703	44.259	136.974	178.149	47.336	37.904	112.309	324.042	31.217	103.933
x-ray	8474240	4.258	10.788	14.429	4.810	6.600	21.268	43.758	4.862	10.555
xml	5345280	2.364	3.851	8.261	2.634	1.698	5.074	18.207	1.969	8.289

Testfiles
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	4194304	11.059	100.097	17.184	21.558	1.982	3.251	6.742	7.392	13.726
test4	2097152	7.445	3.379	12.885	19.044	1.459	2.340	5.162	2.955	10.118
test5	2097152	3.614	96.719	4.298	2.514	0.522	0.911	1.580	4.437	3.607

The Gauntlet
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	67050103	207.191	846.655	362.902	1122.974	87.423	90.091	279.608	92.113	671.603
abac	200000	0.037	0.087	0.152	36.358	0.034	0.055	0.081	0.062	0.100
abba	10500600	18.226	31.245	67.030	61.643	10.460	10.203	45.868	12.565	120.154
book1x20	15375420	24.419	28.920	78.626	177.379	13.355	37.714	91.901	12.714	185.156
fib_s14930352	14930352	72.971	85.010	97.696	376.887	31.996	15.893	62.467	31.704	171.914
fss10	12078908	63.544	64.222	75.654	222.556	24.049	15.967	49.689	21.095	135.464
fss9	2851443	6.895	9.443	10.569	24.392	2.488	2.299	7.831	3.109	21.561
houston	3840000	0.923	2.362	5.226	159.329	0.332	1.098	3.126	0.692	4.215
paper5x80	981924	0.485	0.605	1.512	1.487	0.306	0.822	2.101	0.359	3.546
test1	2097152	5.700	13.876	10.883	28.353	2.420	1.834	5.695	1.721	9.609
test2	2097152	12.299	3.264	10.835	28.221	1.133	1.825	5.703	5.790	9.612
test3	2097152	1.693	607.620	4.719	6.368	0.852	2.381	5.147	2.302	10.272

totals
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

Back to main page

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