Biến vòng lặp foreach trên IEnumerable thành không cấp phát bộ nhớ (allocation-free) bằng reflection và dynamic methods

Trong bài viết này, tôi mô tả một kỹ thuật để giảm việc cấp phát bộ nhớ khi gọi foreach trên một IEnumerable<T>. Kỹ thuật này đã được mô tả và sử dụng trước đây bởi những người khác, nhưng gần đây tôi đã tối ưu một số đoạn mã trong công việc hàng ngày khi làm việc trên .NET SDK tại Datadog và đã dùng kỹ thuật này, nên tôi quyết định giải thích chi tiết hơn về nó.

Bối cảnh: khi nào foreach cấp phát bộ nhớ

foreach là một trong những pattern được dùng phổ biến nhất trong C#; nó được sử dụng ở khắp mọi nơi. Một tìm kiếm nhanh và thô sơ trong kho lưu trữ dotnet/runtime cho thấy có tới 3,9 nghìn trường hợp! Phần lớn các trường hợp đó là duyệt các kiểu dựng sẵn từ thư viện lớp cơ sở (BCL) của .NET, chẳng hạn như List<T> và mảng, nhưng bạn cũng có thể dễ dàng foreach trên các kiểu tùy chỉnh của riêng mình.

Điều thú vị là cách mà hầu hết mọi người nghĩ hoặc được dạy về foreach là bạn cần triển khai IEnumerable (hoặc IEnumerable<T>), rồi sau đó bạn có thể duyệt collection. Điều này đúng, nhưng thực ra có một điểm tinh tế thú vị. Về mặt kỹ thuật, trình biên dịch sử dụng pattern matching và tìm kiếm một phương thức GetEnumerator() trả về một kiểu giống Enumerator với một thuộc tính Current và một phương thức MoveNext. Yêu cầu về pattern đó giống hệt những gì IEnumerable định nghĩa, vậy thì sự khác biệt là gì?

Trước khi đi sâu vào vấn đề đó, đáng để xem xét một benchmark nhanh minh họa sự khác biệt.

Tạo benchmark để so sánh foreach

Tôi bắt đầu bằng việc tạo một dự án BenchmarkDotNet mới sử dụng các template của họ bằng cách chạy:

dotnet new benchmark

Sau đó tôi cập nhật file Benchmarks như dưới đây. Benchmark đơn giản này chỉ gọi foreach trên một instance List<int>, rồi chạy cùng vòng lặp foreach đó trên cùng một List<int>, nhưng lần này được lưu dưới dạng biến IEnumerable<int>:

using System.Collections.Generic;
using System.Linq;
using BenchmarkDotNet.Attributes;

[MemoryDiagnoser]
public class Benchmarks
{
    private List<int> _list;
    private IEnumerable<int> _enumerable;

    [GlobalSetup]
    public void GlobalSetup()
    {
        _list = Enumerable.Range(0, 10_000).ToList();
        _enumerable = _list;
    }

    [Benchmark]
    public long List()
    {
        var value = 0;
        foreach (int i in _list)
        {
            value += i;
        }

        return value;
    }

    [Benchmark]
    public long IEnumerable()
    {
        var value = 0;
        foreach (int i in _enumerable)
        {
            value += i;
        }

        return value;
    }
}

Bạn có thể nghĩ rằng cả hai benchmark này sẽ cho kết quả giống nhau. Suy cho cùng, chúng đang chạy cùng một vòng lặp foreach trên cùng một instance List<T>. Điểm khác biệt duy nhất là biến được lưu dưới dạng List<int> hay IEnumerable<int>, điều đó chắc không tạo ra khác biệt lớn, đúng không?

Nếu chúng ta chạy benchmark (tôi đã chạy chúng trên cả .NET Framework và .NET 9), chúng ta có thể thấy thực sự có sự khác biệt; phiên bản IEnumerable vừa chậm hơn và nó cấp phát bộ nhớ:

Vậy câu hỏi đặt ra là, tại sao?

foreach dưới dạng C# đã được hạ bậc (lowered)

