В какой момент стоит повторно использовать массивы в Java?

Question

Насколько большим должен быть буфер в Java, чтобы его можно было повторно использовать?

Или, говоря по-другому: я могу многократно распределять, использовать и отбрасывать объекты byte [] ИЛИ запускать пул для их сохранения и повторного использования. Я мог бы выделить много маленьких буферов, которые часто сбрасываются, или несколько больших, которых нет. В каком размере дешевле их объединить, чем перераспределить, и как небольшие выделения сравниваются с большими?

EDIT:

Хорошо, конкретные параметры. Скажем, процессор Intel Core 2 Duo, последняя версия виртуальной машины для выбранной ОС. Эти вопросы не так расплывчаты, как кажется ... небольшой код и график могут ответить на них.

EDIT2:

Вы опубликовали много хороших общих правил и обсуждений, но вопрос действительно требует цифр. Опубликуйте их (и код тоже)! Теория великолепна, но доказательством являются цифры. Не имеет значения, отличаются ли результаты от системы к системе, я просто ищу приблизительную оценку (на порядок). Никто, кажется, не знает, будет ли разница в производительности в 1,1, 2, 10 или 100+ раз, и это то, что имеет значение. Это важно для любого кода Java, работающего с большими массивами - сети, биоинформатика и т. Д.

Предложения, чтобы получить хороший тест:

1. Прогрейте код перед запуском в тесте. Все методы должны вызываться как минимум 1000 10000 раз, чтобы получить полную оптимизацию JIT.
2. Убедитесь, что тестируемые методы выполняются не менее 1 10 секунд и, если возможно, используйте System.nanotime, чтобы получить точные значения времени.
3. Запуск бенчмарка в системе, в которой работают только минимальные приложения
4. Запустите бенчмарк 3-5 раз и все время отчитывайтесь, чтобы мы увидели, насколько он последовательный.

---

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

Что я знаю (и мне не нужно повторяться):

• Выделение памяти Java и сборщик мусора происходят быстро и быстро.
• Объединение объектов раньше было хорошей оптимизацией, но теперь это в большинстве случаев снижает производительность.
• Объединение объектов «обычно не является хорошей идеей, если объекты не дороги в создании». Ядда Ядда.

Что я не знаю:

• Как быстро следует ожидать выделения памяти (МБ / с) на стандартном современном ЦП?
• Как размер распределения влияет на скорость распределения?
• Какова точка безубыточности для количества / размера распределений по сравнению с повторным использованием в пуле?

Маршруты к принятому ответу (чем больше, тем лучше):

• Недавний технический документ, показывающий цифры для распределения и GC на современных процессорах (последние, как в прошлом году или около того, JVM 1.6 или позже)
• Код для краткого и правильного микропробега, который я могу запустить
• Объяснение того, как и почему распределение влияет на производительность
• Реальные примеры / анекдоты от тестирования этого вида оптимизации

Контекст:

Я работаю над библиотекой, добавляющей поддержку сжатия LZF в Java. Эта библиотека расширяет классы H2 СУБД LZF, добавляя дополнительные уровни сжатия (большее сжатие) и совместимость с потоками байтов из библиотеки C LZF. Я думаю о том, стоит ли пытаться повторно использовать буферы фиксированного размера, используемые для сжатия / распаковки потоков. Буферы могут быть ~ 8 кБ или ~ 32 кБ, а в оригинальной версии они ~ 128 кБ. Буферы могут быть выделены один или несколько раз на поток. Я пытаюсь понять, как я хочу обрабатывать буферы для достижения наилучшей производительности, с перспективой на потенциальную многопоточность в будущем.

Да, библиотека будет выпущена с открытым исходным кодом, если кто-то заинтересован в ее использовании.

Answer 1

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

Как быстро следует ожидать выделения памяти (МБ / с) на стандартном современном ЦП?

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

Как размер распределения влияет на скорость распределения?

См. Выше.

Какова точка безубыточности для количества / размера распределений по сравнению с повторным использованием в пуле?

Если вы хотите простой ответ, значит, простого ответа не существует.

