Форум программистов, компьютерный форум CyberForum.ru

Почему std::string_view МЕДЛЕННЕЕ, чем std::string? - C++

Восстановить пароль Регистрация
 
 
gromo
 Аватар для gromo
366 / 265 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
04.06.2016, 20:57     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #1
Всем привет!

Нужно найти количество уникальных строк в больших текстовых файлах (размером до нескольких гигабайт).
Почему в нижеследующем коде результат выполнения со string_view, который не копирует элементы, значительно медленнее, чем в случае сo string?!

C++ (Qt)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <fstream>
#include <iomanip>
#include <unordered_set>
#include <chrono>
#include <random>
#include <iterator>
#include <experimental/string_view>
 
#include <QFile>
 
namespace sc = std::chrono;
 
int main()
{
    QFile file("/home/z/data/random_values.txt");
    const int fileSize = file.size();
 
    std::unordered_set<std::/*experimental::*/string/*_view*/> hashSet;
    hashSet.reserve(1024*1024*100);
 
    if(file.open(QIODevice::ReadOnly | QIODevice::Text))
    {
        std::cerr << "File size: " << fileSize << " bytes\n";
 
        // Map the file to virtual address space of a process
        uchar* mapPtr = file.map(0, file.size());
        uchar *ptr = mapPtr, *prevPtr = mapPtr;
 
        file.close(); 
 
        auto start = sc::high_resolution_clock::now();
        
        // Parse lines, delimited by '\n'
        while ( ptr = (uchar*)memchr(ptr, '\n', fileSize - (ptr-mapPtr)))
        {
            hashSet.emplace((const char*)prevPtr, ptr-prevPtr);
 
            prevPtr = ++ptr;
        }
 
 
        auto end = sc::high_resolution_clock::now();
 
        // Print results
        std::cout << "+-----------------------------------------+\n"; // 43 chars
        std::cout << std::setw(25) << std::left << "|    Unique elements:"
                        << "< " << hashSet.size() << " >\n"
 
                  << std::setw(25) << std::left << "|    Elapsed time:"    
                  << "< " << sc::duration_cast<sc::milliseconds>(end-start).count() << "ms >" << std::endl;
        std::cout << "+-----------------------------------------+\n";
 
    }
    else {
        std::cerr << "Error opening file\n";
    }
 
}

Результат с копированием через string:

Почему std::string_view МЕДЛЕННЕЕ, чем std::string?


Результат с "легковесным" string_view:

Почему std::string_view МЕДЛЕННЕЕ, чем std::string?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
04.06.2016, 20:57     Почему std::string_view МЕДЛЕННЕЕ, чем std::string?
Посмотрите здесь:

Алгоритм std::find_end - аналог std::search_n C++
std::string -> std::wstring C++
C++ std::async std::future и функции-члены
C++ std::string + std::remove
Операция std::cout для Объекта типа std::string C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gromo
 Аватар для gromo
366 / 265 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
07.06.2016, 04:44  [ТС]     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #21
Цитата Сообщение от avgoor Посмотреть сообщение
Пока вам статья в тему: https://habrahabr.ru/post/246257/
Видел эту статейку, но у меня, к сожалению, не все так радужно, как там описано. Например, getc_unlocked временами дает худшие результаты, чем просто fread, считывающая файл одним большим блоком.

Таки как-то распараллелил я всю эту штуку.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
#include <iostream>
#include <iomanip>
#include <unordered_set>
#include <chrono>
#include <cstdio>
#include <mutex>
#include <thread>
#include <cstring>
 
#include <experimental/string_view>
#include <experimental/filesystem>
 
 
 
namespace sc = std::chrono;
namespace fs = std::experimental::filesystem;
 
thread_local std::unordered_set<std::/*experimental::*/string/*_view*/> chunk;
std::mutex m;
std::unordered_set<std::/*experimental::*/string/*_view*/> hashSet;
 
 
void processData(const char *const data, uint32_t len)
{
    chunk.reserve(len / 4);
    const char *ptr = data, *prevPtr = data;
 
    while ( ptr = (const char*)memchr(ptr, '\n', len - (ptr-data)))
    {
        chunk.emplace((const char*)prevPtr, ptr-prevPtr);
 
        prevPtr = ++ptr;
    }
    std::lock_guard<decltype(m)> lock(m);
    hashSet.insert(chunk.cbegin(), chunk.cend());
 
}
 
