Самый быстрый способ читать/хранить много многомерных данных? (Java)
У меня есть три вопроса приблизительно три вложенных цикла:
for (int x=0; x<400; x++)
{
for (int y=0; y<300; y++)
{
for (int z=0; z<400; z++)
{
// compute and store value
}
}
}
И я должен сохранить все вычисленные значения. Мой стандартный подход должен был бы использовать 3D массив:
values[x][y][z] = 1; // test value
но это оказывается медленным: требуется 192 мс для завершения этого цикла, где единственное международное присвоение
int value = 1; // test value
берет только 66 мс.
1) Почему массив является настолько относительно медленным?
2) И почему делает это становится еще медленнее, когда я поместил это во внутренний цикл:
values[z][y][x] = 1; // (notice x and z switched)
Это занимает больше чем 4 секунды!
3) Самое главное: я могу использовать структуру данных, которая так же быстра как присвоение единственного целого числа, но может хранить столько же данных сколько 3D массив?
5 ответов
1) Почему массив такой относительно медленный?
Как указывали другие, вы сравниваете яблоки к апельсинам. Тройной массив работает медленно, потому что ему нужно трижды разыменовать (по крайней мере, внутренне - да, «в Java нет указателей»); но опять же, вы не можете ссылаться на одну целочисленную переменную ...
2) И почему это становится еще медленнее, когда я помещаю это во внутренний цикл:
values[z][y][x] = 1; // (notice x and z switched)
Потому что вы снизили согласованность кеша. Наиболее быстро изменяющиеся индексы должны быть последними, чтобы большинство обращений к памяти происходило рядом друг с другом, в пределах одних и тех же блоков кеша, вместо того, чтобы заставлять ваш процессор ждать, пока блоки не будут прочитаны из основного ОЗУ.
3) Самое главное: могу ли я использовать структуру данных, которая работает так же быстро, как присвоение одного целого числа, но может хранить столько же данных, сколько и 3D-массив?
Нет. Такой структуры нет, поскольку целочисленная переменная помещается в машинный регистр (даже быстрее, чем кэш памяти процессора), и к ней всегда можно получить доступ быстрее, чем что-либо еще, о чем вы хотите упомянуть.Скорость процессора намного выше скорости основной памяти. Если ваш «рабочий набор» (данные, с которыми вам нужно работать) не помещается в регистры или кеш, вам придется заплатить штраф, чтобы получить его из ОЗУ (или, что еще хуже, с диска).
При этом Java выполняет проверки границ при каждом доступе к массиву и, похоже, не слишком умен в оптимизации проверки границ. Может быть интересно следующее сравнение:
public static long test1(int[][][] array) {
long start = System.currentTimeMillis();
for ( int x = 0; x < 400; x++ ) {
for ( int y = 0; y < 300; y++ ) {
for ( int z = 0; z < 400; z++ ) {
array[x][y][z] = x + y + z;
}
}
}
return System.currentTimeMillis() - start;
}
public static long test2(int [] array) {
long start = System.currentTimeMillis();
for ( int x = 0; x < 400; x++ ) {
for ( int y = 0; y < 300; y++ ) {
for ( int z = 0; z < 400; z++ ) {
array[z + y*400 + x*400*300] = x + y + z;
}
}
}
return System.currentTimeMillis() - start;
}
public static void main(String[] args) {
int[][][] a1 = new int[400][300][400];
int[] a2 = new int[400*300*400];
int n = 20;
System.err.println("test1");
for (int i=0; i<n; i++) {
System.err.print(test1(a1) + "ms ");
}
System.err.println();
System.err.println("test2");
for (int i=0; i<n; i++) {
System.err.print(test2(a2) + "ms ");
}
System.err.println();
}
Результат в моей системе -
test1
164ms 177ms 148ms 149ms 148ms 147ms 150ms 151ms 152ms 154ms 151ms 150ms 148ms 148ms 150ms 148ms 150ms 148ms 148ms 149ms
test2
141ms 153ms 130ms 130ms 130ms 133ms 130ms 130ms 130ms 132ms 129ms 131ms 130ms 131ms 131ms 130ms 131ms 130ms 130ms 130ms
Следовательно, есть возможности для улучшения ... но я действительно не думаю, что это того стоит.
Вы пробовали это:
Object[][][] store = new Object[ 400 ][300][400];
for (int x=0; x<400; x++)
{
Object[][] matrix = store[x];
for (int y=0; y<300; y++)
{
Object[] line = matrix[y];
for (int z=0; z<400; z++)
{
// compute and store value
line[z] = // result;
}
}
}
это может улучшить работу вашего кеша.
Я предполагаю, что это во многом связано с кэшированием и регистрами, а также с принципом локальности памяти.
Java требует доступа к тысячам байтов памяти при сохранении в массиве. С единственной переменной он может просто сохранить это значение в кеше и просто продолжать его обновлять.
Кэш недостаточно велик, чтобы вместить весь многомерный массив, поэтому Java должна постоянно обновлять кеш в память и из памяти. Время доступа к кешу намного быстрее, чем время доступа к памяти.
Я даже не понимаю, зачем вам проводить этот тест. Если вам нужно хранить много данных в многомерном массиве, использование одной переменной бесполезно, даже если это быстрее.
Кроме того, причина того, что когда параметры переключаются при доступе к массиву, заключается в том, что вы намного больше прыгаете в памяти (намного больше промахов в кэше), чем когда вы просто выполняете итерацию другим способом.
public static void main( String[] args ) {
int[][][] storage = new int[ 400 ][ 300 ][ 400 ];
long start = System.currentTimeMillis();
for ( int x = 0; x < 400; x++ ) {
for ( int y = 0; y < 300; y++ ) {
for ( int z = 0; z < 400; z++ ) {
storage[x][y][z] = 5;
}
}
}
long end = System.currentTimeMillis();
System.out.println( "Time was: " + ( end - start ) / 1000.0 + " seconds." );
}
Запуск с -Xmx1g
Время составило: 0.188 секунды.
Это кажется довольно быстрым... вы смотрите на 48 МИЛЛИОНОВ элементов в самом внутреннем цикле.
Запускаем глупую маленькую структуру данных...
public static void main( String[] args ) {
StorerGuy[] storerGuys = new StorerGuy[ 400 ];
long start = System.currentTimeMillis();
for ( int x = 0; x < 400; x++ ) {
for ( int y = 0; y < 300; y++ ) {
for ( int z = 0; z < 400; z++ ) {
storerGuys[x] = new StorerGuy( x, y, z, 5 );
}
}
}
long end = System.currentTimeMillis();
System.out.println( "Time was: " + ( end - start ) / 1000.0 + " seconds." );
}
public static class StorerGuy {
public int x;
public int y;
public int z;
public int value;
StorerGuy( int x, int y, int z, int value ) {
this.x = x;
this.y = y;
this.z = z;
this.value = value;
}
}
Время составило: 0.925 секунды.
Что быстрее, чем 4 секунды в вашем примере с перепутанным порядком.
Я думаю, что мультимассивы - это слишком много для данной задачи. Лучше использовать более сложную структуру данных, так как в ней все данные будут храниться в одном месте памяти (x,y,z,value).
Java является ОО языком. В большинстве случаев вы должны использовать объекты, а не странные структуры данных типа int[][][][][]
Учитывая, что массив огромен, объем используемой памяти, необходимые косвенные ссылки (многомерный массив - это массивы ссылок на массивы ...), это совсем не кажется медленным для меня. Когда вы переключаете x и z, вы, вероятно, уничтожаете кеш.
Для сравнения, вы могли бы хранить все в плоском массиве ... Это улучшило бы скорость хранения ... но тогда извлечение было бы более сложным и гораздо более медленным.
int k = 0;
for (int x=0; x<400; x++)
{
for (int y=0; y<300; y++)
{
for (int z=0; z<400; z++)
{
// compute and store value
arr[k++] = val;
}
}
}