由for V.S. for each想到的

一直想写一系列如何提高Performance和Scalability的文章,把我的相关经验和所知道的相关的技巧同大家分享。前一阵在园子里有一篇讨论for each 和 for两种循环那个具有更好的performance的blog,议论得沸沸扬扬。我觉得这是一个很好的切入点,我就已此作为引子,开始我的这个系列的文章。这篇文章的重点不是在于比较这两种循环孰优孰劣,我将讨论的重点是如何更好地定义Collection,如何在判断在什么时候该用Array,什么时候用Collection。

一、for each的本质

我们知道,所有实现了System.Collections. IEnumerable接口的类,我们都可以对它运用for each loop。为了弄清楚它的执行过程,我先给出一个Sample:

using System;
using System.Collections.Generic;
using System.Text;
using System.Collections;

namespace Artech.CustomCollection
{
    struct Employee
    {
        Private Fields#region Private Fields
        private string _employeeID;
        private string _name;
        private int _age;
        #endregion

        Constructor#region Constructor
        public Employee(string employeeID, string name, int age)
        {
            this._employeeID = employeeID;
            this._name = name;
            this._age = age;
        }
        #endregion

        Public Properties#region Public Properties

        public string EmployeeID
        {
            get { return _employeeID; }
            set { _employeeID = value; }
        }

        public string Name
        {
            get { return _name; }
            set { _name = value; }
        }

        public int Age
        {
            get { return _age; }
            set { _age = value; }
        }

        #endregion

        Tostring#region Tostring
        public override string ToString()
        {
            return string.Format("\tID: \t{0}\n\tName: \t{1}\n\tAge:\t{2}\n\t", this._employeeID, this._name, this._age);
        }
        #endregion
    }

    class EmployeeList : IEnumerable
    {
        private Employee[] _employees;

        public Employee[] Employees
        {
            get { return _employees; }
            set { _employees = value; }
        }

        IEnumerable Members#region IEnumerable Members

        public  virtual IEnumerator GetEnumerator()
        {
            Console.WriteLine("EmployeeList.GetEnumerator() is invoked");
            return new GenericEmployeeEnumerator(this._employees);
        }

        #endregion
    }

    class EmployeeEnumerator : IEnumerator
    {
        private Employee[] _employees;
        private int _index = -1;

        public EmployeeEnumerator(Employee[] employees)
        {
            this._employees = employees;
        }

        IEnumerator Members#region IEnumerator Members

        public object Current
        {
            get
            {
                Console.WriteLine("EmployeeEnumerator.Current is invoked");
                return this._employees[this._index];
            }
        }

        public bool MoveNext()
        {
            Console.WriteLine("EmployeeEnumerator.MoveNext is invoked");

            if (this._index < this._employees.Length - 1)
            {
                this._index++;
                return true;
            }
            return false;
        }

        public void Reset()
        {
            this._index = -1;
        }
        #endregion
    }
    class Program
    {
        static void Main(string[] args)
        {
            Employee[] employees = new Employee[] { new Employee("0001", "Zhang San", 21), new Employee("0002", "Li Si", 30) };
            EmployeeList empoyeeList = new EmployeeList();
            empoyeeList.Employees = employees;

            Console.WriteLine("Begin foreach loop ");
            foreach (Employee employee in empoyeeList)
            {
                Console.WriteLine(employee.ToString());
            }
            Console.WriteLine("\n\nBegin while loop ");
            IEnumerator enumerator = empoyeeList.GetEnumerator();
            while (enumerator.MoveNext())
            {
                Employee employee = (Employee)enumerator.Current;
                Console.WriteLine(employee.ToString());
            }
        }
    }
}

我们先运行一下上面的程序再来讲述具体的执行的流程。

在上面的Sample中我们先定义了一个Employee的struct,之所以使用struct而不用一般的class,我将在后面的部分介绍。

struct Employee
    {
        Private Fields#region Private Fields
        private string _employeeID;
        private string _name;
        private int _age;
        #endregion

        Constructor#region Constructor
        public Employee(string employeeID, string name, int age)
        {
            this._employeeID = employeeID;
            this._name = name;
            this._age = age;
        }
        #endregion

        Public Properties#region Public Properties

        public string EmployeeID
        {
            get { return _employeeID; }
            set { _employeeID = value; }
        }

        public string Name
        {
            get { return _name; }
            set { _name = value; }
        }

        public int Age
        {
            get { return _age; }
            set { _age = value; }
        }

        #endregion

        Tostring#region Tostring
        public override string ToString()
        {
            return string.Format("\tID: \t{0}\n\tName: \t{1}\n\tAge:\t{2}\n\t", this._employeeID, this._name, this._age);
        }
        #endregion
}

然后我们基于这个Emplyee struct,定义了与之对应的Collection:EmplyeeList。EmplyeeList实现了System.Collections. IEnumerable接口。并以一个virtual 方法的形式实现了该接口的GetEnumerator方法。(为什么用virtual方法的原因,我会再后续部分解释)。

Public virtual  IEnumerator GetEnumerator()
        {
            Console.WriteLine("EmployeeList.GetEnumerator() is invoked");
            return new GenericEmployeeEnumerator(this._employees);
        }

上面方法返回一个的实现了System.Collections. IEnumerator自定义的Enumerator:EmployeeEnumerator。其定义如下:

class EmployeeEnumerator : IEnumerator
    {
        private Employee[] _employees;
        private int _index = -1;

        public EmployeeEnumerator(Employee[] employees)
        {
            this._employees = employees;
        }

        IEnumerator Members#region IEnumerator Members

        public object Current
        {
            get
            {
                Console.WriteLine("EmployeeEnumerator.Current is invoked");
                return this._employees[this._index];
            }
        }

        public bool MoveNext()
        {
            Console.WriteLine("EmployeeEnumerator.MoveNext is invoked");

            if (this._index < this._employees.Length - 1)
            {
                this._index++;
                return true;
            }

            return false;
        }

        public void Reset()
        {
            this._index = -1;
        }

        #endregion
    }

在Program类中,我们两种不同的Loop,for each 和while来遍历我们创建的EmployeeList对象,通过最终的输出结果,我们发现两个Loop具有完全一样的输出。而实际上两种Loop的本质上是一样的。Foreach的执行流程和While完全一样:首先调用EmployeeList对象的GetEnumerator获得对应的Enumerator,然后开始循环,并通过Enumerator的MoveNext方法的返回结果来确定是否中止循环。在每次循环中,通过Enumerator的Current Property获得当前迭代的对象。

二、程序的的缺点和局限

实际上,上面的程序设计方案存在很大的performance的问题:

1. EmployeeList的GetEnumerator是virtual方法导致不能充分利用Inlining的编译优化。

Inlining是C++中广泛运用的一种编译优化方案,甚至在C++有Inlining关键字。他的本质是在编译的时候,把方法的调用嵌入调用堆栈转变成直接放方法体编译到调用堆栈中从而获得在performance上的提升。.NET语言,比如C#,对应的编译器也充分利用了这一编译优化方案,编译器能够分析程序的执行来确定是否采用Inlining的编译方式。

但是对应virtual方法调用的运行时对象类型而非其申明类型中定义的方法,在编译的时候,Complier是不可能获得某一个对象运行时属于什么类型的,所以它也不可能运用Inlining这种编译优化方案。

所以我们在设计我们的类时,如果你确确实实需要把某个方法定义成virtual 方法,否则千万不要这么做。如果父类的该方法是virtual或override,你最好封闭(sealed)它。 

2. EmployeeEnumerator的Current返回值为object导致装箱。

装箱导致performance的降低已经是众所周知的了,在这里就不必多说了。在本例中EmployeeEnumerator的Current实际上是一个ValueType的Emplyee struct,由于该属性的返回值是object,所以需要对获得的Emplyee进行装箱,在使用的时候对它进行拆箱。这一装一拆对于一个具有很大容积的collection来说,有时候是致命的。

三、Array V.S. ArrayList

既然我们已经找出了我们设计的不足,我们就可以从新修改我们的设计来你不这种不足。不过在这之前,我们先来看看我们经常使用的Array和ArrayList是如何实现的,从而来指导我们如何正确使用Array和ArrayList。

我们先来看看Array中GetEnumerator方法的定义:

public IEnumerator GetEnumerator()
{
    int index = this.GetLowerBound(0);
    if ((this.Rank == 1) && (index == 0))
    {
        return new SZArrayEnumerator(this);
    }
    return new ArrayEnumerator(this, index, this.Length);
}

