Подтвердить что ты не робот

Почему `std:: copy` 5x (!) Медленнее, чем` memcpy` в моей тестовой программе?

Это продолжение этого вопроса, где я опубликовал эту программу:

#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <ctime>
#include <iomanip>
#include <iostream>
#include <vector>
#include <chrono>

class Stopwatch
{
public:
    typedef std::chrono::high_resolution_clock Clock;

    //! Constructor starts the stopwatch
    Stopwatch() : mStart(Clock::now())
    {
    }

    //! Returns elapsed number of seconds in decimal form.
    double elapsed()
    {
        return 1.0 * (Clock::now() - mStart).count() / Clock::period::den;
    }

    Clock::time_point mStart;
};

struct test_cast
{
    int operator()(const char * data) const
    {
        return *((int*)data);
    }
};

struct test_memcpy
{
    int operator()(const char * data) const
    {
        int result;
        memcpy(&result, data, sizeof(result));
        return result;
    }
};

struct test_memmove
{
    int operator()(const char * data) const
    {
        int result;
        memmove(&result, data, sizeof(result));
        return result;
    }
};

struct test_std_copy
{
    int operator()(const char * data) const
    {
        int result;
        std::copy(data, data + sizeof(int), reinterpret_cast<char *>(&result));
        return result;
    }
};

enum
{
    iterations = 2000,
    container_size = 2000
};

//! Returns a list of integers in binary form.
std::vector<char> get_binary_data()
{
    std::vector<char> bytes(sizeof(int) * container_size);
    for (std::vector<int>::size_type i = 0; i != bytes.size(); i += sizeof(int))
    {
        memcpy(&bytes[i], &i, sizeof(i));
    }
    return bytes;
}

template<typename Function>
unsigned benchmark(const Function & function, unsigned & counter)
{
    std::vector<char> binary_data = get_binary_data();
    Stopwatch sw;
    for (unsigned iter = 0; iter != iterations; ++iter)
    {
        for (unsigned i = 0; i != binary_data.size(); i += 4)
        {
            const char * c = reinterpret_cast<const char*>(&binary_data[i]);
            counter += function(c);
        }
    }
    return unsigned(0.5 + 1000.0 * sw.elapsed());
}

int main()
{
    srand(time(0));
    unsigned counter = 0;

    std::cout << "cast:      " << benchmark(test_cast(),     counter) << " ms" << std::endl;
    std::cout << "memcpy:    " << benchmark(test_memcpy(),   counter) << " ms" << std::endl;
    std::cout << "memmove:   " << benchmark(test_memmove(),  counter) << " ms" << std::endl;
    std::cout << "std::copy: " << benchmark(test_std_copy(), counter) << " ms" << std::endl;
    std::cout << "(counter:  " << counter << ")" << std::endl << std::endl;

}

Я заметил, что по какой-то причине std::copy выполняет намного хуже, чем memcpy. Результат выглядит так на моем Mac с помощью gcc 4.7.

g++ -o test -std=c++0x -O0 -Wall -Werror -Wextra -pedantic-errors main.cpp
cast:      41 ms
memcpy:    46 ms
memmove:   53 ms
std::copy: 211 ms
(counter:  3838457856)

g++ -o test -std=c++0x -O1 -Wall -Werror -Wextra -pedantic-errors main.cpp
cast:      8 ms
memcpy:    7 ms
memmove:   8 ms
std::copy: 19 ms
(counter:  3838457856)

g++ -o test -std=c++0x -O2 -Wall -Werror -Wextra -pedantic-errors main.cpp
cast:      3 ms
memcpy:    2 ms
memmove:   3 ms
std::copy: 27 ms
(counter:  3838457856)

g++ -o test -std=c++0x -O3 -Wall -Werror -Wextra -pedantic-errors main.cpp
cast:      2 ms
memcpy:    2 ms
memmove:   3 ms
std::copy: 16 ms
(counter:  3838457856)

Как вы можете видеть, даже с -O3 он до 5 раз (!) медленнее, чем memcpy.

Результаты аналогичны для Linux.

Кто-нибудь знает, почему?

4b9b3361

Ответ 1

Это не те результаты, которые я получаю:

> g++ -O3 XX.cpp 
> ./a.out
cast:      5 ms
memcpy:    4 ms
std::copy: 3 ms
(counter:  1264720400)

Hardware: 2GHz Intel Core i7
Memory:   8G 1333 MHz DDR3
OS:       Max OS X 10.7.5
Compiler: i686-apple-darwin11-llvm-g++-4.2 (GCC) 4.2.1

В ящике Linux я получаю разные результаты:

> g++ -std=c++0x -O3 XX.cpp 
> ./a.out 
cast:      3 ms
memcpy:    4 ms
std::copy: 21 ms
(counter:  731359744)


Hardware:  Intel(R) Xeon(R) CPU E5-2670 0 @ 2.60GHz
Memory:    61363780 kB
OS:        Linux ip-10-58-154-83 3.2.0-29-virtual #46-Ubuntu SMP
Compiler:  g++ (Ubuntu/Linaro 4.6.3-1ubuntu5) 4.6.3

Ответ 2

