A simple paged IList, arrays of doubles and the LOH

Turns out large (1000+ elements) arrays of doubles get put on the Large Object Heap, rather than living out their days on the normal heap. Apparently, it’s an optimization by Microsoft to keep the arrays aligned to 8-byte boundaries (as the LOH is collected but not compacted).

This leads to some exciting behaviour if you’re using a List<double> that reaches 1000 doubles. Especially if you’re not thinking about it, and just allowing it to expand, as you’ll keep recreating new arrays whenever you reach the array size limit. Did MS choose 1000 or 1024? Not sure.

A colleague hit this recently in our production code. In our specific case the right thing to do was stop using so many large arrays of doubles, as they weren’t needed.

Alternatively, one way to avoid fragmentation and LOH usage would be to preallocate large arrays or Lists of doubles – if you know how large an array you’re going to need.

Another way would be to create a paged IList implementation, one keeps its contents in a set of arrays that are sized just under the maximum to avoid LOH use.

Yes, it subverts Microsoft’s performance enhancement, and yes, I’m sure they know what they’re doing. I’m not sure what they’re doing though, so if nothing else it means I can run some comparisons, iterating through a list of doubles, for example.

Conveniently it also makes another nice workout – some code below, using a List<T[]> as the underlying page collection. I've not implemented Remove, RemoveAt and Insert methods as I didn't immediately need them for the tests I had in mind.

public class PagedList<T> : IList<T>
{
 private int _pageSize = 100;

 private int _currentPage = 0;

 private int _currentPageHighwatermark = 0;

 private List<T[]> _underlyingList;

 public PagedList(int pageSize)
 {
  _pageSize = pageSize;
  _underlyingList = new List();
  _underlyingList.Add(new T[_pageSize]);      
                    // if it has pages already, we'll be tagging an 
                    // extra empty page on the end ...
  _currentPage = _underlyingList.Count - 1;                   
                    // also, if it has pages already then the 
                    // highwatermark will be wrong            
 }

 /// <returns>Index of element, -1 if not found</returns>
 public int IndexOf(T item) // consider boxing, unboxing
 {
  int index = 0;
  var iter = _underlyingList.GetEnumerator();
  while(iter.MoveNext())
  {
   foreach(var t in iter.Current)
   {
    if(t.Equals(item))
    {
     return index;
    }
    index++;
   }
  }
  return -1;
 }

 public void Insert(int index, T item)
 {
  throw new NotImplementedException();
 }

 public void RemoveAt(int index)
 {
  throw new NotImplementedException();
 }

 public T this[int index]
 {
  get
  {
   int desiredPage = Math.Abs(index/_pageSize);
   int desiredPageIndex = index%_pageSize;
   if (desiredPage * _pageSize + desiredPageIndex > 
                                _currentPage * _pageSize + _currentPageHighwatermark 
                                || index < 0)
   {
    throw new IndexOutOfRangeException("Index was out of bounds");
   }
   return _underlyingList[desiredPage][desiredPageIndex]; // Consider what to do about nulls here
  }
  set
  {
   // Check whether index is out of range
   int desiredPage = Math.Abs(index / _pageSize);
   int desiredPageIndex = index % _pageSize;
   if (desiredPage * _pageSize + desiredPageIndex > 
                                _currentPage * _pageSize + _currentPageHighwatermark 
                                || index < 0)   {
    throw new IndexOutOfRangeException("Index was out of bounds");
   }
   _underlyingList[desiredPage][desiredPageIndex] = value;
  }
 }

 public void Add(T item)
 {
  var page = _underlyingList.Last();
  if (_currentPageHighwatermark == _pageSize)
  {
   _underlyingList.Add(new T[_pageSize]);
   _currentPage++;
   _currentPageHighwatermark = 0;
  }
  _underlyingList[_currentPage][_currentPageHighwatermark] = item;
  _currentPageHighwatermark++;
 }

 public void Clear()
 {
  _underlyingList.Clear();
  _underlyingList.Add(new T[_pageSize]);
  _currentPage = 0;
  _currentPageHighwatermark = 0;
 }

 public bool Contains(T item)
 {
  var iter = _underlyingList.GetEnumerator();
  while (iter.MoveNext())
  {
   foreach (var t in iter.Current)
   {
    if (t.Equals(item))
    {
     return true;
    }
   }
  }
  return false;
 }

        public void CopyTo(T[] array, int arrayIndex)
        {
            // Do out-of-bounds checking on arrayIndex, sizeof array
            for(int i = arrayIndex; i < Count; i++)
            {
                array[i - arrayIndex] = this[i];
            }
        }

 public int Count
 {
  get { return (_currentPage*_pageSize) + _currentPageHighwatermark; }
 }

 public bool IsReadOnly
 {
  get { throw new NotImplementedException(); }
 }

 public bool Remove(T item)
 {
  throw new NotImplementedException();
 }