从上面的定义我们可以看到,Array的GetEnumerator并没有像我一样使用virtual的方法。实际上对于一个Array来说,确实没有必要使用virtual方法,因为你定义的具体的Array只能直接继承自System.Array,而不能继承自别的Array, 比如,你不能定义某个class继承自int[]。.在Array中实际上是使用了两个不同的Enumerator,对于一维基0数组,使用的是SZArrayEnumerator,非一维基0数组则使用的是ArrayEnumerator。我们来看看SZArrayEnumerator具体是如何定义的:

[Serializable]
private sealed class SZArrayEnumerator : IEnumerator, ICloneable
{
    Fields#region Fields
    private Array _array;
    private int _endIndex;
    private int _index;
#endregion

    Methods#region Methods
    internal SZArrayEnumerator(Array array)
    {
        this._array = array;
        this._index = -1;
        this._endIndex = array.Length;
    }

    public object Clone()
    {
        return base.MemberwiseClone();
    }

    public bool MoveNext()
    {
        if (this._index < this._endIndex)
        {
            this._index++;
            return (this._index < this._endIndex);
        }
        return false;
    }

    public void Reset()
    {
        this._index = -1;
    }
    #endregion

    Properties#region Properties
    public object Current
    {
        get
        {
            if (this._index < 0)
            {
                throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumNotStarted"));
            }
            if (this._index >= this._endIndex)
            {
                throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumEnded"));
            }
            return this._array.GetValue(this._index);
        }
    }
    #endregion
}

对于Current 属性,返回值仍然是object,对于一个基于Value Type的array,装箱操作在所难免。我想到现在为止,我们知道为什么for循环在performance上要优于for each的原因了吧。

分析完Array,我们来看看另一个在.NET 2.0之前经常使用的一个类:ArrayList。我们照例来看看他的GetEnumerator的定义: 

public virtual IEnumerator GetEnumerator()
{
    return new ArrayListEnumeratorSimple(this);
}

同Array不同的是,GetEnumerator方法被定义成virtual,所以对于Arraylist来说,它也不可以利用Inlining的编译优化获得performance上的提升。所以我们可以得出结论,Array比ArrayList具有更好的performance。(实际上这只是Array比ArrayList具有更好的performance其中一个原因,还有一个主要的原因时Array是基于某个确定Type的数组,我们在定义的时候就已经给它指定了具体的Type)。在Arraylist中使用的Enumerator是ArrayListEnumeratorSimple。我们来看看它的定义:

[Serializable]
private sealed class ArrayListEnumeratorSimple : IEnumerator, ICloneable
{
    Fields#region Fields
    private object currentElement;
    private static object dummyObject = new object();
    private int index;
    [NonSerialized]
    private bool isArrayList;
    private ArrayList list;
    private int version;
    #endregion

    Methods#region  Methods
    internal ArrayListEnumeratorSimple(ArrayList list)
    {
        this.list = list;
        this.index = -1;
        this.version = list._version;
        this.isArrayList = list.GetType() == typeof(ArrayList);
        this.currentElement = dummyObject;
    }

    public object Clone()
    {
        return base.MemberwiseClone();
    }

    public bool MoveNext()
    {
        if (this.version != this.list._version)
        {
            throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumFailedVersion"));
        }
        if (this.isArrayList)
        {
            if (this.index < (this.list._size - 1))
            {
                this.currentElement = this.list._items[++this.index];
                return true;
            }
            this.currentElement = dummyObject;
            this.index = this.list._size;
            return false;
        }
        if (this.index < (this.list.Count - 1))
        {
            this.currentElement = this.list[++this.index];
            return true;
        }
        this.index = this.list.Count;
        this.currentElement = dummyObject;
        return false;
    }

    public void Reset()
    {
        if (this.version != this.list._version)
        {
            throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumFailedVersion"));
        }
        this.currentElement = dummyObject;
        this.index = -1;
    }
    #endregion

    Properties#region Properties
    public object Current
    {
        get
        {
            object currentElement = this.currentElement;
            if (dummyObject != currentElement)
            {
                return currentElement;
            }
            if (this.index == -1)
            {
                throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumNotStarted"));
            }
            throw new InvalidOperationException(Environment.GetResourceString("InvalidOperation_EnumEnded"));
        }

    }
    #endregion
}

Current属性返回的类型依然是object, 对于ValueType来说,装箱在所难免。不过总的来说,Array较之ArrayList在Performance具有较大的优势,对一个Performance要求比较高的Application来说,尽量使用Array来替代ArrayList。 四、优化方案

