Оптимизация временных файлов

[bin]

Посоветуйте, пожалуйста, как оптимизировать по времени следующую задачу:
научно-исследовательская программа (не коммерческая и не учебная) в ходе вычислений создает квадратную матрицу, в которой элементы являются текстовыми строками (паскалевский тип string) неограниченной длины. Матрица заполняется по столбцам сверху вниз, потом нужно отсортировать элементы каждой строки матрицы и объединить их в одну строку. Т.е. из матрицы в $n$ строк (столбцов) получаем $n$ текстовых строк (надеюсь, путаницы с понятиями «строка матрицы» и «string» не возникло).

Для сравнительно небольших $n$ проблем нет, но при увеличении $n$ не хватает памяти. Очевидный путь преодоления этого ограничения: сохранять данные во временном внешнем файле. Это хорошо еще и тем, что можно будет прерывать работу программы и досчитывать в другой день – мне не удобно без особой необходимости сутками крутить компьютер.

В качестве модели я написал следующий код (Delphi-7):

procedure TForm1.Button1Click(Sender: TObject);
const
 nm = 1000; // можно уменьшить для отладки
var
 i,j,k : integer;
 s,path,fname : string;
 f : textFile;
 t0,t1 : TDateTime;
begin
  path := extractFilePath (application.ExeName)+'tmp';
  MkDir (path); // создаем папку tmp
  t0 := now;      // стартовое время
  for i:=1 to nm do  // для строки i  
   begin
    for j:=1 to 1000 do // для столбца j
     begin
        s := '';
        for k:=1 to 1000 do
         s := s+intToStr(k*i)+', '; // имитируем вычисление элемента (i, j)
        fname := path+'\'+intToStr(j)+'.txt'; // вычисляем имя файла
        assignFile (f,fname); // связываем имя с файловой переменной
        if fileExists (fname) then  // файл существует, дописать в конец
          append (f)
        else // файл не существует, создать его
          rewrite (f);
        writeln (f,s); // записываем элемент (i, j) в файл
        closeFile (f); // закрываем файл
     end;
      Caption := intToStr(i); // отображаем прогресс
    end;
   t1 := now; // финишное время 
  Button1.Caption := 'Done';
  Label1.Caption := ('test finished '+ FloatToStr(SecondSpan(t1,t0))+' sec.');
end;

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

На Pentium-4 (3 ГГц), ОЗУ 1 Гб, ОС Windows XP SP3 приведенный код отрабатывает примерно за два часа (зависит и от качества винчестера). А нельзя ли сократить это время? В руководствах пишут, что блочная запись в файл работает быстрее, чем writeln, что вызов функций API напрямую убыстряет работу, возможно и TFileStream стоит использовать, однако не уверен, что это радикально улучшит дело. У кого были подобные задачи с временными файлами? Есть ли публикации? Инет ресурсы? (Не хотелось бы изобретать велосипед )

[Sphinx Pinastri]

1. Выкинуть (или отдать пионерам) всё старьё: Pentium, Windows, Pascal.
Один день работы программиста стоит больше, чем хороший компьютер.
Поставить i3770 с 64GB памяти. Может, этого и хватит.

2. Оценить, сколько времени занимает

for k:=1 to 1000 do
        s := s+intToStr(k*i)+', '; // имитируем вычисление элемента (i, j)

Скорее всего, вы измеряете скорость работы этого фрагмента,

3. Не закрывать файлы. Открыть сразу 1000 файлов и писать, куда надо.
Если операционная система или язык такого не умеют, то см. пункт 1.

4. Поставить SSD или разложить временные файлы на разные диски.

[Pavia]

bin
Первое не стоит гадать, а надо взять инструмент для измерения производительности.
http://en.wikipedia.org/wiki/List_of_pe ... ysis_tools
Второе надо научиться понимать результаты. Так как в половине инструментов(или большинстве) результаты не очень наглядно отображаются.

Что касается кода, то основные потери из-за того что постоянно открываете файл. Строка

 append (f) // на эту строчку приходиться около 67% времени.

 s := s+intToStr(k*i)+', '; // на эту строчку приходиться около 11% времени

Когда как на сому запись

  writeln (f,s); //на эту строчку приходиться только 8.5 %

Последняя строчку вы не ускорите, так как она выдает максимум и ограничена скоростью жёсткого. А вот уменьшить другие 2 пункта можно.
Причем первый пункт можно свести к мину времени. И получить выигрыш в около 1000/(110+85)=5,1 раза.

Цитата:

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

Это всё мелочи. И на них не стоит тратить время. Конечно запись надо делать не по одному элементу, а блоком размером несколько десятков-сотен килобайт(подбирает имперически).

А вот отказаться от перевода цифр в строку и обратно стоит. Так как то пустая трата времен. Это даст уменьшение объёма до 5 раз. И как следствие скорость записи тоже до 5 раз.
Работать надо со внутренним форматом - это бинарный формат, машинно ориентированный.

[bin]

Sphinx Pinastri
Я предвидел такой совет и не даром написал:

bin в сообщении #700761 писал(а):

научно-исследовательская программа (не коммерческая и не учебная)

Т.е. $n$ инфинитно, т.е. цель вычислительного эксперимента увеличивать $n$ насколько возможно. Если очередные результаты окажутся положительными, то нужен будет не просто новый ПК, а суперкомп, можно будет и новое сообщество добровольных вычислений в сетке открыть. Но сейчас это преждевременно. И в любом случае найдется $n$ , для которого памяти не хватит и на суперкомпе. Поэтому вопрос в том, как преодолеть это ограничение вне зависимости от конкретного размера памяти.

(Оффтоп)

Sphinx Pinastri в сообщении #700899 писал(а):

Один день работы программиста стоит больше, чем хороший компьютер.

Полностью согласен в принципе, но на практике, если минуту погуглить, то для Москвы увидим предложения производительных малошумящих ПК с водяным охлаждением ("для дома и офиса") примерно за 100 тыс.руб. Согласитесь, что это на пару порядков выше, чем средняя зарплата программиста в день Но дело не в деньгах. Чтобы комп надежно работал, собирать его нужно самому и систему ставить самому. В общем на выбор, сборку, установку и конфигурирование уйдет не один день. Прогресс движется стремительно. И по уму нужно было бы менять компы (мне нужно как минимум 2) каждые полгода. Но вот времени жалко. Убежден, что без явной необходимости часто менять машинный парк нецелесообразно.

Sphinx Pinastri в сообщении #700899 писал(а):

Скорее всего, вы измеряете скорость работы этого фрагмента

Это просто проверяется. Удалив I/O увидим, что на фрагмент тратится менее 20% времени.

Sphinx Pinastri в сообщении #700899 писал(а):

Не закрывать файлы. Открыть сразу 1000 файлов и писать, куда надо.

Я думал об этом. В MSDN с ходу информации не нашел (сколько же там шума!), погуглил и увидел, что многих занимает вопрос, сколько файлов можно открыть одновременно. Одна команда, у которых сервер из-за нескольких тысяч открытых файлов зависал, описала историю, как они завалили этими вопросами специалистов Микрософта. (Внятного ответа так и не получили.) Еще пишут, что в Линуксе допустимое число открытых файлов устанавливается в явном виде (я не проверял) - рекомендации различные, примерно 1500 файлов на всю систему. Столько рекомендуют и для "Окон". И что делать, когда я захочу считать $n=10000$ ?

Sphinx Pinastri в сообщении #700899 писал(а):

Поставить SSD или разложить временные файлы на разные диски.

Про разные диски не понял. Вы имеете в виду физические диски? Или если и на разные логические (одного физического) разложить, тоже можно ждать ускорения. Почему? SSD я собираюсь поставить (уже на новый комп), но моего вопроса это не снимает: и на быстром устройстве должна быть оптимизированная программа (как и на медленном).

-- Пн мар 25, 2013 14:30:16 --

Pavia

Pavia в сообщении #701102 писал(а):

Первое не стоит гадать, а надо взять инструмент для измерения производительности.

Ok! Для точных измерений я обычно использую Intel VTune Performance Analyzer, но на данном этапе я просто спрашивал о подходе. Если кто сталкивался с подобной задачей, он может сразу без всяких измерений сказать, что надо делать иначе. Вот и Вы считаете, что блочная запись - это мелочи. Вы это проверяли?

Pavia в сообщении #701102 писал(а):

s := s+intToStr(k*i)+', '; // на эту строчку приходиться около 11% времени

Это модель, где вместо вызова цепочки процедур в несколько тысяч строк поставлен оператор, не несущий особого смысла. В реальной программе цепочка, возможно, будет тратить более 50% времени, но это другая проблема. Т.о. Ваше совершенно верное замечание:

Pavia в сообщении #701102 писал(а):

Работать надо со внутренним форматом - это бинарный формат, машинно ориентированный.

относится исключительно к модели.

Pavia в сообщении #701102 писал(а):

Причем первый пункт можно свести к мину времени.

