Time-stamped, thread-safe data structure for time-based lookup?

Question

I want to implement a list type data structure that can be appended to, with an associated time-stamp. The point of this is that I can then get all the data that is newer than a certain time-stamp.

I have tried doing this with a ConcurrantDicitionary but I'm not confident this is the best way to do it. I would much prefer to have a List< decimal[2] > for applications which I won't go into here. The first value of the array can have the timestamp and the second will be the value. Alternatively, could use List< TimeStampedObject >. However, apparently there is no such thing as a concurrent list in C#.

For the record, my data is ordered with regards to timestamp.

I want to be able to do things like:

public static Dictionary<DateTime, decimal> GetLatest(DateTime since, Dictionary<DateTime, decimal> requestedDict)
{
    Dictionary<DateTime, decimal> returnList = new Dictionary<DateTime, decimal>();
    returnList = requestedDict.Where(x => x.Key > since).ToDictionary(x => x.Key, x => x.Value);
    return returnList;
}

UPDATE:

Here is the List item I have come up with; please let me know if this has any potential downfalls:

public class ConcurrentList: List<StampedValue>
    {

        ReaderWriterLockSlim _samplesLock = new ReaderWriterLockSlim();

        public ConcurrentList() : base()
        {
        }

        public void AddThreadSafe(StampedValue item){

            this._samplesLock.EnterWriteLock();
            try
            {
                this.Add(item);

            }
            finally
            {
                this._samplesLock.ExitWriteLock();
            }

        }

        public List<StampedValue> GetLatest(long since){
            return this.Where( s => s.Timestamp > since ).ToList();
        }

        public List<StampedValue> GetLatest(DateTime since){
            throw new NotImplementedException();
        }
    }


    public class StampedValue
    {
        public long Timestamp { get; set; }
        public decimal Value { get; set; }

        public StampedValue(long t, decimal v){
            this.Timestamp = t;
            this.Value = v;
        }

    }

You are basically reproducing the boilerplate code that the compiler would have produced from the `lock` statement. It's also recommended not to lock on the data (collection in this case) , but to use a private read only object. — Andre Artus, May 09 '14 at 04:48

Jim Mischel · Accepted Answer · 2014-05-09T13:03:32.843

4

Seems to me your best bet is just a List<T> that you protect with a ReaderWriterLockSlim. For example:

class Sample
{
    public DateTime EventTime { get; set; }
    public decimal Value { get; set; }
}

List<Sample> _samples = new List<Sample>();

ReaderWriterLockSlim _samplesLock = new ReaderWriterLockSlim();

// to get items after a particular date
List<Sample> GetSamplesAfterDate(DateTime dt)
{
    _samplesLock.EnterReadLock();
    try
    {
        return _samples.Where(s => s.EventTime >= dt).ToList();
    }
    finally
    {
        _samplesLock.ExitReadLock();
    }
}

If your list is known to be in chronological order, then you can improve the performance by using binary search on the list to find the first item that's greater than or equal to your passed time stamp. I just used the LINQ version here because the point is to illustrate the locking.

Appending to the list is similar: acquire the write lock, append, and release the lock:

void AppendSample(Sample s)
{
    _samplesLock.EnterWriteLock();
    try
    {
        _samples.Add(s);
    }
    finally
    {
        _samplesLock.ExitWriteLock();
    }
}

An alternative is to use List<KeyValuePair<DateTime, decimal>> rather than List<Sample>. The locking would remain the same.

This should perform quite well in most situations.

edited May 09 '14 at 13:03

answered May 08 '14 at 13:48

Jim Mischel

131,090
20
188
351

Hi thanks, I've editted my question with what I'm currently using, does that look like a good solution? – rex May 08 '14 at 23:34
@ArmenSafieh-Garabedian: You have to lock in your `GetLatest` method, too. Otherwise you risk getting an exception because the list is modified while you're enumerating it. That's the whole point of the reader/writer lock: to ensure that reading can be done concurrently, but when the list is being updated only one thread can be accessing it. – Jim Mischel May 09 '14 at 02:59
+1. @JimMischel, I assume the extra `finally` in AppendSample is merely a typo. – Andre Artus May 09 '14 at 04:56
1

@ArmenSafieh-Garabedian, I believe what Jim is saying is that unless you enjoy tracking down heisenbugs you should WriteLock on every write (fine or coarse grain), and ReadLock on every read (incl. taking the Count). It would be a good idea to encapsulate the behaviour in a new class. You have to use the same instance of a ReaderWriterLockSlim object or unpleasantries ensue. – Andre Artus May 09 '14 at 05:09
@JimMischel Ah I see okay. I assumed that if adding was thread-safe then the list wouldn't change while enumerating it since I only do Add operations with regards to writing. – rex May 09 '14 at 07:58
@AndreArtus, Jim, can I add your code to as an extension? PS: for the record, my list is ordered. – rex May 09 '14 at 08:03
1

@ArmenSafieh-Garabedian, writing the locking behaviour as extension methods will be tricky, as I mentioned before you must use the same instance of ReaderWriterLockSlim for all your reads and writes on the same collection. As long as the locking behaviour is contained in instance methods then you can write an extension method that utilizes those instance methods, but does not itself take any direct locks. – Andre Artus May 09 '14 at 08:31
@ArmenSafieh-Garabedian: I removed the spurious `finally`. No, it would not be appropriate to make extension methods out of this, for the reasons that @AndreArtus mentioned. – Jim Mischel May 09 '14 at 13:06
Would it be possible to implement this for IEnumarble as a new type of list? – rex May 13 '14 at 22:46
@ArmenSafieh-Garabedian: Yes, you could wrap this into a custom collection and have it implement `IEnumerable`. You'd probably also want it to implement `IList` and possibly other interfaces, depending on how you intend to use it. – Jim Mischel May 14 '14 at 03:37
@JimMischel Acually it's probably overkill to implement IEnumarable... I just want to have a regular list that is thread safe so I can do things like the above when the list can be appended to from another thread. In the future, I expect to use the list more like an in-memory buffer and keep the actual data in a DB. – rex May 14 '14 at 07:35

Andre Artus · Answer 2 · 2014-05-08T20:48:29.043

0

Have you looked at the SynchronizedCollection<T> class? It seems to me to be what you are looking for. You could also specialize SynchronizedKeyedCollection<K, T>

EDIT (2014/May/8):

The documentation I linked to above is not as clear or useful as one would like, as such it may be helpful to look at the reference implementation.

edited May 08 '14 at 20:48

answered May 08 '14 at 04:07

Andre Artus

1,850
15
21

That looks interesting but what does this mean? "Any public static (Shared in Visual Basic) members of this type are thread safe. Any instance members are not guaranteed to be thread safe." :O – rex May 08 '14 at 06:56
@ArmenSafieh-Garabedian, that's unfortunately a bit of vestigial boilerplate documentation. If you look at the reference implementation you should see that mutation is done under a lock. – Andre Artus May 08 '14 at 20:36

Time-stamped, thread-safe data structure for time-based lookup?

2 Answers2