int main()
{
 
    hashSet.reserve(1024*1024*2);
    const char *const fileName = "/home/z/random_values.txt";
    const auto fileSize = fs::file_size(fileName);
    const std::size_t idealThreadCount = std::thread::hardware_concurrency();
    auto buffer = std::make_unique<char[]>(fileSize);
    auto fh = std::unique_ptr<FILE, void(*)(FILE*)>(std::fopen(fileName, "rb"), [](auto *p){std::fclose(p); });
 
    std::cout << "File size: " << fileSize << " bytes\n"
              << "HW concurrency: " << idealThreadCount << std::endl;
 
    const auto start = sc::high_resolution_clock::now();
    std::fread(buffer.get(), 1, fileSize, fh.get());
 
 
    ///-------------------Multithreaded approach
    const int chunkSize = fileSize / idealThreadCount;
    std::vector<std::thread> threads;
    const char *prevPtr = buffer.get(),
               *ptr     = buffer.get(),
               *endPtr  = buffer.get() + fileSize;
 
    for(size_t threadIndex = 0; threadIndex  < idealThreadCount; ++threadIndex )
    {
 
        // If we have enough data for processing.
        if((endPtr - ptr) >= chunkSize)
        {
            ptr += chunkSize;
 
            // Find closest newline.
            while(*ptr != '\n')
                ++ptr;
        }
        else
        {
            // Process remainders of data: from last pos to the end of file.
            threads.emplace_back(processData, prevPtr, endPtr - prevPtr);
            break;
        }
 
        threads.emplace_back(processData, prevPtr, ptr  - prevPtr +1);
        prevPtr = ++ptr;
    }
 
    for(auto& thread : threads)
        thread.join();
 
 
    ///-------------------Single thread approach
//    const char* mapPtr = /*file.map(0, fileSize)*/buffer.get();
//    const char *ptr = mapPtr, *prevPtr = mapPtr;
//    while ( ptr = (const char*)memchr(ptr, '\n', fileSize - (ptr-mapPtr)))
//    {
//        hashSet.emplace((const char*)prevPtr, ptr-prevPtr);
 
//        prevPtr = ++ptr;
//    }
 
 
    // Show results.
    const auto end = sc::high_resolution_clock::now();
 
    std::cout << "+-----------------------------------------+\n"; // 43 chars
    std::cout << std::setw(25) << std::left << "|    Unique elements:"
              << "< " << hashSet.size() << " >\n"
 
              << std::setw(25) << std::left << "|    Elapsed time:"
              << "< " << sc::duration_cast<sc::milliseconds>(end-start).count()
              << "ms >" << std::endl;
    std::cout << "+-----------------------------------------+\n";
}
И в итоге (замерял сразу после перезагрузки компьютера, для чистоты):
Код
File size: 688885746 bytes
HW concurrency: 2
+-----------------------------------------+
|    Unique elements:    < 1000001 >
|    Elapsed time:       < 21097ms >
+-----------------------------------------+
Это с std::string, такой же тест на string_view упорно оставался на пару секунд медленнее. Ну и чертовщина

И вот что интересно: сразу после перезагрузки результат такой как выше. Запускаю браузер, в котором ничего не происходит ресурсоемкого, и производительность падает почти в 2 раза, до 43 секунд (т.е. хуже чем однопоточная версия!). При повторном запуске уже 30 секунд работает. От чего такие скачки? Однопоточная версия хотя бы стабильно ползала.

Добавлено через 30 минут
А вот и наш победитель на данный момент, сочетание memory mapping и мультипоточной обработки, используя std::string:
Код
File size: 688885746 bytes
HW concurrency: 2
+-----------------------------------------+
|    Unique elements:    < 1000001 >
|    Elapsed time:       < 20435ms >
+-----------------------------------------+
Что ж, неплохо, я думаю. Почти 100% прирост в производительности. Вот только Boost::Spirit я не пробовал. Может быть кто сведущий и напишет парсер простых целых чисел.

Какие будут замечания к коду по параллельной обработке ? Сам вижу, что подход топорный у меня.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Nosey
 Аватар для Nosey
1184 / 351 / 102
Регистрация: 22.10.2014
Сообщений: 786
Завершенные тесты: 2
07.06.2016, 12:58     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #22
gromo,
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
#include <iostream>
#include <fstream>
#include <iomanip>
#include <unordered_set>
#include <chrono>
#include <iterator>
#include <string>
#include <algorithm>
#include <future>
#include <thread>
#include <experimental/filesystem>
#include <boost/spirit/include/qi.hpp>
 
namespace sc = std::chrono;
namespace qi = boost::spirit::qi;
 
