можно ли оптимизировать доступ к массиву?

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

Единственное, что, как я ожидаю, может иметь некоторое значение, — это перемещение ключа из массива значений Entry.

Вместо этого:

class Entry {
    long[] values;
}

//...
if ( entry.values[key_index] == key ) { //...

Попробуй это:

class Entry {
    long key;
    long values[];
}

//...
if ( entry.key == key ) { //...

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

Есть ли тип данных с произвольным доступом быстрее, чем массив?

Меня интересовал ответ на этот вопрос, поэтому я настроил тестовую среду. Это мой интерфейс массива:

interface Array {
    long get(int i);
    void set(int i, long v);
}

Этот «массив» имеет неопределенное поведение, когда индексы выходят за пределы. Я собрал очевидную реализацию:

class NormalArray implements Array {
    private long[] data;

    public NormalArray(int size) {
        data = new long[size];
    }

    @Override
    public long get(int i) {
        return data[i];
    }

    @Override
    public void set(int i, long v) {
        data[i] = v;
    }
}

И затем контроль:

class NoOpArray implements Array {
    @Override
    public long get(int i) {
        return 0;
    }
    @Override
    public void set(int i, long v) {
    }
}

Наконец, я разработал «массив», в котором первые 10 индексов являются жестко заданными членами. Члены устанавливаются/выбираются с помощью переключателя:

class TenArray implements Array {
    private long v0;
    private long v1;
    private long v2;
    private long v3;
    private long v4;
    private long v5;
    private long v6;
    private long v7;
    private long v8;
    private long v9;
    private long[] extras;

    public TenArray(int size) {
        if (size > 10) {
            extras = new long[size - 10];
        }
    }

    @Override
    public long get(final int i) {
        switch (i) {
        case 0:
            return v0;
        case 1:
            return v1;
        case 2:
            return v2;
        case 3:
            return v3;
        case 4:
            return v4;
        case 5:
            return v5;
        case 6:
            return v6;
        case 7:
            return v7;
        case 8:
            return v8;
        case 9:
            return v9;
        default:
            return extras[i - 10];
        }
    }

    @Override
    public void set(final int i, final long v) {
        switch (i) {
        case 0:
            v0 = v; break;
        case 1:
            v1 = v; break;
        case 2:
            v2 = v; break;
        case 3:
            v3 = v; break;
        case 4:
            v4 = v; break;
        case 5:
            v5 = v; break;
        case 6:
            v6 = v; break;
        case 7:
            v7 = v; break;
        case 8:
            v8 = v; break;
        case 9:
            v9 = v; break;
        default:
            extras[i - 10] = v;
        }
    }
}

Я тестировал это с помощью этого ремня:

import java.util.Random;

public class ArrayOptimization {
    public static void main(String[] args) {
        int size = 10;
        long[] data = new long[size];
        Random r = new Random();
        for ( int i = 0; i < data.length; i++ ) {
            data[i] = r.nextLong();
        }

        Array[] a = new Array[] {
                new NoOpArray(),
                new NormalArray(size),
                new TenArray(size)
        };

        for (;;) {
            for ( int i = 0; i < a.length; i++ ) {
                testSet(a[i], data, 10000000);
                testGet(a[i], data, 10000000);
            }
        }
    }

    private static void testGet(Array a, long[] data, int iterations) {
            long nanos = System.nanoTime();
        for ( int i = 0; i < iterations; i++ ) {
            for ( int j = 0; j < data.length; j++ ) {
                data[j] = a.get(j);
            }
        }
        long stop = System.nanoTime();
        System.out.printf("%s/get took %fms%n", a.getClass().getName(), 
                (stop - nanos) / 1000000.0);
    }

    private static void testSet(Array a, long[] data, int iterations) {
        long nanos = System.nanoTime();
        for ( int i = 0; i < iterations; i++ ) {
            for ( int j = 0; j < data.length; j++ ) {
                a.set(j, data[j]);
            }
        }
        long stop = System.nanoTime();
        System.out.printf("%s/set took %fms%n", a.getClass().getName(), 
                (stop - nanos) / 1000000.0);

    }
}

Результаты несколько удивили. TenArray работает нетривиально быстрее, чем NormalArray (для размеров ‹= 10). Вычитая накладные расходы (используя среднее значение NoOpArray), вы получаете TenArray, занимающий ~ 65% времени обычного массива. Итак, если вы знаете вероятный максимальный размер вашего массива, я полагаю, что можно превысить скорость массива. Я бы предположил, что переключатель использует либо меньшую проверку границ, либо более эффективную проверку границ, чем массив.

NoOpArray/set took 953.272654ms
NoOpArray/get took 891.514622ms
NormalArray/set took 1235.694953ms
NormalArray/get took 1148.091061ms
TenArray/set took 1149.833109ms
TenArray/get took 1054.040459ms
NoOpArray/set took 948.458667ms
NoOpArray/get took 888.618223ms
NormalArray/set took 1232.554749ms
NormalArray/get took 1120.333771ms
TenArray/set took 1153.505578ms
TenArray/get took 1056.665337ms
NoOpArray/set took 955.812843ms
NoOpArray/get took 893.398847ms
NormalArray/set took 1237.358472ms
NormalArray/get took 1125.100537ms
TenArray/set took 1150.901231ms
TenArray/get took 1057.867936ms

Теперь, можете ли вы на практике получить скорость быстрее, чем массив, я не уверен; очевидно, что таким образом вы несете любые накладные расходы, связанные с интерфейсом/классом/методами.

Скорее всего, вы частично заблуждаетесь в своей интерпретации результатов профайлеров. Профилировщики, как известно, преувеличивают влияние на производительность небольших, часто вызываемых методов. В вашем случае накладные расходы на профилирование для метода get(), вероятно, больше, чем фактическая обработка, затраченная на сам метод. Ситуация усугубляется еще и тем, что инструментирование также препятствует способности JIT встраивать методы.

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

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

Проверка границ массива может оказать на удивление большое влияние на производительность (если вы делаете сравнительно мало других действий), но ее также может быть трудно четко отделить от общих штрафов за доступ к памяти. В некоторых тривиальных случаях JIT может устранить их (были попытки исключить проверку границ в Java 6), но, насколько мне известно, это в основном ограничивается простыми конструкциями цикла, такими как for(x=0; x‹array.length; х++). При некоторых обстоятельствах вы можете заменить доступ к массиву простым доступом к членам, полностью избегая связанных проверок, но это ограничено редкими случаями, когда вы получаете доступ к массиву исключительно с помощью постоянных индексов. Я не вижу способа применить это к вашей проблеме.

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

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

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

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

• Во-вторых, то, что я подразумеваю под «активным», находится «в стеке», где стек включает текущую выполняющуюся инструкцию и все вызовы «выше» ее обратно в «вызов основного». Если подпрограмма отвечает за 10% времени, включая подпрограммы, которые она вызывает, то в течение этого времени она находится в стеке. То же самое относится и к отдельным заявлениям или даже инструкциям. (Игнорируйте «время на себя» или «эксклюзивное время». Это отвлечение.)

• Профилировщики, которые помещают таймеры и счетчики в функции, могут дать вам только часть этой информации. Профилировщики, которые только проверяют счетчик программ, говорят вам еще меньше. Что вам нужно, так это что-то, что сэмплирует стек вызовов и сообщает вам по строке (а не только по функции) процент сэмплов стека, содержащих эту строку. Также важно, чтобы они выполняли выборку стека а) во время ввода-вывода или другой блокировки, но б) не во время ожидания ввода данных пользователем.

