Добавление () против добавления addAll() в Java PriorityHeap

Question

Я изучаю различные возможности добавления значений в кучу в Java. Я использую PriorityHeap учебный класс. Когда я заметил медленное время выполнения в моем приложении, я решил взглянуть на это. Я добавляю несколько тысяч, а иногда и миллионы пользовательских записей (у меня есть собственный класс, который имеет 3 поля: int, LongWritable и Text, оба из hadoop.io; этот инструментальный агент говорит, что мои записи имеют в среднем 200 байт).

Очевидно ли, что использование addAll() вместо add() способ поместить записи в кучу улучшит производительность, просто потому что это позволит избежать нескольких heapify операции?

Я пытался с разными стратегиями, используя следующий новый пример:

package Sorting;

import java.io.IOException;
import java.util.ArrayList;
import java.util.List;
import java.util.PriorityQueue;

public class Main {

private static final int HEAP_SIZE = 1000000;
private static final int BULK_LIST_SIZE = HEAP_SIZE / 10;

private static String normal;
private static String bulk;
private static String fullBulk;

public static void main(String[] args) throws IOException {
normal = "";
bulk = "";
fullBulk = "";
long time = 0;

warmup();

normal = "";
bulk = "";
fullBulk = "";

for (int i = 0; i < 100; i++) {

    // Normal add time
    System.out.println("Normal starts...");
    time = normalExecution();
    System.out.println("Normal add time " + time);

    // Bulk add time
    System.out.println("Bulk starts...");
    time = bulk();
    System.out.println("Bulk add time " + time);

    // Bulk add time with list and heap with same size
    System.out.println("Full Bulk starts...");
    time = fullBulk();
    System.out.println("Full Bulk add time " + time);
}
System.out.println(normal);
System.out.println(bulk);
System.out.println(fullBulk);

}

private static long fullBulk() {
long time;
long start;
List<Double> fullBulkList = new ArrayList<Double>(HEAP_SIZE);
PriorityQueue<Double> fullBulkHeap = new PriorityQueue<Double>(HEAP_SIZE);

start = System.nanoTime();
for (int j = 0; j < HEAP_SIZE; j++) {
    if (fullBulkList.size() == HEAP_SIZE) {
    fullBulkHeap.addAll(fullBulkList);
    fullBulkList.clear();
    }
}
fullBulkHeap.addAll(fullBulkList);
time = System.nanoTime() - start;

fullBulk = fullBulk + "\t" + time;
fullBulkList = null;
fullBulkHeap = null;
return time;
}

private static long bulk() {
long time;
long start;
List<Double> bulkList = new ArrayList<Double>(BULK_LIST_SIZE);
PriorityQueue<Double> bulkHeap = new PriorityQueue<Double>(HEAP_SIZE);
start = System.nanoTime();
for (int j = 0; j < HEAP_SIZE; j++) {
    if (bulkList.size() == BULK_LIST_SIZE) {
    bulkHeap.addAll(bulkList);
    bulkList.clear();
    }
}
bulkHeap.addAll(bulkList);
time = System.nanoTime() - start;
bulk = bulk + "\t" + time;
bulkList = null;
bulkHeap = null;
return time;
}

private static long normalExecution() {

long time;
long start;
PriorityQueue<Double> normalHeap = new PriorityQueue<Double>(HEAP_SIZE);
start = System.nanoTime();
for (int j = 0; j < HEAP_SIZE; j++) {
    normalHeap.add(Double.MAX_VALUE);
}
time = System.nanoTime() - start;
normal = normal + "\t" + time;
normalHeap = null;
return time;
}

private static void warmup() {
System.out.println("Starting warmup");
for (int i = 0; i < 1000; i++) {
    normalExecution();
    bulk();
    fullBulk();
}
for (int i = 0; i < 1000; i++) {

    bulk();
    fullBulk();
    normalExecution();
}
for (int i = 0; i < 1000; i++) {

    fullBulk();
    normalExecution();
    bulk();
}
System.out.println("Warmup finished");
}

}

Что привело к следующим результатам:

Огромный пик в 11-й итерации обычного метода add объясняется вызовом GC: [GC 1347684K->31354K(1446400K), 0.0331610 secs],

Медиа-значения - 16049669, 783724 и 800276 соответственно. ST dev составляют 3512492,89, 244374,17 и 33344,17.

Answer 1

PriorityQueue не переопределяет метод addAll унаследованный от AbstractQueue,

В AbstractQueue этот метод выглядит следующим образом.

public boolean addAll(Collection<? extends E> c) {
    if (c == null)
        throw new NullPointerException();
    if (c == this)
        throw new IllegalArgumentException();
    boolean modified = false;
    for (E e : c)
        if (add(e))
            modified = true;
    return modified;
}

Как видите, он просто зацикливается и вызывает add,

Так что я не думаю addAll улучшит что-нибудь по сравнению с add,