Sẽ hữu ích khi ban đầu hiểu chính xác cấu trúc foreach trông như thế nào trong C# “đã được hạ bậc” (lowered). Đây thực chất là những gì trình biên dịch chuyển đổi vòng lặp foreach thành trước khi chuyển sang IL. Nếu chúng ta lấy phương thức EnumerateList() ở trên và chạy nó qua sharplab.io, bạn sẽ nhận được kết quả sau:

private List<int> _list;

public long EnumerateList()
{
    int num = 0;
    List<int>.Enumerator enumerator = _list.GetEnumerator();
    try
    {
        while (enumerator.MoveNext())
        {
            int current = enumerator.Current;
            num += current;
        }
    }
    finally
    {
        ((IDisposable)enumerator).Dispose();
    }
    return num;
}

Như bạn có thể thấy, trong ví dụ này, phương thức GetEnumerator() trả về một instance List<int>.Enumerator, expose một phương thức MoveNext(), một thuộc tính Current, và triển khai IDisposable. Nếu chúng ta so sánh với EnumerateIEnumerable(), chúng ta nhận được gần như cùng mã:

private IEnumerable<int> _enumerable;

public long EnumerateIEnumerable()
{
    int num = 0;
    IEnumerator<int> enumerator = _enumerable.GetEnumerator();
    try
    {
        while (enumerator.MoveNext())
        {
            int current = enumerator.Current;
            num += current;
        }
    }
    finally
    {
        if (enumerator != null)
        {
            enumerator.Dispose();
        }
    }
    return num;
}

Sự khác biệt chính trong mã ở trên là phương thức GetEnumerator() trả về một instance IEnumerator<int> thay vì một instance List<int>.Enumerator cụ thể. Nếu chúng ta nhìn vào chi tiết triển khai của các phương thức duyệt của List<T>, chúng ta có thể thấy thực ra có 3 cách triển khai khác nhau, nhưng tất cả cuối cùng đều ủy quyền cho phương thức GetEnumerator() trả về một instance List<T>.Enumerator.

public class List<T>
{
    public Enumerator GetEnumerator() => new Enumerator(this);
    IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
    IEnumerator IEnumerable.GetEnumerator() => ((IEnumerable<T>)this).GetEnumerator();

    public struct Enumerator : IEnumerator<T>, IEnumerator
    {
        // chi tiết được ẩn đi cho ngắn gọn
    }
}

Và quan trọng là, List<T>.Enumerator được định nghĩa là một kiểu struct.

Struct enumerator

Struct enumerator chính là chìa khóa tạo nên sự khác biệt trong việc cấp phát bộ nhớ. Bằng cách trả về một triển khai struct có thể thay đổi (mutable) của Enumerator thay vì một class, kiểu List<T>.Enumerator có thể được cấp phát trên stack, tránh mọi cấp phát trên heap, và do đó tránh gây áp lực lên bộ thu gom rác (garbage collector). Điều đó chỉ đúng khi trình biên dịch có thể gọi trực tiếp phương thức GetEnumerator()…

Tuy nhiên, khi gọi foreach trên biến IEnumerable, chúng ta cần trả về một IEnumerator (hoặc IEnumerator<T>) để thỏa mãn interface. Cách duy nhất để làm điều đó là đối tượng List<T>.Enumerator phải được boxing lên heap. Đây chính là nguồn gốc của việc cấp phát bộ nhớ mà chúng ta thấy trong benchmark cho biến IEnumerable.

Nhìn chung, hạn chế này hơi đáng tiếc và khá phiền phức. Việc trả về các kiểu interface cơ bản như IEnumerable<T> hay ICollection<T> thay vì các kiểu cụ thể của chúng là một phương pháp đóng gói (encapsulation) chuẩn, cho phép tiến hóa sau này mà không phá vỡ API công khai, và nhìn chung, là điều đúng đắn, được khuyến khích. Chỉ đáng tiếc là điều đó dẫn đến việc cấp phát bộ nhớ. Trừ khi, bạn đang sử dụng .NET 10…

Một lưu ý về .NET 10: deabstraction

Nếu tôi chạy cùng benchmark ở trên trên .NET 10, tôi nhận được một số kết quả thú vị:

