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 13:52:20

Text rand2 (alphabet : 2 - size : 1048576 bytes)

	2	4	8	16	32	64	128	256	512	1024	2048	4096
TVSBS	0.23 7.76 4.01 - 19.23	0.24 8.21 3.66 - 17.54	0.19 6.54 2.93 - 19.27	0.26 9.19 2.39 - 21.21	0.22 7.72 1.70 - 20.94	0.25 9.16 1.97 - 21.84	0.19 6.86 1.78 - 21.24	0.23 8.18 2.02 - 21.84	0.20 7.42 1.76 - 21.79	0.23 8.20 1.92 - 21.68	0.24 8.68 2.08 - 24.27	0.23 8.29 1.57 - 20.78
FJS	0.02 8.11 4.94 - 17.11	0.02 8.54 4.65 - 23.04	0.02 8.62 3.86 - 20.21	0.02 10.46 3.71 - 23.13	0.02 10.97 3.44 - 20.63	0.02 11.90 3.91 - 22.34	0.02 11.56 3.66 - 22.19	0.02 11.20 4.17 - 22.88	0.03 11.26 3.63 - 24.21	0.03 10.13 3.92 - 21.58	0.05 12.82 3.38 - 22.06	0.07 11.01 3.53 - 22.38
HASH8	0.01 1.92 1.45 - 4.69	0.01 2.05 1.46 - 4.62	0.01 11.89 8.94 - 27.26	0.02 2.70 1.42 - 4.35	0.02 1.45 0.82 - 2.59	0.02 1.03 0.63 - 2.63	0.01 0.82 0.56 - 1.75	0.02 0.89 0.51 - 1.84	0.02 1.16 0.62 - 1.79	0.02 1.08 0.63 - 1.75	0.03 1.35 0.62 - 1.82	0.03 1.00 0.64 - 1.62
SO	0.02 2.08 1.19 - 4.17	0.02 2.04 1.21 - 5.30	0.01 1.69 1.18 - 4.73	0.01 1.84 1.21 - 4.63	0.02 2.14 1.19 - 5.39	0.02 1.82 1.07 - 3.32	0.01 1.56 1.07 - 3.24	0.02 1.74 1.08 - 4.07	0.01 1.51 1.09 - 3.21	0.01 1.66 1.07 - 4.22	0.02 2.04 1.08 - 3.88	0.02 1.69 1.08 - 3.23
SBNDM	0.02 6.41 3.99 - 14.42	0.03 6.75 2.89 - 13.87	0.02 3.78 1.53 - 9.43	0.03 2.28 1.39 - 5.37	0.03 1.84 1.00 - 3.19	0.02 1.76 1.00 - 3.24	0.02 1.65 1.01 - 3.24	0.03 1.98 1.00 - 3.34	0.03 2.13 1.03 - 3.15	0.02 1.64 1.02 - 3.14	0.02 1.79 1.01 - 3.24	0.02 1.68 1.01 - 3.07
LBNDM	0.01 10.12 6.96 - 22.61	0.01 8.34 4.35 - 18.13	0.01 4.86 2.29 - 11.81	0.01 2.59 1.85 - 6.81	0.02 2.52 1.17 - 4.41	0.02 2.05 0.95 - 6.12	0.02 9.01 0.95 - 49.08	0.02 26.23 8.14 - 40.09	0.02 16.99 7.81 - 31.38	0.02 12.88 8.38 - 26.39	0.02 15.35 7.63 - 23.87	0.03 12.66 7.13 - 22.17
SBNDM2	0.01 6.27 4.10 - 14.28	0.02 7.15 2.80 - 14.05	0.01 3.74 1.54 - 9.37	0.01 2.20 1.40 - 5.36	0.02 1.71 0.97 - 3.09	0.02 1.60 0.93 - 3.02	0.02 1.57 0.93 - 3.03	0.01 1.43 0.92 - 3.38	0.01 1.43 0.92 - 3.12	0.01 1.34 0.93 - 2.89	0.02 1.86 0.93 - 3.56	0.02 1.54 0.91 - 2.94
SBNDM-BMH	0.02 6.62 4.42 - 16.82	0.02 6.74 3.36 - 13.35	0.02 3.96 2.02 - 9.72	0.02 2.90 1.55 - 5.11	0.03 1.94 1.02 - 3.57	0.02 1.33 1.02 - 3.53	0.02 1.85 1.01 - 3.15	0.03 1.96 1.01 - 3.53	0.02 1.72 1.01 - 3.11	0.02 1.63 1.03 - 3.28	0.02 1.60 1.01 - 3.06	0.02 1.80 1.04 - 3.23
FNDM	0.02 9.23 5.38 - 19.80	0.02 6.91 2.63 - 13.26	0.01 3.77 1.27 - 10.03	0.01 2.58 1.19 - 5.87	0.02 2.15 1.14 - 4.11	0.01 2.00 1.15 - 4.26	0.01 2.00 1.13 - 4.13	0.02 2.11 1.15 - 4.06	0.01 1.96 1.16 - 3.99	0.02 2.08 1.14 - 4.12	0.02 2.33 1.12 - 4.11	0.02 2.23 1.15 - 4.21
FSBNDM	0.02 7.97 5.22 - 17.39	0.01 5.76 3.63 - 13.44	0.01 3.54 2.12 - 9.02	0.01 2.31 1.33 - 4.47	0.02 1.85 0.96 - 2.98	0.02 1.70 0.94 - 3.00	0.01 1.48 0.96 - 3.31	0.01 1.54 0.96 - 2.97	0.02 1.73 0.94 - 3.05	0.02 1.76 0.96 - 3.03	0.02 1.85 0.95 - 3.42	0.01 1.41 0.98 - 3.00
SBNDMQ8	0.02 2.42 1.43 - 5.81	0.01 1.90 1.45 - 4.86	0.01 4.75 3.10 - 11.52	0.02 1.48 0.84 - 2.87	0.02 0.99 0.62 - 2.04	0.01 0.91 0.62 - 2.24	0.02 1.23 0.63 - 2.08	0.02 1.24 0.63 - 1.93	0.02 1.07 0.63 - 2.03	0.02 1.07 0.62 - 1.91	0.02 1.13 0.61 - 1.95	0.02 1.09 0.63 - 2.44
UFNDMQ2	0.04 7.05 4.57 - 19.00	0.02 5.90 3.40 - 13.10	0.02 4.00 2.33 - 9.43	0.02 3.51 1.75 - 6.61	0.01 2.26 1.19 - 4.44	0.01 2.35 1.19 - 4.23	0.01 2.27 1.27 - 4.51	0.01 1.92 1.25 - 4.25	0.01 2.21 1.24 - 4.13	0.01 2.11 1.23 - 4.88	0.01 2.23 1.26 - 4.21	0.01 2.44 1.27 - 4.34
UFNDMQ8	0.02 2.47 1.46 - 9.08	0.02 2.29 1.44 - 5.23	0.02 1.25 0.90 - 3.70	0.02 1.23 0.74 - 2.57	0.01 1.05 0.63 - 2.09	0.01 1.24 0.63 - 2.33	0.01 1.31 0.63 - 2.38	0.01 1.18 0.63 - 2.02	0.01 0.96 0.64 - 2.97	0.01 1.03 0.63 - 2.54	0.01 1.11 0.64 - 2.18	0.01 1.21 0.64 - 2.24
KBNDM	0.02 10.20 5.78 - 18.05	0.02 7.00 3.39 - 15.41	0.01 4.02 1.73 - 10.64	0.02 3.38 1.63 - 5.77	0.02 1.97 1.14 - 3.69	0.02 1.76 0.92 - 3.26	0.02 1.63 0.91 - 3.42	0.02 1.50 0.92 - 7.16	0.02 1.68 0.94 - 3.73	0.02 1.66 0.90 - 2.95	0.02 1.69 0.93 - 3.00	0.02 1.85 0.93 - 3.16
FS-W2	0.06 12.08 6.30 - 19.35	0.05 8.22 4.01 - 19.81	0.04 5.33 2.19 - 13.83	0.05 5.23 1.65 - 9.98	0.05 3.74 1.66 - 8.74	0.05 3.04 1.30 - 6.89	0.06 2.95 1.17 - 5.82	0.06 2.23 1.03 - 5.33	0.06 1.90 0.99 - 4.23	0.07 1.69 0.93 - 4.26	0.12 1.83 0.87 - 3.84	0.19 1.94 0.84 - 3.59
LWFR5	0.02 2.37 1.45 - 5.45	0.02 2.26 1.44 - 5.28	0.06 3.37 2.20 - 8.26	0.08 2.26 0.75 - 4.45	0.08 1.66 0.77 - 3.18	0.07 1.25 0.76 - 2.60	0.07 0.91 0.63 - 2.13	0.07 0.91 0.61 - 2.02	0.10 1.26 0.65 - 2.63	0.10 33.35 0.73 - 213.83	0.00 - 357.21 - 357.21	0.00 - 651.98 - 651.98
QF43	0.02 2.42 1.45 - 5.40	0.01 1.93 1.42 - 5.68	0.02 3.89 1.21 - 9.59	0.02 2.09 0.87 - 5.67	0.02 1.66 0.82 - 3.68	0.03 1.66 0.77 - 5.49	0.02 8.88 0.67 - 51.93	0.02 31.37 1.19 - 68.85	0.02 53.72 47.99 - 127.68	0.02 98.03 90.26 - 190.87	0.00 - 174.88 - 358.27	0.00 - 344.76 - 344.76
SBNDM-W2	0.02 7.75 4.57 - 18.43	0.01 7.16 3.87 - 20.42	0.01 5.50 2.46 - 13.08	0.02 3.15 1.70 - 6.21	0.02 1.69 0.99 - 3.49	0.02 1.82 0.99 - 4.15	0.01 1.49 0.95 - 3.33	0.02 1.88 0.94 - 3.13	0.02 1.85 0.98 - 3.42	0.02 2.18 0.99 - 4.09	0.01 1.53 0.97 - 3.30	0.02 1.66 0.99 - 3.37
WFR2	0.07 8.70 5.16 - 22.67	0.06 6.24 3.21 - 14.85	0.06 3.64 1.50 - 10.08	0.06 2.33 1.23 - 6.15	0.06 1.61 0.95 - 3.32	0.07 1.36 0.72 - 2.42	0.07 0.99 0.63 - 2.11	0.08 1.12 0.60 - 1.90	0.07 1.04 0.65 - 2.10	0.00 - 1.69 - 580.19	0.00 - 976.30 - 976.30	0.00 - 999.00 - 1951.59
TWFRQ2	0.07 8.18 4.83 - 18.11	0.06 5.90 3.15 - 15.76	0.06 3.20 1.47 - 9.07	0.06 2.20 1.29 - 4.74	0.08 1.84 0.91 - 3.20	0.07 1.12 0.69 - 2.50	0.07 0.95 0.60 - 2.20	0.07 1.07 0.58 - 1.94	0.07 1.06 0.64 - 1.94	0.00 - 0.66 - 508.30	0.00 - 999.00 - 1191.10	0.00 - 999.00 - 1928.16
TWFRQ4	0.02 2.86 1.42 - 4.89	0.06 3.44 2.60 - 9.13	0.06 3.08 1.15 - 8.09	0.07 1.90 1.06 - 4.51	0.07 1.25 0.70 - 2.60	0.07 1.02 0.58 - 1.94	0.08 1.06 0.55 - 1.85	0.07 0.89 0.55 - 1.82	0.08 1.12 0.64 - 1.88	0.00 - 0.69 - 391.32	0.00 - 698.94 - 698.94	0.00 - 999.00 - 1380.98
WOM	0.02 10.15 4.39 - 23.82	0.02 6.98 3.71 - 19.37	0.02 5.96 2.64 - 16.92	0.02 7.14 2.45 - 27.91	0.02 5.99 1.78 - 14.43	0.02 5.21 1.92 - 12.19	0.02 4.71 1.70 - 10.53	0.02 4.70 1.71 - 11.89	0.03 4.59 1.56 - 9.57	0.03 3.92 1.50 - 8.63	0.03 3.60 1.52 - 7.23	0.05 3.87 1.46 - 7.22
LIBC1	0.01 7.93 4.06 - 13.15	0.01 8.66 4.74 - 20.39	0.01 4.31 1.80 - 12.87	0.01 4.25 1.37 - 9.69	0.01 4.24 1.16 - 9.76	0.01 3.88 1.17 - 9.15	0.01 3.80 1.06 - 10.66	0.01 4.34 1.20 - 9.29	0.01 10.46 1.86 - 21.34	0.01 9.89 1.55 - 21.54	0.01 9.38 1.75 - 21.73	0.01 10.36 1.37 - 22.34
MUSL1	0.00 0.01 0.00 - 0.04	0.00 0.01 0.01 - 0.03	0.00 0.01 0.01 - 0.09	0.00 0.56 0.01 - 8.69	0.00 4.55 0.02 - 18.25	0.01 4.50 0.03 - 20.27	0.01 4.76 0.02 - 21.42	0.01 5.58 0.02 - 19.44	0.01 5.59 0.05 - 21.68	0.02 4.71 0.04 - 22.29	0.04 5.17 0.06 - 19.65	0.09 5.76 0.14 - 22.17
SIMDKR	0.01 1.83 1.30 - 5.01	0.01 3.35 2.34 - 8.61	0.01 2.25 1.60 - 6.44	0.01 2.84 1.61 - 5.88	0.01 2.85 1.57 - 6.60	0.01 2.57 1.45 - 5.54	0.01 2.14 1.43 - 5.39	0.01 2.41 1.44 - 12.52	0.02 2.94 1.44 - 6.92	0.01 2.60 1.45 - 5.25	0.02 2.82 1.45 - 6.18	0.02 2.84 1.45 - 6.01
EPSM	0.01 0.84 0.50 - 1.84	0.01 0.76 0.52 - 2.07	0.01 2.49 1.76 - 6.79	0.02 1.10 0.70 - 2.47	0.02 0.94 0.57 - 1.90	0.03 0.89 0.50 - 1.61	0.03 0.78 0.50 - 1.54	0.05 1.09 0.54 - 1.96	0.08 1.21 0.57 - 1.74	0.10 0.99 0.60 - 1.78	0.22 1.19 0.65 - 2.18	0.51 1.54 0.79 - 2.50

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.