CompiledDictionary

Compiled Dictionary

I recently came across an excellent blog post Compiling a dictionary into a switch expression, where the author proposed an idea to improve the lookup speed of a Dictionary. In short, the approach involves precomputing the hash values of each Key in the dictionary and generating a switch statement to directly return the corresponding value. This eliminates some of the overhead in the dictionary lookup process, thereby improving efficiency. Here’s a simplified version of the pseudocode:

public TValue Lookup(TKey key) => key.GetHashCode() switch
{
  // No hash collision, 1-to-1 mapping  
  9254 => value1,
  -101 => value2,

  // Hash collision, further comparison of the actual keys  
  777 => key switch
  {
      key3 => value3,
      key4 => value4
  },

  // ...

  // Not found  
  _ => throw new KeyNotFoundException(key.ToString())
};

The actual test results were impressive, especially in .Net Framework, where the compiled dictionary was more than twice as fast as a standard dictionary lookup. We know that Microsoft has made significant performance improvements since .Net Core, and in .Net 9, dictionary lookups are already much faster than in .Net Framework. However, even in .Net 9, this method still provides a noticeable performance boost. Below are the benchmark results for dictionaries containing 2000 and 4000 key-value pairs, respectively:

.Net Framework Test Results

.Net 9 Test Results

A Dictionary supports three main lookup operations:

Method	Throws Exception?	Retrieves Value?	Benchmark Name
`this[]`	Yes	Yes	Standard/Compiled dictionary
`TryGetValue`	No	Yes	Standard/Compiled TryGetValue
`ContainsKey`	No	No	Standard/Compiled ContainsKey

The logic for these three methods is fundamentally the same, with the following differences:

Default behavior (when the key is not found):
- this[] throws an exception, while the other two do not.
Behavior on successful lookup:
- this[] directly returns the value.
- TryGetValue returns both the value and a boolean indicating success.
- ContainsKey only returns a boolean indicating whether the key exists.

The original blog post only demonstrated the this[] approach. I refactored the code to let all three methods share the same underlying logic. As shown in the benchmark results, the performance improvements are consistent:

private SwitchExpression CreateSwitchBody(Expression keyParameter, Expression defaultCase, Func<TValue, Expression> switchCaseBodyFunc)
{
  // Expression to compute the hash code of the key  
  var keyGetHashCodeCall = Call(keyParameter, typeof(object).GetMethod(nameof(GetHashCode))!);
  
  return Switch(keyGetHashCodeCall, defaultCase, null,
    inner
      .GroupBy(p => p.Key.GetHashCode())
      .Select(g =>
      {
        if (g.Count() == 1)
        {
          return CreateSwitchCase(g.Key, g.Single().Value);
        }

        return SwitchCase(
          Switch(
            keyParameter,
            defaultCase,
            null,
            g.Select(p => CreateSwitchCase(p.Key, p.Value))
          ),
          Constant(g.Key)
        );
      })
  );

  SwitchCase CreateSwitchCase(object key, TValue value) => SwitchCase(switchCaseBodyFunc(value), Constant(key));
}

All three methods call CreateSwitchBody:

private void CompileLookup()
{
  var keyParameter = Parameter(typeof(TKey));
  var defaultCase = ThrowException();
  var body = CreateSwitchBody(keyParameter, defaultCase, v => Constant(v, TypeValue));
  var lambda = Lambda<Func<TKey, TValue>>(body, keyParameter);
  var str = lambda.ToReadableString();
  _lookup = lambda.Compile();
  return;

  UnaryExpression ThrowException()
  {
    var keyToStringCall = Call(keyParameter, typeof(object).GetMethod(nameof(ToString))!);
    var exceptionCtor = typeof(KeyNotFoundException).GetConstructor([typeof(string)]);
    var unaryExpression = Throw(New(exceptionCtor!, keyToStringCall), TypeValue);
    return unaryExpression;
  }
}

