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

Ms Rem

В книге по внутренностям win2k (под рукой нет чтоб процитировать) написано, что общие принципы работы MMF сформировались ещё до выхода Windows 95. Поэтому, сабж не отличается на 9x и NT, IMHO. Обращения к VMM я видел в WinDbg на своей XP SP2, когда отлаживал один странный глюк при чтении файла через стандартные win32 file I/O. Глюк, как оказалось, был связан именно с тем, что активно использовалась виртуальная память. Поэтому я его и запомнил. Флаг FILE_FLAG_NO_BUFFERING исправил ситуацию. Отсюда напрашивается вывод, что VMM используется для кеширования, но это уже домыслы.

 

Скорее ты заметил кеширование файловых операций драйвером ФС, которое флаг FILE_FLAG_NO_BUFFERING отключает. Естественно, это кеширование не имеет никакого отношения к MMF и стоит на более низком чем MMF уровне.

 

Ms Rem

Ниже MMF стоит VMM. Надо будет почитать исходники w2k на досуге. Как перечитаю - вернусь в дискуссию

 

Corleone

Access из серии тех же монстров. Неужели нет какого-нить проекту на sourceforge, где экзешник со всеми обвязками занимает 200 кб?



2all:

с сортировкой в небольших файлах (которые могут уместиться в памяти целиком) более-менее понятно. Что делать дальше с получившимся набором отсортированных кусков единого целого?

 

У меня есть один очень мощный проект, что именно делает сказать к сожалению не могу, но работает он ч-з ODBC как с mysql так и с access (меняешь опционально), писал я его долго, и работает он с ОГРОМНЫМИ данными, при этом сам ехе файл (ГУИ+куча ресурсов, иконок, меню и т.д.) занимает 230 Кб на асме, прога способна работать месяцами без сбоев. Все проверено и оттестировано

 

Файлы ни грузить в память ни мапить не надо вначале, если нужно отсортировать по нужному полю.

Сортировка в худшем случае в зависимости от алгоритма будет приближаться к квадратичной функции от n - записей,

тут будет самая главная засада - и перед этим все линейные

угловые коэффициенты будут никнуть.

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

Я бы конечно создал в памяти непрерывный массив который представляет именно сортируемое поле (если поле строковое - то изначально бы прохешировал и массив был бы уже хешей). Выделил бы память для индексного массива = по элементам тоже количеству записей. Создал бы карту файлы-номера индексов (т.е. если отдельные сегменты общей базы - сделал бы карту перевода относительных в сквозные, там была бы что то вроде таблицы карта по количеству записей равная количеству файлов (делать можно очень по разному места почти не занимает) Поместил бы в индексных массив значения от 0 до n-1 (где n общее количество записей). Этот индексный массив служил бы как бы полутенью сортируемого массива. Обычно сортировка сводится к проверке значений элементов (по разному в разных алгоритмах выбирается по каким индексам проверяются элементы и по каким индексам пишутся) и перемещению\обмену. Проверочная часть выполняется в сортируемом массиве, обменная в обоих - сортируемом и индексном. Индексный массив - это именно то что ждётся и нужно для конечной операции.

Т.е. например решили в базе из 100 полей сортировать по полю a.

Выбрали в отдельный массив значения этого поля в отдельный массив оказалось там 7 элементов:

13,1,23,33,4,2,8

(отсортированный 1,2,4,8,13,23,33)

создали индексный массив b

0,1,2,3,4,5,6

(полученный 1,5,4,6,0,2,3)

Нужно отсортировать записи по восходящей

Сделали сортировку в которой когда мы перемещили элементы

a[j]<->a по результатм проверки

то в массиве b мы делали b[j]<->b

т.е. пусть в обычном алгоритме сортировки было

в псевдокоде кусок

если траля-ля(что то про сравнение a,a[j])то

a[j]<->a

конец если

мы просто его дополним строчкой



если траля-ля то (что то про сравнение a,a[j])то



a[j]<->a

b[j]<->b[j]

конец если



Нас будет интересовать выход массива b.

1,5,4,6,0,2,3

Далее создание выходного файла f будет тривиально

Очень быстро по карте файлов от b[0 ...6] переводим сквозные 1,5,4,6,0,2,3 в относительные от файлов.

считываем только в память только одну запись и пишем её в выходной файл (даже индексировать ничего не надо в указателе файла, там указатель сам перемещается)

Выбор самого алгоритма сортировки будет сильно зависить от n. Но важно что - нам не нужно всё подряд разом считать или разом записать. Нужно получить индексы какая строка должна записаться первой какая следующей. Большие участки памяти никогда нормально не закешируются. Да и нафиг они не нужны пока сортировка не сделана по полю. Если предпологается что там не отсортированные данные а на выходе - отсортированные, то сортировка тут будет самое ёмкое, а если на выходе получено как должны распологаться начальные записи, то операция сводится к циклу прочтению записи по индексу равному текущему значению в b и записи в файл (там повторюсь вообще ничего не нужно индексировать)

т.е. будет mem size = record size

от 0 до n-1



[файл][а]<-b;получение из сквозного индекса, файла и смещения



mem <- [файл][a]



конечный файл <- mem



Это как мне видится общая стратегия, детали (сортировка, переводы в сквозные и из сквозных индексов в файло указательные, и т.п.) - это можно уже отдельно обсуждать.

 

The Svin

спасибо, перевариваю...

 

TheSvin

> "Файлы ни грузить в память ни мапить не надо вначале"

> "считываем только в память только одну запись и пишем её в выходной файл"

> "сортировка тут будет самое ёмкое"

Ошибаешься - самое емкое (по времени) в данной задаче это скорость загрузки данных с диска. По сути твой вариант минимизирует требуемый объем памяти, а вот насчет скорости - большой вопрос. Тут единственная надежда на файловый кэш (ФК) ОС - если бы после первого чтения данных они по максимому осели в кэше, то можно было бы всерьез рассматривать этот вариант. Но на деле такого не будет (разве что в win 95). NT+ быстро распознают последовательное чтение и не дают расти ФК, считая это бессмысленным занятием. А посему индекс ты действительно создашь достаточно быстро, но вот при записи выходного файла придется 1) заново читать данные с диска, 2) читать записи в случайном порядке из разных файлов => дополнительные потери на перемещение головок HDD.



