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

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

04.06.2016, 20:57. Показов 8790. Ответов 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:




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

0
Programming
Эксперт
39485 / 9562 / 3019
Регистрация: 12.04.2006
Сообщений: 41,671
Блог
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 ошибка error: cannot convert 'std::string {aka...

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

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

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

И вдогонку:

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

2. Можно ли как-нибудь без геморроя распараллелить такую задачу? (Предпочтительно std и Qt способы, но упоминайте все, что знаете )
0
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
04.06.2016, 21:53
Цитата Сообщение от 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
 Аватар для gromo
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
04.06.2016, 22:01  [ТС]
Цитата Сообщение от 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
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
04.06.2016, 22:07
Цитата Сообщение от gromo Посмотреть сообщение
В моей стандартной библиотеке я копался, без преобразования судя по всему. С std::string по такому же принципу хеш считается.
Тогда, возможно, дело в прижимистом алгоритме мапинга файла - когда вы загружаете тысячную строчку, он выкидывает из памяти первую. Типа, все равно же копия на диске есть, чего место тратить? А потом std::unordered_set пытается первую строчку прочитать еще раз и приходится лезть за ней на диск.
Цитата Сообщение от gromo Посмотреть сообщение
Это понятно, я в том плане, что \r\n и \n будут трактоваться по-разному, если mmap открывает файл в бинарном режиме.
Просто в строчку попадет этот \r и всего делов.
1
 Аватар для gromo
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
04.06.2016, 22:30  [ТС]
Цитата Сообщение от Renji Посмотреть сообщение
1) Можно - тыкаетесь в середину файла, находите ближайший '\n', все что слева от '\n' в один поток, все что справа в другой.
2) Станет только хуже, так как map это красивая обертка вокруг чтения данных с диска. А диск (если не SSD), вообще говоря, произвольный доступ поддерживает хреново и от скачки по файлу вперед-назад (один поток читает начало, другой середину) начнет тормозить.
Распараллеливать ввод/вывод, конечно же, плохая задумка (во всяком случае, если нет SSD, как вы уже заметили). А если сосредоточиться на хеш-таблице? Есть ли эффективные алгоритмы слияния двух хеш-таблиц? Для случая нескольких потоков, заполняющих разные хеш-таблицы, а потом главный поток их мерджит?
0
2784 / 1937 / 570
Регистрация: 05.06.2014
Сообщений: 5,602
04.06.2016, 22:55
Цитата Сообщение от gromo Посмотреть сообщение
Есть ли эффективные алгоритмы слияния двух хеш-таблиц?
Вам для std::unordered_set или для своей реализации хеш-таблиц?
Если для std::unordered_set, то dst.insert(src.begin(),src.end()). После этого написать комитету по стандартизации очередное воззвание "впилите splice как в std::list!". Правда, пишут им который год (как минимум про splice в std::map), а воз и ныне там.
Если для своей реализации, то хранить элементы вместе с их хешами, чтобы не пересчитывать при переносе в другую таблицу. Сам перенос элемента (при отсутствии коллизий) и так за константное время делается. Чего там еще оптимизировать?
1
 Аватар для avgoor
1550 / 877 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
04.06.2016, 23:49
gromo, А какое относительное количество уникальных строк?

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

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

Добавлено через 15 минут
Цитата Сообщение от gromo Посмотреть сообщение
У вас есть соображения по этому поводу?
Да, есть. Попробуйте сначала прочитать ваш файл целиком в память (вместо mmap-а) и парсить в памяти. В этом случае разница должна быть в пользу string_view, потому, что ускорение на стрингах вы получаете за счет того, что данные находятся в памяти и обрабатываются там. А mmap именно, что отражает файл на адресное пространство, а не выделяет память и читает туда файл целиком (как бы вы сами написали mmap, учитывая совместный доступ для которого он и есть).
0
 Аватар для gromo
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
05.06.2016, 02:44  [ТС]
Цитата Сообщение от avgoor Посмотреть сообщение
Попробуйте сначала прочитать ваш файл целиком в память (вместо mmap-а) и парсить в памяти. В этом случае разница должна быть в пользу string_view, потому, что ускорение на стрингах вы получаете за счет того, что данные находятся в памяти и обрабатываются там.
Сразу так и было реализовано. И если читать в память все целиком, то и парсить уж не надо, std::getline или std::basic_istream::operator>> сделают всю работу. С использованием mmap производительность выросла на 12%.
Единственным способом дальнейшего повышения производительности вижу распараллеливание считывания из файла при наличии SSD и параллельной обработки нескольких хеш-таблиц с последующим их слиянием.
0
 Аватар для avgoor
