15
\$\begingroup\$

While profiling parts of my code, I noticed that my Split( ... ) function is rather slow, (about 50% of the time). I was wondering if there was a more efficient way of Splitting a string into a vector.

My subject string can be anything between 2 words to well over 1000 words, hence the reason why I would like to speed it up.

Here is an example program with the function.

#include <iostream>
#include <string>
#include <cstring>
#include <vector>

void Split(const std::string& subject, std::vector<std::string>& container)
{
  container.clear();
  size_t len = subject.length() + 1;
  char* s = new char[ len ];
  memset(s, 0, len*sizeof(char));
  memcpy(s, subject.c_str(), (len - 1)*sizeof(char));
  for (char *p = strtok(s, " "); p != NULL; p = strtok(NULL, " "))
  {
    container.push_back( p );
  }
  delete[] s;
}

int main()
{
  std::vector<std::string> container;
  Split( "Hello World", container );

  for( std::vector<std::string>::const_iterator it = container.begin(); it != container.end();++it)
  {
    std::cout << *it << "!\n";
  }
}

Any suggestions on how I could speed it up.

Of course any other general comments are more than welcome.

Edit profiling is very simple.

...
clock_t t = clock (); 
std::vector<std::string> container;
Split( "actus non facit reum nisi mens sit rea", container );
t = clock() - t;
std::cout << (((float)t)/CLOCKS_PER_SEC) << "ms\n";
...
\$\endgroup\$
  • 5
    \$\begingroup\$ @πάνταῥεῖ: I agree that strtok() is not a good choice, but please remember to Be Nice! \$\endgroup\$ – Edward Apr 2 '17 at 16:05
  • 5
    \$\begingroup\$ If strtok(...) is bad, what should I use? Sorry if this is offensive code, but it is kind of the reason why I am asking for a review. \$\endgroup\$ – Simon Goodman Apr 2 '17 at 16:16
  • 2
    \$\begingroup\$ @SimonGoodman There's so many material available about that topic that it sheds a bad light upon you regardinng your research efforts. Hence why I downvoted your question. \$\endgroup\$ – πάντα ῥεῖ Apr 2 '17 at 16:27
  • 3
    \$\begingroup\$ No, please do ask for reviews here - we might not all be extremely polite about it, but we do mean well, and we wish to help you create the "perfect code", insofar as much as it exists :) \$\endgroup\$ – Tamoghna Chowdhury Apr 2 '17 at 20:08
  • 2
    \$\begingroup\$ Considering πάντα ῥεῖ didn't actually explain why strtok is considered to be 'bad' and instead just supplied an example of a good C++ way to split strings, I'll attempt to explain why strtok is considered to be 'bad'. Firstly the fact strtok modifies its first argument is somewhat frowned upon (as are most functions that modify their arguments). Secondly it can't be used on const char*s. And lastly (and most importantly) it's not thread safe. If strtok is used on more than one thread, things will break. \$\endgroup\$ – Pharap Apr 3 '17 at 7:10
17
\$\begingroup\$

I haven't attempted to measure the timing of this, in part because I don't know how you're planning to use it, but here are some ideas for improving your code.

Consider returning something useful from functions

Your Split function doesn't return anything, which isn't an error, but it's an odd design. I'd expect it to be declared like this instead:

std::vector<std::string> Split(const std::string& subject)

Understand sizeof

The sizeof operator is defined as always returning 1 for sizeof(char), so having that expression as part of your code probably isn't useful.

Use "range for" to simplify your code

The code to print the vector could be made much simpler and shorter by using a "range for" that was introduced in C++11:

for(const auto &item : container) {
    std::cout << item << "!\n";
}

Use standard library algorithms

I'd be inclined to write this using C++ rather than C functions. One way to do this is to use std::copy and std::stringstream:

std::vector<std::string> Split(const std::string& subject)
{
    std::istringstream ss{subject};
    using StrIt = std::istream_iterator<std::string>;
    std::vector<std::string> container{StrIt{ss}, StrIt{}};
    return container;
}

I've also been playing with std::sregex_token_iterator lately. Here's how that might look:

