3

There are probably hundreds of questions about Java Collections vs. arrays, but this is something I really didn't expect.

I am developing a server for my game, and to communicate between the client and server you need to send packets (obviously), so I did some tests which Collection (or array) I could use best to handle them, HashMap, ArrayList and a PacketHandler array. And the outcome is very unexpected to me, because the ArrayList wins.

The packet handling structure is just like dictionary usage (index to PacketHandler), and because an array is the most primitive form of dictionary use I thought that would easily perform better than an ArrayList. Could someone explain me why this is?

My test

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

public class Main {
  /**
   * Packet handler interface.
   */
  private interface PacketHandler {
    void handle();
  }

  /**
   * A dummy packet handler.
   */
  private class DummyPacketHandler implements PacketHandler {
    @Override
    public void handle() { }
  }

  public Main() {
    Random r = new Random();
    PacketHandler[] handlers = new PacketHandler[256];
    HashMap<Integer, PacketHandler> m = new HashMap<Integer, PacketHandler>();
    ArrayList<PacketHandler> list = new ArrayList<PacketHandler>();

    // packet handler initialization
    for (int i = 0; i < 255; i++) {
      DummyPacketHandler p = new DummyPacketHandler();
      handlers[i] = p;
      m.put(new Integer(i), p);
      list.add(p);
    }

    // array
    long time = System.currentTimeMillis();
    for (int i = 0; i < 10000000; i++)
      handlers[r.nextInt(255)].handle();
    System.out.println((System.currentTimeMillis() - time));

    // hashmap
    time = System.currentTimeMillis();
    for (int i = 0; i < 10000000; i++)
      m.get(new Integer(r.nextInt(255))).handle();
    System.out.println((System.currentTimeMillis() - time));

    // arraylist
    time = System.currentTimeMillis();
    for (int i = 0; i < 10000000; i++)
      list.get(r.nextInt(255)).handle();
    System.out.println((System.currentTimeMillis() - time));
  }

  public static void main(String[] args) {
    new Main();
  }
}

I think the problem is quite solved, thanks everybody

4

2 に答える 2

4

簡単に言うと、ArrayList は最初は少し最適化されていますが、長期的にはまだ遅くなります。

JVM が完全にウォームアップする前にコードを最適化する方法とタイミングは、常に明らかであるとは限らず、バージョン間およびコマンド ライン オプションに基づいて変更される可能性があります。

本当に興味深いのは、テストを繰り返したときに得られるものです。ここで違いが生じる理由は、コードがバックグラウンドで段階的にコンパイルされるためです。これは、コードが最初からすぐに高速になるテストが必要なためです。

ベンチマークをより再現可能にするためにできることがいくつかあります。

  • 事前に乱数を生成します。乱数はテストの一部ではありませんが、速度が低下する可能性があります。
  • 各ループを別のメソッドに配置します。最初のループは、メソッド全体をトリガーして、良くも悪くもコンパイルします。
  • テストを 5 ～ 10 回繰り返し、最初のテストは無視します。
  • currentTimeMillis() の代わりに System.nanoTime() を使用する ここでは違いはないかもしれませんが、慣れるには良い習慣です。
  • 可能な場合はオートボクシングを使用して、同じことを行う整数キャッシュまたは Integer.valueOf(n) を使用します。new Integer(n)常にオブジェクトを作成します。
  • あなたの内側のループが何かをしていることを確認してください。;)

.

import java.util.ArrayList;
import java.util.HashMap;
import java.util.Random;

public class Main {

    /**
     * Packet handler interface.
     */
    private interface PacketHandler {
        void handle();
    }

    /**
     * A dummy packet handler.
     */
    static class DummyPacketHandler implements PacketHandler {

        @Override
        public void handle() {
        }

    }

    public static void main(String[] args) {
        Random r = new Random();

        PacketHandler[] handlers = new PacketHandler[256];
        HashMap<Integer, PacketHandler> m = new HashMap<Integer, PacketHandler>();
        ArrayList<PacketHandler> list = new ArrayList<PacketHandler>();

        // packet handler initialization
        for (int i = 0; i < 256; i++) {
            DummyPacketHandler p = new DummyPacketHandler();
            handlers[i] = p;
            m.put(new Integer(i), p);
            list.add(p);
        }

        int runs = 10000000;
        int[] handlerToUse = new int[runs];
        for (int i = 0; i < runs; i++)
            handlerToUse[i] = r.nextInt(256);

        for (int i = 0; i < 5; i++) {
            testArray(handlers, runs, handlerToUse);
            testHashMap(m, runs, handlerToUse);
            testArrayList(list, runs, handlerToUse);
            System.out.println();
        }
    }

