65.9K
CodeProject 正在变化。 阅读更多。
Home

Yield Return 优化建议

Paulo Zemek
starIconstarIconstarIconstarIcon
emptyStarIcon
starIcon

4.79/5 (14投票s)

2011年8月5日

CPOL

6分钟阅读

viewsIcon

33253

本文将讨论 yield return 关键字，介绍一种替代方案，并探讨一种更优的 yield return 实现理论；

背景

我最近发表了一篇文章“编写多人游戏（使用 WPF）”。在我自己进行的避免新的编译器生成状态机（State Machine）的修改中，我创造了一种替代方案，它虽然消耗更多资源，但具有一些优势。然后，我仔细思考，我认为 yield return 确实有改进的空间，因此我决定写这篇文章来解释原因，并呼吁大家向微软提出这个功能需求。

功能请求链接为：

http://visualstudio.uservoice.com/forums/121579-visual-studio/suggestions/2107187-create-a-stacksaver-class-to-facilitate-state-mana

yield return 关键字

“yield return”和“yield break”关键字用于返回 IEnumerator<T> 或 IEnumerable<T> 值的方法的体内部。实际上，编译器会为我们生成状态机。

例如，如果你使用 yield return 来组合两个枚举，你可能会写成这样：

public static IEnumerable<T> Combine<T>(IEnumerable<T> first, IEnumerable<T> second)
{
  if (first != null)
    foreach(T value in first)
      yield return value;

  if (second != null)
    foreach(T value in second)
      yield return value;
}

实际上，编译器会实现一个实现 IEnumerable<T> 的新类，并在每次调用 MoveNext 时跟踪其当前位置。实际上，编译器实现的实际代码非常冗长，所以我将尝试展示一个更易读的版本。不使用 yield return 来完成相同工作的代码如下：

public static IEnumerable<T> Combine<T>(IEnumerable<T> first, IEnumerable<T> second)
{
  return new CombineEnumerable<T>(first, second);
}
internal sealed class CombineEnumerable<T>:
  IEnumerable<T>
{
  private IEnumerable<T> _first;
  private IEnumerable<T> _second;

  internal CombineEnumerable(IEnumerable<T> first, IEnumerable<T> second)
  {
    _first = first;
    _second = second;
  }

  public IEnumerator<T> GetEnumerator()
  {  
    IEnumerator<T> firstEnumerator = null;
    IEnumerator<T> secondEnumerator = null;

    if (_first != null)
      firstEnumerator = _first.GetEnumerator();

    if (_second != null)
      secondEnumerator = _second.GetEnumerator();

    return new CombineEnumerator<T>(firstEnumerator, secondEnumerator);
  }
  IEnumerator IEnumerable.GetEnumerator()
  {
    return GetEnumerator();
  }
}
internal sealed class CombineEnumerator<T>:
  IEnumerator<T>
{
  private IEnumerator<T> _first;
  private IEnumerator<T> _second;
  private int _state;

  internal CombineEnumerator(IEnumerator<T> first, IEnumerator<T> second)
  {
    _first = first;
    _second = second;
  }

  public T Current { get; private set; }

  public void Dispose()
  {
    IEnumerator<T> first = _first;
    if (first != null)
    {
      _first = null;
      first.Dispose();
    }
        
    IEnumerator<T> second = _second;
    if (second != null)
    {
      _second = null;
      second.Dispose();
    }
  }

  object IEnumerator.Current
  {
    get
    {
      return Current;
    }
  }

  public bool MoveNext()
  {
    switch(_state)
    {
      case 0:
        if (_first == null || !_first.MoveNext())
        {
          _state = 1;
          goto case 1;
        }

        Current = _first.Current;
        return true;

      case 1:
        if (_second == null || !_second.MoveNext())
        {
          _state = 2;
          return false;
        }

        Current = _second.Current;
        return true;

      default:
        return false;
    }
  }

  public void Reset()
  {
    if (_first != null)
      _first.Reset();

    if (_second != null)
      _second.Dispose();

    _state = 0;
  }
}

正如你所见，“yield return”关键字为我们做了大量工作。但让我们看看 yield return 的一些局限性。

* 它不能在 catch 或 finally 块中调用。原因是无法“goto”到 finally 或 catch 子句。考虑到 yield return 并不是真正的 .Net 资源，而是编译器资源，它必须处理这个限制。* 如果你想将 yield return 放在一个内部方法中，这是不可能的。你最好的办法是始终调用一个方法，例如 BeforeYield(value)，然后 yield return value;。

所以，如果我想要一个只返回偶数的 Combine 方法，我需要这样写：

public static IEnumerable<int> Combine(IEnumerable<int> first, IEnumerable<int> second)
{
  if (first != null)
    foreach(int value in first)
      if ((value % 2) == 0)
        yield return value;

  if (second != null)
    foreach(int value in second)
      if ((value % 2) == 0)
        yield return value;
}

或者像这样：

public static IEnumerable<int> Combine(IEnumerable<int> first, IEnumerable<int> second)
{
  if (first != null)
    foreach(int value in first)
      if (_IsEven(value))
        yield return value;

  if (second != null)
    foreach(int value in second)
      if (_IsEven(value))
        yield return value;
}
private static bool _IsEven(int value)
{
  return (value % 2) == 0;
}

如果条件判断不像 _IsEven 这样简单，你可能会更倾向于第二种方法。另一种方法是将 EnumerateEvenNumbers 与原始的 combine 方法结合起来。这样，一个枚举器将组合另外两个，另一个将过滤偶数。但是，对我来说，最好的解决方案应该是这样的：

