Почему '==' медленнее на std::string?

Ответ 1

UPDATE: выход улучшенного теста в http://ideone.com/rGc36a

==       took:21
.compare took:21
strcmp   took:14
==       took:21
.compare took:25
strcmp   took:14

То, что оказалось решающим для того, чтобы заставить его работать, было "перехитрить" способность компилятора предсказать сравнение строк во время компиляции:

// more strings that might be used...
string s[] = { {len,argc+'A'}, {len,argc+'A'}, {len, argc+'B'}, {len, argc+'B'} };

if(s[i&3].compare(s[(i+1)&3])==0)  // trickier to optimise
  a += i;  // cumulative observable side effects

Обратите внимание, что в общем случае strcmp не является функционально эквивалентным == или .compare, когда текст может вставлять NUL, так как первый будет "рано выйти". (Это не причина, по которой он "быстрее" выше, но читайте ниже для комментариев, повторите возможные варианты с длиной строки/содержанием и т.д.)

Обсуждение/более ранний ответ

Просто взгляните на свою реализацию - например,

echo '#include <string>' > stringE.cc
g++ -E stringE.cc | less

Найдите шаблон basic_string, затем для оператора ==, работающего с двумя экземплярами строки - mine:

template<class _Elem,
    class _Traits,
    class _Alloc> inline
    bool __cdecl operator==(
            const basic_string<_Elem, _Traits, _Alloc>& _Left,
            const basic_string<_Elem, _Traits, _Alloc>& _Right)
    {
    return (_Left.compare(_Right) == 0);
    }

Обратите внимание, что operator== является встроенным и просто вызывает compare. Там нет пути он последовательно значительно медленнее с нормальными уровнями оптимизации, хотя оптимизатор иногда может оптимизировать один цикл лучше другого из-за тонких побочных эффектов окружающего кода.

Ваша очевидная проблема будет вызвана, например, ваш код оптимизируется за пределами предполагаемой работы, for петли произвольно разворачиваются в разной степени или другие причуды или ошибки в оптимизации или в вашем времени. Это необычно, когда у вас есть неизменные входы и петли, которые не имеют каких-либо кумулятивных побочных эффектов (т.е. Компилятор может решить, что промежуточные значения a не используются, поэтому нужно использовать только последний a = i).

Итак, научись писать лучшие тесты. В этом случае это немного сложно, поскольку у них есть много разных строк в памяти, готовых вызвать сравнения, и выбирать их таким образом, чтобы оптимизатор не мог предсказать во время компиляции, что все еще достаточно быстро, чтобы не подавить и не скрыть влияние кода сравнения строк - непростая задача. Кроме того, помимо точки - сравнение вещей, распространяемых по большей части памяти, делает кеш более актуальным для эталона, что еще больше затрудняет реальную производительность сравнения.

Тем не менее, если бы я был вами, я бы прочитал некоторые строки из файла - нажав каждый на vector, а затем переместил через vector выполнение каждой из трех операций сравнения между соседними элементами. Тогда компилятор не может предсказать какой-либо шаблон в результатах. Вы можете найти compare/== быстрее/медленнее, чем strcmp для строк, часто отличающихся первым символом или тремя, но наоборот для длинных строк, которые равны или только отличаются ближе к концу, поэтому убедитесь, что вы попробуйте различные виды ввода, прежде чем вы поймете, что вы понимаете профиль производительности.

Ответ 2

Либо ваши тайминги являются отвратительными, либо ваш компилятор оптимизировал часть вашего кода из существования.

Подумайте об этом, десять миллиардов операций за 0.000349 миллисекунд (я буду использовать 0.000500 миллисекунд или половину микросекунды, чтобы упростить мои вычисления) означает, что вы выполняете двадцать триллионов операций в секунду.

Даже если одна операция может быть выполнена за один такт, это будет 20 000 ГГц, что немного превышает текущую культуру ЦП, даже с их оптимизированными по массе конвейерами и несколькими ядрами.

И, учитывая, что оптимизированные цифры -O2 более похожи друг на друга (==, занимая удвоенное время compare), вероятность "кода оптимизирована из существования" выглядит гораздо более вероятной.