Не понял, поясните, пожалуйста. Как оптимизировать открытие файла? Не закрывать файл? Выше в ответе Sphinx Pinastri я написал подробно о своих сомнениях в таком решении.

[rockclimber]

bin в сообщении #701111 писал(а):

Sphinx Pinastri
Я предвидел такой совет и не даром написал:

bin в сообщении #700761 писал(а):

научно-исследовательская программа (не коммерческая и не учебная)

Т.е. $n$ инфинитно, т.е. цель вычислительного эксперимента увеличивать $n$ насколько возможно. Если очередные результаты окажутся положительными, то нужен будет не просто новый ПК, а суперкомп, можно будет и новое сообщество добровольных вычислений в сетке открыть.

Использование СУБД не спасет отца русской демократии? Если Delphi осилили, то прикрутить к нему хотя бы тот же PostgreSQL будет вопросом пары дней. Храните гигабайты строк и делайте с ними что захотите и когда захотите.

P. S. И SQL отлаживать в разы проще, чем любой другой язык. Хотя для этого его сначала придется выучить (еще пару дней прибавьте).

[Pavia]

Ваш пример очень странный.
1) Зачем куча файлов? Почему не один. Доступ к одному большуму файлу гораздо быстрее чем к куче маленьких.
2) Почему открытие файла находится во 2-ом вложенном цикле? Его надо вынести из цикла. См следующий пункт.
3) Почему добавление в файл идёт интерационно? Оно должно быть последовательным. Поменяй циклы местами.
4) Вызов в цикле s:=s+s0; приводит к перевыделению памяти и копированию всей строки s. Что посути аналогично ещё одному циклу. Поэтому данный код тормазит. Понятно что это первое что пришло в голову.

По поводу блочной записи и write. Write максимум может выполнить лишнее копирование, а это 10% по сравнению blockwrite.

По поводу ssd они не намного превосходят HDD по скорости линейного чтения. А вот если случайный доступ, то HDD начинает сдавать.
Поэтому на маленьких файлах когда их много SSD выигрывает у HDD.
И для оптимизации работы с HDD надо линеализовывать обращения.

На win7 вся свободная память отводится под кэш диска.

[rockclimber]

Pavia в сообщении #701274 писал(а):

4) Вызов в цикле s:=s+s0; приводит к перевыделению памяти и копированию всей строки s. Что посути аналогично ещё одному циклу. Поэтому данный код тормазит. Понятно что это первое что пришло в голову.

Нет (ну или не совсем). Delphi хранит длину строки в памяти вместе со строкой, поэтому перевыделение памяти происходит быстро, независимо от длины строки.

[bin]

Прежде всего спасибо всем ответившим!!! Я и надеялся на именно такое обсуждение. Далее я начну задавать дополнительные вопросы, но не хочу показаться таким, который, по анекдоту, спрашивает совета только затем, чтобы ему не следовать - и потому заранее поблагодарил всех

rockclimber в сообщении #701174 писал(а):

Использование СУБД не спасет отца русской демократии? Если Delphi осилили, то прикрутить к нему хотя бы тот же PostgreSQL будет вопросом пары дней.

Я не только Delphi осилил, но и такие языки, как Dee - слышали о таком? SQL знаю неплохо, и публикации по оригинальным физ-хим СУБД в журналах РАН имею, но почему-то сомневаюсь, что "Использование СУБД" спасет в данном случае. Если сможете, то, пожалуйста, приведите более развернутую аргументацию.

Pavia в сообщении #701274 писал(а):

Ваш пример очень странный.1) Зачем куча файлов? Почему не один. Доступ к одному большуму файлу гораздо быстрее чем к куче маленьких.

Да, это так. Может, у меня затмение, но не могу придумать, как из одного большого файла сделать нужное эффективно. Если Вы знаете, подскажите, please.

Pavia в сообщении #701274 писал(а):

3) Почему добавление в файл идёт интерационно? Оно должно быть последовательным. Поменяй циклы местами.

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

Pavia в сообщении #701274 писал(а):

4) Вызов в цикле s:=s+s0; приводит к перевыделению памяти и копированию всей строки s. Что посути аналогично ещё одному циклу. Поэтому данный код тормазит.

Выше я написал, что это только модель. Но если Вы знаете более эффективные методы добавления новой подстроки к строке, то я с благодарностью Вас выслушаю. (Можем перейти и на ассемблер, но практика показывет, что D-7 делает очень эффективный код.)

[Joker_vD]

bin в сообщении #701427 писал(а):

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

CreateFileMapping/MapViewOfFile. Особенно если у вас столбец матрицы в память не влезает... кстати, "не влезает" в смысле "виртуальное адресное пространство закончилась"?

