生成大表，给DataGrid加列，将DataGrid绑定到表，你猜哪个最慢？

使用DataGrid控件显示数据是很简单的，只要把数据赋给ItemsSource属性就可以了，数据列都会自动地帮你生成出来。那么在整个过程中，哪个环节是最慢的呢？

之所以要写这文章，就是因为最近发现DataGrid的列操作是最慢的。而且慢得不可理喻。比如在DataGrid中显示1万数据行简直就是小菜一碟。因为有RowVirtualization机制，只有显示出来的部分才会生成控件。DataGrid也有ColumnVirtualization机制，那显示1万列数据应该也没有什么问题。但是事实上，DataGrid面对海量列数据的时候毫无招架之力。

下面这个小程序，把整个过程分成了三个步骤：

    第一步：生成数据    第二步：给DataGrid 手工添加数据列。

         注意：这里是一列列加的，Columns属性没有AddRange方法。DataGrid也不支持AddRange。即使用绑定或自动生成，内部也会是一列列加的。

    第三步：将数据绑定到DataGrid的ItemsSource属性上

DataGrid在显示海量行数据的时候还是可以的，这里着重讨论海量列数据。所以目标数据大小定为100行*10000列，数据类型为int。就是“百万格子”。

在我可怜的赛扬2.66G的CPU上的跑分结果如下（公司用的酷睿2，以两万列测试会有类似结果）：

	生成数据	生成列	数据绑定
100行*10列	5ms	5ms	624ms （半屏）
100行*100列	19ms	26ms	1632ms（满屏）
100行*1000列	62ms	571ms	1616ms（满屏）
100行 * 10000列	342ms	32108ms	3341ms（满屏）
1000行*10000列	3121ms	32624ms	3456ms（满屏）

 

注意最后两次都是10000列，10万列的我怕睡觉前都跑不完。从数据中我们基本上可以得出下面的结论。

• 数据生成的时间复杂度为O(row * column)，很正常。
•  生成列的时间复杂度为 O(column²)，这个很不正常。
•  数据绑定，时间都花在控件生成上。所以时间基本上与有多少Item显示在屏幕上相关，而与整体数据量无关。 这个也很正常。如果DataGrid的Virtualization是很有效果的。

一万列是海量么？要我说根本不算，但也已经耐不住一个O(n²)的插入算法的蹂躏了。下图显示了他都在干什么。

几乎所有的时间都花在了DataGridColumnCollection.HasVisibleStarColumnsInternal上面。而且还主要花在了Get两个属性上。Get啊。我们来看看这个神奇的函数做了什么令人发指的事情居然能让Get属性的操作成为瓶颈。代码如下（第796行）：

/// <summary>
///     Method which determines if there are any 
///     star columns in datagrid except the given column and also returns perStarWidth
/// </summary>
private bool HasVisibleStarColumnsInternal(DataGridColumn ignoredColumn, out double perStarWidth)
{ 
    bool hasStarColumns = false;
    perStarWidth = 0.0; 
    foreach (DataGridColumn column in this) 
    {
        if (column == ignoredColumn || !column.IsVisible)
        {
            continue;
        } 
 
        DataGridLength width = column.Width; 
        if (width.IsStar) 
        {
            hasStarColumns = true; 
            if (!DoubleUtil.AreClose(width.Value, 0.0) &&
                !DoubleUtil.AreClose(width.DesiredValue, 0.0))
            {
                perStarWidth = width.DesiredValue / width.Value; 
                break;
            } 
        } 
    }
 
    return hasStarColumns;
}

 