Cả hai benchmark về cơ bản là giống nhau. Không có cấp phát bộ nhớ, và thời gian thực thi về cơ bản là giống nhau! Vậy điều gì đang xảy ra ở đây? Câu trả lời ngắn gọn là .NET 10 đã giới thiệu một loạt các kỹ thuật để làm cho loại pattern này nhanh hơn. Có devertualization (phi-ảo-hóa), nhờ đó runtime có thể thấy rằng nó luôn là một List<T> và gọi struct enumerator, và cũng có Object Stack Allocation, nơi các đối tượng mà nếu không sẽ được cấp phát lên heap thì thực sự được cấp phát lên stack nếu trình biên dịch có thể chứng minh rằng đối tượng sẽ không “thoát” (escape). Cộng thêm công việc bổ sung để sửa List<T>.Enumerator, và bạn sẽ có được những kết quả tuyệt vời ở trên!

Tất cả điều đó thật tuyệt nếu bạn đang dùng .NET 10. Đáng tiếc là, trong công việc của tôi tại Datadog .NET SDK, chúng tôi có những khách hàng chạy trên đủ loại phiên bản .NET cũ hơn (bao gồm cả .NET Framework), và vì chúng tôi thường nằm trong hot path của các ứng dụng, chúng tôi cần phải hiệu quả nhất có thể. Và tất cả những lần cấp phát 40 byte đó cộng dồn lại rất nhiều!

Tránh việc cấp phát bộ nhớ của foreach khi biết trước kiểu trả về

Ngày nay, hầu hết các kiểu collection được expose bởi BCL hoặc bởi các thư viện phổ biến đều sử dụng cùng một pattern với enumerator dựa trên stack. Nhưng bạn sẽ mất những lợi ích về hiệu năng này khi collection được expose dưới dạng một collection IEnumerable.

Một cách để tránh sự suy giảm này (nếu bạn biết kiểu trả về của một API sẽ là gì) là chỉ cần cast sang kiểu đó, để trình biên dịch có thể “tìm thấy” phương thức GetEnumerator() tốt hơn:

IEnumerable<int> someCollection = SomeApiThatReturnsAList();

// Nếu chúng ta biết someCollection luôn trả về List<T>, chúng ta có thể "trợ giúp" trình biên dịch
if(someCollection is List<int> list)
{
    // Trình biên dịch có thể gọi `List<T>.GetEnumerator()`, cấp phát
    // trên stack, và tránh việc boxing cấp phát bộ nhớ
    foreach(var value in list)
    {
    }
}
else
{
    // Tùy chọn giữ lại một nhánh dự phòng cho an toàn, phòng khi giả định của chúng ta sai
    // hoặc nó thay đổi trong tương lai
    foreach(var value in someCollection)
    {
    }
}

Có hơi vụng về một chút nhưng nó có tác dụng tránh việc cấp phát bộ nhớ, và khi bạn đang cố gắng để hiệu quả, từng byte đều có giá trị!

Tránh việc cấp phát bộ nhớ của foreach khi bạn không thể tham chiếu kiểu trả về

Cách tiếp cận trên rất dễ dàng và hoạt động tốt nếu:

1. Bạn biết kiểu nào sẽ được trả về bởi một API. Hiển nhiên điều này có thể thay đổi (rốt cuộc đó chính là toàn bộ ý nghĩa của việc dùng IEnumerable!) nên bạn phải đảm bảo xử lý kịch bản này.
2. Kiểu đó là public, để bạn có thể tham chiếu nó.

Điểm thứ hai thường là một vấn đề đối với chúng tôi trong Datadog SDK, bởi vì chúng tôi instrument (theo dõi) rất nhiều thư viện khác nhau, và không thể tham chiếu chúng tại thời điểm biên dịch. Vì vậy nếu chúng tôi muốn tránh việc cấp phát bộ nhớ từ enumerator, chúng tôi cần làm điều gì đó khác.

Lấy ví dụ thuộc tính Activity.TagObjects. API này trả về một IEnumerable<KeyValuePair<string, object>>, nhưng kiểu cụ thể là TagsLinkedList, đây là một kiểu nội bộ (internal), với một struct enumerator. Chúng tôi không thể dùng mẹo is ở trên vì TagsLinkedList không public (và chúng tôi không thể dùng phương thức EnumerateTagObjects(), vì nó không khả dụng trên tất cả các runtime mà chúng tôi hỗ trợ). Vậy làm sao chúng tôi tránh được việc cấp phát bộ nhớ?

