Many memory management routines allocate 2x the required capacity on overflow and and de-allocate when the array is 1/2 used.

This method is inefficient and wastes up to 100% of the actually memory required, although some on average is is probably much lower than this.

I am thinking it might be best to increase and decrease the capacity based on the rate of length changes.

If the length changes very quickly then the app is using the array a lot and we can expect this to continue. The capacity for reallocation is proportionate to the the rate additions or removals from the array.

De-allocation strategy is inverse to allocation. The faster the length decreases the less we de-allocate. The slower it happen the more we de-allocate.

These strategies essentially automatically tune the capacity depending on what the program is doing. This is more intelligent than a blind 2x/0.5x capacity change.


Ideally, we could have the capacity slowing decrease over time automatically to free up memory when the array is not being used, but the adds a layer of complexity I'm not interested in dealing with.


I have written a simple Fixed Array type of container for you guys to play with:



import core.stdc.stdlib, std.traits, std.exception, core.stdc.string;

mixin template FixedArray(T, int Alignment = 1, bool clear = true)
{	

	private int capacity = 4;
	private int length = 0;
	private T* mem = null;
	public @property auto Length()
	{
	   return length;
	}
	
	public @property auto Capacity()
	{
	   return capacity;
	}

	public this(int capacity)
	{
		allocateBlock(capacity);		
	}

	private void allocateBlock(int capacity)
	{
		this.capacity = capacity;
		size_t size = T.sizeof*capacity;
		enforce(size > 0, "Cannot allocate fixed array of size 0.");
		if (mem is null)
			mem = cast(T*)malloc(size+Alignment);
		else
			mem = cast(T*)realloc(mem, size+Alignment);

		enforce(cast(int)mem > 0, "Could not malloc memory block.");
		
		// Adjust memory pointer to be aligned
		long tmp = (cast(long)mem) & (Alignment - 1);
		long ofs = (Alignment - tmp) & (Alignment - 1);
		mem = cast(T*)((cast(long)mem) + ofs);
		
		// Add extra space to be additional end capacity.
		this.capacity = cast(int)((size + Alignment - ofs)/T.sizeof);

		// Init all allocated memory
		if (clear)
			Clear();
	}

	public ~this()
	{
		Free();
	}

	public void Free()
	{
		if (mem !is null)
		{
			capacity = 0;
			length = 0;
			free(mem);			
		}
	}

	public ref T opIndex(int i)
	{
		enforce(i < length, "Array access outside useful values.");
		return mem[i];
	}

        public @property int opDollar(size_t dim : 0)()
	{
		return length;
	}

	

	public int opApply(int delegate(ref T) dg)
    {
        int result = 0;

        for (int i = 0; i < length; i++)
        {
            result = dg(mem[i]);
            if (result)
                break;
        }
        return result;
    }

	public int opApplyReverse(int delegate(ref T) dg)
    {
        int result = 0;

        for (int i = 0; i < length; i++)
        {
            result = dg(mem[length - i - 1]);
            if (result)
                break;
        }
        return result;
    }


	public void opOpAssign(string op)(T d)
	{
		if (op == "~")
		{			
			static if (__traits(compiles, Expand()))
			{
				if (length >= capacity)
					Expand();
			}
			else
				enforce(length < capacity, "FixedArray Full, Cannot Add More!");
			mem[length] = d;
			length++;		
			
		}
	}

	public void Clear()
	{
		length = 0;
		static if (__traits(compiles, Contract()))
		{
			Contract();
		}
	
	}
	
	// Removes value at index
	public void RemoveAt(int index)
	{
		if (index < length && index >= 0)
		{
			static import core.stdc.string;
			core.stdc.string.memmove(mem + index, mem + index + 1, length - index);
			length--;
		}		

		static if (__traits(compiles, Contract()))
		{
			Contract();
		}
	}

	// Removes first occurrence of val.
	public bool Remove(T val)
	{
		bool found = false;
		for(int i = 0; i < length; i++)
		{
			if (mem[i] == val)
			{
				RemoveAt(i);
				found = true;
				break;
			}
		}

		static if (__traits(compiles, Contract()))
		{
			if (found)
				Contract();
		}

		return found;
	}
}



One can create a variable array by mixing in the template:

public struct VarArray(T)
{
   mixin FixedArray!T;

   private void Expand(int capacity = 4)
   {
	
		if (length >= capacity)
		{
			allocateBlock(2*capacity);
		}
   }


   private void Contract()
   {
		if (length > 0 && 2*length <= capacity)
		{
			allocateBlock(capacity/2 + 1);
		}
   }
}



The idea here is to create a more intelligent expand and contract. Something that is efficient yet responds to the programs actual behavior rather than assuming worse case.

Since most software tends to behave in certain patterns, such as appending in large numbers then removing in large numbers, this behavior be captured and used to create more efficient memory and cycle usage.

The problem I see is trying to make it efficient. We could, for example, get the time every x expands or contracts and use this time to estimate the number of rate which can then be used to set the capacity. We reduce the overhead of the timing call by a factor of x. We have to keep track of the number of expands and contracts though.

Can we use more complex prediction techniques? Keep a history of usage? Real time tuning of allocation strategies depending on program state and history?

I leave it up to someone more interested than me to figure this stuff out ;)