Золотое правило гласит: чем больше ваша куча (вплоть до объема доступной физической памяти), тем меньше амортизируемая стоимость сбора мусора. При быстром копировании сборщика мусора амортизированная стоимость освобождения мусорного объекта приближается к нулю, когда куча увеличивается. Стоимость GC фактически определяется (в упрощенном виде) количеством и размером объектов без мусора, с которыми GC имеет дело.

В предположении, что ваша куча велика, стоимость жизненного цикла выделения и GC'а большого объекта (в одном цикле GC) приближается к стоимости обнуления памяти при выделении объекта.

EDIT : Если вам нужны только простые числа, напишите простое приложение, которое распределяет и отбрасывает большие буферы, и запускайте его на своем компьютере с различными параметрами GC и кучи и смотрите, что происходит. Но имейте в виду, что это не даст вам реалистичного ответа, потому что реальные затраты на сборку мусора зависят от объектов, не являющихся мусором приложения.

Я не собираюсь писать для вас тест, потому что Я знаю , что он даст вам поддельные ответы.

РЕДАКТИРОВАТЬ 2 : в ответ на комментарии ОП.

Итак, я должен ожидать, что распределение будет выполняться так же быстро, как System.arraycopy или цикл инициализации массива JITed (около 1 ГБ / с на моем последнем тесте, но я сомневаюсь в результате)?

Теоретически да. На практике это трудно измерить таким образом, чтобы отделить затраты на распределение от затрат на сборщик мусора.

По размеру кучи, вы говорите, что выделение большего объема памяти для использования JVM фактически снизит производительность?

Нет, я говорю, что это может увеличить производительность. Значительно. (При условии, что вы не столкнетесь с эффектами виртуальной памяти на уровне ОС.)

Распределения предназначены только для массивов, и почти все остальное в моем коде выполняется в стеке. Это должно упростить измерение и прогнозирование производительности.

Может быть. Честно говоря, я думаю, что вы не добьетесь большого улучшения за счет утилизации буферов.

Но если вы собираетесь пойти по этому пути, создайте пул буферов interface с двумя реализациями. Первый - это реальный потокобезопасный пул буферов, который перезапускает буферы. Второй - фиктивный пул, который просто выделяет новый буфер каждый раз, когда вызывается alloc, и обрабатывает dispose как неработоспособный. Наконец, позвольте разработчику приложения выбирать между реализациями пула с помощью метода setBufferPool и / или параметров конструктора и / или свойств конфигурации времени выполнения. Приложение также должно иметь возможность предоставлять класс / экземпляр пула буферов своего собственного создания.

Answer 2

Когда оно больше молодого пространства.

Если ваш массив больше локального молодого пространства потока, он непосредственно выделяется в старом пространстве. Сборка мусора на старом пространстве намного медленнее, чем на молодом. Так что, если ваш массив больше, чем молодое пространство, возможно, имеет смысл использовать его повторно.

На моей машине 32 КБ превосходит молодое пространство. Поэтому имеет смысл использовать его повторно.

Answer 3

Ответ от совершенно другого направления: пусть решит пользователь вашей библиотеки.

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

Итак, создайте механизм объединения в виде интерфейса и на основе какого-либо параметра конфигурации выберите реализацию, используемую вашей библиотекой. Установите значение по умолчанию равным тому, что ваши тесты производительности определят как лучшее решение. ¹ И да, если вы используете интерфейс, вам придется полагаться на то, что JVM будет достаточно умна для внутренних вызовов. ²

---

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

(2) Это может привести вас к еще одной дискуссии об относительной эффективности различных кодов invoke .

Answer 4

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

Answer 5

Краткий ответ: не буферизировать.

Причины следующие:

• Не оптимизируйте его, пока оно не станет узким местом
• Если вы перезапустите его, накладные расходы на управление пулом станут еще одним узким местом
• Попробуй довериться JIT. В последней JVM ваш массив может размещаться в STACK, а не в HEAP.
• Поверь мне, JRE обычно справляются с ними быстрее и лучше, чем ты сам.
• Сохраняйте это простым, чтобы легче было читать и отлаживать

Когда вы должны утилизировать объект:

