Определение набора основных правил для высокопроизводительных структур данных (Java) - PullRequest
11 голосов
/ 18 ноября 2011

Я обычно использую векторы / массивы, hashmaps / treemaps и другие коллекции java взаимозаменяемо, за исключением того факта, что иногда существуют функциональные требования API (например, в некоторых случаях мне может понадобиться отсортированный набор данных).

В последнее время, однако, я обнаружил необходимость довести производительность Java до предела для некоторых алгоритмов, которые я запускаю.

Существует ли ряд рекомендаций для высокой производительностиструктуры данных, которые я могу использовать в качестве основных правил для своего кодирования?

Я ищу общие правила, но в этом контексте ответы на следующие вопросы также могут быть очень полезны:

1) Когда я должен использовать многомерные массивы вместо вложенных коллекций?

2) Векторы и списки массивов - действительно ли существует разница в производительности?

3) Как API-интерфейсы коллекций, такие как коллекции Google, уловки Java (например, отражение и приведение) и другие распространенные идиомы разработчика Java, имеют тенденцию замедлять JVM, когда он находится под большой нагрузкой?

4) Замедляют ли примитивы и обычные объекты (т. Е. Double против double) JVM при выполнении большого количества вычислений?

5) Существуют ли другие важные рекомендации по работе с большими коллекциями в Java-программах, которые должны быть высокопроизводительными?

  • Примечание: на данный момент яне выполняю многопоточность ... Я понимаю, что есть другие ограничения, которые могут применяться после того, как я начну распараллеливание.

Ответы [ 8 ]

9 голосов
/ 18 ноября 2011

Все проблемы с производительностью должны решаться в первую очередь путем профилирования (как для времени, так и для использования памяти / объектов).Не оптимизируйте вещи, которые не влияют на производительность вашего кода.С этим предупреждением существуют некоторые общие практические правила (которые все должны быть проверены профилированием!)

1) Когда я должен использовать многомерные массивы вместо вложенных коллекций?

Если вам не нужно динамическое определение размера коллекций и вам не нужно передавать данные в то, что требует коллекции, тогда многомерные массивы (собственно массивы) могут быть быстрее.

2) Векторы и списки массивов - действительно ли разница в производительности?

Да.Многие методы в векторе синхронизированы, что дорого.Если вы не многопоточны, тогда избегайте Vector.Даже если это так, детализация синхронизации обычно неправильна, и вам лучше обеспечить безопасность потоков самостоятельно.

3) Делайте API-интерфейсы коллекций подобными коллекциям Google, трюкам Java (например, отражению и приведению)и другие распространенные идиомы разработчика Java, как правило, замедляют JVM, когда он находится под большой нагрузкой?

Отражение медленное;сборка мусора идет медленно.Все, что вы можете сделать, чтобы избежать этого, ускорит процесс.

4) Замедляют ли примитивы или обычные объекты (например, Double против Double) JVM при выполнении большого количества вычислений?

Да.Автобокс / распаковка может очень быстро создать огромное количество мусора.Все это нужно собрать, что также замедлит вашу программу.

5) Существуют ли другие важные рекомендации для работы с большими коллекциями в программах Java, которые должны быть высокопроизводительными?

Предпочитать переменные локального метода доступу к полю.Вы можете найти много других рекомендаций, выполнив поиск в Интернете.Но главное - это профиль.

Редактировать: Здесь есть хорошая коллекция подсказок по производительности здесь .

8 голосов
/ 18 ноября 2011

Чтобы ответить на ваш 4) Да, Двойной против двойной определенно меняет спектакли

Когда у вас есть коллекции, состоящие из примитивов, вы, безусловно, можете использовать коллекции, поддерживаемые примитивами, например очень хороший Trove API. Избегая постоянного примитива к объекту и наоборот (не) бокса, вы экономите память и драгоценное время.

Кроме того, класс Vector уже давно ушел в прошлое.

3 голосов
/ 18 ноября 2011

1) Если вам не требуется действительно динамическое изменение размера или вы можете разместить свои данные в достаточно маленьком контейнере «максимального размера», то вы получите более высокую производительность при произвольном доступе из массивов, чем из коллекций, благодаряудаление накладных расходов на вызов метода и, возможно, больше (в зависимости от используемых коллекций).

2) Векторы и Hashtables следует рассматривать почти так, как будто они устарели, на мой взгляд.Они «поточнобезопасны», но для большинства реальных сценариев просто иметь саму структуру данных в поточно-ориентированном виде недостаточно;обычно логика вашего приложения также должна быть частью этой синхронизации.ArrayList, HashMap будет работать лучше, поскольку у них нет синхронизированных блоков, которые в 99,9% случаев не приносят вам никакой пользы.

