title: Performance of reverse-mapping collection
body: <p>I have a collection of objects where every object has a unique string Id, and any other object can contain entirely arbitrary (many-to-one) "Links" to another object.  I also want to be able to generate a "usage map" which is the reverse index -- given any one object, which other objects are linked either directly to it or to a child of it?  (Here a "child" is defined as any object with a matching prefix Id, as the Id is a dotted-path notation.)</p>
  
  <p>So <code>Baz.Boz</code> might be one object that links to <code>Foo.Bar</code> -- the usage map should then reflect that both <code>Foo</code> and <code>Foo.Bar</code> (but not <code>Foo.Bob</code>) are used by <code>Baz.Boz</code>.</p>
  
  <p>This is the code used to calculate the usage map:</p>
  
  <pre><code>// builds Id =&gt; links that link to Id or one of Id's children (by prefix)
  public IDictionary&lt;string, IList&lt;Link&gt;&gt; CalculateUsageMap()
  {
      var all = All();
      var links = all.Values
          .SelectMany(o =&gt; o.Links ?? Enumerable.Empty&lt;Link&gt;())
          .ToList();
      return all.Keys.ToDictionary(i =&gt; i, i =&gt; links.Where(k =&gt; IsLinkedTo(k, i)).ToList());
      // this last line is very slow
  }
  
  private static bool IsLinkedTo(Link link, string candidateId)
  {
      return !string.IsNullOrEmpty(link.TargetId)
          &amp;&amp; !string.IsNullOrEmpty(candidateId)
          &amp;&amp; link.TargetId.StartsWith(candidateId, StringComparison.Ordinal);
  }
  </code></pre>
  
  <p>This is the supporting structure behind it:</p>
  
  <pre><code>public interface ILinkable
  {
      string Id { get; }
      IEnumerable&lt;ILinkable&gt; Children { get; }
      IEnumerable&lt;Link&gt; Links { get; }
  }
  
  public class Link
  {
      public string Name { get; }
      public ILinkable Source { get; } // our immediate owner
      public string TargetId { get; }
      // plus constructors etc that's irrelevant at present
  }
  
  public ILinkable Root { get; }
  
  public IDictionary&lt;string, ILinkable&gt; All()
  {
      var tree = new Dictionary&lt;string, ILinkable&gt;();
      AddWithDescendants(tree, Root);
      return tree;
  }
  
  private static void AddWithDescendants(IDictionary&lt;string, ILinkable&gt; tree, ILinkable obj)
  {
      tree.Add(obj.Id, obj);
  
      foreach (var child in obj.Children ?? Enumerable.Empty&lt;ILinkable&gt;())
      {
          AddWithDescendants(tree, child);
      }
  }
  </code></pre>
  
  <p>This works, but in a tree with ~14k objects and ~3k links (producing ~20k usages) this takes ~5s to generate, which is longer than I'd like.  (I've checked and <code>All()</code> and calculating <code>links</code> takes basically no time; it's all being spent inside <code>ToDictionary</code>.)</p>
  
  <p><strong>Is there some way to improve performance of this line?</strong>  My first thought was using something like <code>GroupJoin</code>, but since we're "joining" on prefix-equality rather than actual equality that doesn't really work.  I would prefer to keep this in pure code, not involving a database.</p>
  
  <p>(I did attempt to write a custom equality comparer for <code>GroupJoin</code> but this ended up being both slower and producing the wrong results, with only ~7k of usage output.  And it's dubious anyway since this is an asymmetric match, while equality comparers assume symmetry.)</p>