maytonDima T,

Смотрите. Я готов добавить ещё одну графу мультипоточности в наши будущие бенчмарки..

Но будем ли мы все алгоритмы укомплектовывать этой опцией?
Сомневаюсь что все будут иметь многопоточный вариант.
Думаю для тестов основным надо считать однопоточный вариант. Его и мерить.

Если кто предложит дополнительно многопоточный - можно тоже померить. Доп.графы не надо, достаточно просто пометки MT в названии алгоритма.

Bred eFeMИтак, без оптимизаций тайминги на паспортах такие (~3GHz):
(да, там нет повторов - совсем забыл, что отключал инкремент позиции при чтении файла)

- загрузка и заполнение структуры (много реаллоков - буду тюнить) ~40c;
- отсеивание дублей по второму 32 битному хешу ~10c;
- память 2,5GB

много/мало - как у вас? )
Для паспортов мне 600 Мб требуется.

Выше обсуждали что в процессе надо контролировать расход памяти, в итоге остановились на опросе ОС занимаемой процессом памяти mem_used.h
Т.к. теоретически может попасться такой файл что съест всю память. Тогда или прога свопиться начнет или ОС перестанет выделять память для твоего процесса, т.е. вылет с исключением std::bad_alloc.

PS У mayton`а есть супер-файлик 20783786

maytonDima TPS У mayton`а есть супер-файлик 20783786
Кстати я-бы проверил в сколько максимальное количество buckets может работать стандартная
реализация std::*_map.
Нам хватит


http://www.cplusplus.com/reference/unordered_map/unordered_map/max_size/

maytonМожет мы укрупним единицу аллокации? Пускай там лежит пара строк.
ИМХО Так мы до самодельного архиватора дойдем :)

Нашел еще одно тормозное место: fwrite(). Заменил на блочную запись ( block_write.h ), стало чуть быстрее: паспорта были 18 сек. стали 14 сек.

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

Dima TmaytonМожет мы укрупним единицу аллокации? Пускай там лежит пара строк.
ИМХО Так мы до самодельного архиватора дойдем :)
Размышляю над архиватором, возможно оно может пригодится для получения хэша: строим словарь, общий для всего множества, и далее начало пожатой строки используем как хэш. Например паспорт скорее всего целиком в 32 бита поместится после сжатия: 105 млн. строк в 344 Мб, т.е. ~3.3 байта на строку. С ripe.db статистика похуже: 180 Мб (пожал только уникальные) для 30 млн. строк, т.е. 6 байт на строку.
Кроме того можно сжатыми строками оперировать, например во временные файлы их писать. Текст жмется в 4-6 раз.

Правда тут есть большой минус в том что первый проход надо будет делать для построения словаря.

Написал многопоточный вариант, правда не полноценный, а только однопроходную часть, алгоритм тот же, но с акторами :) Сделал чтение блоками 256 Kб, запараллелил разбор блока на строки и расчет хэшей строк, остальное как было.
Исходники завтра покажу, после причесывания.

Результаты такие (оба варианта работали в одинаковом режиме, т.е. в один проход чтения файла)

I7-6700K, DDR4, 4 ядра без HT, 4 потока:
ФайлОднопоточноМногопоточнопаспорта (1.2 Гб)12.9 сек.4.1 сек.ripe.db (5.2 Гб)24.4 сек.7.6 сек.
I7-3770K, DDR3, 4 ядра c HT, 8 потоков
ФайлОднопоточноМногопоточнопаспорта (1.2 Гб) 15.9 сек.5.6 сек.ripe.db (5.2 Гб) 27.9 сек.9.2 сек.

PS Т.к. памяти у меня много и все там закэшировано, то максимальное чтение удалось выжать 2+ Гб/сек. Это просто чтение, разбор на строки, подсчет количества строк и контрольной суммы XOR(хэш строк). Полноценная работа 500 Мб/сек максимум, т.е IO ни при чем, есть куда тюнинговать алгоритм.

PPS Амдал не дает больше чем в 3 раза ускориться :(

Холодный старт. Перезагрузка перед каждым замером.

I7-3770K, DDR3, 4 ядра c HT, 8 потоков, SSD SATA3 (SanDisk SDSSDHII120G)
ФайлОднопоточноМногопоточноПодсчет строкпаспорта (1.2 Гб) 17.7 сек. 6.1 сек.3.4 сек.ripe.db (5.2 Гб) 29.5 сек. 18.3 сек.15.0 сек.
Третья колонка: просто чтение, разбор на строки, подсчет количества строк и контрольной суммы XOR(хэш строк).

Залил исходник к себе в акторы uniq.cpp , как еще один пример использования акторов.

Дублировать в местную репку? Он не полностью дублирует однопоточный вариант, не стал делать контроль за памятью и переключение на "план Б" с несколькими проходами когда памяти не хватает.

Залил uniq-mt.cpp
Бинарники тоже.