public static IEnumerable<int> Combine(IEnumerable<int> first, IEnumerable<int> second)
{
  if (first != null)
    foreach(int value in first)
      _YieldIfEven(value);

  if (second != null)
    foreach(int value in second)
      _YieldIfEven(value);
}

// It is not an enumerator, but calls yield return as it is called from one.
private static void YieldIfEven(int value)
{
  if ((value % 2) == 0)
    yield return value;
}

目前这还不可以实现，但我非常期待如何实现类似的功能。

使用线程和同步，我已经可以实现类似的功能：

public static IEnumerable<int> Combine(IEnumerable<int> first, IEnumerable<int> second)
{
  return 
    new ThreadedEnumeratorFromAction<T>
    (
      (yieldReturn) =>
      {
        if (first != null)
          foreach(int value in first)
            _YieldIfEven(value, yieldReturn);

        if (second != null)
          foreach(int value in second)
            _YieldIfEven(value, yieldReturn);
      }
    );
}
private static bool _IsEven(int value, Action<T> yieldReturn)
{
  if ((value % 2) == 0)
    yieldReturn(value);
}

事实上，这种方法之所以有效，是因为有另一个线程在运行这段代码。第一个线程只是简单地等待第二个线程完成。

缺点？很多。需要一个线程和两个 AutoResetEvents 来完成这项工作。我已经使用了自己的线程池和 EventWaitHandle 池来尽量减少开销，但还有一个问题。如果第一个线程持有锁，即使它在等待第二个线程，第二个线程也无法获取该锁，否则就会发生死锁。如果这个解决方案在同一个线程中运行，锁就已经被获取了，所以不会有问题。

优点？嗯，方法不需要特殊的编译器资源即可工作。如果它们可以接收操作（actions）或继承自该类，任何方法都可以随时“yield return”。如果你将“yieldReturn”作为操作传递，你实际上可以传递一个立即处理该值的操作，一个将该值发布到另一个线程的操作，或者一个强制执行“yieldReturn”的操作，这样你的方法就可以比使用编译器生成的“yield return”更加通用。此外，值可以在任何时候提供，包括在 finally 和 catch 块中。

StackSaver（或 StackStateMachine）理论

栈（stack）已经“存储”了所有值，但它是顺序的。我们无法将栈的一部分复制到另一个对象，然后回退几层栈。但至少在我用 680x0 汇编编程时，是可以直接操作栈的。

所以，我的想法是这样的。会有一个类（我称它为 StackSaver，但也许 StackStateMachine 更好）。它使用一个操作进行初始化，并且是 Enumerable 的。当你调用 MoveNext 时，它会存储其当前的栈位置并运行直到调用其 YieldReturn 方法。

当发生这种情况时，它会将从激活到此时刻的栈复制到自己的存储中，然后回退栈并返回 true。如果方法结束，则返回 false。

因此，考虑到它接收一个简单的 Action（不是 Action<object> 或类似类型），代码可能如下所示：

private static IEnumerable<int> Combine(IEnumerable<int> first, IEnumerable<int> second)
{
  return
    new StackSaver
    (
      () =>
      {
        if (first != null)
          foreach(int value in first)
            _YieldIfEven(value);

        if (second != null)
          foreach(int value in second)
            _YieldIfEven(value);
      }
    );
}
private static bool _IsEven(int value)
{
  if ((value % 2) == 0)
    StackSaver.StaticYieldReturn(value); // this method will return to the last active StackSaver.
}

即使这个初始代码看起来比“yield return”版本更复杂，但它也有很多优势：

  • 编译器不需要支持 yield return 的自动生成即可利用这一点。支持 Action 就足够了。
  • 我使用了 YieldReturn 的静态版本，但实例版本也可以存在，如果通过委托接收它，你的方法仍然可以直接处理结果（无需 yield），并且可以使用嵌套的 StackSaver。如果你在另一个 StackSaver 内部使用一个 StackSaver，你就可以 yield 到第一个 StackSaver。
  • 如果他们真的实现了这个功能，我强烈建议他们也创建一个 IIterator 接口，用于不需要返回值（yield）的迭代器。我肯定会在我的游戏中用到它。
  • 如果调用者持有锁，StackSaver 中运行的操作也会持有该锁，因此不会发生因此而导致的死锁。

Dispose 或收集

有些人可能会认为，如果我们创建了这样的 StackSaver 但忘记使用它，就会产生问题。

好吧，我不这么认为。调用 dispose 时，可能会抛出类似 ThreadAbortException 的异常。这是一种可捕获的异常，它总是会重新抛出，因此它会强制执行 finally 和 catch 块，但不会执行其他操作。这可能发生在 Dispose 时，或者当线程死亡但未被 dispose 时。

实现起来容易吗？

我真的不知道微软是如何处理 .Net 的调用栈的，但我认为它比 yield return 关键字的实现要容易。毕竟，栈已经被管理了，将其复制到对象然后返回几个级别会有多难呢？

如果你同意我的观点，认为这是一个非常有用的资源，请访问 http://visualstudio.uservoice.com/forums/121579-visual-studio/suggestions/2107187-create-a-stacksaver-class-to-facilitate-state-mana 并投票。

源代码？

嗯，我唯一真正能展示的是 ThreadedEnumeratorFromAction<T> 类，但目前我只有它的非返回版本，我正在我的游戏中使用它。我想很快发布一个更新，届时将使用它。所以，请耐心等待。
© . All rights reserved.