3) API коллекций Google великолепны, реальных проблем с производительностью нет.Отражение определенно медленное и не должно быть во внутренних циклах.

4) В идеале вы хотели бы избежать упаковки / распаковки примитивов во внутренних циклах.Вы можете найти коллекции, которые специально настроены на примитивы (например, коллекции Trove http://trove.starlight -systems.com / ).

5) Это зависит от конкретного использования, я бы не сталСкажите, что есть какие-то общие рекомендации.Просто убедитесь, что вы понимаете, что делаете при преобразовании коллекций и т. Д. Например, убедитесь, что он не клонирует всю коллекцию при преобразовании списка в набор или что-то в этом роде.

2 голосов
/ 18 ноября 2011
  1. Я считаю, что единственный раз, когда вы должны использовать Vector, - это когда вам нужно синхронизировать его, но вы можете использовать специальную синхронизированную вещь в ArrayList, поэтому я бы сказал, что Vector не нужен. Всегда используйте ArrayList вместо LinkedList. Он отличается от здравого смысла, поэтому он должен быть реализацией Java, но ArrayList работает намного быстрее. Раньше я верил в LinkedList, поэтому создал следующий тест:

    import java.util.ArrayList; import java.util.GregorianCalendar; import java.util.LinkedList; import java.util.List; import java.util.Random;

/ ** * * /

/ ** * @author thom * * / открытый класс ListTest {

private ArrayList<Integer>      arrayList = new ArrayList<Integer>();
private LinkedList<Integer>     linkedList = new LinkedList<Integer>();

/**
 * 
 */
public void test(){
    LinkedList<Integer> arrayTimes = new LinkedList<Integer>();
    LinkedList<Integer> linkedTimes = new LinkedList<Integer>();

    for(int ix = 0; ix < 100; ix ++){
        arrayList.clear();
        long start = new GregorianCalendar().getTimeInMillis();
        fillList(arrayList);
        long stop = new GregorianCalendar().getTimeInMillis();
        int elapsed = (int) (stop - start);
        arrayTimes.add(elapsed);
    }

    for(int ix = 0; ix < 100; ix ++){
        linkedList.clear();
        long start = new GregorianCalendar().getTimeInMillis();
        fillList(linkedList);
        long stop = new GregorianCalendar().getTimeInMillis();
        int elapsed = (int) (stop - start);
        linkedTimes.add(elapsed);
    }

    double arrayAvg = avg(arrayTimes);
    double linkedAvg = avg(linkedTimes);

    System.err.println("Adding 100,000 entries 100 times to linked list.");
    System.err.println("ArrayList elapsed time (ms.):" + arrayAvg);
    System.err.println("LinkedList elapsed time (ms.):" + linkedAvg);

    arrayTimes.clear();
    linkedTimes.clear();

    long start = new GregorianCalendar().getTimeInMillis();
    insertMiddle(arrayList);
    long stop = new GregorianCalendar().getTimeInMillis();
    int elapsed = (int) (stop - start);

    System.err.println();
    System.err.println("Inserting 1,000 entries to the middle of the list.");
    System.err.println("ArrayList elapsed time (ms.):" + elapsed);

    start = new GregorianCalendar().getTimeInMillis();
    insertMiddle(linkedList);
    stop = new GregorianCalendar().getTimeInMillis();
    elapsed = (int) (stop - start);
    System.err.println("LinkedList elapsed time (ms.):" + elapsed);

    start = new GregorianCalendar().getTimeInMillis();
    for(int ix = 0; ix < 100; ++ix){
        for(int jx = 0; jx < 100000; ++jx){
            arrayList.get(jx);
        }
    }
    stop = new GregorianCalendar().getTimeInMillis();
    elapsed = (int) (stop - start);

    System.err.println();
    System.err.println("Sequentially reading the list 100 times");
    System.err.println("ArrayList elapsed time (ms.):" + elapsed);

    start = new GregorianCalendar().getTimeInMillis();
    for(int ix = 0; ix < 100; ++ix){
        for(int jx = 0; jx < 100000; ++jx){
            linkedList.get(jx);
        }
    }
    stop = new GregorianCalendar().getTimeInMillis();
    elapsed = (int) (stop - start);
    System.err.println("LinkedList elapsed time (ms.):" + elapsed);

    Random rnd = new Random();
    start = new GregorianCalendar().getTimeInMillis();
    for(int ix = 0; ix < 100; ++ix){
        for(int jx = 0; jx < 100000; ++jx){
            int index = rnd.nextInt(100000);
            arrayList.get(index);
        }
    }
    stop = new GregorianCalendar().getTimeInMillis();
    elapsed = (int) (stop - start);

    System.err.println();
    System.err.println("Randomly reading the list 100 times");
    System.err.println("ArrayList elapsed time (ms.):" + elapsed);

    start = new GregorianCalendar().getTimeInMillis();
    for(int ix = 0; ix < 100; ++ix){
        for(int jx = 0; jx < 100000; ++jx){
            int index = rnd.nextInt(100000);
            linkedList.get(index);
        }
    }
    stop = new GregorianCalendar().getTimeInMillis();
    elapsed = (int) (stop - start);
    System.err.println("LinkedList elapsed time (ms.):" + elapsed);
}

/**
 * @param values
 */
protected double avg(List<Integer> values){
    double sum = 0;
    for(int ix:values){
        sum += ix;
    }

    double result = sum / values.size();
    return result;
}

/**
 * @param list
 */
protected void fillList(List<Integer> list){
    for(int ix = 0; ix < 100000; ix++){
        list.add(ix);
    }
}

/**
 * @param list
 */
protected void insertMiddle(List<Integer> list){
    for(int ix = 0; ix < 1000; ix++){
        list.add(50000, ix);
    }
}

/**
 * @param args
 */
public static void main(String[] args) {
    ListTest listTest = new ListTest();
    listTest.test();
}

}

