Шифратор (smok) wrote,
Шифратор
smok

java arrays access

Подумал тут вдруг: а куда быстрее "случайный" доступ - в двумерный массив (по [i][j]) или в одномерный, хранящий те же данные (по [i*cols + j])

Соорудил небольшой тестик, и получилось, что читать как попало из одномерного - быстрее. Причем нехило так быстрее, раза в полтора (для больших массивов).

Код (FloatMatrix.java):
public abstract class FloatMatrix {
	protected final int rows;
	protected final int cols;

	FloatMatrix(int rows, int cols) {
		this.rows = rows;
		this.cols = cols;
	}

	public abstract float get(int i, int j);
}

class FloatMatrix2D extends FloatMatrix {
	float[][] array;

	public FloatMatrix2D(int rows, int cols) {
		super(rows, cols);
		array = new float[rows][cols];
	}

	public float get(int i, int j) {
		return array[i][j];
	}
}

class FloatMatrix1D extends FloatMatrix {
	float[] array;

	public FloatMatrix1D(int rows, int cols) {
		super(rows, cols);
		array = new float[rows*cols];
	}

	public float get(int i, int j) {
		return array[i*cols + j];
	}
}


Еще код (ArrayDimTest.java)
import java.util.Random;

public class ArrayDimTest {

	static final int RANDOMS = 100000;
	static final int TESTS = 1000;

	int N, M;
	int[] randoms1, randoms2;
	float f;
	long startTime, endTime;

	public static void main(String[] args) {
		int N = 5000;
		try {
			N = Integer.parseInt(args[0]);
		} catch(Exception e) {}
		int M = 5000;
		try {
			M = Integer.parseInt(args[1]);
		} catch(Exception e) {}
		ArrayDimTest t = new ArrayDimTest(N, M);
		System.out.println("N=" + N + ", M=" + M + ", RANDOMS=" + RANDOMS + ", TESTS=" + TESTS);

		FloatMatrix m1 = new FloatMatrix1D(N, M);
		FloatMatrix m2 = new FloatMatrix2D(N, M);
		long time1 = t.testMatrix(m1);
		System.out.println("Time 1: " + time1);
		long time2 = t.testMatrix(m2);
		System.out.println("Time 2: " + time2);
	}

	public ArrayDimTest(int N, int M) {
		this.N = N;
		this.M = M;
		randoms1 = new int[RANDOMS];
		randoms2 = new int[RANDOMS];

		Random r = new Random();
		for(int i = 0; i < RANDOMS; i++) {
			randoms1[i] = r.nextInt(N);
			randoms2[i] = r.nextInt(M);
		}
	}

	public long testMatrix(FloatMatrix m) {
		startTime = System.currentTimeMillis();
		for(int j = 0; j < TESTS; j++) {
			for(int i = 0; i < RANDOMS; i++) {
				f = m.get(randoms1[i], randoms2[i]);
			}
		}
		endTime = System.currentTimeMillis();
		return endTime-startTime;
	}

}


Результаты запуска (JDK 1.5.0_08):

java -server -Xnoclassgc -Xms512m -Xmx512m ArrayDimTest
N=5000, M=5000, RANDOMS=100000, TESTS=1000
Time 1: 24375
Time 2: 38703

(в 1м хранение в массиве [], во 2м - в [][]);


Для N,M = 500 результаты уже не такие впечатляющие:
java -server -Xnoclassgc -Xms512m -Xmx512m ArrayDimTest 500 500
N=500, M=500, RANDOMS=100000, TESTS=1000
Time 1: 9484
Time 2: 13782


(наверное, это уже связано с каким-то кешированием и т.п.)



Связано ли это явление с природой "тяжелого" доступа к элементам двумерного массива т.к. он, по сути, "массив массивов", т.е. в JVM фактически идет доступ сначала по указателю в "массиве массивов", потом уже в конкретном массиве?
Что же там внутри действительно происходит?

x-post: ru_java
Tags: прогр.
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 2 comments