Suffix Array Construction Benchmark

Last updated: 2008-03-02

Timing results on Core 2 Duo:

ACT-Executable
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	4938680	0.306	1.072	2.059	0.456	0.397	1.422	3.187	0.594	1.003
101.EXE	438144	0.044	0.194	0.206	0.062	0.050	0.150	0.144	0.084	0.075
netscape.exe	2934336	0.169	0.547	1.219	0.250	0.228	0.834	2.306	0.322	0.628
pine.bin	1566200	0.094	0.331	0.634	0.144	0.119	0.437	0.738	0.188	0.300

ACT-Graphics
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	12466304	1.144	2.747	5.184	1.388	0.822	2.965	4.459	1.356	2.422
clegg.tif	2149096	0.475	0.431	0.884	0.459	0.200	0.662	0.959	0.278	0.700
frymire.tif	3706306	0.200	0.469	1.759	0.269	0.156	0.631	1.372	0.312	0.781
lena.tif	786568	0.050	0.259	0.291	0.078	0.056	0.256	0.269	0.097	0.097
monarch.tif	1179784	0.066	0.294	0.425	0.103	0.078	0.278	0.362	0.131	0.156
peppers.tif	786568	0.047	0.247	0.291	0.069	0.056	0.253	0.259	0.097	0.097
sail.tif	1179784	0.075	0.291	0.428	0.109	0.109	0.341	0.444	0.131	0.166
serrano.tif	1498414	0.156	0.453	0.678	0.197	0.088	0.237	0.369	0.156	0.275
tulips.tif	1179784	0.075	0.303	0.428	0.103	0.078	0.306	0.425	0.153	0.150

ACT-Sound
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	8702392	0.916	2.319	4.428	0.934	0.937	4.956	12.275	1.297	1.872
every.wav	6994092	0.791	1.919	3.800	0.766	0.772	4.553	11.569	1.097	1.578
mike.wav	1708300	0.125	0.400	0.628	0.169	0.166	0.403	0.706	0.200	0.294

ACT-Text
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	4920286	0.369	0.756	2.050	0.594	0.450	1.266	3.175	0.619	1.241
1musk10.txt	1344739	0.094	0.197	0.503	0.156	0.119	0.294	0.641	0.138	0.313
anne11.txt	586969	0.053	0.087	0.222	0.075	0.062	0.122	0.169	0.072	0.106
world95.txt	2988578	0.222	0.472	1.325	0.363	0.269	0.850	2.366	0.409	0.822

Artificial Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	300001	0.084	0.106	0.200	0.425	0.084	0.234	0.119	0.109	0.112
a.txt	1	0.019	0.022	0.022	0.019	0.016	0.025	0.019	0.025	0.019
aaa.txt	100000	0.025	0.025	0.062	0.025	0.022	0.147	0.034	0.025	0.031
alphabet.txt	100000	0.019	0.034	0.066	0.356	0.022	0.025	0.034	0.025	0.034
random.txt	100000	0.022	0.025	0.050	0.025	0.025	0.037	0.031	0.034	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.409	0.997	1.438	0.503	0.453	0.900	1.022	0.566	0.722
bib	111261	0.028	0.031	0.059	0.031	0.028	0.044	0.041	0.034	0.034
book1	768771	0.059	0.109	0.284	0.094	0.075	0.156	0.244	0.084	0.141
book2	610856	0.050	0.091	0.231	0.078	0.062	0.131	0.191	0.078	0.109
geo	102400	0.022	0.150	0.053	0.022	0.025	0.044	0.038	0.031	0.031
news	377109	0.041	0.066	0.156	0.053	0.041	0.103	0.116	0.053	0.069
obj1	21504	0.019	0.138	0.025	0.019	0.019	0.025	0.022	0.025	0.019
obj2	246814	0.028	0.159	0.128	0.034	0.038	0.072	0.078	0.047	0.053
paper1	53161	0.019	0.028	0.034	0.022	0.022	0.031	0.028	0.028	0.025
paper2	82199	0.022	0.031	0.044	0.022	0.022	0.034	0.034	0.031	0.028
pic	513216	0.034	0.078	0.259	0.037	0.034	0.128	0.112	0.044	0.106
progc	39611	0.019	0.025	0.031	0.022	0.019	0.031	0.025	0.025	0.022
progl	71646	0.022	0.028	0.044	0.022	0.022	0.034	0.031	0.028	0.028
progp	49379	0.022	0.028	0.038	0.022	0.022	0.028	0.025	0.028	0.025
trans	93695	0.025	0.034	0.050	0.025	0.025	0.037	0.038	0.028	0.031