• только если он тяжелый. Размер памяти не сделает его тяжелым, но это делают собственные ресурсы и цикл ЦП, что приводит к завершению сложения стоимости и циклу ЦП.
• Возможно, вы захотите утилизировать их, если они являются «ByteBuffer», а не byte []

Answer 6

Я наткнулся на этот поток и, поскольку я реализовывал алгоритм связности всех пар Флойд-Варшалла на графе с тысячей вершин, я пытался реализовать его обоими способами (повторно используя матрицы или создание новых) и проверьте прошедшее время.

Для вычислений мне нужно 1000 различных матриц размером 1000 x 1000, так что это неплохой тест.

Моя система - Ubuntu Linux со следующей виртуальной машиной.

java version "1.7.0_65"
Java(TM) SE Runtime Environment (build 1.7.0_65-b17)
Java HotSpot(TM) 64-Bit Server VM (build 24.65-b04, mixed mode)

Повторное использование матриц было примерно на 10% медленнее (среднее время выполнения за 5 выполнений 17354 мс против 15708 мс. Я не знаю, будет ли оно все еще быстрее, если бы матрица была намного больше.

Вот соответствующий код:

private void computeSolutionCreatingNewMatrices() {
    computeBaseCase();
    smallest = Integer.MAX_VALUE;
    for (int k = 1; k <= nVertices; k++) {
        current = new int[nVertices + 1][nVertices + 1];
        for (int i = 1; i <= nVertices; i++) {
            for (int j = 1; j <= nVertices; j++) {
                if (previous[i][k] != Integer.MAX_VALUE && previous[k][j] != Integer.MAX_VALUE) {
                    current[i][j] = Math.min(previous[i][j], previous[i][k] + previous[k][j]);
                } else {
                    current[i][j] = previous[i][j];
                }
                smallest = Math.min(smallest, current[i][j]);
            }
        }
        previous = current;
    }
}

private void computeSolutionReusingMatrices() {
    computeBaseCase();
    current = new int[nVertices + 1][nVertices + 1];
    smallest = Integer.MAX_VALUE;
    for (int k = 1; k <= nVertices; k++) {            
        for (int i = 1; i <= nVertices; i++) {
            for (int j = 1; j <= nVertices; j++) {
                if (previous[i][k] != Integer.MAX_VALUE && previous[k][j] != Integer.MAX_VALUE) {
                    current[i][j] = Math.min(previous[i][j], previous[i][k] + previous[k][j]);
                } else {
                    current[i][j] = previous[i][j];
                }
                smallest = Math.min(smallest, current[i][j]);
            }
        }
        matrixCopy(current, previous);
    }
}

private void matrixCopy(int[][] source, int[][] destination) {
    assert source.length == destination.length : "matrix sizes must be the same";
    for (int i = 0; i < source.length; i++) {
        assert source[i].length == destination[i].length : "matrix sizes must be the same";
        System.arraycopy(source[i], 0, destination[i], 0, source[i].length);
    }        
}

Answer 7

Глядя на микропроцессор (код ниже), нет заметной разницы во времени на моей машине, независимо от размера и времени использования массива (я не публикую время, вы можете легко запустить его на своей машине: -). Я подозреваю, что это потому, что мусор жив так короткое время, что нечего делать для очистки. Распределение массива должно, вероятно, вызывать calloc или malloc / memset. В зависимости от процессора это будет очень быстрая операция. Если массивы выжили в течение более длительного времени, чтобы преодолеть начальную область GC (питомник), то время для того, кто выделил несколько массивов, может занять немного больше времени.

код:

import java.util.Random;

public class Main
{
    public static void main(String[] args) 
    {
        final int size;
        final int times;

        size  = 1024 * 128;
        times = 100;

        // uncomment only one of the ones below for each run
        test(new NewTester(size), times);   
//        test(new ReuseTester(size), times); 
    }

    private static void test(final Tester tester, final int times)
    {
        final long total;

        // warmup
        testIt(tester, 1000);
        total = testIt(tester, times);

        System.out.println("took:   " + total);
    }

    private static long testIt(final Tester tester, final int times)
    {
        long total;

        total = 0;

        for(int i = 0; i < times; i++)
        {
            final long start;
            final long end;
            final int value;

            start = System.nanoTime();
            value = tester.run();
            end   = System.nanoTime();
            total += (end - start);

            // make sure the value is used so the VM cannot optimize too much
            System.out.println(value);
        }

        return (total);
    }
}

interface Tester
{
    int run();
}

abstract class AbstractTester
    implements Tester
{
    protected final Random random;

    {
        random = new Random(0);
    }

    public final int run()
    {
        int value;

        value = 0;

        // make sure the random number generater always has the same work to do
        random.setSeed(0);

        // make sure that we have something to return so the VM cannot optimize the code out of existence.
        value += doRun();

        return (value);
    }

    protected abstract int doRun();
}

class ReuseTester
    extends AbstractTester
{
    private final int[] array;

    ReuseTester(final int size)
    {
        array = new int[size];
    }

    public int doRun()
    {
        final int size;

        // make sure the lookup of the array.length happens once
        size = array.length;

        for(int i = 0; i < size; i++)
        {
            array[i] = random.nextInt();
        }

        return (array[size - 1]);
    }
}

class NewTester
    extends AbstractTester
{
    private int[] array;
    private final int length;

    NewTester(final int size)
    {
        length = size;
    }

    public int doRun()
    {
        final int   size;

        // make sure the lookup of the length happens once
        size = length;
        array = new int[size];

        for(int i = 0; i < size; i++)
        {
            array[i] = random.nextInt();
        }

        return (array[size - 1]);
    }
}

Answer 8

Я забыл, что это система с управляемой памятью.

На самом деле, вы, вероятно, ошиблись. Надлежащий способ определить, когда он полезен, зависит от приложения, системы, в которой он работает, и модели использования пользователя.

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

Вы, вероятно, обнаружите, что gc даже не вызывается вообще. Поэтому написание кода для его оптимизации было бы пустой тратой времени.

с сегодняшним большим объемом памяти, я подозреваю, что 90% времени это вообще не стоит делать. Вы не можете определить это по параметрам - это слишком сложно. Просто профиль - просто и точно.

Answer 9

Имейте в виду, что эффекты кэша, вероятно, будут более серьезной проблемой, чем стоимость "new int [size]" и соответствующей коллекции. Поэтому повторное использование буферов - хорошая идея, если у вас хорошая временная локализация. Перераспределение буфера вместо его повторного использования означает, что вы можете каждый раз получать новый фрагмент памяти. Как уже упоминалось, это особенно верно, когда ваши буферы не вписываются в молодое поколение.

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

Answer 10

Я думаю, что вам нужен ответ, связанный с «порядком» (измерением пространства, а не времени!) Алгоритма.

Пример копирования файла

Например, если вы хотите скопировать файл, вам нужно прочитать из входного потока и записать в выходной поток. Порядок TIME равен O (n), потому что время будет пропорционально размеру файла. Но порядок SPACE будет O (1), потому что программа, которая вам понадобится, будет занимать фиксированный объем памяти (вам понадобится только один фиксированный буфер). В этом случае ясно, что удобно повторно использовать тот самый буфер, который вы создали в начале программы.

Свяжите политику буфера с вашей структурой выполнения алгоритма

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

• попробуйте исправить размер буферов (даже жертвуя немного памяти).
• Попробуй посмотреть, как устроена выполнение: например, если вы алгоритм пересекает какое-то дерево и вы буферы связаны с каждый узел, может быть, вам нужен только O (журнал п) буферы ... так что вы можете сделать обоснованное предположение о необходимом пространстве.
• Также, если вам нужны разные буферы, но Вы можете организовать вещи, чтобы поделиться разные сегменты одного и того же массив ... может быть, лучше решение.
• Когда вы освобождаете буфер, вы можете добавьте его в пул буферов. Тот бассейн может быть куча, заказанная «подходящие» критерии (буферы, которые Подходит больше всего должно быть первым).

То, что я пытаюсь сказать, это: нет точного ответа. Если вы создали что-то, что вы можете использовать повторно ... вероятно, лучше использовать это снова. Сложность состоит в том, чтобы найти, как вы можете сделать это без лишних затрат на управление буфером. Вот когда пригодится алгоритм анализа.

Надеюсь, это поможет ...:)