И это дало следующие результаты:

Adding 100,000 entries 100 times to linked list.
ArrayList elapsed time (ms.):2.78
LinkedList elapsed time (ms.):12.24

Inserting 1,000 entries to the middle of the list.
ArrayList elapsed time (ms.):35
LinkedList elapsed time (ms.):154

Sequentially reading the list 100 times
ArrayList elapsed time (ms.):94
LinkedList elapsed time (ms.):748271

Randomly reading the list 100 times
ArrayList elapsed time (ms.):404
LinkedList elapsed time (ms.):1158273

Кто-то, пожалуйста, проверьте мой код, чтобы убедиться, что я не сделал что-то глупое, но это показывает, что ArrayList ОЧЕНЬ быстрее, чем LinkedList для всех.

  1. Отражение определенно медленное.

  2. Примитивы намного быстрее для расчетов. Будьте осторожны с автобоксом, так как это хит производительности. Это приятно, просто убедитесь, что вы понимаете стоимость.

1 голос
/ 18 ноября 2011

ИМХО первое и главное правило - выбрать правильную структуру для вашего варианта использования.

Использование карты для реализации словаря может быть полезным для производительности (времени), поскольку потребует много памяти (пространства), вместо этого используйте Trie .

Поиск по хешу (с использованием HashMap) хорош, но если у вас есть ключ с конечным числовым диапазоном, массив будет работать лучше.

Единственное эмпирическое правило, которое я рекомендую, - это разработать собственную структуру данных, когда вам приходится иметь дело с ГБ данных и / или требованиями "отклик в микросекундах".

1 голос
/ 18 ноября 2011

1) Если вы знаете максимальный размер, используйте массивы.

2) Векторы имеют синхронизированные методы, поэтому работают медленнее, чем ArrayLists.Есть разница.В последнее время наблюдается тенденция использовать Collections.synchronizedList вместо векторов.

3) Существует несколько реализаций "быстрых" коллекций, например http://labs.carrotsearch.com/hppc.html или Trove, другие Какая библиотека Java Collections наиболее эффективна?

4) Если можете, используйте примитив.Обертки приносят дополнительные издержки.

5) Подумайте, что вам нужно сделать, какие действия будут выполняться чаще всего, например, добавление элемента в set медленнее, чем для arraylist, итерация по arraylist быстрее, чем в set.Однако удаление элементов из массива происходит медленнее, чем в наборе.Когда это возможно, используйте массивы - они будут быстрее, чем любая другая коллекция.Если вам нужно использовать коллекцию, но вы приблизительно знаете, сколько элементов будет вставлено, используйте конструктор с начальным размером.

0 голосов
/ 18 ноября 2011

Еще один маленький трюк:

Если вы работаете с действительно большими коллекциями и заранее знаете (или можете оценить) их размер, вам следует использовать конструкторы, которые позволяют вам указатьначальная емкость.Это позволяет избежать нескольких распределений массивов.

0 голосов
/ 18 ноября 2011

Вам нужен прямой доступ к данным, и если да, то точно ли вы сейчас располагаете объекты? Если вы все время просматриваете коллекцию, чтобы выяснить, где находится объект, который вам нужен, это займет некоторое время (и поэтому прямой доступ будет иметь преимущество)

Кроме того, автоматический бокс требует времени, и поскольку вы не можете создавать коллекции примитивных типов, они будут автоматически помещаться в их родственников.

...