Canterbury Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	2810784	0.337	0.759	1.222	0.516	0.350	0.672	0.781	0.503	0.587
alice29.txt	152089	0.028	0.038	0.072	0.034	0.031	0.047	0.050	0.050	0.038
asyoulik.txt	125179	0.022	0.031	0.059	0.028	0.025	0.044	0.044	0.031	0.034
cp.html	24603	0.019	0.025	0.028	0.019	0.022	0.025	0.022	0.022	0.022
fields.c	11150	0.022	0.025	0.025	0.022	0.016	0.025	0.022	0.028	0.019
grammar.lsp	3721	0.016	0.022	0.022	0.019	0.019	0.022	0.019	0.022	0.016
kennedy.xls	1029744	0.072	0.247	0.338	0.194	0.072	0.156	0.203	0.134	0.153
lcet10.txt	426754	0.037	0.062	0.163	0.053	0.044	0.091	0.119	0.059	0.075
plrabn12.txt	481861	0.047	0.072	0.184	0.069	0.050	0.106	0.147	0.059	0.088
ptt5	513216	0.034	0.075	0.281	0.038	0.034	0.100	0.112	0.044	0.103
sum	38240	0.022	0.141	0.031	0.022	0.022	0.037	0.025	0.031	0.022
xargs.1	4227	0.019	0.022	0.019	0.019	0.016	0.019	0.019	0.022	0.019

Large Canterbury Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	11159482	0.981	1.638	4.947	1.419	1.175	3.319	10.372	1.565	2.953
bible.txt	4047392	0.334	0.688	1.816	0.509	0.416	1.250	3.987	0.550	1.206
E.coli	4638690	0.475	0.572	2.084	0.625	0.547	1.416	4.644	0.722	1.091
world192.txt	2473400	0.172	0.378	1.047	0.284	0.212	0.653	1.741	0.294	0.656

Manzini's Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	896819039	186.047	278.297	769.319	323.347	132.866	501.503	1501.054	158.944	465.809
chr22.dna	34553758	5.994	6.397	23.916	7.572	5.506	17.028	50.641	7.137	10.194
etext99	105277340	21.881	33.116	84.525	34.272	19.047	74.222	203.966	23.925	54.247
gcc-3.0.tar	86630400	13.834	21.197	65.278	35.706	10.581	40.569	137.113	14.856	39.241
howto	39422105	5.763	8.547	26.856	8.384	5.541	20.719	65.675	5.556	15.806
jdk13c	69728899	17.978	22.684	64.825	32.194	9.466	33.800	103.222	10.841	38.166
linux-2.4.5.tar	116254720	18.056	26.791	87.213	26.131	14.941	58.328	196.188	19.781	52.066
rctail96	114711151	32.394	56.234	126.603	62.312	18.844	70.087	192.488	20.266	67.419
rfc	116421901	20.609	36.038	96.425	29.738	16.478	64.928	197.813	17.387	59.044
sprot34.dat	109617186	22.681	37.291	98.800	32.219	18.272	68.791	188.713	23.075	54.778
w3c2	104201579	26.856	30.003	94.878	54.819	14.191	53.031	165.237	16.119	74.850

Maximum Compression Testfiles
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	53134726	7.131	12.647	34.512	10.625	5.200	17.769	49.391	6.747	16.366
A10.jpg	842468	0.056	0.313	0.331	0.072	0.069	0.225	0.406	0.109	0.103
acrord32.exe	3870784	0.225	0.659	1.569	0.328	0.288	1.175	3.147	0.406	0.822
english.dic	4067439	0.278	0.459	1.541	0.994	0.319	0.913	2.656	0.375	0.737
FlashMX.pdf	4526946	0.334	1.100	2.053	0.434	0.394	2.022	5.809	0.634	0.956
fp.log	20617071	4.466	6.825	20.572	5.297	2.619	8.456	23.862	3.028	8.694
mso97.dll	3782416	0.234	0.744	1.541	0.353	0.312	1.353	3.663	0.444	0.844
ohs.doc	4168192	0.753	0.806	2.225	1.794	0.341	1.072	2.997	0.534	1.581
rafale.bmp	4149414	0.244	0.616	1.566	0.434	0.291	0.791	1.741	0.428	0.719
vcfiu.hlp	4121418	0.316	0.656	1.819	0.553	0.300	0.913	2.744	0.419	1.088
world95.txt	2988578	0.225	0.469	1.297	0.366	0.269	0.850	2.366	0.369	0.822

