性能优化:Trove集合库

1 初见Trove

昨天在Startup News上看到一篇文章:优化技巧分享：把内存消耗降低至原来的1/20。里边提到了一个案例，Java应用中如何降低内存消耗，总结了他的优化过程:

开始时,存放1.3M个Person对象，消耗堆空间1.5GB
修改为java.util.HashMap<Long, Person>进行缓存,从1.5GB降低为214MB
修改HashMap为Trove的TLongObjectHashMap，从214MB降低为143MB
优化Person内部结构,减少重复字段,从143MB降低为93MB
开启64位JDK的XX:UseCompressedOops参数进行指针压缩,从93MB降低为73MB

优化经常得针对具体的场景、数据特性来优化，上述提到的Trove集合库就是这么一个典型例子,它针对的是JDK集合类中处理原生类型的场景。

2 使用Trove

如果使用Maven的话,可使用下面的配置

<dependency>
  <groupId>net.sf.trove4j</groupId>
  <artifactId>trove4j</artifactId>
  <version>3.0.3</version>
</dependency>

常用方法和JDK集合类是一样的，方便迁移

TIntObjectMap<String> ints = new TIntObjectHashMap<String>();
ints.put(100, "John");
ints.put(101, "Tom");
System.out.println(ints.get(100));

Trove相当于把JDK集合类都针对原生类型处理了一遍，例如int，常见的类有 TIntList、TIntObjectMap、TObjectIntMap、TIntSet，可想而知，维护Trove的工作量是挺大的。

Trove还提供了开放寻址法的Map,Set,LinkedList实现,可以参考Enhance Collection Performance with this Treasure Trove的做法,类似于:

public class CollectionFactory {
  static boolean useTrove = true;

    /**
  *  Return a hashmap based on the properties
  */
  public static Map getHashMap() {
      if ( useTrove ) return new THashMap();
      else            return new HashMap();
  }

  /**
  *  Return a hashset based on the properties
  */
  public static Set getHashSet() {
      if ( useTrove ) return new THashSet();
      else            return new HashSet();
  }

  /**
  *  Return a linkedlist based on the properties
  */
  public static List getLinkedList() {
      if ( useTrove ) return new TLinkedList();
      else            return new LinkedList();
  }
}

迭代集合中的元素

Trove不推荐JDK的entryXX的做法，而是采用了forEach的回调方式。代码显得更好看些，另外内存方面也有优势，因为使用entryXX的做法，需要创建一个新的数组。

TIntObjectMap<String> ints = new TIntObjectHashMap<String>();
ints.put(100, "John");
ints.put(101, "Tom");
ints.forEachEntry(new TIntObjectProcedure<String>() {
    public boolean execute(int a, String b) {
        System.out.println("key: " + a + ", val: " + b);
        return true;
    }
});
ints.forEachKey(new TIntProcedure() {
    public boolean execute(int value) {
        System.out.println("key: " + value);
        return true;
    }
});
ints.forEachValue(new TObjectProcedure<String>() {
    public boolean execute(String object) {
        System.out.println("val: " + object);
        return true;
    }
});

自定义Hash策略

我们知道，在JDK集合类里边，有时候是没法自定义Hash策略的，例如String。 不过Trove提供了自定义Hash策略的功能，让你可以根据数据特性进行优化。

public static void main(String[] args) {
    char[] foo = new char[]{'a', 'b', 'c'};
    char[] bar = new char[]{'a', 'b', 'c'};
    TCustomHashMap<char[], String> ch = new TCustomHashMap<char[], String>(new CharArrayStrategy());
    ch.put(foo, "John");
    ch.put(bar, "Tom");
}

class CharArrayStrategy implements HashingStrategy<char[]> {
    public int computeHashCode(char[] c) {
        // use the shift-add-xor class of string hashing functions
        // cf. Ramakrishna and Zobel, "Performance in Practice
        // of String Hashing Functions"
        int h = 31; // seed chosen at random
        for (int i = 0; i < c.length; i++) { // could skip invariants
            h = h ^ ((h << 5) + (h >> 2) + c[i]); // L=5, R=2 works well for
                                                  // ASCII input
        }
        return h;
    }

    public boolean equals(char[] c1, char[] c2) {
        if (c1.length != c2.length) { // could drop this check for fixed-length
                                      // keys
            return false;
        }
        for (int i = 0, len = c1.length; i < len; i++) { // could skip
                                                         // invariants
            if (c1[i] != c2[i]) {
                return false;
            }
        }
        return true;
    }
}

3 Trove内幕

Trove是以减少内存消耗为主要目的的，同时也要保持性能。我们这里简单描述一下Trove的实现内幕。这里有有另外一篇文章可以参考：性能观察: Trove 集合类

直接使用原生类型,而不是包装类型

JDK5的自动封箱机制，让我们可以暂时忽略原生类型和包准类型的区别。自动封箱机制只是一种语法糖，实际上并没有提高效率。直接使用原生类型替代包装类型，明显可以占用更小的内存、运行起来也更有效率。对于基本类型的集合组合，Trove都提供了等价的集合类。

使用开放寻址法，而不是链地址法

大多数的JDK集合类都是采用链地址法实现的，它需要一个地址表，并且元素之间需要链表结点，而Trove采用开放寻址法，虽然需要保持足够的空闲位置(装载因子小于0.5),但因为不需要链表结点，所以总体上内存占用要更少，性能还要更快一些。

HashSet不再通过内置HashMap实现

JDK的HashSet是通过内置一个HashSet来实现的，所以白白浪费了value的空间。 Trove提供的THashSet和其他基本类型的HashSet,都不再采用这种方式，直接使用开放地址存储。

采用素数长度大小的数组

为了最大程度避免hash冲突，除了保持较小的装载因子，还采用了素数长度大小的数组。具体见gnu.trove.impl.PrimeFinder

采用代码生成进行维护

虽然这个和性能没什么关系。但是我们也知道要维护这么多的原生类型集合类，重复的逻辑多但没法重用，是个很纠结的事情。 Trove采用代码模板，生成大量的类，通过这种方式，可以大大减少维护的工作量。

4 总结

JDK作为通用集合类，大多数情况下我们还是会优先选择的。不过，在一些性能敏感的地方，或者Trove可以提供更好的选择。作为靠谱的java开发人员，Trove应该像apache commons、google guava那样，存放在你的工具箱里边。

小毛的胡思乱想

凡走过,必留痕迹.

1 初见Trove

2 使用Trove

3 Trove内幕

4 总结

Comments