Alternatives to standard functions of C++ to get speed optimization

Question

Just to clarify that I also think the title is a bit silly. We all know that most built-in functions of the language are really well written and fast (there are ones even written by assembly). Though may be there still are some advices for my situation. I have a small project which demonstrates the work of a search engine. In the indexing phase, I have a filter method to filter out unnecessary things from the keywords. It's here:

bool Indexer::filter(string &keyword)
{
    // Remove all characters defined in isGarbage method
    keyword.resize(std::remove_if(keyword.begin(), keyword.end(), isGarbage) - keyword.begin());

    // Transform all characters to lower case
    std::transform(keyword.begin(), keyword.end(), keyword.begin(), ::tolower);

    // After filtering, if the keyword is empty or it is contained in stop words list, mark as invalid keyword
    if (keyword.size() == 0 || stopwords_.find(keyword) != stopwords_.end())
        return false;

    return true;
}

At first sign, these functions (alls are member functions of STL container or standard function) are supposed to be fast and not take many time in the indexing phase. But after profiling with Valgrind, the inclusive cost of this filter is ridiculous high: 33.4%. There are three standard functions of this filter take most of the time for that percentage: std::remove_if takes 6.53%, std::set::find takes 15.07% and std::transform takes 7.71%.

So if there are any thing I can do (or change) to reduce the instruction times cost by this filter (like using parallellizing or something like that), please give me your advice. Thanks in advance.

UPDATE: Thanks for all your suggestion. So in brief, I've summarize what I need to do is: 1) Merge tolower and remove_if into one by construct my own loop. 2) Use unordered_set instead of set for faster find method. Thus I've chosen Mark_B's as the right answer.

Answer 1

You might make this faster by making a single pass through the string, ignoring the garbage characters. Something like this (pseudo-code):

std::string normalizedKeyword;
normalizedKeyword.reserve(keyword.size())
for (auto p = keyword.begin(); p != keyword.end(); ++p)
{
    char ch = *p;
    if (!isGarbage(ch))
        normalizedKeyword.append(tolower(ch));
}

// then search for normalizedKeyword in stopwords

This should eliminate the overhead of std::remove_if, although there is a memory allocation and some new overhead of copying characters to normalizedKeyword.

Answer 2

If a call to isGarbage() does not require synchronization, then parallelization should be the first optimization to consider (given of course that filtering one keyword is a big enough task, otherwise parallelization should be done one level higher). Here's how it could be done - in one pass through the original data, multi-threaded using Threading Building Blocks:

    bool isGarbage(char c) {
    return c == 'a';
}

struct RemoveGarbageAndLowerCase {
    std::string result;
    const std::string& keyword;

    RemoveGarbageAndLowerCase(const std::string& keyword_) : keyword(keyword_) {}

    RemoveGarbageAndLowerCase(RemoveGarbageAndLowerCase& r, tbb::split) : keyword(r.keyword) {}

    void operator()(const tbb::blocked_range<size_t> &r) {
        for(size_t i = r.begin(); i != r.end(); ++i) {
            if(!isGarbage(keyword[i])) {
                result.push_back(tolower(keyword[i]));
            }
        }
    }

    void join(RemoveGarbageAndLowerCase &rhs) {
        result.insert(result.end(), rhs.result.begin(), rhs.result.end());
    }
};

void filter_garbage(std::string &keyword) {
    RemoveGarbageAndLowerCase res(keyword);
    tbb::parallel_reduce(tbb::blocked_range<size_t>(0, keyword.size()), res);
    keyword = res.result;
}

int main() {
    std::string keyword = "ThIas_iS:saome-aTYpe_Ofa=MoDElaKEYwoRDastrang";

    filter_garbage(keyword);

    std::cout << keyword << std::endl;

    return 0;
}

Of course, the final code could be improved further by avoiding data copying, but the goal of the sample is to demonstrate that it's an easily threadable problem.

Answer 3

If you use a boost filter iterator you can merge the remove_if and transform into one, something like (untested):

keyword.erase(std::transform(boost::make_filter_iterator(!boost::bind(isGarbage), keyword.begin(), keyword.end()),
                             boost::make_filter_iterator(!boost::bind(isGarbage), keyword.end(), keyword.end()),
                             keyword.begin(),
                            ::tolower), keyword.end());

This is assuming you want the side effect of modifying the string to still be visible externally, otherwise pass by const reference instead and just use count_if and a predicate to do all in one. You can build a hierarchical data structure (basically a tree) for the list of stop words that makes "in-place" matching possible, for example if your stop words are SELECT, SELECTION, SELECTED you might build a tree:

|- (other/empty accept)
\- S-E-L-E-C-T- (empty, fail)
             |- (other, accept)
             |- I-O-N (fail)
             \- E-D (fail)

You can traverse a tree structure like that simultaneously whilst transforming and filtering without any modifications to the string itself. In reality you'd want to compact the multi-character runs into a single node in the tree (probably).

You can build such a data structure fairly trivially with something like:

#include <iostream>
#include <map>
#include <memory>

