Форум программистов, компьютерный форум, киберфорум
С++ для начинающих
Войти
Регистрация
Восстановить пароль
Блоги Сообщество Поиск  
 
 
Рейтинг 4.96/47: Рейтинг темы: голосов - 47, средняя оценка - 4.96
 Аватар для gromo
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225

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

04.06.2016, 20:57. Показов 9812. Ответов 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
07.06.2016, 04:44  [ТС]
Студворк — интернет-сервис помощи студентам
Цитата Сообщение от 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";
}
И в итоге (замерял сразу после перезагрузки компьютера, для чистоты):
Code
1
2
3
4
5
6
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:
Code
1
2
3
4
5
6
File size: 688885746 bytes
HW concurrency: 2
+-----------------------------------------+
|    Unique elements:    < 1000001 >
|    Elapsed time:       < 20435ms >
+-----------------------------------------+
Что ж, неплохо, я думаю. Почти 100% прирост в производительности. Вот только Boost::Spirit я не пробовал. Может быть кто сведущий и напишет парсер простых целых чисел.

Какие будут замечания к коду по параллельной обработке ? Сам вижу, что подход топорный у меня.
0
 Аватар для Nosey
1379 / 406 / 144
Регистрация: 22.10.2014
Сообщений: 872
07.06.2016, 12:58
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.
1
 Аватар для avgoor
1550 / 877 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
07.06.2016, 13:55
Цитата Сообщение от gromo Посмотреть сообщение
Может быть кто сведущий и напишет парсер простых целых чисел
Так вам парсер целых чисел нужен был?
0
 Аватар для gromo
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
07.06.2016, 14:05  [ТС]
avgoor, ну просто для теста и для простоты. А так строки могут какие-угодно.
0
 Аватар для avgoor
1550 / 877 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
07.06.2016, 14:19
Цитата Сообщение от gromo Посмотреть сообщение
А так строки могут какие-угодно.
Я ж об этом спрашивал. Алгоритм обработки данных зависит от вида самих данных. Если строки в основном уникальные (редко повторяются) - быстрее будет загнать их все в вектор, отсортировать, и посчитать (ну, или erase+unique).Тестовые данные должны отражать реальные. Мне сложно представить реальную задачу, где есть файл с полумиллиардом строк, длинной в 4 байта.
1
 Аватар для gromo
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
13.06.2016, 14:29  [ТС]
Цитата Сообщение от 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 секунд. Поразительно!
0
 Аватар для Nosey
1379 / 406 / 144
Регистрация: 22.10.2014
Сообщений: 872
13.06.2016, 15:04
Цитата Сообщение от gromo Посмотреть сообщение
А разве не тратятся дополнительные ресурсы на приведение std::string в int? Я всегда думал, что вариант со string будет быстрее чем int.
(*1) Тратятся, но копирование инта всяко быстрее строки + рассчет хэша для инта - это сам инт.
Т.е. работа при добавлении элемента std::unordered_set<int> при отсутствии балансировки (reserve был вызван) примерно следущая:
Code
1
2
3
4
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 секунд. Поразительно!
Как я сказал это за счёт инта, сделаете в стринг и отработает за очень близкое время к вашему алгоритму.
1
 Аватар для gromo
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
13.06.2016, 15:17  [ТС]
Nosey, спасибо за разъяснения!
Немножко не по теме: стоит ли включать в работу главный поток наравне с рабочими? То есть делегировать часть работы главному потоку, а не оставлять его спать и ждать пока приджоинятся все "работяги"?
Я считаю, что на современных системах это не критично и не принесет выигрыша в производительности, так как работают сотни потоков и десятки процессов, и то, что мы завели один лишний поток — сути дела не меняет.
0
 Аватар для Nosey
1379 / 406 / 144
Регистрация: 22.10.2014
Сообщений: 872
13.06.2016, 15:29
Цитата Сообщение от gromo Посмотреть сообщение
Немножко не по теме: стоит ли включать в работу главный поток наравне с рабочими? То есть делегировать часть работы главному потоку, а не оставлять его спать и ждать пока приджоинятся все "работяги"?
Я считаю, что на современных системах это не критично и не принесет выигрыша в производительности, так как работают сотни потоков и десятки процессов, и то, что мы завели один лишний поток — сути дела не меняет.
Да, это все мелочи редкостные, если учитывать что у ОС могут "закончиться потоки"
http://en.cppreference.com/w/c... ead/thread См. раздел "Exceptions".
1
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
inter-admin
Эксперт
29715 / 6470 / 2152
Регистрация: 06.03.2009
Сообщений: 28,500
Блог
13.06.2016, 15:29

Реализация класса 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 ?
Собственно как? :)


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

Или воспользуйтесь поиском по форуму:
29
Ответ Создать тему
Новые блоги и статьи
Программный домашний кинотеатр
russiannick 27.09.2026
Сподобился на программный домашний кинотеатр. В качестве ЯВУ по традиции выбрал js. В помощники взял Яндекс-Алису. Было создано три зала на разные интересы. исторические и ретро сериал Хичкок. . .
Беседа с ИИ о программистах, недопускающих к созданию и правке кода генеративные ИИ и причины этого
zorxor 21.09.2026
Раньше я радовался или получал некоторые эмоции, пусть небольшие, но всё же, от самого процесса написания кода, рекомпиляции и запуска, видя постепенное развитие программы и прочее. А теперь лень. . .
Мобильное приложение ColorStep
pavlinmavlin 17.09.2026
Реализовал приложение Красный, Зеленый, Синий в Unity3d + c#. Название изменил на ColorStep. Приложение прошло модерацию и теперь доступно для скачивания. Делал его сам, шаг за шагом — и вот,. . .
Запрет дублирования строк в табличной части
Maks 13.09.2026
Реализация из решения ниже выполнена на нетиповом справочнике "Нормы ТО" с табличной часть "Виды ТО", разработанного в КА2, со следующими реквизитами: - ВидТО (СправочникСсылка. ВидыТО); - ВидГСМ. . .
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр.
Jin X 06.09.2026
Скрипты Tampermonkey для CyberForum, ChatGPT, Claude и пр. Работая с форумом и нейросетями в браузере часто хочется что-то подкорректировать или добавить какого-то функционала. Ниже прикреплён. . .
Программа опроса у.з. расходомера SLS-720F
Argus19 02.09.2026
Программа опроса у. з. расходомера SLS-720F Программа опрашивает один раз в минуту три ультразвуковых расходомера SLS-720F через интерфейс RS-485 по протоколу Modbus RTU. Опрашиваются регистры. . .
Hyper-V: Компьютер должен поддерживать доверенный платформенный модуль 2.0.
Maks 31.08.2026
При установке Windows 11 на виртуальную машину Hyper-V 2-го поколения вылезла такая ошибка: Решение: в параметрах виртуальной машины, в разделе "Безопасность" (Security) активировать флаг. . .
Архитектура биовида Стива в Майнкрафте: Зачем бонобо кубический каннибализм
anaschu 30.08.2026
Кубический Вагинокапитализм в Minecraft: Математический инвариант ОДУ и рок Стивов-бонобо Главная задача разработанной «Модели Всего» — наглядно продемонстрировать наличие системной «судьбы». . .
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin
Copyright ©2000 - 2026, CyberForum.ru