 public IEnumerator<T> GetEnumerator()
 {
  return new PagedListEnumerator<T>(this);
 }

 private class PagedListEnumerator<T> : IEnumerator<T>
 {
  private PagedList<T> _underlyingPagedList;
  private int _cursor;

  public PagedListEnumerator(PagedList<T> list)
  {
   _underlyingPagedList = list;
   _cursor = -1;
  }

  public void Dispose()
  {
  }

  public bool MoveNext()
  {
   if (_cursor < _underlyingPagedList.Count)
    _cursor++;

   return (!(_cursor == _underlyingPagedList.Count));
  }

  public void Reset()
  {
   _cursor = -1;
  }

  public T Current
  {
   get { return _underlyingPagedList[_cursor]; }   // Handle fail when out of bounds
  }

  object IEnumerator.Current
  {
   get { return Current; }
  }
 }

        System.Collections.IEnumerator System.Collections.IEnumerable.GetEnumerator()
        {
            return GetEnumerator();
        }
}

C# BiDirectional Lookup

This seems to happen regularly: I start using a Dictionary to group data, only to find that at some stage I need to lookup from value to key again. As .NET has no birectional map, dictionary or lookup, handling this is always cumbersome, like trying to find out which kitchen junk drawer contains the screwdriver you need.

In my case I was building groups of financial transactions by creating a map keyed on group name. I matched each new transaction to each existing transaction to work out which was the closest match, based on some criteria, then added the new transaction to the same group as the closest match.

The problem here is that I needed to do a reverse lookup – also traversing each element of the group map to work out which group the closest match was in. It works, but it feels wrong.

One solution is to maintain both forward and lookup structures – which informed the bidirectional lookup workout presented below. That felt a little better – at least I was no longer completely abusing the dictionary every time I wanted to add something.

A little thought, though, showed that if I want to work out which group a new transaction should be in, then I should compare each transaction to some group criteria (not trade criteria) and add it to the closest matching group. As there’ll be fewer groups than trades, this should be quicker – and no reverse lookup needed.

In any event: just because a bidirectional lookup might be wrong in this case, doesn’t mean it’s always so, and working a simple one up isn’t an enormous task. And it makes a nice workout for the list.

Also: this is certainly not the only way of doing a bidirectional lookup; it really does depend on what you need. For a set of {first, second} pairs, I wanted to allow a second to map to multiple firsts, and vice versa.

Bit of a mix of styles as it's the result of a workout.

public class BiDiLookup<TFirst, TSecond>
{
    private IDictionary<TFirst, List<TSecond>> Forward
    {
        get;
        set;
    }

    private IDictionary<TSecond, List<TFirst>> Backward
    {
        get;
        set;
    }

    private BiDiLookup()
    {
    }

    public BiDiLookup(
                IDictionary<TFirst, List<TSecond>> forward, 
                IDictionary<TSecond, List<TFirst>> backward)
    {
        Forward = forward;
        Backward = backward;
    }

    public void Add(TFirst first, TSecond second)
    {
        // Consider what to do when adding an already-existing pair ..
        // Nice trick here courtesy Jon Skeet to reduce the number 
        // of lookups -- see also GetByFirst etc for comparison
        List<TSecond> secondList;
	if (!Forward.TryGetValue(first, out secondList))
        {
            secondList = new List<TSecond>();
            Forward[first] = secondList;
        }
        List<TFirst> firstList;
        if (!Backward.TryGetValue(second, out firstList))
        {
            firstList = new List<TFirst>();
            Backward[second] = firstList;
        }
        secondList.Add(second);
        firstList.Add(first);
    }

    private static List<TFirst> EmptyFirstList = new List<TFirst>();
    private static List<TSecond> EmptySecondList = new List<TSecond>();

    public List<TSecond> GetByFirst(TFirst first)
    {
        // Consider what to do if first doesn't exist yet -- return an empty list? return null?
        if (Forward.ContainsKey(first))
        {
            return Forward[first];
        }
        return EmptySecondList;
    }

    public List<TFirst> GetBySecond(TSecond second)
    {
        if (Backward.ContainsKey(second))
        {
            return Backward[second];
        }
        return EmptyFirstList;
   }

   public void Remove(TFirst first, TSecond second)
    {
        // Consider -- what if we want to just remove all instances of first, or second?
        List<TSecond> seconds = Forward[first];
        List<TFirst> firsts = Backward[second];
        Forward.Remove(first);
        foreach (var s in seconds)
        {
            Backward[s].Remove(first);
            if (Backward[s].Count == 0)
            {
                Backward.Remove(s);
            }
        }
        Backward.Remove(second);
        foreach (var f in firsts)
        {
            Forward[f].Remove(second);
            if (Forward[f].Count == 0)
            {
                Forward.Remove(f);
            }
        }
    }
}