Сделал блочное чтение. Быстрее стало в 2 с лишним раза. Кто хочет - можете пользоваться. Класс block_read.h

Зафиксировал. Там два проекта:
uniq-mem - просто добавляет в unordered_set<string> и в конце скидывает его в файл.
uniq-crc - с биткартами и CRC32

По скорости одинаково работают.

maytonПохоже Дима сделал аж 2 реализации. Одну из них я выше называл Naive Hash-table(NHT).
Давно ее сделал 20770314 , просто оформил в проект, чтобы было с чем результаты сравнивать.

После замены fgets() на блочное чтение уникальных строк в ripe.db стало чуть меньше, как понял fgets() 0xA на конце оставляет и еще что-то есть.

SiemarglDima T,

Не сходится с моим результатом 20772846

Или может файл поменялся. Надо исходников Md5 сверять
Я давно заметил что не сходится, потом присмотрелся:
у тебя 143393110 строк в файле, у меня 143404062

Файлы разные.

ИМХО надо по одним и тем же файлам все прогонять. Я для того и сделал второй вариант чтобы было с чем сравнить.
И у меня еще нюанс: пустые строки игнорируются, т.е. любая комбинация 0xA и 0xD считается одним переводом строки.

SiemarglDima T,

Не сходится с моим результатом 20772846

Или может файл поменялся. Надо исходников Md5 сверять
Прогнал твой код со своим файлом, сходится
Мой результат: Time 50668 ms. Total unique 26511418 rows.
Твой: number of unique strings: 26511419 Время 176 сек.
Разница в 1, т.к. я пустые строки пропускаю.

PS Ты бы добавил передачу имени файла в параметрах и сохранение результата

Siemargl, заменил в твоем коде map на unordered_map время упало с 176 сек. до 122 сек.

Еще немного затюнинговал: Заменил crc32() на хэш попроще.
ripe.db проходит за 40 сек вместо 50 :)

mayton, затестил триткарту 20780617 , скорость чуть-чуть выше, хоть у проца меньше промахов кэша, но доп.расчеты съели сэкономленное время.
Не буду ее добавлять, т.к. по результату первого шага удаляется первая биткарта (512 Мб), а на втором шаге используется только вторая.
От второй биткарты тоже не буду избавляться, т.к. при ее использовании 2-3 шаги можно делать частями если за раз не проходит.

mayton, мой обнови. Добавил однопроходный вариант с более агрессивным расходом памяти. ripe.db за 26 сек.
Если будет вылетать, то двухпроходный запускается с доп.ключом /L.

maytonDima T, ого. С вылетанием - это плохо. С точки зрения конечного пользователя. Может задать
какую-то логику. Если превышаем 80% от доступной памяти - то откат агрессивного алгоритма
и старт экономного.

Падающие алгоритмы мне будет сложно тетсировать. Что обрабатывать? Аварийное завершение.
Синий экран. Вобщем у меня не получится автоматизация тестирования.
Поразмышлял про ключик. Он не спасет, в обоих случаях в памяти будет биткарта + map из повторившихся строк. В первом еще set из строк на хэше которых коллизия была, но их не много.
В общем чтобы ключик спасал надо вариант с ключиком допрописывать на еще 2+ проходов.
Добавлю обработку исключений при нехватке памяти.
maytonПо поводу твоего блочного чтения. Я не совсем понял зачем там копирование памяти.




Мне казалось блочное чтение строк можно реализовать без него. Или я ошибаюсь? ХЗ.
Логика такая: есть буфер 1 Мб например, прочитали туда 1Мб и парсим последовательно: наткнулись на конец строки - отдали на обработку и т.д., а когда наткнулись на конец буфера и в нем только начало строки, то начало строки копируется в начало буфера, затем буфер дочитывается из файла.
Это только на концах буфера происходит, можно просто размер буфера увеличить чтобы это реже происходило.

maytonDima TЛогика такая: есть буфер 1 Мб например, прочитали туда 1Мб и парсим последовательно: наткнулись на конец строки - отдали на обработку и т.д., а когда наткнулись на конец буфера и в нем только начало строки, то начало строки копируется в начало буфера, затем буфер дочитывается из файла.
Это только на концах буфера происходит, можно просто размер буфера увеличить чтобы это реже происходило.
Для твоего алгоритма (update CRC32) не обязательно подавать на вход целую строку. Можно в 2 шага.
Update head, update tail.

Тебе целая строка может только понадобиться на только в той фазе когда ты ее кладешь в хеш-таблицу.
Согласен, но я руководствуюсь принципом изолированности уровней: нижний не знает что делает верхний. Нижний читает, верхний считает.
Задача нижнего выдать строку целиком. Так проще, иначе в коде каша получается: нижний должен сообщить что это кусок, а не целое, верхний должен это как-то обрабатывать. И выигрыша в производительности тут доли процента, а то и наоборот потери будут из-за лишних проверок целая/нецелая.

PS Добавил обработку исключений нехватки памяти. Пока просто останов и удаление неполного результата.

maytonПоследний тестовый файл я добавляю к исследованию. 13Гб в открытом виде.
1.2 миллиарда строк. По некоторым соображениям я не буду давать на него
ссылки в форуме (сами понимаете, есть действующие правила). Но дам в личку
если кому надо.
Думаю мой код его за один проход переварит даже на твоем ноуте, но если ты сделаешь


то на superbig.txt вылетит.

Завалялся файлик с утерянными паспортами 1.2 Гб, для эмуляции недостатка памяти скомпилировал в x86, он обработался, там 100% уникальных строк, пришлось его удвоить чтобы вылетать начало. В общем чем больше уникальных строк, тем меньше надо памяти.

Пока думаю что делать если память кончилась, надо как-то задействовать наработанное и перейти к плану Б.

PS Интересное наблюдение: Win7 в диспетчере задач показывает *32 на x86 процессах, а Win10 - нет. Похоже MS передумал уходить от x86.

maytonDima TPS Добавил обработку исключений нехватки памяти. Пока просто останов и удаление неполного результата.
Тут вот какое дело. Я думаю что исключение нехватки памяти это очень ПОЗДНЕЕ событие.
Я про это тоже думал. Как вариант кидать исключение при выводе статистики:


в этот момент оценивать скорость обработки, и если она упала в несколько раз, значит начался своп, можно кидать исключение. Или просто ограничится x86 процессом где 2 Гб наше все.

maytonМой поинт в том чтобы не ловить эти грабли а заведомо до запуска утилиты оценивать свободное
место.
Тут проблема оценивать расход памяти в ходе расчета: std::string забирает доп. память для служебной инфы, контейнеры забирают под массивы хэшей/деревья и т.д. и т.п. Например мой код с unordered_set<string> на ripe.db (проект uniq-mem) съедает 4 Гб оперативки, хотя результат всего 1 Гб.
Расход памяти никак не оценить изнутри, т.е. средствами языка. Можно конечно средства ОС вызывать, но это как-то не спортивно.