std :: remove_if GCC实现效率不高？ [英] std::remove_if GCC implementation isn't efficient?

问题描述

来自​​此处的另一个问题似乎有证据表明，与以下实现相比，GCC对 std :: remove_if 的实施不能提供相同的效率：

'原生自制'解决方案：

  static char str1 [100] =str ,, ing; 
 size_t size = sizeof（str1）/ sizeof（str1 [0]）; 
 
 int bad = 0; 
 int cur = 0; （bad [cur&&！ispunct（str1 [cur]）&&！isspace（str1 [cur1！] ='\0'）{
 while（str1 [ cur]））{
 str1 [bad] = str1 [cur]; 
 
 if（ispunct（str1 [cur]）|| isspace（str1 [cur]））{
 cur ++; 
} else {
 cur ++; 
坏++; 
} 
} 
 str1 [bad] ='\0'; 
  

计时输出：

0.106860

为 std :: remove_if 提供一个解决同样问题的示例基准代码：

  bool is_char_category_in_question（const char& c）{
 return std :: ispunct（c）||的std :: isspace为（C）; 
} 
 
 std :: remove_if（& str1 [0]，& str1 [size-1]，is_char_category_in_question）; 
  

计时输出：

1.986838

请检查并获取运行上述ideone链接的代码的实际运行时结果（请在此提供完整的代码）。

考虑到提供的执行时间结果（来自示例），这些似乎证实了第一个实现具有更好的性能。

任何人都可以说出理由，为什么 std :: remove_if（）算法没有（或不能）提供类似的对于给定的问题有效的解决方案？

解决方案

看起来好像你正在运行 remove_if size 为100个字符后，code>在100个字符范围内，但homebrew会一直运行，直到找到nul终止符（只有10个字符）。

使用下面评论中的更改处理此问题，在使用-O2的GCC上我仍然看到不同约为2倍， remove_if 变慢。改为：

$ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $ $返回std :: ispunct（c）||的std :: isspace为（C）;
}
};

几乎消除了所有这种差异，尽管可能仍有<10％的差异。因此，这看起来像是一个实施质量问题，不管测试是否被内联，尽管我没有检查程序集来确认。

由于您的测试线束意味着第一遍之后没有字符被删除，我不会为10％的差异感到困扰。我有点惊讶，但还不足以真正进入。 YMMV： - ）

From another question here there seems to be evidence, that GCC's implementation of std::remove_if doesn't provide equally efficiency compared to the following implementation:

'raw homebrew' solution:

static char str1[100] = "str,, ing";
size_t size = sizeof(str1)/sizeof(str1[0]);

int bad = 0;
int cur = 0;
while (str1[cur] != '\0') {
    if (bad < cur && !ispunct(str1[cur]) && !isspace(str1[cur])) {
        str1[bad] = str1[cur];
    }
    if (ispunct(str1[cur]) || isspace(str1[cur])) {
        cur++;
    } else {
        cur++;
        bad++;
    }
}
str1[bad] = '\0';

Timing outputs:

0.106860

Sample benchmarking code for std::remove_if for a solution of the same problem:

bool is_char_category_in_question(const char& c) {
    return std::ispunct(c) || std::isspace(c);
}

std::remove_if(&str1[0], &str1[size-1], is_char_category_in_question);

Timing outputs:

1.986838

Check and get actual runtime results for the code running the ideone links above please (giving the full codes here would obscure the question!).

Given the provided execution time results (from the samples), these seem to confirm the first implementation is having much better performance.

Can anyone tell reasons, why the std::remove_if() algorithm doesn't (or can't) provide a similarly efficient solution for the given problem?

解决方案

Looks to me as though you're running remove_if on a range of 100 characters since size is 100, but the "homebrew" runs until you find the nul terminator (which is only 10 characters in).

Dealing with that using the change in your comment below, on GCC with -O2 I still see a difference of about a factor of 2, with remove_if being slower. Changing to:

struct is_char_category_in_question {
    bool operator()(const char& c) const {
        return std::ispunct(c) || std::isspace(c);
    }
};

gets rid of almost all of this difference, although there may still be a <10% difference. So that looks to me like a quality of implementation issue, whether or not the test gets inlined although I haven't checked the assembly to confirm.

Since your test harness means that no characters are actually removed after the first pass, I'm not troubled by a 10% difference. I'm a bit surprised, but not enough to really get into it. YMMV :-)

这篇关于std :: remove_if GCC实现效率不高？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！