А посему главное в данной задачке по максимому использовать ОЗУ для хранения данных. Если результирующий файл умещается в ОЗУ, то проблем то особых нет - все сводится к частной задаче выбора метода сортировки.



> "если поле строковое - то изначально бы прохешировал и массив был бы уже хешей"

А ты знаешь хэши, позволяющие производить упорядоченное сравнение на "больше"\"меньше" ?!



Ms Rem, Quantum

Успокойтесь, горячие финские парни )))

Вопреки бытущим мнениям MMF не так хорош и не так плох, как о нем говорят. Дело в том, что есть теоретические выигрыши\прогрыши, а есть практические. Практические различия это те, которые имеет смысл учитывать на практике и которые заметно превышают прочие случайные факторы. Теоретическое преимущество MMF перед буферированным чтением (по скорости) состоит в том, что данные пишутся с диска непосредственно в ту страницу памяти, которая передается юзеру, а при буферированном чтении данные пишутся в файловый кэш и затем копируются в буфер юзера. Разумеется один из минусов от использования как MMF и так и чтения больших файлов в память целиком (а не блоками) - это отказы страниц. Но это теория, а что получается на практике ?

Типичное время обработки отказа страницы составляет несколько тысяч тактов процессора - казалось бы "о, ужас", но если сравнить это со скростью чтения данных с диска, то ничего особенного ужасного мы не увидим. Возьмем грубо потери на отказ страницы ~(4К_тиков)/4Кб=1тик/байт. Скорость чтения обычно не превышает 50 Мб/с, что в пересчете к частоте CPU скажем 1ГГц дает порядка ~20тик/байт, т.е. отказы страниц дают потери в скорости чтения не более 5% (при большей частоте CPU и фрагментации файла, относительные потери будут еще меньше).

