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

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

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

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

04.06.2016, 20:57. Просмотров 893. Ответов 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++ Не воспринимает ни std::cout, ни std::cin. Вобщем ничего из std. Также не понимает iostream
C++ запрошено преобразование от ‘const std::string*’ к нескалярному типу ‘std::string’
C++ Здравствуйте! Создал класс std::string. Не создается объкт типа string... Подскажите в чем причина?
Передача функции указатель на элемент std::vector<std::string> C++
C++ Где и почему используют ту или иную строку std::string, char[], System::String^ ?
C++ Как правильно перевести std::wstring в std::string ?
C++ Как привести std::wstring к std::string?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
gromo
370 / 269 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
04.06.2016, 21:12  [ТС]     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #2
Может быть я не туда копаю, в чем тогда бутылочное горлышко? Может мапить файл нужно по частям, а не сразу весь?

И вдогонку:

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

2. Можно ли как-нибудь без геморроя распараллелить такую задачу? (Предпочтительно std и Qt способы, но упоминайте все, что знаете )
Renji
1742 / 1175 / 273
Регистрация: 05.06.2014
Сообщений: 3,394
04.06.2016, 21:53     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #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  [ТС]     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #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
1742 / 1175 / 273
Регистрация: 05.06.2014
Сообщений: 3,394
04.06.2016, 22:07     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #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  [ТС]     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #6
Цитата Сообщение от Renji Посмотреть сообщение
1) Можно - тыкаетесь в середину файла, находите ближайший '\n', все что слева от '\n' в один поток, все что справа в другой.
2) Станет только хуже, так как map это красивая обертка вокруг чтения данных с диска. А диск (если не SSD), вообще говоря, произвольный доступ поддерживает хреново и от скачки по файлу вперед-назад (один поток читает начало, другой середину) начнет тормозить.
Распараллеливать ввод/вывод, конечно же, плохая задумка (во всяком случае, если нет SSD, как вы уже заметили). А если сосредоточиться на хеш-таблице? Есть ли эффективные алгоритмы слияния двух хеш-таблиц? Для случая нескольких потоков, заполняющих разные хеш-таблицы, а потом главный поток их мерджит?
Renji
1742 / 1175 / 273
Регистрация: 05.06.2014
Сообщений: 3,394
04.06.2016, 22:55     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #7
Цитата Сообщение от gromo Посмотреть сообщение
Есть ли эффективные алгоритмы слияния двух хеш-таблиц?
Вам для std::unordered_set или для своей реализации хеш-таблиц?
Если для std::unordered_set, то dst.insert(src.begin(),src.end()). После этого написать комитету по стандартизации очередное воззвание "впилите splice как в std::list!". Правда, пишут им который год (как минимум про splice в std::map), а воз и ныне там.
Если для своей реализации, то хранить элементы вместе с их хешами, чтобы не пересчитывать при переносе в другую таблицу. Сам перенос элемента (при отсутствии коллизий) и так за константное время делается. Чего там еще оптимизировать?
avgoor
837 / 479 / 107
Регистрация: 05.12.2015
Сообщений: 1,371
04.06.2016, 23:49     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #8
gromo, А какое относительное количество уникальных строк?

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

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

Добавлено через 15 минут
Цитата Сообщение от gromo Посмотреть сообщение
У вас есть соображения по этому поводу?
Да, есть. Попробуйте сначала прочитать ваш файл целиком в память (вместо mmap-а) и парсить в памяти. В этом случае разница должна быть в пользу string_view, потому, что ускорение на стрингах вы получаете за счет того, что данные находятся в памяти и обрабатываются там. А mmap именно, что отражает файл на адресное пространство, а не выделяет память и читает туда файл целиком (как бы вы сами написали mmap, учитывая совместный доступ для которого он и есть).
gromo
370 / 269 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
05.06.2016, 02:44  [ТС]     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #15
Цитата Сообщение от avgoor Посмотреть сообщение
Попробуйте сначала прочитать ваш файл целиком в память (вместо mmap-а) и парсить в памяти. В этом случае разница должна быть в пользу string_view, потому, что ускорение на стрингах вы получаете за счет того, что данные находятся в памяти и обрабатываются там.
Сразу так и было реализовано. И если читать в память все целиком, то и парсить уж не надо, std::getline или std::basic_istream::operator>> сделают всю работу. С использованием mmap производительность выросла на 12%.
Единственным способом дальнейшего повышения производительности вижу распараллеливание считывания из файла при наличии SSD и параллельной обработки нескольких хеш-таблиц с последующим их слиянием.
avgoor
837 / 479 / 107
Регистрация: 05.12.2015
Сообщений: 1,371
05.06.2016, 02:58     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #16
Цитата Сообщение от gromo Посмотреть сообщение
И если читать в память все целиком, то и парсить уж не надо
Вы неправильно поняли.
C++
1
2
3
4
5
size_t file_size=...;
char * data=new char[file_size+1]
<функция бинарного чтения из файла>(file, data, file_size);
data[file_size]=0;
/* например, хоть и не самый быстрый способ*/std::istringstream ss(data);
gromo
370 / 269 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
05.06.2016, 04:17  [ТС]     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #17
avgoor, а такой вариант я, как ни странно, еще не пробовал. Думаю сишный ввод/вывод уделает с++. Попробую днем, а то уже ничего не соображаю

