[Intermediate] Competing against Microsofts ArrayList

08/21/2008 21:07 InfamousNoone#1
Performance status:

(Attempting to add 1,000,000 Elements)
Flexible: 156ms
List: 234ms
Improvement Speed: 40-50%

(Attempting to remove 1,000 Elements)
Flexible: 16ms
List: 7907ms
Improvement Speed: 99.998%

(Attempting to clear 1,000,000 Elements)
Flexible: 0ms (Less than 1ms)
List: 16ms


Ups / Downs
Collection speed improved (up)
Remove speed improved (up)
Removing re-arranged the array (down)
Supports multi-threaded operations (up)
Potentially 'wasted' memory (down)

Coded in Managed C++ by Infamous

Code:
	public ref class FlexibleArray
	{
		private:
			array<Object^>^ Elements;
			int Count;
			bool Synchronized;
		public:
			FlexibleArray(int Capacity)
			FlexibleArray()
			void Add(Object^ Value)
			void Remove(Object^ Value)
                        void Clear()
			int IndexOf(Object^ Value)
			bool Contains(Object^ Value)
			array<Object^>^ GetElements(int& Length)
	};
Code:
// Constructors
FlexibleArray(int Capacity)
{
        // Allocate elements using their estimated capacity
	Elements = gcnew array<Object^>(Capacity);
	Count = 0;
	Synchronized = true;
}
FlexibleArray()
{
        // Allocate elements using a default size of 36
	Elements = gcnew array<Object^>(36);
	Count = 0;
	Synchronized = true;
}
Code:
void Add(Object^ Value)
{
	while (!Synchronized)
		Sleep(1);
	Synchronized = false;
        // Resize the array if needed
	if (Count == Elements->Length)
	{
		array<Object^>^ nObj = gcnew array<Object^>(GetPrime(Elements->Length * 2));
                // Get prime returns the next prime number after the param
		Array::Copy(Elements, nObj, Count);
		Elements = nObj;
	}
	Elements[Count] = Value;
	Count++;
	Synchronized = true;
}
Code:
void Remove(Object^ Value)
{
	while (!Synchronized)
		Sleep(1);
	Synchronized = false;
	int Slot = 0;
	bool Found = false;
	int hashCode = Value->GetHashCode();
        // Find the elements index
	for each(Object^ tmp in Elements)
	{
		if (tmp->GetHashCode() == hashCode)
		{
			Found = true;
			break;
		}
		Slot++;
	}
	if (Found)
	{
		Count--;
		Elements[Slot] = Elements[Count];
                // Move the last element to the element's place
                // that we no longer need
		Elements[Count] = nullptr;
                // nullify the last element because its now in the index of the
                // element that we're removing
	}
	Synchronized = true;
}
Code:
// Clear the collection
void Clear()
{
	while (!Synchronized)
		Sleep(1);
	Synchronized = false;
	for (int i = 0; i < Count; i++)
	{
		Elements[i] = nullptr;
	}
	Count = 0;
	Synchronized = true;
}
Code:
// Pretty much a copy/paste from "Remove"
int IndexOf(Object^ Value)
{
	while (!Synchronized)
		Sleep(1);
	Synchronized = false;
	int Slot = 0;
	int hashCode = Value->GetHashCode();
	for each(Object^ tmp in Elements)
	{
		if (tmp->GetHashCode() == hashCode)
		{
			Synchronized = true;	
			return Slot;
		}
		Slot++;
	}
	Synchronized = true;
	return -1;
}
bool Contains(Object^ Value)
{
	return (IndexOf(Value) > -1);
}
Code:
// Lastly, beable to retrieve our block of data
array<Object^>^ GetElements(int& Length)
{
	Length = Count;
	return Elements;
}
08/28/2008 03:23 flowerpot!#2
What does the ^ modifier do? I don't know anything about C# but it looks to be used just like a pointer to me...

Anyways, some comments:

The clear function could be O(1) since you don't really need to set the items to null, do you?

Also I'm surprised at how slow the ArrayList remove is... your implementation is O(N) in the size of the list.. from a complexity analysis that's pretty much as slow as it gets. I assume the Arraylist one is O(N) as well (average 2n while yours is n/2, but in complexity analysis constants don't matter). Also, it seems that you're trying to use a hash of sorts to do the comparison? But then it requires the object to implement a GetHashCode() function? Why not just overload the equality operator?

Oh and is it really synchronized? In practice you probably won't have any problems but in theory assignment isn't atomic. To truly synchronize you should ask the OS for a semaphore of some kind.
08/28/2008 03:26 tao4229#3
Quote:
Originally Posted by flowerpot! View Post
What does the ^ modifier do? I don't know anything about C# but it looks to be used just like a pointer to me...

Anyways, some comments:

The clear function could be O(1) since you don't really need to set the items to null, do you?

Also I'm surprised at how slow the ArrayList remove is... your implementation is O(N) in the size of the list.. from a complexity analysis that's pretty much as slow as it gets. I assume the Arraylist one is O(N) as well (average 2n while yours is n/2, but in complexity analysis constants don't matter). Also, it seems that you're trying to use a hash of sorts to do the comparison? But then it requires the object to implement a GetHashCode() function? Why not just overload the equality operator?

Oh and is it really synchronized? In practice you probably won't have any problems but in theory assignment isn't atomic. To truly synchronize you should ask the OS for a semaphore of some kind.
Just one thing.. this is Managed C++ not C#, both still .NET...
08/28/2008 17:45 InfamousNoone#4
Quote:
Originally Posted by flowerpot! View Post
What does the ^ modifier do? I don't know anything about C# but it looks to be used just like a pointer to me...

It's used as a pointer in managed C++ to represent a 'pointer' to a managed object.

Anyways, some comments:

The clear function could be O(1) since you don't really need to set the items to null, do you?

Also I'm surprised at how slow the ArrayList remove is... your implementation is O(N) in the size of the list.. from a complexity analysis that's pretty much as slow as it gets. I assume the Arraylist one is O(N) as well (average 2n while yours is n/2, but in complexity analysis constants don't matter). Also, it seems that you're trying to use a hash of sorts to do the comparison? But then it requires the object to implement a GetHashCode() function? Why not just overload the equality operator?

System::Object (the root of everything in the .NET Framework) implements a default GetHashCode() function tat can be overridden by default, so and object/class/struct will be fine

Oh and is it really synchronized? In practice you probably won't have any problems but in theory assignment isn't atomic. To truly synchronize you should ask the OS for a semaphore of some kind.
Fanks for your input, I'm going to compete against their Random soon probably (amazingly their Random is faster than 'rand() and srand()').