Comments 175
Кажется что лучше оставаться просто человеком разумным и грузить такие недоцсв в sqlite и делать дальше с данными все что хочется в среде которая для этого и была создана.
Попробуйте, напишите сколько времени это заняло
как люди разумные, само собой разумеем что файл уже лежит в клауде AWS на S3
Для десятигигобайтного файла:
CREATE TABLE test(prefix NUMBER, line TEXT);
.separator "."
.import files/out10Gb.txt test.separator '.'
.once files/sorted10Gb.txt
SELECT * FROM test ORDER BY line, prefix;$ time sqlite3 files/test.db < import.sql
real 2m30.515s
user 1m55.529s
sys 0m11.604s
$ time sqlite3 files/test.db < export.sql
real 3m51.936s
user 2m32.629s
sys 0m32.780sЯ позволил себе небольшую вольность в интерпретации условий и считаю, что в самих строках нет точек, и соответственно точку можно использовать как разделитель. Этого нет в тексте задачи, но так написан код генерации тестового файла.
ЦПУ и диск использует активно, RAM в пике меньше двух гигабайт, с диска читает (и пишет) порядка двадцати. Работает в один поток, так что с процессором помощнее возможно есть какие-то шансы на час для 100 Гб, но только с хорошим SSD.
Интересно использует ли sqlite UCA? И как я понимаю order by в отсутвие индексов делается в памяти. На 100гб это заработает вообще?
ну как минимум постгрес умеет сортировать со выгрузкой промежуточных данных на диск.
кишки не смотрел, думаю, что устроено примерно как в этой статье.
Конечно заработает. Откуда такое непонимание sqlite? Sqlite использует кэш и спиллит на диск, если место кончилось. Его не идиоты писали.
По умолчанию никаких UCA не используется. Лечится подключением ICU или самописки(философия sqlite - быть lite. Надо что-то выпендрежное, загружаешь плагин). Строки хранятся как юникод, но из коробки collationы лишь бинарный, rtrim('abc '='abc') и nocase для ascii. То есть никакой нормализации по умолчанию.
Надо сказать убийственное задание... Интересно, у них самих-то есть решение, укладывающееся в требуемые рамки?
Я думаю никто реально 100гб не сортировал
Наверняка есть. Вон автор заморочился и в итоге уложился чуть больше, чем за 30 мин. Хотя у автора тестовый стенд не хилый - а что там у интервьюеров за тестовое железо не известно - вдруг там жалкий Core i3 и 8Gb памяти (специально, чтобы не выезжать за счёт высокого производительного железа) - так там решение автора может за 1 часа и не уложиться! А интервьюеры хотели увидеть какой-то ещё более хитрый алгоритм - дабы тут есть куда копать ещё! Впрочем, может они на таком объёме и не тестируют вовсе - им важнее сделать грубую оценку на малом объёме и глянуть на сам код. Даже если алгоритм во времени не уложится - важно то, как программист мыслил, какую алгоритмическую архитектуру выстраивал. А мелкая оптимизация - ну у многих это может занимать месяцы анализа профилированной статистики и вытачивания узких мест.
Интересно - это тестовое задание для оффлайн решения, или надо было "на месте" у интервьюеров сделать за пару часиков (ну ладно - может часов за 8). Скорее всего для оффлайн - всё-таки тут даже тестовый прогон на полном объёме - это около часа (а то и больше) - на месте такую задачу можно решить только если заранее нечто подобное (очень близко по объёму данных) уже решать и отлично, на 5+ владеть пулом технологий! Впрочем когда ищут именно таких специалистов на з/п от полуляма деревянных - то могут и откровенно жестить и требовать решения "здесь и сейчас" за пару часиков - решат только те, кто 100% подобные задачи уже не раз решал! Но это поиск очень узкого и очень профессионального программиста - наверное же не синьор помидор разработчик на ступеньку повыше - всякие лиды и архитекторы
Упирается в основном в диск. Если запустить на ssd, то можно большой прирост получить даже на слабом железе.
SSD всего лишь в несколько раз медленнее оперативной памяти. Так что это читерство в некотором смысле. Ну примерно такое же, как взять сервер с большим кол-вом RAM (скажем, у меня есть доступ к нескольким серверам с > 100Гб оперативки).
У SSD ещё быстрый рандомный доступ. По сути можно просто отммапить файл и дальше сортировать "как будто в памяти", без всяких слияний.
С HDD такое не прокатит из-за медленных seek.
В оригинале тестовое задание было конечно для оффлайн.
Были некие хитро-выдуманные решения без учета особенностей сортировки строк.
Для чтения 100 Гб со скоростью 100 Мб/с (близко к скорость типичного HDD) потребуется почти полчаса. У вас SplitSort занял 11 минут, в три раза быстрее. Мне кажется, что тут что-то не так.
Также на одном из скриншотов вы показали, что у вас 64 Гб RAM. Не уверен, что при таком размере памяти тестирование на 100 Гб имеет смысл. Может быть хотя бы 500 Гб? Или запустить на машине с меньшим количеством памяти.
Современные диски на плоских файлах запросто выдают 200мб/с. Гигабайт за 5с, 100гб за 500с или 8,5 минут.
Чтение линейное. Скорость примерно 170мб/сек, примерно 10гб/мин. Кроме того кэш диска около 2-3гб. То есть последние 2-3 Гб не пишутся на диск сразу, а первые 2-3 Гб могут реально не читаться с диска.
У меня нет машины с меньшим количеством памяти.
На 100гб с dop=4 съело около 20гб оперативки. На машине с меньшим количеством ядер dop будет меньше и оперативки съест пропорционально меньше.
Кеш для чтения с диска не учитывается в потреблении памяти программой, но всё равно ускоряет работу. Не очень знаком с Windows кешами, если ошибся, прошу прощения.
Не учитывается. Виндоус умеет префетчить. Если вы читаете файл линейно, то Виндоус будет читать с диска в кэш в фоне без участия процессора. То есть в некоторых сценариях суммарный io может отказаться выше пропускной способности диска.
Все умеют префетчить. И без участия процессора диска работает с доисторических времён (все помнят PIO и UDMA настройки в биосе?).
Пропускная способность сата3 600мб/сек, что гарантировано выше любого современного ХДД.
Да, часть данных может застрять в дисковом кеше, под который отводится вся неиспользуемая память. Но на больших файлах этот кеш будет активно вымываться.
Это я к тому, что если узким местом является размер системного кеша, то просто потребления памяти программой недостаточно. А на вашей системе слишком много RAM.
Представьте, что первая половина была "как бы в памяти", а с диска читалась только вторая.
Размер системного кэша не является узким местом Обычно кэш заканчивается на 2-3 гб и дальше идет честная работа с диском.
Тут точно не скажешь. Эта виндовая служба любит отжирать под 80-100% от свободного места в оперативке под кэш (у меня прям сейчас 18 из 20Гб свободного съело). Правда, что оно туда кладёт - фиг его знает.
Современные ОС под дисковый кеш отдают всю доступную оперативку и быстро evict-ят эти страницы если они для дела нужны, так что если памяти 16Гб то кеш может быть сильно больше 2-3Гб.
Эти цифры по результатам забегов. Независимо от размеров чанков чтение шло именно с диска после обработки 2-3 гб исходного файла.
Столько лет живу и только недавно осознал что существует кэш чтения с диска ) Парсил 15Гб surefire репортов, надо было проанализировать статистику падения тестов, и очень удивился что после первого запуска маленькой программы на Java, последующие запуски занимают пару секунд. Ведь у меня диск даже читать с такой скоростью не способен, up to 3500 )
Современная винда на самом деле не очень охотно расстаётся с кешем, предпочитая вместо эвикта этих страниц выгрузить что-нибудь в подкачку или даже отказать программе в выделении памяти.
Одно время мне даже пришлось rammap -et на хоткей посадить чтобы побороть тормоза. Правда, последнее время я его не использую, не то всё-таки эвикт починили, не то отключение superfetch помогло.
Не уверен, что я достаточно внимательно прочитал статью, т.к. задача от меня крайне далекая (как и язык), и в код я даже не лазил. Но я так и не понял: а зачем сортировать 100-Гб файл? Почему нельзя сделать короткие хэши, оставив от каждой строки по несколько символов, и сгенерировать относительно небольшой временный файл, который будет содержать три поля:
1) короткий (не уникальный!) ключ сортировки текстовой части, сгенерированный по началу этого текста.
2) число, которое стояло в начале строки
3) номер строки в исходном файле
Причем, построение такого ключа - это самая важная и
самая творческая задача всей операции.
Так как эффективность сортировки почти полностью зависит от того, насколько удачно мы эту задачу решим.
А именно, тут надо достичь компромисса между длиной этого ключа (как можно меньше) и максимальным размером блока записей с одинаковым ключом. При этом уникальность ключей совершенно не обязательна! Нет никакой проблемы, если ключ будет одним и тем же для нескольких записей. Однако очень важно, чтобы максимальное число записей с одинаковым ключом для любого ключа было не очень большим. Попросту говоря, нам гораздо лучше иметь на весь файл всего 100 разных ключей, но чтобы каждый такой ключ "метил" 1/100 исходного файла, чем чтобы ВСЕ ключи, кроме одного, были уникальными и метили только одну запись, но зато этот единственный не-уникальный ключ метил половину записей в файле.
Ради построения такого ключа я бы при получении задания не поленился и уточнил примерную длину и характер строк в исходном файле: упорядочены ли они, сколько там символов, насколько там типичны почти одинаковые блоки и т.д., чтобы эти ключи как-то оптимизировать, если это возможно.
Понятно, что пп.1-3 делаются за один проход по исходному файлу, причем чтение будет последовательное и достаточно быстрое
На втором шаге сортируем наш tmp-файл любым способом. Возможно, он вообще в ОП влезет (если строки очень-очень длинные были). Но это по-любому должно быть намного быстрее, чем сортировка исходного файла - просто за счет его размера.
На третьем шаге формируем промежуточный частично отсортированный полный файл. Для этого у нас в нашем отсортированном tmp-файле есть номера исходных строк. Это будет второй полный проход по исходному файлу - правда, теперь уже с чтением нужной строки из рандомного места, а не с последовательным.
Ну и заключительный шаг - это сортировка тех блоков, внутри которых наш первоначальный ключ сортировки текстовых строк совпадает. Да, тут уже придется честно сравнивать строки. Но если хорошо подобрать компромиссную длину ключа, то размер этих блоков должен быть не очень большим, правда? И сортироваться они будут достаточно быстро.
P.S. Извините, если велосипед написал. Но мне показалось, что решение в статье хотя и эффективное, но достаточно сложное. А может, сперва стоило все же попробовать какую-нибудь элементарщину типа описанной? Или мое предложение заведомо не сработает? Это не стеб, мне правда интересно, так как я такие задачки никогда не решал и рассуждаю сугубо теоретически.
UPD: забыл уточнить, что мое решение будет работать только для строк фиксированной длины. Иначе с рандомным поиском нужной строки по ее номеру может возникнуть проблема. Но в статье сказано про строки "определенного формата", что на такую одинаковость как бы слегка намекает...
Интересная идея.
Это похоже на поразрядную сортировку, только мы сначала сортируем по префиксы, так чтобы индекс префиксов влез в память, а потом сортируем в строки в рамках совпадающих префиксов, потом пишем результирующий файл.
Вижу несколько слабых мест:
Первое это то, что такая сортировка не заработает если все строки одинаковы. Как вообще гарантировать что блок сортируемых строк с одним префиксом влезет в память?
Второе это нелинейное чтение исходного файла при формировании результата. Я делал вариант своей программы, когда ее сохранял строки в промежуточном файле, а сохранял только их смещение и длину в исходном (ветка only-keys). Я результата для 10гб не дождался.
От нелинейного чтения скорость падает на порядок
Достаточно вместо номера строки держать в ключе её смещение в файле, и проблем с переменной длиной не будет.
В общем, эта задача очень напоминает индекс нодлиста в фидонете, что заставляет предположить в её авторе фидошника :)
Я делал такое решение https://github.com/gandjustas/HugeFileSort/tree/only-keys
Можете запустить и сравнить производительность.
что заставляет предположить в её авторе фидошника :)
Как говорил Андрей Миронов, если Вы ясновидящий, предупреждать надо ;-)
Да, я застал ФИДО
но только и исключительно как тупой пользователь этих благ. Конкретнее говоря, я там искал партнеров, чтобы оптом купить походную пилу-цепь: они тогда только появились и в розницу было дорого, а оптом выходило кратно дешевле. Спасибо Андрею Ч., который все это организовал! (Кстати, он до сих пор регулярно организует так называемый ММБ - спортивное ориентирование на два дня и сто километров, которое дважды в год собирает от 1000 до 2000 участников).
А вообще, по моим скромным воспоминаниям, среди пользователей этих эх туристов (в том числе и IT-шников) было значительно больше, чем просто IT-шников (не-туристов).
Но может быть и аберрация личного восприятия, ведь тогда и экраны были зеленее, и клавиатуры щелкали громче, и подставка для кофе из компьютера выезжала быстрее.
P.S. Интересно, а какой процент современных IT-шников знает, для чего те компьютеры комплектовались подставкой для кофе? ;-))))
Первое это то, что такая сортировка не заработает если все строки одинаковы.
Разумеется. Вот поэтому я и написал, что было бы здорово получить какую-то априорную инфу про эти строки сразу при при получении тестового задания. По крайней мере, я бы попытался задать этот вопрос
Как вообще гарантировать что блок сортируемых строк с одним префиксом влезет в память?
Гарантировать - никак. Есть только шанс, вероятность которого, опять-таки, зависит от содержания текстов. Но если мы вдруг действительно этот шанс выиграем - то прирост скорости сортировки будет очень серьезный.
Но даже если не влезет, то мы все равно имеем альтернативу между сортировкой 100ГБ и 10ГБ. Мне почему-то кажется, что второе должно быть заметно быстрее ;-)
От нелинейного чтения скорость падает на порядок
Разумеется. Это один из главных вопросов моего варианта.
Я исхожу из того, что любая сортировка, выходящая за размер ОП, определенно потребует такого нелинейного чтения на каком-то этапе. Либо из одного большого файла, либо из множества маленьких. Ведь в итоге нам в любом случае придется переставлять строки, которые в исходном файле были весьма далеки друг от друга.
Конечно, при слиянии файлов они оба читаются последовательно. Но ведь таких слияний придется делать довольно много (каждую запись придется прочитать логарифм раз, причем чтение всегда идет сразу из минимум двух разных файлов, и на каком-то этапе каждый из них перестает помещаться в ОП). Если эти файлы вдруг окажутся на одной пластине, то головки буду дергаться не хуже, чем при рандомном чтении из одного мегафайла...
С другой стороны если наш большой файл раскидан по множеству пластин (дисковая подсистема сообразила, что мы собираемся замутить рандомный доступ, либо ей кто-то это каким-то способом подсказал) то, на мой непросвещенный взгляд, время доступа вроде бы должно уменьшаться пропорционально числу пластин? В общем, тут было бы интересно послушать специалиста.
Но в целом я совершенно согласен, что аргумент про рандомное чтение очень веский. Вопрос лишь в том, ставит ли он автоматически крест на идее такой сортировки или все-таки нет. Ведь и альтернатива - совсем не безупречное O(N).
Разумеется. Вот поэтому я и написал, что было бы здорово получить какую-то априорную инфу про эти строки сразу при при получении тестового задания. По крайней мере, я бы попытался задать этот вопрос
Нет априорной инфы, в этом и суть задачи. Оптимизация под частные случаи тоже так себе идея.
Но даже если не влезет, то мы все равно имеем альтернативу между сортировкой 100ГБ и 10ГБ. Мне почему-то кажется, что второе должно быть заметно быстрее ;-)
Но вы все равно сортируете N строк, только для ключа берете не всю строку, а часть. Такая оптимизация на практике не сильно полезна, так как сравнение векторов оптимизируется SIMD (по крайней мере в .NET) и обычная быстрая сортировка выигрывает у поразрядной.
Я исхожу из того, что любая сортировка, выходящая за размер ОП, определенно потребует такого нелинейного чтения на каком-то этапе.
Если вы посмотрите внимательно мой код - там нет нелинейных чтений. В этом и есть фишка алгоритма слияния, что он не требует рандомных чтений файлов. Во времена когда алгоритм придумывали еще не было префетчингов и реальное перемещение головки чтения-записи выполнялось за наблюдаемое глазом время.
Конечно, при слиянии файлов они оба читаются последовательно.
Только не оба файла, а все сразу. Сегодня у нас много памяти и мы удержать в памяти элементы из десятков и даже сотен тысяч файлов. Для сортировки 100гб (даже 500гб или 1ТБ) не требуется попарное слияние. Но даже при попарном слиянии все чтения и записи будут линейными
С другой стороны если наш большой файл раскидан по множеству пластин
Много пластин это из далекого-далекого детства. Сейчас подавляющее большинство дисков с одной пластиной, изредка с двумя. Описанная вами схема может быть в RAID 5 или 6 (не помню точно), но они очень непопулярны и вы скорее найдёте рейд-массивы где данные тупо дублируются.
В этом и есть фишка алгоритма слияния, что он не требует рандомных чтений файлов. Во времена когда алгоритм придумывали еще не было префетчингов и реальное перемещение головки чтения-записи выполнялось за наблюдаемое глазом время.
Это верно, но тогда у компьютера было много независимых устройств внешней памяти (дисков и лент). Алгоритм слияния изначально рассчитан на то, что каждый из кусков записывается на отдельный диск или ленту. В случае одного диска рандомные перемещения головки всё-таки будут, но не в пределах одного файла, а между файлами.
Много пластин это из далекого-далекого детства.
Спасибо за ликбез! Не знал. Я последний раз в этой теме копался примерно тогда же (с разницей в несколько лет), когда увидел свой первый персональный компьютер. Кстати, про него на днях написали вот в этой статье на Хабре. Он там на фото 1.
Оптимизация под частные случаи тоже так себе идея.
Ну я-то скорее оптимизировал под достаточно общий случай. Но вот в некоторых крайних случаях (все строки одинаковые и др.) мой алгоритм будет ужасен ;-)
Если вы посмотрите внимательно мой код - там нет нелинейных чтений.
(...)
Только не оба файла, а все сразу.
Да, конечно, тут я криво выразился. Я сперва хотел порассуждать про крайний случай попарных слияний, чтобы пояснить идею, а потом уже обобщать на слияние n файлов сразу. Но на самом деле это не важно. Ведь если у нас есть n небольших файлов на одной пластине, и нам надо поочередно взять по одной записи из каждого такого файла, то головки будут поочередно дергаться к каждому из этих файлов. Так как в кэше они, по условиям задачи, не помещаются. То есть несмотря на последовательное чтение каждого отдельного файла, у нас фактически будет то же самое чтение из рандомно расположенных мест на диске.
Так вот, мой вопрос сводился к тому, будет ли разница в скорости чтения
а) n таких записей из n разных файлов, и
б) при чтении тех же самых n записей из разных мест одного файла?
Интуиция мне подсказывает, что это может зависеть от настроек кэширования диска, но в общем случае принципиальной разницы быть не должно. Или нет?
А ведь прежде, чем проводить сортировку слиянием, нам еще надо каждый из этих n файлов рассортировать внутри себя... Так что какого-то однозначного выигрыша у алгоритма с предварительной сортировкой ключей я тут пока не вижу. Особенно если с ключами нам повезло, так что они влезли в ОП и рассортировалсь "бесплатно"
Ну я-то скорее оптимизировал под достаточно общий случай. Но вот в некоторых крайних случаях (все строки одинаковые и др.) мой алгоритм будет ужасен ;-)
Если вы хотите посоревноваться, то нужно сделать не хуже стандартного Array,Sort в среднем случае, то есть на случайных входных данных.
Ведь если у нас есть n небольших файлов на одной пластине, и нам надо поочередно взять по одной записи из каждого такого файла, то головки будут поочередно дергаться к каждому из этих файлов.
Это немного не так работает. Чтение в рамках одного диска контроллер выстраивает последовательно в рамках движения головок ( для HDD). Например вы заказываете чтение секторов 15, 8445, 2 (в любой последовательности), контроллер диска вам заполнит память для секторов 2, 15. 8445 именно в такой последовательности.
А ОС умеет делать pefetch: видя что вы читаете файл последовательно она в очередь чтения с диска ставит следующие сектора файла, независимо от того будете вы читать их или нет. Если вы перемещаете указатель чтения\записи файла (fseek), то весь префетч идет нафиг. И это работает для любого количества открытых файлов.
Поэтому есть разница - читать последовательно N файлов (работает prefetch), или читать рандомно из N мест одного файла. Первое будет быстрее.
Кроме того в моем коде при чтении из N промежуточных файлов используется большой прикладной буфер и реальное чтение доходит до диска один из 10 раз.
А ведь прежде, чем проводить сортировку слиянием, нам еще надо каждый из этих n файлов рассортировать внутри себя...
Они сортируются в памяти прежде чем записать на диск
Если вы хотите посоревноваться,
Спасибо за дружеский троллинг ;-) Я ведь написал, что я тут совсем-совсем крокодилмимо, и не претендую на работающее решение - для меня это скорее тренировка ума из серии Занимательные задачки. Один только
мой глюк
про перестановку строк (вместо перестановки указателей) уже однозначно показывает степень моей некомпетентности. Хотя справедливости ради,
в очень далеком DOS-прошлом
когда я сам писал сортировку за неимением подходящей функции в стандартной библиотеке, я все же сообразил, что сортировать нужно именно указатели, и даже сумел эмулировать их на фортране, где такого инструмента тогда еще не было. Но вот сейчас 100ГБ-файлы, заполнившие мою ОП в голове, вытеснили это знание куда-то в глубокий свопинг ;-)
Это я к тому говорю, что Вы не зря потратили свои силы на разбор моих ошибок: есть надежда, что я смогу чему-то на них научиться. Хотя конечно, умный человек пользуется для этого чужими ошибками... Возможно, и мои тоже кому-нибудь пригодятся?
Но в целом, довольно неожиданно (и приятно), что некоторые сугубо абстрактные идеи, появившиеся у меня "из первых принципов" (без малейших знаний предметной области), оказались не совсем уж бредовыми.
Так что спасибо за предложение, но я совсем не горю желанием войти в историю, как провокатор, вынудивший Вас всерьез (на уровне, близком к коду) разбирать нелепости моих предложений. Вы же не хотите заслужить репутацию человека, который конфеты у детей отбирает ;-) За проведенный здесь час я узнал про разные технические нюансы много больше, чем мог бы раскопать в интернете при самостоятельном обучении ;-) Спасибо еще раз за статью и индуцированное ей обсуждение, полезное и интересное для читателей с самым разным уровнем погружения в тему.
Но вы все равно сортируете N строк, только для ключа берете не всю строку, а часть. Такая оптимизация на практике не сильно полезна, так как сравнение векторов оптимизируется SIMD (по крайней мере в .NET) и обычная быстрая сортировка выигрывает у поразрядной.
Я, видимо, плохо описал свою идею. Если бы речь шла только об экономии на операции сравнения, то игра, вероятно, не стоила бы свеч (ведь потом все равно придется сортировать внутри блоков). Точнее, такая оптимизация была бы, наверно, полезна, но лишь для для некоторых наборов данных.
Но мне сперва показалось (прошу прощения, если я не прав - язык я не знаю, и код не читал), что в процессе сравнения Вы больше одного раза переставляете строки. Поэтому второй (или даже первый) краеугольный камень моей оптимизации состоит в том, чтобы избежать лишних манипуляций с длинными строками. Мое предложение сводится к тому, чтобы прочитать эти длинные строки один раз (последовательно) в самом начале работы, а затем основную часть операций проделать с гораздо более короткими эквивалентами этих строк. И получить выигрыш грубо за счет того, что эти новые строки намного короче. (Кстати, никто не мешает эти короткие строки отсортировать именно с помощью Вашего эффективного алгоритма вместо одной из стандартных библиотечных быстрых сортировок).
А уже на заключительном этапе, когда нам надо сгенерировать итоговый файл из длинных отсортированных строк, снова лезем в эти 100Гб и кошмарим диск и процессор ;-)
Как я понял из обсуждения, идея в целом получилась рабочая, но, конечно же, не бесплатная. Так как выигрыш в ходе основной сортировки потом аукнется необходимостью сортировки записей внутри блоков с одинаковым значением ключа у всех записей. И вот если в этот момент нам навстречу радостно выбежит наихудший возможный случай, то вся заранее выполненная работа окажется пустой тратой времени.
Впрочем, большого проигрыша тут тоже не должно быть, если, конечно, эту внутриблочную сортировку выполнять с помощью Вашего алгоритма, эффективно справляющегося именно с этой задачей?
Но мне сперва показалось (прошу прощения, если я не прав - язык я не знаю, и код не читал), что в процессе сравнения Вы больше одного раза переставляете строки.
Переставляются только указатели на строки.
А уже на заключительном этапе, когда нам надо сгенерировать итоговый файл из длинных отсортированных строк, снова лезем в эти 100Гб и кошмарим диск и процессор ;-)
это будет очень медленно.
для каждой строкой длиной в десятки байт вам нужен поиск места на диске, время которого на hdd грубо 10 мс, это время последовательного чтения 10 мегабайт.
то есть случайное чтение для переборки файла в нужном порядке оказывается на 5 порядков медленнее первоначального линейного!
Описанная вами схема может быть в RAID 5 или 6 (не помню точно), но они очень непопулярны
Raid 5/6 - это буквально любой SAN, программный или аппаратный. Т.е. все prod-сервера, включая бэкэнд облачного стораджа.
Много пластин это из далекого-далекого детства
А вот и нет. Современные многотерабайтные винты (16, 18ТБ) как раз содержат много пластин (самсунговские 8 и 9 соответственно).
Много таких дисков вы видели в настольных компьютерах?
Нагуглил старую уже спецификацию на Seagate Barracuda 2TB ST32000DM008 — а в ней тоже две пластины. Не совсем "много", но и не одна. Значит, 4-ТБ диск того же технологического уровня может иметь 3 или 4 пластины, а 4-ТБ диски люди используют и в домашних ПК.
Тоже вчера про это думал, но всё это упирается в простую истину - это не более чем попытка написать свою базу данных. Скорее всего это выйдет быстрее чем загнать всё в готовое решение так как будет чуть меньше ненужных телодвижений, но в конечном итоге всё упрётся в неэффективность такого решения из-за разности скорости последовательного и выборочного чтения.
И вот тут даже сверх быстрый ssd потеряет в своей производительности потому что его максимальная скорость достигается только во время последовательного чтения.
Из всего этого есть простой вывод, что стоить таблицы и создавать ключи выгодно только в том случае когда вы собираете данные, а если нужно работать с уже готовыми данными - вариантов не много.
Я начал думать примерно также: сначала, на первом проходе, мы строим индекс, который потом сортируем, а потом, используя индекс, читаем строки и пишем их в нужном порядке в выходной файл, дополнительно сортируя строки с одинаковым ключом. Проблема в том, что для сравнительно коротких строк (50-80 символов в строке) размер индекса будет сравнимым с исходным файлом. Я заложился на то, что индекс содержит - первые четыре байта строки (uint32), смещение от начала файла (uint64), длина строки (допустим, максимум 65535 - uint32), crc32 (uint32). Итого - 20 байт. Если средняя длина строки - от 250 байт и память 8 Гб, то максимум за 2 прохода мы получим количество необходимых блоков (уникальных ключей) и их размеры.
А вот дальше начинается самое интересное: нам надо как-то выбрать количество и размеры входных и выходных буферов, чтобы минимизировать количество операций чтения-записи на диск. Тут я слегка подзавис... Пока, навскидку, надо сначала найти ключи, для которых выходные блоки будут с 1) максимальным количеством строк и 2) максимальным объемом, потом отсортировать эти ключи, чтобы строки с ними попадали в минимальное количество входных блоков... после первой итерации отсортировать оставшиеся ключи...
В-общем, интуитивно все кажется понятным и простым, но при реализации, боюсь, возникнут нюансы. :) Интересно было бы посмотреть это все на какой-нибудь модели (если будет время).
0. 4 байта строки
1.1. если храните смещение, то длину строки не нужно. если длину, то смещение не нужно, но расчет смещение будет занимать заметное время. Допустим 8 байт.
1.2. длина строки (допустим, максимум 65535) это 2 байта
2. цифры до точки. 2 байта
Итого 8 или 14 байт. Если считать строки как досовый формат в 80 символов, то экономия в 5-10 раз, если как типичные предложения 400 символов, то экономия в 30-50 раз. И предположительно, можно будет легко отсортировать в памяти без всяких выкрутасов.
Да, я не понял, а зачем crc32?
Тоже сразу о таком варианте подумал. И строки можно не фиксированной длины, если сохранять значение их длины.
Далеко не первая статья на Хабре, посвящённая оптимизации сортировки. Но , наверное, первая, где и объёмы задачи хоть немного достойные BigData (хотя 100Гб это это ещё очень и очень условный BigData - тут бы хотя бы на порядок объёмы поднять - вот тогда точно будет BigData - и даже ещё вполне моделируемый в домашних условиях). Впрочем 100Гб - это не 100Мб - и тут уже начали проявляться всякие тонкие места работы с действительно большими данными, и началась соответствующая оптимизация.
Собственно в этой статье больше внимания как раз уделено как раз тонкостям обработки больших данных, чем оптимизации самой сортировки (где автор взял типовую реализацию). Это и хорошо и плохо. Но скорее хорошо - это более практическая задача, чем копания в тонкостях того, как ещё можно было бы оптимизировать алгоритм сортировки чанка под подставновку задачи. Этим эта статья хорошо себя противопоставляет предыдущую похожую статью, ссылку на которую хорошо было бы привести в начале - там акцентировали то, что ввод-вывод не узкое место и даже не добрались до распараллеливания - а в текущей статье автор как раз вывел это в узкое место - но понятно - объёмы данных то совсем иные.
К сожалению, в статье не нашлось места каким-то продвинутым логическим алгоритмам оптимизации сортировки и слияния - нет ни хешей, ни словарей, ни бинарных деревьев, ни статистических гистограмм. Хотя применение техники ключей сравнения тут многого стоят и, для решения задачи этого оказалось достаточно - цель то с лихвой досигнута.
Так же за боротом остались и нюансы аллоцирования непрерывных пространств памяти - в первую очередь для файлов - что тоже важно при работе с большими данными.
Ну и жалко, что автор так и не привёл описание тестового стенда - хотя с со скриншотов таскменеджера можно частино узнать что тестовая машина не хилая - 64Gb ОЗУ, 3.6Гц камень (под бустом аж до 4.75Гц - интересно это с каким охлаждением такой разгон в многопоточном приложении) с 8 ядрами. Тестовый диск то хоть HDD (хотя система вероятно на SSD стоит, интересно - временные фалы точно на HDD создаются - но наверное да - вроде бы в том же каталоге, где и исходный файл).
ОЗУ , конечно, распараллеленное приложение жрёт немеренно. Это и хорошо и плохо - с одной стороны при такой нагрузке на остальные ресурсы экономить память смысла нет, с другой - в серверном исполнении, при числе ядер от сотни общая нагрузка на ЦП уже будет не такая большая (всё упрётся уже, скорее всего в ввод-вывод), но тут уже две стратегии возможны:
Оставляем ресурсы ЦП для других задач - если это универсальный сервер с распаренными сервисами для многих - тогда и памяти им тоже бы лучше оставить побольше (хотя тут уже гибкое управление памятью нужно)
Либо наоборот - берём всё что есть - тогда можно сэкономить на операциях ввода-вывода и чанках - просто перенеся все файлы в память - коли всё влезет (ну или столько, сколько влезет). Постепенно высвобождая уже обработанную память (выделяя на её месте новые буферы - если все не влезли).
Хотя, при БигДата скорее всего не стоит рассчитывать на выделение памяти сразу подовсё. Как и при БигДата - скорее всего данные будут подавать и возвращаться (и даже скорее всего временно буферизироваться) на отдельных микросервисах - и эти операции заметно просядут по производительности. И тут нужна будет уже дополнительная оптимизация, чтобы сократить операции ввода вывода.
В любом случае статья получилась очень хорошая - автору большой респект
Предыдущую стать не читал, спасибо за ссылку, посмотрю, может чего добавлю.
Алгоритмическая оптимизация получилась в итоге одна - с использованием кучи для слияния. Все остальное не помогло, встроенная в .net сортировка достаточно хороша (в исходниках есть бенчмарки)
Также можно считать оптимизацией алгоритма формирование одного массива - ключа сортировки. Этот подход можно обобщить на любое количество ключей.
Расход памяти, если придется на практике сортировать такие объемы, зависит от степени параллелизма. Хочется быстро - сожрёт пару десятков Гб, хочется малый расход памяти - запускаем последовательно, сожрёт не более суммарного размера ключей и строк в чанке.
Над способами уменьшить расход в параллельном случае много думал, но вариантов не придумал совсем.
Над способами уменьшить расход в параллельном случае много думал, но вариантов не придумал совсем.
Способов знаю только два:
Ужимать сами данные в памяти - тут нужна хорошая функция построения весовоых коэффициента, и применения сжатия данных
Увеличивать повторное использование памяти - лично я не смог понять почему так быстро растёт память - при чанках в 50мб и где-то 32 потоках как возникают объёмы расхода памяти в более чем в 10 раз больше в среднем на поток.
В какой момент ужимать? Строки нам нужны в несжатом виде чтобы получить ключ, ключи нам нужны в несжатом виде чтобы сортировать. Сразу после сортировки данные ужимаются.
Память и так повторно используется за счет пула. В дебаггере показывает 9 буферов при dop=1. Объем может расти по следующим причинам: gc неохотно освобождает страницы для ОС, возможно за счет пиннига объектов для вызовов gc плохо освобождает память, память съедает BrotliEncoder, он реализован в неуправляемом коде.
Возможно все-таки последний запуск был при чанках по 100мб, потому что замеры я вставлял уже после написания статьи и код мог слегка отличаться.
Я думаю надо реализовать программу на языке без GC и сравнить результаты. Сам планирую это сделать на Rust.
Прочитал статью по ссылке, в целом она верная, но не полная.
Чтение данных редко оказывается узким местом, а вот запись часто. Операции в памяти можно распараллелить, а io нет. Поэтому в простых задачах io не будет узким местом, а сложных - будет.
тестовая машина не хилая - 64Gb ОЗУ, 3.6Гц камень (под бустом аж до 4.75Гц
Что тут "нехилого" ?
Мой домашний комп, самый обычный, куплен в начале 2017, имеет 4 ядра на 4,5ггц (7700к + настройка в биосе, обходящая ограничение турбобумста). 64гб.
Рабочий комп, собран в 2019. Имеет 6 ядер на 5ггц (8700к из 2017года + небольшой разгон)
Дома есть несколько двухпроцессорных серверов на БУ зионах. Сейчас стоимость процессоров + матплаты + памяти вряд-ли превышает 50тр.. Т.е.дешевле среднего нового ноутбука. А это 36 ядер на 3,3 и 256гб оперативки.
А в статье точно описана сортировка слиянием? Потому как то, что автор "отбросил идею нескольких прогонов для объединения блоков" выглядит как переход к совершенно другому алгоритму (причём с ограничением на размер данных, хотя и куда более мягкому, чем размер оперативной памяти).
P.S. Спасибо за ключи сортировки юникодных строк, может пригодиться.
Точно сортировка и именно слиянием. Просто изначально алгоритм описывался когда объем памяти был такой, что уместить все итераторы было невозможно.
В нашем случае даже при 10 000 чанков мы можем все итераторы уместить в памяти.
Можно считать это оптимизацией для частного случая, но этот частный случай на практике встречается чуть чаще, чем всегда.
Хорошее задание. Надо взять на заметку. Абсолютно бессмысленное с практической точки зрения (в смысле никто не скажет, что компания за бесплатно хочет решить техническую проблему), но сможет много поведать о кандидате - с разных точек зрения. Соискатели, держитесь!
были ли попытки сравнить производительность с GNU sort или чем-то таким? А ещё оптимизация чтения с диска, чтобы не возникало лишних аллокаций в ядре ОС - это вообще кроличья нора. Вот советую почитать, чтобы оценить ее глубину: https://itnext.io/modern-storage-is-plenty-fast-it-is-the-apis-that-are-bad-6a68319fbc1a
Пока не пытался гоняться с кем-то. Цель была решить задачу на моем железе с таким запасом, чтобы и более слабое железо тоже могло потянуть.
Статью прочитал, но, увы, не понял. Она про какие-то технологии, которыми я не владею. Да и для этой задачи обычных синхронных вызовов чтения\записи файла вполне достаточно на любой ОС.
Перевод вышей ссылки: https://habr.com/ru/company/vdsina/blog/530664/
Такие абстрактные задачи плохи тем, что всегда можно подобрать набор оборудования и внешних факторов, на котором текущий подход провалится, а соседний заработает.
await foreach (var (buffer, bufferLength) in compressToWrite.Reader.ReadAllAsync())
{
var tempFileName = Path.ChangeExtension(file, $".part-{tempFiles.Count}.tmp");Кажется, два потока могут создать временные файлы с одинаковым именем.
В целом — крутая статья и крутое решение.
Если сортировка строк подразумевает именно сортировку по коду каждого символа, то вроде как UTF-8 можно напрямую как массив байт сортировать - выйдет то же самое. Так можно избавится от лишних преобразований в string.
А если не подразумевает, то что вы делать будете?
В условиях не было сказано какая должна быть сортировка, поэтому может быть любая юникодная.
То это уже другая задача. В рамках этой можно и массивы сравнить.
Я не говорю, что вы неправильно делаете. Просто указываю на интересный момент.
В условиях не было сказано какая должна быть сортировка— не аргумент, потому что задание всегда можно уточнить. Если ответят, что без разницы — вы как автор кода вольны использовать любую, в том числе и побайтовую, в том числе в порядке, обратном алфавитному (потому что это абсолютно корректная сортировка, а «по возрастанию» нигде не сказано). А на простой аргумент
Не будет простых способов вернуться к UCA без потери быстродействия.есть простой ответ: новые ограничения = новая, другая задача.
Для работы с файлами таких размеров есть Memory-Mapped Files https://learn.microsoft.com/en-us/dotnet/standard/io/memory-mapped-files Уже давно с ними не работал, но раньше разница была значительной
Вы можете попробовать сделать свое решение на этих файлах. Возможно у вас получится быстрее. Правда непонятно какой это даст выигрыш при сортировке строк.
О да, в них ещё в книге системное программирование для windows рассказывали, как же давно это было...
Разница могла стать значительной при неудачном алгоритме работы с файлами – поскольку слой работы с ними отдаётся откуп системе (в разработку которой вложена уйма труда). Если нормально оптимизировать файловый ввод/вывод – разницы быть не должно.
Я кстати и на MMF пробовал делать этот вариант задания, получалось прилично медленее (~в 1.5-2 раза), чем с обычными файлами
В этой конторе наверно всему дают это задание. Мой рекорд 1гб за 85 секунд на i5 ноуте с ssd. Памяти почти не жрет, алгоритм простой, сортирует диском, работает со строками любой длинны. Для серверного решения где везде сейчас твердотелы - пойдет.
Можете название конторы озвучить?
1Гб это величина, которая влезает в ОП полностью, поэтому на таком объеме эффекты чтения с диска не проявятся.
Если честно я не помню название. Это было два года назад. 1 гб я сгенерировал сегодня просто на бенчмарк глянуть. Можно и 10 и 100 гб сделать и прогнать, не принципиально. Были идеи как улучшить используя хэш деревья, но я забил.
Я видел эту задачу на собеседовании в
https://www.altium.com/
примерно в 2019 году
А просто mmap и qsort работают на NVME SSD? Ну если строки сделать одной и той же длины в памяти.
Мой результат:
Исходный файл: 1 GB
Строк: ~19 млн (~ 55 символов в строке)
Использование памяти: 550 MB в пике
Время: ~24 сек разделение на партишены + 18 сек на слияние = ~42 сек
i7 (11й серии) с nvme SSD. Кода было значительно меньше, чем у топикстартера. span'ы не использовал, при чтении находил индекс разделителя и сохранял в памяти, а после использовал string.Compare с StringComparison.Ordinal и overload с указанием индекса начала сравнения и длины
Слияние сделал с помощью SortedSet<T>. Оффер получил, год там проработал :)
Для достижения наиболее высокой производительности на таком объёме сортируемых данных надо делать всё на массивах в статической памяти, никаких динамических структур.
А для начала надо уточнить, что в понимании заказчика значит “отсортировать файл”. Является ли файл с построенным индексом отсортированным, или надо его непременно переписать в другой последовательный файл?
Ну и очень многое зависит от характера данных, как верно заметили выше.
На входе файл где в каждой строке идет: xxxxxx. Yyyyyyyy, где xxxxxx - произвольное число, yyyyyyyyy - произвольный текст. Сортировка сначала по тексту потом по числу. Результат - отсортированный файл.
Для достижения наиболее высокой производительности на таком объёме сортируемых данных надо делать всё на массивах в статической памяти, никаких динамических структур.
Почему?
Является ли файл с построенным индексом отсортированным, или надо его непременно переписать в другой последовательный файл?
Надо переписать
Ну и очень многое зависит от характера данных, как верно заметили выше.
Характер данных - случайный
На управление памятью уходит много процессорного времени.
Случайный - это недостаточно точный ответ в данном случае. Надо понимать распределение.
Много это сколько? По сравнению с сортировкой и сжатием данных, не говоря уже о времени чтения-записи
На самом деле может случиться так (и чем больше отношение "размер файла" \ "доступная память" - тем вероятнее, что случиться), что несколько последовательных сортировок слиянием (так конечно проблема со сравнением UTF8-строк) будут работать быстрее, чем:
1. отсортировать всё в памяти
2. заполнить конечный файл ориентируясь на индексы в памяти.
Не скажу как конкретно у такой задачи, но "в целом" можно ориентироваться на
- 200-400 МБ/сек поточного чтения
- 300-450 МБ/сек поточной записи (разница от того, что часто чтение "не совсем" поточное, а асинхронка файлового кэша делает запись совсем поточной)
- 150 IO*opers / sec
Но в целом всё зависит от данных.
На вашем решении вы уложились, если бы было "околонулевой" шанс совпадения строк - сортировать поточно наверное (с мапингом файлов в память) наверное было бы оптимально.
На HDD скорость чтения почти в 10 раз превышает скорость записи.
Извините где и как такого добиться?
Единственное что приходит в голову - черепичные диски (ну или на нормальных дисках прям какая-то жуткая ошибка программиста)? https://habr.com/ru/post/529860/
Потому, как с точки зрения общего случая - нормальная кэшируемая "достаточно поточная" запись в ФС то, что вы написали противоречит и опыту, замерам и разумным объяснениям.
Если дописать в конец полученного массива байты числа, стоящего в начале, то мы можем всю сортировку свести к сортировке байтовых массивов.
Разве это будет правильно работать "most significant digit (MSD) or least significant digit (LSD)" [b, ba, c, d, e, f, g] [1, 10, 2, 3, 4, 5, 6, 7, 8, 9]
Т.к все строки из небольшого пула, можно засунуть их в небольшую структуру данных и отсортировать потом.
Написал на плюсах, сейчас посмотрю сколько работает, на 10Gb всего 100 секунд cpu time. Так как исходные строки длинные (avg=231), их таким образом мало (всего 463'523'186 у меня), можно попробовать поместить в память, у меня это tuple<u64,u32,fixed_string<10>> (24 байта) на строчку (это 10% от данных). Продублировал числовой ключ в строке что бы вывод был побыстрее.
P.S.
код итого 24 минуты. В любом случае явно упирается в диск.
Это все потому что у вас вместе с N*logN операций в памяти появились также N*logN операций с диском.
Файл вы читаете не UTF8 и UCA не используете
По диску только 2(3) прохода, NlogN+NlogM только в памяти. NlogN операций с диском я бы не дождался и за 10 часов. 100Gb*2/(170Mib/s) - это уже 20 минут.
Сравниваю действительно побайтово, у файлов от автора явно какие-то проблемы с кодировкой, source.txt вообще в cp1251. Забавно что сравнение с учетом utf вообще не повлияет на скорость, так как сравниваться будет очень маленькое число уникальных строк (all_keys=16137) Место для компаратора тут, поленился скачивать библиотеку только из-за того что это ни на что не повлияет.
string_view при сравнении у вас обращается к области памяти в mm-файле. А это, видимо, создаёт обращения к диску. Не каждый раз конечно, но порядок обращений O(N * logN).
Никаким други способом я не могу объяснить такое время работы. Кстати посмотрите прямо в таск менеджере количество байт ввода-вывода для процесса. Если превышает объем файла, то это плохо.
изначально действительно было так
map<string_view, u64> all_keys;
И в мапчике лежали вьюхи на случайные (скорее всего в пределах первых мегабайт, но всё равно) части диска, сейчас происходит копирование.
map<string, u64, less<>> all_keys;
auto get_key(string_view key) {
Аргумент get_key это линейное чтение с диска.
Так какая проблема с временем работы? Это просто два прохода по 100 Gb, сколько просили столько получили. Так еще и ядро не нагружено.
P.S.
На 10Gb чуть быстрее выходит, это правда, в 1.4 раза от линейной интерполяции 100Gb, тут наверняка кеширование смазывает картину.
Запустил на своем компе на 10 ГБ файле:
total_proc=184067 ms.
total_output=398044 ms.Общее время 6:37
Учитывая что не UTF8 и не UCA - хороший результат.
.NET код из ветки https://github.com/gandjustas/HugeFileSort/tree/reduced-allocations при Ordinal (посимвольном) сравнении показал результат:
SplitSort done in 00:02:02.1302621
Merge done in 00:01:22.2265601Общее время 3:25
Это при том что он пишет и читает в два раз больше, но линейно.
нелинейное чтение с диска у вас тут:
sort(idx.begin(), idx.end(), [&] (u64 i, u64 j) {
return vec_keys[i] < vec_keys[j]; // TODO add utf-8 compare
});https://en.cppreference.com/w/cpp/string/basic_string/basic_string
смотреть 10 конструктор.
Везде где есть string - это строка в куче.
Здесь сортируется 16к строк в памяти, за ~5ms.
Тогда не ясно почему так долго сортируется.у меня сортировка вместе с записью на диск вы выполняется быстрее чем построение индекса у вас.
Попробуйте -O2.
Я не умею в cmake, студия как-то сама собрала. Залейте проект с нужными флагами компилятора, utf8 и uca, чтобы сравнивать яблоки с яблокамм
add_compile_options("-O2")
Скорее всего где-то можно выбрать Release вместо Debug.
можно сравнивать, скорость не изменилась (сортировка теперь вместо 5ms 30ms), разве что теперь форсится Release. Ну и я предполагаю что все строки разные с точки зрения сортировки всегда записаны каким-то одним образом, (по сути нет нормализации).
Сейчас все время уходит на проходки по красно-черному дереву.
Интересно, а нельзя просто бором решить?) Переносим число до пробела в конец строки, задача свелась к сортировке строк. По первому символу добавляем в бор. Если всё совпало, переходим к следующему символу, текущий хранитьтне обязательно, если не совпало, "что-то делаем", например создаём файлы по текущей букве. Количество созданных файлов не превысит количество строк в исходном.
Если просто число перенести, то порядок сортировки сломается.
на входе:
2. Строка
12. СтрокаПосле переноса будет
Строка .2
Строка .12Сортировка строк расположит их в порядке:
Строка .12
Строка .2Я пробовал это делать.
И число разворачивал тоже, тоже не работает как надо
Посимвольная сортировка, она же radix сортировка не дает результат соответствующий культуре. Посмотрите раздел "Как сравнивать строки"
Конечно можно, только числу надо лидирующих нулей забацать, тогда лексикографическое совпадет с числовым сравнением. Проблема в том что в условиях внешней памяти для бора захочется случайный доступ - а его нет в случае hdd.
Некоторые даже попытались сделать решение на Apache Spark
Можно все-же полюбопытствовать - в чем проблема такого решения?
А интервьюер такой: а вот и не верно. Лампочек тринадцать. У меня ещё одна вс кармане. Вы нам не подходите)
По некотором размышлении, я пришёл к выводу, что эту задачу нельзя эффективно решить, не обусловив среднюю (и максимальную) длину строки.
Можно выделить три принципиально разные ситуации:
1) Длина строки составляет примерно от нескольких десятков символов до сотен миллионов символов. Тогда можно играть на том, чтобы вместо самих строк сортировать сначала ключи в виде их начальных частей, как предлагал уважаемый@adeshere (при условии, что начальные части настолько же разные, как и сами строки).
2) Длина строки недостаточна для выделения ключа, отличающегося от самой строки. Одновременно это означает, что, скорее всего, имеется очень большое количество одинаковых строк.
3) Длина строки такова, что даже несколько строк или, в пределе, одна-единственная строка, не влезает в оперативную память. Если при этом строки различаются только в последних символах, то их эффективное сравнение само по себе представляет нетривиальную задачу.
Спасибо за статью, однако один вопрос не дает покоя:
try
{
var mergedLines = tempFiles
.Select(f => File.ReadLines(f).Select(s => new Item(s, s.IndexOf('.'))))
.Merge(comparer) // IEnumerable<IEnumerable<T>> -> IEnumerable<T>
.Select(x => x.Line);
File.WriteAllLines(Path.ChangeExtension(file, ".sorted" + Path.GetExtension(file)), mergedLines);
}
finally
{
tempFiles.ForEach(File.Delete);
}Я ведь правильно понимаю, что мы несмотря на такую запись ни в какой момент времени не вычитываем файлы целиком в память? По идее в памяти будут N буферов файлов открытых на чтение и одного файла открытого на запись, вся остальная работа будет с дисками. Если так, то кажется можно ощутимо поднять производительноть максимально увеличив размеры буферов.
P.S. ради интереса можно попробовать наивную реализацию на расте написать, получится ли выиграть что-то. По идее там сразу в диск упирание произойдет. По крайней мере там такие штуки как раз можно писать не включая мозг, но получая производительность отличного уровня и без мемори футпринта.
Правильно. В финальном варианте есть разная оптимизация буферов чтения/записи , везде выбран размер буфера в 1мб, чтобы не съедать слишком много памяти при слиянии 1000чанков.
Если говорить про это вариант кода, то там сложно настроить буфер, так как у StreamReader есть своя буферизация, а у FileStream своя.
Странное совпадение, но решение такой задачи разбирали на Ютубе более года назад https://www.youtube.com/live/B9v7pdfhUYw?feature=share
Если файл не влазит в лимит (по умолчанию 1 ГБ), то разбиваем его на мелкие части (по умолчанию на 100 МБ). Для этого рандомно выбираем нужное кол-во строк (тут используется произвольный доступ к файлу) и сортируем их. Например, получились строки
Груша.123, Земляника.321, Помидор.456.Потом выполняем полный проход по файлу и распределяем строки по временным файлам — если строка меньше
Груша.123, то в первый файл, если меньше Земляника.321 — то во второй и т.д. Если какие-то файлы всё равно получились больше лимита, то рекурсивно разбиваем их дальше.В результате имеем список файлов, в каждом из которых все строки больше, чем в предудущих файлах и меньше, чем в следующих. Загружаем временные файлы по порядку, сортируем содержимое и пишем в результирующий файл.
Шаги распределения по временным файлам и загрузки/сортировки временных файлов паралеллятся, но в случае сортировки временных файлов с учетом порядка файлов и общего лимита по памяти.
В Go только побайтовая сортировка, соответственно другие варианты не реализованы. Почему-то при варианте
Ordinal .Net вариант даже на 1 GB завис, поэтому запускал я его с вариантом по умолчанию LocalСulture.Используются только стоковые реализации сортировки и бинарного поиска.
Время работы (потребление памяти для 100GB держалось на уровне 2.2-2.7 GB):
$ ./HugeFileSort 1GB.txt
seed: 1675673671845497510
Split done in 1.692s
Sort/Write done in 2.45s
TOTAL done in 4.143s
$ ./HugeFileSort 10GB.txt
seed: 1675673683524993942
Split done in 11.599s
Sort/Write done in 19.012s
TOTAL done in 30.611s
$ ./HugeFileSort 100GB.txt
seed: 1675674146313347712
Split done in 4m1.065s
Sort/Write done in 3m22.516s
TOTAL done in 7m23.581s
Для сравнения время работы оригинального варианта:
$ ./bin/Release/net7.0/Sort ../Generate/1GB.txt
SplitSort done in 00:00:04.6032571
Merge done in 00:00:02.5344427
$ ./bin/Release/net7.0/Sort ../Generate/10GB.txt
SplitSort done in 00:00:31.9568792
Merge done in 00:00:35.2578093
$ ./bin/Release/net7.0/Sort ../Generate/100GB.txt
SplitSort done in 00:05:03.6851885
Merge done in 00:09:11.5672847
Среда выполнения: Kubuntu 22.04.1, AMD 5700G, 64GB, SSD Samsung 970 Evo Plus
$ go version
go version go1.20 linux/amd64
$ dotnet --version
7.0.102
Быстрокод: github.com/falconandy/HugeFileSort
https://pkg.go.dev/golang.org/x/text/collate
Я нашел для вас подходящий пакет. Можно сделать сортировку строк, а не массивов байт
Кстати как заработает алгоритм все строки одинаковые?
С сортировкой строк посмотрю на досуге, спасибо.
Добавил поддержку русского языка. В чистом виде массовое сравение pkg.go.dev/golang.org/x/text/collate тормозит, я даже форкнул библиотеку, чтобы некоторые внутренние струкутры сделать публичными и переиспользовать уже «вычисленные» данные. Но в результате обошелся парой «трюков» в функции сравнения строк в своем коде.
Время выполнения для русского языка (несмотря на другой алгоритм/реализацию/язык/компилятор результаты для Go и .Net оказались схожими):
$ time ./HugeFileSort 1GB.txt
seed: 1676191709148358132
Split done in 2.066s
Sort/Write done in 5.192s
TOTAL done in 7.258s
real 0m7,291s
user 1m6,773s
sys 0m4,695s
$ time ./HugeFileSort 10GB.txt
seed: 1676191614805000905
Split done in 24.541s
Sort/Write done in 39.46s
TOTAL done in 1m4.001s
real 1m4,018s
user 12m1,858s
sys 0m40,673s
$ time ./HugeFileSort 100GB.txt
seed: 1676191997311186498
Split done in 7m5.411s
Sort/Write done in 5m46.03s
TOTAL done in 12m51.441s
real 12m51,525s
user 128m25,751s
sys 7m27,114s
Кстати спасибо за тест на линуксе и ссд. Цифры более чем устраивают.
В результате имеем список файлов, в каждом из которых все строки больше, чем в предудущих файлах и меньше, чем в следующих.
а ради чего? чтобы избавиться от сортировки слиянием? так она сама по себе достаточно быстрая и будет упираться в скорость hdd (то есть я не ожидаю, что она окажется медленнее, чем просто слияние файлов без сортировки)
Забавно, что я буквально вчера отправил тестовое на схожую тему (сортировка слиянием файлов, которые не влезают в озу, без ограничения по времени правда), но не на сеньера и даже не на стажера, а в качестве студента на курсы при одной крупной конторе. (12Гб файл со включенным профайлером прошел за 13 минут)
Может быть код приложите, чтобы я не зря апрувил ваш коммент?
Разумеется: https://github.com/scroogemcfawk/cft-shift-java-test-task
Сортировку сделал однопоточной, в условии ничего про производительность не было сказано, разве что файлы могут целиком не влезать в озу.
Вам по условиям задачи надо было свою сортировку писать?
Да. Проблема возникла с тем, что сортировка происходит в 2 режимах: строк и целых чисел. Я не работал с дженериками раньше и свести задачу к дженерик сортировке у меня не вышло. Тем не менее, профайлер поведал мне, что непосредственно сортировка занимает менее 60% времени.
Еще интересно, что BufferedReader, видимо, работает не так, как я предполагал. При слиянии временных отсортированных файлов у меня были открыты эти ридеры в обертках (класс по методу getNext просто выдает следующий элемент на запись среди всех временных файлов (типо указатели при слиянии)), причем буффер на каждый я выделял на основе свободной озу в рантайме. В обертках я сделал метод peek(), который использовал методы BufferedReader'а mark, readline и reset (по сути откатиться после прочтения) и это занимало очень много времени при слиянии. Затем я просто добавил поле "кэша" в обертку, чтобы снова не вызывать методы ридера при peek() и pop(), а брать из поля и время метода уменьшилось В 10 РАЗ.
Это странно, тк в доках написано, что системных вызовов быть не должно, но, видимо, что то там все же есть.
Короче задачу, видимо, можно настолько сильно развить, что она от уровня стажера перейдет на уровнь сеньера, все зависит только от ее интерпретации))
Я думаю, что данная задача проверяет совсем не умение писать сортировку работать с большими файлами. На мой взгляд тут проверяется, насколько человек умеет видеть нечеткие моменты в задаче и задавать уточняющие вопросы, ДО того, как начнет писать код.
Т.е. если получив задачу кандидат пошел сразу писать, код, то ему до сеньора-помидора еще как до луны пешком. А если задавать правильные вопросы, и обсудить все детали, то возможно писать ничего и не придется (например, окажется, что можно использовать готовое решение или например данные изначально можно получить в отсортированном виде из источника).
Что конечно не отменяет того, что все же надо уметь написать код, который отсортирует за час 100 Гб файл.
Хочу попробовать решить задачу на другом ЯП, а также дать своим студентам для попытки поиска решения. Можно пояснить задачу для тех кто не понимает в C# - что понимается под "сначала сортируем текстовой части строки".
Во первых, какой размер этой строки? Произвольный? Тогда какие границы строки, хотя бы примерные. Есть у меня подозрение что сортировать строки с одним символом после точки-пробела и с 1-2 тысячами символов - будет несколько разный временной результат.
В вторых, какая сортировка имеется ввиду? Алфавитная? Тоесть строку вида "111. здравствуйте" надо преобрзовать в вид " 111. аввдезйрстту"? Пробелы, если имеются, куда сортировать? А если есть символы других языков? Или все символы сортируются по байтовым значениям?
Каждая строка исходного файла состоит из числа (a) и текстовой части (b). Порядок для двух строк (a1, b2) и (a2, b2) по формуле (a1, b2) < (a2, b2) = b1==b2 ? a1<a2 : b1<b2
Размер строки меньше размера чанка, других ограничений нет. Текстовая часть всех строк может как совпадать, так и быть разной для всех строк. Код должен работать в этом случае. Хотя вполне может быть оптимизирован под "средний" случай, когда уникальных строк менее 2%.
Сортировать надо строки файла, а не текстовые части внутри себя. b1<b2 понимается в смысле UCA https://www.unicode.org/reports/tr10/ это не побайтовая сортировка если что.
хм.. кажется, что вся статья - это борьба с языком, чтобы получить нормальный доступ к аппаратуре.
Как-то во время чтения созрела мысль, что высокопроизводительный код на C# \ Java выглядит настолько уродливо потому, что "пробиваться сквозь абстракции к аппаратуре" сложнее, чем "навернуть ещё один слой абстракций".
ПС.
Мне кажется, что rust был бы оптимален для этой задаче - совмещает в себе библиотеку с UCA алгоритмом с низкоуровневыми возможностями.
В каком месте борьба, тем более с языком?
FileStream вызывает непосредственно api операционной системы, над ним только один слой - для преобразования в строки. В итоге от него пришлось отказаться, так как сортируются в итоге не строки, а байтовые массивы.
Все остальное - высокоуровневые абстракции. Например итераторы, динамические коллекции, каналы и таски, стрим для сжатия, да и сама сортировка выполняется в итоге штатной функцией. Так что язык и библиотека очень даже помогает решить задачу.
Сортировка слиянием — не так просто, как кажется