Оптимизация работы с БД на асме

Дано: много больших файлов (примерно по 20 Мб). Каждый файл состоит из записей (до 200 тыс. записей). Формат записей известен.



Нужно максимально быстро:

а). Объединить все файлы в один большой

б). Произвести сортировку по определенному критерию в получившемся файле



Вопросы:

1. Какой алгоритм в плане скорости лучше применять для таких больших объемов?

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



Пока все.

 

Broken Sword

Их нужно физически склеить или логически? Второе можно осуществить создав ещё один файл вроде индекса.

Деревья B+ и производные годятся для организации структур данных в больших файлах. Исходники можно тут на сайте найти вместе с книгой T. Niemann.

В Винде ничего не работает быстрее MMF, AFAIK.

 

Не могу понять чть ты имеешь ввиду под БД?



1. Если БД=mysql, то лучше чем команды LOAD не придумали, вот пример запроса, делал прогу на асме. Вполне нормально заносит в таблицу файлы по 100 метров с 4-5 ляма строк за 10 сек.

Код (Text):

1.  
2. LOAD DATA INFILE '%s' REPLACE INTO TABLE `where_search`FIELDS TERMINATED BY ''
3. LINES TERMINATED BY '\r\n'(`url_where`)
4.  

С сортировкой еще проще в mysql



2. если ты имеешь ввиду свою структуру и сравнения, то файлы грузить лучше путем проеццирования их в память блочно (Memory Mapped Files), настчет сортировки обрати внимание на этот документ http://dox.sbnet.ru/publications/findstr.ru.txt

 

merge sort

 

Corleone

Недавно мне про проецировние говорил leo, поэтому:

много больших файлов * 20 метров может не прокатить

 

EvilsInterrupt

хм интересно) Писать программы надо всегда универсальные способные работать как на копмах с малыми параметрами так и на монстрах, так же огромная вероятность того что сегодня ему надо на 20 метров грузить а завтра на 200.

 

Quantum

Насчет физическои и логической склейки - где мы в конечном счете выиграем в производительности? Следует помнить, что в конечном итоге нам нужно работать со ВСЕЙ совокупностью файлов, как с единым целым.



Corleone

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



Noble Ghost

merge sort будет быстрее деревьев?



EvilsInterrupt

Что ты имеешь ввиду про "много больших файлов * 20 метров может не прокатить"



Какие есть компактные средства (ну вы поняли - не монстры типа SQL), которые позволяют осуществлять простейшие операции с записями в БД, вывод на экран и т.п.

Excel не подходит по причине ограниченности кол-ва строк в 65535 штук.

 

В одной из моих тем, leo мне написал что при проецировании особого выигрыша на больших нет, http://www.wasm.ru/forum/index.php?action=vthread&topic=13988&forum=4&page=-1

 

Чувак, не гони, уже давно доказано обратное (MMF это тормоз).

 

о, теперь совсем интересно... и как мне прикажете работать с одним (результирующим) 300 мб файлом? Или результирующий создавать нет смысла и можно как-то быстрее по кускам? Только скорость волнует, больше ничего.

 

Broken Sword

Быстрее всего через ReadFile, главное подобрать размер буфера на конкретной машине (выше 64кб имхо брать смысла особого нет). Что касается размера в 300мб, то еще не известно сколько будет памяти на результирующей машине(машинах). Весьма разные по реализации по алгоритмам/скорости будут для машины с 1мб свободной памяти, и для машины с 512мб, куда этот файл можно целиком уместить.

 

Broken Sword

Во-первых, процесс "склейки", аналогично процессу архивирования нескольких больших файлов без сжатия, займёт время и довольно много, если только не провести его на низком уровне (на секторном уровне, чтобы на самом деле не происходило копирования). Гораздо быстрее будет переместить все файлы в один каталог и проиндексировать их. Работать с одним огромным файлом всегда труднее и накладнее в плане скорости (даже через MMF), чем с несколькими маленькими. Опять таки, подразумевается работа не на низком уровне. Многие БД делят базу на несколько файлов, если размер базы превышает определённый максимум.



Ms Rem

Хе-хе. Тормоз по сравнению с чем? CreateFile, ReadFile, WriteFile и т.д. работают через MMF. Следовательно, томозят ещё больше. Или ты советуешь использовать прерывания?



ЗЫ: Подразумевается, что файлы большого размера и доступ на чтение/запись random, а не sequential.

 

alpet

Допустим, заранее известно, что физической памяти на машине МЕНЬШЕ, чем размер файла. Насчет буфера в 64Кб - это для какого алгоритма?



Quantum

Что ты имеешь ввиду под "индексированием"? Допустим у меня в одном каталоге дружно лежат 23 файла по 180 Мб. Чегоо дальше делать?

 

Это всё не так однозначно.

Выбор оптимального варианта зависит от соотношения размер файла/размер свободного озу. Если файл < 50% ОЗУ, ReadFile будет быстрее, и чем меньше файл, тем больше преимущество.



Broken Sword

64 КБ - это совсем мало (может опечатка?). Для задач чтения, сортировки и сохранения метод ReadFile-sort-WriteFile на машине со 128 озу будет быстрее для файлом размером от 50-60 Мб и менее.

Наверное больше надо думать над тем, что файлов много, а в пределах одного файла ReadFile на указанных тобой размерах значительно быстрее.

 

Чувак, ты какую травку куришь?? Это просто МЕГАЛОЛ!!

MMF работает через механизм управления виртуальной памятью, и при обработке исключений посылает IRP либо FastIo запросы драйверу ФС.

ReadFile/WriteFile посылают эти запросы напрямую, а следовательно не тратиться время на обработку исключений и управление распределением памяти.

 

Я могу с увереностью сказать, что преимущество ReadFile перед MMF будет на файлах любого размера. Причина приведена выше.

 

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

 

Это из разряда И вишню съесть и косточкой не подавится. Над такими монстрами работают целые институты! Если ты упомянул Excel, то лучше создавать базу Access, коннектится к ней ч-з ODBC, на любом компе есть необходимые для этого средства (Под виндой имеется ввиду для особо придирчивых), и посылать запросы.

 

Ms Rem

Сокращённо VMM. Стандартный file I/O тоже использует VMM, т.к. обязан учитывать выравнивание буферов, т.е. напрямую копировать данные он не может в любом случае. Точное поведение file I/O зависит от флагов с которыми открыт файл, от размера файла и от обьёма ОЗУ доступного данному процессу (тут могу и ошибаться, но в отладчике видно, что кол-во физ. памяти для чего-то запрашивается).



MMF и VMM так тесно связаны, что ошибку в моём предыдущем посте можно отнести к разряду опечаток



Кол-во исключений, тормозящее MMF можно проконтролировать на уровне алгоритма. Т.к. вместо одного огромного файла изначально имеем несколько больших и доступ можно оптимизировать через индекс (словарь). В крайнем случае, можно залочить несколько Мб виртуальной памяти для процесса БД и исключений не будет вообще.

 

Quantum

Может быть ты говоришь про линейку win9х?

Не знаю как в них, но в NT обработка ввода-вывода как при помоши MMF, так и при помощи ReadFile сводиться к вызовам Fastio обработчиков ФС (либо посылке IRP если Fastio не поддерживается). Просто при рабоче через MMF происходит больше лишних действий, а отсюда и тормоза.

Если не веришь, то посомтри исходники windows2000 и ее драйверов ФС. Я в свое время рассматривал эту часть довольно подробно чтобы утверждать что вызов ReadFile не приводит ни к каким обращениям к механизмам виртуальной памяти, а является только обращением к драйверу ФС.