CODEWITHSUNDEEP
c++visual-c++
Jari666
Jari666

Reputation: 73

Fast method to check for substrings

I'm currently programming a chat system based on a server - client model and using TCP as the communication protocol. Although it's working as expected, I'd like to further optimize important parts on the server side.

The server uses four extra threads to handle new connections, console input, etc, without blocking normal chat conversations. Well, there is only one thread for all messages that are being sent from client to client, so I assume it would be good to optimize the code there, as it would be the most obvious bottleneck. After reading the data on each client's socket, the data has to be processed using different steps. One of those steps would be to check for blocked words. And that's where my original question starts.

I played with std::string::find() and the strstr() function. According to my tests, std::string::find() was clearly faster than the old C-style strstr() function.

I know that the std::string is very well optimized, but C-style char arrays and their own functions always seemed to be somewhat faster, especially if the string has to be constructed over and over again.

So, is there anything faster than std::string::find() to scan a series of characters for blocked words? Is std::string::find() faster than strstr(), or are my benchmarks lousy? I know that the gain may be negligigle compared to effort needed to keep C-style char arrays and their functions clean, but I'd like to keep it as fast as possible, even if it is just for testing purposes.

EDIT: Sorry, forgot to mention that I am using MSVC++2010 Express. I am only targeting Windows machines.

Upvotes: 4

Views: 357

Answers (3)

mirk
mirk

Reputation: 5520

There exist faster searching-algorithms than the linear search typically used in STL, or strstr.

Boyer-Moore is quite popular. It requires preprocessing of the target-string, which should be feasible for your usecase.

Exact string matching algorithms is a free e-book with an in-depth description of different search-algorithms and their tradeofs.

Implementing more advanced algorithms could take considerable effort. As said in the other answers, It is doubtful that string-searching is a bottle-neck in your chat-server.

Upvotes: 1

Moishe Lettvin
Moishe Lettvin

Reputation: 8471

Have you benchmarked to verify that lots of time is in fact being taken in the check for blocked words? My completely naive guess is you're gonna be spending lots more time waiting for RPCs than any local processing...

Upvotes: 4

Ayjay
Ayjay

Reputation: 3433

Have you tried the regular expressions library in either C++11 if you use that, or Boost if you don't? I'm not sure about the speed, but I believe they perform quite well. Additionally, if you are using this as a form of profanity filter, you'd want regular expressions anyway to prevent trivial circumvention.

Upvotes: 2

Related Questions