嗯，他遍历了当前所有Column去找当前可见范围内有没有宽度自动的列。从上面的图中也可以看出来，这个方法会在添加一个列的时候调用。看源代码会更直观些（位于DataGridColumnCollection第89行）：

 protected override void OnCollectionChanged(NotifyCollectionChangedEventArgs e){

     switch (e.Action)
   {
        case NotifyCollectionChangedAction.Add:
            if (DisplayIndexMapInitialized)
            {
                 UpdateDisplayIndexForNewColumns(e.NewItems, e.NewStartingIndex);
            }
            InvalidateHasVisibleStarColumns();

            break;
     case NotifyCollectionChangedAction.Move:

 

好了，这样，要加N列数据，就要调用Get_IsVisible和Get_Width，各N*(N+1)/2次。当然总计就是N*(N+1)次。添加一万列数据，就要Get DependencyProperty一亿次。要是加1亿列，恐怕“天河”都会觉得压力很大。

另外，请大家注意一下，HasVisibleStarColumnsInternal函数不仅仅Get这两个Property，还Get了5次非DP。但是他们没有成为瓶颈。从Sampling的结果来看，Get两个DP，占用了这个函数近91%的运算时间。而且这两个DP还不是inheritance的DP（这种DP性能更差）。而MSDN上却说Get DP不比Get CLR property慢。但是从上面的例子可以看出，DP在真实环境中要比CLR Property要慢10倍以上。这里的真实环境是指，基本上每个会用到DP的类（比如控件）都会有几十个DP。再来看Sampling的结果，看看Get DP慢在了什么地方。

在Get DP的时候，近70%的时间被用来LookupEntry。这与DP的实现原理有关，其实DP的原理类似一个大表，上面全是名值对，GetDP的过程，就是拿着Property的名字，去这个表里找值的过程。如果数据和分析都没有什么说服力的话，那我们就来看看GetValue的代码吧。

 
   
    ///
     
    <summary>
    

    ///
         Retrieve the value of a property 

    ///
     
    </summary>
     

    ///
     
    <param name="dp">
    Dependency property
    </param>
    

    ///
     
    <returns>
    The computed value
    </returns>
     
    

    public
     
    object
     GetValue(DependencyProperty dp)
 {
     
    //
     Do not allow foreign threads access.
     
    //
     (This is a noop if this object is not assigned to a Dispatcher.) 
     
    //

        
    this
    .VerifyAccess(); 

     
    if
     (dp 
    ==
     
    null
    )
     { 
         
    throw
     
    new
     ArgumentNullException(
    "
    dp
    "
    );
     }

     
    //
     Call Forwarded 
    

        
    return
     GetValueEntry(LookupEntry(dp.GlobalIndex), dp, 
    null
    ,
             RequestFlags.FullyResolved).Value;
 }


    
  

 

里面的LookupEntry就是在查表，Lookup所需要的时间取决于DP的GlobalIndex在表里的位置。空口无凭，我们再来看看LookupEntry的代码。

 
   
    //
     look for an entry that matches the given dp 

    //
     return value has Found set to true if an entry is found

    //
     return value has Index set to the index of the found entry (if Found is true) 

    //
                or  the location to insert an entry for this dp (if Found is false)
    

    [FriendAccessAllowed] 
    //
     Built into Base, also used by Framework.
    

    internal
     EntryIndex LookupEntry(
    int
     targetIndex)
 { 
     
    int
     checkIndex;
     
    uint
     iLo 
    =
     
    0
    ; 
     
    uint
     iHi 
    =
     EffectiveValuesCount; 

     
    if
     (iHi 
    <=
     
    0
    ) 
     {
         
    return
     
    new
     EntryIndex(
    0
    , 
    false
     
    /*
     Found 
    */
    );
     }

     
    //
     Do a binary search to find the value
    

        
    while
     (iHi 
    -
     iLo 
    >
     
    3
    ) 
     { 
         
    uint
     iPv 
    =
     (iHi 
    +
     iLo) 
    /
     
    2
    ;
         checkIndex 
    =
     _effectiveValues[iPv].PropertyIndex; 
         
    if
     (targetIndex 
    ==
     checkIndex)
         {
             
    return
     
    new
     EntryIndex(iPv);
         } 
         
    if
     (targetIndex 
    <=
     checkIndex)
         { 
             iHi 
    =
     iPv; 
         }
         
    else
     
         {
             iLo 
    =
     iPv 
    +
     
    1
    ;
         }
     } 

     
    //
     Now we only have three values to search; switch to a linear search 
    

        
    do
     
     {
         checkIndex 
    =
     _effectiveValues[iLo].PropertyIndex; 

         
    if
     (checkIndex 
    ==
     targetIndex)
         {
             
    return
     
    new
     EntryIndex(iLo); 
         }

         
    if
     (checkIndex 
    >
     targetIndex) 
         {
             
    //
     we've gone past the targetIndex - return not found 
    

                
    break
    ;
         }

         iLo
    ++
    ; 
     }
     
    while
     (iLo 
    <
     iHi);  

     
    return
     
    new
     EntryIndex(iLo, 
    false
     
    /*
     Found 
    */
    );
 } 
    
  

就是折半查找，很常见的算法。本来Get Property的操作是个O(1)的操作。用上DP就成了一个O(log(DP count))的操作了。从代码中可以看出，每一次循环，就要做4次四则运算、3次比较、3次赋值。怎么可能像MSDN上说的“不比CLR Property慢”！最佳情况，你一个类只定义一个DP，函数内也走最短路径，也要有3次赋值，3次比较，2次取值，1次四则运算，最后还要实例化一个EntryIndex类的实例出来。到这里，你还只是找到了Index，还没有去找值呢！怎么可能不比CLR Property里直接返回一个变量慢呢？而且每次都要折半查找一次，显然是个用CPU换内存的策略，毕竟这是WPF里几乎所有新功能的基础，这里多个Bit都是很要命的事情。即使这样WPF的内存占用也是WinForm的3倍，Win32的9倍（均为经验值）。

我们可以想象MSDN的作者是如何得出DP不比CLR Property慢的结论的。他们很可能是用两个类，各有那么俩、仨属性，一个类都是用DP，一个类都是用CLR Property。然后比较 Get Value的速度。真是梦幻般的测试环境啊。当然我们要理解微软，因为写MSDN Sample和开发.NET Framework的根本不是一群人。让精英们写Sample成本太高了，而且他们自己也不愿意。所以.NET 和Visual Studio Team的Blog是比MSDN更重要的学习资源。

扯远了，回来说DataGridColumnCollection。总结一下，他的Add单个 Column方法，用了一个O(n)的算法。还因为大量使用DP（当然，必须的）给O(n)前面加了个巨大的系数。最终缔造出了一个奇慢的Columns初始化速度。好在现实情况下，多数数据的Column没有多少。但是作为一个控件，就不应该假设使用者的数据列不会太多。况且，存在着一个显然的优化方法就是提供一次可以Add多个列的功能。20个月之前就有人在MSDN上问过这个问题，微软也说这个功能也在他们的计划中。但是AddRange功能谈何容易，这其实是一个迁一发而动全身的功能。怕是WPF 5也不会有了。而且多数情况下，ItemsControl的ItemsSource并不需要AddRange来减少CollectionChanged事件的次数。原因很简单，那些控件的瓶颈根本就不在这里，而在Layout和Render上。

 

抱怨也是多余的。微软Connect网站上的WPF Bug多如牛毛，还轮不到这个“罕见的横宽的”百万数据的用例。就算这个Performance问题解决了，DataGrid还有别的Performance问题。比如一开始的表中，绑定数据后显示出来就要3秒，谁受得了？当你在DataGrid中放上百万级的数据之后，就会发现所有的操作都很卡。就算是有Virtualization机制也卡。WinForm的DataGrid显示百万数据的时候，Scroll什么的小菜一碟。而WPF的DataGrid就成了碟子里的菜了。

但是问题还是要解决的，我想了各种各样的方法。全部需要用反射。在这里用反射我很放心，有个O(n²)的算法给我垫底我还怕什么呢？（补充下，通过反射方式访问、修改私有成员这种事，不到万不得已不要用。如果用了，以后就要小心向后兼容问题和移植问题。微软从来不保证私有成员不会变。）

               法一：把CollectionChanged事件禁用，全加完了再发个Reset类型的CollectionChanged事件。经过实验，不可行。

              法二：调用CopyFrom一次加完。也不行。因为整个DataGridColumnCollection的实现都是基于这样的一个假设。Add操作，一次一个。比如下面的代码（有删节）：

 
   
    ///
     
    <summary>
    

    ///
         Sets the DisplayIndex on all newly inserted or added columns and updates the existing columns as necessary. 

    ///
     
    </summary>
    

    private
     
    void
     UpdateDisplayIndexForNewColumns(IList newColumns, 
    int
     startingIndex)
 {
     DataGridColumn column; 
     
    int
     newDisplayIndex, columnIndex; 

     
    try
    
     { 
         IsUpdatingDisplayIndex 
    =
     
    true
    ;

         
    //
     Set the display index of the new columns and add them to the DisplayIndexMap 
    

            column 
    =
     (DataGridColumn)newColumns[
    0
    ];
         columnIndex 
    =
     startingIndex; 


    
  

       它就直接取newColumns 的第一个，其它的不管了。

               法三：只能一次一个，从上面的分析可以看出，性能瓶颈在InvalidateHasVisibleStarColumns函数上，Add的时候不调用这个函数，全Add完后再调用。这个方法正在试。

               法四：好吧，不用.NET Framework的功能上下手了。只能是一万列数据，不全Load，只Load比如10列，水平方向填满DataGrid就行了，但是这时DataGrid的水平滚动条肯定是不对的。解决方法就是自己在DataGrid下面放一个ScrollBar控件，自己维护滚动、数据加载、数据绑定与数据列的生成。垂直方向有性能问题也可以这么干。不过，好麻烦，好山寨，好无力啊。

 

问题总是能解决的。但是给人的感觉就是用WPF做东西真的是要很小心。一不小心性能上就有问题。至于微软给的Performance Guide，我的感觉是，那是最基本的，不Follow那个，性能一定会有问题。完全Follow，性能不一定没问题。

当然WPF还是要用的，而且推荐用微软自己的库，现在微软自己的WPF库，什么图表啦、Ribbon啦全都有。个人不推荐用第三方的比如Infragistics和Xceed的东西。如果微软库没有，而且时间也不紧，更推荐自己写一个，其实用不了多少时间的。有了Bug也好修。