class keywords {
  struct node {
        node() : end(false) {}
    std::map<char, std::unique_ptr<node>> children;
        bool end;
  } root;

  void add(const std::string::const_iterator& stop, const std::string::const_iterator c, node& n) {
    if (!n.children[*c])
      n.children[*c] = std::unique_ptr<node>(new node);

    if (stop == c+1) {
      n.children[*c]->end = true;
      return;
    }
    add(stop, c+1, *n.children[*c]);
  }
public:
  void add(const std::string& str) {
    add(str.end(), str.begin(), root);
  }

  bool match(const std::string& str) const {
    const node *current = &root;
    std::string::size_type pos = 0;
    while(current && pos < str.size()) {
      const std::map<char,std::unique_ptr<node>>::const_iterator it = current->children.find(str[pos++]);
      current = it != current->children.end() ? it->second.get() : nullptr;
    }
    if (!current) {
      return false;
    }
    return current->end;
  }
};

int main() {
  keywords list;
  list.add("SELECT");
  list.add("SELECTION");
  list.add("SELECTED");
  std::cout << list.match("TEST") << std::endl;
  std::cout << list.match("SELECT") << std::endl;
  std::cout << list.match("SELECTOR") << std::endl;
  std::cout << list.match("SELECTED") << std::endl;
  std::cout << list.match("SELECTION") << std::endl;
}

This worked as you'd hope and gave:

0
1
0
1
1

Which then just needs to have match() modified to call the transformation and filtering functions appropriately e.g.:

const char c = str[pos++];
if (filter(c)) {
  const std::map<char,std::unique_ptr<node>>::const_iterator it = current->children.find(transform(c));
}

You can optimise this a bit (compact long single string runs) and make it more generic, but it shows how doing everything in-place in one pass might be achieved and that's the most likely candidate for speeding up the function you showed.

(Benchmark changes of course)

Answer 4

Here's a way to combine the garbage removal and lower-casing into a single step. It won't work for multi-byte encoding such as UTF-8, but neither did your original code. I assume 0 and 1 are both garbage values.

bool Indexer::filter(string &keyword)
{
    static char replacements[256] = {1}; // initialize with an invalid char
    if (replacements[0] == 1)
    {
        for (int i = 0;  i < 256;  ++i)
            replacements[i] = isGarbage(i) ? 0 : ::tolower(i);
    }
    string::iterator tail = keyword.begin();
    for (string::iterator it = keyword.begin();  it != keyword.end();  ++it)
    {
        unsigned int index = (unsigned int) *it & 0xff;
        if (replacements[index])
            *tail++ = replacements[index];
    }
    keyword.resize(tail - keyword.begin());

    // After filtering, if the keyword is empty or it is contained in stop words list, mark as invalid keyword
    if (keyword.size() == 0 || stopwords_.find(keyword) != stopwords_.end())
        return false;

    return true;
}

The largest part of your timing is the std::set::find so I'd also try std::unordered_set to see if it improves things.

Answer 5

The problem here isn't the standard functions, it's your use of them. You are making multiple passes over your string when you obviously need to be doing only one.

What you need to do probably can't be done with the algorithms straight up, you'll need help from boost or rolling your own.

You should also carefully consider whether resizing the string is actually necessary. Yeah, you might save some space but it's going to cost you in speed. Removing this alone might account for quite a bit of your operation's expense.

Answer 6

I would implement it with lower level C functions, something like this maybe (not checking this compiles), doing the replacement in place and not resizing the keyword.

1. Instead of using a set for garbage characters, I'd add a static table of all 256 characters (yeah, it will work for ascii only), with 0 for all characters that are ok, and 1 for those who should be filtered out. something like:

static const char GARBAGE[256] = { 1, 1, 1, 1, 1, ...., 0, 0, 0, 0, 1, 1, ... };

then for each character in offset pos in const char *str you can just check if (GARBAGE[str[pos]] == 1);

this is more or less what an unordered set does, but will have much less instructions. stopwords should be an unordered set if they're not.

now the filtering function (I'm assuming ascii/utf8 and null terminated strings here):

bool Indexer::filter(char *keyword)
{

    char *head = pos;
    char *tail = pos;

    while (*head != '\0') {
        //copy non garbage chars from head to tail, lowercasing them while at it
        if (!GARBAGE[*head])  {
           *tail = tolower(*head);
           ++tail; //we only advance tail if no garbag
        }
        //head always advances
        ++head;
    }
    *tail = '\0';

    // After filtering, if the keyword is empty or it is contained in stop words list, mark as invalid keyword
    if (tail == keyword || stopwords_.find(keyword) != stopwords_.end())
        return false;


    return true;
}

Answer 7

First, are you certain that optimization and inlining are enabled when you compile?

Assuming that's the case, I would first try writing my own transformer that combines removing garbage and lower-casing into one step to prevent iterating over the keyword that second time.

There's not a lot you can do about the find without using a different container such as unordered_set as suggested in a comment.

Is it possible for your application that doing the filtering really just is a really CPU-intensive part of the operation?