LINQ and loops

by Matt 28. April 2010 09:52

Well, gosh. What a busy few months. What started as a bit of spit and polish to a website has turned into a huge rewrite and a great opportunity to learn and play with MVC(2), the Spark view engine, Lucene.net and NHibernate. But more on those some other time. Today, I’m interested in a performance problem that wasn’t what I was expecting it to be.

One core scenario of this website is that users can watch video files. We don’t want to allow them to view just anything, so we grant them access to a subset of the videos. Which means we have the following requirement: what programmes does the user have access to watch?

This is calculated like so: get the video access tokens for the user. Map each token to an episode. Strip out episodes which don’t have videos available. Retrieve the programmes for all viewable episodes.

For better or worse, this touches 5 tables across 3 separate databases.

We wrote a cache.

And you know what? It works great. The site is fast, the data is readily available, everybody is happy.

Except for one user.

We have a demo user that is granted access to a large number of episodes in a large number of programmes, ready to be used at conferences and other events.

This user killed the site.

Once the data was in the cache, everything was great. But it took 5 minutes to get into the cache. And killed the site while it was doing so.

I was expecting some trouble with this user – they didn’t work well on the existing site, and it’s obvious that we’re doing too much database activity. So I fired up the wonderful NHProf to see exactly what was going wrong and immediately proved myself wrong. All the data was being retrieved with a minimum amount of fuss and sql statements and round trips to the database. It took 5 seconds.

Now, we are definitely doing too much with the database here. We really could do with denormalising some of the data, using less databases and pulling back ids instead of unused entities. But it still only took 5 seconds. As an edge case populating a cache for a user only used by staff at conferences, 5 seconds is pretty much ok.

So what was happening for the remaining 4 minutes and 55 seconds?

The title of the post might help. The heart of this little process was a LINQ to objects query that joined up the lists from the various databases to create the final list of programmes, episodes and tokens that we could cache and present to the user. It went something like this:

var tokens = GetTokens();
var episodes = GetEpisodes(tokens);
var availableEpisodes = GetAvailableEpisodes(episodes);
from p in GetProgrammes(availableEpisodes)
select new ProgrammesWithTokens(p.Id, p.Title, GetTokensForProgramme(p, episodes, tokens))

where GetTokensForProgramme was defined like:

from t in tokens.OrderByDescending(x => x.GrantedDate)
from e in episodes
where e.OpaqueStringId == t.OpaqueStringId 
   && e.EpisodeNumber == t.EpisodeNumber 
   && p.Episodes.Contains(e)
select t

Now, there are two glaring issues going on here: We’re always ordering the tokens list – we could do that once before anything else. Similarly, we could do something about the p.Episodes.Contains(e) which isn’t going to be very quick.

But that’s small fry. Where’s the real problem?

It took me a little while to realise that what looks deceptively like nice, declarative, friendly LINQ, is in fact (of course) nested loops. Three deep. This simple bit of data collation is O(n * m * p).

I didn’t mention data size before. Turns out it’s not really that large. The demo user has about 1600 tokens, for 1500 available episodes for about 300 programmes.

Not much, actually.

But when you count the looping, this gives us 300 * 1600 * 1500 = 720,000,000 iterations.

Seven hundred and twenty MILLION iterations. That’s 720 MILLION string comparisons, and 720 MILLION list traversals for the Contains calls. It’s also 299 unnecessary ordering of the tokens list.

That’s where my 5 minutes was going.

Rewriting this as a bunch of lookups has reduced this bottleneck to essentially the time it takes to read from the database – about 5 seconds.

So the moral of the story is simple. LINQ is nice. It’s lovely. But when you’re doing multiple from statements, don’t forget it’s now doing nested loops.

That can really hurt.

Tags:

Comments (27) -

cyclerack
cyclerack
3/4/2011 9:15:25 AM #

Fair-and-square point you produce in sticklebackplastic com . Interesting to study the post and supplemental thoughts verbalised by writers on this and different websites. A post a day keeps the remarks arriving.

Reply

LAURENCE  Debora
LAURENCE Debora
5/22/2011 4:56:18 AM #

Recherche thématique sur plusieurs thèmes, c'est sukoga.com, moteur.

Reply

LAURENCE  Debora
LAURENCE Debora
5/27/2011 8:32:06 AM #

Liste d'annuaires détaillées pour faciliter le référencement, Créez votre propre article.

Reply

New york yankees Baseball cap
New york yankees Baseball cap
6/19/2011 3:06:14 PM #


I've learned a lot from your blog here,Keep on going,I will keep an eye on it,One more thing

Reply

best suv 2010
best suv 2010
7/20/2011 10:25:08 PM #

Is it ok if I quote your article in my monthly newsletter? I would think this article suits my topic perfectly. Well ya, thanks for posting this article.

Reply

free i pad
free i pad
7/23/2011 1:16:13 PM #

I wonder if he cheated on her? I remember he cheated on his previous wife with JLO so it wouldn’t be surprising.

Reply

LAURENCE  Debora
LAURENCE Debora
7/27/2011 10:47:56 AM #

Bienvenue sur annuaires-gratuit.com.Des fonctionnalités inédites, nombreuses annuaires.

Reply

DEBORA Laurence
DEBORA Laurence
8/1/2011 8:34:55 AM #

