По поводу сортировки файла в 3GB

Опубликовано Mar 7, 2012 в Алгоритмы и Структуры данных, Тестовые проекты (2-3 часа) | 16 коммент.

, , , ,

По поводу сортировки файла в 3GB

Анализ задачи

  1. В чем суть проблемы? 32-х битовая операционная система Windows не может выделить 3GB для процесса. Считается, что данный лимит – 2GB, но на самом деле выделять под собственно данные нужно еще меньше. Примем этот лимит равным 1,5GB, то есть можно считать, что за одну итерацию в оперативную память можно поднять половину данных. Отсюда следует неизбежная необходимость подгружать данные с диска в процессе их обработки.
  2. Что оптимизировать? Так как файловые операции несоизмеримо медленнее, чем работа с памятью, то нацеливаться нужно на уменьшение количества обращений к диску, а не на борьбу за создание алгоритма с меньшим Big O. Кроме того, очень затратной может оказаться реализация операции сравнения для больших строк, а в пределе возможна такая строка, которая сама будет иметь размер больше 1,5GB и даже в одиночку не влезет в память. А может быть очень много коротких строк, но тогда велика вероятность их повторения. Отсюда вывод, что для оптимизации общей производительности наверняка придется переключать алгоритмы в зависимости от статистики распределения длин строк и их количества.
  3. Можно ли использовать нечто готовое? Скорее да, чем нет, так как более классическую алгоритмическую задачу, чем сортировка, вряд ли можно найти.
    ВОПРОС: где же она решена именно в такой постановке?
    ОТВЕТ: в любой промышленной реляционной СУБД. Работа с объемами данных, большими чем лимит, установленный процессом, оптимизация работы с диском под эти задачи, индексы, основанные на самых производительных алгоритмах сортировки – все это может оказаться полезным, так как самые сложные части задачи будут переложены на чужие плечи, заслуживающие доверия. Решение задачи, основанное на использовании MS SQL Server видится, по крайней мере, интересным и его стоит попробовать поискать, а результаты сравнить с теми, которые будут предложены на основе применения подхода, где алгоритм сортировки и работа с файлами будут реализованы только стандартными средствами выбранного высокоуровневого языка.
  4. Как тестировать результаты? Очевидно, что полноценное тестирование данной задачи может быть выполнено только с применением средств автоматизации, так как исходные данные абсолютно необозримы. Значит, необходим тестовый скрипт. Кроме того, в нашей ситуации нереальной является передача тестовых файлов ввиду их огромного размера. Следовательно, нужны дополнительные скрипты генерации тестовых данных, которые можно будет пересылать.

Автор публикации:

16 Коммент. : “По поводу сортировки файла в 3GB”

  1. Kostiantyn says:

    Касательно п.2, небольшой комментарий “из головы”, потом перепроверю и опровергну если что :-)

    Во-первых, хотел напомнить про приход SSD дисков в наши края. Я понимаю, они ещё не особо популярны. Тем не менее, на них время “случайного доступа” стало меньшим на 3-4 порядка по сравнению с обычными винчестерами.

    Во-вторых, в определённых условиях, которыми являются использование Windows Vista / 7 64bit и наличие скажем 8 GB оперативной памяти, фирменная технология от Microsoft под названием SuperFetch сделает так, что физически данные будут считанны всего лишь 1 (один) раз. Проверить это можно, увы, только эмпирическим путём.

    • Ну это же задача рассматривается на этом сайте не в промышленной постановке. Нужен алгоритм. А для отладки и проверки вполне можно сделать модельную задачу. Установить параметр MaxMemoryLength – максимально возможный размер данных, загруженных за одну итерацию в память. Это аналог 1.5GB из соответствующего поста. И дальше программно следить, чтобы не создавались массивы с большим, чем MaxMemoryLength размером. Лично я бы своим студентам задачу ставила именно так – за это и флешку бы присудила. Тогда задача проверяема, и, главное, не нужно тратить огромное время на каждый запуск, пока автор создает решение.

    • По мотивам личных практических наблюдений…
      Типичный “бытовой” современный САТА НЖМД обеспечивает среднюю скорость чтения/записи около 10 МБ/с (+/- небольшой паровоз в зависимости от ряда очевидных облегчающих/отягчающих факторов).
      На самом деле, скорость обработки строк при сортировке в памяти имеет тот же порядок, а то и меньше. Конечно, чтобы повлиять на скорость сортировки существует намного больше вариантов, чем на жесткий диск…
      Однако, система должна быть сбалансирована, если целью является её бизнес-приложение, а не способ освоить побольше денег. А это значит, что если мы вставляем твердотельный накопитель (и сможем каким-то образом выжать из него его рекламные порядка 200 МБ/с), то и процессор надо ставить как минимум восьмиядреный (чтобы освоить возможности накопителя)… А кто с таким процессором поставит менее 16 ГБ памяти?…
      Вот и приехали – главная проблема в нашей задачке отпадает сама собой. Ура экстенсивным методам ведения народного хозяйства! :)
      Поэтому, чтобы задачка представлялась практически значимой, нужно конкретизировать в ней существенные технические ограничения, как-то:
      У вас есть 32-разрядный АРМ процессор с тактовой частотой 100 МГц и 16 МБ внешнего ОЗУ, скорость обмена с которым 80 Мбод, и т.д. Реализовать алгоритм……., который успешно закончит работу за/до [появления у заказчика желания выпить чаю (детей, внуков, правнуков...)].
      Так будет более похоже на правду, гораздо конкретнее и интереснее. ;)

      • Эммм, уважаемый, Вы что курили?)
        Какие 10 Мб/с? Вы с какого столетия?)
        Будьте добры, почитайте нынешние спеки на диски и контроллеры ;)
        Какие восемь ядер? Нафига? Для сортировок?
        Какое “скорость обработки строк при сортировке в памяти имеет тот же порядок, а то и меньше”? О_о
        Как-то несерьезно…

    • Trusov Denis says:

      А ещё в наши края забегал псевдовинт на планках памяти. У него производительность на пределе интерфейса подключения с мгновенным доступом к любой области. И чо, тоже бижать покупать?..

  2. В добавление в ответу на предыдущий комментарий. Попробовала немного действовать по пункту 3. То есть посмотреть, как для этой задачи использовать MS SQL Server. Сгенерирован тестовый файл чуть больше 1 ГБ с длиной строки до 900 байт. Количество строк в файле получилось равным 2 220 713.
    Сценарий.

    1) Создать таблицу из одного столбца varchar(900) и для него создать кластерный индекс. Цифра 900 выбрана не просто так, это максимальный размер строкового столбца, для которого еще возможно создание индексов.

    2) С помощью BULK INSERT загрузить данные в таблицу. Отработало все примерно за 13 минут. Из C# пройтись по таблице с помощью SqlDataReader, активизированного запросом select Line FROM dbo.Sorting3GPost ORDER BY Line, и записать полученные данные в файл. Отработало примерно за 5 минут. Количество памяти, использовавшееся процессом, очень небольшое, проблемы тут вроде не просматриваются при росте размера файла в 3 раза.

    3) Тесты: проверялось совпадение количества записей и совпадение размеров файла. Поверить, в то, что SQL Server неправильно выполнит сортировку, я не могу, но все же глазами просматривались файлы, которые выгружались с опцией TOP N.

    4) Решение ли это? Для поста с сайта, явно, нет. Для промышленной ситуации вполне может быть, что и да. Во всяком случае, экономится время программиста: нужно было вспоминать синтаксис BULK INSERT и набрать около 15 строк кода на C#, над которым совершенно не надо задумываться. Кроме того, время решения в целом оказалась меньше, чем время, затраченное на генерацию исходного файла с помощью того же C#. Разумеется, последнее сравнение не является полностью корректной метрикой, но как прикидка кажется здравым.

    • Галина, спасибо за приложенные Вами усилия!
      Прекрасный пример брутфорса, плюс тестовая конфигурация, которая дает ориентир времени выполнения для всех желающих переплюнуть Майкрософт в реализации внешней сортировки ;)

      Кстати, как Вы полагаете, по каким причинам время генерации тестового файла оказалось больше времени решения?

      P.S. Правильность сортировки можете проверить утилитой, ссылку на которую я выкладывал в комментариях к записи с задачей. Нужно лишь выбрать исходный и отсортированный файлы, нажать на одну кнопку и немного подождать. )

      • Время генерации тестового файла было больше, чем просто вывод данных, переданных через DataReader, потому что был еще внутренний цикл (0..900), который ПОСИМВОЛЬНО генерировал строки разной длины с помощью стандартного Random.

        • Спасибо за ответ.
          На самом деле, моё знакомство с С# очень поверхностно, но меня всегда глубоко удивляла непомерная прожорливость CLR приложений, поэтому интересно Ваше мнение как практика – в чем вычислительная сложность настолько элементарного кода, и что всех тормозит: то-ли Random, то ли класть числа в символьный массив?
          Вероятно, в связи с наличием больших перспектив дальнейших исследований, будет целесообразно немного оптимизировать этот весьма необоснованно прожорливый цикл.

  3. Trusov Denis says:

    Мне анализ не понравился.
    1. Почему-то первым пунктом поставили, т.е. во главе всех проблем, ограничения конкретной реализации под конкретной платформой. Но данное ограничение не является проблемой этой задачи. Если мы можем выбирать программное обеспечение для “промышленного” решения, то что мешает выбрать любую подходящую ось, лишенную данного недостатка? Хотя жаль, что всё-таки не были озвучены более детальные требования заказчика (постановщика задачи), а то вдруг нужно было эту задачу решить под голым ДОСом и ограничения там были бы несколько иные. ;) Да и вроде ничто не мешает создать проецируемый в память файл (один или несколько, которые не будут в одном виртуальном пространстве с основным процессом), чтобы избавиться как от ограничений среды Win32, так и от недостатков накопителя, при наличии достаточного количества физической памяти (хотя, опять же, теория, которую лично не проверял — может так можно только сделать запустив Win32-приложение в среде Win64). Помоему очевидно, что проблема заключается просто в непомерном потреблении памяти данной операцией — файл мог бы быть длиной как десять, так и сто гигабайт. В общем, как результат, первым запостившимся был продавец-консультант, который, как ему и полагалось, не преминул посоветовать чего-нибудь купить.
    2. Вроде бы близко, но не совсем то. Если файл читать “побайтово” и последовательно, то он будет прочитан за несколько минут. Не так уж и много. А если попытаться прочитать тот же обьем, но вразнобой — задание будет выполнено в аккурат к тому времени, когда терабайтовые планки памяти будут стоить по 5 копеек связка. Стандартные алгоритмы упорядочивания требуют как раз последнего варианта доступа, а эффективное использование накопителя — предыдущего. И суть задачи сводится к разработке алгоритма с последовательным доступом к файлу. Собственно, эта проблема должна была быть под номером первым, если экономим ОЗУ. Тут уж выбор невелик — приходится создавать промежуточный файл, состоящий из кусков с упорядоченными строками и сводящий к минимуму непоследовательный доступ (полностью не получается, однако). Затраты на создание этого файла и чтения из него окупятся исключением ёмких по времени операций произвольного доступа к исходному файлу. Вот и вся идея внешней сортировки. А статистика длин строк что нам даёт? Да ровным счётом ничего — балласт. Предварительно нецелесообразно собирать, а при совмещении нескольких этапов в один — пользы от нее тоже ноль.
    3. “Чужие плечи, заслуживающие доверия”, к сожалению, обычно прячут свой алгоритм за пазухой и не позволяют поискать в нём узкие места, путём конструирования специального файла, которым он должен бы подавиться. И оценить количество ресурсов и времени реально нужных для операции можно только косвенно… Да и, как оказалось, эти плечи не такие уж широкие, как хотелось бы, всего — 900 попугаев. Хотя, конечно, чужой алгоритм уже давно отработан и выверен временем. Да и, при таких ограничениях, вряд ли, удастся что-то сконструировать. Не спорю — слишком незатейливо, чтобы был изъян. Лучше все же сравнивать с реализацией, работающей в идеальных условиях — физической памяти достаточно для выполнения классической сортировки строк (один раз прочитал, отсортировал и сразу записал результат). Таким образом, мы узнаем, что проиграли и что получили взамен.
    4. Тестирование… Естественно, без скриптов автоматизации можно усохнуть на такой проверке. Спору нет. А вот скрипт генерации тестового файла следует готовить по особому. Простой генератор случайных строк не интересен (а кажется именно такой был в тесте с SQL, хотя могу ошибаться), поскольку на случайных данных получим случайные результаты. Другое дело возвести в абсолют недостатки, характерные для плохих реализаций. Первый вариант тестового файла. Создается файл с максимальным числом строк минимальной длины, все строки должны быть разными. Таким файлом подавится программа, которая для абсолютно каждой строки в файле создаёт какую-либо структуру. Второй вариант. Файл содержит гигабайтовые строки, отличающиеся только последним байтом. Таким подавится та, которая любит кешировать отдельные строки целиком и перебрасывать их из одного буфера в другой или читающая данные часто и слишком маленькими порциями. Ну и третий, заморский — смешанный. Строк много, все разные, но имеют одинаковый префикс, длину выбирать приличную и обеспечивающую максимальное количество циклов считывания с накопителя для алгоритмов, подкачивающих фрагмент строки во время сортировки. Противопоказания — алгоритм ориетирован либо только на короткие, либо длинные строки, а также многократное считывание. Если файл не обработан за час, то тестера можно не мучать, а исходник сразу отправлять в музей говнокода.
    Нету сил мусолить больше тему внешней сортировки, все слова кончились. Я больше не буду… XD

    • Да, вы правы будем заканчивать с этой задачей. Имеется несколько вариантов для выбора наилучшего.
      PS. По поводу более детальных требований заказчика – их нет как и нет никакого заказчика. Задача давалась чисто на интерес и разбор вариантов. Наши реальные заказчики (один из которых, например, очень известная компания) весьма бы удивились, если бы узнали, что мы подобным образом поступаем с их задачами.
      Лично я, если бы решала эту задачу на работе, задала бы десятки вопросов и по-всякому пыталась бы строить архитектуру проекта в целом таким образом, чтобы избежать подобной затеи.
      PPS. Мы будем менять задачу в рубрике с получением приза. Вполне можем опубликовать задачу, которую предложите вы – вы и будете тогда заказчиком.

      • Жаль, что уже пора заканчивать.

        Я лет шесть нигде ничего в таких количествах не писал, а тут – юность вспомнилась, ностальгия, словоблудие…

        Но Вы, конечно же, правы. Пора заканчивать. :)

  4. Александр says:

    Предлагаю поступить таким образом:
    1. Кусками с неотсортированного файла, закидывать в память и сортируем от min.
    2. В памяти сортировать любыми удобными способами.
    3. Из отсортированного в памяти массива убирать кусок, вместо него с файла забрасывать в память неотсортированный кусок.
    4. Неотсортированный кусок массива отсортировать и слиянием соеденить со 2 куском.
    5. Далее повторяем с пп.3 до окончания неотсортированного файла.
    6. Теперь мы имеем в памяти, кусок отсортированного файла, и можем записать на диск его. Он отсортирован скажем от min до индекса N.
    7. Далее начинаем с пп.1 с условием отбрасывания строк с индексом меньшим N.
    8. От пп.1 до пп.5 идет только считывание файла.

  5. Простите, может, глупость скажу, конечно )))
    Но почему не прочитать файл в упорядоченное дерево…
    Надеюсь, понятно о чем речь – первый уровень дерева – первые буквы слов, второй – вторые и т.д. ну и каждый узел/лист хранит соответственно, скажем, кол-во слов, которые на этом узле/листе заканчиваются…
    Ну и, следовательно, записать уже упорядоченное дерево обратно в файл.
    Имеем одно полное последовательное считывание из файла, одну полную запись – похоже на минимум здесь.
    По поводу процессорного времени, вполне очевидно, что время линейное относительно размера файла.
    Вот вопрос сколько это дерево займет в памяти…но несложно доказать, что в случае с файлом в 3 Гб оно уж точно “спрячется” в ОП в 2 Гб.

    • Иванов says:

      Суть задачки – не впихивать все данные в память за раз. И как 3ГБ данных можно разместить в 2ГБ??

    • Очевидно, что для каждой уникальной строки потребуется как минимум один отдельный узел. Если предположить, что для узла потребуется 2 указателя и счётчик, т.е. 12 байт на узел, то, чтобы окупить затраты на дерево, потребуется наличие в исходном файле соответствующее размеру узла число одинаковых экземпляров строк, описываемых этим узлом. Довольно смелое предположение о содержимом исходного файла. А доказательство хотелось бы послушать.

Оставить комментарий

Ваш адрес email не будет опубликован.


*