avgoor, в общем не смог я уснуть не попробовав
Такой код:

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
namespace sc = std::chrono;
namespace fs = std::experimental::filesystem;
 
int main()
{
    const char *const fileName = "/home/z/data/random_values.txt";
    const int fileSize = fs::file_size(fileName);
 
    auto buffer = std::make_unique<uchar[]>(fileSize);
    auto fh = std::unique_ptr<FILE, void(*)(FILE*)>(std::fopen(fileName, "rb"),
                                [](auto *p){std::fclose(p); });
 
    std::fread(buffer.get(), 1, fileSize, fh.get());
 
 
    std::unordered_set<std::/*experimental::*/string/*_view*/> hashSet;
    hashSet.reserve(1024*1024*100);
 
        std::cerr << "File size: " << fileSize << " bytes\n";
 
        uchar* mapPtr = /*file.map(0, fileSize)*/buffer.get();
        uchar *ptr = mapPtr, *prevPtr = mapPtr;
 
        auto start = sc::high_resolution_clock::now();
        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();
 
        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";
 
}
Используя std::string, получается чуть медленнее, чем mmap — 37 сек:
Код
File size: 688885746 bytes
+-----------------------------------------+
|    Unique elements:    < 1000001 >
|    Elapsed time:       < 36675ms >
+-----------------------------------------+
Используя string_view... сюрприз — 52сек:
Код
FFile size: 688885746 bytes
+-----------------------------------------+
|    Unique elements:    < 1000001 >
|    Elapsed time:       < 51288ms >
+-----------------------------------------+
Так что mmap пока держит лидерство!
avgoor
837 / 479 / 107
Регистрация: 05.12.2015
Сообщений: 1,371
05.06.2016, 13:22     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #18
gromo, Тогда осталась только одна мысль: Т.к. вы писали, что у вас пол миллиарда строк на два гига - строки в среднем полусаются по 4 байта и срабатывает short string optimization, которая за счет локальности данных заруливает string_view.
А вообще ковырять надо. Сбросьте сюда генератор тестовых данных - поковыряюсь.

Добавлено через 5 минут
Цитата Сообщение от gromo Посмотреть сообщение
Так что mmap пока держит лидерство!
Не путайте теплое с мягким. Я отвечал на вопрос:
Цитата Сообщение от gromo Посмотреть сообщение
string_view не дает прироста производительности, а наоборот ухудшает?
Важна была именно относительная скорость string и string_view.
gromo
370 / 269 / 24
Регистрация: 04.09.2009
Сообщений: 1,214
05.06.2016, 17:11  [ТС]     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #19
avgoor, вообще важна именно итоговая производительность операции по обнаружению кол-ва уникальных строк в файле, — а что будет лежать в основе этого, какие-нибудь хитрые операции ввода вывода в сочетании с хранением в string или в string_view — дело десятое. Хотя я действительно чуть перепутал предмет дискуссии выше, прошу прощения.

Генератор самый простой:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void generateRandomNumbers()
{
std::ofstream outFile("/home/z/data/random_values.txt");
 
 
// Seed with a real random value, if available
std::random_device rd;
 
std::mt19937_64 e(rd());
std::uniform_int_distribution<long long> d(0, 1000000);
 
for(int index = 0; index < 100000000; ++index)
outFile << d(e) << '\n';
 
}
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
05.06.2016, 23:41     Почему std::string_view МЕДЛЕННЕЕ, чем std::string?
Еще ссылки по теме:

C++ Error C2664: std::vector<_Ty>::push: невозможно преобразовать параметр 1 из 'double' в 'const std::string &'
C++ Std::string and std::wstring convert
Операция std::cout для Объекта типа std::string C++
отсутствует оператор "<<" соответствующий этим операндам (std::ostream << const std::string) C++
C++ В чем отличия между std::cref() и std::bind()?

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

Или воспользуйтесь поиском по форуму:
avgoor
837 / 479 / 107
Регистрация: 05.12.2015
Сообщений: 1,371
05.06.2016, 23:41     Почему std::string_view МЕДЛЕННЕЕ, чем std::string? #20
gromo, Сегодня уже лень, завтра поковыряю. Пока вам статья в тему: https://habrahabr.ru/post/246257/
Обратите внимание на пункт 8 в ыводной таблице (точнее на разницу во времени).
Yandex
Объявления
05.06.2016, 23:41     Почему std::string_view МЕДЛЕННЕЕ, чем std::string?
Ответ Создать тему
Опции темы

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