c# - Memory efficient data structure for high performance -
i have need circular buffer (or other data structure), on can "toarray" or similar call current state of buffer , use whilst buffer carries on possibly overwriting values held.
the reason use case returned data passed worker thread process , idea ensure little data overwritten possible in between calls. choice of circular data structure ostensibly reduce memory usage of buffer fixed value.
i built data structure below, until yesterday sufficient needs. relevant calls takesnapshot, takeall , takeweakarraysnapshot variations on same theme.
the call made quite when 1000 samples of reference types available.
all calls result in out of memory exception @ point. exception takeweakarraysnapshot reverts null midway through using array (something guess fact gc handle weak?)
is there more suitable memory efficient data structure use or doing wrong? changing gc handle type normal help. possible create output type wraps references (like attempted weakreference) reclaimed garbage collector?
thanks reading.
using system; using system.collections; using system.collections.generic; using system.diagnostics.contracts; using system.threading; using system.runtime.interopservices; public class weakarray<t> { private gchandle[] farray; public weakarray(int length) { farray = new gchandle[length]; (int = 0; < length; i++) farray[i] = gchandle.alloc(null, gchandletype.weak); } ~weakarray() { if (farray == null) return; int count = farray.length; (int = 0; < count; i++) { gchandle gchandle = farray[i]; if (!gchandle.isallocated) break; gchandle.free(); } } public int length { { return farray.length; } } public t this[int index] { { return (t) farray[index].target; } set { farray[index].target = value; } } } public class outputdata<tdatatype>:ienumerable<tdatatype>,idisposable { private tdatatype[] buffer { get; set; } private readonly object _lock = new object(); public outputdata(ref tdatatype[] buffer,long length) { buffer = buffer; length = length; } public long length { get; private set; } /// <summary> /// gets <see cref="`0"/> @ specified index. throws indexoutofrange invalid index /// or returns default value of generic type on empty queue /// </summary> /// <value> /// <see cref="`0"/>. /// </value> /// <param name="i">the item @ index.</param> /// <returns></returns> public tdatatype this[int i] { { lock (_lock) { return length > 0 ? buffer[i] : default(tdatatype); } } } public ienumerator<tdatatype> getenumerator() { (int = 0; < length; i++) { yield return buffer[i]; } } ienumerator ienumerable.getenumerator() { return getenumerator(); } public void dispose() { array.clear(buffer,0,buffer.length); } public void setlength(int count) { length = count; } } /// <summary> /// implements circularbuffer behaves queue /// </summary> /// <typeparam name="t"></typeparam> public class fixedcapacityqueue<t> { private t[] _buffer; private t[] _output; private outputdata<t> _outputdata; /// <summary> /// gets dropped count. number of samples have been dropped /// maintain fixed size of datastructure. /// </summary> /// <value> /// dropped count. /// </value> public int droppedcount { get; protected set; } /// <summary> /// default number of dropped items required generate report /// </summary> protected const int droppedframesbetweenreports = 1000; /// <summary> /// _start. index of first element in buffer. /// </summary> private int _start; /// <summary> /// _end. index after last element in buffer. /// </summary> private int _end; /// <summary> /// _size. buffer size. /// </summary> private int _numberofitemsinbuffer; private readonly object _lock = new object(); /// <summary> /// gets or sets name of buffer. /// </summary> /// <value> /// name. /// </value> public string name { get; protected set; } private readonly t _default = default(t); /// <summary> /// initializes new instance of <see cref="fixedcapacityqueue{t}" /> class. /// </summary> /// <param name="name">the name of queue.</param> /// <param name="buffersize">size of buffer.</param> public fixedcapacityqueue(string name, int buffersize) { contract.requires(buffersize > 0); contract.requires(!string.isnullorempty(name)); _buffer = new t[buffersize]; _output = new t[buffersize]; _outputdata = new outputdata<t>(ref _output, 0); _start = 0; _end = _numberofitemsinbuffer == buffersize ? 0 : _numberofitemsinbuffer; name = string.format("fixedcapacityqueue {0}", name); } /// <summary> /// initializes new instance of <see cref="fixedcapacityqueue{t}" /> class. /// </summary> /// <param name="name">the nameof buffer.</param> /// <param name="buffersize">size of buffer.</param> /// <param name="data">the data added queue.</param> /// <exception cref="system.argumentexception"></exception> public fixedcapacityqueue(string name, int buffersize, icollection<t> data) : this(name, buffersize) { contract.requires(data != null); contract.requires(buffersize > 0); contract.requires(data.count < buffersize); foreach (var dataitem in data) { enqueue(dataitem); } } /// <summary> /// gets value indicating whether queue [is empty]. /// </summary> /// <value> /// <c>true</c> if [is empty]; otherwise, <c>false</c>. /// </value> public bool isempty { { lock (_lock) { return _numberofitemsinbuffer == 0; } } } /// <summary> /// gets value indicating whether queue [is full]. /// </summary> /// <value> /// <c>true</c> if [is full]; otherwise, <c>false</c>. /// </value> public bool isfull { { lock (_lock) { return count == size; } } } /// <summary> /// gets number of items present in queue. /// </summary> /// <value> /// count. /// </value> public int count { { lock (_lock) { return _numberofitemsinbuffer; } } } /// <summary> /// gets declared size of queue. /// </summary> /// <value> /// size. /// </value> public int size { { lock (_lock) { return _buffer.length; } } } /// <summary> /// dequeues item queue. expected behaviour if dequeue operation /// requested whilst queue empty, default type of generic queue returned. /// </summary> /// <returns></returns> public t dequeue() { lock (_lock) { if (isempty) return _default; var item = _buffer[_start]; _buffer[_start] = _default; increment(ref _start); --_numberofitemsinbuffer; return item; } } /// <summary> /// enqueues specified item queue. /// </summary> /// <param name="toadd">to add.</param> public void enqueue(t toadd) { lock (_lock) { if (isfull) { _buffer[_end] = toadd; increment(ref _end); _start = _end; droppedcount++; //report drops if (droppedcount >= droppedframesbetweenreports) { //eventanderrorpump.instance.writeonce(1000, reportlevelenum.warning, // string.format("{0} fixedqueue dropped items: {1} ", name, droppedcount)); droppedcount = 0; } } else { _buffer[_end] = toadd; increment(ref _end); ++_numberofitemsinbuffer; } } } /// <summary> /// increments provided index variable one, wrapping /// around if necessary. /// </summary> /// <param name="index"></param> private void increment(ref int index) { if (++index == size) { index = 0; } } /// <summary> /// decrements provided index variable one, wrapping /// around if necessary. /// </summary> /// <param name="index"></param> private void decrement(ref int index) { if (index == 0) { index = size; } index--; } public void enqueue(ienumerable<t> toadd) { lock (_lock) { foreach (var dataitem in toadd) { enqueue(dataitem); } } } public ienumerator<t> getenumerator() { var segments = new arraysegment<t>[2] {arrayone(), arraytwo()}; foreach (arraysegment<t> segment in segments) { (int = 0; < segment.count; i++) { yield return segment.array[segment.offset + i]; } } } /// <summary> /// gets @ specified index. throws indexoutofrange invalid index /// or returns default value of generic type on empty queue. head/earliest item index can /// null in event of dequeue. if front of queue required,please use front function instead /// </summary> /// <param name="i">the item @ index.</param> /// <returns></returns> /// <exception cref="system.indexoutofrangeexception"></exception> public t this[int index] { { lock (_lock) { if (isempty) { return _default; } if (index >= _numberofitemsinbuffer) { throw new indexoutofrangeexception(string.format("cannot access index {0}. buffer size {1}", index, _numberofitemsinbuffer)); } int actualindex = internalindex(index); return _buffer[actualindex]; } } } /// <summary> /// converts index in argument index in <code>_buffer</code> /// </summary> /// <returns> /// transformed index. /// </returns> /// <param name='index'> /// external index. /// </param> private int internalindex(int index) { return _start + (index < (size - _start) ? index : index - size); } /// <summary> /// clears instance. /// </summary> public void clear() { lock (_lock) { _numberofitemsinbuffer = 0; _start = 0; _end = 0; } } /// <summary> /// takes snapshot of queue , returns it. if used in isolation .i.e not in buffer implementation /// return elements of queue , leave queue empty. /// in buffer implementation , since buffer accepting data @ point of call; stale /// snapshot of queue when call made. /// </summary> /// <returns></returns> [obsolete("use takealldata() instead")] public t[] takesnapshot() { lock (_lock) { return takesnapshot(count); } } /// <summary> /// takes data available in queue. /// </summary> /// <returns></returns> public outputdata<t> takeall() { var count = count; if (count <= 0) return null; lock (_lock) { copyinto(count, _output); _outputdata.setlength(count); return _outputdata; } } /// <summary> /// takes snapshot of queue using count limit output return. in event specified /// count larger current size of queue, throw exception. 0 count value return /// in buffer implementation , since buffer accepting data @ point of call; stale /// snapshot of queue when call made. /// </summary> /// <returns></returns> [obsolete("use takealldata(int count) instead")] public t[] takesnapshot(int count) { if (count == 0) return null; lock (_lock) { if (count > _numberofitemsinbuffer) { count = _numberofitemsinbuffer; //throw new argumentoutofrangeexception(string.format("queue size {0}", size)); } var output = new t[count]; copyinto(count, output); return output; } } private void copyinto(int count, t[] output) { var lastindex = (_start + count) - 1; if (lastindex >= size) { array.copy(_buffer, _start, output, 0, size - _start); array.copy(_buffer, 0, output, size - _start, (lastindex%size) + 1); } else { array.copy(_buffer, _start, output, 0, count); } _start = (_start + count)%size; _numberofitemsinbuffer = _numberofitemsinbuffer - count; } public t[] peeksnapshot() { lock (_lock) { var count = count; var output = new t[count]; (var = 0; < count; i++) { output[i] = this[i]; } return output; } } public t[] peeksnapshot(int count) { if (count == 0) return null; lock (_lock) { if (count > size) { throw new argumentoutofrangeexception(string.format("queue size {0}", size)); } var output = new t[count]; (var = 0; < count; i++) { output[i] = this[i]; } return output; } } /// <summary> /// gets front of queue. earliest item added queue. /// use in lieu of checking this[0] null whilst items still /// exist in queue /// </summary> /// <value> /// front. /// </value> public t front() { lock (_lock) { return isempty ? _default : _buffer[_start]; } } /// <summary> /// gets utilisation of datastructure i.e % of datastructure in use /// </summary> /// <value> /// utilisation. /// </value> public float utilisation { { lock (_lock) { return calculateutilisation(); } } } private float calculateutilisation() { var util = 0f; if (size > 0) { util = (count/(float) size)*100; } return util; } /// <summary> /// returns latest item in queue. /// </summary> /// <returns></returns> public t back() { lock (_lock) { return count > 0 ? _buffer[_end - 1] : _default; ; } } public weakarray<t> takeweakarraysnapshot() { lock (_lock) { var count = count; var arr = new weakarray<t>(count); (var = 0; < count; i++) { arr[i] = dequeue(); } return arr; } } /// <summary> /// gets internal array. use extreme caution! not thread safe operation /// , should used in situations modification queue not possible. /// modification operations include enqueing or dequeing /// </summary> /// <returns></returns> public t[] getinternalarray() { return _buffer; } // doing arrayone , arraytwo methods returning arraysegment<t> seen here: // http://www.boost.org/doc/libs/1_37_0/libs/circular_buffer/doc/circular_buffer.html#classboost_1_1circular__buffer_1957cccdcb0c4ef7d80a34a990065818d // http://www.boost.org/doc/libs/1_37_0/libs/circular_buffer/doc/circular_buffer.html#classboost_1_1circular__buffer_1f5081a54afbc2dfc1a7fb20329df7d5b // should lot code. #region array items easy access. // array composed @ 2 non-contiguous segments, // next 2 methods allow easy access those. private arraysegment<t> arrayone() { if (_start < _end) { return new arraysegment<t>(_buffer, _start, _end - _start); } else { return new arraysegment<t>(_buffer, _start, _buffer.length - _start); } } private arraysegment<t> arraytwo() { if (_start < _end) { return new arraysegment<t>(_buffer, _end, 0); } else { return new arraysegment<t>(_buffer, 0, _end); } } #endregion }
most data structure performance , efficiency comes down problem trying solve.
i recommend not re-implement data structures unless don't exist already. things ngenerics exist solve kind of problems.
this sample project i'm sure there other types.
Comments
Post a Comment