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 16:25:10

Text rand256 (alphabet : 256 - size : 1048576 bytes)

	2	4	8	16	32	64	128	256	512	1024	2048	4096
TVSBS	0.31 5.69 3.73 - 9.00	0.30 4.01 2.81 - 6.62	0.30 3.12 2.13 - 5.28	0.29 2.25 1.64 - 3.82	0.32 2.05 1.39 - 2.87	0.33 1.85 1.22 - 2.58	0.29 1.78 1.16 - 2.73	0.32 1.87 1.42 - 2.79	0.34 1.75 1.24 - 2.44	0.33 1.50 1.02 - 2.24	0.32 1.33 0.87 - 2.20	0.36 1.40 0.84 - 2.04
FJS	0.03 4.59 2.73 - 6.06	0.02 2.99 1.95 - 4.23	0.02 2.03 1.42 - 4.85	0.02 1.47 1.12 - 2.63	0.02 1.35 0.97 - 2.07	0.02 1.20 0.92 - 2.02	0.02 1.25 0.88 - 1.81	0.02 1.20 0.83 - 5.48	0.03 1.49 1.08 - 1.97	0.04 1.49 1.10 - 1.93	0.04 1.45 1.12 - 2.38	0.06 1.53 1.13 - 2.02
HASH8	0.02 3.00 2.15 - 7.18	0.02 2.93 2.18 - 5.40	0.02 20.85 13.05 - 26.38	0.02 3.19 2.13 - 15.23	0.02 1.82 1.26 - 2.53	0.02 1.37 0.99 - 2.10	0.02 1.30 0.89 - 1.81	0.02 1.13 0.84 - 2.16	0.02 1.47 1.05 - 2.15	0.03 1.53 1.10 - 2.06	0.03 1.53 1.08 - 1.99	0.04 1.51 1.07 - 2.74
SO	0.02 2.71 1.69 - 5.94	0.02 2.76 1.82 - 3.97	0.02 3.05 1.80 - 4.61	0.02 2.70 1.77 - 5.36	0.02 2.91 1.81 - 5.75	0.02 2.33 1.62 - 4.25	0.02 2.22 1.62 - 4.26	0.02 2.55 1.62 - 4.38	0.02 2.48 1.62 - 3.66	0.02 2.42 1.65 - 4.41	0.02 2.48 1.64 - 4.03	0.02 2.27 1.64 - 6.50
SBNDM	0.04 4.65 2.73 - 6.01	0.04 1.98 1.38 - 4.80	0.04 1.48 0.99 - 2.50	0.03 1.15 0.83 - 2.00	0.04 1.21 0.79 - 1.53	0.03 1.14 0.77 - 1.93	0.03 1.07 0.77 - 1.86	0.03 1.23 0.78 - 1.72	0.03 1.18 0.77 - 1.88	0.03 1.22 0.79 - 1.79	0.03 1.17 0.77 - 1.87	0.03 1.08 0.77 - 1.69
LBNDM	0.02 2.44 1.47 - 4.45	0.02 1.72 1.13 - 3.15	0.02 1.49 0.94 - 2.09	0.02 1.20 0.80 - 2.21	0.02 1.24 0.78 - 1.71	0.02 1.11 0.79 - 1.90	0.02 1.13 0.75 - 1.84	0.02 1.01 0.70 - 1.70	0.02 0.95 0.68 - 1.81	0.02 1.02 0.66 - 1.55	0.02 1.01 0.65 - 1.50	0.03 0.95 0.63 - 1.33
SBNDM2	0.02 2.96 1.76 - 6.55	0.02 1.59 1.11 - 2.45	0.02 1.38 0.89 - 2.02	0.02 1.11 0.81 - 1.93	0.02 1.12 0.76 - 1.63	0.02 1.03 0.76 - 1.54	0.02 1.06 0.75 - 1.87	0.02 1.06 0.74 - 1.57	0.02 1.12 0.77 - 1.72	0.02 1.11 0.75 - 1.75	0.02 1.08 0.74 - 1.54	0.02 1.14 0.74 - 1.53
SBNDM-BMH	0.03 3.32 2.22 - 4.53	0.03 2.03 1.48 - 3.36	0.03 1.67 1.14 - 2.36	0.03 1.27 0.96 - 2.42	0.03 1.35 0.91 - 3.56	0.04 1.35 0.89 - 2.03	0.03 1.32 0.91 - 1.94	0.03 1.30 0.91 - 1.84	0.03 1.34 0.91 - 1.92	0.04 1.37 0.92 - 1.79	0.03 1.29 0.90 - 1.78	0.03 1.31 0.89 - 2.04
FNDM	0.02 2.41 1.47 - 3.91	0.02 1.85 1.10 - 2.87	0.02 1.41 0.91 - 2.46	0.02 1.16 0.83 - 2.19	0.02 1.22 0.84 - 1.90	0.02 1.16 0.77 - 1.56	0.02 1.15 0.77 - 5.34	0.02 1.19 0.77 - 1.90	0.02 1.19 0.76 - 1.86	0.02 1.14 0.76 - 1.75	0.02 1.16 0.77 - 3.81	0.02 1.27 0.77 - 1.68
FSBNDM	0.02 2.07 1.28 - 5.90	0.02 1.42 1.01 - 3.26	0.02 1.30 0.84 - 2.27	0.02 1.06 0.81 - 2.03	0.02 1.16 0.75 - 1.85	0.02 1.11 0.77 - 1.84	0.02 1.17 0.76 - 2.24	0.02 1.12 0.75 - 1.64	0.02 1.14 0.76 - 1.52	0.02 1.13 0.75 - 1.54	0.02 1.08 0.75 - 1.89	0.02 1.00 0.74 - 1.77
SBNDMQ8	0.02 3.10 2.11 - 8.86	0.02 3.00 2.17 - 4.61	0.02 7.61 4.45 - 13.78	0.02 1.73 1.17 - 4.08	0.02 1.30 0.90 - 1.98	0.02 1.28 0.89 - 2.33	0.02 1.27 0.91 - 2.28	0.02 1.33 0.89 - 2.29	0.02 1.28 0.89 - 2.03	0.02 1.36 0.87 - 2.08	0.02 1.31 0.88 - 2.15	0.02 1.35 0.90 - 2.01
UFNDMQ2	0.03 2.30 1.48 - 3.46	0.03 1.67 1.12 - 2.38	0.03 1.39 0.92 - 2.28	0.03 1.14 0.82 - 1.76	0.01 1.07 0.80 - 2.10	0.02 1.15 0.78 - 3.16	0.02 1.15 0.76 - 1.71	0.02 1.12 0.76 - 1.61	0.01 1.12 0.76 - 1.79	0.02 1.08 0.76 - 1.58	0.01 0.96 0.80 - 1.57	0.02 1.13 0.75 - 2.02
UFNDMQ8	0.02 3.28 2.16 - 5.21	0.02 3.00 2.16 - 5.17	0.03 1.90 1.23 - 3.54	0.03 1.47 0.99 - 3.30	0.02 1.30 0.91 - 1.80	0.02 1.40 0.91 - 2.75	0.02 1.30 0.89 - 2.04	0.02 1.31 0.90 - 2.64	0.02 1.38 0.90 - 2.00	0.01 1.34 0.90 - 3.57	0.01 1.28 0.91 - 2.06	0.02 1.38 0.88 - 2.36
KBNDM	0.02 4.75 2.97 - 8.91	0.02 3.09 1.85 - 5.83	0.02 1.77 1.25 - 3.34	0.02 1.42 1.01 - 2.37	0.02 1.36 0.94 - 1.93	0.02 1.24 0.89 - 2.09	0.02 1.15 0.84 - 1.63	0.03 1.12 0.77 - 1.72	0.03 1.08 0.78 - 1.64	0.03 1.15 0.75 - 5.85	0.03 1.22 0.75 - 1.73	0.03 1.14 0.72 - 1.82
FS-W2	0.06 2.70 1.98 - 4.22	0.07 2.16 1.34 - 3.10	0.06 1.39 1.04 - 3.69	0.06 1.27 0.90 - 2.00	0.06 1.16 0.84 - 1.83	0.07 1.26 0.84 - 1.60	0.07 1.22 0.81 - 1.61	0.07 1.17 0.77 - 1.73	0.08 1.31 0.95 - 1.70	0.08 1.28 0.94 - 2.18	0.11 1.31 0.94 - 1.94	0.15 1.36 0.97 - 1.87
LWFR5	0.02 3.19 2.13 - 5.62	0.02 3.29 2.18 - 4.31	0.11 5.32 2.74 - 7.58	0.09 1.35 0.93 - 2.40	0.10 1.29 0.85 - 2.44	0.10 1.13 0.83 - 1.82	0.10 1.15 0.78 - 2.00	0.11 1.19 0.76 - 1.69	0.13 1.14 0.73 - 1.69	0.15 1.13 0.70 - 1.55	0.20 1.22 0.74 - 1.65	0.26 1.19 0.74 - 1.94
QF43	0.02 3.44 2.16 - 4.40	0.02 3.26 2.17 - 4.45	0.03 1.61 1.12 - 3.57	0.03 1.30 0.87 - 2.24	0.03 1.08 0.79 - 1.97	0.03 1.14 0.75 - 1.60	0.03 1.13 0.73 - 1.61	0.03 1.03 0.70 - 1.53	0.03 1.00 0.65 - 1.68	0.04 0.96 0.63 - 1.52	0.04 0.94 0.62 - 1.41	0.04 1.00 0.62 - 1.82
SBNDM-W2	0.02 2.15 1.47 - 4.38	0.02 1.69 1.09 - 2.50	0.02 1.30 0.90 - 1.95	0.02 1.16 0.81 - 2.04	0.02 1.09 0.79 - 1.99	0.02 1.15 0.79 - 1.78	0.02 1.21 0.78 - 1.70	0.02 1.03 0.79 - 1.75	0.02 1.01 0.78 - 1.58	0.02 1.18 0.79 - 2.17	0.02 1.18 0.79 - 1.84	0.02 1.07 0.79 - 1.71
WFR2	0.10 3.69 2.11 - 6.06	0.09 1.99 1.26 - 5.04	0.10 1.62 1.01 - 2.64	0.10 1.26 0.85 - 2.22	0.10 1.27 0.82 - 4.36	0.10 1.21 0.82 - 1.63	0.10 1.21 0.80 - 1.75	0.11 1.21 0.80 - 1.78	0.12 1.18 0.72 - 1.75	0.12 1.02 0.69 - 1.60	0.16 1.10 0.69 - 1.52	0.23 1.22 0.73 - 1.86
TWFRQ2	0.10 3.06 1.78 - 4.02	0.10 1.82 1.14 - 3.72	0.10 1.39 0.93 - 2.35	0.09 1.16 0.82 - 1.79	0.09 1.16 0.83 - 1.71	0.09 1.12 0.78 - 1.75	0.10 1.18 0.80 - 2.18	0.09 1.04 0.72 - 1.70	0.10 1.06 0.69 - 1.82	0.12 1.14 0.68 - 1.60	0.12 1.04 0.66 - 1.97	0.15 1.15 0.67 - 1.64
TWFRQ4	0.02 2.79 2.13 - 4.53	0.09 3.65 2.27 - 6.17	0.08 1.35 1.08 - 3.39	0.09 1.27 0.91 - 1.79	0.10 1.21 0.84 - 1.76	0.09 1.08 0.78 - 2.23	0.10 1.18 0.79 - 1.56	0.10 1.13 0.74 - 1.74	0.10 1.05 0.68 - 1.84	0.10 0.94 0.67 - 1.77	0.12 1.08 0.68 - 1.45	0.14 1.09 0.68 - 1.58
WOM	0.03 4.02 2.80 - 5.96	0.03 3.04 1.96 - 4.15	0.02 1.72 1.42 - 4.04	0.03 1.56 1.13 - 3.36	0.03 1.42 0.97 - 1.96	0.03 1.13 0.89 - 2.15	0.03 1.12 0.87 - 1.63	0.04 1.24 0.80 - 1.68	0.04 1.33 0.95 - 1.76	0.03 1.29 1.03 - 2.61	0.04 1.37 0.99 - 2.48	0.05 1.35 1.04 - 2.18
LIBC1	0.01 2.33 1.57 - 4.23	0.02 2.00 1.27 - 3.36	0.01 1.24 0.93 - 3.30	0.02 1.18 0.81 - 1.94	0.01 1.11 0.80 - 1.60	0.01 1.08 0.77 - 1.94	0.02 1.18 0.79 - 1.54	0.02 1.25 0.84 - 1.90	0.02 1.40 1.11 - 2.46	0.01 1.34 1.08 - 2.16	0.02 1.40 1.08 - 4.46	0.02 1.48 1.10 - 1.95
MUSL1	0.00 0.14 0.01 - 1.11	0.01 1.19 0.01 - 2.90	0.00 0.69 0.01 - 2.03	0.00 0.64 0.01 - 5.88	0.01 0.59 0.01 - 1.40	0.01 0.55 0.01 - 1.47	0.01 0.58 0.02 - 2.20	0.01 0.64 0.01 - 1.85	0.01 0.71 0.02 - 1.64	0.01 0.67 0.02 - 1.95	0.02 0.75 0.04 - 1.75	0.04 0.80 0.05 - 1.98
SIMDKR	0.02 1.10 0.76 - 1.62	0.02 1.13 0.77 - 1.89	0.02 1.07 0.75 - 2.67	0.02 1.08 0.78 - 1.73	0.02 1.07 0.77 - 1.54	0.02 1.15 0.76 - 1.54	0.02 1.11 0.78 - 1.59	0.02 1.18 0.78 - 1.85	0.02 1.24 0.76 - 1.65	0.02 0.99 0.77 - 1.61	0.02 1.19 0.76 - 1.96	0.02 1.16 0.76 - 2.60
EPSM	0.02 1.30 0.81 - 1.76	0.02 1.27 0.81 - 2.05	0.03 1.31 0.91 - 4.00	0.03 1.42 1.03 - 2.26	0.03 1.23 0.84 - 2.48	0.03 1.16 0.80 - 1.72	0.04 1.12 0.78 - 1.84	0.06 1.17 0.81 - 1.65	0.08 1.18 0.77 - 1.50	0.12 1.16 0.78 - 1.67	0.21 1.20 0.82 - 1.86	0.41 1.48 1.01 - 2.69

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.