Я согласен с @rici comment о разработке более значимого теста, поэтому я переписал ваш тест для сравнения двух векторов с использованием memcpy(), memmove(), std::copy() и оператор назначения std::vector:

#include <algorithm>
#include <iostream>
#include <vector>
#include <chrono>
#include <random>
#include <cstring>
#include <cassert>

typedef std::vector<int> vector_type;

void test_memcpy(vector_type & destv, vector_type const & srcv)
{
    vector_type::pointer       const dest = destv.data();
    vector_type::const_pointer const src  = srcv.data();

    std::memcpy(dest, src, srcv.size() * sizeof(vector_type::value_type));
}

void test_memmove(vector_type & destv, vector_type const & srcv)
{
    vector_type::pointer       const dest = destv.data();
    vector_type::const_pointer const src  = srcv.data();

    std::memmove(dest, src, srcv.size() * sizeof(vector_type::value_type));
}

void test_std_copy(vector_type & dest, vector_type const & src)
{
    std::copy(src.begin(), src.end(), dest.begin());
}

void test_assignment(vector_type & dest, vector_type const & src)
{
    dest = src;
}

auto
benchmark(std::function<void(vector_type &, vector_type const &)> copy_func)
    ->decltype(std::chrono::milliseconds().count())
{
    std::random_device rd;
    std::mt19937 generator(rd());
    std::uniform_int_distribution<vector_type::value_type> distribution;

    static vector_type::size_type const num_elems = 2000;

    vector_type dest(num_elems);
    vector_type src(num_elems);

    // Fill the source and destination vectors with random data.
    for (vector_type::size_type i = 0; i < num_elems; ++i) {
        src.push_back(distribution(generator));
        dest.push_back(distribution(generator));
    }

    static int const iterations = 50000;

    std::chrono::time_point<std::chrono::system_clock> start, end;

    start = std::chrono::system_clock::now();

    for (int i = 0; i != iterations; ++i)
        copy_func(dest, src);

    end = std::chrono::system_clock::now();

    assert(src == dest);

    return
        std::chrono::duration_cast<std::chrono::milliseconds>(
            end - start).count();
}

int main()
{
    std::cout
        << "memcpy:     " << benchmark(test_memcpy)     << " ms" << std::endl
        << "memmove:    " << benchmark(test_memmove)    << " ms" << std::endl
        << "std::copy:  " << benchmark(test_std_copy)   << " ms" << std::endl
        << "assignment: " << benchmark(test_assignment) << " ms" << std::endl
        << std::endl;
}

Я немного переборщил с С++ 11 просто для удовольствия.

Вот результаты, которые я получаю в своем 64-битном поле Ubuntu с g++ 4.6.3:

$ g++ -O3 -std=c++0x foo.cpp ; ./a.out 
memcpy:     33 ms
memmove:    33 ms
std::copy:  33 ms
assignment: 34 ms

Результаты вполне сопоставимы! Я получаю сопоставимые времена во всех тестовых случаях, когда я меняю целочисленный тип, например. к long long, и в векторе.

Если моя контрольная переиздание не будет нарушена, похоже, что ваш собственный тест не выполняет корректного сравнения. НТН!

Ответ 3

Похоже, что ответ заключается в том, что gcc может оптимизировать эти конкретные вызовы memmove и memcpy, но не std:: copy. gcc знает семантику memmove и memcpy и в этом случае может воспользоваться тем фактом, что размер известен (sizeof (int)), чтобы превратить вызов в одну команду mov.

std:: copy реализуется в терминах memcpy, но, судя по всему, gcc-оптимизатор не может определить, что data + sizeof (int) - данные точно sizeof (int). Таким образом, эталонный вызов вызывает memcpy.

Я получил все это, вызвав gcc с помощью -S и быстро перевернувшись через выход; Я мог бы легко ошибиться, но то, что я видел, похоже на ваши измерения.

Кстати, я думаю, что тест более или менее бессмыслен. Более правдоподобный реальный тест может создавать реальные vector<int> src и int[N] dst, а затем сравнивать memcpy(dst, src.data(), sizeof(int)*src.size()) с std::copy(src.begin(), src.end(), &dst).

Ответ 4

memcpy и std::copy каждый из них имеет свои применения, std::copy должен (как указано в Cheers ниже) быть таким же медленным, как memmove, потому что нет гарантии, что области памяти будут перекрываться. Это означает, что вы можете легко копировать несмежные регионы (поскольку он поддерживает итераторы) (подумайте о редко распределенных структурах, таких как связанный список и т.д.... даже пользовательские классы/структуры, которые реализуют итераторы). memcpy работает только по смежным причинам и как таковая может быть сильно оптимизирована.

Ответ 5

В соответствии с выходом ассемблера g++ 4.8.1, test_memcpy:

movl    (%r15), %r15d

test_std_copy:

movl    $4, %edx
movq    %r15, %rsi
leaq    16(%rsp), %rdi
call    memcpy

Как вы можете видеть, std::copy успешно распознал, что он может копировать данные с помощью memcpy, но по какой-то причине дальнейшая инкрустация не произошла - так что это является причиной разницы в производительности.

Кстати, Clang 3.4 производит идентичный код для обоих случаев:

movl    (%r14,%rbx), %ebp