Here's the source:

package com.solyanik.perftesting;

import java.util.Arrays;

import java.util.Vector;

import java.util.ArrayList;

/**

* Implements a micro-benchmark using

* high-resolution RDTSC timer.

*

* @author sergey@solyanik.com (Sergey Solyanik)

*/

public class MicroBenchmark {

/*

* RDTSC - returns number of clocks since

* the core was last reset.

*

* NOTE: no synchronizing instruction

* is executed before RDTSC, so this

* is not suitable for really short

* runs as the second RDTSC can execute

* before the instruction we're trying

* to measure.

*

* NOTE2: Different cores have

* different clock counters, and they

* are not synchronized.

*/

private native static long rdtsc();

/**

* A function that consists of one

* instruction - ret.

*/

private native static void nop();

/**

* Fixes the thread to the first CPU

* and core.

*/

private native static void fixthread();

/**

* Loads the library containing our

* native code.

*/

static {

System.loadLibrary("jnipc");

}

/**

* Prints the statistics for an array

* of clock intervals.

*

* @param clocks The array of clocks

* @param iterations Number of iterations

* @param bucket_number How many buckets

* to use for the histogram

* @param scale Scale for the histogram

*/

private static void Analyze(

String header, long [] clocks,

int iterations, int bucket_number,

int scale) {

Arrays.sort(clocks);

double average = 0.0;

long [] buckets = new long[bucket_number];

double log2 = Math.log(2.0);

for (int i = 0 ; i < clocks.length; ++i) {

average += clocks[i];

int ndx = (int)(Math.log(

(double)clocks[i]

/ (double)scale) / log2);

if (ndx < 0)

buckets[0]++;

else if (ndx < buckets.length - 1)

buckets[ndx + 1]++;

else

buckets[buckets.length - 1]++;

}

average /= clocks.length;

System.out.println(header + ":");

System.out.println("Median for " +

iterations + " iterations: " +

clocks[clocks.length / 2]);

System.out.println("Average for " +

iterations + " iterations: " +

average);

System.out.println("Median per iteration: "

+ clocks[clocks.length / 2]

/ iterations);

System.out.println("Average per iteration: "

+ average / iterations);

System.out.println("Histogram:");

int prev = 0;

int curr = scale;

for (int i = 0; i < buckets.length - 1; ++i) {

System.out.println(prev + " - " + curr

+ ": " + buckets[i]);

prev = curr;

curr *= 2;

}

System.out.println(" > " + prev + ": " +

buckets[buckets.length - 1]);

}

/**

* Number of loop iterations per sample.

*/

private static final int ITERATIONS = 10000;

/**

* Number of samples.

*/

private static final int SAMPLES = 1000;

/**

* Number of buckets for the histogram.

*/

private static final int BUCKETS = 20;

/**

* Bucket scale for the histogram.

*/

private static final int BUCKET_SCALE = 1000;

/**

* Main function.

*

* @param args

*/

public static void main(String[] args) {

fixthread();

System.out.println("Let the fun begin!");

long [] clocks = new long[SAMPLES];

Boolean b = new Boolean(true);

for (int i = 0; i < clocks.length; ++i) {

Boolean [] a = new Boolean[ITERATIONS];

long start = rdtsc();

for (int j = 0; j < ITERATIONS; ++j)

a[j] = b;

long stop = rdtsc();

clocks[i] = stop - start;

}

Analyze("Array",

clocks, ITERATIONS, BUCKETS,

BUCKET_SCALE);

for (int i = 0; i < clocks.length; ++i) {

Vector<Object> v = new Vector<Object>();

long start = rdtsc();

for (int j = 0; j < ITERATIONS; ++j)

v.add(b);

long stop = rdtsc();

clocks[i] = stop - start;

}

Analyze("Expanding Vector", clocks,

ITERATIONS, BUCKETS, BUCKET_SCALE);

for (int i = 0; i < clocks.length; ++i) {

Vector<Object> v = new Vector<Object>();

v.setSize(ITERATIONS);

long start = rdtsc();

for (int j = 0; j < ITERATIONS; ++j)

v.set(j, b);

long stop = rdtsc();

clocks[i] = stop - start;

}

Analyze("Pre-allocated Vector",

clocks, ITERATIONS, BUCKETS,

BUCKET_SCALE);

for (int i = 0; i < clocks.length; ++i) {

ArrayList<Object> al = new ArrayList<Object>();

long start = rdtsc();

for (int j = 0; j < ITERATIONS; ++j)

al.add(b);

long stop = rdtsc();

clocks[i] = stop - start;

}

Analyze("Expanding ArrayList", clocks,

ITERATIONS, BUCKETS, BUCKET_SCALE);

for (int i = 0; i < clocks.length; ++i) {

ArrayList<Object> al = new ArrayList<Object>();

al.ensureCapacity(ITERATIONS);

long start = rdtsc();

for (int j = 0; j < ITERATIONS; ++j)

al.add(b);

long stop = rdtsc();

clocks[i] = stop - start;

}

Analyze("Pre-allocated ArrayList", clocks,

ITERATIONS, BUCKETS, BUCKET_SCALE);

}

}

And here's what I've got:

To remind, C++ numbers were like this:

Median Average

Array 14 15

Expanding vector 124 133

Pre-allocated vector 115 119

Expanding ArrayList 57 66

Pre-allocated ArrayList 43 46

Median Average

Array 2 2

Pre-allocated vector,

assigment 2 2

Pre-allocated vector,

push_back 8 8

Expanding vector,

push_back 145 148 (*)

(*) Obviously, this number very much depends on number of expansions, because STL vector grows by 50%, a very big vectors will have smaller cost. See my previous posts for details on C++ testing.

## No comments:

Post a Comment