Tag Archives: Disjoint Subset

ADM – Pt 2 Unconstrained Arrays

Application Data Manager (ADM) is an open source solution for processing large amounts of real-time data. In this segment I describe the ADM process for memory allocation.

Unconstrained Arrays

In the segment on Sequences the length of the sequence had reached maximum capacity and we needed to append a new element. One solution would be to allocate more memory and then copy the old sequence to a subset of the new sequence. In a real time system this can have significant performance consequences and may lead to memory leaks. Another strategy would be to create a linked list. This minimizes memory allocation but can be much less efficient than direct access.
The solution chosen for ADM is an unconstrained array. As defined here, an unconstrained array combines the benefits of a linked list with direct access as it increases capacity in regular increments to meet the demands of real-time data acquisition.

Unconstrained Array Declarations:

private byte[] small;
private byte[][] medium;
private byte[][][] large;

Unconstrained Array Initial State – Case Small

A byte can enumerate up to 256 elements. Initially medium and large are both null. The array small is dimensioned 256 x 1 byte (blue) and assigned the values 0 to 255 (note: sign extension can be overridden by a policy that widens bytes unsigned to int). Next, let us illustrate what happens when we exceed the capacity of small.


First Increment of 256 elements – Case Medium

On adding the 257th element the 256 x 1 byte array small needs to be widened to the 256 x 2 byte array medium[0] (green). Another 256 x 2 byte array medium[1] is allocated to increase the capacity by another 256 elements and initialized with the values 256 to 511. The arrays medium[2] to medium[255] can remain null until more increments of 256 elements are needed. When medium[255] is allocated, the unconstrained array has a maximum capacity of 65536 elements.

Increment 257 of 256 elements – Case Large

Up until this time the array large has been null. On adding element 65537 the 256 arrays of 256 x 2 byte elements of medium (green) must be widened to 256 arrays of 256 x 3 byte elements (yellow) as shown in the following illustration.
The array large[0] allocates 256 arrays large[0][0] to large[0][255] and populates these with the widened data from medium.  The array large[1]  allocates 256 arrays large[1][0] to large[1][255] but only allocates memory to the 256 x 3 byte array large[1][0], initializing it with the 256 values 65536 to 65791.

As required capacity increases,  additional arrays of 256×3 elements are allocated to large[m][n]. When both m and n are 255, the maximum capacity of 16777216 elements has been reached. 

Disjoint Subsets

If additional capacity is required, the problem must be restructured using disjoint subsets so that each disjoint subset has less than 16777216 elements. Disjoint subsets are also recommended for capacities much lower than the 16777216 maximum.

Unconstrained Arrays of Objects.

Until now we have only looked at sequences. Unconstrained arrays can also be used for numeric row data and sets of objects. These will be the topic for future segments in this blog.

Copyright © 2014 Color My Data, All Rights Reserved

previous next