[.NET]快快樂樂學LINQ系列前哨戰－延遲執行 (Deferred Execution)

2013-09-10

前言

講到 LINQ 的基礎，當然不能跳過「延遲執行」的特性。雖然小朱這一篇文章： [.NET] LINQ 的延遲執行 (Deferred Execution) 已經寫的很深入跟清楚了，這邊會在搭配一下 LINQ 中綜合的例子再解釋一下，LINQ 中的延遲執行究竟是怎麼一回事。

這邊將小朱文章中，最該留意的一句話 highlight 出來：LINQ 在呼叫 select 時，還沒有引發查詢動作，真正引發動作會是在 foreach，也就是 IEnumerator<T>.MoveNext()。

延遲執行的緣由

一般的情況，程式執行到哪一行，運算式應該就會立刻被執行，如下圖所示：

1. 當呼叫 Power(1) 的時候：

2. 會執行 Power() 中的 number * number：

3 .接下來會執行 Power(2) 的部份：

延遲執行的意義，就是等到實際驅動點時，才會執行原本該執行的程式。（感覺上有點像 delegate 跟呼叫 Invoke() 的情況。）

這邊來看一個實際的案例，如下圖所示，針對 people 先呼叫 Where() 再呼叫 Select()：

就一般上來說，跑完 names 這一行程式碼後，names 應該就有值了，其值為 Where(person => person.Age > 18) 也就是先把 people 中年紀大於 18 的 people 全抓出來。然後再透過 Select() 把這些「成人」的姓名全撈出來。就語意上來說，的確如此。不過實際上執行的順序就不完全如此了。

延遲執行的基礎－ Iterator

Iterator 的部份，可以參考一下前面的這篇文章： [.NET]快快樂樂學LINQ系列前哨戰－IEnumerable, IEnumerator, yield, Iterator 。這裡提到，當方法中使用 yield 關鍵字，C# 會自動將該 block 實作為 iterator 方式執行。來看一下簡單的例子，如下圖所示：

如上次文章所提到，其實 foreach(var item in items) 骨子裡就是：

呼叫 items.GetEnumerator() ，得到一個 IEnumerator ，這邊以 iterator 稱呼它。
呼叫 iterator.MoveNext() ，這時如果 IEnumerable 已經巡覽完畢，則會回傳 false 。如果還有下一個項目，則會回傳 true ，並將 current 的指標移到下一個 element 上。
接下來 yield return iterator.Current ，回到 foreach(var item in items)，這一次的迴圈（也就是 iterator）取得的 item ，就是剛剛 yield return 的 iterator.Current。

這也是為什麼當大家去偵錯 foreach(var item in items) ，用逐步執行偵錯時，游標會停在：

foreach: 代表要執行 foreach 骨子裡的內容。
items: 因為要呼叫 items 的 GetEnumerator() 。
in: 可以把它對應到呼叫 iterator 的 MoveNext()
var item: 當 MoveNext() 為 true ，代表還沒巡覽結束時，就會 yield return iterator.Current。
當MoveNext() 為 false 時，代表巡覽已經結束，沒有 yield return ， iterator block 結束，就會結束 foreach 迴圈。（不會停在 var item 上）

這也是為什麼， IEnumerable<T> 跟 IEnumerable 兩個介面，基本上只提供一個方法叫做 GetEnumerator() 就可以被 foreach 巡覽。

了解了 foreach 骨子裡是怎麼執行的時候，再回過頭來看小朱的文章，就會比較銜接的上。

回到我們剛剛的例子，var names = people.Where().Select(); 會怎麼執行？

這邊我先簡單示意一下，Where() 跟 Select() 裡面的基本概念程式碼。

Where() 的部份，其方法簽章為 public static IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate) 。而其目的為篩選出符合 predicate 條件的 elements。其內容大致上如下：


        static IEnumerable<TSource> Where<TSource>(this IEnumerable<TSource> source, Func<TSource, bool> predicate)
        {
            var iterator = source.GetEnumerator();
            while (iterator.MoveNext())
            {
                if (predicate(iterator.Current))
                {
                    yield return iterator.Current;
                }
            }
        }

Select() 的部份，其方法簽章為 public static IEnumerable<TResult> Select<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector)。而其目的為將 source 的每一個型別為 TSource 的 element 投影成 TResult 。

