-
-
Save afish/fc17adbbcddb6e32956978bca4c3dce7 to your computer and use it in GitHub Desktop.
Simple implementation of UnsafeList in C#
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
// 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