西西河

主题:【原创】说说.NET 3.5中的高性能害死集--HashSet -- Highway

共:💬19 🌺63
全看分页树展 · 主题
家园 【原创】说说.NET 3.5中的高性能害死集--HashSet

几个月前,看到MSDN杂志上有一篇文章叫做《CLR Inside Out: New Library Classes in “Orcas”》,里面提到了.NET3.5中新增的一个类HashSet,当时就觉得很有意思,一直想探个究竟,但苦于没有时间。这两天Labor day休息,算是找了点时间,把这个问题把玩了一下。这里就跟大家聊聊。

首先先把这个HashSet解释一下。HashSet就是使用Hash技术实现的集合(Set)。集合是个很重要数据结构,不论是从逻辑上讲还是从实际编程上来说。使用Hash技术来实现集合操作也是最为普遍和常见的。这个Hash呢,国内好像翻译作“哈虚”,叫人看着就头晕。什么哈虚表,哈虚集的,望之比堆栈,链表什么的还要俨然。要是让我翻译,叫做“害死”肯能更亲和一些,发音也更接近,大家说是不是?

那么这个Set到底是干什么的呢?我们这里举个例子简单介绍一下。

比如说你来西西河灌水,第一件事就是要注册一个网名。这个网名首先不能和别人的重合。铁手可能用的是database query来检查重复性的问题,如果用程序语言来办的话,Set就是一个很好的数据结构。已有的网友放在一个Set里面,以后每有用户注册的话,就问一下这个Set (contains() 函数),看看有没有问题。没有重复并且认证通过以后这个新的ID就加入到网友集合中去(add()函数)。

如果有一天西西河和别的网站合并了(比如说把柚子网收购了),那么第一件事情就是清点网友。西西河3万,柚子网2万,结果呢,3万5。为什么不是5万呢?因为很多人两面注册,统计的时候不用算两次。这呢,就是取两个集合的合集(Superset)。合并后,铁手要选拔新的版主。可能最合适人选是两面都脸熟的网友。这时候呢,就要先看看两个网站的交集,看看哪些家伙是两边混的(Intersect)。

往简单里说,集合主要就是这么写操作。

说来你们可能不相信,就这么一个最常见最普遍的东西微软的.NET里居然没有。从1.0开始到现在将近7年了,这个缺就一直空着。直到.NET 3.5这个窟窿才算是有人给堵上。有些搞笑是不是?

更搞笑的是微软在填这个黑窟窿的时候,居然还堂而皇之的,美其名曰“高性能害死集(HashSet)”。大有王婆卖瓜的架势。

就我个人看来,Java的Collection比微软的.NET要好不止一点半点。感觉一个是有框架,有结构,深思熟虑后的东西;而另外一个有些拼拼凑凑,仓促上阵的杂牌军。有些朋友问我一些编程的建议,我总是把Java的Collections Framework放在显要位置。上Google一查,第一个蹦出来的就是老剑客Josh Bloch(巨牛级人物)的Java Collections Framework入门教程。外链出处。这个短篇高屋建瓴,深入浅出,绝对是大家手笔。把它学好了,绝对是收益非浅。Java发展到5.0以后,搞出了一个Concurrent package,给Collections Framework引入了不少新鲜血液。对于成天价在线程里讨营生的程序员来说,这些都是都是宝,都是好东东,

Java Collections Framework唯一的缺点就是对于新手来说,选择太多,有些眼晕,比如说吧,最简单的一个Map功能,到底是该使用那个具体实现呢(implementation)?抛开那些生僻的不说,最常见的就有好几个,比如说Hashtable, HashMap, WeakHashMap, TreeMap, ConcurrentHashMap, ConcurrentSkipListMap。如何更好的归纳整理一下,让新手和老枪都各得其所这可能是Java需要解决的一个小问题。

微软这边到没这个问题。不是老式的Hashtable,就是Generic的Dictionary<T, U>。没得挑反倒省心。自打2.0起,大家都捧Generics场,所以Dictionary几乎成了不二人选。事实上,Dictionary<T, U>倒也称职,一般的事情都能解决。如果需要排序的话,请SortedDictionary<T, U>出场也就够了。

Dictionary<T, U>不光可以解决Java里面所谓Map Interface里面定义的那些功能,稍加改动,Set功能也就实现了。事实上,Java的HashSet就是在HashMap上蒙了一层皮,你们要是看一些JDK里面的Source code,一眼就明白了。使用同样的手法,我们可以用三两分钟就创建出.NET的HashSet来。

譬如说

    class HashSet<T>
    {
        private static readonly Object DUMMY = new Object();

        private Dictionary<T, Object> map;

        public HashSet()
        {
            this.map = new Dictionary<T, object>();
        }

        public void Add(T obj)
        {
            if(!this.map.ContainsKey(obj))
            {
                this.map.Add(obj, DUMMY);
            }
        }

        public void Remove(T obj)
        {
            map.Remove(obj);
        }

        public bool Contains(T obj)
        {
            return this.map.ContainsKey(obj);
        }

        //此处略去308字...
}

