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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
gromo
370 / 269 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
#1

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

04.06.2016, 20:57. Просмотров 1155. Ответов 28
Метки нет (Все метки)

Всем привет!

Нужно найти количество уникальных строк в больших текстовых файлах (размером до нескольких гигабайт).
Почему в нижеследующем коде результат выполнения со 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? (C++):

ошибка error: cannot convert 'std::string {aka std::basic_string<char>}' to 'std::string* {aka std::basic_stri - C++
на вод поступают 2 строки типа string. определить количество вхождений строки 2 в строку 1 ошибка error: cannot convert 'std::string {aka...

На основе исходного std::vector<std::string> содержащего числа, создать std::vector<int> с этими же числами - C++
подскажите есть вот такая задача. Есть список . Создать второй список, в котором будут все эти же числа, но не в виде строк, а в виде...

запрошено преобразование от ‘const std::string*’ к нескалярному типу ‘std::string’ - C++
private: std::string firstName; }; std::string ClientData::getFirstName() const{ return firstName; } Дает в итоге...

Реализация класса MyString. Стандартная библиотека, std::string, std::vector - C++
как добавить реализацию конкатенации строк через перегрузку оператора &quot;+=&quot; в классе MyString и почему ошибка выдается???#include...

Передача функции указатель на элемент std::vector<std::string> - C++
Доброй ночи тем, кому не спится (или живет в другом часовом поясе:p)! Есть функция, требующая в качестве параметра указатель на...

Операция std::cout для Объекта типа std::string - C++
Кто детально объяснит почему не выводит ? Дает вот так &quot;Отсутствует оператор &quot;&lt;&lt;&quot;, соответствующий этим операндам&quot; void...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
gromo
370 / 269 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
04.06.2016, 21:12  [ТС] #2
Может быть я не туда копаю, в чем тогда бутылочное горлышко? Может мапить файл нужно по частям, а не сразу весь?

И вдогонку:

1. Безопасно ли в таком коде парсить текст через поиск '\n' используя memchr ? Насколько я знаю, системный вызов mmap работает с сырым содержимым файла и не преобразовывает переводы строки в нативный формат (хотя QFile выше я открываю в текстовом режиме).