通过以上的分析,通过Enumerator遍历Collection对象来说,影响performance的主要因素体现在以下两个方面:

1. EmployeeList的GetEnumerator是virtual方法导致不能充分利用Inline的编译优化。

2. EmployeeEnumerator的Current返回值为object导致装箱。

基于这两点,我们重新定义Enumerator:OptimizedEmployeeEnumerator。

class OptimizedEmployeeEnumerator : IEnumerator
    {

        private Employee[] _employees;
        private int _index = -1;

        public OptimizedEmployeeEnumerator(Employee[] employees)
        {
            this._employees = employees;
        }

        IEnumerator Members#region IEnumerator Members

        public Employee Current
        {
            get
            {
                Console.WriteLine("OptimizedEmployeeEnumerator.Current is invoked");
                return this._employees[this._index];
            }
        }

        object IEnumerator.Current
        {
            get
            {
                Console.WriteLine("IEnumerator.Current is invoked");
                return this._employees[this._index];
            }
        }

        public bool MoveNext()
        {
            Console.WriteLine("EmployeeEnumerator.MoveNext is invoked");

            if (this._index < this._employees.Length - 1)
            {
                this._index++;
                return true;
            }

            return false;
        }

        public void Reset()
        {
            this._index = -1;
        }


        #endregion
    }

通过上面的Code,我们可以看到,我们通过显示接口实现的方式实现了object Current,并对应了另一个不需要装箱、返回类型为Employee的Current属性。

我们随之EmployeeList作相应的修改:

class EmployeeList : IEnumerable
    {
        public  IEnumerator GetEnumerator()
        {
            Console.WriteLine("EmployeeList.GetEnumerator() is invoked");
            return new OptimizedEmployeeEnumerator(this._employees);
        }
}

我们去掉我们不需要的virtual关键字,并修正GetEnumerator方法使之返回我们新定义的OptimizedEmployeeEnumerator。

五、进一步优化

通过上面对程序的修正,如果现在我们通过通过while  Loop的方式来遍历EmpoyeeList,在较大数据的情况下,performance可以得到较大的提升(注:我们必须通过申明为OptimizedEmployeeEnumerator而不是Enumerator的变量来获得对应的Enumerator,这样我们才能访问Employee Current属性,而不是object Current属性,从而避免装箱,具体的原因,请查阅MSDN关于“显式接口实现“的内容)。但是使用for each来进行遍历的话,装箱还是难以避免的。我们可以通过程序来证明这一点。

我们修改Main方法:

static void Main(string[] args)
        {
            Employee[] employees = new Employee[] { new Employee("0001", "Zhang San", 21), new Employee("0002", "Li Si", 30) };
            EmployeeList empoyeeList = new EmployeeList();
            empoyeeList.Employees = employees;

            Console.WriteLine("Begin foreach loop ");
            foreach (Employee employee in empoyeeList)
            {
                Console.WriteLine(employee.ToString());
            }

            Console.WriteLine("\n\nBegin while loop ");
            OptimizedEmployeeEnumerator enumerator = empoyeeList.GetEnumerator() as OptimizedEmployeeEnumerator;

            while (enumerator.MoveNext())
            {
                Employee employee = (Employee)enumerator.Current;
                Console.WriteLine(employee.ToString());
            }
        }

运行程序,看看现在的输出:

通过输出我们可以看到While循环调用的是返回类型是Employee的Current 属性,而for each循环仍然使用的是返回类型是Object的Current 属性。了解接口的“显式实现”的人一看就知道怎么回事,在这里不想再对说了。其实这是无法避免的,因为for each会把获得的Enumerator转换成对应的接口类型IEnumerator,所以调用的永远是IEnumerator中定义的返回类型为object的Current属性。

所以我们还需要我们的程序作进一步的优化来使for each Loop避免装箱。提到避免装箱,我想了解.NET 2.0的人马上就会联想到Generic。不错,我们的解决方案就是使用Generic的Enumerator。所以我们重新定义我们的Enumerator:GenericEmployeeEnumerator。