就我所知,现在的.NET程序员们都是用这样的办法“对付着” 过的。可能微软觉得大家日子还能过,所以也就不急的想办法了。

Better later than never。不管怎么说,微软算是把这个Collections API的黑窟窿给堵上了。那我们现在就看看这个“高性能”是吹牛还是名归实致。

我写了段非常简单的程序,原理是随机产生一些东西(整数,String),然后将这些东西放到Set里面去,检验最常用的add操作。然后再产生另外一组东西,一个个的检查一下,看看Set里面是不是已经包含了(检验contains操作),最后再循环一次,把Set里面的东西一个个删除(检验remove操作。)

这里是测试结果。同样的程序我在Java 6.0, Java 7.0(测试版) ,以及.NET 3.5 Beta 2版本下进行测试。结果呢,.NET 3.5的HashSet还真是比Java快一些。其中整数测试大概快17%-29%,String测试快5%左右(有一组例外,Java要快)。

点看全图

外链图片需谨慎,可能会被源头改

点看全图

外链图片需谨慎,可能会被源头改

从这个角度讲,微软宣称的“高性能”倒也不完全是瞎吹。表现也还过得去。但为什么整数测试优势明显,而String测试差距就很小了呢?

选择整数和String我是有针对性的。在Java中,所有的Collection操作都是针对Object的,整数,浮点数这些Primitive类型是不可以的。即使从语法上你可以放一个整数到Set里面,但实际上Java是将这个整数先变成了Integer Object,然后才放到Set里面的。这里有个包装的开销(boxing)。

.NET的Generics是针对任何类型的。整数,浮点数这些Value type可以直接放到Set中去,不需要所谓的Boxing。就这一点而言,.NET是有绝对优势的。所以最后测试胜出,可能也就在于把Java boxing的开销省了。

大家不妨这样来理解,Hash一类的操作都是基于一个Object的Hash code来进行的。Java里面 int x = 5,double y = 3.8,这x, y哪里来的Hash code。变成Integer,Double对象以后呢,这些属性才有,所以哈虚才玩得转。相反,在.NET里面, int x= 5,这个x是一个Value Type,它的确是有Hash Code的(就是他本身),也提供GetHashCode()这么个函数让你把x的Hash Code拿出来。

String操作呢,两面都是Object,大家半斤八两。不过呢,.NET的Generics不需要类型转化(casting),虽然现在计算当中casting并不费时,但没有这个操作可能还是有一点点的优势的。可能由于这点节省,.NET最终比Java快了5%左右。

就测试的这些结果分析一下,我们可以大概得出这样一个结论,那就是.NET和Java在“哈虚”一端功力相若。虽然没有直接拼比HashMap和Dictionary,但我觉得两者也应该非常接近。由于.NET在Generics上的基础优势,所以在针对Primitive类型/value type操作上,由于节省了boxing/un-boxing的开销,所以性能上有一定的优势;在Object / Reference类型操作上,.NET也还是保持着一点点的优势,不过节省casting带来的优势远没有那么明显罢了。所以在我的测试中.NET赢了两阵,功劳可能还算不到Hash头上。

出于好奇,我把这个新的HashSet和我前面提到的用Dictionary包装生成的“自制”Set比试了一把,结果打了个难分难解,自制的土货甚至还有一点点的优势。这个就有些怪异了。敢情微软费了那么大的劲儿,全力推出的这么个HashSet和我几分钟就炮制的东西差不多呀?

点看全图

外链图片需谨慎,可能会被源头改

点看全图

外链图片需谨慎,可能会被源头改

有没有可能微软这个HashSet就是基于已有的那个Dictionary的啊?我觉得可能性不大。并且我反编译了这个两个类的程序,看着差异还是蛮大的,不象Java的HashMap和HashSet那么昭然若揭。

点看全图

外链图片需谨慎,可能会被源头改

点看全图

外链图片需谨慎,可能会被源头改

当然微软这个新的HashSet功能比较多,有一些挺方便的函数,比如IsSuperSetOf, IsSubsetOf, IntersectWith等等。但是我觉得这些功能并不复杂,用Dictionary也就是几句程序行的事情。不知道微软花了这么长的时间怎么就整出这个个东西来,有些匪夷所思。不过呢,我的测试只是闹着玩的,很多功能都没有测试,所以我不便于轻下结论。有兴趣的朋友可以沿着这条思路走下去,把这个问题搞搞清楚。

好了,就先灌到这里吧。

关键词(Tags): #NET#HashSet#Java元宝推荐:铁手,请尽量,
全看分页树展 · 主题


有趣有益,互惠互利;开阔视野,博采众长。
虚拟的网络,真实的人。天南地北客,相逢皆朋友

Copyright © cchere 西西河