SMARTString Matching Algorithms Research Tool

by Simone Faro - www.dmi.unict.it/~faro/smart/ - email: faro@dmi.unict.it

Report of Experimental Results

Test Code EXP1712145140

Date 2024:04:03 15:13:58

Text rand8 (alphabet : 8 - size : 1048576 bytes)

	2	4	8	16	32	64	128	256	512	1024	2048	4096
TVSBS	0.18 3.47 2.71 - 9.47	0.19 2.70 2.04 - 8.10	0.18 1.91 1.52 - 5.41	0.18 1.43 1.14 - 3.69	0.18 1.20 0.92 - 2.99	0.18 1.04 0.82 - 2.71	0.18 0.95 0.72 - 2.46	0.25 1.26 0.71 - 2.34	0.27 1.37 0.71 - 2.36	0.21 1.08 0.71 - 2.86	0.25 1.27 0.72 - 2.46	0.18 0.94 0.71 - 2.67
FJS	0.01 3.89 2.97 - 10.09	0.01 2.98 2.14 - 8.53	0.01 2.33 1.59 - 5.54	0.01 2.07 1.30 - 7.24	0.01 1.86 1.02 - 5.69	0.01 1.87 1.02 - 7.48	0.01 1.85 0.98 - 5.39	0.02 2.05 1.03 - 6.16	0.02 1.90 0.97 - 5.12	0.03 2.40 0.92 - 7.33	0.03 1.99 1.05 - 5.42	0.05 2.04 1.00 - 6.48
HASH8	0.01 1.84 1.44 - 4.43	0.01 1.87 1.45 - 5.89	0.01 10.87 8.97 - 25.35	0.01 1.80 1.44 - 4.37	0.01 1.03 0.82 - 2.41	0.01 0.82 0.64 - 1.83	0.01 0.71 0.55 - 1.80	0.01 0.79 0.52 - 1.56	0.01 0.87 0.61 - 1.78	0.02 0.99 0.62 - 1.86	0.02 0.84 0.62 - 1.79	0.03 0.92 0.63 - 2.36
SO	0.01 1.76 1.19 - 3.80	0.01 1.64 1.20 - 4.68	0.01 1.70 1.18 - 5.48	0.01 1.68 1.20 - 5.93	0.01 1.78 1.21 - 5.52	0.01 1.39 1.07 - 4.15	0.01 1.39 1.09 - 3.14	0.01 1.40 1.07 - 3.52	0.01 1.56 1.08 - 4.77	0.02 1.65 1.08 - 4.37	0.01 1.48 1.08 - 3.26	0.01 1.49 1.08 - 3.92
SBNDM	0.02 2.68 1.91 - 6.96	0.02 1.35 1.05 - 3.64	0.02 1.04 0.80 - 3.03	0.02 0.90 0.68 - 2.46	0.02 0.82 0.61 - 2.21	0.02 0.81 0.64 - 1.85	0.02 0.82 0.62 - 2.18	0.02 0.86 0.63 - 1.94	0.02 1.10 0.63 - 2.28	0.02 1.01 0.63 - 2.26	0.02 0.82 0.63 - 2.09	0.02 0.90 0.64 - 2.29
LBNDM	0.01 3.40 1.85 - 9.67	0.01 2.85 1.18 - 6.72	0.01 1.84 1.15 - 6.14	0.01 1.12 0.77 - 2.73	0.01 0.92 0.66 - 6.59	0.01 0.78 0.60 - 1.83	0.01 0.81 0.55 - 2.50	0.02 0.98 0.57 - 2.17	0.02 1.84 0.80 - 4.99	0.02 7.07 2.40 - 16.17	0.02 5.71 3.52 - 13.03	0.02 5.35 3.38 - 13.49
SBNDM2	0.01 1.91 1.36 - 5.32	0.01 1.28 0.86 - 3.17	0.01 0.98 0.76 - 2.73	0.01 0.89 0.64 - 2.80	0.01 0.82 0.62 - 2.10	0.01 0.78 0.60 - 1.78	0.01 0.78 0.60 - 2.03	0.02 0.92 0.61 - 2.06	0.02 1.14 0.60 - 1.93	0.02 0.98 0.61 - 2.60	0.01 0.91 0.58 - 2.33	0.01 0.94 0.59 - 2.11
SBNDM-BMH	0.02 3.55 2.31 - 9.49	0.02 2.58 1.48 - 7.84	0.02 1.60 1.09 - 3.90	0.02 1.03 0.73 - 3.21	0.02 0.83 0.63 - 2.68	0.02 0.87 0.64 - 2.25	0.02 0.83 0.65 - 2.81	0.02 1.11 0.62 - 2.01	0.02 1.04 0.64 - 2.21	0.03 1.20 0.64 - 2.43	0.02 1.06 0.63 - 2.03	0.02 1.20 0.61 - 2.35
FNDM	0.01 3.44 1.89 - 8.21	0.01 2.70 1.60 - 7.40	0.01 1.76 1.31 - 4.78	0.01 1.18 0.86 - 2.80	0.01 0.93 0.70 - 3.20	0.01 0.91 0.69 - 2.49	0.01 0.90 0.68 - 2.35	0.02 1.22 0.70 - 2.49	0.01 1.02 0.68 - 2.29	0.02 1.21 0.70 - 2.46	0.01 0.98 0.68 - 2.73	0.01 1.01 0.71 - 2.68
FSBNDM	0.01 2.49 1.75 - 7.24	0.01 1.54 1.13 - 4.61	0.01 1.14 0.86 - 2.69	0.01 0.98 0.74 - 2.76	0.01 0.81 0.63 - 1.75	0.01 0.85 0.64 - 2.22	0.01 0.81 0.63 - 1.86	0.02 1.28 0.63 - 2.43	0.01 1.01 0.63 - 1.97	0.01 0.89 0.63 - 2.45	0.01 0.97 0.62 - 2.52	0.02 1.04 0.62 - 2.21
SBNDMQ8	0.01 1.82 1.47 - 4.43	0.01 1.85 1.44 - 6.06	0.01 4.33 3.11 - 10.95	0.01 1.00 0.76 - 2.88	0.01 0.72 0.55 - 1.65	0.01 0.80 0.56 - 2.20	0.01 0.72 0.56 - 1.87	0.02 1.03 0.56 - 2.08	0.02 0.94 0.55 - 1.87	0.01 0.81 0.55 - 2.35	0.01 0.79 0.55 - 2.15	0.01 0.80 0.54 - 2.27
UFNDMQ2	0.02 1.66 1.22 - 6.32	0.02 1.28 0.93 - 3.84	0.02 1.06 0.75 - 3.24	0.02 0.90 0.68 - 2.52	0.01 0.82 0.60 - 2.25	0.01 0.80 0.60 - 2.01	0.01 0.80 0.59 - 1.89	0.01 1.09 0.63 - 2.12	0.01 1.00 0.61 - 2.09	0.01 0.95 0.60 - 2.53	0.01 0.95 0.60 - 2.39	0.01 0.91 0.62 - 2.62
UFNDMQ8	0.01 1.83 1.43 - 5.43	0.01 1.87 1.44 - 5.07	0.02 1.11 0.80 - 4.24	0.02 0.85 0.63 - 2.80	0.01 0.75 0.56 - 2.64	0.01 0.81 0.57 - 2.44	0.01 0.75 0.56 - 2.24	0.01 0.91 0.58 - 1.60	0.01 0.87 0.56 - 2.59	0.01 0.90 0.56 - 2.28	0.01 0.90 0.55 - 2.28	0.01 0.85 0.56 - 2.15
KBNDM	0.01 3.09 2.38 - 8.26	0.01 1.80 1.43 - 4.82	0.01 1.28 1.02 - 3.44	0.01 1.04 0.81 - 3.44	0.01 0.89 0.72 - 2.61	0.01 0.78 0.59 - 2.11	0.01 0.70 0.53 - 1.81	0.02 0.89 0.52 - 1.83	0.02 0.80 0.53 - 1.90	0.02 0.74 0.53 - 2.11	0.02 0.86 0.53 - 1.87	0.02 0.88 0.52 - 2.25
FS-W2	0.04 3.03 2.28 - 8.18	0.04 1.95 1.35 - 6.30	0.04 1.43 1.06 - 4.52	0.04 1.22 0.83 - 3.53	0.04 1.10 0.76 - 2.80	0.04 1.08 0.74 - 2.85	0.04 1.13 0.72 - 2.57	0.06 1.57 0.72 - 3.08	0.05 1.07 0.68 - 3.67	0.06 1.08 0.63 - 2.63	0.10 1.38 0.67 - 2.56	0.11 1.12 0.68 - 2.87
LWFR5	0.01 1.88 1.44 - 4.83	0.01 1.82 1.43 - 4.34	0.06 2.53 1.79 - 6.76	0.06 0.81 0.59 - 1.98	0.06 0.69 0.53 - 1.98	0.06 0.66 0.50 - 1.53	0.07 0.75 0.57 - 1.96	0.11 1.12 0.49 - 1.63	0.08 0.67 0.47 - 1.82	0.11 0.84 0.47 - 1.63	0.11 0.69 0.48 - 2.01	0.18 0.79 0.51 - 2.18
QF43	0.01 1.88 1.43 - 4.53	0.01 1.90 1.43 - 4.89	0.02 0.94 0.72 - 2.57	0.02 0.72 0.55 - 1.90	0.02 0.64 0.49 - 1.53	0.02 0.60 0.46 - 1.50	0.02 0.69 0.46 - 1.47	0.02 0.77 0.44 - 1.46	0.02 0.69 0.42 - 2.59	0.03 0.71 0.41 - 1.44	0.02 0.57 0.41 - 1.41	0.03 0.59 0.41 - 1.59
SBNDM-W2	0.01 3.71 2.22 - 11.72	0.01 2.04 1.52 - 6.61	0.01 1.30 1.00 - 3.32	0.01 0.98 0.74 - 2.72	0.01 0.75 0.57 - 2.51	0.01 0.72 0.57 - 1.70	0.01 0.86 0.57 - 2.12	0.02 1.10 0.59 - 2.18	0.02 0.92 0.56 - 2.10	0.02 0.88 0.56 - 2.11	0.01 0.87 0.57 - 2.19	0.01 0.76 0.56 - 1.96
WFR2	0.06 2.99 1.98 - 7.98	0.06 1.58 1.08 - 5.22	0.06 1.27 0.86 - 3.39	0.06 1.08 0.80 - 2.78	0.06 0.87 0.66 - 2.58	0.06 0.73 0.54 - 2.04	0.08 0.92 0.52 - 2.13	0.08 0.92 0.53 - 1.89	0.07 0.71 0.48 - 1.46	0.09 0.73 0.45 - 1.88	0.11 0.75 0.46 - 1.82	0.14 0.74 0.47 - 1.71
TWFRQ2	0.06 2.28 1.44 - 5.95	0.06 1.45 1.02 - 3.36	0.06 1.22 0.87 - 3.73	0.06 1.10 0.80 - 3.36	0.06 0.89 0.68 - 2.35	0.06 0.71 0.55 - 2.01	0.07 0.80 0.51 - 2.18	0.09 1.12 0.52 - 1.80	0.06 0.60 0.48 - 1.43	0.07 0.68 0.45 - 1.58	0.09 0.74 0.44 - 1.81	0.10 0.73 0.45 - 1.92
TWFRQ4	0.01 1.86 1.45 - 5.24	0.06 2.20 1.60 - 6.03	0.05 0.95 0.73 - 3.19	0.06 0.77 0.59 - 2.47	0.06 0.68 0.52 - 1.78	0.06 0.67 0.49 - 1.78	0.07 0.85 0.49 - 1.82	0.07 0.85 0.49 - 1.65	0.06 0.70 0.48 - 1.52	0.07 0.66 0.45 - 2.11	0.08 0.71 0.45 - 1.58	0.08 0.62 0.44 - 1.94
WOM	0.02 3.87 2.65 - 9.43	0.02 2.71 1.78 - 7.75	0.02 2.00 1.30 - 5.91	0.02 1.85 1.04 - 10.83	0.02 1.37 0.87 - 4.41	0.02 1.34 0.85 - 3.27	0.02 1.45 0.73 - 3.21	0.02 1.41 0.76 - 3.43	0.02 1.24 0.74 - 2.78	0.02 1.21 0.71 - 2.88	0.03 1.48 0.74 - 2.62	0.03 1.06 0.74 - 3.02
LIBC1	0.01 1.55 1.24 - 3.73	0.01 1.29 0.90 - 3.46	0.01 1.01 0.74 - 3.05	0.01 0.93 0.65 - 2.38	0.01 0.85 0.63 - 2.50	0.01 0.81 0.62 - 2.09	0.01 0.88 0.53 - 2.06	0.01 0.81 0.51 - 1.78	0.01 1.85 0.82 - 4.71	0.01 1.66 0.77 - 4.06	0.01 1.82 0.84 - 4.11	0.01 1.72 0.86 - 4.41
MUSL1	0.00 0.01 0.00 - 0.06	0.00 0.01 0.00 - 0.13	0.00 1.19 0.01 - 6.97	0.00 0.91 0.02 - 4.47	0.00 0.81 0.01 - 3.96	0.00 0.75 0.01 - 3.06	0.00 0.89 0.01 - 4.46	0.01 0.86 0.02 - 3.85	0.01 0.86 0.02 - 6.33	0.01 0.86 0.02 - 4.01	0.02 0.80 0.04 - 3.15	0.05 1.14 0.06 - 4.10
SIMDKR	0.01 0.82 0.63 - 5.25	0.01 0.87 0.68 - 2.74	0.01 0.91 0.67 - 2.61	0.01 0.87 0.67 - 1.85	0.01 0.87 0.67 - 2.27	0.01 0.86 0.67 - 2.36	0.01 1.07 0.66 - 2.19	0.01 0.90 0.66 - 2.25	0.02 1.08 0.67 - 2.29	0.01 0.94 0.65 - 2.75	0.01 0.92 0.66 - 2.19	0.01 1.03 0.66 - 2.11
EPSM	0.01 0.70 0.50 - 1.93	0.02 0.73 0.53 - 2.23	0.02 0.82 0.59 - 2.94	0.02 0.84 0.67 - 1.98	0.02 0.68 0.53 - 1.96	0.02 0.65 0.48 - 2.14	0.03 0.81 0.48 - 1.57	0.04 0.79 0.48 - 1.72	0.06 0.80 0.49 - 1.46	0.07 0.70 0.50 - 3.66	0.13 0.77 0.53 - 1.96	0.31 1.06 0.68 - 2.40

