383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
1

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

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

Author24 — интернет-сервис помощи студентам
Всем привет!

Нужно найти количество уникальных строк в больших текстовых файлах (размером до нескольких гигабайт).
Почему в нижеследующем коде результат выполнения со 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?
0
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
04.06.2016, 20:57
Ответы с готовыми решениями:

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

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

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

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

28
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
04.06.2016, 21:12  [ТС] 2
Может быть я не туда копаю, в чем тогда бутылочное горлышко? Может мапить файл нужно по частям, а не сразу весь?

И вдогонку:

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

2. Можно ли как-нибудь без геморроя распараллелить такую задачу? (Предпочтительно std и Qt способы, но упоминайте все, что знаете )
0
2780 / 1933 / 570
Регистрация: 05.06.2014
Сообщений: 5,598
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), вообще говоря, произвольный доступ поддерживает хреново и от скачки по файлу вперед-назад (один поток читает начало, другой середину) начнет тормозить.
0
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
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
0
2780 / 1933 / 570
Регистрация: 05.06.2014
Сообщений: 5,598
04.06.2016, 22:07 5
Цитата Сообщение от gromo Посмотреть сообщение
В моей стандартной библиотеке я копался, без преобразования судя по всему. С std::string по такому же принципу хеш считается.
Тогда, возможно, дело в прижимистом алгоритме мапинга файла - когда вы загружаете тысячную строчку, он выкидывает из памяти первую. Типа, все равно же копия на диске есть, чего место тратить? А потом std::unordered_set пытается первую строчку прочитать еще раз и приходится лезть за ней на диск.
Цитата Сообщение от gromo Посмотреть сообщение
Это понятно, я в том плане, что \r\n и \n будут трактоваться по-разному, если mmap открывает файл в бинарном режиме.
Просто в строчку попадет этот \r и всего делов.
1
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
04.06.2016, 22:30  [ТС] 6
Цитата Сообщение от Renji Посмотреть сообщение
1) Можно - тыкаетесь в середину файла, находите ближайший '\n', все что слева от '\n' в один поток, все что справа в другой.
2) Станет только хуже, так как map это красивая обертка вокруг чтения данных с диска. А диск (если не SSD), вообще говоря, произвольный доступ поддерживает хреново и от скачки по файлу вперед-назад (один поток читает начало, другой середину) начнет тормозить.
Распараллеливать ввод/вывод, конечно же, плохая задумка (во всяком случае, если нет SSD, как вы уже заметили). А если сосредоточиться на хеш-таблице? Есть ли эффективные алгоритмы слияния двух хеш-таблиц? Для случая нескольких потоков, заполняющих разные хеш-таблицы, а потом главный поток их мерджит?
0
2780 / 1933 / 570
Регистрация: 05.06.2014
Сообщений: 5,598
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), а воз и ныне там.
Если для своей реализации, то хранить элементы вместе с их хешами, чтобы не пересчитывать при переносе в другую таблицу. Сам перенос элемента (при отсутствии коллизий) и так за константное время делается. Чего там еще оптимизировать?
1
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
04.06.2016, 23:49 8
gromo, А какое относительное количество уникальных строк?

Добавлено через 14 минут
А еще лучше мат. ожидание количества повторов одной строки.
0
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
05.06.2016, 00:09  [ТС] 9
Цитата Сообщение от avgoor Посмотреть сообщение
А какое относительное количество уникальных строк?
Ну в среднем файлы по 2Гб и где-то 15 000 000 уникальных строк в них есть.
Цитата Сообщение от avgoor Посмотреть сообщение
А еще лучше мат. ожидание количества повторов одной строки.
А вот с математикой я не сильно дружу
0
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
05.06.2016, 00:18 10
Цитата Сообщение от gromo Посмотреть сообщение
и где-то 15 000 000
А всего строк сколько?