private void CompileTryGetValue()
{
  var keyParameter = Parameter(typeof(TKey));
  var valueParameter = Parameter(TypeValue.MakeByRefType());
  var defaultCase = ReturnValueBlock(false, default!);
  var body = CreateSwitchBody(keyParameter, defaultCase, v => ReturnValueBlock(true, v));
  var lambda = Lambda<TryGetValueDelegate>(body, keyParameter, valueParameter);
  _tryGetValue = lambda.Compile();
  return;

  BlockExpression ReturnValueBlock(bool found, TValue value)
  {
    return Block(Assign(valueParameter, Constant(value, TypeValue)), Constant(found));
  }
}

private void CompileContainsKey()
{
  var keyParameter = Parameter(typeof(TKey));
  var defaultCase = ReturnValue(false);
  var body = CreateSwitchBody(keyParameter, defaultCase, _ => ReturnValue(true));
  var lambda = Lambda<Func<TKey, bool>>(body, keyParameter);
  _containsKey = lambda.Compile();
  return;

  Expression ReturnValue(bool found) => Constant(found, typeof(bool));
}

Further Thoughts

After implementing this, I recalled a well-known optimization tip: when dealing with a small number of values, iterating over an array is actually faster than using a dictionary. This is why some implementations dynamically switch between arrays and dictionaries based on the data size—arrays are more memory-efficient and, in some cases, faster. However, with the compiled dictionary approach, the situation changes.

Below are the lookup performance comparisons in .Net Framework for datasets ranging from 1 to 7 entries. The results show that for 5 or fewer entries, array iteration is indeed faster, but beyond that, the standard dictionary wins. However, the compiled dictionary consistently outperforms both.

In .Net 9, array iteration remains faster for up to 8 entries, but the compiled dictionary is still the fastest in all cases.

Since dictionaries are typically populated once and then repeatedly queried, the overhead of compiling the switch expression is negligible. This means we can achieve immediate performance gains without the need for dynamic switching between arrays and dictionaries—a win-win scenario.

For the full implementation, visit GitHub.

Compiled Dictionary

最近读到一篇很棒的博客Compiling a dictionary into a switch expression，作者提供了一个提高Dictionary查询速度的思路。简单来说是把字典里面每个Key的哈希值算出来，生成一个switch语句直接返回相应的值，这样就省去了字典查询过程中一些不必要的开销从而提高效率。伪代码如下：

public TValue Lookup(TKey key) => key.GetHashCode() switch
{
  // 没有哈希冲突，1对1返回响应值
  9254 => value1,
  -101 => value2,

  // 哈希值冲突，进而比较每个值本身
  777 => key switch
  {
      key3 => value3,
      key4 => value4
  },

  // ...

  // Not found
  _ => throw new KeyNotFoundException(key.ToString())
};

实测下来效果非常好，尤其是在.Net Framework中，速度比字典直接查询快了一倍还多。我们知道从.Net Core开始微软在性能上下了不少功夫，.Net 9中字典查询已经比.Net Framework快了不少，但应用上这个方法后性能仍旧有提升。下面是当字典中分别有2000和4000对键值时的性能对比：

.Net Framework测试结果

.Net9测试结果

Dictionary的查询操作有三个：

方法	是否抛异常	是否取值	测试名
`this[]`	是	是	Standard/Compiled dictionary
`TryGetValue`	否	是	Standard/Compiled TryGetValue
`ContainsKey`	否	否	Standard/Compiled ContainsKey

这三个方法的逻辑其实是统一的，不同之处在于：

默认行为不同，即查询失败时的操作不同。this[]会抛异常而且另外两个不会
查询成功的行为不同。this[]直接返回值，TryGetValue不仅返回值还返回查询成功与否，ContainsKey则只返回查询成功与否

原博客只用this[]举例，我把代码重构了一下，让这三个方法共用同一套逻辑，如上性能测试的结果所示，性能提升幅度是一致的：