Câu trả lời là sử dụng một cách tiếp cận mà chúng tôi dùng ở nhiều nơi khác: sử dụng khả năng của Reflection.Emit để tạo ra một DynamicMethod sử dụng tường minh struct enumerator.

Như tôi đã đề cập ở đầu bài viết này, cách tiếp cận này không mới, và đã được mô tả và sử dụng trước đây bởi những người khác. Tôi chủ yếu tiếp thu phần công trình trước đó đó và điều chỉnh nó cho mục đích của mình, nên xin ghi nhận công lao của họ vì đã làm phần việc khó khăn!

Thiết kế Reflection.Emit DynamicMethod của chúng ta

Reflection.Emit đề cập đến namespace System.Reflection.Emit, chứa nhiều phương thức khác nhau để tạo ra ngôn ngữ trung gian (IL) mới trong ứng dụng của bạn. Các chỉ thị IL là “mã assembly” mà trình biên dịch xuất ra khi bạn biên dịch ứng dụng của mình. JIT trong .NET runtime chuyển đổi các chỉ thị IL này thành mã assembly thực sự khi ứng dụng của bạn chạy.

Reflection.Emit chủ yếu được sử dụng bởi các thư viện và framework đang cố gắng làm những điều táo bạo hoặc đang cố gắng tận dụng hiệu năng ở mọi nơi có thể, nên chắc chắn đây là một API “nâng cao”. Nếu bạn chưa từng dùng nó trước đây, hoặc bạn thấy nó khó hiểu, đừng lo lắng về điều đó!

Trong phần triển khai dưới đây, về cơ bản chúng ta sẽ “thủ công” xây dựng một phương thức chứa một vòng lặp foreach “đã được hạ bậc”, nhưng đảm bảo chúng ta gọi GetEnumerator() dựa trên struct trên đối tượng. Đại loại như thế này:

// Đây thực chất là phương thức chúng ta sẽ tạo ra
public static void AllocationFreeForEach(
    TagsLinkedList list, // Đối tượng cần duyệt
     ref SomeState state, // Một đối tượng trạng thái mà callback có thể sử dụng
      Func<SomeState, KeyValuePair<string, object>, bool> callback) // Callback sẽ được thực thi
{
    // Chúng ta tạo một phiên bản đã hạ bậc của mã này:
    // foreach(var item in list)
    // {
    //     if (!callback(ref state, item))
    //         break;
    // }
    using (TagsLinkedList.Enumerator enumerator = list.GetEnumerator())
    {
        while (enumerator.MoveNext())
        {
            if (!callback(ref state, enumerator.Current))
                break;
        }
    }
}

Chúng ta phải tạo phiên bản “đã hạ bậc” của mã khi xây dựng Dynamic Method của mình, điều đó có nghĩa chúng ta cũng cần hạ bậc khối using, nên thực ra chúng ta đang xem xét một thứ giống như thế này:

public static void AllocationFreeForEach(
    TagsLinkedList list,
     ref SomeState state,
      Func<SomeState, KeyValuePair<string, object>, bool> callback)
{
    TagsLinkedList.Enumerator enumerator = list.GetEnumerator();

    try
    {
        while (enumerator.MoveNext())
        {
            if (!callback(ref state, enumerator.Current))
                break;
        }

    }
    finally
    {
        enumerator.Dispose();
    }
}

Điều đó bao quát khá đầy đủ những gì chúng ta muốn phát ra (emit); tất cả những gì chúng ta cần làm bây giờ là tạo ra DynamicMethod của mình.

Tạo ra DynamicMethod

Chúng ta sẽ phát ra một phương thức tương tự mã ở trên, nhưng dưới dạng một phiên bản tổng quát hóa có thể được gọi với nhiều kiểu duyệt khác nhau, và với nhiều kiểu item khác nhau.