    private static void testArray(PacketHandler[] handlers, int runs, int[] handlerToUse) {
        // array
        long time = System.nanoTime();
        for (int i = 0; i < runs; i++)
            handlers[handlerToUse[i]].handle();
        System.out.print((System.nanoTime() - time)/1e6+" ");
    }

    private static void testHashMap(HashMap<Integer, PacketHandler> m, int runs, int[] handlerToUse) {
        // hashmap
        long time = System.nanoTime();
        for (int i = 0; i < runs; i++)
            m.get(handlerToUse[i]).handle();
        System.out.print((System.nanoTime() - time)/1e6+" ");
    }

    private static void testArrayList(ArrayList<PacketHandler> list, int runs, int[] handlerToUse) {
        // arraylist
        long time = System.nanoTime();
        for (int i = 0; i < runs; i++)
            list.get(handlerToUse[i]).handle();
        System.out.print((System.nanoTime() - time)/1e6+" ");
    }
}

プリントarray HashMap ArrayList

24.62537 263.185092 24.19565 
28.997305 206.956117 23.437585 
19.422327 224.894738 21.191718 
14.154433 194.014725 16.927638 
13.897081 163.383876 16.678818

コードがウォームアップした後、配列はわずかに高速になります。

于 2012-09-13T17:53:29.273 に答える
2

ベンチマークには少なくともいくつかの問題があります。

  • テストを main で直接実行します。つまり、main メソッドがコンパイルされるとき、JIT コンパイラーはまだ実行していないため、すべてのコードを最適化する時間がありませんでした。
  • map メソッドは毎回新しい整数を作成しますが、これは公平ではありません:m.get(r.nextInt(255)).handle();整数キャッシュの使用を許可するために使用します
  • 結論を導き出す前に、テストを数回実行する必要があります
  • ループで行ったことの結果を使用していないため、JIT は単純にそれらを無視することができます。
  • GC は常に同時に実行される可能性があるため、GC を監視し、ループの 1 つの結果にバイアスをSystem.gc()かけ、各ループ間に呼び出しを追加します。

しかし、それを行う前に、この投稿を読んでください;-)

コードを少し調整した後、次の結果が得られます。

Array: 116
Map: 139
List: 117

そのため、コンパイルすると配列とリストはほぼ同じになり、マップは少し遅くなります。

コード：

パブリック クラス メイン {

/**
 * Packet handler interface.
 */
private interface PacketHandler {

    int handle();
}

/**
 * A dummy packet handler.
 */
private class DummyPacketHandler implements PacketHandler {

    @Override
    public int handle() {
        return 123;
    }
}

public Main() {
    Random r = new Random();

    PacketHandler[] handlers = new PacketHandler[256];
    HashMap<Integer, PacketHandler> m = new HashMap<Integer, PacketHandler>();
    ArrayList<PacketHandler> list = new ArrayList<PacketHandler>();

    // packet handler initialization
    for (int i = 0; i < 255; i++) {
        DummyPacketHandler p = new DummyPacketHandler();
        handlers[i] = p;
        m.put(new Integer(i), p);
        list.add(p);
    }

    long sum = 0;
    runArray(handlers, r, 20000);
    runMap(m, r, 20000);
    runList(list, r, 20000);

    // array
    long time = System.nanoTime();
    sum += runArray(handlers, r, 10000000);
    System.out.println("Array: " + (System.nanoTime() - time) / 1000000);

    // hashmap
    time = System.nanoTime();
    sum += runMap(m, r, 10000000);
    System.out.println("Map: " + (System.nanoTime() - time) / 1000000);

    // arraylist
    time = System.nanoTime();
    sum += runList(list, r, 10000000);
    System.out.println("List: " + (System.nanoTime() - time) / 1000000);

    System.out.println(sum);
}

public static void main(String[] args) {
    new Main();
}


private long runArray(PacketHandler[] handlers, Random r, int loops) {
    long sum = 0;
    for (int i = 0; i < loops; i++)
        sum += handlers[r.nextInt(255)].handle();
    return sum;
}

private long runMap(HashMap<Integer, PacketHandler> m, Random r, int loops) {
    long sum = 0;
    for (int i = 0; i < loops; i++)
        sum += m.get(new Integer(r.nextInt(255))).handle();
    return sum;
}

private long runList(List<PacketHandler> list, Random r, int loops) {
    long sum = 0;
    for (int i = 0; i < loops; i++)
        sum += list.get(r.nextInt(255)).handle();
    return sum;
}

}

于 2012-09-13T17:54:16.240 に答える