Удвоение времени можно легко объяснить как десять миллиардов дополнительных вызовов функций, из-за того, что operator== нужно вызвать compare для выполнения своей работы.

В качестве дополнительной поддержки рассмотрите следующую таблицу, в которой показаны цифры в миллисекундах (третий столбец - это простая шкала разделить на десять второго столбца, чтобы как первый, так и третий столбцы составляли миллиард итераций):

         -O2/1billion  -O3/10billion  -O3/1billion  Improvement
               (a)            (b)     (c = b / 10)    (a / c)
         ============  =============  ============  ===========
oper==          19151           5987           599           32
compare          8319         0.0005       0.00005  166,380,000

Он убеждает, что -O3 может ускорить код == примерно в 32 раза, но ускорить код compare на несколько сотен миллионов.

Я настоятельно рекомендую вам взглянуть на код ассемблера, сгенерированный вашим компилятором (например, с опцией gcc -S), чтобы убедиться, что он фактически выполняет ту работу, которую он требует.

Ответ 3

Проблема заключается в том, что компилятор делает много серьезных оптимизаций для вашего кода.

Здесь измененный код:

#include <iostream>
#include <vector>
#include <string>
#include <stdint.h>
#include "Timer.h"
#include <random>
#include <time.h>
#include <string.h>
using namespace std;
uint64_t itr  = 500000000;//10 Billion
int len = 100;
int main() {
  srand(time(0));
  string s1(len,random()%128);
  string s2(len,random()%128);

uint64_t a = 0;
  Timer t;
  t.begin();
  for(uint64_t i =0;i<itr;i++){
asm volatile("" : "+g"(s2));
    if(s1 == s2)
      a += i;
  }
  t.end();

  cout<<"==       took:"<<t.elapsedMillis()<<",a="<<a<<endl;

  t.begin();
  for(uint64_t i =0;i<itr;i++){
asm volatile("" : "+g"(s2));
    if(s1.compare(s2)==0)
      a+=i;
  }
  t.end();

  cout<<".compare took:"<<t.elapsedMillis()<<",a="<<a<<endl;

  t.begin();
  for(uint64_t i =0;i<itr;i++){
asm volatile("" : "+g"(s2));
    if(strcmp(s1.c_str(),s2.c_str()) == 0)
      a+=i;
  }
  t.end();

  cout<<"strcmp   took:"<<t.elapsedMillis()<<",a="<<a<< endl;

  return a;
}

