Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- On Mon, 24 Feb 2014 10:43:10 -0800 (PST)
- Cooler_x0a <[email protected]> wrote:
- > So when i need find a "string" i use "strstr()", but this form not
- > seems better form...
- >
- > Some peoples talk me about bitap algorithm:
- > http://en.wikipedia.org/wiki/Bitap_algorithm
- >
- > Someone know another method to find string ?
- > (my priority of research is fast algorithms)
- >
- >
- > Cheers
- Well I have made small benchmark of different substring search
- algorithms and in general case best performers are SSE42 pcmpistri
- pcmpestri instructions with brute force search. strstr and memmem are
- pretty good, too. (gcc)
- referent points are memmemopt which is optimized memmemsse2 (both in
- asm) and strstrasm which is naive brute force asm.
- strstrsse42 memmemsse42 are also asm routines that use sse42 string
- instructions.
- bmaxa@maxa:~/examples/assembler$ time ./strings
- haystack alice.html 202167, needle (added to end) "this has to be found" 20
- strstrsse42 0x7f0b697865cb 19.3
- strstr 0x7f0b697865cb 31.0
- memmemsse42 0x7f0b697865cb 38.6
- strcasestr 0x7f0b697865cb 43.2
- BM horspool 0x7f0b697865cb 58.2
- bmhorspoolasm 0x7f0b697865cb 61.0
- BM 0x7f0b697865cb 82.1
- BM Turbo 0x7f0b697865cb 86.7
- memmemsse2 0x7f0b697865cb 97.3
- memmemopt 0x7f0b697865cb 103.9
- strstrsse2 0x7f0b697865cb 106.2
- memmem2 0x7f0b697865cb 181.9
- memmem 0x7f0b697865cb 233.9
- strstrasm 0x7f0b697865cb 262.1
- string find 0x7f0b697865cb 270.1
- KMP 0x7f0b697865cb 483.3
- bitap 0x7f0b697865cb 5745.0
- haystack 1048576 random data, needle 1024 random data
- bmhorspoolasm (nil) 30.7
- BM horspool (nil) 31.1
- memmem (nil) 33.7
- BM (nil) 38.5
- BM Turbo (nil) 40.9
- strstrsse42 (nil) 61.2
- memmemopt (nil) 80.6
- memmemsse2 (nil) 89.9
- strstr (nil) 90.3
- strstrsse2 (nil) 102.2
- memmem2 (nil) 108.9
- strcasestr (nil) 141.8
- memmemsse42 (nil) 152.2
- string find (nil) 689.0
- strstrasm (nil) 827.9
- KMP (nil) 1414.8
- bitap (nil) 562742.6
- haystack 1048576 random data, needle 7 random data
- strstrsse42 (nil) 59.6
- memmemopt (nil) 80.9
- memmemsse2 (nil) 90.1
- memmem2 (nil) 99.8
- strstrsse2 (nil) 104.5
- memmemsse42 (nil) 151.3
- strstr (nil) 375.3
- BM horspool (nil) 464.0
- strcasestr (nil) 469.0
- bmhorspoolasm (nil) 477.1
- memmem (nil) 586.6
- BM Turbo (nil) 633.2
- BM (nil) 656.5
- string find (nil) 684.3
- strstrasm (nil) 825.2
- KMP (nil) 1410.8
- bitap (nil) 9032.7
- haystack 1048593 8 byte repeated pattern, needle 9 byte data (begins with pattern)
- strstrsse42 0x7f0b688f1030 345.0
- BM horspool 0x7f0b688f1030 396.8
- bmhorspoolasm 0x7f0b688f1030 410.5
- memmemsse42 0x7f0b688f1030 449.8
- memmem 0x7f0b688f1030 533.8
- BM Turbo 0x7f0b688f1030 543.6
- memmemsse2 0x7f0b688f1030 552.5
- BM 0x7f0b688f1030 564.7
- memmemopt 0x7f0b688f1030 573.1
- strstrsse2 0x7f0b688f1030 585.3
- strstr 0x7f0b688f1030 733.7
- memmem2 0x7f0b688f1030 760.7
- strcasestr 0x7f0b688f1030 910.5
- string find 0x7f0b688f1030 995.7
- strstrasm 0x7f0b688f1030 1677.3
- KMP 0x7f0b688f1030 2748.7
- bitap 0x7f0b688f1030 11363.7
- haystack 1048580 1 byte repeated pattern, needle 4 byte data (begins with pattern)
- strstrsse42 0x7f0b688f1028 393.4
- strstr 0x7f0b688f1028 462.4
- memmemsse42 0x7f0b688f1028 515.5
- memmem 0x7f0b688f1028 529.9
- strcasestr 0x7f0b688f1028 574.4
- memmemopt 0x7f0b688f1028 799.2
- bmhorspoolasm 0x7f0b688f1028 1787.4
- BM horspool 0x7f0b688f1028 3190.6
- KMP 0x7f0b688f1028 3380.5
- string find 0x7f0b688f1028 3449.8
- bitap 0x7f0b688f1028 3741.0
- strstrasm 0x7f0b688f1028 4052.4
- memmemsse2 0x7f0b688f1028 4443.1
- BM Turbo 0x7f0b688f1028 4501.4
- BM 0x7f0b688f1028 4565.5
- strstrsse2 0x7f0b688f1028 4681.0
- memmem2 0x7f0b688f1028 6867.1
- haystack 1048576 1 byte repeated pattern, needle 4 byte data (all fail)
- memmem2 (nil) 30.5
- memmem (nil) 32.2
- memmemopt (nil) 40.6
- memmemsse2 (nil) 44.8
- strstrsse42 (nil) 56.7
- strstrsse2 (nil) 62.4
- memmemsse42 (nil) 149.4
- strstr (nil) 383.7
- strcasestr (nil) 471.7
- string find (nil) 646.4
- strstrasm (nil) 793.4
- BM horspool (nil) 801.0
- bmhorspoolasm (nil) 805.7
- BM (nil) 1133.2
- BM Turbo (nil) 1326.4
- KMP (nil) 1328.3
- bitap (nil) 3114.4
- cumulative list by time
- strstrsse42 935.2
- memmemsse42 1456.8
- memmemopt 1678.2
- memmem 1950.2
- strstr 2076.4
- strcasestr 2610.6
- bmhorspoolasm 3572.6
- BM horspool 4941.6
- memmemsse2 5317.7
- strstrsse2 5641.5
- string find 6735.3
- BM 7040.5
- BM Turbo 7132.2
- memmem2 8048.9
- strstrasm 8438.3
- KMP 10766.4
- bitap 595739.5
- cumulative list by place
- strstrsse42 15
- memmemsse42 36
- memmemopt 37
- BM horspool 37
- memmem 38
- strstr 39
- bmhorspoolasm 40
- memmemsse2 44
- strcasestr 52
- memmem2 57
- strstrsse2 58
- BM Turbo 60
- BM 61
- string find 77
- strstrasm 82
- KMP 89
- bitap 96
Advertisement
Add Comment
Please, Sign In to add comment