internal static class AllocationFreeEnumerator<TEnumerable, TItem, TState>
    where TEnumerable : IEnumerable<TItem>
    where TState : struct
{
    // Sử dụng reflection để lấy tham chiếu đến các phương thức chúng ta cần gọi
    private static readonly MethodInfo GenericGetEnumeratorMethod = typeof(IEnumerable<TItem>).GetMethod("GetEnumerator")!;
    private static readonly MethodInfo GenericCurrentGetMethod = typeof(IEnumerator<TItem>).GetProperty("Current")!.GetMethod!;
    private static readonly MethodInfo MoveNextMethod = typeof(IEnumerator).GetMethod("MoveNext")!;
    private static readonly MethodInfo DisposeMethod = typeof(IDisposable).GetMethod("Dispose")!;

    // Đây là phương thức chúng ta sẽ gọi
    public delegate void AllocationFreeForEachDelegate(TEnumerable instance, ref TState state, CallbackDelegate itemCallback);

    // Đây là callback được gọi cho mỗi item
    public delegate bool CallbackDelegate(ref TState state, TItem item);

    // Xây dựng một enumerator không cấp phát bộ nhớ
    public static AllocationFreeForEachDelegate BuildAllocationFreeForEachDelegate(Type enumerableType)
    {
        var itemCallbackType = typeof(CallbackDelegate);

        // Cố gắng tìm một phương thức GetEnumerator() không trả về interface
        var getEnumeratorMethod = ResolveGetEnumeratorMethodForType(enumerableType);
        if (getEnumeratorMethod == null)
        {
            // Chúng ta không thể tìm thấy phương thức GetEnumerator() không phải interface, nên
            // quay lại chế độ cấp phát và sử dụng IEnumerable<TItem>.GetEnumerator
            getEnumeratorMethod = GenericGetEnumeratorMethod;
        }

        var enumeratorType = getEnumeratorMethod.ReturnType;

        // xây dựng Dynamic method (AllocationFreeForEachDelegate của chúng ta)
        var dynamicMethod = new DynamicMethod(
            "AllocationFreeForEach",
            null,
            [typeof(TEnumerable), typeof(TState).MakeByRefType(), itemCallbackType],
            typeof(AllocationFreeForEachDelegate).Module,
            skipVisibility: true);

        var generator = dynamicMethod.GetILGenerator();

        // TagsLinkedList.Enumerator enumerator
        generator.DeclareLocal(enumeratorType);

        var beginLoopLabel = generator.DefineLabel();
        var processCurrentLabel = generator.DefineLabel();
        var returnLabel = generator.DefineLabel();
        var breakLoopLabel = generator.DefineLabel();

        // enumerator = arg0.GetEnumerator();
        generator.Emit(OpCodes.Ldarg_0);
        generator.Emit(OpCodes.Callvirt, getEnumeratorMethod);
        generator.Emit(OpCodes.Stloc_0);

        // try
        generator.BeginExceptionBlock();
        {
            // while()
            generator.Emit(OpCodes.Br_S, beginLoopLabel);

            generator.MarkLabel(processCurrentLabel);

            // bool shouldContinue = callback(arg1, enumerator.Current);
            generator.Emit(OpCodes.Ldarg_2);
            generator.Emit(OpCodes.Ldarg_1);
            generator.Emit(OpCodes.Ldloca_S, 0);
            generator.Emit(OpCodes.Constrained, enumeratorType);
            generator.Emit(OpCodes.Callvirt, GenericCurrentGetMethod);

            generator.Emit(OpCodes.Callvirt, itemCallbackType.GetMethod("Invoke")!);

            // if (!continue)
            //     break;
            generator.Emit(OpCodes.Brtrue_S, beginLoopLabel);
            generator.Emit(OpCodes.Leave_S, returnLabel);

            // if (enumerator.MoveNext())
            //    goto: start of while loop
            generator.MarkLabel(beginLoopLabel);
            generator.Emit(OpCodes.Ldloca_S, 0);
            generator.Emit(OpCodes.Constrained, enumeratorType);
            generator.Emit(OpCodes.Callvirt, MoveNextMethod);
            generator.Emit(OpCodes.Brtrue_S, processCurrentLabel);

            // đóng vòng lặp while
            generator.MarkLabel(breakLoopLabel);
            generator.Emit(OpCodes.Leave_S, returnLabel);
        }

        // finally
        generator.BeginFinallyBlock();
        {
            // enumerator.Dispose();
            if (typeof(IDisposable).IsAssignableFrom(enumeratorType))
            {
                generator.Emit(OpCodes.Ldloca_S, 0);
                generator.Emit(OpCodes.Constrained, enumeratorType);
                generator.Emit(OpCodes.Callvirt, DisposeMethod);
            }
        }

        generator.EndExceptionBlock();

        generator.MarkLabel(returnLabel);

        // return
        generator.Emit(OpCodes.Ret);

        return (AllocationFreeForEachDelegate)dynamicMethod.CreateDelegate(typeof(AllocationFreeForEachDelegate));
    }

    private static MethodInfo? ResolveGetEnumeratorMethodForType(Type type)
    {
        // Tìm một phương thức `GetEnumerator()` mà <em>không</em> trả về một
        // interface. Điều này không <em>đảm bảo</em> một enumerator dựa trên struct,
        // nhưng đó là pattern chuẩn nên bắt được hầu hết các trường hợp
        var methods = type.GetMethods(BindingFlags.Instance | BindingFlags.Public | BindingFlags.NonPublic);

        foreach (var method in methods)
        {
            if (method.Name == "GetEnumerator" && !method.ReturnType.IsInterface)
            {
                return method;
            }
        }

        return null;
    }
}