std::vector<std::string> Split(const std::string& subject) {
    static const std::regex re{"\\s+"};
    std::vector<std::string> container{
        std::sregex_token_iterator(subject.begin(), subject.end(), re, -1), 
        std::sregex_token_iterator()
    };
    return container;
}
\$\endgroup\$
  • 3
    \$\begingroup\$ Just to add: the resulting vector probably won't trigger copy constructor on return, but will probably be constructed in the destination. Also, return {...} would help on triggering RVO, while current code probably triggers NRVO. Even if neither of above happens, move constructor will kick in. Copying probably won't be slow, but depending on implementation it could decrease throughput. \$\endgroup\$ – Incomputable Apr 2 '17 at 16:39
  • \$\begingroup\$ Thanks for the response, isn't std::vector<std::string> Split(const std::string& subject) slower than void Split(const std::string& subject, std::vector<std::string> container) because of the copying that happens in the return? \$\endgroup\$ – Simon Goodman Apr 2 '17 at 16:43
  • 2
    \$\begingroup\$ @SimonGoodman, I placed the comment above, since I knew you will ask that! RVO and NRVO are return value optimization and named return value optimization. Both of them elide a copy, e.g. construct the result right into the call site. Move constructor is also really cheap and fast. \$\endgroup\$ – Incomputable Apr 2 '17 at 16:43
  • 1
    \$\begingroup\$ Yes, as @Incomputable has already said, many modern C++ compilers do "return value optimization" (RVO) which allows them to skip the actual copy. All the compilers I use (clang, gcc, MSVC++) apply this optimization. You can test yours by looking at the generated assembly code. \$\endgroup\$ – Edward Apr 2 '17 at 16:46
  • 1
    \$\begingroup\$ @Edward: Note that a compiler doesn't have to be particularly modern to do RVO/NRVO. Just for example, VC++ 6 could do it, despite predating the original 1998 C++ standard. \$\endgroup\$ – Jerry Coffin Apr 2 '17 at 19:55
7
\$\begingroup\$

Avoid unnecessary dynamic allocations

Right now, you're dynamically allocating memory, and copying the input data into that dynamically allocated buffer, almost exclusively so you can use strtok to do the tokenizing.

Avoid unnecessary work

You're also zeroing that entire block of dynamically allocated memory, then immediately copying the data from the input over the zeros you just wrote into the block.

If you're going to mess with something like this at all, you can probably speed it up at least a little just by avoiding that unnecessary zeroing.

auto *s = new char [strlen(input)+1];
strcpy(s, input);

Get from input to output as directly as possible

I'd rather avoid that amount of copying, and create results directly from the input data instead, something like this:

std::vector<std::string> tokenize(std::string const &in) {
    char sep = ' ';
    std::string::size_type b = 0;
    std::vector<std::string> result;

    while ((b = in.find_first_not_of(sep, b)) != std::string::npos) {
        auto e = in.find_first_of(sep, b);
        result.push_back(in.substr(b, e-b));
        b = e;
    }
    return result;
}

Although it's difficult to be certain without profiling, my guess is that this has less overhead than using a stringstream or a regex token iterator to do the job. A heavily optimized regex library might get pretty close (possibly even close enough to make differences irrelevant). stringstreams can make for neat code, so as long as you don't care about the overhead, they're often an excellent choice--but at a guess, using a stringstream is going to end up slower than your current code.

Consider using string_view instead of string

If you can afford to restrict your code to C++17 (or later), consider using a string_view for the input, rather than an std::string. A string_view gives you string-like access to some data, but without actually storing that data in the string_view object itself. At least in the typical implementation, it stores only the location and length of the data.

The same principle can be applied to the result: instead of each result being a string that holds a copy of the data from the input, you might be able to use a string_view that holds only a location and length for each. This can be a little tricky though. In particular, it makes you responsible for lifetime issues--since you're storing references to the original input data, you need to ensure that the original input data remains valid for as long as you might use the tokens you've created from that input. In your case (string literals) that's pretty trivial (they have static storage duration, so they're always valid). For real use, where you're tokenizing some string that came from user input, it may be more difficult (but if you can do it, it can be a substantial win).

Be sure you're using a current standard library

Many older implementations of the standard library used implementations of std::string that always allocated storage for the string's data dynamically. This typically means creating a string has a fairly substantial amount of overhead, regardless of its size.

More recent implementations of the standard library typically use what's called a "short string optimization". This means they allocate enough storage for a short string (for some arbitrary definition of short, but usually around 16-32 characters) inside the string object itself. This avoids a dynamic allocation for the buffer space when you're storing lots of small strings (e.g., your result tokens/words, probably). The speed difference can be pretty dramatic (I've seen around 10:1 pretty routinely).

\$\endgroup\$
  • \$\begingroup\$ I considered suggesting creating an array of pointers, but that's both ugly and dangerous, so I decided not. Your std::string_view is a much better way of accomplishing something like that. \$\endgroup\$ – Edward Apr 2 '17 at 19:08
  • \$\begingroup\$ @Edward: Yeah, I think they did a nice piece of work there--almost as "lean" as a bare pointer, but also almost as safe as a full-blown string. \$\endgroup\$ – Jerry Coffin Apr 2 '17 at 19:12
  • \$\begingroup\$ Since you can construct a std::string from a pair of input iterators, I think you could use result.emplace_back(b, e) instead of explicitly calling in.substr(). It shouldn't be any faster (as the substring result is an rvalue, and so movable), but is a little clearer (IMHO). \$\endgroup\$ – Toby Speight Apr 27 '17 at 10:40
  • \$\begingroup\$ One improvement this code has over the original (and that you didn't mention): it now works when the input string contains NUL characters. The question code would stop at the first NUL, due to strtok() treating that as end-of-string. \$\endgroup\$ – Toby Speight Apr 27 '17 at 10:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.