Skip to content

Instantly share code, notes, and snippets.

@afish
Created November 23, 2016 20:49
Show Gist options
  • Star 1 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save afish/fc17adbbcddb6e32956978bca4c3dce7 to your computer and use it in GitHub Desktop.
Save afish/fc17adbbcddb6e32956978bca4c3dce7 to your computer and use it in GitHub Desktop.
Simple implementation of UnsafeList in C#
// UnsafeList
using System;
using System.Collections;
using System.Collections.Generic;
namespace UnsafeList
{
public class UnsafeList<T> : IEnumerable where T : class
{
private readonly int _elementSize;
private T _target;
private int[] _storage;
private int _currentIndex = -1;
private readonly T[] _elements;
public UnsafeList(int size, int elementSize)
{
_elementSize = elementSize + 1;
_storage = new int[size * _elementSize];
_elements = new T[size];
_target = default(T);
}
public void Add(T item)
{
_currentIndex++;
unsafe
{
TypedReference reference = __makeref(item);
int* itemAddress = (int*) (*(int*) *(int*) &reference - 4);
for (int i = 1; i < _elementSize; ++i)
{
_storage[_currentIndex*_elementSize + i] = *itemAddress;
itemAddress = itemAddress + 1;
}
reference = __makeref(_storage);
_storage[_currentIndex*_elementSize] = *(int*) *(int*) &reference + _currentIndex*_elementSize*4 + 16;
_elements[_currentIndex] = GetInternal(_currentIndex);
}
}
private T GetInternal(int index)
{
unsafe
{
TypedReference reference = __makeref(_target);
*(int*)*(int*)&reference = _storage[index * _elementSize];
T result = __refvalue(reference, T);
return result;
}
}
public T Get(int index)
{
return _elements[index];
}
public IEnumerator<T> GetEnumerator()
{
return new CustomEnumerator<T>(this);
}
IEnumerator IEnumerable.GetEnumerator()
{
return GetEnumerator();
}
private class CustomEnumerator<T> : IEnumerator<T> where T : class
{
private readonly UnsafeList<T> _list;
private int _index;
private T _current;
private int size;
public CustomEnumerator(UnsafeList<T> list)
{
_list = list;
_index = -1;
size = _list._currentIndex;
}
public void Dispose()
{
}
public bool MoveNext()
{
_index++;
if (_index <= size)
{
_current = _list.Get(_index);
return true;
}
return false;
}
public void Reset()
{
_index = -1;
}
public T Current
{
get { return _current; }
}
object IEnumerator.Current
{
get { return _current; }
}
}
}
}
// DEMO
using System;
using System.Collections.Generic;
using System.Diagnostics;
namespace UnsafeList
{
class Poco
{
public int Field1;
public int Field2;
public int Field3;
public int Field4;
public int Field5;
public int Field6;
public int Field7;
public int Field8;
public int Field9;
public int Field10;
public int Field11;
public int Field12;
public int Field13;
public int Field14;
public int Field15;
public int Field16;
}
class Program
{
private static Poco CreatePoco(int i)
{
return new Poco
{
Field1 = i,
Field2 = i - 1,
Field3 = i - 2,
Field4 = i - 3,
Field5 = i - 4,
Field6 = i - 5,
Field7 = i - 6,
Field8 = i - 7,
Field9 = i - 7,
Field10 = i - 6,
Field11 = i - 5,
Field12 = i - 4,
Field13 = i - 3,
Field14 = i - 2,
Field15 = i - 1,
Field16 = i
};
}
static void TestArray(int elementsCount)
{
Console.WriteLine("Array");
var stopwatch = new Stopwatch();
stopwatch.Start();
var array = new Poco[elementsCount];
for (int i = 0; i < elementsCount; ++i)
{
var poco = CreatePoco(i);
array[i] = poco;
}
stopwatch.Stop();
Console.WriteLine($"Insertion time: {stopwatch.ElapsedMilliseconds}");
int sum = 0;
stopwatch.Restart();
for (int i = 0; i < elementsCount; ++i)
{
var poco = array[i];
sum += poco.Field1;
sum += poco.Field2;
sum += poco.Field3;
sum += poco.Field4;
sum += poco.Field5;
sum += poco.Field6;
sum += poco.Field7;
sum += poco.Field8;
sum += poco.Field9;
sum += poco.Field10;
sum += poco.Field11;
sum += poco.Field12;
sum += poco.Field13;
sum += poco.Field14;
sum += poco.Field15;
sum += poco.Field16;
}
stopwatch.Stop();
Console.WriteLine($"Sum: {sum}");
Console.WriteLine($"Calculation time: {stopwatch.ElapsedMilliseconds}");
}
static void TestList(int elementsCount)
{
Console.WriteLine("List");
var stopwatch = new Stopwatch();
stopwatch.Start();
var normalList = new List<Poco>(elementsCount);
for (int i = 0; i < elementsCount; ++i)
{
var poco = CreatePoco(i);
normalList.Add(poco);
}
stopwatch.Stop();
Console.WriteLine($"Insertion time: {stopwatch.ElapsedMilliseconds}");
int sum = 0;
stopwatch.Restart();
for (int i = 0; i < elementsCount; ++i)
{
var poco = normalList[i];
sum += poco.Field1;
sum += poco.Field2;
sum += poco.Field3;
sum += poco.Field4;
sum += poco.Field5;
sum += poco.Field6;
sum += poco.Field7;
sum += poco.Field8;
sum += poco.Field9;
sum += poco.Field10;
sum += poco.Field11;
sum += poco.Field12;
sum += poco.Field13;
sum += poco.Field14;
sum += poco.Field15;
sum += poco.Field16;
}
stopwatch.Stop();
Console.WriteLine($"Sum: {sum}");
Console.WriteLine($"Calculation time: {stopwatch.ElapsedMilliseconds}");
}
static void TestUnsafeList(int elementsCount)
{
Console.WriteLine("UnsafeList");
var stopwatch = new Stopwatch();
stopwatch.Start();
var unsafeList = new UnsafeList<Poco>(elementsCount, 18);
for (int i = 0; i < elementsCount; ++i)
{
var poco = CreatePoco(i);
unsafeList.Add(poco);
}
stopwatch.Stop();
Console.WriteLine($"Insertion time: {stopwatch.ElapsedMilliseconds}");
int sum = 0;
stopwatch.Restart();
for (int i = 0; i < elementsCount; ++i)
{
var poco = unsafeList.Get(i);
sum += poco.Field1;
sum += poco.Field2;
sum += poco.Field3;
sum += poco.Field4;
sum += poco.Field5;
sum += poco.Field6;
sum += poco.Field7;
sum += poco.Field8;
sum += poco.Field9;
sum += poco.Field10;
sum += poco.Field11;
sum += poco.Field12;
sum += poco.Field13;
sum += poco.Field14;
sum += poco.Field15;
sum += poco.Field16;
}
stopwatch.Stop();
Console.WriteLine($"Sum: {sum}");
Console.WriteLine($"Calculation time: {stopwatch.ElapsedMilliseconds}");
}
static void Main()
{
var testsCount = 3;
var elementsCount = 20 * 1000 * 1000;
Console.WriteLine("------------------------");
for (int i = 0; i < testsCount; ++i)
{
TestArray(elementsCount);
}
GC.Collect();
GC.WaitForPendingFinalizers();
Console.WriteLine("------------------------");
for (int i = 0; i < testsCount; ++i)
{
TestList(elementsCount);
}
GC.Collect();
GC.WaitForPendingFinalizers();
Console.WriteLine("------------------------");
for (int i = 0; i < testsCount; ++i)
{
TestUnsafeList(elementsCount);
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment