9
\$\begingroup\$

In my open source project, I have code that uses a dictionary very intensively so a system dictionary implementation did not suit me due to performance reasons. Therefore, I decided to write my own implementation that uses unsafe code. Fortunately, I can use integers as dictionary keys and I always know the max dictionary size.

Here is the implementation of the specific collection:

using System.Collections;
using System.Collections.Generic;
using System.Linq;

namespace logviewer.logic.support
{
    public unsafe class FixedSizeDictionary<T> : IDictionary<int, T>
    {
        private readonly int count;
        private int[] indexes;
        private T[] store;

        public FixedSizeDictionary(int count)
        {
            this.count = count;
            this.store = new T[count];
            this.indexes = new int[count];
        }

        public IEnumerator<KeyValuePair<int, T>> GetEnumerator()
        {
            for (var i = 0; i < this.store.Length; i++)
            {
                if (this.ContainsKeyInternal(i))
                {
                    yield return new KeyValuePair<int, T>(i, this.store[i]);
                }
            }
        }

        IEnumerator IEnumerable.GetEnumerator()
        {
            return this.GetEnumerator();
        }

        public void Add(KeyValuePair<int, T> item)
        {
            this.Add(item.Key, item.Value);
        }

        public void Clear()
        {
            this.store = new T[this.count];
            this.indexes = new int[this.count];
        }

        public bool Contains(KeyValuePair<int, T> item)
        {
            return this.indexes[item.Key] > 0 && Equals(this.store[item.Key], item.Value);
        }

        public void CopyTo(KeyValuePair<int, T>[] array, int arrayIndex)
        {
            for (var i = arrayIndex; i < array.Length && i < this.store.Length; i++)
            {
                if (this.ContainsKeyInternal(i))
                {
                    array[i] = new KeyValuePair<int, T>(i, this.store[i]);
                }
            }
        }

        public bool Remove(KeyValuePair<int, T> item)
        {
            return this.Remove(item.Key);
        }

        public int Count
        {
            get
            {
                var result = 0;
                for (var i = 0; i < this.store.Length; i++)
                {
                    if (this.ContainsKeyInternal(i))
                    {
                        result++;
                    }
                }
                return result;
            }
        }

        public bool IsReadOnly => false;

        public bool ContainsKey(int key)
        {
            return key < this.count && this.ContainsKeyInternal(key);
        }

        public void Add(int key, T value)
        {
            if (key >= this.count)
            {
                return;
            }
            this.store[key] = value;
            this.indexes[key] = 1;
        }

        public bool Remove(int key)
        {
            if (key >= this.count || !this.ContainsKeyInternal(key))
            {
                return false;
            }
            this.store[key] = default(T);
            this.indexes[key] = 0;
            return true;
        }

        /// <remarks>
        ///     IMPORTANT: key out of range intentionally missed here due to performance reasons.
        ///     You shouldn't pass key that out of size range to avoid undefined behaviour
        /// </remarks>
        public bool TryGetValue(int key, out T value)
        {
            fixed (int* p = this.indexes)
            {
                if (p[key] == 0)
                {
                    value = default(T);
                    return false;
                }
            }
            value = this.store[key];
            return true;
        }

        public T this[int key]
        {
            get { return this.store[key]; }
            set { this.store[key] = value; }
        }

        public ICollection<int> Keys
        {
            get { return this.Select(pair => pair.Key).ToArray(); }
        }

        public ICollection<T> Values
        {
            get { return this.Select(pair => pair.Value).ToArray(); }
        }

        private bool ContainsKeyInternal(int key)
        {
            fixed (int* p = this.indexes)
            {
                return p[key] > 0;
            }
        }
    }
}

The results of benchmarking (getting element by key) using BenchmarkDotNet.

<html lang='en'>
<head>
<meta charset='utf-8' />
<title>DictionaryVsFixedSizeDictionary</title>

<style type="text/css">
	table { border-collapse: collapse; display: block; width: 100%; overflow: auto; }
	td, th { padding: 6px 13px; border: 1px solid #ddd; }
	tr { background-color: #fff; border-top: 1px solid #ccc; }
	tr:nth-child(even) { background: #f8f8f8; }
</style>
</head>
<body>
<pre><code>
BenchmarkDotNet=v0.10.3.0, OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i5-4570 CPU 3.20GHz, ProcessorCount=4
Frequency=3125011 Hz, Resolution=319.9989 ns, Timer=TSC
  [Host]           : Clr 4.0.30319.42000, 32bit LegacyJIT-v4.6.1637.0
  RyuJitColdStart  : Clr 4.0.30319.42000, 64bit RyuJIT-v4.6.1637.0
  RyuJitMonitoring : Clr 4.0.30319.42000, 64bit RyuJIT-v4.6.1637.0
  RyuJitThroughput : Clr 4.0.30319.42000, 64bit RyuJIT-v4.6.1637.0
</code></pre>
<pre><code>Jit=RyuJit  Platform=X64  Runtime=Clr  
InvocationCount=100000000  LaunchCount=1  TargetCount=10  
WarmupCount=3  
</code></pre>

<table>
<thead><tr><th>Method</th><th>       Job</th><th>RunStrategy</th><th>UnrollFactor</th><th>Mean</th><th>StdErr</th><th>StdDev</th><th>Scaled</th><th>Scaled-StdDev</th>
</tr>
</thead><tbody><tr><td>FixedSize</td><td>RyuJitColdStart</td><td>ColdStart</td><td>     1</td><td>3.8716 ns</td><td>0.0092 ns</td><td>0.0292 ns</td><td>0.27</td><td>   0.00</td>
</tr><tr><td>Standart</td><td>RyuJitColdStart</td><td>ColdStart</td><td>     1</td><td>14.1455 ns</td><td>0.0117 ns</td><td>0.0371 ns</td><td>1.00</td><td>   0.00</td>
</tr><tr><td>FixedSize</td><td>RyuJitMonitoring</td><td>Monitoring</td><td>     1</td><td>4.1917 ns</td><td>0.0082 ns</td><td>0.0261 ns</td><td>0.29</td><td>   0.00</td>
</tr><tr><td>Standart</td><td>RyuJitMonitoring</td><td>Monitoring</td><td>     1</td><td>14.3810 ns</td><td>0.0103 ns</td><td>0.0325 ns</td><td>1.00</td><td>   0.00</td>
</tr><tr><td>FixedSize</td><td>RyuJitThroughput</td><td>Throughput</td><td>    16</td><td>0.3458 ns</td><td>0.0089 ns</td><td>0.0268 ns</td><td>0.04</td><td>   0.00</td>
</tr><tr><td>Standart</td><td>RyuJitThroughput</td><td>Throughput</td><td>    16</td><td>9.8207 ns</td><td>0.0127 ns</td><td>0.0403 ns</td><td>1.00</td><td>   0.00</td>
</tr></tbody></table>
</body>
</html>

As you can see it's much faster than the standard .NET dictionary collection in this specific case.

As people asked me to test safe version of the collection (i.e. without unsafe code), here is the implementation (it's almost the same like unsafe version) but without usings which is the same as before:

public class SafeFixedSizeDictionary<T> : IDictionary<int, T>
{
    private readonly int count;
    private int[] indexes;
    private T[] store;

    public SafeFixedSizeDictionary(int count)
    {
        this.count = count;
        this.store = new T[count];
        this.indexes = new int[count];
    }

    public IEnumerator<KeyValuePair<int, T>> GetEnumerator()
    {
        for (var i = 0; i < this.store.Length; i++)
        {
            if (this.ContainsKeyInternal(i))
            {
                yield return new KeyValuePair<int, T>(i, this.store[i]);
            }
        }
    }

    IEnumerator IEnumerable.GetEnumerator()
    {
        return this.GetEnumerator();
    }

    public void Add(KeyValuePair<int, T> item)
    {
        this.Add(item.Key, item.Value);
    }

    public void Clear()
    {
        this.store = new T[this.count];
        this.indexes = new int[this.count];
    }

    [Pure]
    public bool Contains(KeyValuePair<int, T> item)
    {
        return this.indexes[item.Key] > 0 && Equals(this.store[item.Key], item.Value);
    }

    public void CopyTo(KeyValuePair<int, T>[] array, int arrayIndex)
    {
        for (var i = arrayIndex; i < array.Length && i < this.store.Length; i++)
        {
            if (this.ContainsKeyInternal(i))
            {
                array[i] = new KeyValuePair<int, T>(i, this.store[i]);
            }
        }
    }

    public bool Remove(KeyValuePair<int, T> item)
    {
        return this.Remove(item.Key);
    }

    public int Count
    {
        get
        {
            var result = 0;
            for (var i = 0; i < this.store.Length; i++)
            {
                if (this.ContainsKeyInternal(i))
                {
                    result++;
                }
            }
            return result;
        }
    }

    public bool IsReadOnly => false;

    [Pure]
    public bool ContainsKey(int key)
    {
        return key < this.count && this.ContainsKeyInternal(key);
    }

    public void Add(int key, T value)
    {
        if (key >= this.count)
        {
            return;
        }
        this.store[key] = value;
        this.indexes[key] = 1;
    }

    public bool Remove(int key)
    {
        if (key >= this.count || !this.ContainsKeyInternal(key))
        {
            return false;
        }
        this.store[key] = default(T);
        this.indexes[key] = 0;
        return true;
    }

    /// <remarks>
    ///     IMPORTANT: key out of range intentionally missed here due to performance reasons.
    ///     You shouldn't pass key that out of size range to avoid undefined behaviour
    /// </remarks>
    public bool TryGetValue(int key, out T value)
    {
        if (this.indexes[key] == 0)
        {
            value = default(T);
            return false;
        }
        value = this.store[key];
        return true;
    }

    public T this[int key]
    {
        get { return this.store[key]; }
        set { this.store[key] = value; }
    }

    public ICollection<int> Keys
    {
        get { return this.Select(pair => pair.Key).ToArray(); }
    }

    public ICollection<T> Values
    {
        get { return this.Select(pair => pair.Value).ToArray(); }
    }

    private bool ContainsKeyInternal(int key)
    {
        return this.indexes[key] > 0;
    }
}

This time I tested the TryGetValue method that uses unsafe code instead of a plain indexer which implementation is the same in both versions. And I found that the safe version is even faster than unsafe code and only two times faster than a standard .NET dictionary.

Here is the benchmark results:

<!DOCTYPE html>
<html lang='en'>

<head>
  <meta charset='utf-8' />
  <title>DictionaryVsFixedSizeDictionary</title>

  <style type="text/css">
    table {
      border-collapse: collapse;
      display: block;
      width: 100%;
      overflow: auto;
    }
    
    td,
    th {
      padding: 6px 13px;
      border: 1px solid #ddd;
    }
    
    tr {
      background-color: #fff;
      border-top: 1px solid #ccc;
    }
    
    tr:nth-child(even) {
      background: #f8f8f8;
    }
  </style>
</head>

<body>
  <pre><code>
BenchmarkDotNet=v0.10.3.0, OS=Microsoft Windows NT 6.2.9200.0
Processor=Intel(R) Core(TM) i5-4570 CPU 3.20GHz, ProcessorCount=4
Frequency=3125012 Hz, Resolution=319.9988 ns, Timer=TSC
  [Host]              : Clr 4.0.30319.42000, 32bit LegacyJIT-v4.6.1637.0
  LegacyJitColdStart  : Clr 4.0.30319.42000, 64bit LegacyJIT/clrjit-v4.6.1637.0;compatjit-v4.6.1637.0
  LegacyJitMonitoring : Clr 4.0.30319.42000, 64bit LegacyJIT/clrjit-v4.6.1637.0;compatjit-v4.6.1637.0
  LegacyJitThroughput : Clr 4.0.30319.42000, 64bit LegacyJIT/clrjit-v4.6.1637.0;compatjit-v4.6.1637.0
  RyuJitColdStart     : Clr 4.0.30319.42000, 64bit RyuJIT-v4.6.1637.0
  RyuJitMonitoring    : Clr 4.0.30319.42000, 64bit RyuJIT-v4.6.1637.0
  RyuJitThroughput    : Clr 4.0.30319.42000, 64bit RyuJIT-v4.6.1637.0
</code></pre>
  <pre><code>Platform=X64  Runtime=Clr  InvocationCount=100000000  
LaunchCount=1  TargetCount=10  WarmupCount=3  
</code></pre>

  <table>
    <thead>
      <tr>
        <th> Method</th>
        <th> Job</th>
        <th>Jit</th>
        <th>RunStrategy</th>
        <th>UnrollFactor</th>
        <th>Mean</th>
        <th>StdErr</th>
        <th>StdDev</th>
        <th>Scaled</th>
        <th>Scaled-StdDev</th>
      </tr>
    </thead>
    <tbody>
      <tr>
        <td>FixedSize</td>
        <td>LegacyJitColdStart</td>
        <td>LegacyJit</td>
        <td>ColdStart</td>
        <td> 1</td>
        <td>5.3069 ns</td>
        <td>0.0412 ns</td>
        <td>0.1301 ns</td>
        <td>0.33</td>
        <td> 0.01</td>
      </tr>
      <tr>
        <td>SafeFixedSize</td>
        <td>LegacyJitColdStart</td>
        <td>LegacyJit</td>
        <td>ColdStart</td>
        <td> 1</td>
        <td>4.7658 ns</td>
        <td>0.0233 ns</td>
        <td>0.0736 ns</td>
        <td>0.30</td>
        <td> 0.01</td>
      </tr>
      <tr>
        <td>Standart</td>
        <td>LegacyJitColdStart</td>
        <td>LegacyJit</td>
        <td>ColdStart</td>
        <td> 1</td>
        <td>15.9246 ns</td>
        <td>0.0701 ns</td>
        <td>0.2215 ns</td>
        <td>1.00</td>
        <td> 0.00</td>
      </tr>
      <tr>
        <td>FixedSize</td>
        <td>LegacyJitMonitoring</td>
        <td>LegacyJit</td>
        <td>Monitoring</td>
        <td> 1</td>
        <td>6.2377 ns</td>
        <td>0.0266 ns</td>
        <td>0.0840 ns</td>
        <td>0.41</td>
        <td> 0.01</td>
      </tr>
      <tr>
        <td>SafeFixedSize</td>
        <td>LegacyJitMonitoring</td>
        <td>LegacyJit</td>
        <td>Monitoring</td>
        <td> 1</td>
        <td>5.1902 ns</td>
        <td>0.0122 ns</td>
        <td>0.0387 ns</td>
        <td>0.34</td>
        <td> 0.00</td>
      </tr>
      <tr>
        <td>Standart</td>
        <td>LegacyJitMonitoring</td>
        <td>LegacyJit</td>
        <td>Monitoring</td>
        <td> 1</td>
        <td>15.3916 ns</td>
        <td>0.0289 ns</td>
        <td>0.0914 ns</td>
        <td>1.00</td>
        <td> 0.00</td>
      </tr>
      <tr>
        <td>FixedSize</td>
        <td>LegacyJitThroughput</td>
        <td>LegacyJit</td>
        <td>Throughput</td>
        <td> 16</td>
        <td>2.2629 ns</td>
        <td>0.0262 ns</td>
        <td>0.0829 ns</td>
        <td>0.19</td>
        <td> 0.01</td>
      </tr>
      <tr>
        <td>SafeFixedSize</td>
        <td>LegacyJitThroughput</td>
        <td>LegacyJit</td>
        <td>Throughput</td>
        <td> 16</td>
        <td>1.1241 ns</td>
        <td>0.0161 ns</td>
        <td>0.0508 ns</td>
        <td>0.10</td>
        <td> 0.00</td>
      </tr>
      <tr>
        <td>Standart</td>
        <td>LegacyJitThroughput</td>
        <td>LegacyJit</td>
        <td>Throughput</td>
        <td> 16</td>
        <td>11.6338 ns</td>
        <td>0.0457 ns</td>
        <td>0.1444 ns</td>
        <td>1.00</td>
        <td> 0.00</td>
      </tr>
      <tr>
        <td>FixedSize</td>
        <td>RyuJitColdStart</td>
        <td>RyuJit</td>
        <td>ColdStart</td>
        <td> 1</td>
        <td>9.4315 ns</td>
        <td>0.0148 ns</td>
        <td>0.0467 ns</td>
        <td>0.57</td>
        <td> 0.01</td>
      </tr>
      <tr>
        <td>SafeFixedSize</td>
        <td>RyuJitColdStart</td>
        <td>RyuJit</td>
        <td>ColdStart</td>
        <td> 1</td>
        <td>8.7796 ns</td>
        <td>0.0152 ns</td>
        <td>0.0482 ns</td>
        <td>0.53</td>
        <td> 0.01</td>
      </tr>
      <tr>
        <td>Standart</td>
        <td>RyuJitColdStart</td>
        <td>RyuJit</td>
        <td>ColdStart</td>
        <td> 1</td>
        <td>16.5658 ns</td>
        <td>0.0565 ns</td>
        <td>0.1786 ns</td>
        <td>1.00</td>
        <td> 0.00</td>
      </tr>
      <tr>
        <td>FixedSize</td>
        <td>RyuJitMonitoring</td>
        <td>RyuJit</td>
        <td>Monitoring</td>
        <td> 1</td>
        <td>8.7325 ns</td>
        <td>0.0312 ns</td>
        <td>0.0988 ns</td>
        <td>0.54</td>
        <td> 0.01</td>
      </tr>
      <tr>
        <td>SafeFixedSize</td>
        <td>RyuJitMonitoring</td>
        <td>RyuJit</td>
        <td>Monitoring</td>
        <td> 1</td>
        <td>7.8220 ns</td>
        <td>0.0241 ns</td>
        <td>0.0762 ns</td>
        <td>0.48</td>
        <td> 0.00</td>
      </tr>
      <tr>
        <td>Standart</td>
        <td>RyuJitMonitoring</td>
        <td>RyuJit</td>
        <td>Monitoring</td>
        <td> 1</td>
        <td>16.2030 ns</td>
        <td>0.0184 ns</td>
        <td>0.0583 ns</td>
        <td>1.00</td>
        <td> 0.00</td>
      </tr>
      <tr>
        <td>FixedSize</td>
        <td>RyuJitThroughput</td>
        <td>RyuJit</td>
        <td>Throughput</td>
        <td> 16</td>
        <td>5.4260 ns</td>
        <td>0.0276 ns</td>
        <td>0.0874 ns</td>
        <td>0.46</td>
        <td> 0.01</td>
      </tr>
      <tr>
        <td>SafeFixedSize</td>
        <td>RyuJitThroughput</td>
        <td>RyuJit</td>
        <td>Throughput</td>
        <td> 16</td>
        <td>4.2026 ns</td>
        <td>0.0077 ns</td>
        <td>0.0232 ns</td>
        <td>0.35</td>
        <td> 0.00</td>
      </tr>
      <tr>
        <td>Standart</td>
        <td>RyuJitThroughput</td>
        <td>RyuJit</td>
        <td>Throughput</td>
        <td> 16</td>
        <td>11.9118 ns</td>
        <td>0.0195 ns</td>
        <td>0.0586 ns</td>
        <td>1.00</td>
        <td> 0.00</td>
      </tr>
    </tbody>
  </table>
</body>

</html>

The morale - before using unsafe code it would better to do benchmark before.

One answer pointed out Count property optimization, but I think it's not needed because the code is optimized by JIT.

Here is the assembler code:

0:000> !u 00007ff93b299dc9
Normal JIT generated code
logviewer.logic.support.FixedSizeDictionary`1[[System.DateTime,    mscorlib]].get_Count()
Begin 00007ff93b299d90, size 44

C:\code\logviewer\logviewer.logic\support\FixedSizeDictionary.cs @ 92:
00007ff9`3b299d90 4883ec28        sub     rsp,28h
00007ff9`3b299d94 33c0            xor     eax,eax

C:\code\logviewer\logviewer.logic\support\FixedSizeDictionary.cs @ 93:
00007ff9`3b299d96 33d2            xor     edx,edx
00007ff9`3b299d98 4c8b4110        mov     r8,qword ptr [rcx+10h]
00007ff9`3b299d9c 458b4008        mov     r8d,dword ptr [r8+8]
00007ff9`3b299da0 4585c0          test    r8d,r8d
00007ff9`3b299da3 7e24            jle     00007ff9`3b299dc9
00007ff9`3b299da5 488b4908        mov     rcx,qword ptr [rcx+8]
00007ff9`3b299da9 4c8bc9          mov     r9,rcx
00007ff9`3b299dac 458b5108        mov     r10d,dword ptr [r9+8]
00007ff9`3b299db0 413bd2          cmp     edx,r10d
00007ff9`3b299db3 7319            jae     00007ff9`3b299dce
00007ff9`3b299db5 4c63d2          movsxd  r10,edx
00007ff9`3b299db8 43837c911000    cmp     dword ptr [r9+r10*4+10h],0
00007ff9`3b299dbe 7e02            jle     00007ff9`3b299dc2

C:\code\logviewer\logviewer.logic\support\FixedSizeDictionary.cs @ 97:
00007ff9`3b299dc0 ffc0            inc     eax

C:\code\logviewer\logviewer.logic\support\FixedSizeDictionary.cs @ 93:
00007ff9`3b299dc2 ffc2            inc     edx
00007ff9`3b299dc4 443bc2          cmp     r8d,edx
00007ff9`3b299dc7 7fe0            jg      00007ff9`3b299da9

C:\code\logviewer\logviewer.logic\support\FixedSizeDictionary.cs @ 100:
00007ff9`3b299dc9 4883c428        add     rsp,28h
00007ff9`3b299dcd c3              ret

C:\code\logviewer\logviewer.logic\support\FixedSizeDictionary.cs @ 92:
00007ff9`3b299dce e89dd9535f      call    clr!JIT_RngChkFail (00007ff9`9a7d7770)
00007ff9`3b299dd3 cc              int     3

Some comments:

The first property line is 92. Loop for is line 93. As you can see all private method usages inlined.

\$\endgroup\$
11
  • 1
    \$\begingroup\$ I want to get feedback whether this approach good or bad and of course to get advice about code improvements. \$\endgroup\$ Commented Mar 20, 2017 at 21:17
  • \$\begingroup\$ Unfortunatelly the benchmark is useless without comparing it to system dictionary. \$\endgroup\$
    – t3chb0t
    Commented Mar 21, 2017 at 4:47
  • \$\begingroup\$ As you can see I compared it exactly with the BCL dictionary. Standard row is the result of BCL dictionary measure \$\endgroup\$ Commented Mar 21, 2017 at 4:49
  • 1
    \$\begingroup\$ Here is the benchmark test code on GitHub github.com/aegoroff/logviewer/blob/develop/logviewer.bench/… \$\endgroup\$ Commented Mar 21, 2017 at 5:05
  • 1
    \$\begingroup\$ Its unclear of which version you want to get a code review. \$\endgroup\$
    – Heslacher
    Commented Mar 23, 2017 at 8:53

2 Answers 2

2
\$\begingroup\$

Here're a few more mistakes.

public bool Contains(KeyValuePair<int, T> item)
{
  return this.indexes[item.Key] > 0 && Equals(this.store[item.Key], item.Value);
}

This method will throw if the key is out of range but it shouldn't.

Rather then using a 0 for an invalid index (which by the way is a valid index unless you're dealing with db indexes) you should create two constants like

const int indexOutOfRange = -1;
const int unsetIndex = -1;

and use them instead of the magic numbers so the correct version of Contains could be:

public bool Contains(KeyValuePair<int, T> item)
{
    return 
        item.Key > indexOutOfRange &&
        item.Key < indexes.Length &&
        indexes[item.Key] != unsetIndex && 
        store[item.Key].Equals(item.Value);
}

private readonly int count;

You don't need this field. The length is already the same as indexes.Length. Instead you can use the count to actually count how many items the dictionary stores so you don't have to count them with linq if you need this property frequently.

\$\endgroup\$
1
  • \$\begingroup\$ Thank you. You pointed out the real problems in the code. I fixed them, but you should avoid ContainsKeyInternal method usage because in real assembler code it will be inlined an no call instruction will be generated. And i would like to say that you should loop over array with for using array Length property instead of count field so as to runtime could use array access optimization. \$\endgroup\$ Commented Mar 27, 2017 at 18:28
2
\$\begingroup\$

A big problem I see with either version is, that it doesn't behave like a Dictionary nor does it follow the documentation of the IDictionary<TKey, TValue>.

Examples about this point

  • Adding a KeyValuePair twice with the same key is silently overwriting the value responding to the key. Your class should throw an ArgumentException for such a case.

  • Accessing the Item property should throw a KeyNotFoundException for any Tkey key which isn't in the dictionary.

  • ...


The Count property of each version could be simplified either by using Linq like

return this.indexes.Count(i => i > 0);  

which is slow, or by a simple loop without the ContainsKeyInternal() call like so

            var result = 0;
            for (var i = 0; i < count; i++)
            {
                if (this.indexes[i] > 0)
                {
                    result++;
                }
            }
            return result;  

as you see I have changed the loop condition by using the count field. Accessing the Length property of the array each time the condition is evaluated will take some time as well and you have the count field, so you should use it.


You don't need for the Keys and Values properties the call to the GetEnumerator() of your class and later restricting the result either to the Key or Value property of the returned KeyValuePair`.

I would suggest to add two more methods IEnumerable<int> GetKeysInternal() and IEnumerable<T> GetValuesInternal() like so

public ICollection<int> Keys
{
    get {
        return this.GetKeysInternal().ToArray();
    }
}
private IEnumerable<int> GetKeysInternal()
{
    for (var i = 0; i < count; i++)
    {
        if (this.indexes[i] > 0)
        {
            yield return i;
        }
    }
}

public ICollection<T> Values
{
    get { return this.GetValuesInternal().ToArray(); }
}
private IEnumerable<T> GetValuesInternal()
{
    for (var i = 0; i < count; i++)
    {
        if (this.indexes[i] > 0)
        {
            yield return this.store[i];
        }
    }
}

Both versions have this

/// <remarks>
///     IMPORTANT: key out of range intentionally missed here due to performance reasons.
///     You shouldn't pass key that out of size range to avoid undefined behaviour
/// </remarks>
public bool TryGetValue(int key, out T value)  

IMO a bool Try...() method should never ever throw an exception hence this xml doc isn't neccessary. A simple check for key >= count would be enough like so

public bool TryGetValue(int key, out T value)
{
    if (key >= this.count || this.indexes[key] == 0)
    {
        value = default(T);
        return false;
    }
    value = this.store[key];
    return true;
}

The CopyTo() method has some more flaws.

  • If we take the CopyTo() method of the standard Dictionary<> implemented through the IDictionary<> interface we get an array returned where the found KeyValuePair's are stored in the beginning of the array. Your implementation stores the KeyValuePair's at its original positions. As a user of your class I wouldn't expect this.

  • If we pass a negativ arrayIndex we get a IndexOutOfRangeException from the private ContainsKeyInternal() method which means you are exposing implementation details of your class.

    You should check the parameter and throw an ArgumentOutOfRangeException.

  • If the array isn't big enough to get all KeyValuePair's an ArgumentException should be thrown stating that the array isn't big enough.
    Currently your implementation is copying items until the array is full or until the end of the source array is reached, but with the sideeffect of the first point above.


Without knowing how you are using the posted dictionaries its hard to tell if the dictionaries are the bottleneck or if their usage is flawed.

\$\endgroup\$
1
  • \$\begingroup\$ i dont thing you are right about Count property optimization. It's an old trick of .net when you loop over array and use it's Length property - VM enables optimization and don't check index out of range on each access operation. If you do this using count field - it will be much slower. In addition - i debugged release code version using debug and didn't see in assembler code any call because jit compiler inlined ContainsKeyInternal into Count property. I wanted to show assembler code in comment but i cant because of comment length restriction :( sorry \$\endgroup\$ Commented Mar 27, 2017 at 18:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.