383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
|
||||||
1 | ||||||
Почему std::string_view МЕДЛЕННЕЕ, чем std::string?04.06.2016, 20:57. Показов 8326. Ответов 28
Метки нет (Все метки)
Всем привет!
Нужно найти количество уникальных строк в больших текстовых файлах (размером до нескольких гигабайт). Почему в нижеследующем коде результат выполнения со string_view , который не копирует элементы, значительно медленнее, чем в случае сo string ?!
0
|
04.06.2016, 20:57 | |
Ответы с готовыми решениями:
28
ошибка error: cannot convert 'std::string {aka std::basic_string<char>}' to 'std::string* {aka std::basic_stri На основе исходного std::vector<std::string> содержащего числа, создать std::vector<int> с этими же числами Запрошено преобразование от ‘const std::string*’ к нескалярному типу ‘std::string’ Реализация класса MyString. Стандартная библиотека, std::string, std::vector |
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 |
Возможно, потому что какая-то ленивая скотина сделала std::hash<std::string_view> через предварительное преобразование std::string_view в std::string. Это надо в потрохах копаться, чтобы разобраться что именно тормозит.
Потеряет последнюю строчку, если там '\n' нет. 1) Можно - тыкаетесь в середину файла, находите ближайший '\n', все что слева от '\n' в один поток, все что справа в другой. 2) Станет только хуже, так как map это красивая обертка вокруг чтения данных с диска. А диск (если не SSD), вообще говоря, произвольный доступ поддерживает хреново и от скачки по файлу вперед-назад (один поток читает начало, другой середину) начнет тормозить.
0
|
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
|
|
04.06.2016, 22:01 [ТС] | 4 |
В моей стандартной библиотеке я копался, без преобразования судя по всему. С
std::string по такому же принципу хеш считается.Это понятно, я в том плане, что \r\n и \n будут трактоваться по-разному, если mmap открывает файл в бинарном режиме. (Если конечно qt-обертка не добавляет такое преобразование, ведь QFile я открывал в режиме QFile::Text)Ну не только в красоте дело, ведь при маппинге данные с файла считываются блоками размером со страницу памяти + copy on write
0
|
2780 / 1933 / 570
Регистрация: 05.06.2014
Сообщений: 5,598
|
|
04.06.2016, 22:07 | 5 |
Тогда, возможно, дело в прижимистом алгоритме мапинга файла - когда вы загружаете тысячную строчку, он выкидывает из памяти первую. Типа, все равно же копия на диске есть, чего место тратить? А потом std::unordered_set пытается первую строчку прочитать еще раз и приходится лезть за ней на диск.
Просто в строчку попадет этот \r и всего делов.
1
|
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
|
|
04.06.2016, 22:30 [ТС] | 6 |
Распараллеливать ввод/вывод, конечно же, плохая задумка (во всяком случае, если нет SSD, как вы уже заметили). А если сосредоточиться на хеш-таблице? Есть ли эффективные алгоритмы слияния двух хеш-таблиц? Для случая нескольких потоков, заполняющих разные хеш-таблицы, а потом главный поток их мерджит?
0
|
2780 / 1933 / 570
Регистрация: 05.06.2014
Сообщений: 5,598
|
|
04.06.2016, 22:55 | 7 |
Вам для 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 |
Ну в среднем файлы по 2Гб и где-то 15 000 000 уникальных строк в них есть.
А вот с математикой я не сильно дружу
0
|
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
|
|
05.06.2016, 00:18 | 10 |
А всего строк сколько?
Добавлено через 4 минуты Вот это зря. Теория информации - развитие теории вероятностей.
0
|
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
|
|
05.06.2016, 01:53 [ТС] | 11 |
0
|
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
|
|
05.06.2016, 02:08 | 12 |
0
|
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
|
|
05.06.2016, 02:11 [ТС] | 13 |
avgoor, вы спрашивали
Так вот я и ответил сколько их ВСЕГО. Да и какое это имеет отношение к тому, что string_view не дает прироста производительности, а наоборот ухудшает? У вас есть соображения по этому поводу?
0
|
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
|
|
05.06.2016, 02:30 | 14 |
UPD: поправка: уникальных - лишнее.
Добавлено через 15 минут Да, есть. Попробуйте сначала прочитать ваш файл целиком в память (вместо mmap-а) и парсить в памяти. В этом случае разница должна быть в пользу string_view, потому, что ускорение на стрингах вы получаете за счет того, что данные находятся в памяти и обрабатываются там. А mmap именно, что отражает файл на адресное пространство, а не выделяет память и читает туда файл целиком (как бы вы сами написали mmap, учитывая совместный доступ для которого он и есть).
0
|
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
|
|
05.06.2016, 02:44 [ТС] | 15 |
Сразу так и было реализовано. И если читать в память все целиком, то и парсить уж не надо,
std::getline или std::basic_istream::operator>> сделают всю работу. С использованием mmap производительность выросла на 12%.Единственным способом дальнейшего повышения производительности вижу распараллеливание считывания из файла при наличии SSD и параллельной обработки нескольких хеш-таблиц с последующим их слиянием.
0
|
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
|
||||||
05.06.2016, 02:58 | 16 | |||||
Вы неправильно поняли.
1
|
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
|
||||||
05.06.2016, 04:17 [ТС] | 17 | |||||
avgoor, а такой вариант я, как ни странно, еще не пробовал. Думаю сишный ввод/вывод уделает с++. Попробую днем, а то уже ничего не соображаю
avgoor, в общем не смог я уснуть не попробовав Такой код:
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 > +-----------------------------------------+
0
|
1550 / 875 / 179
Регистрация: 05.12.2015
Сообщений: 2,555
|
|
05.06.2016, 13:22 | 18 |
gromo, Тогда осталась только одна мысль: Т.к. вы писали, что у вас пол миллиарда строк на два гига - строки в среднем полусаются по 4 байта и срабатывает short string optimization, которая за счет локальности данных заруливает string_view.
А вообще ковырять надо. Сбросьте сюда генератор тестовых данных - поковыряюсь. Добавлено через 5 минут Не путайте теплое с мягким. Я отвечал на вопрос: Важна была именно относительная скорость string и string_view.
0
|
383 / 281 / 31
Регистрация: 04.09.2009
Сообщений: 1,225
|
||||||
05.06.2016, 17:11 [ТС] | 19 | |||||
avgoor, вообще важна именно итоговая производительность операции по обнаружению кол-ва уникальных строк в файле, — а что будет лежать в основе этого, какие-нибудь хитрые операции ввода вывода в сочетании с хранением в string или в string_view — дело десятое. Хотя я действительно чуть перепутал предмет дискуссии выше, прошу прощения.
Генератор самый простой:
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 | |
05.06.2016, 23:41 | |
Помогаю со студенческими работами здесь
20
Передача функции указатель на элемент std::vector<std::string> Операция std::cout для Объекта типа std::string No match for 'operator<' (operand types are 'std::__cxx11::string {aka std::__c Как правильно перевести std::wstring в std::string ? Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |