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:07:56

Text rand128 (alphabet : 128 - size : 1048576 bytes)

248163264128256512102420484096
TVSBS
4.61
3.74
2.99
2.02
1.73
1.59
1.69
1.84
1.61
1.53
1.35
1.23
FJS
3.45
3.11
2.07
1.61
1.45
1.27
1.21
1.22
1.32
1.39
1.27
1.30
HASH8
2.74
3.32
20.07
2.97
1.72
1.34
1.25
1.24
1.43
1.45
1.39
1.41
SO
2.98
3.07
2.97
2.94
2.56
2.14
2.41
2.46
2.32
2.27
2.45
2.50
SBNDM
3.60
1.96
1.43
1.20
1.09
1.19
1.34
1.25
1.16
1.34
1.26
1.24
LBNDM
2.14
2.03
1.47
1.26
1.27
1.28
1.19
1.12
1.02
1.04
1.01
1.01
SBNDM2
2.31
1.62
1.34
1.16
1.08
1.06
1.08
1.08
1.15
1.11
1.09
1.14
SBNDM-BMH
3.21
2.35
1.80
1.57
1.31
1.23
1.29
1.37
1.31
1.19
1.34
1.34
FNDM
2.26
1.95
1.45
1.25
1.26
1.22
1.26
1.29
1.26
1.12
1.26
1.30
FSBNDM
1.68
1.43
1.25
1.16
1.03
1.12
1.12
1.02
1.10
1.14
1.13
1.12
SBNDMQ8
3.05
3.20
7.09
1.77
1.21
1.37
1.29
1.23
1.26
1.28
1.33
1.31
UFNDMQ2
1.87
1.81
1.31
1.17
1.10
1.15
1.15
1.16
1.15
1.12
1.06
1.08
UFNDMQ8
2.56
2.97
1.84
1.33
1.40
1.34
1.44
1.30
1.32
1.35
1.36
1.27
KBNDM
4.57
2.84
1.80
1.36
1.25
1.31
1.17
1.17
1.17
1.07
1.20
1.16
FS-W2
2.75
1.99
1.56
1.24
1.23
1.20
1.19
1.14
1.22
1.28
1.31
1.21
LWFR5
2.45
3.40
4.43
1.47
1.32
1.14
1.23
1.24
1.09
1.15
1.09
1.08
QF43
2.85
3.03
1.56
1.20
1.15
1.04
1.16
1.17
1.02
0.91
0.94
0.95
SBNDM-W2
2.16
1.72
1.37
1.19
1.16
1.24
1.09
1.23
1.18
1.16
1.10
1.11
WFR2
3.47
1.90
1.59
1.33
1.14
1.18
1.16
1.20
1.17
1.12
1.01
1.16
TWFRQ2
2.82
1.73
1.47
1.21
1.23
1.12
1.19
1.24
1.08
1.09
0.92
1.03
TWFRQ4
3.15
3.48
1.56
1.22
1.24
1.16
1.22
1.11
1.16
1.01
0.99
1.08
WOM
4.40
2.99
2.25
1.66
1.24
1.30
1.20
1.15
1.16
1.19
1.26
1.25
LIBC1
2.59
1.77
1.38
1.31
1.10
1.14
1.14
1.23
1.22
1.31
1.31
1.31
MUSL1
0.05
1.17
0.74
0.68
0.62
0.60
0.58
0.62
0.64
0.59
0.62
0.75
SIMDKR
1.07
1.20
1.08
1.10
1.10
1.11
1.10
1.16
1.15
1.16
1.09
1.15
EPSM
1.20
1.21
1.25
1.35
1.18
1.15
1.17
1.25
1.17
1.15
1.26
1.57
Table 1. Running times of experimental tests n.EXP1712145140. Each time value is the mean of 500 runs. Running times are in milliseconds.

Average Running Times
[No canvas support]
TVSBS
FJS
HASH8
SO
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
[No canvas support]
Best Running Times
[No canvas support]
TVSBS - Thathoo-Virmani-Sai-Balakrishnan-Sekar
[No canvas support]
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
[No canvas support]
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)
[No canvas support]
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
[No canvas support]
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
[No canvas support]
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
[No canvas support]
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
[No canvas support]
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
[No canvas support]
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
[No canvas support]
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
[No canvas support]
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
[No canvas support]
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
[No canvas support]
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
[No canvas support]
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
[No canvas support]
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
[No canvas support]
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
[No canvas support]
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
[No canvas support]
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
[No canvas support]
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)
[No canvas support]
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
[No canvas support]
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
[No canvas support]
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
[No canvas support]
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
[No canvas support]
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
[No canvas support]
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
[No canvas support]
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
[No canvas support]
Detailed plot of the running times relative to the EPSM algorithm. The plot reports the mean and the distribution of the running times.