std::unordered_set<int> MTVersion()
{
    const static char* fileName = "/home/xxx/random_values";
    std::ifstream file(fileName);
    if (file)
    {
        auto start = sc::high_resolution_clock::now();
 
        const auto fileSize = std::experimental::filesystem::file_size(
                fileName);
 
        std::istreambuf_iterator<char> begFile { file };
        std::istreambuf_iterator<char> endFile;
        std::string fileBuf;
        fileBuf.reserve(fileSize);
        fileBuf.insert(fileBuf.begin(), begFile, endFile);
        file.close();
 
        std::vector<std::future<std::unordered_set<int>>>vecOfFut;
 
        const auto threadCount = std::thread::hardware_concurrency();
        auto threadOffset = fileBuf.size() / threadCount;
        double threadOffsetDelta = threadOffset / threadCount;//на глазок :)
        auto beginIt = fileBuf.begin();
        auto endIt = fileBuf.begin();
 
        size_t backetCount = 1024 * 1024 * 10;
 
        double i = threadCount;
        while (--i)
        {
            endIt = std::find(
                    beginIt + threadOffset
                            - static_cast<size_t>((i - threadCount / 2.0)
                                    * threadOffsetDelta), fileBuf.end(), '\n');
 
            vecOfFut.push_back(
                    std::async(std::launch::async,
                            [=](std::string::iterator begin,std::string::iterator end)
                            {
                                std::unordered_set<int> ret;
                                qi::parse(begin, end, qi::int_ % qi::eol, ret);
 
                                return ret;
                            }, beginIt, endIt));
 
            beginIt = ++endIt;
        }
        std::unordered_set<int> hashSet(backetCount);
        for (auto& fut : vecOfFut)
        {
            auto set = fut.get();
            hashSet.insert(std::begin(set), std::end(set));
        }
        auto end = sc::high_resolution_clock::now();
 
        std::cout << "+-----------------------------------------+\n"; // 43 chars
        std::cout << std::setw(25) << std::left << "|    Unique elements:"
                << "< " << hashSet.size() << " >\n"
 
                << std::setw(25) << std::left << "|    Elapsed time:" << "< "
                << sc::duration_cast<sc::milliseconds>(end - start).count()
                << "ms >" << std::endl;
        std::cout << "+-----------------------------------------+\n";
 
        return hashSet;
    }
    throw std::runtime_error("Error opening file");
}
 
int main()
{
    MTVersion();
}
Должен отметить, что полученное ускорение по сравнению с чтением строк, это не заслуга spirit'a, это заслуга std::unordered_set<int> вместо std::unordered_set<std::string>, ну и копеечка от спирита, если сравнивать между std::istream(буферезированный конечно аля stringstream) >> TOINT и qi::int_. Но если же мы сделаем граммматику такой : *(qi::char_ - qi::eol) % qi::eol и соответственно поменяем контейнер, то ускорения уже не будет. Т.е. *(qi::char_ - qi::eol) % qi::eol в лучшем случае будет "делать" тоже самое что и std::getline.
avgoor
562 / 352 / 83
Регистрация: 05.12.2015
Сообщений: 1,137
07.06.2016, 13:55     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #23
Цитата Сообщение от gromo Посмотреть сообщение
Может быть кто сведущий и напишет парсер простых целых чисел
Так вам парсер целых чисел нужен был?
gromo
 Аватар для gromo
366 / 265 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
07.06.2016, 14:05  [ТС]     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #24
avgoor, ну просто для теста и для простоты. А так строки могут какие-угодно.
avgoor
562 / 352 / 83
Регистрация: 05.12.2015
Сообщений: 1,137
07.06.2016, 14:19     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #25
Цитата Сообщение от gromo Посмотреть сообщение
А так строки могут какие-угодно.
Я ж об этом спрашивал. Алгоритм обработки данных зависит от вида самих данных. Если строки в основном уникальные (редко повторяются) - быстрее будет загнать их все в вектор, отсортировать, и посчитать (ну, или erase+unique).Тестовые данные должны отражать реальные. Мне сложно представить реальную задачу, где есть файл с полумиллиардом строк, длинной в 4 байта.
gromo
 Аватар для gromo
366 / 265 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
13.06.2016, 14:29  [ТС]     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #26
Цитата Сообщение от Nosey Посмотреть сообщение
это заслуга std::unordered_set<int> вместо std::unordered_set<std::string>,
А разве не тратятся дополнительные ресурсы на приведение std::string в int? Я всегда думал, что вариант со string будет быстрее чем int.