Есть профилировщики, которые могут это сделать. Я не уверен в Java.

Если ты все еще со мной, позволь мне выкинуть еще один звонок. Вы ищете вещи, которые можно оптимизировать, верно? и только то, что имеет достаточно большой процент, чтобы окупиться, например, 10% или больше? Такая строка кода стоимостью 10% находится в стеке 10% времени. Это означает, что если взять 20 000 образцов, то примерно на 2 000 из них. Если брать 20 образцов, в среднем это примерно 2 из них. Теперь вы пытаетесь найти линию, верно? Действительно ли имеет значение, если процент немного отклоняется, если вы его найдете? Это еще один из тех счастливых мифов профилировщиков, что важна точность тайминга. Для поиска проблем, которые стоит исправить, 20 000 образцов не скажут вам гораздо больше, чем 20 образцов. Итак, что мне делать? Просто возьмите образцы вручную и изучите их. Код, который стоит оптимизировать, просто бросается в глаза.

Наконец, есть большая порция хороших новостей. Вероятно, есть несколько вещей, которые вы могли бы оптимизировать. Предположим, вы решаете 20-процентную проблему и заставляете ее исчезнуть. Общее время сократилось до 4/5 от того, что было, но другие задачи занимают не меньше времени, так что теперь их процент составляет 5/4 от того, что было, потому что знаменатель стал меньше. В процентном отношении они стали больше, и их стало легче найти. Этот эффект снежный ком, позволяя вам действительно сжимать код.

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