Добавлено через 4 минуты
Цитата Сообщение от gromo Посмотреть сообщение
А вот с математикой я не сильно дружу
Вот это зря. Теория информации - развитие теории вероятностей.
0
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
05.06.2016, 01:53  [ТС] 11
Цитата Сообщение от avgoor Посмотреть сообщение
А всего строк сколько?
По-разному опять же... но до пол миллиарда доходит
0
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
05.06.2016, 02:08 12
Цитата Сообщение от gromo Посмотреть сообщение
но до пол миллиарда доходит
Не может в два гига поместиться пятьсот миллионов уникальных (текстовых!) строк.
0
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
05.06.2016, 02:11  [ТС] 13
avgoor, вы спрашивали
Цитата Сообщение от avgoor Посмотреть сообщение
А всего строк сколько?
Так вот я и ответил сколько их ВСЕГО. Да и какое это имеет отношение к тому, что string_view не дает прироста производительности, а наоборот ухудшает? У вас есть соображения по этому поводу?
0
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
05.06.2016, 02:30 14
UPD: поправка: уникальных - лишнее.

Добавлено через 15 минут
Цитата Сообщение от gromo Посмотреть сообщение
У вас есть соображения по этому поводу?
Да, есть. Попробуйте сначала прочитать ваш файл целиком в память (вместо mmap-а) и парсить в памяти. В этом случае разница должна быть в пользу string_view, потому, что ускорение на стрингах вы получаете за счет того, что данные находятся в памяти и обрабатываются там. А mmap именно, что отражает файл на адресное пространство, а не выделяет память и читает туда файл целиком (как бы вы сами написали mmap, учитывая совместный доступ для которого он и есть).
0
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
05.06.2016, 02:44  [ТС] 15
Цитата Сообщение от avgoor Посмотреть сообщение
Попробуйте сначала прочитать ваш файл целиком в память (вместо mmap-а) и парсить в памяти. В этом случае разница должна быть в пользу string_view, потому, что ускорение на стрингах вы получаете за счет того, что данные находятся в памяти и обрабатываются там.
Сразу так и было реализовано. И если читать в память все целиком, то и парсить уж не надо, std::getline или std::basic_istream::operator>> сделают всю работу. С использованием mmap производительность выросла на 12%.
Единственным способом дальнейшего повышения производительности вижу распараллеливание считывания из файла при наличии SSD и параллельной обработки нескольких хеш-таблиц с последующим их слиянием.
0
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
05.06.2016, 02:58 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);
1
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
05.06.2016, 04:17  [ТС] 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 пока держит лидерство!
0
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
05.06.2016, 13:22 18
gromo, Тогда осталась только одна мысль: Т.к. вы писали, что у вас пол миллиарда строк на два гига - строки в среднем полусаются по 4 байта и срабатывает short string optimization, которая за счет локальности данных заруливает string_view.
А вообще ковырять надо. Сбросьте сюда генератор тестовых данных - поковыряюсь.

Добавлено через 5 минут
Цитата Сообщение от gromo Посмотреть сообщение
Так что mmap пока держит лидерство!
Не путайте теплое с мягким. Я отвечал на вопрос:
Цитата Сообщение от gromo Посмотреть сообщение
string_view не дает прироста производительности, а наоборот ухудшает?
Важна была именно относительная скорость string и string_view.
0
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
05.06.2016, 17:11  [ТС] 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';
 
}
0
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
05.06.2016, 23:41 20
gromo, Сегодня уже лень, завтра поковыряю. Пока вам статья в тему: https://habrahabr.ru/post/246257/
Обратите внимание на пункт 8 в ыводной таблице (точнее на разницу во времени).
0
05.06.2016, 23:41
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
05.06.2016, 23:41
Помогаю со студенческими работами здесь

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

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

No match for 'operator<' (operand types are 'std::__cxx11::string {aka std::__c
Имеем следующий код: #include &lt;iostream&gt; #include &lt;string&gt; #include &lt;vector&gt; #include...

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


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

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2024, CyberForum.ru