Разряженный массив - когда в очень большом массиве хранится не очень много элементов, а большинство ячеек пусты. В винде при помощи функции VirtualAlloc можно выделить память таким образом, что программе будет казаться, что ей выделили весь объем, а реально будут выделины только те страницы, в которых есть данные.
Вопрос: можно ли провернуть такой фокус в unix - системах, и если да, то как.
Для примера можно предположить, что у нас имеется массив структур на 2^24 элементов, из которого реально используется 1024 элемента массива.
>Разряженный массив - когда в очень большом массиве хранится не очень много
>элементов, а большинство ячеек пусты. В винде при помощи функции VirtualAlloc
>можно выделить память таким образом, что программе будет казаться, что ей
>выделили весь объем, а реально будут выделины только те страницы, в
>которых есть данные.
>Вопрос: можно ли провернуть такой фокус в unix - системах, и если
>да, то как.
>Для примера можно предположить, что у нас имеется массив структур на 2^24
>элементов, из которого реально используется 1024 элемента массива.
А зачем?
>В винде при помощи функции VirtualAlloc
>можно выделить память таким образом, что программе будет казаться, что ей
>выделили весь объем, а реально будут выделины только те страницы, в
>которых есть данные.
Ремарочка: в системном программировании на C для Винды.>Вопрос: можно ли провернуть такой фокус в unix - системах, и если
>да, то как.
Если система поддерживает соответствующую часть POSIX (не смогу привести
пример кандидата).>Для примера можно предположить, что у нас имеется массив структур на 2^24
>элементов, из которого реально используется 1024 элемента массива.
Ремарочка: речь у Вас идёт о системном программировании на С.
Речь шла о возможности подобного выделения памяти. Реализуется это при помощи средств ОС, так как именно на нее возлагается задача отслеживать те страницы, которые надо выделять. Процессу же кажется, что у него непрерывное адресное пространство. Мне не известно что-либо о POSIX - поддержке подобных процедур. И хотелось бы выяснить, возможно ли подобное выделение памяти в линуксе или каких-либо других юникс-подобных операционках, и если да, то как?
[...]
>И хотелось бы выяснить, возможно ли подобное выделение памяти в линуксе
>или каких-либо других юникс-подобных операционках, и если да, то как?Я тоже не припоминаю ничего подобного, но особой нужды в подобном методе доступа нет. В курсе программирования советуют для плотных матриц использовать массивы, а для разрежённых - списки. Если ты сам не сможешь реализовать список и к нему простенький хэш или индекс - пиши сюда, что-нибудь накидаем на коленке.
Я полагаю, идеология очевидна - на уровне ОС подобный фокус можно сделать только крайне неоптимально. Скажем, использование единственного int выделяет целую страницу (4К). В списке это займёт 3-4 машинных слова + пару слов в хэше либо одно слово в индексе.
>Я полагаю, идеология очевидна - на уровне ОС подобный фокус можно сделать >только крайне неоптимально. Скажем, использование единственного int выделяет >целую страницу (4К). В списке это займёт 3-4 машинных слова + пару слов в >хэше либо одно слово в индексе.Тут вы несколько заблуждаетесь. Да, расход памяти в случае самого неудачного варианта будет гораздо больше, чем у списка, однако именно при помощи средств ОС возможна реализация самого быстрого варианта. А насчет реализации на основе списков - так это самый убогий в плане быстродействия вариант - если значений достаточно много, то тормоза будут офигенные. Есть правда способы существенного ускорения обхода списка, но гораздо лучше тут подходит бинарное дерево или хэш.
>Тут вы несколько заблуждаетесь. Да, расход памяти в случае самого неудачного варианта
>будет гораздо больше, чем у списка, однако именно при помощи средств
>ОС возможна реализация самого быстрого варианта. А насчет реализации наВ ОС нельзя реализовать "самый быстрый вариант" по самому определению термина "ОС". ОС не знает специфики моей задачи.
>списков - так это самый убогий в плане быстродействия вариант -
>если значений достаточно много, то тормоза будут офигенные. Есть правдаЕсли значений достаточно много (а именно больше log(N)), то массив уже не разрежённый. Для него имеет смысл применять хэши, двоичные деревья и прочие фокусы. Не забывай, что организация и поддержка хэшей и двоичных деревьев совсем не бесплатная.
Ещё подумай вот о чём - поиск в массиве из десятка элементов быстрее всего сделать последовательным перебором, причём без цикла. Любой современный процессор скажет тебе большое пролетарское спасибо.
>существенного ускорения обхода списка, но гораздо лучше тут подходит бинарное дерево
>или хэш.Ещё раз - ты пытаешься найти универсальное решение на все случаи жизни. Его не бывает, нужно внимательно смотреть на задачу.
Двоичное дерево нужно балансировать.
Список+индекс = хэш-функция.Не ожидай, что "хэш средствами ОС" будет за тебя думать - для лучшей производительности тебе придётся подобрать хорошую хэш-функцию.
>Речь шла о возможности подобного выделения памяти. Реализуется это при помощи средств
>ОС, так как именно на нее возлагается задача отслеживать те страницы,
>которые надо выделять. Процессу же кажется, что у него непрерывное адресное
>пространство.
Это есть просто особенность некоторых ОС, вроде системы сообщений Виндури.
Это доп.средство, не дающее _никаких_ преимуществ ни в каком смысле, кроме
личных вкусов разработчиков конкретной ОС и прикладных программистов,
которым это средство кажется удобным.
По этому, речь идёт конкретно о системном программировании, конкретно на
С, конкретно под Виндурь (ну, прлюс, ещё под POSIX мечты).>И хотелось бы выяснить, возможно ли подобное выделение памяти в линуксе
>или каких-либо других юникс-подобных операционках, и если да, то как?
Я уверен, что мало кому сейчас приходит в голову заниматься реализацией
этого, но как обстоит дело точно я сейчас не смогу сказать, нужно время на
раскопки.
>>Вопрос: можно ли провернуть такой фокус в unix - системах, и если
>>да, то как.
>Если система поддерживает соответствующую часть POSIX (не смогу привести
>пример кандидата).
Это ляп.
Думаю об одном (блокировки записей), пишу о другом. Извиняюся я. Ниже есть
разъяснения по поводу приплетения POSIX.
>Разряженный массив - когда в очень большом массиве хранится не очень
>много элементов, а большинство ячеек пусты. В винде при помощи функции
>VirtualAlloc можно выделить память таким образом, что программе будет
>казаться, что ей выделили весь объем, а реально будут выделины только
>те страницы, в которых есть данные.Не совсем так - всё равно придётся следить за тем, где данные есть,
а где их нету. При помещении новых элементов в неиспользуемую область
память нужно коммитить. Да и попытки обращения в незакоммиченные
области нужно пресекать до того, как они произойдут, иначе
"Access violation" гарантирован.>Вопрос: можно ли провернуть такой фокус в unix - системах, и если
>да, то как.
>Для примера можно предположить, что у нас имеется массив структур на 2^24
>элементов, из которого реально используется 1024 элемента массива.Можно поиграться с флагами mmap()а. Точной аналогии не будет, однако
что-то похожее может получиться. Честно говоря, не вижу большого смысла -
всё равно поверх средств ОС здесь нужно реализовывать свои средства
проверки валидности индексов в этом хитром массиве. Существенного
ускорения по сравнению с реализацией, скажеи, через хеш-таблицу
не получится.
сам такими эксперементами не занимался, НО можно покапать в таком направлении :
1) в *NIX есть такая штука как файлы с 'дырками' то есть файлы, часть пространства которых не имеет физ. привязки, То есть текущее смещение в открытом файле может быть около 1gb, а реально аллоцированно порядка 10 блоков..
(такие файлы получаются через truncate вызовы, но, в теории,
не в каждой ФС)
2) отображение файлов в память - хлеб насущный упомянутых nix, и никто не запретит отобразить подобный файл или его часть в память...
3) тут много-много граблей..есть возможность начисто забить ФС..есть маза поставить в тупик средства резервного копирования и получить п@#$% от админа...
4) есть охренительное число более простых способов ;-)
Спасибо за интересные идеи. Файл с дырками - это похожая по смыслу конструкция. Не знаю правда, удастся ли при помощи него изготовить разряженный массив :) Жаль конечно, что нет юниксового VirtualAlloc - тут винда далеко впереди :(. (Для тех, кому интересно - см. например книгу Дж. Рихтера)
>Спасибо за интересные идеи. Файл с дырками - это похожая по смыслу
>конструкция. Не знаю правда, удастся ли при помощи него изготовить разряженный
>массив :) Жаль конечно, что нет юниксового VirtualAlloc - тут винда
>далеко впереди :(. (Для тех, кому интересно - см. например книгу
>Дж. Рихтера)А Вы почитайте http://www.genesys-e.de/jwalter/mix4win.htm
:))
Удачи
--- sas
>Спасибо за интересные идеи. Файл с дырками - это похожая по смыслу
>конструкция. Не знаю правда, удастся ли при помощи него изготовить разряженный
>массив :)
Выложите код потом -- такое надо выставлять на общее обозрение, определённо.
Это всё полезно не только Вам лично: многие плохо представляют, где раки
зимуют.>Жаль конечно, что нет юниксового VirtualAlloc - тут винда
>далеко впереди :(. (Для тех, кому интересно - см. например книгу
>Дж. Рихтера)
Джефри Рихтер? О чём это Вы? Книга очень хороша, автор уважаемый эксперт,
пишет очень ясно и точно. Я тоже рекомендую. Но это Вы о "посмотреть о
VirtualAlloc()" (тогда можно и по документации), или "посмотреть о далеко
впереди" (вот этого я у него не встречал, хорошо бы уточнить цитаткой).Может программку напишем, чтобы прозреть окончательно:
// Mememory Allocation Test
#include <unistd.h>
#include <cstdlib>
#include <iostream>
using namespace std;int main(int argc, char* argv[]){
if( argc != 3 ){
cerr << "usage: " << argv[0] << " n m" << endl;
exit( EXIT_FAILURE );
}
int n= atoi( argv[1] );
int m= atoi( argv[2] );
cout << "Выделяю массив из " << n << " char..." << flush;
char* pa= new char[n];
cout << "\tсдделано." << endl;cout << "Записываю " << m << " +- 1 значений..." << flush;
int d= n / m;
for( int k= 0; k < m; k+= d ){
pa[k]= k;
}
cout << "\tсделано." << endl;cout << "Освобождаю массив..." << flush;
delete []pa;
cout << "\tсделано." << endl;
return EXIT_SUCCESS;
}
// EOFТеперь нужно посмотреть как она жрёт память при разном количестве реально
использованных данных. Даже просто утилитка time (Гнусной версии) покажет
кое-какую информацию для размышлений.
Сильно рекомендую проделать подобные эксперименты, после окончания
которых стоит поразмышлять о причинах столь убогой поддержки блокировок
записей по образу мысли POSIX со стороны всех BSD образных версий UNIX.
> cout << "Записываю " << m << " +- 1 значений..." << flush;
> int d= n / m;
> for( int k= 0; k < m; k+= d ){
Очепятка, не влияющая серьёзно на результат.
Исправить:
for( int k= 0; k < n; k+= d ){
Результат выполнения наводит на размышления. Я запускал программу, которую вы предложили с очень большими значениями размера массива:./memtest 1000000000 1000
(это не опечатка - там действительно девять нулей) Тестовая машина - Athlon 2700/2x512 Mb PC3200 + свап метров на 250. Ядро линукс версии 2.4.29. Память выделялась практически мнгновенно и без вопросов(!) К сожалению, у меня какая-то не такая версия команды time (а может руки кривые) - мне так и не удалось вытянуть из нее что-то кроме времени выполнения. Оно незначительно менялось при изменении размера выделяемого массива и сильно колебалось при изменении числа заполняемых элементов. Так как с командой time у меня ничего путного не вышло, я решил попробовать запустить команду top в одной консоли и выделять массив в другой. Команда top ни разу не показала, что что-то кушает гигантские объемы памяти. Тестовой программы вообще не было в ее выводе, а на первом месте висел ogg123 :). Вообще по ощущениям при выделении 1000000000 байт памяти никаких видимых эффектов не было - как будто система по умолчанию создает разряженный массив. Кто-нибудь исследовал, как происходит выделение памяти процессу - может никаких специальных усилий по созданию разряженного массива предпринимать и не надо? И чем еще можно посмотреть статистику по использованию памяти (я пока придумал cat /proc/meminfo). Еще хотелось бы узнать, как выделение больших кусков памяти будет работать под другими операционными системами - если кто попробует - сообщите пожалуйста результат.
при выделении памяти функциями malloc и new ,
требуемый кусок сначала ищется в текущей куче (куча это кусок до конец сегмента данных), если там не найденно, то изменяется конец (размер) сегмента через вызов sbrk.. учитывая странично-сегментный механизм управления памятью - реальное выделение памяти под страницу происходит только при обращении к ней (причем без разницы на чтение или запись), до этого момента она отмеченна просто как отсутствующая.
На первый взгляд конечно похоже на разряженный массив...
НО вот только пользователь не должен на это полагаться (т.е. на конкретный физический метод управления памятью в системе)
>./memtest 1000000000 1000
>
>(это не опечатка - там действительно девять нулей)
Предел int на 32-х разрядной архитектуре -- около 2 миллиардов. Адресное
пространство для UNIX -- 4Г (а не 2Г, как в Win32).>Память выделялась практически мнгновенно и без вопросов(!)
А какие могут быть проблемы?>К сожалению, у
>меня какая-то не такая версия команды time
Под Linux time способна возвращать слишком мало информации, поэтому
разработчики дистрибутивов компилируют её так убого.
Можно скачать её отсюда:
http://gnu.tsuren.net/directory/GNU/time.html
и скомпилировать (можно с другим именем, например, gtime).
Но это мало что даст.>Так как с командой
>time у меня ничего путного не вышло, я решил попробовать запустить
>команду top в одной консоли и выделять массив в другой.
Проще сделать так, чтобы программка сама вызывала ps в нужный момент.
Вот новый вариант:// Mememory Allocation Test
// POSIX
#include <unistd.h>
#include <sys/types.h>
// C++
#include <cstdlib>
#include <iostream>
#include <sstream>
using namespace std;int main(int argc, char* argv[]){
if( argc != 3 ){
cerr << "Формат: " << argv[0] << " n m" << endl;
exit( EXIT_FAILURE );
}
pid_t pid= getpid();
int n= atoi( argv[1] );
int m= atoi( argv[2] );
ostringstream strout;
strout << "ps -eo pid,%mem,args | egrep '(^ *" << pid << ")'";cout << "Выделяю массив из " << n << " char..." << endl;
char* pa= new char[n];
system( strout.str().c_str() );cout << "Записываю " << m << " +- 1 значений..." << endl;
int d= n / m;
for( int k= 0; k < n; k+= d )
pa[k]= static_cast<char>( k % (1 << sizeof(char)) );
system( strout.str().c_str() );cout << "Освобождаю массив..." << flush;
delete []pa;
system( strout.str().c_str() );
cout << "Это всё. Удачи!" << endl;
return EXIT_SUCCESS;
}
// EOF>Вообще по ощущениям при выделении 1000000000 байт
>памяти никаких видимых эффектов не было - как будто система по
>умолчанию создает разряженный массив.
Наверно, я всё-таки прав насчёт того, что пара подобных экспериментов
лучше любого трёпа на технические темы...>может никаких специальных усилий по созданию разряженного массива
>предпринимать
>и не надо?
Не надо.>И чем еще можно посмотреть статистику по использованию
>памяти (я пока придумал cat /proc/meminfo).
Лично я привык к ps.>Еще хотелось бы узнать, как
>выделение больших кусков памяти будет работать под другими операционными
>системами
Поразному.
>Не совсем так - всё равно придётся следить за тем, где данные
>есть,
>а где их нету. При помещении новых элементов в неиспользуемую область
>память нужно коммитить. Да и попытки обращения в незакоммиченные
>области нужно пресекать до того, как они произойдут, иначе
>"Access violation" гарантирован.
>
Пояснение для Винды - привожу, чтобы устранить возможное недопонимание того, как это там может быть реализовано:
В книге Дж. Рихтера приводится примерно такой алгоритм действий (естественно, он его излагает более подробно, это моя вольная интерпретация)
1. При помощи VirtualAlloc приложение говорит опреационной системе "зарезервируй для меня этот кусок памяти, но сразу не выделяй. Я потом самостоятельно займусь выделением"
2. Приложение регистрирует свой обработчик исключительной ситуации "обращение в никуда", в котором, если возможно, происходит выделение требуемой страницы.
3. При обращении к несуществующей странице происходит исключение и память выделяется (либо сообщается о невозможности этого сделать). При обращении к существующей странице все работает как обычно.
У Рихтера есть пример программы "SpreadSheet", где по такой технологии создается разряженный массив на 256 Мб. При этом реально используется порядка нескольких килобайт. По моему, это очень элегантное решение проблемы. Именно это я хотел сказать, когда утверждал, что VirtualAlloc рулит.
Очень низкоуровневый код получается. И как следствие, завязанный
на специфику MMU x86-совместимых процессоров. В POSIX подобных
средств нету, так как MMU "среднестатистического" процессора
совершенно не обязан уметь такие вещи.Работать будет, конечно, неплохо, однако существенного преимущества
в скорости по сравнению хотя бы с реализацией того же массива на
базе хеш-таблицы IMHO не будет. А код получается настолько же
громоздкий. Так что, опять же IMHO, оно того не стоит.
>В POSIX подобных
>средств нету
Тут я и перечитал своё первое сообщение...
Полезное это занятие, оказывается!>Работать будет, конечно, неплохо
Как мне кажется, это всё по сути -- предоставление программисту возможности
реализовывать по-своему алгоритмы, которыми обычно занимается ядро.
Конечно, в любой конкретной задаче можно написать лучше ядрёной реализации.
Но ядро-то на то и нужно, чтобы в нём были реализованы средства, которые
нужны особенно часто, пусть и не оптимальным способом (оптимального нет).
Для Linux это вообще лишено смысла; хочешь писать ядро -- пиши прямо в него.