Потери на копирование данных при буферированном чтении. В современных процах соотношение частоты CPU и ОЗУ составляет порядка 8, т.е. скорость потокового чтения данных из ОЗУ составляет тоже порядка 1байт/тик (64бита=8байт делить на Fcpu=8*Fram). Следовательно, потери на загрузку данных из ОЗУ в кэш процессора сравнимы с потерями на отказы страниц при чтении файлов, и значит MMF уж никак не может быть быстрее (правильно организованного) блочного чтения. Далее, а нужно ли вообще учитывать потери на копирование ? Вопрос интересный и на 100% я на него ответа не знаю. А измышлизмы тут могут быть такие. При MMF и небуферированном чтении даные читаются с диска непосредственно на нужное место в ОЗУ и никакого дополнительного копирования не требуется. Но чтение с диска идет в режиме DMA, поэтому когда мы обращаемся к данным - их в кэше процессора нет и они читаются из ОЗУ со скоростью ~1байт/тик. При буферированном чтении данные сначала попадают в файловый кэш и затем копируются в наш буфер. Весь вопрос - как копируются. Если через процессор обычными mov\movsd, то при рекомендуемом размере буфера <= 64K эти данные лишь читаются из ОЗУ и оседают в кэше процессора. Поэтому при обращении к данным они уже сидят в кэше и дополнительных (заметных) потерь при буферированном чтении блоками по 64К вроде как и не должно быть. Потери будут если копирование с места на место идет не через кэш процессора (т.е. через movntq или DMA), или через кэш, но при использовании больших буферов (вытеснение данных из кэша). На практике (где-то я график уже приводил), скорость буферированного чтения незначительно уменьшается при увеличении размера буфера от 4К до 64К (затем - обвал), но связано это с копированием или с другими механизмами работы файлового кэша - сказать трудно.

Ну и еще один "теоретический" довод в пользу "больших" буферов перед "маленькими" - это затраты на вызовы Read\Write. Разумеется затраты есть и при небуферированном чтении блоками менее 8Кб они очень даже существенны, но при увеличении размера блока их относительный вклад монотонно убывает и при 64К ими можно пренебречь - наступает насыщение. А для обычного буферированного чтения вообще после 64К начинается чехарда и резкое падение скорости - тут уже вступают в действие "секретные особенности" реализации файлового кэша ОС. Аналогичные прибамбасы наблюдаются и при MMF, когда размер MapView превышает размер свободной физ.памяти (см.ссылку на тему EvilsInterrupt), можно ли с этим как-то бороться (например ограничением размера working set или еще как) - не знаю.



Ох, рука бойцов писать устала Пока все



PS: на вскидку, если результирующий размер файла может превышать ОЗУ, то возможен вариант с созданием MMF на запись c блочным небуферированным чтением в него данных из отдельных файлов (возможно в асинхронном overlapped режиме). Вот только не знаю как работает MMF с создаваемым файлом - при отказе страницы ОС понимает, что страницы на диске нет ? Судя по прибамбасам - от мелкософтов можно что угодно ожидать ))

 

Еще один вариант сортировки записей - воспользоваться алфавитным методом (линейным в терминологии КК). Для этого в временной папке (желательно на другом HDD относительно исходного) создается набор файлов. Каждый файл в наборе содержит записи, начинающиеся с одного символа (или числа), являющегося первым для соответствующего поля записи (которое используется для сортировки). Например все записи начинающиеся с "A" попадут в отдельный файл. Таким образом в результате получится (согласно распределению первых символов среди всех записей), несколько десятков неособенно больших файлов. Их можно последовательно будет загружать в память, сортировать, и записывать в результирующий файл. Насколько я представляю скорость такого алгоритма будет примерно равна при использовании одного HDD примерно "время чтения + 2 * время записи", а для двух еще меньше. Если брать среднюю скорость чтения 30мб/с, и записи 25мб/с, для 200мб исходного материала весь процесс займет порядка 25 сек.



Все еще конечно зависит от цели алгоритма - если сортировку+слияние надо проводить регулярно и с разными критериями сортировки, лучшие результаты даст индексирование.

 

Может немножко напряжёшься и приведёшь хоть какие-то расчёты или логические доводы?

Ты хоть немножко представляешь математику сортировки записей по полю?

Читать из файла и писать в файл нужно будет при любой методике. По моей методике прочитается только то что нужно для данного этапа (без завершения которого дальше нет смысла вообще что-то делать)и тут же освободится ненужная память когда массив b получен и отдастся под следующую операцию.

Прочитается сначало выборочно одно поле, а значит выгода времени считывания будет равна разности размера поля * коэф. непоследовательного считывания из общего размера базы с коэффициентом последовательного.

И дальше по одному разу считываются данные и по одному разу копируются.

При этом получаем более высокую вероятность размещения данных в памяти а не swapе.

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

Запись когда уже получен указанный массив b можно осторожно оптимизировать развернув цикл на считывание - запись по нескольку записей а не по одной.

Это оптимизация не по сокращению использования памяти, а по скорости с учётом того факта что запрос памяти вовсе не будет означать что тебе её в RAM дадут а уж тем более в кеш. Поэтому в память нужно поместить только то что требуется позарез для работы с большой скоростью - а это сортировка. Ты понимаешь что такое квадратичная функция?

У тебя диски начнут сначала долго пердеть а потом возможно просто сгорят если ты вместо того чтобы манипулировать определяющим полем и его начальными индексами начнёшь строки переставлять местами. Подобный идиотизм я видел в поздних версиях VTUNE, выделило память под само "не хочу" и давай месить там (а реально не там - а в swape), убило у меня диск со всеми материалами к книге во время его "работы". Пока нет данных по каким индексам нужно записывать строки - нефиг вообще что-то мапить и лить в память, ты сам себя послушай - ты говоришь что актуальна будет скорость считывания - а теперь задайся вопросом - на кой хрен что-то считывать в память если тот порядок в котором ты считываешь вообще поменяется? Не проще ли узнать сначала этот самый порядок а потом считывать?

Иначе ты получишь то же непоследовательное чтение, но уже + к тому что ты потратил чтобы слить в память несортированные файлы с базами.

Вообще человек спросил конкретно про операцию - реализацию одной функции управления базой данных на ассемблере. Ему то про SQL ответят то про MMF. Может будут лучше отвечать те кто хоть какое-то подобие баз данных писал на асме, а не оболчки для чужих СУБД, где своими только и были что SQL строчки которые переваривал не собственный движок а код написанный другими дядями?

Прошу прощения если кого задел...

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

Т.е. перед сложением символу переприсваивается значение которое будет соответсвовать его номеру+база в алфавите а не ANSII к примеру коду. Это делается "на лету" внутри алогоритма табличными методами. Т.е. размер хэшевого элемента будет бит на символ+базовый.

Вообще нужно иметь ввиду размер полей в таблице.

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

Не понял :\ что значит заново? Я читаю только одно поле.

 

Согласен, что потери процессорного времени могут быть незначительными перед временем чтения данных с диска, но следует учесть еще один немаловажный фактор - количество запросов ввода-вывода. При возникновении исключения винда читает одну страницу (4кб) и возвращает управление приложению только после полного завершения ее чтения. Затем исключение возникает снова и все многократно повторяется, что приводит к появлению большого числа запросов на чтение мелких блоков данных, что значительно снижает эффективность чтения данных с диска. Конечно система может пытаться читать несколько страниц за раз и использовать другие методы оптимизации этого процесса, но предсказать сколько реально данных нам понадобиться она врядли сможет, поэтому эффективность ReadFile будет в любом случае выше.

 

Строго говоря нам вообще-то не сказали (или я пропустил что-то?) ни под какой камень это делается ни какие винты будут это обрабатывать, ни какова частота микросхем памяти, ни в какой операционке это делается то есть все мы чего-то додумываем за "человечество" глядя на него из своего огорода и недопонятки будут только множится...

 

Проц - Amd 2Ghz, память - 512 Мб, винт - 80 Гб обычный, ОС - любая винда. Естественно, вышеозначенные файлы попадают на указанную конфигурацию с частотой один раз в сутки, другое время они кучей хранятся на дисковых массивах удаленной системы. Сортировку нужно проводить именно по собранной статистике за один день.

 

Broken Sword

Ну вот, если эта конфигурация будет типичной - и думать нечего, сортировка может производиться в памяти. Линейный метод лишь немного ее может ускорить, практически незначительно. Если доступ к массивам организуется с макс. скоростью 100мбит/сек, то в любом случае весь процесс будет занимать 30-60 сек (загрузка данных из сети, плюс сохранение на локальный винт). Хотя если сетевых подключений больше чем одно, можно процесс еще немного ускорить.

 

Ms Rem

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



Broken Sword

Ты не ответил еще на один вопрос: по какому полю производится сортировка - по строковому или числовому (или сводящемуся к числовому, например строковому представлению времени и т.п.) и не являются ли отдельные файлы уже отсортированными (например, по времени получения отсчета с датчика).



The Svin

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

Давай по порядку.

1) С тем, что при сортировке нужно оперировать указателями или индексами никто не спорит - я считаю это само-собой разумеющимся (т.к. 20Мб/200тыс ~ 100 байт на запись - явно многовато для промежуточных пересылок). И кстати про саму методику сортировки я пока ничего не говорил и уж тем более ничего не критиковал, разве что про хэширование строк - т.к. этот вопрос уже как-то раз поднимался с участием volodya и вроде как остался без ответа. И идею со сдвигом на бит и сложением я не понял - вроде как уравнение 2x+y=h имеет множество решений, а значит и разным парам (х,y) может соответствовать одно значение хэша ?



