Безразмерный саморасширяемый массив как некая неисчерпаемая виртуальная память

#c++ #алгоритм

Пытаюсь сам реализовать безразмерный саморасширяемый массив, вначале на 2Gb, затем
больше. Т.е. при обращении к элементу массива чтобы проверялось, есть ли кластер в
оперативке, и выдавался кластер, если нет - чтобы кластер грузился из файла. Если кластеров
много - менее используемые выгружались. Т.е. как некая неисчерпаемая виртуальная память.
Цель - закешировать результат выборки из любой СУБД, например, если она вернула миллион
строк.

Может, есть готовая библиотека реализующая это через IStream интерфейс работы с файлами,
или что-то такое? Часть СУБД бывают 32bit, чтобы решение могло работать и в 32bit,
и 64bit. VirtualAlloc не подходит (адресное пространство в 32bit ограничено).

В идеале нечто такое

class BigArea{


  operator char& [] (__int64 index) {
      char * tmp_buff;
     //...
      return &tmp_buff[ index & 4095]; // Т.к. блок памяти 4096 байт.
      }
  }


Как источник "неисчерпаемой" памяти.
Есть ли библиотека, которая позволит закешировать 2-4-10 Gb памяти, разместив "лишнее"
на диске, а наиболее используемую память в оперативной памяти?
    

Ответы

Ответ 1

Под WinApi просто выгрузите все во временный файл (флаг FILE_ATTRIBUTE_TEMPORARY),
потом не закрывая файл, отображайте в память части которые необходимо читать. Все!

В винде (по крайней мере с 7) есть дисковый кэш, который кэширует часто или недавно
читавшиеся куски файлов в ОЗУ. То есть делает ровно то, что вы хотите сделать. Флаг
FILE_ATTRIBUTE_TEMPORARY говорит файловой системе что вы хотите создать, что характерно,
временный файл и поэтому нужно блоки этого файла по-придержать в кэше. Если памяти
под кэш хватает конечно.

ОЗУ для этого использовать не рекомендую. Управляемого свопа в WinApi не предусмотрено,
это автоматический общесистемный процесс. Иными словами своп начинается когда памяти
всем не хватает, то есть когда вся система уже сидит. И выдиление 10 ГБ может легко
к этому привести.


Ответ 2

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

Т.е. структура должна вот что делать:  


сохранять переданный от неё большой кусок данных от СУБД внутри
себя.
при сохранении данных нарезает её на куски размером скажем по 64КБ и
такими кусками всегда оперирует.
частые куски хранит в ОЗУ, редкие на диске.
может вернуть любой участок из куска данных по запрошенному смещению
заданного размера и записывает этот кусок в заданный буфер (это
функция get что упоминал выше).
может изменять любой участок внутри зарегистрированного куска на
заданный блок байт.


Такая структура может очень экономно использовать память, всмысле что ей не помеха
будет большой объём данных, т.к. она у себя хранит их кусками мелкими а не выделяет
непрерывный большой участок в ОЗУ. Кстати в ней можно хранить только большие данные,
мелкие нужно хранить во второй структуре которая будет выделять просто непрерывный
участок классически, т.к. большая структура имеет куски по 64КБ а это значит что мелкие
куски будут очень неэффективно занимать ОЗУ.


Ответ 3

Поскольку реализации до сих пор нету, собрал такой "скелет". 

class TBigMem{
  private:
  HANDLE hFile;
  HANDLE hMap;
  __int64 hIndex; //можно переназначить тип на тот, который в вашей IDE
  __int64 maxsize;
  void * mWnd;
  DWORD AllocationGranularity; // Размер кратным которого должно быть окно


  bool DoMap(unsigned long * index){
     if (hIndex >=0)
        UnmapViewOfFile(mWnd);
     hIndex = *(__int64*)index;
     void * wnd = MapViewOfFileEx(hMap, FILE_MAP_ALL_ACCESS, index[1],
       index[0],AllocationGranularity,mWnd); /*Окно*/
     if (wnd == 0) wnd=MapViewOfFileEx(hMap,FILE_MAP_ALL_ACCESS,
       index[1], index[0],AllocationGranularity,NULL);/*Новое окно*/
     if (wnd == 0) {
        /*Обработать ошибку - не хватает памяти скорее всего*/};
     if (wnd!=0) mWnd = wnd;
     return wnd != 0;
     };



  public:
   TBigMem (__int64 size) {// Размер можно сделать константой
      char buff[512];
      SYSTEM_INFO si;
      GetSystemInfo(&si);
      AllocationGranularity = si.dwAllocationGranularity;
      GetTempPathA(sizeof(buff),buff);
      GetTempFileNameA(buff,"bigmem",0,buff); // Тут задать префикс для временного файла
      hFile = CreateFileA(buff,GENERIC_READ | GENERIC_WRITE ,0,NULL,CREATE_ALWAYS,
        FILE_ATTRIBUTE_TEMPORARY | FILE_FLAG_DELETE_ON_CLOSE,0);
      hIndex = -1;
      Realloc(size);
     }

   bool Realloc(__int64 size){
      if (!hFile) return 0;
      if (hIndex >=0) UnmapViewOfFile(mWnd);         
      if (hMap) CloseHandle(hMap);
      hMap = 0;
      hIndex = -1;
      hMap = CreateFileMappingA(hFile,0, PAGE_READWRITE,  
       ((unsigned long*)&size)[1], ((unsigned long*)&size)[0] ,0);
      if (hMap !=0) maxsize = size;
      return hMap != 0;
      }

   bool isValid() { return hMap !=0; };


  ~TBigMem(){
     CloseHandle(hMap);
     CloseHandle(hFile);
     };


  char& operator[](__int64 index){
     union {
       __int64 i;
       unsigned long w[2];
        } u;
     if (index >= maxsize)// Авторасширение с выравниванием
         Relloc(index - (index & AllocationGranularity)+AllocationGranularity); 
     if (hMap == 0) return *(char*)NULL; // Не возможно, обработать ошибку
     unsigned long offs;
     int err = 0;
     u.i = index;
     offs = u.w[0] & (AllocationGranularity-1);
     u.w[0] &=      ~(AllocationGranularity-1);         
     //TODO: тут можно дописать сдвиг индекса, что б окно было шире
     if (u.i != hIndex) DoMap(&u.w[0]);
     //err = GetLastError();
     return *((char*)mWnd + offs);
    };

  unsigned int GetAvalible(__int64 index) { // Колличество байт, доступных в окне
    return AllocationGranularity-((unsigned int)(index & (AllocationGranularity-1)));
    }    
  };


Протестировал на небольших обьёмах так:

 char c;
 TBigMem data(1000000);
 data[0]=1;
 data[65536]=2;
 с = data[0]; // переключить на первую страницу
 с = data[65536]; // переключить другую станицу


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

P.S. Ожидаю более удобную реализацию. На сейчас момент это единственный пример реализации.


Для char такое решение подходит, а для более емких типов нужно добавить "двойной"
буфер, потому что при размере более одного байта тип может оказаться на "разрезе двух
страниц". 
Я столкнулся с тем, что не нашёл толкового описания как зарезервировать память для
MapViewOfFileEx. 
Для "расширеного" функционала, возможно нужны шаблоны template, это на будущее.