Цитата Сообщение от Nosey Посмотреть сообщение
Но если же мы сделаем граммматику такой : *(qi::char_ - qi::eol) % qi::eol и соответственно поменяем контейнер, то ускорения уже не будет.
А эта грамматика соответствует любой произвольной строке? ( Просто я спирит вообще не знаю ) И почему не будет ускорения?


Добавлено через 2 минуты
Цитата Сообщение от Nosey Посмотреть сообщение
C++
1
2
3
4
endIt = std::find(
 beginIt + threadOffset
 - static_cast<size_t>((i - threadCount / 2.0)
 threadOffsetDelta), fileBuf.end(), '\n');
И можете объяснить эту строчку? Что это за магическая константа и вообще хитро-вывернутый способ подсчета смещения?

P.s. Ваш код отработал за 10 секунд. Поразительно!
Nosey
 Аватар для Nosey
1184 / 351 / 102
Регистрация: 22.10.2014
Сообщений: 786
Завершенные тесты: 2
13.06.2016, 15:04     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #27
Цитата Сообщение от gromo Посмотреть сообщение
А разве не тратятся дополнительные ресурсы на приведение std::string в int? Я всегда думал, что вариант со string будет быстрее чем int.
(*1) Тратятся, но копирование инта всяко быстрее строки + рассчет хэша для инта - это сам инт.
Т.е. работа при добавлении элемента std::unordered_set<int> при отсутствии балансировки (reserve был вызван) примерно следущая:
Код
ar[value] = value;
//где
//int ar[reserveSize];
// value - добавляемое значение.
Цитата Сообщение от gromo Посмотреть сообщение
А эта грамматика соответствует любой произвольной строке?
*(qi::char_ - qi::eol) - это соответствует любому количеству (любых символов за исключением переноса строки).

Цитата Сообщение от gromo Посмотреть сообщение
И почему не будет ускорения?
См. (*1)

[quote="gromo;9266578"]И можете объяснить эту строчку? Что это за магическая константа и вообще хитро-вывернутый способ подсчета смещения?
Эта магическая константа - это черная магия, которую лучше не использовать
Суть в том, чтобы (n-1)-ый поток закончил рассчёт быстрее чем n-ый поток, и пока n-ый поток еще считает, основной поток может сливать данные от n-1 потока. Но если данных много, это даст не прирост а ухудшение производительности, поскольку данные у последнего потока будут самыми большими и мержить придется со всеми данными. Т.е. это скользкая дорожка в общем случае.
А написал я эту скользкую дорожку, поскольку не успел остановить руки

Цитата Сообщение от gromo Посмотреть сообщение
P.s. Ваш код отработал за 10 секунд. Поразительно!
Как я сказал это за счёт инта, сделаете в стринг и отработает за очень близкое время к вашему алгоритму.
gromo
 Аватар для gromo
366 / 265 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
13.06.2016, 15:17  [ТС]     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #28
Nosey, спасибо за разъяснения!
Немножко не по теме: стоит ли включать в работу главный поток наравне с рабочими? То есть делегировать часть работы главному потоку, а не оставлять его спать и ждать пока приджоинятся все "работяги"?
Я считаю, что на современных системах это не критично и не принесет выигрыша в производительности, так как работают сотни потоков и десятки процессов, и то, что мы завели один лишний поток — сути дела не меняет.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
13.06.2016, 15:29     Почему std::string_view МЕДЛЕННЕЕ, чем std::string?
Еще ссылки по теме:

отсутствует оператор "<<" соответствующий этим операндам (std::ostream << const std::string) C++
C++ Как можно еще использовать std::placeholders вне в связки с std::bind?
C++ В чем отличия между std::cref() и std::bind()?

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
Nosey
 Аватар для Nosey
1184 / 351 / 102
Регистрация: 22.10.2014
Сообщений: 786
Завершенные тесты: 2
13.06.2016, 15:29     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #29
Цитата Сообщение от gromo Посмотреть сообщение
Немножко не по теме: стоит ли включать в работу главный поток наравне с рабочими? То есть делегировать часть работы главному потоку, а не оставлять его спать и ждать пока приджоинятся все "работяги"?
Я считаю, что на современных системах это не критично и не принесет выигрыша в производительности, так как работают сотни потоков и десятки процессов, и то, что мы завели один лишний поток — сути дела не меняет.
Да, это все мелочи редкостные, если учитывать что у ОС могут "закончиться потоки"
http://en.cppreference.com/w/cpp/thread/thread/thread См. раздел "Exceptions".
Yandex
Объявления
13.06.2016, 15:29     Почему std::string_view МЕДЛЕННЕЕ, чем std::string?
Ответ Создать тему
Опции темы

Текущее время: 12:58. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru