• Hiemlick Hiemlicker (211/211) Jun 28 2016 Many memory management routines allocate 2x the required capacity

Hiemlick Hiemlicker <HH reign.com> writes:

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 ;)