[bin]

Joker_vD в сообщении #701429 писал(а):

bin в сообщении #701427 писал(а):

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

CreateFileMapping/MapViewOfFile. Особенно если у вас столбец матрицы в память не влезает... кстати, "не влезает" в смысле "виртуальное адресное пространство закончилась"?

Да, закончилось. Чем тут поможет CreateFileMapping/MapViewOfFile?

[rockclimber]

bin в сообщении #701427 писал(а):

rockclimber в сообщении #701174 писал(а):

Использование СУБД не спасет отца русской демократии? Если Delphi осилили, то прикрутить к нему хотя бы тот же PostgreSQL будет вопросом пары дней.

Я не только Delphi осилил, но и такие языки, как Dee - слышали о таком? SQL знаю неплохо, и публикации по оригинальным физ-хим СУБД в журналах РАН имею, но почему-то сомневаюсь, что "Использование СУБД" спасет в данном случае. Если сможете, то, пожалуйста, приведите более развернутую аргументацию.

Чтобы привести более развернутую аргументацию, мне нужно знать подробнее ваши алгоритмы и объем данных, которыми вы оперируете. Я пока просто спросил - не задумывались ли вы использовать БД? Или может уже пробовали?
Пока вы просили помочь оптимизировать работу с файлами, в которых вы храните промежуточные результаты. Хорошие промышленные СУБД умеют эффективно работать с диском, но придется почитать документацию для настройки. Postgres я рекомендовал в силу бесплатности и простоты настройки. Но у Postgres настройки "по умолчанию" (о чем прямо сказано в документации) такие, чтобы "максимально не мешать остальным программам". Так что начать придется прямо с документации. Из бесплатных - это лучшая СУБД. Еще можно Oracle, но Oracle сильно сложнее в устройстве и бесплатными будут только первые 11 ГБ. Еще есть MS SQL, но я с ним не сталкивался и рекомендовать не буду.

Еще немного плюсов:
1. Как я понял, вы преобразуете строки в числа - СУБД не будет тратить на это время.
2. У Oracle и Postgres есть возможность писать код на встроенных языках (у Oracle - C, PL/SQL и Java, у Postgres - C, Python, Perl, pl/pgSQL и еще немного по мелочи). Не знаю, как на счет скорости в сравнении с Delphi, но есть неплохие возможности оптимизации: если результат работы вашей процедуры/функции зависит только от входных параметров, СУБД будет хранить в кэше результат вычисления и использовать его каждый раз вместо вычисления заново, когда в функцию будут передаваться точно такие же параметры (это только одна из возможностей).
3. Быстрый поиск нужных данных в большом массиве. Очень быстрый, вряд ли вы напишете быстрее за приемлемое для вас время (хотя это будет зависеть от вашей задачи).
4. Есть возможность явно указать СУБД, какую долю данных в процессе расчета держать в оперативной памяти - тогда СУБД будет сама решать, когда писать на диск, причем за целостностью данных она тоже будет следить. Опять же устойчивость к сбоям у них очень хорошая, заставить хорошую СУБД потерять данные практически невозможно, а тупое выдергивание вилки из розетки - это для них детская шалость .

P. S. Я работаю с ораклом последние два года, так что мои советы будут немного похожи на поговорку "человек, умеющий пользоваться молотком, в любой задаче видит гвоздь".

[Pavia]

bin

Цитата:

у, в которой элементы являются текстовыми строками (паскалевский тип string) неограниченной длины.

Паскалевские строки как раз ограничены и у Delphi тоже.
Вопрос в том какой длины строки? Если как в примере около 4КБайт , то тут можно думать о дисковой оптимизации. А если больше 256 КБайт, то тут не стоит задумываться о том как писать или читать.

Цитата:

Да, это так. Может, у меня затмение, но не могу придумать, как из одного большого файла сделать нужное эффективно. Если Вы знаете, подскажите, please.

Сваливаем всё в один файл последовательно. Плюс параллельно создаём индексный файл. Как в СУБД.

А вообще для сортировки наверно достаточно первых 1-8 байт строчек. Эти первые 1-8 скорее всего уникальные для строчки. Так что можно сформировать в отдельный файл.

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

Ещё после сохранения можно подумать над транспонирование строк в файле. Есть быстрые алгоритмы транспонирования. Кэши или блочный алгоритм транспонирования. хотя скорее всего транспонирование вам не понадобится.

Тоже думаю что будет проще взять СУБД.

[bin]

Pavia в сообщении #701458 писал(а):