2) С квадратичной зависимостью от N можно поспорить, т.к. N^2 это наихудший случай сравнения каждого с каждым, а быстрые методы сортировки стремятся к пределу k*N*log(N). Например, если сортировать массивы по каждому файлу, а затем делать их попарное слияние, то N^2 от общего числа записей никак не получится



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

А) При формировании массива индексов мы можем читать данные с диска последовательно с максимальной скоростью. Читать "выборочно одно поле" никакого смысла не имеет и скорости не прибавляет, т.к. во-первых, обмен с диском идет как минимум секторами, во-вторых, при MMF или обычном буферированном чтении винда сама за тебя решит какими кусками ей читать данные - это будет никак не 4 и не 512 байт, а от 4К до 64К за раз, в-третьих, при частых обращениях к ReadFile ты будешь иметь ненужные накладные расходы (формирование запросов IRP и\или FastIO, о которых говорил Ms Rem) - от этого скорость чтения только упадет.

Б) Сформировали мы отсортированный массив индексов - теперь нужно записать данные в нужной последовательности в новый файл. Как я уже говорил, по твоей методике в файловом кэше может сохраниться от силы несколько последних прочитанных мегабайт. Поэтому при формировании выходного файла придется читать все исходные файлы заново, но уже со случайным доступом - а это большие затраты на поиск записи и перемещение головок HDD. О небуферированном чтении тут вообще речи не может идти и остается только надеятся на "интеллектуальность" файлового кэша при обычном буферированном чтении. Насколько он хорошо справится с кэшированием десятка-другого файлов я не знаю. Но налицо будут дополнительные существенные затраты по сравнению со случаем, когда у нас после первого чтения значительная часть данных осталась бы в ОЗУ. Во-первых, даже при упреждающем чтении и кэшировании файлов блоками от 4К до 64К за счет произвольного доступа и перемещения головок скорость чтения может упасть до (4-64)К/(5-10)мс = 0.4-12Мб/с вместо 30-40Мб/с при последовательном чтении. Во-вторых, возьмем для примера размер выходного файла порядка 300Мб, упомянутых Broken Sword. Тогда при размере ОЗУ в 512Мб и более вообще все данные после первого чтения могли бы уместиться в ОЗУ и повторное чтение файлов тут выливается в чистые потери времени. Если размер ОЗУ меньше размера файла, то тут вступает в действие вероятность попадания = отношению размера ОЗУ к размеру файла. При соотношении 256/300 можно считать что до 85% случаев мы могли бы брать данные из ОЗУ (т.е. практически "мгновенно") и только 15% пришлось бы подкачивать с диска. Сответственно при отношении 128/300 будем иметь 40% и 60% - хоть и "плохо", но по крайней мере в 1.5 раза быстрее чем читать все заново.



Вывод: ИМХО не следует "жалеть" ОЗУ, нужно при первом чтении максимально загрузить его данными, по возможности не нарвавшись на ненужный свопинг. Тогда при последующем сохранении у нас может быть достаточно большой процент попаданий в ОЗУ и меньше медленных чтений диска со случайным доступом. Разумеется это справедливо при разумных соотношениях размеров ОЗУ и выходного файла. Думаю для прозвучавших цифр ОЗУ 512Мб и размерах файлов ~20Мб это вполне реально, если конечно на момент обработки ОЗУ не забито фиг знает чем Соответсвенно и первоначально лучше читать не отдельные поля, а все целиком - это во-первых, даст возможность сохранить часть данных в ОЗУ, во-вторых, оставит возможности для асинхронного чтения и распараллеливания чтения диска с выполнением частичных сортировок.

 

Кнут, т.3, стр 423:

<font size=1>Одним из распространённых тестов для сравнительной оценки различных средств решения такого рода задач с 1985 года стала сортировка миллиона 100-символьных записей с равномерно распределёнными случайными 10-символьными ключами. Предполагается что исходная последовательность и результат должны храниться на диске, а целью является минимизация времени обработки

...

Методом поразрядной сортировки обрабатывались файлы, распределённые между восемью дисками и задача была решена за 5.1 с. В подобных экспериментах узким местом является скорость ввода-вывода. Процессору для решения этой задачи понадобилось всего 0.6 с!</font><!--size-->

 

А вот такя у меня идея простая. Вобще не сортировать файл.

Файлы смёрджить, лучше собственным драйвером Отсортировать индексы. Создать дописаное поле из индексов которое и использовать в пользовательском выводе. Вот

 

The Svin, Вы только что описАли дерево B+