If you are looking for a way of creating and accessing very large arrays, arrays that can handle content in the order of Terabytes, then probably you might find the File Mapping techniques useful for that purpose.
File mapping is the association of a file's contents with a portion of the virtual address space of a process. It allows the process to work efficiently with a large data files without having to map the whole file into memory. Processes read from and write to the file view using pointers, just as they would with dynamically allocated memory. This improves efficiency because the file resides on disk, but the file view resides in memory, the page-in and page-out happening seamlessly behind the scenes.
In a typical Win32 environment, applications have 4 gigabyte (GB) of virtual address space available. The virtual address space is divided so that 2 GB is available to the application and the other 2 GB is available only to the system. The size of a file mapping object that is backed by a named file is limited by disk space. The size of a file view is limited to the largest available contiguous block of unreserved virtual memory. This is at most 2 GB minus the virtual memory already reserved by the process.
To create a huge array, create multiple temporary files, each of _MaxFileSize, _MaxFileSize being any convenient maximum file size limit such as 2GB, and access their content by mapping and unmapping portions of them to the main memory as required. Creating the temporary files and mapping/unmapping them can be taken care by the CreateFile, CreateFileMapping, MapViewOfFile, and UnmapViewOfFile API. A simple implementation of this will look like below:
#define _TWOGB (0x80000000)
#define _64KB (0x00010000)
#define _64MB (0x04000000)
class HugeArray
{
public:
enum : unsigned long
{ _ElemSize = sizeof(BYTE),
_ViewSize = _64KB,
_MaxFileSize = _TWOGB,
_MaxNoOfCachedViews = 16,
_MaxNoOfElemsPerFile= (_MaxFileSize/_ElemSize),
_MaxNoOfViewsPerFile= (_MaxFileSize/_ViewSize) //=0x00008000
};
protected:
HANDLE* hFileMappings; // The File mappings
ATL::CAtlFile* Files; // The Files that were mapped
unsigned int nFileCount; // Number of Files
BIGNUMBER _RequestedLen; // No.of Elements requested
BIGNUMBER _AllocatedLen; // No.of Elements actually allocated
ATL::CAtlMap<unsigned int, LPVOID> pCachedViews; //[FileIndex, FileView] map for few cached views
std::vector <CBitVector&> bvFileViewCleared; // Keeps track of views that need be cleared upon mapping
public:
HugeArray() // Directory where to create the memory mapped files
: _RequestedLen(0), _AllocatedLen(0), hFileMappings(0), Files(0), nFileCount(0)
{
}
// _nCount: Number of Elements to allocate space for
// lpszDirPath: Directory where to create the memory mapped files
// nInitVal: Value that should be used to initialize the allocated space
HugeArray(const BIGNUMBER& _nCount, LPCTSTR lpszDirPath = _T("."), int nInitVal=0)
: _RequestedLen(0), _AllocatedLen(0), hFileMappings(0), Files(0), nFileCount(0)
{
Allocate(_nCount, lpszDirPath, nInitVal);
}
~HugeArray()
{
DeAllocate();
}
// Allocates space for _nCount number of elements (each of _ElemSize)
//returns the error code in case of failures
DWORD Allocate(const BIGNUMBER& _nCount, LPCTSTR lpszDirPath = _T("."), int nInitVal=0)
{
// Make sure things are clean
DeAllocate();
// Prepare the file name prefixes
ATL::CString strDir(lpszDirPath), strPrefix;
TCHAR TempFileName[MAX_PATH+32];
// Make sure the directory path is terminate with "\"
if(strDir.Right(1) != _T("\\")) strDir += _T("\\");
// Compute the required number of files
unsigned long lNumFiles = (_nCount/(unsigned long)_MaxNoOfElemsPerFile).GetNumberIntoLong() + 1;
// Allocate space for the handles
if(NULL == (Files = new ATL::CAtlFile[lNumFiles]) ||
NULL == (hFileMappings = new HANDLE[lNumFiles]))
return E_OUTOFMEMORY;
for(unsigned long l=0; l < lNumFiles; ++l)
{
// Get a unique name for the file
strPrefix.Format(_T("%dHA"), l);
if(!GetTempFileName(strDir, strPrefix, 0, TempFileName))
return ErrorMessage();
// Create the file
if(FAILED(Files[l].Create(TempFileName, GENERIC_READ|GENERIC_WRITE|STANDARD_RIGHTS_ALL,
FILE_SHARE_READ, OPEN_ALWAYS,
FILE_ATTRIBUTE_TEMPORARY|
FILE_ATTRIBUTE_NOT_CONTENT_INDEXED|
FILE_FLAG_DELETE_ON_CLOSE|FILE_FLAG_SEQUENTIAL_SCAN)))
return ErrorMessage();
// Set the file size to the maximum
if(FAILED(Files[l].SetSize((0x00000000ffffffff & _MaxFileSize))))
return ErrorMessage();
// Create the File Mapping
if(NULL == (hFileMappings[l] = ::CreateFileMapping(Files[l], 0, PAGE_READWRITE, 0, 0, 0)))
return ErrorMessage();
// Create the Clearance vector
bvFileViewCleared.push_back(CBitVector());
}
_RequestedLen = _AllocatedLen = _nCount; nFileCount = lNumFiles;
return S_OK;
}
void DeAllocate()
{
// Unmap the cached views
POSITION pos = pCachedViews.GetStartPosition();
while(pos != NULL)
{
LPVOID pViewBase = pCachedViews.GetNext(pos)->m_value;
if(pViewBase != NULL)
::UnmapViewOfFile(pViewBase);
}
pCachedViews.RemoveAll();
// Close the File Mapping Handles
for(unsigned int i = 0; i < nFileCount; ++i)
{
if(hFileMappings[i] != NULL)
::CloseHandle(hFileMappings[i]);
}
// Free the File Mapping Handles memory
if(hFileMappings != NULL)
delete[] hFileMappings;
// Free the Files Memory (which automatically closes the Files too)
if(Files != NULL)
delete[] Files;
// Clear the bitvector
bvFileViewCleared.clear();
// Reset Values to NULL
hFileMappings = NULL;
Files = NULL;
nFileCount = 0;
_AllocatedLen = 0;
_RequestedLen = 0;
}
inline BYTE* _GetAt(unsigned long lFileIndex, unsigned long nViewIndex, unsigned long nViewOffset)
{
_ASSERTE(lFileIndex < nFileCount);
unsigned long nFileViewIndex = ((lFileIndex & 0x0000ffff) << 16) | (nViewIndex & 0x0000ffff);
LPVOID pViewBase = NULL;
if(pCachedViews.Lookup(nFileViewIndex, pViewBase) == false) // Cache Miss
{
if(pCachedViews.GetCount() >= _MaxNoOfCachedViews) // if Cache is full, make room to load the new map
{
POSITION pos = pCachedViews.GetStartPosition();
pViewBase = pCachedViews.GetAt(pos)->m_value;
if(pViewBase != NULL) ::UnmapViewOfFile(pViewBase);
pCachedViews.RemoveAtPos(pos);
}
// Map the View
if(NULL == (pViewBase = ::MapViewOfFile(hFileMappings[lFileIndex],
FILE_MAP_WRITE, 0,
nViewIndex*_ViewSize, _ViewSize)))
{
ATL::CString strFilePath;
strFilePath.Format(_T("File Index: %d"), lFileIndex);
::MessageBox(NULL, _T("Unable to map view for: ") + strFilePath, _T("Error"), MB_OK|MB_ICONERROR);
return (BYTE*)pViewBase;
}
// Clear the contents of the view if this is the first time it is mapped
if(bvFileViewCleared[lFileIndex].IsBitSet(nViewIndex)==false)
{
::memset(pViewBase, 0, _ViewSize);
bvFileViewCleared[lFileIndex] += nViewIndex; // set the cleared flag
}
// Cache the mapped view
pCachedViews[nFileViewIndex] = pViewBase;
}
return ((BYTE*)pViewBase + nViewOffset);
}
inline BYTE& operator[](const BIGNUMBER& nIndex)
{
unsigned long lFileIndex = (nIndex / (unsigned long)_MaxNoOfElemsPerFile).GetNumberIntoLong();
unsigned long lFileOffset = (nIndex % (unsigned long)_MaxNoOfElemsPerFile).GetNumberIntoLong(); // Compute the offset in file
unsigned long nViewIndex = (lFileOffset / (unsigned long)_ViewSize); // Compute the view that should be containing the offset
unsigned long nViewOffset = (lFileOffset % (unsigned long)_ViewSize); // Compute the offset in the view
return *_GetAt(lFileIndex, nViewIndex, nViewOffset);
}
inline BYTE& operator[](const unsigned long ulIndex)
{
unsigned long lFileIndex = (ulIndex / (unsigned long)_MaxNoOfElemsPerFile);
unsigned long lFileOffset = (ulIndex % (unsigned long)_MaxNoOfElemsPerFile); // Compute the offset in file
unsigned long nViewIndex = (lFileOffset / (unsigned long)_ViewSize); // Compute the view that should be containing the offset
unsigned long nViewOffset = (lFileOffset % (unsigned long)_ViewSize); // Compute the offset in the view
return *_GetAt(lFileIndex, nViewIndex, nViewOffset);
}
// Attemps to allocate space for _nCount number of elements.
// If the currently allocate space is more than what is required, this would do nothing.
// Else Deallocates the existing space and allocates new space.
// In any case clears the contents.
bool ReDim(const BIGNUMBER& _nCount, LPCTSTR lpszDirPath = _T("."), int nInitVal=0)
{
if(_AllocatedLen < _nCount)
{
return (S_OK == Allocate(_nCount, lpszDirPath, nInitVal));
}
else
{
_RequestedLen = _nCount;
ClearContents();
}
return false;
}
void ClearContents()
{
// Unmap the cached views
POSITION pos = pCachedViews.GetStartPosition();
while(pos != NULL)
{
LPVOID pViewBase = pCachedViews.GetNext(pos)->m_value;
if(pViewBase != NULL)
::UnmapViewOfFile(pViewBase);
}
pCachedViews.RemoveAll();
// Clear the Clearance vector and Create it again
bvFileViewCleared.clear();
for(unsigned int i = 0; i < nFileCount; ++i)
bvFileViewCleared.push_back(CBitVector());
}
const BIGNUMBER& Length() const { return _RequestedLen; }
};
The HugeArray class shown above facilitates large Byte arrays to be allocated and accessed by using the file mapping. It uses multiple files of _MaxFileSize to allocate the space and maps views on the files. Views are mapped and unmapped as required, with a limited number of views cached at a time. _MaxNoOfCachedViews governs this limit.
CachedViews are picked in FIFO fashion to unmap so as to make space for new views. (FIFO could be replaced with LRU or any other efficent techqniue, but that requires keeping track of the view usage and hence might incur extra processing - but then the best method has to be decided based on the target scenario.)
The _ViewSize governs the size of the view that is mapped. (_MaxFileSize/_ViewSize) gives the max no. of views per file. As per our other metrics above, since the MaxNoOfViewsPerFile require only 16bits, we can use the upper 16 bits (of a 32-bit integer) to keep track of which file this view belongs to. Thus, we are restricting the maximum number of files to be 2^16 (=65536). With 2GB per file, this restricts us to have at most 65536 * 2GB address space. Thus our HugeArray class cannot work for arrays that require more than 131072GB space.
If we require more space to be mapped, then we need to maintain the FileIndex and View offset seperately (instead of merging them both into one 32-bit integer), thus increasing the number of bits for FileIndex making it possible to have more files mapped.
A typical usage of this call will look like:
#include "HugeArray.h"
int _tmain(int argc, _TCHAR* argv[])
{
BIGNUMBER bSize("4294967296"); // 4GB
HugeArray ha(bSize, _T(".")); // Lets allocate an array of 4GB
ha[0] = 0;
ha[1] = 1;
ha[2] = 2;
ha[bSize-1] = (BYTE)((bSize-1).GetNumberIntoLong() % 256);
ha[bSize-2] = (BYTE)((bSize-2).GetNumberIntoLong() % 256);
for(BIGNUMBER i=bSize-3; i >= 0; --i)
{
ha[i] = (BYTE)(i.GetNumberIntoLong())%256;
if(ha[i+2] != ((i+2).GetNumberIntoLong()%256))
printf("\nError at %s\n", i.GetNumberIntoString(sz));
}
}
A sample project demonstrating this can be downloaded from the attachments.
Of course, this class can be templatized to allow the elements to be complex records than just Bytes. Only that care should be taken to ensure the records fall within the file boundary and do not spawn across.
A point worth noting is, this mechanism relies on the assumption that we never require to have all the content in the memory at once and that the element access follow the temporal and special proximity when possible.
Download Sample Application: HugeArrays.zip
By
P.Gopalakrishna