Dynamic 2D Arrays
Vik Rubenfeld, Programmer

Dynamic 2D Arrays
by Vik Rubenfeld
May 15, 2004

This article chronicles a threat on the MacPascal mailing list for implementing dynamically allocated 2D arrays in Pascal.

Contents

• The Original Post
• The Final Post
• The Solution
• Archived Thread

Type
     PtrToLarge2DArray = ^Large2DArray;
     HandleToLarge2DArray =^PtrToLarge2DArray;
     Large2DArray = array[1..MaxLongInt] of array[1..MaxLongInt] of str[MaxFieldWidth];

Var
     RecordSize, NumberOfRowsNeeded, NumberOfColumnsNeeded : LongInt;

     {...}
     Begin
     {determine array size on the fly at runtime}
     NumberOfRowsNeeded:= 75000;
     NumberOfColumnsNeeded:= 2000;

     RecordSize:= MaxFieldWidth + 1; {+1 for the length byte of a Pascal string}
     HandleToLarge2DArray := NewHandle(RecordSize * NumberOfRowsNeeded * NumberOfColumnsNeeded);

     FailNil(handle(HandleToLarge2DArray));
     MoveHi(handle(HandleToLarge2DArray));
     Hlock(handle(HandleToLarge2DArray));

     {...}
     End;

Now here's the interesting part. To get this to map correctly to the ram allocated by the call to NewHandle, do I access this array like this:

HandleToLarge2DArray^^[aRow, aColumn]:= 'a string';

Or like this:

HandleToLarge2DArray^^[aColumn, aRow]:= 'a string';


Thanks very much in advance to all for any info.

-Vik

• Allocated a pointer to a data storage block 10 megs in size.
• Arranged for new data storage blocks to be automatically allocated as needed.
• Data in this case is all strings. Strings are stored in Pascal string (length byte first) format


Pointer Storage

• Allocated a pointer to a pointer storage block of size RequiredRows * RequiredColumns * SizeOf(ptr)
• When a string is stored to the data storage block, a pointer to that string is stored in the pointer storage block at location (((theRow - 1) * TotalColumnsInSpeedFormat) + (theColumn - 1)) * sizeOf(ptr);

Access

• Strings in the data storage block are retrieved by reference to their pointers in the pointer storage block.


The data storage block is saved to disk in the same format. I found that this data storage format permits very rapid access, even on disk, versus the tab-text format I had been using. On my system it takes about 90 seconds to parse and read in about 3,000,000 fields in tab-text format, vs. about 9 seconds in the new format. I'm sure most apps that do this sort of thing use a similar format.

When the data is in memory, it takes my system around 6 seconds to access 3,000,000 fields in this format using the data structures described above. For my particular application (rapid response to requests coming from a web browser, accessing my system via the net), every second counts, particularly as data comes in weekly, and more data means slower response times.

At Bill's request I'm sending to Pascal Central a file containing the text of this thread, and the code I used to implement the data structures described above.

Thanks to all here for your help on this!

-Vik




{This is the code I used to implement the dynamically allocated 2D arrays.}
{The format of the file I used is:}

{TotalRows stored as a LongInt}
{TotalColumns stored as a LongInt}
{Each string stored as a Pascal string, i.e. length byte first, with no delimiters of any kind between the strings.}

{The code included here is not self-enclosed. It refers to routines that are not provided here, particularly routines that}
{read and write data to and from files. However, most of the code needed for the dynamically allocated 2D arrays is here.}

{The code is provided for information purposes only and has not been strenuously tested at this time. }

{-Vik Rubenfeld}

{cBufferedFile is a file reading and writing object}

cBufferedFile = object(cDataFile)
     {.....}
     TotalRowsInSpeedFormat: LongInt;
     TotalColumnsInSpeedFormat: LongInt;

     HeadBlockOfDataStorage:= DataStorageForSpeedFormatFile;
     CurrentBlockOfDataStorage:= DataStorageForSpeedFormatFile;

     itsPointerToSpeedFormatPointerStorage: Ptr;
     {.....}
     end;

DataStorageForSpeedFormatFile = object(cTCL_Object)
     itsDataStorageForSpeedFormatFile: ptr;
     NextFreeByte: LongInt;
     NextDataStorageForSpeedFormatFile: DataStorageForSpeedFormatFile;

     itsBufferedFile: cBufferedFile;

     Procedure InitializeDataStorageForSpeedFormatFile(theCBufferedFile: cBufferedFile);

     Function AddStringToStorage(S: DecStr): ptr;

     Procedure Free; override;
     end;


Procedure cBufferedFile.CreateSpeedFormatDataStructures(RequestedRows, 
               RequestedColumns: LongInt);

Var
     thePtrToTheSpeedFormat: ptr;
     theDataStorageForSpeedFormatFile: DataStorageForSpeedFormatFile;
     theBufferedFile: cBufferedFile;

     begin
     if itsPointerToSpeedFormatPointerStorage <> nil then
          FreeSpeedFormat;

     TotalRowsInSpeedFormat:= RequestedRows;
     TotalColumnsInSpeedFormat:= RequestedColumns;

     thePtrToTheSpeedFormat:= NewPtrClear(RequestedRows * RequestedColumns * sizeOf(ptr));
     FailNil(thePtrToTheSpeedFormat);

     itsPointerToSpeedFormatPointerStorage:= thePtrToTheSpeedFormat;

     new(theDataStorageForSpeedFormatFile);
     FailNil(theDataStorageForSpeedFormatFile);
     theBufferedFile:= self;
     theDataStorageForSpeedFormatFile.InitializeDataStorageForSpeedFormatFile(theBufferedFile);

     HeadBlockOfDataStorage:= theDataStorageForSpeedFormatFile;
     CurrentBlockOfDataStorage:= theDataStorageForSpeedFormatFile;
     end;

Function cBufferedFile.FreeDataStorageForSpeedFormatFile;

Var
     theDataStorageForSpeedFormatFile: DataStorageForSpeedFormatFile;
     theNextDataStorageForSpeedFormatFile: DataStorageForSpeedFormatFile;

     begin
     theDataStorageForSpeedFormatFile:= HeadBlockOfDataStorage;

     while theDataStorageForSpeedFormatFile <> nil do
          begin
          theNextDataStorageForSpeedFormatFile:= theDataStorageForSpeedFormatFile.NextDataStorageForSpeedFormatFile;

          theDataStorageForSpeedFormatFile.NextDataStorageForSpeedFormatFile:= nil;
          theDataStorageForSpeedFormatFile.Free;

          theDataStorageForSpeedFormatFile:= theNextDataStorageForSpeedFormatFile;
          end;

     HeadBlockOfDataStorage:= nil;
     CurrentBlockOfDataStorage:= nil;
     end; 

Procedure cBufferedFile.FreeSpeedFormat;

Var
     thePtrToTheSpeedFormat: ptr;

     begin
     if itsPointerToSpeedFormatPointerStorage = nil then
          exit(FreeSpeedFormat);

     thePtrToTheSpeedFormat:= itsPointerToSpeedFormatPointerStorage;
     itsPointerToSpeedFormatPointerStorage:= nil;
     ForgetPtr(thePtrToTheSpeedFormat);

     TotalRowsInSpeedFormat:= 0;
     TotalColumnsInSpeedFormat:= 0;

     FreeDataStorageForSpeedFormatFile;
     end;

Function cBufferedFile.StoreFieldToSpeedFormat(theRow, theColumn: LongInt; S: DecStr): ptr;

Var
     thePtrToTheStoredString: Ptr;
     LocationWhereThatPtrWillBeStored: Ptr;

     begin
     {there is no garbage collection in the DataStorageForSpeedFormatFile objects. If you change the contents of a field, the old 
     contents remain in memory until FreeDataStorageForSpeedFormatFile is called.}
     thePtrToTheStoredString:= CurrentBlockOfDataStorage.AddStringToStorage(S);

     LocationWhereThatPtrWillBeStored:= GetLocationInRamOfRequestedPtrToItemInSpeedFormatDataStorage(theRow, theColumn);

     BlockMove(@thePtrToTheStoredString, LocationWhereThatPtrWillBeStored, sizeof(ptr));
     end;

Function cBufferedFile.GetFieldFromSpeedFormat(theRow, theColumn: LongInt): DecStr;

Var
     PtrToThePtr, thePtrToTheString: Ptr;
     S: DecStr;
     theLength: byte;

     begin
     PtrToThePtr:= GetLocationInRamOfRequestedPtrToItemInSpeedFormatDataStorage(theRow, theColumn);

     BlockMove(PtrToThePtr, @thePtrToTheString, sizeOf(ptr));

     if thePtrToTheString = nil then
          S:= ''
     else
          begin
          theLength:= byte(thePtrToTheString^);
          BlockMove(thePtrToTheString, @S[0], theLength + 1);
          end;

     GetFieldFromSpeedFormat:= S;
     end;

Function cBufferedFile.GetLocationInRamOfRequestedPtrToItemInSpeedFormatDataStorage(theRow, theColumn: LongInt): ptr;

Var
     LocationOfThePtr: Ptr;
     theOffset: LongInt;

     begin
     LocationOfThePtr:= itsPointerToSpeedFormatPointerStorage;

     theOffset:= (((theRow - 1) * TotalColumnsInSpeedFormat) + (theColumn - 1)) * sizeOf(ptr);

     LocationOfThePtr := Ptr(LongInt(LocationOfThePtr) + theOffset);

     GetLocationInRamOfRequestedPtrToItemInSpeedFormatDataStorage:= LocationOfThePtr;
     end;

Procedure cBufferedFile.SaveSpeedFormatToDisk;

Var
     LI: LongInt;
     S: DecStr;
     theRow: LongInt;
     theColumn: LongInt;
     theLength: byte;

     begin
     {save length byte of string for faster readin times}
     For theRow:= 1 to TotalRowsInSpeedFormat do
          For theColumn:= 1 to TotalColumnsInSpeedFormat do
               begin
               S:= GetFieldFromSpeedFormat(theRow, theColumn);
               theLength:= byte(S[0]);
               WriteByte(theLength);
               Write(S);
               end;
     end;

Procedure cBufferedFile.ReadInSpeedFormatDataFromDisk;

Var 
     S: DecStr;
     R: Real;
     LI: LongInt;
     theRow: LongInt;
     theColumn: LongInt;
     theByte: byte;
     theLength: LongInt;
     thePtr: Ptr;
     LocationOfThePtr: Ptr;
     TotalRows, TotalColumns: LongInt;

     fi: FailInfo;

     Procedure HandleError (error: integer; message: LongInt);

          begin
          SetFailInfo(kSilentErr, 0);
          UseStatusDoc(DoCleanUp, 'Loading Speed Format Data', '');
          end;

     begin
     {Has data been previously read into memory for this file? This can happen if the file was
     opened and closed, but not freed. This permits SpeedFormat data to remain in memory in
     case it's called for again.}
     if itsPointerToSpeedFormatPointerStorage <> nil then
          exit(ReadInSpeedFormatDataFromDisk); 

     CatchFailures(fi, HandleError);

     UseStatusDoc(DoInit, 'Loading Speed Format Data.', '');

     ReadLn(S);

     if S <> StringIdentifyingFileAsASpeedFormatFile then
          begin
          WhoaDude('File is not a SpeedFormat file.');
          Failure(kSilentErr, 0);
          end;

     ReadReal(R); {version number}

     ReadLongInteger(TotalRows);
     TotalRowsInSpeedFormat := TotalRows;

     ReadLongInteger(TotalColumns);
     TotalColumnsInSpeedFormat := TotalColumns;

     CreateSpeedFormatDataStructures(TotalRows, TotalColumns);

     For theRow:= 1 to TotalRowsInSpeedFormat do
          For theColumn:= 1 to TotalColumnsInSpeedFormat do
               begin
               ReadByte(theByte);
               if theByte > 0 then
                    begin
                    theLength:= theByte;
                    ReadPointerOfSpecifiedLength(thePtr, theLength);

                    {get the data into a string}
                    S[0]:= char(theByte);
                    BlockMove(thePtr, @S[1], theLength);

                    {dispose of the pointer}
                    ForgetPtr(thePtr);

                    {store the string to Data Storage}
                    thePtr:= CurrentBlockOfDataStorage.AddStringToStorage(S);

                    {take the address of the string in Data Storage, and put it in the correct place in the SpeedFormat pointer storage 
                    where it's easy to find}
                    LocationOfThePtr := GetLocationInRamOfRequestedPtrToItemInSpeedFormatDataStorage(theRow, theColumn);
                    BlockMove(@thePtr , LocationOfThePtr, sizeof(ptr));
                    end;
               end;

     UseStatusDoc(DoCleanUp, 'Loading Speed Format Data', '');

     Success;
     end;

Procedure cBufferedFile.WriteContentsOfFieldArrayToSpeedFormatFile(theTargetFile: cBufferedFile);

Var
     S: DecStr;
     I:integer;
     theLength: byte;

     begin
     for I := 1 to TabDelimitedEndingColumn do
          begin
          S := Field^^[I];

          If ItsAllBlanks(S) then
               S:= '';

          theLength:= byte(S[0]);
          theTargetFile.WriteByte(theLength);

          if theLength > 0 then
               theTargetFile.Write(S);
          end;
     end;

Procedure DataStorageForSpeedFormatFile.InitializeDataStorageForSpeedFormatFile(theBufferedFile: cBufferedFile);

Var
     thePtr: Ptr;

     begin
     NextFreeByte:= 1;
     NextDataStorageForSpeedFormatFile:= nil;

     thePtr:= NewPtrClear(SizeOfDataStorageForSpeedFormatFileBlock);
     FailNIL(thePtr);

     itsBufferedFile:= theBufferedFile;

     itsDataStorageForSpeedFormatFile:= thePtr;
     end;

Function DataStorageForSpeedFormatFile.AddStringToStorage(S: DecStr): ptr;

Var
     LengthOfTheString: LongInt;
     AvailableSpace: LongInt;
     theBufferedFile: cBufferedFile;
     thePtr: Ptr;
     theDataStorageForSpeedFormatFile: DataStorageForSpeedFormatFile;

     begin
     theDataStorageForSpeedFormatFile:= self;

     LengthOfTheString:= Length(S) + 1; {+1 for the length byte}

     AvailableSpace:= SizeOfDataStorageForSpeedFormatFileBlock - NextFreeByte + 1;

     if AvailableSpace < LengthOfTheString then
          begin
          New(theDataStorageForSpeedFormatFile);
          FailNIL(theDataStorageForSpeedFormatFile);

          theBufferedFile:= itsBufferedFile;
          theDataStorageForSpeedFormatFile.InitializeDataStorageForSpeedFormatFile(theBufferedFile);
          itsBufferedFile.CurrentBlockOfDataStorage:= theDataStorageForSpeedFormatFile;
          end;

          thePtr:= theDataStorageForSpeedFormatFile.itsDataStorageForSpeedFormatFile;
          thePtr:= Ptr(LongInt(thePtr) + theDataStorageForSpeedFormatFile.NextFreeByte - 1);
          BlockMove(@S[0], thePtr, LengthOfTheString);

          theDataStorageForSpeedFormatFile.NextFreeByte:= theDataStorageForSpeedFormatFile.NextFreeByte + LengthOfTheString;

          AddStringToStorage:= thePtr;
          end;

Function DataStorageForSpeedFormatFile.Free;

Var
     thePtr: Ptr;

     begin
     thePtr:= itsDataStorageForSpeedFormatFile;
     itsDataStorageForSpeedFormatFile:= nil;

     ForgetPtr(thePtr);

     inherited Free;
     end;

Click here for the full Archived Thread...