Table 1. Running times of experimental tests n.EXP1712145140. Each time value is the mean of 500 runs. Running times are in milliseconds.

Best mean times

Heatmap top 5%

Heatmap top 10%

Heatmap top 25%

Heatmap top 50%

Show pre-processing times

Show best and worst running times

Average Running Times

TVSBS

FJS

HASH8

SBNDM

LBNDM

SBNDM2

SBNDM-BMH

FNDM

FSBNDM

SBNDMQ8

UFNDMQ2

UFNDMQ8

KBNDM

FS-W2

LWFR5

QF43

SBNDM-W2

WFR2

TWFRQ2

TWFRQ4

WOM

LIBC1

MUSL1

SIMDKR

EPSM

Chart 1. Plot of the running times of experimental tests n.EXP1712145140. The x axes reports the length of the pattern (in a log scale) while the y axes reports the running time in milliseconds.

Worst Running Times

Best Running Times

TVSBS - Thathoo-Virmani-Sai-Balakrishnan-Sekar

Detailed plot of the running times relative to the TVSBS algorithm. The plot reports the mean and the distribution of the running times.

FJS - Franek-Jennings-Smyth

Detailed plot of the running times relative to the FJS algorithm. The plot reports the mean and the distribution of the running times.

HASH8 - Wu-Manber for Single Pattern Matching (q=8)

Detailed plot of the running times relative to the HASH8 algorithm. The plot reports the mean and the distribution of the running times.

SO - Shift-Or

Detailed plot of the running times relative to the SO algorithm. The plot reports the mean and the distribution of the running times.

SBNDM - Simplified BNDM

Detailed plot of the running times relative to the SBNDM algorithm. The plot reports the mean and the distribution of the running times.

LBNDM - long patterns bndm

Detailed plot of the running times relative to the LBNDM algorithm. The plot reports the mean and the distribution of the running times.

SBNDM2 - simplified bndm with loop-unrolling

Detailed plot of the running times relative to the SBNDM2 algorithm. The plot reports the mean and the distribution of the running times.

SBNDM-BMH - sbndm with horspool shift

Detailed plot of the running times relative to the SBNDM-BMH algorithm. The plot reports the mean and the distribution of the running times.

FNDM - forward nondeterministic dawg matching

Detailed plot of the running times relative to the FNDM algorithm. The plot reports the mean and the distribution of the running times.

FSBNDM - forward sbndm

Detailed plot of the running times relative to the FSBNDM algorithm. The plot reports the mean and the distribution of the running times.

SBNDMQ8 - simplified bndm with q-grams

Detailed plot of the running times relative to the SBNDMQ8 algorithm. The plot reports the mean and the distribution of the running times.

UFNDMQ2 - Upper bits fndm with q-grams

Detailed plot of the running times relative to the UFNDMQ2 algorithm. The plot reports the mean and the distribution of the running times.

UFNDMQ8 - Upper bits fndm with q-grams

Detailed plot of the running times relative to the UFNDMQ8 algorithm. The plot reports the mean and the distribution of the running times.

KBNDM - Factorized BNDM

Detailed plot of the running times relative to the KBNDM algorithm. The plot reports the mean and the distribution of the running times.

FS-W2 - Multiple Sliding Windows

Detailed plot of the running times relative to the FS-W2 algorithm. The plot reports the mean and the distribution of the running times.

LWFR5 - Weak Factor Recognizer, Linear Version

Detailed plot of the running times relative to the LWFR5 algorithm. The plot reports the mean and the distribution of the running times.

QF43 - Q-gram Filtering q=4 s=3

Detailed plot of the running times relative to the QF43 algorithm. The plot reports the mean and the distribution of the running times.

SBNDM-W2 - SBNDM with lookahead

Detailed plot of the running times relative to the SBNDM-W2 algorithm. The plot reports the mean and the distribution of the running times.

WFR2 - Weak Factor Recognizer (m>=2)

Detailed plot of the running times relative to the WFR2 algorithm. The plot reports the mean and the distribution of the running times.

TWFRQ2 - Tuned Weak Factor Recognizer with q-grams

Detailed plot of the running times relative to the TWFRQ2 algorithm. The plot reports the mean and the distribution of the running times.

TWFRQ4 - Tuned Weak Factor Recognizer with q-grams

Detailed plot of the running times relative to the TWFRQ4 algorithm. The plot reports the mean and the distribution of the running times.

WOM - Worst Occurrence Matcher

Detailed plot of the running times relative to the WOM algorithm. The plot reports the mean and the distribution of the running times.

LIBC1 - memmem

Detailed plot of the running times relative to the LIBC1 algorithm. The plot reports the mean and the distribution of the running times.

MUSL1 - musl memmem

Detailed plot of the running times relative to the MUSL1 algorithm. The plot reports the mean and the distribution of the running times.

SIMDKR - SIMD generic Rabin-Karp variants

Detailed plot of the running times relative to the SIMDKR algorithm. The plot reports the mean and the distribution of the running times.

EPSM - SSE4 Exact Packed String Matching

Detailed plot of the running times relative to the EPSM algorithm. The plot reports the mean and the distribution of the running times.