# Optimizing List<string> performance

I have a List<string> 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<string> GetProducts()
{
var cached = HttpContext.Current.Cache["MyApp-Products"];
if (cached == null)
{
UpdateCache();
return GetProducts();
}
return ((List<string>)cached);
}


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

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


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?

• Were you aware that the List<T> type that you are using as backend is not thread safe? You should really take that into account when attempting to use it in a multi-threaded environment such as ASP.NET. – Darin Dimitrov Mar 7 '12 at 17:13
• Not sure I'm too keen on the recursion there, even if it should only be a single loop-around. I'd replace return GetProducts(); with the (also-repeat, might want to DRY it out) cached = HttpContext.Current.Cache["MyApp-Products"];. – Jesse C. Slicer Mar 7 '12 at 17:39
• sounds like the perfect use for a en.wikipedia.org/wiki/Directed_acyclic_word_graph – jk. Mar 7 '12 at 22:06
• A public static List<T> is threadsafe. Instance members are not guaranteed to be. But either way, as long as the collection is not modified during runtime, it does not matter. msdn.microsoft.com/en-us/library/6sh2ey19.aspx (see Thread Safety near bottom above Community Content) – Lars-Erik Mar 8 '12 at 13:07
• @Lars-Erik: You read the specification wrong. The fact that static members of the class (all zero of them) are thread safe doesn't mean that a static variable holding an instance of the class is thread safe. Neither the variable nor the class instance is thread safe. – Guffa Mar 12 '12 at 9:35

Marc has the best answer but a trivial step in the right direciton would be to drop all the expensive ToUpper calls. Just replace .Where(s => s.ToUpper().StartsWith(term.ToUpper())) with .Where(s => s.StartsWith(term, StringComparison.InvariantCultureIgnoreCase)

• Thanks! The StringComparison.InvariantCultureIgnoreCase actually helped significantly. – Paul Mar 7 '12 at 17:54
• How much exactly did it help? 10%? 50%? 99%? – Andrei Rînea Jun 4 '12 at 18:49

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.

• The binary search will get you to a match quickly, not necessarily the first. You'd have to then back up until you find the first match and proceed forward from there. On average I would expect this to be much faster (than iterating through a pre-sorted set), but there are some cases where it could be slower. For example, the case where you end up taking the first 5 elements out of a very large set. – tvanfosson Mar 8 '12 at 0:54
• @tvanfosson: After finding a match, you just treat the match as "too large" and continue the binary search. After the binary search has completed fully (i.e., after all log_2(n) steps), you know exactly where the first match is located. In other words, instead of searching for "prefix.*", you search just for "prefix". If you found "prefix", you know that this is the first element (since "prefix<whatever>" is greater). If you did not find "prefix", the end point of your binary search will be right before the first match (or not, if there is no match at all). – Heinzi Mar 8 '12 at 6:14
• @Heinzi you're assuming no duplicates, but I see what you mean. Go until you can't go any more, then check the next element (with special handling for the boundary cases). I'm not sure that's a lot faster than just finding one then going backwards (pushing on a stack) until you find the first non-match, popping the elements off the stack, then continuing at the point after the first match. It sounds more complicated. I suppose whether it's worth it depends on whether you expect a large or small number of matches and the size of the data set. – tvanfosson Mar 8 '12 at 13:10
• @tvanfosson: You are right, the average-case performance depends on the actual data. There is a difference in the worst-case time compexity, though: The binary-search-till-the-end approach requires at most O(log n), whereas the find-first-match-then-go-backwards method could have O(n). – Heinzi Mar 8 '12 at 14:12
• @Heinzi you're only considering the search phase, not the selection phase for your algorithm. Both algorithms are O(log n) + O(m) where m is the number of elements selected. If m is large then the difference in the constant on the second term is meaningful. – tvanfosson Mar 8 '12 at 14:47

I see that you order the list just to take 5 items. .OrderBy(s => s).Take(5). This is an O(n*log(n)) operation. Instead you can find the top most N items in an O(n) time. Here is an extension method TakeOrdered ( http://pastebin.com/NHDdrbYV ) I wrote some time ago just for this purpose .

 return Json(MyModel.GetProducts()
.Where(s => s.ToUpper().StartsWith(term.ToUpper()))
.TakeOrdered(5,s=>s)
.ToList<string>()
);


you can compare the performance results with a function like below

void PerformanceTest()
{
Stopwatch sw = new Stopwatch();

int N = 1000000;
int M = 10;

//JIT - Warm up
var seq1 = RandomSequence().Take(10).OrderBy(x => x).Take(M).ToArray();
var seq2 = RandomSequence().Take(10).TakeOrdered(M).ToArray();

sw.Start();
seq1 = RandomSequence().Take(N).OrderBy(x => x).Take(M).ToArray();
long t1 = sw.ElapsedMilliseconds;

sw.Restart();
seq2 = RandomSequence().Take(N).TakeOrdered(M).ToArray();
long t2 = sw.ElapsedMilliseconds;

for (int i = 0; i < seq1.Length; i++) Debug.Assert(seq1[i] == seq2[i]);

Console.WriteLine(t1 + " " + t2);
}

public IEnumerable<int> RandomSequence()
{
Random rnd = new Random(0);
while (true)
yield return rnd.Next();
}

N   |.OrderBy.Take     .TakeOrdered (in ms.)
-----+---------------------------
100K | 65               23
600K | 578              131
1M   | 1110             224
10M  | 16540            2243


And since It doesn't require all items to be kept in memory(for sorting), it consumes much less RAM

PS: TakeOrdered utilizes PriorityQueue of Lucene.Net internally http://lucene.apache.org/core/old_versioned_docs/versions/3_0_2/api/all/org/apache/lucene/util/PriorityQueue.html

Here is more explanation: How can I use Lucene's PriorityQueue when I don't know the max size at create time?

• I suspect that the use of the PriorityQueue makes this a non-stable sort. If you need to retain the relative ordering of items with "equal" prefixes, you probably shouldn't use this. – tvanfosson Mar 8 '12 at 13:15
• @tvanfosson If you'd taken a look to PerformanceTest(Assert code), you would see that it produces exactly the same output as OrderBy().Take() – L.B Mar 8 '12 at 13:30
• HeapSort is known to be a non-stable sort. If the priority queue implementation uses the same heap data structure (which the docs seem to suggest), then I would expect that it would have the same characteristics. Note that your test wouldn't detect this as there is no way to tell the difference between identical keys sorted in a different relative way. Attach a bit of unique data to each key and compare the order of those data elements and see if it's still in the same relative order. According to the docs, OrderBy uses a stable sort. – tvanfosson Mar 8 '12 at 13:39
• @tvanfosson Just forget the implemantation details for now: The idea is: You can find the Max(or Min) item of a List in O(n) time. if you extend this idea to m item(5 in the question), you can get top(or buttom) m items faster then sorting the list(just in one pass on the list + the cost of keeping 5 sorted items) – L.B Mar 8 '12 at 13:45
• I should also add that my comment wasn't directed at this particular question, but rather meant as a caveat for anyone who finds this later and is doing a key-based sort rather than sorting on the entire element. I just thought people should know that it's not a drop in replacement IF stability is important. – tvanfosson Mar 8 '12 at 14:54

You should put your strings in a database.

CREATE TABLE MyStrings
(
UpperCaseVersion varchar(8000)
StringValue varchar(8000)
PRIMARY KEY(UpperCaseVersion, StringValue)
)


Now it's threadsafe and quickly searchable (via the ordering from the primary key).

This solution will easily scale to 100 Million strings.

• Wouldn't the database I/O be slower than doing it in memory directly? – M.Babcock Mar 7 '12 at 17:23
• @M.Babcock no, the IO is not bad at all because of the clustered index seek. – David B Mar 7 '12 at 17:24
• Thanks for the tip, however for reasons beyond my control, I don't have the option of putting this in a db. – Paul Mar 7 '12 at 17:54
• We could rename CodeReview.Stackexchange.com to ProgrammingHumour.StackExchange.com :)))) – Andrei Rînea Jun 4 '12 at 18:55

