All geek questions in one place

Is it possible to optimize array access?

My Netbeans profiler may be misleading, but I see some strange behavior, hoping someone can help me figure this out.

I am working on an application that heavily uses fairly large hash tables (keys are long, values ​​are objects). Performance with the built-in java hash table (HashMap specifically) was very poor, and after trying some alternatives - Trove, Fastutils, Colt, Carrot - I started working on my own.

The code is very simple using a double hash strategy. This works well and shows the best performance of all the other parameters that I have tried so far.

The trick, according to the profiler, hash table search is the most expensive method in the entire application - despite the fact that other methods are called many times and / or do a lot more logic.

What really bothers me is the search with only one class; the calling method performs a search and processes the results. Both are called almost the same number of times, and the method that calls the search has a lot of logic in it to process the search result, but about 100 times faster.

Below is the hash search code. These are basically just two calls to the array (functions that calculate hash codes, according to profiling, are actually free). I don’t understand how this bit of code can be so slow, because it is just accessing the array, and I don’t see any way to speed up its execution.

Note that the code simply returns the bucket corresponding to the key, as expected, the handler will process the bucket. 'size' - hash.length / 2, hash1 searches in the first half of the hash table, hash2 searches in the second half. key_index is the final int field in the hash table passed to the constructor, and the array of values ​​in Entry objects is a small array of lengths, usually 10 or less.

Any thoughts that people have on this are greatly appreciated.

Thank.

public final Entry get(final long theKey) {
    Entry aEntry = hash[hash1(theKey, size)];

    if (aEntry != null && aEntry.values[key_index] != theKey) {
        aEntry = hash[hash2(theKey, size)];

        if (aEntry != null && aEntry.values[key_index] != theKey) {
            return null;
        }
    }

    return aEntry;
}

Change, code for hash1 and hash2

private static int hash1(final long key, final int hashTableSize) { 
    return (int)(key&(hashTableSize-1)); 
}
private static int hash2(final long key, final int hashTableSize) { 
    return (int)(hashTableSize+((key^(key>>3))&(hashTableSize-1))); 
}
+3
source share
4 answers

. , /, , , .

, , - Entry.

:

class Entry {
    long[] values;
}

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

:

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

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

, , , , .

, ?

, . Array:

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

"" undefined, . :

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

, , , ; , - , //.

+6

, . , , , . get(), , , , . , JIT .

, - - , .

, , . , , , .

( ), . JIT ( Java 6), AFAIK , (x = 0; x < array.length; ++). , , , . .

, , , , , , .

+1

, - , , , . , , , , , .

, , .

  • , , , , , , . , , -, , , . , , , .

  • -, "", " ", "" "call main". 10% , , , . . ( " " " ". .)

  • , , . , , . , , - , ( ) , . , a) - , b) .

, . Java.

, . , , ? , , , 10% ? 10% 10% . , 20 000 , 2000 . 20 , 2 , . , ? , , ? , . , , 20 000 , 20 . , ? . .

, . , , . , 20% . 4/5 , , , 5/4 , , . . , .

+1

You can try using a memoizing or caching strategy to reduce the number of actual calls. Another thing you could try if you are very desperate is your own array, since indexing this data is incredibly fast, and JNI should not refer to excessive overhead if you use parameters like longs that do not require sorting .

0
source

Source: https://habr.com/ru/post/1773250/

More articles:


All Articles