投影一詞為 projection ，不管英文或中文都挺難懂的，我喜歡把它視為 var y = f(x); 的感覺。傳入 x ，經過一個 function 之後回傳 y 。

其內容大致上如下：


        static IEnumerable<TResult> Select<TSource, TResult>(this IEnumerable<TSource> source, Func<TSource, TResult> selector)
        {
            var iterator = source.GetEnumerator();
            while (iterator.MoveNext())
            {
                yield return selector(iterator.Current);
            }
        }

了解了 Where() 與 Select() 基本運作的程式碼，接下來就回到我們的 context 端程式碼，如下所示：


        private static void Main(string[] args)
        {
            var people = GetPeople();
            var names = people
                .Where(person => person.Age > 18)
                .Select(person => person.Name);

            foreach (var name in names)
            {
                Console.WriteLine(name);
            }
        }

        private static IEnumerable<Person> GetPeople()
        {
            yield return new Person { Id = 1, Name = "John", Age = 36 };
            yield return new Person { Id = 2, Name = "Bill", Age = 6 };
            yield return new Person { Id = 3, Name = "Steve", Age = 23 };
        }

原本我們以為程式碼會如下圖這樣跑（事實上語意順序也是如此）

但有興趣的朋友可以拿上面的程式碼去跑跑看逐步偵錯的過程，會發現其實實際執行是倒著打的。

帶著各位看一下整個程式碼是怎麼執行的。

延遲執行的運作範例

讓我們從第一行開始進行偵錯，因為第一行的 GetPeople() 就有延遲執行了。

1. 第一行的 var people = GetPeople();
我們期望按下 F11 時，應該進去 GetPeople() 方法內容內的 yield return new Person ，如下圖所示：

但事實上按下 F11 時，是跳到下一行的 var names = people.Where().Select();

為什麼呢？因為 GetPeople() 中有 yield 關鍵字，因此 GetPeople() 實際執行的時間點，會在某個 iterator 的 MoveNext() 中，需要實際用到 GetPeople() 中的值時，才會執行。

2. 同樣的，一般來說，var names = people.Where().Select(); 我們會期望先呼叫 people 的 Where() 方法，再把 Where() 的結果，呼叫 Select() 的方法，取得最後的結果， assign 給 names。

但事實上，當我們按下 F11 時，並沒有進去 GetPeople(), Where() 或 Select() 裡面，而是直接跳到 foreach(var name in names) 這一行。

原因與 GetPeople() 沒有被馬上執行相同，因為 Where() 的方法內容中有 yield 關鍵字，而 Select() 方法內容中，也有 yield 關鍵字。因此這一行並不會馬上執行。到這個時候的 CodeMap 如下圖所示：

3. 重點來了，我們到了 foreach (var name in names) ，如同文章前半段針對 foreach 執行過程的說明，逐步偵錯的過程中，會先停在 foreach (var name in names) 的 in 上，如下圖所示：

接下來神奇的事發生了，按下 F11 之後，進去的是 Select() 的方法內容中！

為什麼會這樣？其實很簡單，這就只是個 iterator chain 的感覺而已。

foreach 的 in ，指的是 names 的 GetEnumerator() 後的 MoveNext() ， names 要 MoveNext() 就得從 names 來源開始執行，而 names 是怎麼來的？ names 是 people.Where().Select() 的結果而來的。

所以要巡覽 names ，得先知道 Select() 完的結果是什麼。因為延遲執行，所以 names 的 MoveNext() 時才會呼叫 Select() 。

那麼這時候 Select() 的 IEnumerable<TSource> source 怎麼來的？ Select() 方法中的 source 是 people.Where() 的結果。所以，當我們在 Select() 方法中，呼叫 source.GetEnumerator().MoveNext() 時，就會實際去執行 Where() 的方法內容，因為需要取得 Where() 的結果了。

再按下 F11 的時候，才會進入 Where() 的方法內容中。這時候 Where() 方法中的 source 是怎麼來的？是 people ，而 people 是怎麼來的呢？ people 是 GetPeople() 的結果。所以，當我們在 Where() 方法中，呼叫 source.GetEnumerator().MoveNext() 時，就會去執行 GetPeople() 的方法，因為我們需要 people 了。

在 Where() 的 iterator.MoveNext() 按下 F11 後，就會進入 GetPeoploe() 的 yield return new Person ，並取得第一個 Person。