где я добавил asm volatile ( ":" + g "(s2)); чтобы заставить компилятор выполнить сравнение. Я также добавил < <", a =" < чтобы заставить компилятор вычислить a.

Теперь вывод:

==       took:10221.5,a=0
.compare took:10739,a=0
strcmp   took:9700,a=0

Можете ли вы объяснить, почему strcmp быстрее, чем .compare, который медленнее, чем ==? однако различия в скорости являются незначительными, но значительными.

Это на самом деле имеет смысл!: Р

Ответ 4

Ниже приведен неверный анализ скорости - благодаря Tony D для указания моей ошибки. Критика и советы для лучших тестов все еще применяются.

Все предыдущие ответы касаются проблем оптимизации компилятора в вашем тесте, но не отвечайте, почему strcmp все еще немного быстрее.

strcmp, скорее всего, быстрее (в скорректированных тестах) из-за строк, иногда содержащих нули. Поскольку strcmp использует C-строки, он может выйти, когда встречается завершение строки char '\0'. std::string::compare() рассматривает '\0' как еще один char и продолжается до конца массива строк.

Поскольку у вас есть недетерминированное сеяние RNG и генерируется только две строки, ваши результаты будут меняться при каждом запуске кода. (Я бы посоветовал это в тестах.) Учитывая цифры, 28 раз из 128, не должно быть никакого преимущества. В 10 раз из 128 вы получите более 10-кратное ускорение. И так далее.

Как и победить оптимизатор компилятора, я бы предположил, что в следующий раз вы создадите новую строку для каждой итерации сравнения, что позволит вам усреднить такие эффекты.

Ответ 5

Скомпилирован код gcc -O3 -S --std=c++1y. В результате здесь. Версия gcc:

gcc (Ubuntu 4.9.1-16ubuntu6) 4.9.1
Copyright (C) 2014 Free Software Foundation, Inc.
This is free software; see the source for copying conditions.  There is NO
warranty; not even for MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.

Посмотрите на это, мы можем быть первым циклом (operator ==) следующим образом: (комментарий добавлен мной)

    movq    itr(%rip), %rbp
    movq    %rax, %r12
    movq    %rax, 56(%rsp)
    testq   %rbp, %rbp
    je  .L25
    movq    16(%rsp), %rdi
    movq    32(%rsp), %rsi
    xorl    %ebx, %ebx
    movq    -24(%rsi), %rdx  ; length of string1
    cmpq    -24(%rdi), %rdx  ; compare lengths
    je  .L53                 ; compare content only when length is the same
.L10
   ; end of loop, print out follows

;....
.L53:
    .cfi_restore_state
    call    memcmp      ; compare content
    xorl    %edx, %edx  ; zero loop count
    .p2align 4,,10
    .p2align 3
.L13:
    testl   %eax, %eax  ; check result
    cmove   %rdx, %rbx  ; a = i
    addq    $1, %rdx    ; i++
    cmpq    %rbp, %rdx  ; i < itr?
    jne .L13
    jmp .L10    

; ....
.L25:
    xorl    %ebx, %ebx
    jmp .L10

Мы видим, что operator == является строковым, существует только вызов memcmp. И для operator ==, если длина отличается, содержимое не сравнивается.

Самое главное, что сравнение выполняется только один раз. Содержимое цикла содержит только i++;, a=i;, i<itr;.

Для второго цикла (compare()):

    movq    itr(%rip), %r12
    movq    %rax, %r13
    movq    %rax, 56(%rsp)
    testq   %r12, %r12
    je  .L14
    movq    16(%rsp), %rdi
    movq    32(%rsp), %rsi
    movq    -24(%rdi), %rbp
    movq    -24(%rsi), %r14  ; read and compare length
    movq    %rbp, %rdx
    cmpq    %rbp, %r14
    cmovbe  %r14, %rdx       ; save the shorter length of the two string to %rdx
    subq    %r14, %rbp       ; length difference in %rbp
    call    memcmp           ; content is always compared
    movl    $2147483648, %edx ; 0x80000000 sign extended
    addq    %rbp, %rdx       ; revert the sign bit of %rbp (length difference) and save to %rdx
    testl   %eax, %eax       ; memcmp returned 0?
    jne .L14                 ; no, string different
    testl   %ebp, %ebp       ; memcmp returned 0. Are lengths the same (%ebp == 0)?
    jne .L14                 ; no, string different
    movl    $4294967295, %eax ; string compare equal
    subq    $1, %r12         ; itr - 1
    cmpq    %rax, %rdx
    cmovbe  %r12, %rbx       ; a = itr - 1
.L14:
    ; output follows

Здесь нет петли.

В compare(), поскольку он должен возвращать плюс, минус или ноль на основе сравнения, содержимое строки всегда сравнивается. memcmp, вызываемый один раз.

Для третьего цикла (strcmp()) сборка является самой простой:

    movq    itr(%rip), %rbp   ; itr to %rbp
    movq    %rax, %r12
    movq    %rax, 56(%rsp)
    testq   %rbp, %rbp
    je  .L16
    movq    32(%rsp), %rsi
    movq    16(%rsp), %rdi
    subq    $1, %rbp       ; itr - 1 to %rbp
    call    strcmp
    testl   %eax, %eax     ; test compare result
    cmovne  %rbp, %rbx     ; if not equal, save itr - 1 to %rbx (a)
.L16:

Это тоже не петля. strcmp вызывается, и если строки не равны (как в вашем коде), сохраните itr-1 до a напрямую.

Итак, ваш тест не может проверить время работы operator ==, compare() или strcmp(). Все они вызываются только один раз, не в состоянии показать разницу во времени.

Что касается того, почему operator == занимает больше всего времени, это потому, что для operator== компилятор почему-то не устранил цикл. Цикл занимает время (но цикл вообще не содержит сравнения строк).

И из представленной сборки мы можем предположить, что operator == может быть самым быстрым, потому что он не будет выполнять сравнение строк вообще, если длина двух строк различна. (Конечно, под gcc4.9.1 -O3)