Có rất nhiều mã ở đó, và nếu bạn gặp khó khăn khi theo dõi IL thì chắc chắn nó sẽ gây bối rối 😅 Lời khuyên nhỏ duy nhất tôi có nếu bạn đang cố gắng viết mã này, đó là hãy sử dụng một trình phát IL (IL generator) để hiển thị IL mà bạn nên cố gắng tạo ra. Tôi thường dùng trình phát IL tích hợp trong Rider khi làm việc với những thứ này:

Bây giờ chúng ta đã có trình tạo dynamic method này, chúng ta có thể đưa nó vào thử nghiệm và kiểm tra kết quả.

Benchmark DynamicMethod trên List<T>

Để kiểm thử nó, ban đầu tôi đã cập nhật benchmark để kiểm thử 3 kịch bản khác nhau:

• Một List<int> được lưu trong một biến List<int>
• Một List<int> được lưu trong một biến IEnumerable<int>
• Một List<int> được lưu trong một biến IEnumerable<int>, sử dụng DynamicMethod ở trên

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using BenchmarkDotNet.Attributes;

[MemoryDiagnoser]
public class Benchmarks
{
    private List<int>? _list;
    private IEnumerable<int>? _listEnumerable;
    private AllocationFreeEnumerator<IEnumerable<int>, int, long>.AllocationFreeForEachDelegate _listEnumerator;

    [GlobalSetup]
    public void GlobalSetup()
    {
        _list = Enumerable.Range(0, 10_000).ToList();
        _listEnumerable = _list;
        _listEnumerator = AllocationFreeEnumerator<IEnumerable<int>, int, long>.BuildAllocationFreeForEachDelegate(_list.GetType());
    }

    [Benchmark]
    public long List()
    {
        long value = 0;
        foreach (int i in _list!)
        {
            value += i;
        }

        return value;
    }

    [Benchmark]
    public long IEnumerable()
    {
        long value = 0;
        foreach (int i in _listEnumerable!)
        {
            value += i;
        }

        return value;
    }

    [Benchmark]
    public long IEnumerableDynamicMethod()
    {
        long value = 0;
        _listEnumerator(_list!, ref value, static (ref state, i) =>
        {
            state += i;
            return true;
        });

        return value;
    }
}

Kết quả khi chạy trên .NET Framework 4.8 và .NET 9 là một kết quả trái chiều:

Với .NET Framework, rõ ràng chúng ta đã tìm ra một giải pháp thắng lợi. Chúng ta thấy thời gian thực thi giảm và giờ đây không còn cấp phát bộ nhớ, nên điều đó thật tuyệt.