class GenericEmployeeEnumerator : IEnumerator<Employee>
    {
        private Employee[] _employees;
        private int _index = -1;

        public GenericEmployeeEnumerator(Employee[] employees)
        {
            this._employees = employees;
        }

        IEnumerator Members#region IEnumerator<Employee> Members

        public Employee Current
        {
            get
            {
                Console.WriteLine("GenericEmployeeEnumerator.Current is invoked");
                return this._employees[this._index];
            }
        }


        #endregion

        IDisposable Members#region IDisposable Members

        public void Dispose()
        {

        }

        #endregion

        IEnumerator Members#region IEnumerator Members

        object IEnumerator.Current
        {
            get
            {
                Console.WriteLine("IEnumerator.Current is invoked");
                return this._employees[this._index];
            }
        }

        public bool MoveNext()
        {
            Console.WriteLine("GenericEmployeeEnumerator.MoveNext is invoked");

            if (this._index < this._employees.Length - 1)
            {
                this._index++;
                return true;
            }

            return false;
        }

        public void Reset()
        {
            this._index = -1;
        }

        #endregion
}

代码不复杂,不需要多说什么。我们对EmployeeList的GetEnumerator方法作相应的修改使之返回我们重新定义个GenericEmployeeEnumerator。为了验证,我们修改Main方法:

static void Main(string[] args)
        {
            Employee[] employees = new Employee[] { new Employee("0001", "Zhang San", 21), new Employee("0002", "Li Si", 30) };
            EmployeeList empoyeeList = new EmployeeList();
            empoyeeList.Employees = employees;

            Console.WriteLine("Begin foreach loop ");
            foreach (Employee employee in empoyeeList)
            {
                Console.WriteLine(employee.ToString());
            }

            Console.WriteLine("\n\nBegin while loop ");
            GenericEmployeeEnumerator enumerator = empoyeeList.GetEnumerator() as GenericEmployeeEnumerator;

            while (enumerator.MoveNext())
            {
                Employee employee = (Employee)enumerator.Current;
                Console.WriteLine(employee.ToString());
            }
        }

我们将会得到下面的输出:

六、回归简约

事实上,我们上面做的事情是在把简单的事情复杂化,我们可以利用Generic的Collection来实现相应的功能。比如我们我们通过定义System.Collections.Generic .List<Employee>来创建我们的EmploteeList对象。 相关内容: [原创]如何改Managed Code的Performance和Scalability系列之二:深入理解string和如何高效地使用string

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏跟着阿笨一起玩NET

DataGridView绑定BindingList<T>带数据排序的类

本文章转载:http://yuyingying1986.blog.hexun.com/30905610_d.html

781
来自专栏技术博客

Asp.net MVC后台 XML、DataTable、DataSet之间的数据转换

  上面的方法只是将XMl字符串读入到DataSet中,然后再冲DataSet中查找先前定义过的DataTable即可。

1412
来自专栏飞扬的花生

集合中随机取不重复的索引

有时候希望从一个集合中随机取n个元素不重复 那么就取到这n个数字的索引 public static int[] GetRandomArray(int Numb...

3298
来自专栏hbbliyong

C#基础知识回顾-- 反射(3)

获取Type对象的构造函数: 前一篇因为篇幅问题因为篇幅太短被移除首页,反射这一块还有一篇“怎样在程序集中使用反射”, 其他没有什么可以写的了,前两篇主要是铺...

2976
来自专栏菩提树下的杨过

Silverlight与WPF中BeginInvoke的差异

Silverlight/WPF中,如果要在多线程中对界面控件值做修改,用Dispatcher对象的BeginInvoke方法无疑是最方便的办法 ,见:温故而知新...

2298
来自专栏技术博客

一步一步学Linq to sql(一):预备知识

  Linq to sql(或者叫DLINQ)是LINQ(.NET语言集成查询)的一部分,全称基于关系数据的 .NET 语言集成查询,用于以对象形式管理关系数据...

951
来自专栏码农阿宇

关于C#委托的一些学习笔记

1.什么是委托就是把方法作为参数传给另一个方法。委托说指向的函数,必须和函数具有相同的签名(返回值和参数类型) Public delegate void D...

2757
来自专栏GreenLeaves

C# 字符串操作基本过程(Equals、Compare、EndsWith等处理方法)

4022
来自专栏二进制文集

JSON Java 解析

要使程序可以运行必须引入JSON-lib包——org.json.jar包。综合来看,这个JAR包比较好用。

1632
来自专栏用户3030674的专栏

Java中Json解析

首先准备一个JSON格式的字符串 * String JsonStr = "{object:{persons:" + "[{name:'呵呵',im...

3512

扫码关注云+社区

领取腾讯云代金券