UInt32ArrayAllocator.kl

Types

UInt32ArrayAllocator (struct)

The UInt32ArrayAllocator is used to efficiently allocate of many UInt32 arrays within the same memory buffer. This allocator is used internally by various performance oriented objects, like the Octree or the PolygonMesh.

The UInt32ArrayAllocator was written for optimal performance and not simplicity. One example is that it is not storing the stored array sizes, as the owner can use a more compact encoding for the size. A simple way is to use the 1st array data to store the array size.

Using a single buffer has multiple performance benefits, such as avoiding multiple heap allocation calls (slow), avoiding memory fragmentation (reduces global memory usage) and making the data access CPU cache friendly. This allocator is not threadsafe, but supporting a single thread avoids locking checks overhead.

For performance reason, this allocator will only grow, unless UInt32ArrayAllocator.clear or UInt32ArrayAllocator.recompact is called. A proper usage of this allocator should call UInt32ArrayAllocator.recompact when a large enough portion of the memory is unused (eg: 25% or 50%).

Although the UInt32ArrayAllocator is able to reused free storage by using simplified heap-like structure, the user that cares about memory usage should monitor the portion of unused data (internal fragmentation) and recompact it when this portion is large enough (eg: 50%). This can be done through a call to UInt32ArrayAllocator.recompact, however the caller needs to remap all its indices accordingly.

For optimal performance, the array indices (keys) are not safeguarded. The user should do the safeguarding if required.

注釈

This allocator is not threadsafe, unless all threads are having a read-only access.

注釈

Technical detail: UInt32ArrayAllocator.data[0] is a reserved entry, so 0 can always be used as a ‘null’ index for convenience

Members

UInt32[]

data

The UInt32 buffer containing all data. Users need to use this data member directly to read or write their UInt32 data.

/*
** Example: UInt32ArrayAllocator
*/

require Containers;
  
operator entry() {

      UInt32ArrayAllocator allocator;
      
      //Allocate array1 with size 2
      UInt32 array1Key = allocator.allocate(2, 0);
      allocator.data[array1Key] = 10;
      allocator.data[array1Key+1] = 11;
      
      //Allocate array2 with size 1 + 1 reserved entry for future growth
      UInt32 array2Key = allocator.allocate(1, 1);
      allocator.data[array2Key] = 20;
      
      //Reallocate array1 to size 3, and update its key with the new one
      array1Key = allocator.reallocate(array1Key, 2, 3, 0);
      allocator.data[array1Key+2] = 12;
      
      //Reallocate array2 to size 2, but we don't expect the key to change since there was 1 reserved entry
      if( allocator.reallocate(array2Key, 1, 2, 0) != array2Key )
        report("UNEXPECTED");
      allocator.data[array2Key+1] = 21;
      
      //Recompact the array
      report( "Unused data after reallocates: " + allocator.unusedSize() );
      UInt32 oldIndexToNewIndex[];
      allocator.recompact( oldIndexToNewIndex );
      //Remap our array keys
      array1Key = oldIndexToNewIndex[array1Key];
      array2Key = oldIndexToNewIndex[array2Key];
      report( "Unused data after recompact: " + allocator.unusedSize() );
      
      report( "Array1 content: " 
              + allocator.data[array1Key] 
              + " " + allocator.data[array1Key+1] 
              + " " + allocator.data[array1Key+2] );
      
      report( "Array2 content: " 
              + allocator.data[array2Key] 
              + " " + allocator.data[array2Key+1] );
  
}

/*
** Output:

Unused data after reallocates: 2
Unused data after recompact: 0
Array1 content: 10 11 12
Array2 content: 20 21

*/

Methods

	UInt32ArrayAllocator ( in UInt32ArrayAllocator other )
	UInt32ArrayAllocator ()
UInt32	allocate ! ( in UInt32 allocateCount, in UInt32 reserveCount )
	append ! ( in UInt32ArrayAllocator other, io Size dataOffset )
	clear ! ()
UInt32ArrayAllocator	clone ? ()
	copy ! ( in UInt32ArrayAllocator src )
	free ! ( in UInt32 head, in UInt32 count )
Boolean	isUsed ? ( in UInt32 i )
Size	memUsage ? ()
UInt32	reallocate ! ( in UInt32 head, in UInt32 prevCount, in UInt32 newCount, in UInt32 reserveCountIfShrinkOrMove )
	recompact ! ( io UInt32 oldIndexToNewIndex[] )
UInt32	size ? ()
UInt32	unusedSize ? ()