Với .NET 9, giờ chúng ta không còn cấp phát bộ nhớ, nhưng thời gian thực thi đã tăng gấp đôi, điều này thật đáng tiếc, nhưng có thể đến từ thực tế là List<T> đã nhận được rất nhiều sự chú ý về hiệu năng trong nhiều năm qua, và chúng ta có thể đang giẫm đạp lên điều đó phần nào với DynamicMethod của mình. Việc đánh đổi hiệu năng có đáng hay không có lẽ phụ thuộc vào yếu tố giới hạn của bạn ở đây là gì. Hãy nhớ rằng chi phí cấp phát là cố định bất kể kích thước của danh sách, trong khi thời gian thực thi trong trường hợp này rõ ràng mở rộng gần như tuyến tính theo kích thước danh sách.

Với .NET 10, không có gì ngạc nhiên, cách tiếp cận DynamicMethod của chúng ta cho kết quả tệ hơn so với chỉ sử dụng IEnumerable<int>:

Đây là điều chúng ta mong đợi, với tất cả những cải tiến hiệu năng qua các năm, và sự chú ý dành cho List<T>. Vì việc duyệt IEnumerable<T> đã không cấp phát bộ nhớ trong .NET 10, nên không có lý do chính đáng nào để sử dụng nó trong trường hợp này.

Benchmark DynamicMethod với một IEnumerable<T> tùy chỉnh

Lý do ban đầu của tôi khi tìm hiểu cách tiếp cận DynamicMethod là để xử lý các kiểu không được dựng sẵn trong BCL, nên tôi đã xem xét việc benchmark một triển khai IEnumerable<T> tùy chỉnh. Triển khai danh sách liên kết (linked list) sau đây cực kỳ cơ bản, và là một phiên bản được lược bỏ mạnh mẽ của một triển khai được sử dụng nội bộ bởi Activity. Những chi tiết này không thực sự quan trọng, tôi chỉ đưa vào dưới đây để đầy đủ:

internal sealed class CustomLinkedList<T> : IEnumerable<T>
{
    private Node<T>? _first;
    private Node<T>? _last;

    public CustomLinkedList()
    {
    }

    public CustomLinkedList(T firstValue) => _last = _first = new Node<T>(firstValue);

    public CustomLinkedList(IEnumerator<T> e)
    {
        _last = _first = new Node<T>(e.Current);

        while (e.MoveNext())
        {
            _last.Next = new Node<T>(e.Current);
            _last = _last.Next;
        }
    }

    public Node<T>? First => _first;

    public void Add(T value)
    {
        Node<T> newNode = new Node<T>(value);
        if (_first is null)
        {
            _first = _last = newNode;
            return;
        }

        _last!.Next = newNode;
        _last = newNode;
    }

    public Enumerator<T> GetEnumerator() => new Enumerator<T>(_first);
    IEnumerator<T> IEnumerable<T>.GetEnumerator() => GetEnumerator();
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();

    internal struct Enumerator<T> : IEnumerator<T>
    {
        private static readonly Node<T> s_Empty = new Node<T>(default!);

        private Node<T>? _nextNode;
        private Node<T> _currentNode;

        public Enumerator(Node<T>? head)
        {
            _nextNode = head;
            _currentNode = s_Empty;
        }

        public T Current => _currentNode.Value;

        object? IEnumerator.Current => Current;

        public bool MoveNext()
        {
            if (_nextNode == null)
            {
                _currentNode = s_Empty;
                return false;
            }

            _currentNode = _nextNode;
            _nextNode = _nextNode.Next;
            return true;
        }

        public void Reset() => throw new Exception();

        public void Dispose()
        {
        }
    }
    
    internal sealed partial class Node<T>
    {
        public Node(T value) => Value = value;
        public T Value;
        public Node<T>? Next;
    }
}

Sau đó tôi đã cập nhật benchmark để chạy cùng bộ kiểm thử với triển khai CustomLinkedList thay thế:

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;
using BenchmarkDotNet.Attributes;

[MemoryDiagnoser]
public class Benchmarks
{
    private CustomLinkedList<int>? _linkedList;
    private IEnumerable<int>? _linkedListEnumerable;
    private AllocationFreeEnumerator<IEnumerable<int>, int, long>.AllocationFreeForEachDelegate _linkedListEnumerator;

