Optimizing List performance I have a List&lt;string&gt; being stored in my cache with about 600K members.  I want this to act as the backend for an Ajax autocomplete box.  It's accessible through my model:

public static List&lt;string&gt; GetProducts()
{            
    var cached = HttpContext.Current.Cache["MyApp-Products"];
    if (cached == null)
    {
        UpdateCache();
        return GetProducts();
    }
    return ((List&lt;string&gt;)cached);
}


My ajax call uses this method to get it's data:

[HttpPost]
public JsonResult ProductSearch(string term)
{
    return Json(MyModel.GetProducts()
        .Where(s =&gt; s.ToUpper().StartsWith(term.ToUpper()))
        .OrderBy(s =&gt; s)
        .Take(5)
        .ToList&lt;string&gt;()
    );
}


The problem is, this Ajax call to ProductSearch() is waiting 2.09 seconds for a response. I'm doing the same with other objects in my model that have smaller list sizes and they respond in 35-125ms (which is acceptable).

So, I believe my performance issue is somewhere in accessing the list.  Is there a faster way to access this list besides the Linq code that I'm using, or just a better way to use Linq?
A starts-with should be easy enough to store in a pre-sorted list, ideally using a case-insensitive sort comparer rather than applying conversions each sort. Then: use binary search to find the first match, and keep moving forwards until it no longer matches. Should be pretty efficient.

If this needs to be edited in a shared multi-threaded context, be sure to use appropriate synchronization - presumably readers will be more common than writers, so a ReaderWriterLockSlim may be the best option.