Очень большие массивы

[MarkM]

Возникла проблема: в программе надо использовать массивы размером больше, чем 4GB.
Напрашивающееся решение - создать библиотеку, которая через memory-mapped files будет хранить массив на диске и по мере надобности подмонтировать нужные секции в память.
Нужен совет вот по каким вопросам:
1. Есть ли какие-то подводные камни в этом подходе?
2. Нет ли уже написанной библиотеки?

П.С. Платформа - Win32.

[trn]V Vin32 adresnoe prostranstvo processa 2Gb. (3Gb v Advanced Server). Kak ne kruti, bol'she v pamjat' ne vpihnesh. Hranit' 2-h Gb sekcii na diske mozhno. Esli u tebja posledovatel'nyj dostup. Esli dostup vraznoboj, to peremaplen'ja sozhrut ves' performans.


[/trn]

[trn] Eshe. Standartnyj podhod vseh BD, bit' fail na stranicy (bloki) i hranit' neskol'ko elementov dannyh v stranice. Tut pravda nado podderzhivat' kesh blokov. No vse eto samomu pisat' - vse ravno chto SUBD s nulja delat'.
[/trn]

[MarkM]

... так как Оракл не поддерживает больше 1К столбцов....

[trn] Pisec! Che za dizajn takoj? Nafig imet' stol'ko stolbov?
[/trn]

[dEBUGER]

Во блин а что там Offset то я прозевал!

А как mapped memory file решает проблему?

Код: Выделить всё

LPVOID MapViewOfFile(
  HANDLE hFileMappingObject,
  DWORD dwDesiredAccess,
  DWORD dwFileOffsetHigh,             // 32 bit +
  DWORD dwFileOffsetLow,              // 32 bit
  SIZE_T dwNumberOfBytesToMap
);

А как код, использующий MMF, вычисляет и хранит индекс для доступа к массиву с потенциальным размером (не числом элементов, размером!) в 64 бит - это вовсе не Win32 проблема.

[tasko]

Во блин а что там Offset то я прозевал!

А вот слона то я и не приметил...



Конечно, это дает возможность замаппить файл большей длины, чем возможно для процесса. Только читать то можно будет все равно только максимум, сколько отводится процессу.
"Mapping a file makes the specified portion of the file visible in the address space of the calling process. "

Я маппил файлы по 800мб. Удовольствие, скажу, не из приятных.
В общем, что-то просто неладно в предлагаемой модели. Перепахать ее как следует, и мукам конец.

[Woozy]

Только читать то можно будет все равно только максимум, сколько отводится процессу.

Автор предполагает читать небольшими пачками несколько объектов типа double, not a problem.

[tasko]

Автор предполагает читать небольшими пачками несколько объектов типа double, not a problem.

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

[Xa-xa]

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

Есть подозрение, что лучше Оракла обработку файлов написать сложно Поэтому ИМХО лучше всего использовать базу, предварительно настроив СУБД.

Насчет медленности работы БД. Согласно моему ограниченному экспириенсу работы с СУБД, оверхед можно _существенно_ уменьшить как минимум двумя способами:

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

2) Отключить опицю fsync (или как там она называется в той СУБД которую Вы используете). Смысл опции в том, чтобы флашить данные на диск, как только коммитится очередная транзакция. Еще, если мне не изменяет склероз, в Оракле есть опция group commit, которая позволяет делать delayed коммит, это когда если за одним коммитом через <n миллисекунд следует другой коммит, то она флашит данные сразу для обоих транзакций.

Насколько я помню, в Оракле подобных опций несколько. Можно посмотреть на все опции с подстрокой "MTTR".

ИМХО если покрутить эти ручки в нужную сторону, то производительность БД можно поднять в *разы*, пожертвовав при этом MTTR.

Кроме того, СУБД обычно использует директ аксесс со своим алгоритмом кеширования, который учитывает историю запросов, итп. Если же Вы решите использовать обычные file IO, то вы будете привязаны к системному buffer/page кэшу.

Суммируя вышесказанное, повторюсь еще раз -- лучше базы Вы ничего не придумаете. Надо только с ней немного поработать и все будет летать на ура.

[aldep]

Народ, спасибо за многочисленные отклики. Не мог сразу всем ответить.
База данных не подходит по следующим причинам:
1. Приложение наше работает с данными заказчика, данные эти поступают в том виде, как я сказал: ~5000 столбцов на ~миллион строк. Сроки выполнения заказа критичны, и нет времени каждый раз пытаться проектировать базу под конкретного заказчика. Дизайн поступающий от заказчика не обсуждается - это данность причем имеющая смысл (см пункт 2)
2. Алгоритмы работы во многом взяты из линейной алгебры, т.е. идет работа со строкой как с целым.
3. Размер алгоритмов порядка 30-100 тыс строк С++ кода. Портировать это на храниые прцедуры не представляется реальным.
4. Все алгоритмы, фактически, взять два значения сложить или умножить, положить обратно и так много часов, если обращаться к серверу БД, даже очень оптимизированному, то занимает кучу времени. Сравните прямое обращение к памяти с вызовом удаленной процедуры на другой машине (процессе).


Насчет файлов:
1. предполагаю подсоединять большии куски в память, чтобы обращения к диску было мало.
2. Исполняться все это будет на мощных серверах, там работа с диском быстрая и не требует процессорных ресурсов. Насколько я знаю обрабатываться могут несколько запросов параллельно.
3. Сервер БД так или иначе все равно использует MM файлы (по крайней мере МС СКЛ).
4. Если действительно производительность так упадет, то попробую делать predictive read. Хотя даже если упадет в 2 раза, то можно мириться. Тут счастливы будут, если вообще работать будет.

Насчет 64-бит процессоров:
1. Итаниум умирает - мы поэтому и не рассматриваем его. Да и очень дорог он. Я все таки получаю не настолько много, чтобы 1-2 месяца моей работы стоили как 8 процессорный сервак.
2. AMD64 еще не имеет стабильной операционки. Как винды выйдут под него так начнем портировать. Да и все равно потребует, чует мое сердце после знакомства с этими алгоритмами, это много затрат.
3. PAE/AWE это что-то типа XMS/EMS то еще извращение. Конечно оно хорошо, но Advanced Server адресует только 8 ГБ, что лучше чем 3, но не намного. Да и работать с ними тоже потребует много програмирования.
4. Спарк не катит: портировать алгоритмы надо раз., тот же софт мы будем продавать заказчикам у которых Wintel стоит в основном это два, дешевый САН не прокатит это три. Нужно что-то с 4-8 процессорами, 8 ГБ памяти


Woozy: Спасибо за линк, буду смотреть.

Lepsik: Ты гонишь .

Долб**б: Спасибо, буду смотреть Рихтера, но по моему там нет ничего нужного, теорию я и так неплохо знаю. Интересует конкретный опыт имплементации.

AMC: Спасибо за советы, буду обращаться к тебе по поводу САСа и бинарного дерева, если не против.

Всем остальным большое спасибо еще раз.

[Woozy]

Автор предполагает читать небольшими пачками несколько объектов типа double, not a problem.

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

Ты заботься о логической правильности и двигай окно View (или класс-обвёртка за тебя сделает). Система позаботится о скорости. Он кэширует. Не надо всё мапить, особенно 2 GB сразу.

Конечно, поэкспериментировать с размером "окна" не помешает. И наверняка есть его оптимальный размер для задачи. Тонкости связаны с реализацией "обёртки". Вроде той, что по ссылке.

[tasko]

Ты заботься о логической правильности и двигай окно View (или класс-обвёртка за тебя сделает). Система позаботится о скорости.

Ну, так сделать можно, конечно. Гложет меня, однако червь сомнения, что окно будет так быстро передвигаться по файлу. Это ж надо предыдущее окно "размаппить", затем следующее "замаппить".
Самому проверять влом. А ежели кто проверит и напишет - тому спасибо.

[Lepsik]

2 alder
-1. Приложение наше работает с данными заказчика, данные эти поступают в том виде, как я сказал: ~5000 столбцов на ~миллион строк. Сроки выполнения заказа критичны, и нет времени каждый раз пытаться проектировать базу под конкретного заказчика. Дизайн поступающий от заказчика не обсуждается - это данность причем имеющая смысл (см пункт 2)

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


2. Алгоритмы работы во многом взяты из линейной алгебры, т.е. идет работа со строкой как с целым.

и в чем проблема ?

3. Размер алгоритмов порядка 30-100 тыс строк С++ кода.

и ???


---Портировать это на храниые прцедуры не представляется реальным.
зачем портировать - ESP на C++ спасут отца демократии

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

медленее, но не малую вещи можно будет сделать проще чем на С++
читай соседний тред про таблицы в памяти


--Lepsik: Ты гонишь .
что за проблемы ?

[aldep]

Самому проверять влом. А ежели кто проверит и напишет - тому спасибо.

Скорее всего этим кто-то буду я

[Lepsik]

посмотри исходники VirtualDub - он легко бегает по файлам десятки гигобайт

[MarkM]

Насчет файлов:
1. предполагаю подсоединять большии куски в память, чтобы обращения к диску было мало.
2. Исполняться все это будет на мощных серверах, там работа с диском быстрая и не требует процессорных ресурсов. Насколько я знаю обрабатываться могут несколько запросов параллельно.
3. Сервер БД так или иначе все равно использует MM файлы (по крайней мере МС СКЛ).
4. Если действительно производительность так упадет, то попробую делать predictive read. Хотя даже если упадет в 2 раза, то можно мириться. Тут счастливы будут, если вообще работать будет.

[trn]Ty ne rasskazal pro dostup k dannym. Eto dejstvitel'no raznobojnyj sluchajnyj dostup ili podchinjaetsja zakonu (prediktiv rid).
Est' li vozmozhnost' razdelit' tablicu na kuski < 2Gb i otdat' rabskim processam na obrabotku?
Mozhet byt' prosto otkryvat' fajl kak tipizirovannyj fail i rabotat' kak s fajlom? OS budet keshirovat' vvdod/vyvod sama. Fizicheski to zhe samoe budet s MM fajlom. V NT mozhno otkryt' faijl s opcijami na posledovatel'nyj ili sluchajnyj dostup, daby pomoch OS opredelit'sja s politikoj keshirovanija i uprezhdajushego chtenija.
Nu esstestvenno chitat' nado po neskol'ku strok za raz daby ne terjat' na I/O kollah.
[/trn]

[MarkM]

Есть подозрение, что лучше Оракла обработку файлов написать сложно Поэтому ИМХО лучше всего использовать базу, предварительно настроив СУБД.

[trn]
Orakl universal'naja SUBD. Vsegda est' vozmozhnost' sdelat' rabotu progi s fajlami bolle optimal'noj putem zatochki pod zadachu.
[/trn]

Насчет медленности работы БД. Согласно моему ограниченному экспириенсу работы с СУБД, оверхед можно _существенно_ уменьшить как минимум двумя способами:

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

[trn]
naoborot, srazu pishet v log, zatem pogodja "lenivo" v datafajl.
[/trn]

2) Отключить опицю fsync (или как там она называется в той СУБД которую Вы используете). Смысл опции в том, чтобы флашить данные на диск, как только коммитится очередная транзакция. Еще, если мне не изменяет склероз, в Оракле есть опция group commit, которая позволяет делать delayed коммит, это когда если за одним коммитом через <n миллисекунд следует другой коммит, то она флашит данные сразу для обоих транзакций.

[trn]
eto po defaultu
[/trn]

Насколько я помню, в Оракле подобных опций несколько. Можно посмотреть на все опции с подстрокой "MTTR".

[trn]
netu MTTR opcij. est' drugie.
[/trn]

ИМХО если покрутить эти ручки в нужную сторону, то производительность БД можно поднять в *разы*, пожертвовав при этом MTTR.

[trn]
CHto za MTTR?
V razy "ruchkami" - vrjad li. Chtob v razy - dizzajn menjat' nado.
[/trn]

Кроме того, СУБД обычно использует директ аксесс со своим алгоритмом кеширования, который учитывает историю запросов, итп. Если же Вы решите использовать обычные file IO, то вы будете привязаны к системному buffer/page кэшу.

[trn]
Mozhno otkryt' fajl s prjamym dostupom k FS. Bez keshirovanija. Chto i rekomenduetsja dlja BD daby iskljuchit' dvojnoe keshirovanie.
[/trn]

Суммируя вышесказанное, повторюсь еще раз -- лучше базы Вы ничего не придумаете. Надо только с ней немного поработать и все будет летать на ура.

[trn]
Uchityvaja specifiku zadachi, navrjad li v BD budet rabotat' bystree.
Odnako razrabotka mozhet sushestvenno uprostit'sja.
[/trn]