    [GlobalSetup]
    public void GlobalSetup()
    {
        _linkedList = new();
        foreach (var i in Enumerable.Range(0, 10_000))
        {
            _linkedList.Add(i);
        }

        _linkedListEnumerable = _linkedList;
        _linkedListEnumerator =
            AllocationFreeEnumerator<IEnumerable<int>, int, long>.BuildAllocationFreeForEachDelegate(
                _linkedList.GetType());
    }

    [Benchmark]
    public long LinkedList()
    {
        long value = 0;
        foreach (int i in _linkedList!)
        {
            value += i;
        }

        return value;
    }

    [Benchmark]
    public long IEnumerableLinkedList()
    {
        long value = 0;
        foreach (int i in _linkedListEnumerable!)
        {
            value += i;
        }

        return value;
    }

    [Benchmark]
    public long IEnumerableLinkedListDynamicMethod()
    {
        long value = 0;
        _linkedListEnumerator(_linkedList!, ref value, static (ref state, i) =>
        {
            state += i;
            return true;
        });

        return value;
    }
}

Kết quả từ các benchmark CustomLinkedList<T> này khá tương đồng với các benchmark dành cho List<T>, nhưng với một lưu ý chính: cách tiếp cận DynamicMethod giờ đây nhanh hơn trên .NET 9 cũng như không cấp phát bộ nhớ, nên nó trở thành người chiến thắng rõ ràng trong trường hợp này. Việc tăng tốc trên .NET Framework cũng khá đáng kể:

Như trước đó, với .NET 10, kết quả của DynamicMethod tệ hơn so với IEnumerable<T> thông thường. Điều này thực sự khá ấn tượng — .NET 10 xử lý các benchmark LinkedList và IEnumerableLinkedList gần như không thể phân biệt được. Rất ngầu 😎

Vậy là bạn đã có nó — một cách để thực hiện việc duyệt collection mà không cấp phát bộ nhớ. Rõ ràng câu hỏi liệu bạn có nên làm điều này hay không hoàn toàn phụ thuộc vào ngữ cảnh. Nếu việc duyệt nằm trong hot path, bạn không dùng .NET 10, và những lần cấp phát này đang xuất hiện trong quá trình profiling của bạn, thì, ừm, có lẽ bạn nên cân nhắc nó 😅

Tóm tắt

Trong phần đầu của bài viết này, tôi cung cấp một số bối cảnh về cách thức và thời điểm một vòng lặp foreach có thể gây ra việc cấp phát bộ nhớ. Tôi tạo một benchmark đơn giản để minh họa vấn đề, trình bày C# “đã được hạ bậc”, và mô tả rằng việc cấp phát đến từ việc boxing một struct enumerator.

Trong phần thứ hai của bài viết, tôi mô tả cách bạn có thể tránh việc cấp phát này, cho các kịch bản mà bạn không thể đơn giản cast sang một kiểu đã biết, bằng cách tạo ra một DynamicMethod sử dụng Reflection.Emit. Đây là một kỹ thuật khá nâng cao, nhưng nó cho thấy cách bạn có thể loại bỏ hoàn toàn việc cấp phát bộ nhớ khỏi quá trình duyệt.

Cuối cùng, tôi đã trình bày cách tiếp cận này hoạt động như thế nào trong các benchmark. Nếu bạn đang dùng .NET 10, thì bạn không cần đến DynamicMethod và không cần phải lo lắng gì cả 😀 Trên các runtime cũ hơn, bao gồm cả .NET Framework, cách tiếp cận DynamicMethod loại bỏ việc cấp phát bộ nhớ, và trong nhiều trường hợp cải thiện thời gian thực thi, đặc biệt là đối với các kiểu collection “tùy chỉnh”.

Việc bạn có nên sử dụng cách tiếp cận này hay không rất phụ thuộc vào ngữ cảnh. Trong hầu hết các kịch bản, việc cấp phát 40 byte không phải là vấn đề lớn. Nhưng nếu nó là một vấn đề đối với bạn, thì giờ bạn đã có một công cụ trong bộ công cụ của mình!