Igor Ostrovsky Blogging

Little LINQ puzzle

IEnumerable<int> empty = Enumerable.Empty<int>();
for (int i = 0; i < 40; i++)
{
    empty = empty.Concat(empty);
}
int[] emptyArray = empty.ToArray();

Friday 12 Sep 2008 | Igor Ostrovsky | Uncategorized

6 Responses to “Little LINQ puzzle”

1. on 12 Sep 2008 at 7:49 am 1beefarino

   Hi Igor!

   Concat() execution is deferred, so each call to Concat() returns a decorated IEnumerable instance; by Concat()ing the collection to itself 40 times, you end up with a tree of (I believe) 40! unique collection instances that must be traversed during the call to ToArray().

   jimbo

2. on 12 Sep 2008 at 9:24 am 2Pete

   Actually it doesn’t hang on the last line. The problem is with the Concat operation. If you decrease the for-loop iteration to something smaller (like 10) the code snippet will execute and emptyArray will be the equivalent to Enumerable.Empty or {int[0]}. The Concat operations slows things down exponentially and in the end you’ll end up with an OutOfMemoryException. Why ? I don’t have a clue…yet

3. on 12 Sep 2008 at 9:27 am 3Pete

   Instead of

   empty = empty.Concat(empty)

   just have

   empty.Concat(empty)

   it will run fine. Still trying to figure out why…

4. on 12 Sep 2008 at 9:37 am 4Pete

   Got it; I think…

   Enumerable.Concat has a parameter (first) which is the first sequence to concatinate which is itself. Because of this you get massive recursion that’s why it appears to hang. Am I correct ?

5. on 15 Sep 2008 at 7:51 am 5Joe White

   It doesn’t hang; it just takes an unreasonably long time.

   You end up with a “tree” with only 41 distinct node objects (the original empty Enumerable, plus 40 Concat decorators), which is why there’s no risk of an OutOfMemoryException. But the second node down serves double duty — it’s both the left and the right child of the top node. The third node down serves quadruple duty, the fourth 8x, the fifth 16x, etc.

   ToArray() has to traverse the entire tree, and it’s not visiting 40 objects — it’s visiting all 2,199,023,255,551 nodes in the tree (2^41 - 1). Even a “for” loop with that many iterations will take longer than most of us are willing to wait.

   It’s not the 40 layers of decorators that kill you, it’s the fact that every single layer (except the first) is visited more than once, which takes you into exponential time.

6. on 16 Sep 2008 at 4:39 pm 6Igor Ostrovsky

   Those are some good answers. Joe, yours is particularly accurate.

   Now, what about the other puzzle? Still no answer there.

Leave a Reply