Performance Optimization of n:1-mapping I am filtering a List (childList) based on the contents of another List (parentList).

The parentList can contain 0-n entities where items of the childList are referenced by an ID (btw. ID is in this case a string, you could also call it "Name" or whatever you like). I want to filter the childList in a way that the result is all elements that have at least one entry in the parentList.

The obvious solution is:

List&lt;childItem&gt; resultList = new List&lt;childItem&gt;();    

foreach(var childItem in childList){
    foreach(var parentItem in parentList){
        if(childItem.ID.Equals(parentItem.ChildID,StringComparison.InvariantCultureIgnoreCase){
            resultList.Add(childItem); //found entity
            break; // search for next childItem
        } 
}


What I have done by now is:

// Group by childID and create List with all relevant IDs
var groupedParentList = parentList.AsParallel().GroupBy(p =&gt; p.ChildID).Select(group =&gt; group.First()).ToList();

// Filter childList on groupedParentList
var result = childList.AsParallel().Where(child =&gt; groupedParentList.AsParallel().Count(parent =&gt; parent.childID.Equals(child.ID, StringComparison.InvariantCultureIgnoreCase)) &gt; 0).ToList();


But it's lasting rather long. The parentList contains about 75k entries and the childList about 4.5k entries. I just can't believe it actually takes time - imo this should be done in almost no time?

Maybe I am on the wrong track or am I missing some obvious performance-stopper?

Btw.: I have chosen the names parent- and childList just as an example. It's actaully no parent-child-relation. 

Additional Question: Could it be faster to direcly check if the parentList contains the childList-Item? Something a lá:

var test = childList.RemoveWhere(child =&gt; !parentList.Contains(item =&gt; item.childID.Equals(child.ID));


So I would just skip the grouping? Any suggestions/ideas?
First red flag; you're using Count(predicate) &gt; 0. The Count() overload that takes a predicate must iterate over all elements of the parent enumerable to determine the correct count, and you're telling it to do so for each element of the child list. You simply want to know if at least one of those elements matches; for that, the Any() overload which accepts the same parameter will be faster, because it will quit as soon as it finds the first element that matches (unfortunately the worst-case of a match not existing will still require a full scan of the enumerable).

You're also parallelizing parallelization. While parallel is good, threads waiting on threads waiting on threads can easily result in an algorithm that is bound by the ThreadPool's ability to spin up new threads (the default is a 250ms wait for each new thread after a predetermined number of "readily-available" threads have been scheduled). So, after creating, let's say 10 threads for this algorithm, most of which will be waiting on sub-threads, the ThreadPool will only create four new threads per second. Let's say the TPL begind the PLinq library thinks that one thread per 100 elements of both collections is necessary. On a collection of 4500 elements, for each of which a comparison of 4500 more elements is necessary, the ThreadPool could schedule two thousand worker threads to execute. After 10 of them are created near-instantaneously, only four more per second will be created as long as at least 10 are running, meaning this algorithm will take up to 500 seconds just to schedule all the necessary threads. The more "instantaneous" threads you tell the ThreadPool to spin up before queueing them, the more cache-thrashing you'll do forcing the CPU to juggle all these threads.

First step to improving this: Instead of grouping, select a list of distinct child IDs from the parent list. This process will produce strings instead of groups of larger ParentItems, which should hopefully reduce the amount of "heap-thrashing" required to generate the groups only to reduce it down to a much smaller collection. You only ever need the child IDs from the parent list anyway.

// Group by childID and create List with all relevant IDs
var childrenOfParents = parentList.AsParallel()
   .Select(p =&gt; p.childId)
   .Distinct()
   .OrderBy(x=&gt;x)
   .ToList();


Then, filter the child list based on the ID being in the derived list of child IDs:

// Filter childList on groupedParentList
var result = childList.AsParallel()
   .Where(child =&gt; childrenOfParents
      .Any(cid=&gt;cid.Equals(child.ID, StringComparison.InvariantCultureIgnoreCase)))
   .ToList();


I do not know about the culture-specific comparison behavior, but if it's at all possible to compare the strings verbatim (even ToLower()ed), it would likely be preferable performance-wise.

Other things that may help include building custom extension methods that make certain assumptions:


Naive grouping or deduping (Distinct()) of an enumerable is an N2-complexity operation (compare each element to a list of already-processed elements and remove if it exists). This is the least efficient part of the first query. Deduping of a list sorted by the same projection that must be de-duped is linear (compare each element to the previous one and remove if equal). You will be able to dedupe the list of child IDs more efficiently than PLinq's default implementation if you know the list is sorted by the same projection (in this case the identity projection) that you must dedupe.

public IEnumerable&lt;TObj&gt; SortAndDedupe&lt;TObj, TProj&gt;(this IEnumerable&lt;TObj&gt; input, Func&lt;TObj, TProj&gt; projection)
{
    sortedInput = input.OrderBy(projection);

    TProj last;
    var init = false; //default(T) might be valid
    foreach(var element in sortedInput)
    {
       if(!init || !projection(element).Equals(last))
       {
          init = true;
          last = projection(element);
          yield return element;
       }
    }
}

...

// Your first query is now an NlogN operation
var childrenOfParents = parentList.AsParallel()
   .Select(p =&gt; p.childId)
   .SortAndDedupe(s=&gt;s)
   .ToList();

Naive searching for elements that match a predicate is linear, which makes the second query N2-complexity. In your case, with a sorted list of childID strings being searched for a value that is equal to a passed projection, you can use a logarithmic binary search:

public bool IsInSortedList(this T toFind, List&lt;T&gt; collection)
    where T: IComparable&lt;T&gt;
{
    var max = collection.Count - 1;
    var min = 0;
    var idx = (max-min)/2;

    while(max &gt;= min)
    {
       if(collection[idx].CompareTo(toFind) == 0) return true;
       else if(collection[idx].CompareTo(toFind) &lt; 0) //search right
          min = idx+1;
       else if(collection[idx].CompareTo(toFind) &gt; 0) //search left
          max = idx-1;

       idx = (max-min)/2 + min;            
    }

    return false;       
}

...

//This query is now an NlogN as well
var result = childList.AsParallel()
  .Where(child =&gt; child.IsInSortedList(childrenOfParents)
  .ToList();