You can get rid of the OrderBy statement and just make sure that you're filling the cache with an already sorted list - this will not save a lot of time, but should give some improvement.

You're asking the wrong question. You should be asking how to return the results quickly, not how to do it quickly with a particular data structure (a List).

There has been a lot of work done on exactly this sort of problem. I don't know a lot about this, but most likely some sort of tree structure will be much faster. Off the top of my head, I would look into a trie structure, which is a particular type of tree. (Yeah, the spelling is confusing.)

But I'm certainly no expert on this, and there might well be better options. You may want to post this question on a board with a more algorithmic focus.

If you're doing a StartsWith, perhaps you could break the list down into sub-lists, which obviously would take time, but it wouldn't be time that a human would wait on, since it could be done in the background. Then you could have a list for each letter of the alphabet (or break it down more for common letters and group a few common ones together, whatever works to break it down most evenly).

It wouldn't be 'elegant' to have a bunch of switch statements for each starting letter, but you could easily trim the list length from 600k to sort through to 60k or less, which would drastically reduce the time required to return results.

Alternatively, another option would be to change your datatype entirely. You could pre-sort your 600k list into Dictionary<string, List<string>> with the key being a string of the "StartsWith" you want to match. Then modify your code to simply pull the list stored as the value in the dictionary that matches your StartsWith. So, if you pre-sort to 2 letters, such as aa, ab, ac, ad, etc etc, once you match that, you get can then sort through a drastically smaller list. You could even pre-sort to 3 letters, such as aaa, aab, aac, and so on, which should result in needing to parse through a list of probably under 1000 elements for the longest list in the dictionary, with many being significantly smaller than 1000.

Using a 3-letter key would result in a dictionary with around 17k keys, which should yield acceptable performance. Accessing the dictionary value should be well under 1ms, then sorting through a list with under 1000 elements should be under 10ms, which should result in your function returning a value in more like 20ms rather than 2 seconds. The downside would be needing to break apart your 600k element list into 17,576 smaller sorted lists, then storing each of those in a dictionary with the appropriate "StartsWith" key. This, however, should only take a few seconds and can be done at initialization (and new entries for your list, which I assume isn't static, can be added to the dictionary rather than the jumbo-list, resulting in only needing to sort the list once, ever).

The best bet would be a database, but since that's not an option for you, the second-best thing would be simply reducing the length of your list from 600k down to something much much smaller.