Miscellaneous Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	1000000	0.078	0.153	0.347	0.122	0.106	0.200	0.328	0.122	0.128
pi.txt	1000000	0.078	0.153	0.347	0.122	0.106	0.200	0.328	0.122	0.128

Protein Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	7154401	0.572	1.500	2.834	0.893	0.822	2.391	6.447	0.881	1.362
hi	509519	0.047	0.116	0.216	0.069	0.056	0.131	0.169	0.069	0.075
hs	3295751	0.259	0.678	1.306	0.406	0.391	1.159	3.375	0.387	0.656
mj	448779	0.038	0.097	0.163	0.059	0.047	0.109	0.134	0.056	0.062
sc	2900352	0.228	0.609	1.150	0.359	0.328	0.991	2.769	0.369	0.569

Silesia Corpus
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	211938580	28.694	133.393	144.306	40.713	25.544	92.891	283.378	31.556	79.781
dickens	10192446	1.209	2.003	5.934	1.859	1.419	4.713	14.741	1.675	3.300
mozilla	51220480	4.947	10.416	32.597	7.391	5.578	25.219	77.559	6.850	17.869
mr	9970564	1.125	1.775	5.859	1.325	1.225	3.369	10.412	1.603	3.303
nci	33553445	8.131	90.472	31.822	11.503	3.850	9.959	38.763	5.269	18.234
ooffice	6152192	0.456	1.147	2.866	0.675	0.569	2.247	7.294	0.731	1.600
osdb	10085684	1.169	2.478	6.312	1.569	1.331	5.147	12.741	1.544	3.331
reymont	6627202	0.672	1.391	3.594	0.941	0.806	2.316	7.366	1.056	2.331
samba	21606400	2.447	3.681	12.716	3.431	2.125	7.931	26.981	3.425	7.988
sao	7251944	0.653	1.706	3.831	0.878	0.859	3.913	7.750	1.122	1.903
webster	41458703	6.603	15.775	32.275	9.206	6.341	22.984	68.013	6.450	16.109
x-ray	8474240	0.684	1.703	3.800	1.009	0.997	3.772	7.594	1.188	1.975
xml	5345280	0.597	0.847	2.700	0.925	0.444	1.322	4.166	0.644	1.837

Testfiles
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	4194304	2.509	34.450	2.391	3.447	0.338	0.681	1.869	36.590	5.753
test4	2097152	1.594	0.816	1.303	2.103	0.150	0.412	1.116	33.353	3.069
test5	2097152	0.916	33.634	1.088	1.344	0.188	0.269	0.753	3.237	2.684

The Gauntlet
File	Size	Archon4r0	BPR	DC32	Deep-Shallow	divsufsort-1.2.3	KA	KS	MSufSort-3.1.1beta	qsufsort
totals	67050103	34.066	246.363	69.581	570.066	11.894	19.747	49.838	24.728	78.897
abac	200000	0.031	0.053	0.106	28.781	0.028	0.038	0.050	0.041	0.047
abba	10500600	3.281	5.109	11.334	30.641	1.722	2.513	8.278	3.487	14.269
book1x20	15375420	4.387	3.613	14.903	97.331	2.356	7.450	16.094	3.491	20.703
fib_s14930352	14930352	12.456	10.803	19.212	178.984	3.666	3.787	10.619	6.616	17.375
fss10	12078908	11.009	8.975	15.784	85.337	2.853	3.594	9.006	4.534	14.056
fss9	2851443	0.975	1.206	1.747	5.250	0.403	0.581	1.350	0.522	2.709
houston	3840000	0.350	0.725	2.313	123.241	0.116	0.484	0.847	0.269	1.184
paper5x80	981924	0.109	0.156	0.494	0.769	0.084	0.187	0.272	0.131	0.406
test1	2097152	0.334	2.131	1.213	8.916	0.266	0.341	1.103	1.306	2.547
test2	2097152	0.659	0.619	1.194	8.975	0.172	0.328	1.109	3.387	2.550
test3	2097152	0.472	212.972	1.281	1.841	0.228	0.444	1.109	0.944	3.050

totals
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

Back to main page

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