Il ne vous reste plus qu' à créer votre propre annuaire, l'inscription est  gratuite .

Reply

garage automation
garage automation
8/5/2011 9:26:47 AM #

Very Interesting. Is there any more information on the topic?

Reply

DEBORA Laurence
DEBORA Laurence
8/8/2011 10:05:33 AM #

Vous pouvez configuré vos systèmes de paiement allopas sur annuaires-gratuit.com

Reply

DEBORA Laurence
DEBORA Laurence
8/9/2011 9:22:51 AM #

Remplissez les informations ci-dessous pour créer votre annuaire, annuaires-gratuit.com

Reply

DEBORA Laurence
DEBORA Laurence
8/9/2011 11:23:44 AM #

Remplissez les informations ci-dessous pour créer votre annuaire, annuaires-gratuit.com

Reply

DEBORA Laurence
DEBORA Laurence
8/9/2011 6:40:46 PM #

Recevoir la newsletter et les informations des partenaires de annuaires-gratuit.com

Reply

DEBORA Laurence
DEBORA Laurence
8/9/2011 7:46:01 PM #

Recevoir la newsletter et les informations des partenaires de annuaires-gratuit.com

Reply

DEBORA Laurence
DEBORA Laurence
8/9/2011 9:18:03 PM #

Recevoir la newsletter et les informations des partenaires de annuaires-gratuit.com

Reply

DEBORA Laurence
DEBORA Laurence
8/13/2011 4:20:03 AM #

Vendez aux enchères vos objets neuf.Vendre et acheter aux enchères sur sibeys.com,

Reply

DEBORA Laurence
DEBORA Laurence
8/13/2011 6:58:41 AM #

Vendez aux enchères vos objets neuf.Vendre et acheter aux enchères sur sibeys.com,

Reply

DEBORA Laurence
DEBORA Laurence
8/13/2011 10:59:20 AM #

Le système d'Enchère automatique sibeys.com, vendez aux enchères vos objets neuf.

Reply

Erought
Erought
8/29/2011 6:57:34 PM #

W. 442. An action <a href="http://www.drdreheadphones-sale.com/">dre headphones</a>had there been brought against the defendant on a covenant, <a href="http://www.drdreheadphones-sale.com/">dr dre headphones</a>that he would appear at any insurance office which the plaintiff might designate, <a href="http://www.topsunglassmall.com/">cheap oakleys</a>and answer all such questions as should be put to him with<a href="http://www.topsunglassmall.com/">ray ban sunglasses</a>regard to his health, in order that an insurance might be effected <a href="www.beatsbydrdre-headphones.com/">beats by dre</a>on his life, and would not afterwards do any act by which such insurance <a href="www.beatsbydrdre-headphones.com/">dr dre</a>should be vitiated. The declaration further averred, that the defendant <a href="www.beatsbydrdre-headphones.com/">beats by dr dre</a>had appeared and answered certain questions so put to him at the Rock <a href="http://www.ray-banlunette.com/">lunette ray ban</a>Life Insurance Company, and that the plaintiff had thereupon effected<a href="http://www.ray-banlunette.com/">ray ban aviator</a>an insurance with that Company, conditioned to be void in case the <a href="http://www.ray-banlunette.com/">ray ban wayfarer</a>defendant went beyond the limits of Europe, and then assigned as a <a href="http://www.canada-goosejakke.com/">canada goose</a>breach, that the defendant did go beyond the limits of Europe, but without any <a href="http://www.canada-goosejakke.com/">canada goose jakke</a>allegation of notice to him, either of the time and place of insurance, or of the condition <a href="http://www.canada-goosejakke.com/">canada goose jakker</a>which had thus been violated.

Reply

Wordfeud fusk och wordfeud hj&#228;lp
Wordfeud fusk och wordfeud hjälp
9/2/2011 9:02:47 AM #

Very Interesting. Is there any more information on the topic?

Reply

Andrew Cole
Andrew Cole United States
9/14/2011 3:32:13 AM #

Exceedingly educational many thanks, It looks like your subscribers would possibly want far more content similar to this continue the excellent effort.

Reply

cheat point blank
cheat point blank
10/7/2011 10:06:07 PM #

nice blog, I'll come back later, a useful post for me

Reply

Stephen
Stephen
10/17/2011 3:55:31 PM #

Thanks  for this super site.  Seems like there\\\'s always something new I learn even after being in the field for 10 years.

Reply

how to get rid of a cold sore
how to get rid of a cold sore
11/7/2011 3:04:57 PM #

Even though if McCain won, I wouldn’t really care because he’s also a pretty good president too. Anyways, GO OBAMA!!!

Reply

Gabriel Jefferson
Gabriel Jefferson United States
11/8/2011 10:25:40 PM #

Truly enlightening thanks, I reckon your trusty readers could very well want even more articles along these lines maintain the great content.

Reply

ixchel price
ixchel price
11/17/2011 10:07:23 PM #

You must take life the way it comes at you and make the best of it.-Yann Martel

Reply

Sport guy
Sport guy
11/22/2011 9:44:53 AM #

Thanks for info. Is there more info on this subject elsewhere?

Reply

Add comment

biuquote
  • Comment
  • Preview
Loading

Month List

RecentComments

Comment RSS