Паскалевские строки как раз ограничены и у Delphi тоже. Вопрос в том какой длины строки? Если как в примере около 4КБайт , то тут можно думать о дисковой оптимизации. А если больше 256 КБайт, то тут не стоит задумываться о том как писать или читать.

Ограничены разрядностью нулевого элемента (в Delphi отличается от разрядности остальных), который хранит длину строки и т.о. больше $2^{32}-1$ символов в строку типа string не записать.(Кажется, в первых версиях Delphi были проблемы с очень длинными строками, и конечно же нужно свериться с руководством пользователя, прежде чем утверждать). При этом никто не мешает сделать собственный тип для строк длиннее $2^{32}$. В моей задаче строки могут быть разной длины. Средняя длина растет с ростом $n$ нелинейно, а по меньшей мере квадратично. Выше я уже сказал, что цель насколько возможно увеличить $n$. Это и отвечает на вопрос, что строки могут быть очень длинными.

Pavia в сообщении #701458 писал(а):

А вообще для сортировки наверно достаточно первых 1-8 байт строчек. Эти первые 1-8 скорее всего уникальные для строчки. Так что можно сформировать в отдельный файл.

Не тот случай: в моем случае строки могут полностью совпадать, т.о. при сравнении иногда придется сравнивать все символы. В Delphi, естественно, сравниваются символы до первого несовпадения.

Pavia в сообщении #701458 писал(а):

Сваливаем всё в один файл последовательно. Плюс параллельно создаём индексный файл. Как в СУБД.

Если я правильно понял, Вы предлагаете писать в индексном файле позицию первого символа каждой строки, а также значения i,j (место элемента в матрице). Т.о. придется постоянно делать выход на нужную позицию файла данных. Диск конечно же не лента, но все же переспрошу: Вы уверены, что так будет быстрее, чем с кучей файлов?

rockclimber в сообщении #701456 писал(а):

Как я понял, вы преобразуете строки в числа

Нет. В модели я преобразовывал числа в строки. В реальной программе более сложная структура данных, которая в настоящий момент описывается дюжиной БНФ. Нет смысла их тут все приводить, приведу одну упрощенную формулу:

<элемент матрицы>::=<натуральное число>{<разделитель><натуральное число>}

При этом нужно несколько разделителей, например, ",",".","&", а еще и скобки "(",")" (приведенная формула скобки не учитывает), понятно, что речь идет о рекурсивной структуре данных. Про натуральные числа можно утверждать, что они в каждой строке принимают все значения от 0 до $n$ . И тут возникает дополнительный вопрос: как лучше представить такую последовательность чисел с несколькими типами разделителей и скобками? В модели я пошел по самому примитивному пути - взял строки. Но правы те, кто указал, что такое представление не лучшее. Какое лучше на Ваш взгляд? Нужно только отметить, что по мере развития алгоритма приходится корректировать список разделителей и скобок, т.е. формат не полностью устоялся и хотелось бы выбрать достаточно гибкое представление, чтобы не переписывать много кода, если вдруг выяснится, что нужен еще один тип разделителя.

Про СУБД я серьезно задумался. Для СУБД моя задача выглядит слишком примитивной и большую часть возможностей СУБД она использовать не будет. Но и за неиспользованные возможности приходится платить, и вопрос в том, не окажется ли такая плата слишком высокой для производительности? Но наверное никто не сможет ответить мне на вопрос: что лучше в данном случае? сделать маленькое и специализированное или взять уже готовое, большое и универсальное? Придется пробовать: сделать и то и другое, и посмотреть, что будет работать быстрее. Технический вопрос: а есть ли в рекомендованных здесь СУБД ограничения на размер строки (или на вектор байтов)? Допускаются ли записи, размер которых меняется динамически во время выполнения? Насколько мне сейчас представляется,
каждая запись БД будет содержать три поля:

i,j:integer; // уникальные ключи
s: string; // или s: array of byte; ключ для сортировки

[arseniiv]

bin в сообщении #701637 писал(а):

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

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

[Joker_vD]

bin в сообщении #701637 писал(а):

Если я правильно понял, Вы предлагаете писать в индексном файле позицию первого символа каждой строки, а также значения i,j (место элемента в матрице). Т.о. придется постоянно делать выход на нужную позицию файла данных. Диск конечно же не лента, но все же переспрошу: Вы уверены, что так будет быстрее, чем с кучей файлов?

Все это можно делать в одном файле. Особо промышленные СУБД, говорят, вообще под свои нужды целый раздел диска брали и сами ввод-вывод организовывали, но может, и байка это.