private SwitchExpression CreateSwitchBody(Expression keyParameter, Expression defaultCase, Func<TValue, Expression> switchCaseBodyFunc)
{
  // 计算Key哈希值的表达式
  var keyGetHashCodeCall = Call(keyParameter, typeof(object).GetMethod(nameof(GetHashCode))!);
  
  return Switch(keyGetHashCodeCall, defaultCase, null,
    inner
      .GroupBy(p => p.Key.GetHashCode())
      .Select(g =>
      {
        if (g.Count() == 1)
        {
          return CreateSwitchCase(g.Key, g.Single().Value);
        }

        return SwitchCase(
          Switch(
            keyParameter,
            defaultCase,
            null,
            g.Select(p => CreateSwitchCase(p.Key, p.Value))
          ),
          Constant(g.Key)
        );
      })
  );

  SwitchCase CreateSwitchCase(object key, TValue value) => SwitchCase(switchCaseBodyFunc(value), Constant(key));
}

三个方法的实现都调用了CreateSwitchBody方法：

private void CompileLookup()
{
  var keyParameter = Parameter(typeof(TKey));
  var defaultCase = ThrowException();
  var body = CreateSwitchBody(keyParameter, defaultCase, v => Constant(v, TypeValue));
  var lambda = Lambda<Func<TKey, TValue>>(body, keyParameter);
  var str = lambda.ToReadableString();
  _lookup = lambda.Compile();
  return;

  UnaryExpression ThrowException()
  {
    var keyToStringCall = Call(keyParameter, typeof(object).GetMethod(nameof(ToString))!);
    var exceptionCtor = typeof(KeyNotFoundException).GetConstructor([typeof(string)]);
    var unaryExpression = Throw(New(exceptionCtor!, keyToStringCall), TypeValue);
    return unaryExpression;
  }
}

private void CompileTryGetValue()
{
  var keyParameter = Parameter(typeof(TKey));
  var valueParameter = Parameter(TypeValue.MakeByRefType());
  var defaultCase = ReturnValueBlock(false, default!);
  var body = CreateSwitchBody(keyParameter, defaultCase, v => ReturnValueBlock(true, v));
  var lambda = Lambda<TryGetValueDelegate>(body, keyParameter, valueParameter);
  _tryGetValue = lambda.Compile();
  return;

  BlockExpression ReturnValueBlock(bool found, TValue value)
  {
    return Block(Assign(valueParameter, Constant(value, TypeValue)), Constant(found));
  }
}

private void CompileContainsKey()
{
  var keyParameter = Parameter(typeof(TKey));
  var defaultCase = ReturnValue(false);
  var body = CreateSwitchBody(keyParameter, defaultCase, _ => ReturnValue(true));
  var lambda = Lambda<Func<TKey, bool>>(body, keyParameter);
  _containsKey = lambda.Compile();
  return;

  Expression ReturnValue(bool found) => Constant(found, typeof(bool));
}

扩展思考

代码写完后我又想起一个著名的说法：当只有少数几个值的时候，直接用数组保存并轮训数组其实比字典更快。因此有时候我们会实现一些复杂的逻辑来根据数据量动态切换选择数组或者字典来存储。数组本身更省内存，如果更快的话何乐而不为？不过有了本文的方法，情况不一样了。

下面.Net Framework中数据量分别为1-7的情况下查询性能的对比。可以看到5个数据及以下确实是数组更快一些，超过5个时字典查询胜出。但是Compiled Dictionary性能则始终碾压另外两个。

.Net9中数组查询在8个及以下比字典快，但Compiled Dictionary仍然更快。

考虑到大多数情况下字典数据塞完之后几乎都是查询操作，所以无需频繁重新生成表达式，在这种情况下使用Compiled Dictionary可以带来就地性能提升，也用不着根据数据量动态切换来选择数组或者字典了，算得上一举两得。

具体实现请移步github

Compiled Dictionary

Further Thoughts

Compiled Dictionary

扩展思考

CATALOG

FEATURED TAGS

FRIENDS