2. Можно ли как-нибудь без геморроя распараллелить такую задачу? (Предпочтительно std и Qt способы, но упоминайте все, что знаете )
Renji
1904 / 1302 / 291
Регистрация: 05.06.2014
Сообщений: 3,727
04.06.2016, 21:53 #3
Цитата Сообщение от gromo Посмотреть сообщение
Почему в нижеследующем коде результат выполнения со string_view, который не копирует элементы, значительно медленнее, чем в случае сo string?!
Возможно, потому что какая-то ленивая скотина сделала std::hash<std::string_view> через предварительное преобразование std::string_view в std::string. Это надо в потрохах копаться, чтобы разобраться что именно тормозит.
Цитата Сообщение от gromo Посмотреть сообщение
1. Безопасно ли в таком коде парсить текст через поиск '\n' используя memchr ?
Потеряет последнюю строчку, если там '\n' нет.
Цитата Сообщение от gromo Посмотреть сообщение
2. Можно ли как-нибудь без геморроя распараллелить такую задачу?
1) Можно - тыкаетесь в середину файла, находите ближайший '\n', все что слева от '\n' в один поток, все что справа в другой.
2) Станет только хуже, так как map это красивая обертка вокруг чтения данных с диска. А диск (если не SSD), вообще говоря, произвольный доступ поддерживает хреново и от скачки по файлу вперед-назад (один поток читает начало, другой середину) начнет тормозить.
gromo
370 / 269 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
04.06.2016, 22:01  [ТС] #4
Цитата Сообщение от Renji Посмотреть сообщение
Возможно, потому что какая-то ленивая скотина сделала std::hash<std::string_view> через предварительное преобразование std::string_view в std::string. Это надо в потрохах копаться, чтобы разобраться что именно тормозит.
В моей стандартной библиотеке я копался, без преобразования судя по всему. С std::string по такому же принципу хеш считается.
Цитата Сообщение от Renji Посмотреть сообщение
Потеряет последнюю строчку, если там '\n' нет.
Это понятно, я в том плане, что \r\n и \n будут трактоваться по-разному, если mmap открывает файл в бинарном режиме. (Если конечно qt-обертка не добавляет такое преобразование, ведь QFile я открывал в режиме QFile::Text)
Цитата Сообщение от Renji Посмотреть сообщение
map это красивая обертка вокруг чтения данных с диска.
Ну не только в красоте дело, ведь при маппинге данные с файла считываются блоками размером со страницу памяти + copy on write
Renji
1904 / 1302 / 291
Регистрация: 05.06.2014
Сообщений: 3,727
04.06.2016, 22:07 #5
Цитата Сообщение от gromo Посмотреть сообщение
В моей стандартной библиотеке я копался, без преобразования судя по всему. С std::string по такому же принципу хеш считается.
Тогда, возможно, дело в прижимистом алгоритме мапинга файла - когда вы загружаете тысячную строчку, он выкидывает из памяти первую. Типа, все равно же копия на диске есть, чего место тратить? А потом std::unordered_set пытается первую строчку прочитать еще раз и приходится лезть за ней на диск.
Цитата Сообщение от gromo Посмотреть сообщение
Это понятно, я в том плане, что \r\n и \n будут трактоваться по-разному, если mmap открывает файл в бинарном режиме.
Просто в строчку попадет этот \r и всего делов.
gromo
370 / 269 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
04.06.2016, 22:30  [ТС] #6
Цитата Сообщение от Renji Посмотреть сообщение
1) Можно - тыкаетесь в середину файла, находите ближайший '\n', все что слева от '\n' в один поток, все что справа в другой.
2) Станет только хуже, так как map это красивая обертка вокруг чтения данных с диска. А диск (если не SSD), вообще говоря, произвольный доступ поддерживает хреново и от скачки по файлу вперед-назад (один поток читает начало, другой середину) начнет тормозить.
Распараллеливать ввод/вывод, конечно же, плохая задумка (во всяком случае, если нет SSD, как вы уже заметили). А если сосредоточиться на хеш-таблице? Есть ли эффективные алгоритмы слияния двух хеш-таблиц? Для случая нескольких потоков, заполняющих разные хеш-таблицы, а потом главный поток их мерджит?
Renji
1904 / 1302 / 291
Регистрация: 05.06.2014
Сообщений: 3,727
04.06.2016, 22:55 #7
Цитата Сообщение от gromo Посмотреть сообщение
Есть ли эффективные алгоритмы слияния двух хеш-таблиц?
Вам для std::unordered_set или для своей реализации хеш-таблиц?
Если для std::unordered_set, то dst.insert(src.begin(),src.end()). После этого написать комитету по стандартизации очередное воззвание "впилите splice как в std::list!". Правда, пишут им который год (как минимум про splice в std::map), а воз и ныне там.
Если для своей реализации, то хранить элементы вместе с их хешами, чтобы не пересчитывать при переносе в другую таблицу. Сам перенос элемента (при отсутствии коллизий) и так за константное время делается. Чего там еще оптимизировать?
avgoor
885 / 520 / 112
Регистрация: 05.12.2015
Сообщений: 1,465
04.06.2016, 23:49 #8
gromo, А какое относительное количество уникальных строк?

Добавлено через 14 минут
А еще лучше мат. ожидание количества повторов одной строки.
gromo
370 / 269 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
05.06.2016, 00:09  [ТС] #9
Цитата Сообщение от avgoor Посмотреть сообщение
А какое относительное количество уникальных строк?
Ну в среднем файлы по 2Гб и где-то 15 000 000 уникальных строк в них есть.
Цитата Сообщение от avgoor Посмотреть сообщение
А еще лучше мат. ожидание количества повторов одной строки.
А вот с математикой я не сильно дружу
avgoor
885 / 520 / 112
Регистрация: 05.12.2015
Сообщений: 1,465
05.06.2016, 00:18 #10
Цитата Сообщение от gromo Посмотреть сообщение
и где-то 15 000 000
А всего строк сколько?

Добавлено через 4 минуты
Цитата Сообщение от gromo Посмотреть сообщение
А вот с математикой я не сильно дружу
Вот это зря. Теория информации - развитие теории вероятностей.
gromo
370 / 269 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
05.06.2016, 01:53  [ТС] #11
Цитата Сообщение от avgoor Посмотреть сообщение
А всего строк сколько?
По-разному опять же... но до пол миллиарда доходит
avgoor
885 / 520 / 112
Регистрация: 05.12.2015
Сообщений: 1,465
05.06.2016, 02:08 #12
Цитата Сообщение от gromo Посмотреть сообщение
но до пол миллиарда доходит
Не может в два гига поместиться пятьсот миллионов уникальных (текстовых!) строк.
gromo
370 / 269 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
05.06.2016, 02:11  [ТС] #13
avgoor, вы спрашивали
Цитата Сообщение от avgoor Посмотреть сообщение
А всего строк сколько?
Так вот я и ответил сколько их ВСЕГО. Да и какое это имеет отношение к тому, что string_view не дает прироста производительности, а наоборот ухудшает? У вас есть соображения по этому поводу?
avgoor
885 / 520 / 112
Регистрация: 05.12.2015
Сообщений: 1,465
05.06.2016, 02:30 #14
UPD: поправка: уникальных - лишнее.

Добавлено через 15 минут
Цитата Сообщение от gromo Посмотреть сообщение
У вас есть соображения по этому поводу?
Да, есть. Попробуйте сначала прочитать ваш файл целиком в память (вместо mmap-а) и парсить в памяти. В этом случае разница должна быть в пользу string_view, потому, что ускорение на стрингах вы получаете за счет того, что данные находятся в памяти и обрабатываются там. А mmap именно, что отражает файл на адресное пространство, а не выделяет память и читает туда файл целиком (как бы вы сами написали mmap, учитывая совместный доступ для которого он и есть).
gromo
370 / 269 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
05.06.2016, 02:44  [ТС] #15
Цитата Сообщение от avgoor Посмотреть сообщение
Попробуйте сначала прочитать ваш файл целиком в память (вместо mmap-а) и парсить в памяти. В этом случае разница должна быть в пользу string_view, потому, что ускорение на стрингах вы получаете за счет того, что данные находятся в памяти и обрабатываются там.
Сразу так и было реализовано. И если читать в память все целиком, то и парсить уж не надо, std::getline или std::basic_istream::operator>> сделают всю работу. С использованием mmap производительность выросла на 12%.
Единственным способом дальнейшего повышения производительности вижу распараллеливание считывания из файла при наличии SSD и параллельной обработки нескольких хеш-таблиц с последующим их слиянием.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.06.2016, 02:44
Привет! Вот еще темы с ответами:

Как правильно перевести std::wstring в std::string ? - C++
Собственно как? :)

Как привести std::wstring к std::string? - C++
Как привести std::wstring к std::string?

Error C2664: std::vector<_Ty>::push: невозможно преобразовать параметр 1 из 'double' в 'const std::string &' - C++
#include &lt;iostream&gt; #include &lt;stack&gt; #include &lt;sstream&gt; #include &lt;string&gt; using namespace std; int main() { string...

В чем отличия между std::cref() и std::bind()? - C++
В документации не понял, что делает bind() ? И чем отличается cref() от операции взятия адреса? int x; int *y = &amp;x; ...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
05.06.2016, 02:44
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru