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 14:26:53

Text rand4 (alphabet : 4 - size : 1048576 bytes)

	2	4	8	16	32	64	128	256	512	1024	2048	4096
TVSBS	0.24 6.82 3.76 - 12.45	0.19 4.15 2.99 - 11.33	0.20 3.24 2.13 - 7.74	0.19 2.29 1.61 - 5.77	0.18 1.96 1.23 - 5.75	0.19 1.96 1.20 - 5.30	0.19 1.92 1.15 - 4.68	0.19 1.88 1.05 - 4.86	0.18 1.84 1.03 - 4.96	0.18 1.80 1.13 - 5.56	0.19 1.84 1.01 - 4.60	0.18 1.82 1.03 - 5.25
FJS	0.02 7.99 4.07 - 13.91	0.01 4.96 3.17 - 14.99	0.01 4.28 2.45 - 11.12	0.01 4.24 2.15 - 13.79	0.02 4.24 1.62 - 12.80	0.01 4.10 1.72 - 10.78	0.02 4.38 1.84 - 10.16	0.02 4.27 1.34 - 11.87	0.02 4.08 1.86 - 10.68	0.02 4.20 1.90 - 10.70	0.03 4.13 1.96 - 14.29	0.05 4.14 2.04 - 11.61
HASH8	0.02 2.67 1.44 - 5.49	0.01 1.89 1.45 - 5.03	0.01 10.70 8.95 - 24.50	0.01 1.72 1.43 - 4.00	0.01 1.06 0.83 - 2.64	0.01 0.79 0.64 - 1.84	0.01 0.71 0.57 - 1.83	0.01 0.70 0.51 - 2.59	0.01 0.79 0.63 - 1.73	0.01 0.80 0.65 - 2.03	0.02 0.83 0.65 - 1.71	0.02 0.82 0.66 - 1.84
SO	0.02 2.36 1.20 - 6.10	0.01 1.66 1.19 - 4.12	0.01 1.63 1.19 - 4.08	0.01 1.77 1.21 - 5.22	0.01 1.68 1.20 - 4.12	0.01 1.35 1.08 - 4.10	0.01 1.39 1.09 - 3.18	0.01 1.40 1.08 - 3.49	0.01 1.39 1.08 - 3.67	0.01 1.38 1.09 - 3.51	0.01 1.39 1.08 - 3.21	0.01 1.41 1.08 - 4.09
SBNDM	0.03 4.60 2.56 - 11.55	0.02 2.43 1.26 - 6.10	0.02 1.80 0.97 - 4.86	0.02 1.39 1.01 - 3.61	0.02 0.97 0.74 - 3.04	0.02 0.96 0.72 - 2.13	0.02 1.03 0.71 - 3.21	0.02 0.96 0.72 - 2.98	0.02 0.94 0.71 - 2.42	0.02 0.96 0.74 - 2.42	0.02 0.94 0.71 - 2.49	0.02 0.95 0.73 - 2.40
LBNDM	0.02 8.93 3.22 - 15.91	0.01 4.00 1.87 - 10.66	0.01 2.28 1.66 - 7.96	0.01 1.65 1.12 - 5.29	0.01 1.10 0.82 - 2.95	0.01 0.99 0.71 - 2.66	0.01 0.96 0.65 - 2.17	0.01 2.11 0.80 - 10.44	0.01 8.66 3.80 - 21.70	0.01 8.02 5.65 - 23.18	0.02 6.83 5.02 - 15.13	0.02 6.49 4.52 - 14.25
SBNDM2	0.00 - 1.92 - 1739.71	0.01 2.06 1.06 - 6.05	0.01 1.79 0.91 - 4.42	0.01 1.32 0.94 - 3.14	0.01 0.91 0.69 - 2.12	0.01 0.87 0.66 - 2.56	0.01 0.88 0.67 - 2.24	0.01 0.93 0.69 - 2.19	0.01 0.91 0.65 - 2.28	0.01 0.88 0.68 - 2.87	0.01 0.89 0.66 - 2.52	0.01 0.89 0.68 - 2.57
SBNDM-BMH	0.02 7.21 3.36 - 13.48	0.02 3.29 1.92 - 9.19	0.02 2.01 1.43 - 7.32	0.02 1.36 1.01 - 3.51	0.02 0.96 0.73 - 2.51	0.02 0.94 0.72 - 2.44	0.02 0.96 0.71 - 3.04	0.02 0.96 0.73 - 2.32	0.02 0.97 0.76 - 2.66	0.02 0.98 0.71 - 3.01	0.02 0.94 0.72 - 2.39	0.02 0.93 0.73 - 2.47
FNDM	0.01 6.22 2.80 - 15.81	0.01 4.27 1.89 - 10.09	0.01 2.50 1.83 - 6.58	0.01 1.69 1.26 - 4.41	0.01 1.17 0.87 - 2.96	0.01 1.16 0.89 - 2.75	0.01 1.17 0.88 - 2.78	0.01 1.20 0.89 - 3.11	0.01 1.18 0.88 - 2.98	0.01 1.17 0.89 - 3.14	0.01 1.14 0.89 - 2.96	0.01 1.16 0.89 - 3.33
FSBNDM	0.01 5.96 2.85 - 15.19	0.01 3.26 1.80 - 8.42	0.01 1.88 1.39 - 4.87	0.01 1.22 0.91 - 3.13	0.01 0.89 0.69 - 2.15	0.01 0.91 0.68 - 2.20	0.01 0.90 0.69 - 1.97	0.01 0.92 0.69 - 2.49	0.01 0.94 0.68 - 6.17	0.01 0.91 0.70 - 2.59	0.01 0.95 0.71 - 2.94	0.01 0.90 0.70 - 3.13
SBNDMQ8	0.02 2.61 1.44 - 5.27	0.01 1.88 1.43 - 4.70	0.01 4.85 3.06 - 10.45	0.01 1.00 0.75 - 2.29	0.01 0.75 0.55 - 1.84	0.01 0.74 0.55 - 2.33	0.01 0.71 0.56 - 1.53	0.01 0.75 0.55 - 2.30	0.01 0.72 0.54 - 1.71	0.01 0.73 0.56 - 1.95	0.01 0.74 0.55 - 2.09	0.01 0.74 0.55 - 1.94
UFNDMQ2	0.02 2.77 1.91 - 7.44	0.02 2.32 1.33 - 5.85	0.02 1.86 1.33 - 4.00	0.02 1.31 0.95 - 2.95	0.01 0.88 0.68 - 2.22	0.01 0.89 0.67 - 2.77	0.01 0.90 0.68 - 2.12	0.01 0.91 0.68 - 2.16	0.02 0.96 0.68 - 4.30	0.01 0.95 0.64 - 3.25	0.01 0.93 0.68 - 2.91	0.01 0.91 0.68 - 2.53
UFNDMQ8	0.01 1.95 1.43 - 4.42	0.01 1.86 1.43 - 4.69	0.02 1.08 0.79 - 3.24	0.02 0.83 0.63 - 2.46	0.01 0.76 0.55 - 2.00	0.01 0.75 0.55 - 2.06	0.01 0.75 0.55 - 1.71	0.01 0.74 0.56 - 1.73	0.01 0.76 0.56 - 2.06	0.01 0.74 0.56 - 1.82	0.01 0.75 0.56 - 1.90	0.01 0.75 0.56 - 1.94
KBNDM	0.01 4.63 3.13 - 10.73	0.01 2.61 1.70 - 7.51	0.01 1.91 1.30 - 4.83	0.01 1.44 1.07 - 3.54	0.01 1.06 0.80 - 2.91	0.01 0.85 0.65 - 2.17	0.01 0.82 0.62 - 2.11	0.01 0.81 0.62 - 1.97	0.01 0.82 0.62 - 2.31	0.01 0.81 0.62 - 1.90	0.01 0.82 0.61 - 2.04	0.01 0.82 0.63 - 2.27
FS-W2	0.04 5.09 3.49 - 13.05	0.04 3.60 2.02 - 10.58	0.04 2.47 1.49 - 6.19	0.04 2.14 1.27 - 5.36	0.04 1.91 1.14 - 4.63	0.04 1.75 1.03 - 5.18	0.04 1.58 0.94 - 4.06	0.04 1.41 0.86 - 3.54	0.05 1.37 0.85 - 3.61	0.06 1.34 0.87 - 4.24	0.08 1.29 0.77 - 3.43	0.11 1.17 0.80 - 2.98
LWFR5	0.01 1.92 1.45 - 5.33	0.01 1.93 1.45 - 5.14	0.06 2.57 1.78 - 7.88	0.06 0.81 0.60 - 2.38	0.06 0.73 0.54 - 1.82	0.07 0.79 0.51 - 5.06	0.06 0.64 0.49 - 1.63	0.07 0.67 0.51 - 1.87	0.07 0.65 0.48 - 1.81	0.09 0.64 0.47 - 1.63	0.11 0.63 0.49 - 1.66	0.16 0.69 0.51 - 2.14
QF43	0.01 1.80 1.41 - 4.90	0.01 1.96 1.45 - 5.14	0.02 1.09 0.80 - 3.01	0.02 0.74 0.59 - 1.56	0.02 0.70 0.52 - 2.09	0.02 0.64 0.49 - 1.77	0.02 0.63 0.48 - 1.66	0.02 0.66 0.50 - 1.81	0.02 0.63 0.48 - 1.65	0.02 0.63 0.48 - 1.69	0.02 0.61 0.47 - 1.78	0.00 - 0.55 - 420.25
SBNDM-W2	0.01 5.42 3.41 - 13.51	0.01 3.68 2.06 - 10.43	0.01 1.95 1.47 - 5.36	0.02 1.49 0.98 - 7.97	0.01 0.88 0.69 - 2.07	0.01 0.88 0.68 - 2.55	0.01 0.90 0.69 - 2.62	0.01 0.89 0.69 - 2.36	0.01 0.89 0.68 - 3.21	0.01 0.87 0.68 - 2.15	0.02 0.94 0.69 - 3.14	0.01 0.90 0.70 - 2.42
WFR2	0.06 3.73 2.37 - 8.50	0.06 2.41 1.44 - 6.92	0.06 1.82 1.08 - 4.44	0.06 1.24 0.85 - 3.14	0.06 0.86 0.61 - 2.00	0.06 0.72 0.55 - 1.94	0.06 0.74 0.52 - 1.74	0.06 0.70 0.52 - 1.75	0.06 0.63 0.48 - 1.86	0.07 0.60 0.46 - 1.60	0.09 0.62 0.46 - 1.66	0.12 0.64 0.49 - 1.89
TWFRQ2	0.06 3.23 2.07 - 8.21	0.07 2.51 1.34 - 6.33	0.06 1.83 1.10 - 5.15	0.06 1.22 0.84 - 2.96	0.06 0.85 0.62 - 2.18	0.06 0.72 0.54 - 2.21	0.06 0.72 0.52 - 1.68	0.06 0.71 0.54 - 2.02	0.06 0.65 0.47 - 1.63	0.06 0.61 0.45 - 3.14	0.07 0.59 0.45 - 1.62	0.09 0.63 0.46 - 1.91
TWFRQ4	0.01 2.12 1.45 - 4.33	0.06 2.59 1.64 - 6.71	0.06 1.06 0.78 - 2.54	0.06 0.81 0.60 - 3.86	0.05 0.70 0.53 - 1.56	0.06 0.68 0.51 - 1.84	0.06 0.71 0.51 - 2.07	0.06 0.70 0.52 - 1.79	0.06 0.64 0.47 - 1.97	0.06 0.60 0.45 - 1.73	0.07 0.58 0.45 - 1.57	0.08 0.61 0.45 - 1.97
WOM	0.02 7.62 3.76 - 16.78	0.02 5.42 2.40 - 14.58	0.02 3.32 1.83 - 9.24	0.02 2.69 1.33 - 7.36	0.02 2.22 1.29 - 6.69	0.02 2.02 1.19 - 5.16	0.02 1.90 1.23 - 5.39	0.02 1.77 1.03 - 4.98	0.02 1.65 1.04 - 4.62	0.02 1.58 1.06 - 3.98	0.02 1.53 1.02 - 3.54	0.03 1.53 1.02 - 5.06
LIBC1	0.01 3.62 1.83 - 6.24	0.01 2.59 1.36 - 6.86	0.01 1.98 1.09 - 5.48	0.01 1.47 0.98 - 4.16	0.01 1.12 0.81 - 2.49	0.01 0.96 0.71 - 2.28	0.01 0.99 0.70 - 2.55	0.01 0.97 0.64 - 2.50	0.01 2.98 1.20 - 12.17	0.01 3.01 1.17 - 9.00	0.01 3.03 1.34 - 8.41	0.01 3.14 1.34 - 8.48
MUSL1	0.00 0.01 0.00 - 0.03	0.00 0.01 0.01 - 0.05	0.00 0.23 0.01 - 2.18	0.00 1.74 0.02 - 9.08	0.00 1.66 0.01 - 9.30	0.00 1.69 0.02 - 6.85	0.00 1.66 0.01 - 8.17	0.01 1.66 0.02 - 9.51	0.01 1.66 0.02 - 9.59	0.01 1.78 0.03 - 8.80	0.03 1.73 0.05 - 8.69	0.05 1.90 0.09 - 11.14
SIMDKR	0.01 1.03 0.78 - 2.52	0.01 1.38 0.92 - 3.52	0.01 1.17 0.86 - 2.62	0.01 1.18 0.88 - 3.04	0.01 1.23 0.87 - 3.54	0.01 1.14 0.84 - 2.73	0.01 1.12 0.84 - 2.33	0.01 1.18 0.84 - 2.85	0.01 1.16 0.84 - 3.36	0.01 1.13 0.84 - 3.11	0.01 1.10 0.83 - 2.51	0.01 1.11 0.84 - 3.00
EPSM	0.01 0.74 0.50 - 1.84	0.01 0.84 0.52 - 1.88	0.02 0.89 0.68 - 3.20	0.02 0.82 0.66 - 2.14	0.02 0.68 0.52 - 1.75	0.02 0.64 0.48 - 1.44	0.02 0.65 0.48 - 1.63	0.03 0.63 0.48 - 1.72	0.04 0.64 0.48 - 1.40	0.07 0.65 0.49 - 1.96	0.12 0.71 0.54 - 1.81	0.24 0.87 0.65 - 3.15

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.