Member 14654526 Ответов: 2

Подкачанная виртуальная память: почему второй шаг вдруг стал быстрее?


В этой программе есть матрица 128 х 128 целых чисел. На первом этапе мы меняем каждый элемент на 1. На втором этапе мы меняем каждый элемент на 2. Если мы сравним время, необходимое для этих шагов, то увидим, что Шаг 2 намного быстрее, чем Шаг 1, Когда мы меняем длину матрицы. Это различие начинается с 512x512 и становится более значительным, когда мы меняем его на 1024,2000... Как это можно объяснить?

public class PagingTest 
{
    private static int size = 128;          // 128, 1024, 8192, ...
    private static long start, stop;
    private static int[][] data;

    public static void main (String[] args) 
    {
        if(args.length > 0)
        {
            size = Integer.parseInt(args[0]);
        }

        data = new int[size][size];
        System.out.println("Updating " + size + " x " + size + " array ... ");

        start = System.nanoTime();

        for(int j = 0; j < size; j++)
        {  
            for(int i = 0; i < size; i++)
            {  
                data[i][j] = 1;
            }
        }
        stop = System.nanoTime();
        System.out.println("  step 1: " + (stop - start) + " nanoseconds");
     
        start = System.nanoTime();

        for(int i = 0; i < size; i++)
        {  
            for(int j = 0; j < size; j++)
            {  
                data[i][j] = 2;
            }
        }
        stop = System.nanoTime();
        System.out.println("  step 2: " + (stop - start) + " nanoseconds");
    }
}


Что я уже пробовал:

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

2 Ответов

Рейтинг:
2

phil.o

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


Member 14654526

Как это можно объяснить на уровне реализации, что итерация по смежным значениям происходит быстрее?

phil.o

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

Member 14654526

Наш профессор уже заявил, что это определенно не кэширование.

Рейтинг:
2

OriginalGriff

Цитата:
Как это можно объяснить на уровне реализации, что итерация по смежным значениям происходит быстрее?

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

Поэтому, если ваш цикл обращается к последовательным адресам, есть хороший шанс, что он уже находится в кэше (15 из 16 int-чтений будут).

(Кроме того, существует ширина памяти: два последовательных доступа int могут быть сделаны (и действительно сделаны) в 64 - битной системе при чтении 32-битного целого числа, потому что шина данных всегда считывает 64 бита одновременно-но вы можете игнорировать это для всех практических целей в ваших приложениях. Компилятор этого не сделает!)

Так что если один цикл всегда пропускал кэш, а другой попадал в него 15 раз из 16, я думаю, вы можете догадаться, что будет быстрее!