1550 / 877 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
05.06.2016, 02:58
Цитата Сообщение от 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
 Аватар для gromo
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
05.06.2016, 04: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 сек:
Code
1
2
3
4
5
File size: 688885746 bytes
+-----------------------------------------+
|    Unique elements:    < 1000001 >
|    Elapsed time:       < 36675ms >
+-----------------------------------------+
Используя string_view... сюрприз — 52сек:
Code
1
2
3
4
5
FFile size: 688885746 bytes
+-----------------------------------------+
|    Unique elements:    < 1000001 >
|    Elapsed time:       < 51288ms >
+-----------------------------------------+
Так что mmap пока держит лидерство!
0
 Аватар для avgoor
1550 / 877 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
05.06.2016, 13:22
gromo, Тогда осталась только одна мысль: Т.к. вы писали, что у вас пол миллиарда строк на два гига - строки в среднем полусаются по 4 байта и срабатывает short string optimization, которая за счет локальности данных заруливает string_view.
А вообще ковырять надо. Сбросьте сюда генератор тестовых данных - поковыряюсь.

Добавлено через 5 минут
Цитата Сообщение от gromo Посмотреть сообщение
Так что mmap пока держит лидерство!
Не путайте теплое с мягким. Я отвечал на вопрос:
Цитата Сообщение от gromo Посмотреть сообщение
string_view не дает прироста производительности, а наоборот ухудшает?
Важна была именно относительная скорость string и string_view.
0
 Аватар для gromo
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
05.06.2016, 17:11  [ТС]
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
 Аватар для avgoor
1550 / 877 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
05.06.2016, 23:41
gromo, Сегодня уже лень, завтра поковыряю. Пока вам статья в тему: https://habrahabr.ru/post/246257/
Обратите внимание на пункт 8 в ыводной таблице (точнее на разницу во времени).
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
05.06.2016, 23:41
Помогаю со студенческими работами здесь

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

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

Операция std::cout для Объекта типа std::string
Кто детально объяснит почему не выводит ? Дает вот так &quot;Отсутствует оператор &quot;&lt;&lt;&quot;, соответствующий этим операндам&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 &lt;sstream&gt; using namespace std; int...

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


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

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

Новые блоги и статьи
Мастер-класс по микросервисам на Node.js
Reangularity 21.06.2025
Node. js стал одной из самых популярных платформ для микросервисной архитектуры не случайно. Его неблокирующая однопоточная модель и событийно-ориентированный подход делают его идеальным для. . .
Управление Arduino из WPF приложения
Wired 21.06.2025
Зачем вообще связывать Arduino с WPF-приложением? Казалось бы, у Arduino есть собственная среда разработки, своя экосистема, свои способы управления. Однако при создании серьезных проектов. . .
Звёздная пыль
kumehtar 20.06.2025
Я просто это себе представляю: как создавался этот мир. Как энергия слипалась в маленькие частички. Как они собирались в первые звёзды, как во вселенной впервые появился Свет. Как эти звёзды. . .
Создание нейросети с PyTorch
AI_Generated 19.06.2025
Ключевое преимущество PyTorch — его питоновская натура. В отличие от TensorFlow, который изначально был построен как статический вычислительный граф, PyTorch предлагает динамический подход. Это. . .
JWT аутентификация в ASP.NET Core
UnmanagedCoder 18.06.2025
Разрабатывая веб-приложения, я постоянно сталкиваюсь с дилеммой: как обеспечить надежную аутентификацию пользователей без ущерба для производительности и масштабируемости? Классические подходы на. . .
Краткий курс по С#
aaLeXAA 18.06.2025
Здесь вы найдете все необходимые функции чтоб написать програму на C# Задание 1: КЛАСС FORM 1 public partial class Form1 : Form { Spisok listin = new Spisok(); . . .
50 самых полезных примеров кода Python для частых задач
py-thonny 17.06.2025
Эффективность работы разработчика часто измеряется не количеством написаных строк, а скоростью решения задач. Готовые сниппеты значительно ускоряют разработку, помогают избежать типичных ошибок и. . .
C# и продвинутые приемы работы с БД
stackOverflow 17.06.2025
Каждый . NET разработчик рано или поздно сталкивается с ситуацией, когда привычные методы работы с базами данных превращаются в источник бессонных ночей. Я сам неоднократно попадал в такие ситуации,. . .
Angular: Вопросы и ответы на собеседовании
Reangularity 15.06.2025
Готовишься к техническому интервью по Angular? Я собрал самые распространенные вопросы, с которыми сталкиваются разработчики на собеседованиях в этом году. От базовых концепций до продвинутых. . .
Архитектура Onion в ASP.NET Core MVC
stackOverflow 15.06.2025
Что такое эта "луковая" архитектура? Термин предложил Джеффри Палермо (Jeffrey Palermo) в 2008 году, и с тех пор подход только набирал обороты. Суть проста - представьте себе лук с его. . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2025, CyberForum.ru