[C++] C++11 Signature Scanning

[atom0s]

Originally Posted by Carbon

I think both your implementations are still not perfect. Think about this: https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
or at least
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm
This algorithm is even more efficient for byte search. Skip as many bytes as possible...

Yeah there is a lot of room for improvement. My method was more aimed towards making use of C++11 features (to try them out and such) as well as being more maintainable as well as async which I needed for my project that I use it in.

Implementing Boyer Moore will definitely be a bit faster though.

Comparing my FindPattern to the original posted above, mine sees a lot of improvement when the data being scanned within is large and the number of scans being done is high. For low amounts of scanning and where async is not required, then the original will tend to outperform mine.

Overall it really depends on some specific factors:
- The data size being scanned within.
- The number of patterns being looked for.
- Threading; is it required or not, (along with thread-safety).
- Hardware can land up playing a roll as well etc.

Another implementation that could make use of different hardware would be a GPU implementation, which could also have a handful of speed benefits depending on similar factors above.

[Nukem]

Originally Posted by atom0s

Yeah there is a lot of room for improvement. My method was more aimed towards making use of C++11 features (to try them out and such) as well as being more maintainable as well as async which I needed for my project that I use it in.

Implementing Boyer Moore will definitely be a bit faster though.

Actually a couple of those methods have been tested here: https://github.com/learn-more/findpattern-bench

BMH was second place when I checked (57ms):

FindPattern benchmark
Page size: 4096, allocating 22 pages (including 2 guard pages).
Running tests on 9 different implementations
===========
Running M-i-K-e
ran outside the area
FAILED
===========
Running Trippeh
Finding pattern 0 x 1000 took 1774.23 ms.
Finding pattern 1 x 1000 took 1905.49 ms.
===========
Running Trippeh v2
Finding pattern 0 x 1000 took 81.864 ms.
Finding pattern 1 x 1000 took 81.937 ms.
===========
Running Trippeh v3
Failed, cheating with the pattern length!
FAILED
===========
Running learn_more
Finding pattern 0 x 1000 took 204.665 ms.
Finding pattern 1 x 1000 took 164.068 ms.
===========
Running learn_more v2
Finding pattern 0 x 1000 took 82.226 ms.
Finding pattern 1 x 1000 took 82.679 ms.
===========
Running afffsdd
Finding pattern 0 x 1000 took 40.943 ms.
Finding pattern 1 x 1000 took 40.968 ms.
===========
Running DarthTon
Finding pattern 0 x 1000 took 56.974 ms.
Finding pattern 1 x 1000 took 57.045 ms.
===========
Running kokole
Finding pattern 0 x 1000 took 122.41 ms.
Finding pattern 1 x 1000 took 122.646 ms.
Done.
Press any key to continue . . .

Although it really does depend on what you're scanning/how long it is. I prefer a linear search because the code is shorter and it's still pretty fast.