這個時候，因為 GetPeople() 中有 yield return 一個 TSource 的 item ，因此在 Where() 中的 iterator.MoveNext() 會是 true 。且可以看到 iterator.Current 就是剛剛 GetPeople() yield return 的第一個 Person 。

接下來到 if (predicate(iterator.Current)) 這一行，移至定義時，才會跑到 context 端裡面的 predicate delegate 中，來驗證目前的 iterator.Current 有沒符合 Where() 的條件。

可以看到 Age 是 36 ，所以符合 >18 的條件，回到 Where() 方法中， yield return 這一個 Age > 18 的 Person 。

因為 Where() 有 yield return 一個 Person ，所以 call stack 回到 Select() 方法中，在 Select() 中的 iterator.MoveNext() 就會是 true 。

接下來 Select() 會 yield return selector(iterator.Current) ，因此 call stack 會回到 context 端 Select() 中的 selector delegate，取得 projection 後的結果。

最後 Select() yield return 給 foreach 的結果是 "John" 。

foreach 這邊其實機制是一模一樣的，foreach 的 MoveNext() 因為 Select() 有 yield return "John"，所以是 true ，接下來 var name 所取得的 name ，就會是剛剛整串延遲執行中，第一個 iterator 所回傳的結果："John"。

然後 foreach 迴圈就這樣直到 MoveNext() 為 false ，結束 foreach 迴圈。而 MoveNext() 為 false 的情況，就是沒有 yield return 且執行完畢，或是碰到 yield break ，這兩者都會結束 iterator block 。

所以，用 Visaul Studio 內建產生 Sequence Diagram 的工具，在延遲執行的機制底下，出來的圖會跟實際 runtime 執行的 call stack 不一樣唷。下方為自動產生的 Sequence Diagram。

而上面這張錯誤的 Sequence Diagram 也是大家普遍以為 LINQ 的執行方式。

以這例子來說，實際的執行順序，應該如下圖所示：

經過上面 trace 的過程，大家就不難發現，為什麼當第二筆 Bill 不符合 predicate 條件時，會直接再跟 GetPeople() 取得第三筆 Steven 。因為在 Where() 的 while (iterator.MoveNext()) 中，其 source 來源就是 GetPeople() 。

結論

經過這一篇文章解釋延遲執行，大家應該可以比較清楚地了解幾點：

yield 關鍵字會形成 iterator block ，並帶有延遲執行效果。
為什麼大部分的 LINQ to Objects API ，也就是 Enumerable static class 上，幾乎都是針對 IEnumerable<TSource> 進行擴充
為什麼 IEnumerable 可以被巡覽
IEnumerator 的作用
實際驅動延遲執行的時間點，就是在 IEnumerator<T>.MoveNext() 上。

這也是為什麼前哨戰要花這麼多篇幅跟時間，講解 foreach, IEnumerable, IEnumerator, Extension Method, delegate 跟 Lambda 了。

希望各位讀者下次再聽到別人說， LINQ 在實際執行時，是倒著打回去的，也可以會心一笑。

延伸議題

延遲執行基本上分成兩種，一種是 Lazy Evaluation ，另一種是 Eager Evaluation 。

Lazy Evaluation 舉例來說，如下圖所示，每一次 iterator block 才去執行相關的邏輯。

Eager Evaluation 則比較像下面這個例子，第一次就把值全都準備好，然後在每一次的 iterator 做 yield return：

這兩者對我們來說有什麼差異？

別忘了，只要講到 delegate 就有 closure 的問題，延遲執行的方式可能會影響 closure 的影響範圍。

而在 LINQ to Objects 中，哪一些情況會直接就執行呢？

轉型類型的 API ，如 ToList(), ToArray(), ToDictionary() 等等…
因為這個動作需要巡覽每一個 element 並進行轉型，所以會直接執行。
回傳值為單一值，如 Count(), Max(), Sum(), First(), Last() 等等…
因為要拿到彙總後的結果，或者說直接取得一個結果，自然不需要用到 yield return ，就不會有延遲執行了。

感謝

感謝同事小林與 Titan 一起設計 training 的教材！

範例下載：DeferredExecutionSample.zip

blog 與課程更新內容，請前往新站位置：http://tdd.best/

回首頁

In 91

擁有熱血魂，熱衷敏捷開發相關的點火師，專門點燃其他人內心的火種