Effizienter byte-Zugriff auf ein long[]-Array

[LucasGlockner]

Hallo,

kann man in Java irgendwie auf ein long[]-Array als byte[] zugreifen, ohne die Daten hin und her kopieren zu müssen?

Hintergrund: Ich habe ein Algorithmus der als Zustand ein long[]-Array benutzt. Die meisten Berechnungsschritte arbeiten dabei direkt auf den long-Werten, also auf ℤ/n mit n = 2^64. Es gibt aber einen Schritt, wo direkt die einzelnen Bytes modifiziert werden müssen!

Anders ausgedrückt, was ist das Java-Äquivalent zu folgendem C#- bzw. JavaScript- bzw. Python-Code?

long[] array = new long[] { /* ... */ };
fixed (ulong* buffer = array)
{
    byte* bytes = (byte*)buffer;
    for (int pos = 0; pos < NUHASH_BYTES; ++pos)
    {
        bytes[pos] = SBOX[bytes[pos]];
    }
}

let array = new BigUint64Array ([ /* ... */ ]);
const view = new DataView(array.buffer);
const begin = view.byteOffset, end = begin + view.byteLength;
for (let offset = begin; offset < end; ++offset) {
    view.setUint8(offset, SBOX[view.getUint8(offset)]);
}

array = arr.array('Q', [ ... ])
mem_view = memoryview(array).cast('B')
for i in range(len(view)):
    mem_view[i] = SBOX[mem_view[i]]

Danke!

 

[mrBrown]

Bytebuffer könnte eine Variante sein, ansonsten selber rechnen und mit Bitmasken arbeiten.

Die C-Variante ist so zumindest nicht möglich, in Java sind byte[] und long[] einfach unterschiedliche Typen.

 

[LucasGlockner]

Bytebuffer könnte eine Variante sein, ansonsten selber rechnen und mit Bitmasken arbeiten.

Kannst Du das genauer ausführen?

Soweit ich sehe, klappt das auch mit ByteBuffer nur indem man die Daten hin und her kopiert, was natürlich ziemlich ineffizient wäre:

final long[] array = new long[] { /* ... */ };
final ByteBuffer buffer = ByteBuffer.allocate(array.length * Long.BYTES);

for (final long value : array) {
    buffer.putLong(value);
}

for (int i = 0; i < buffer.capacity(); ++i) {
    buffer.put(i, SBOX[buffer.get(i)]);
}

for (int i = 0, j = 0; i < array.length; ++i, j += Long.BYTES) {
    array[i] = buffer.getLong(j);
}

Es gibt zwar ByteBuffer.wrap(), was aber leider nur mit einem byte[]-Array, nicht aber mit einem long[] funktioniert 😟

LongBuffer.wrap() funktioniert, aber aus unverständlichen Gründen fehlt LongBuffer.asByteBuffer().

ByteBuffer.asLongBuffer() hingegen existiert. Aber das ist genau die umgekehrte Richtung, die hier benötigt wird... 🙄

Die C-Variante ist so zumindest nicht möglich, in Java sind byte[] und long[] einfach unterschiedliche Typen.

Schon klar, dass es unterschiedliche Typen sind.

Aber in so ziemlich jeder anderen Sprache (C#, JavaScript, Python, etc.) kann man sich ein byte-"View" für das long (uint64) Array holen und darüber die Daten auf der byte-Ebene zugreifen/manipulieren. Gibt es tatsächlich in Java nichts entsprechendes ???

 

[httpdigest]

Aber in so ziemlich jeder anderen Sprache (..., JavaScript, ...) kann man sich byte-"View" für das Array holen und dann die Daten auf der byte zugreifen/manipulieren.

Also zumindest in JavaScript kannst du keine byte-orientierte View auf ein multi-byte-Wert Typed Array haben. Ausgangspunkt einer View ist immer zuerst ein byte-basierter ArrayBuffer, aus dem du dann multi-byte-basierte Typed Arrays (wie etwa ein Int32Array) als Views erzeugen kannst. Aber ja nicht umgekehrt (was du machen möchtest).
Und außerhalb der Typed Arrays gibt es sowieso nur number[] (als double), wo du auch nicht byte-basiert drauf zugreifen kannst.

EDIT: Und tatsächlich ist es in C Undefined Behaviour (also explizit nicht in dem Standard spezifiziert - und jeder Compiler kann hier machen, was er will), wenn du einen Pointer vom Typ T* in einen anderen Pointer U* konvertierst, und dann U* dereferenzierst. Auf den meisten Plattformen funktioniert das aber, weil sie Speicher als kontinuierliche Anreihung individuell adressierbaren Bytes ansehen und es auf Plattformebene im Speicher kein Unterschied zwischen byte und int, long, etc. gibt (außer natürlich alignment-Voraussetzungen beim Zugriff).
Streng genommen ist also das von dir gezeigte C-Programm undefined behaviour (aber welches C-Programm ist schon nicht UB was den C-Standard angeht).

 

[LucasGlockner]

Also zumindest in JavaScript kannst du keine byte-orientierte View auf ein multi-byte-Wert Typed Array haben. Ausgangspunkt einer View ist immer zuerst ein byte-basierter ArrayBuffer, aus dem du dann multi-byte-basierte Typed Arrays (wie etwa ein Int32Array) als Views erzeugen kannst. Aber ja nicht umgekehrt (was du machen möchtest).
Und außerhalb der Typed Arrays gibt es sowieso nur number[] (als double), wo du auch nicht byte-basiert drauf zugreifen kannst.

Doch das geht, wenn man, wie heutzutage empfohlen, ein Uint32Array oder Uint64Array benutzt. Beispiel-Code siehe oben.

EDIT: Und tatsächlich ist es in C Undefined Behaviour (also explizit nicht in dem Standard spezifiziert - und jeder Compiler kann hier machen, was er will), wenn du einen Pointer vom Typ T* in einen anderen Pointer U* konvertierst, und dann U* dereferenzierst. Auf den meisten Plattformen funktioniert das aber, weil sie Speicher als kontinuierliche Anreihung individuell adressierbaren Bytes ansehen und es auf Plattformebene im Speicher kein Unterschied zwischen byte und int, long, etc. gibt (außer natürlich alignment-Voraussetzungen beim Zugriff).
Streng genommen ist also das von dir gezeigte C-Programm undefined behaviour (aber welches C-Programm ist schon nicht UB was den C-Standard angeht).

Ich sprach allerdings auch von C# (das Java-Äquivalent auf der .NET Plattform), nicht C. Beispiel-Code siehe oben.

 

[LucasGlockner]

Anscheinend kann man Byte-Zugriff mittels "theUnsafe" erhalten:

lz4-java/src/java-unsafe/net/jpountz/util/UnsafeUtils.java at master · lz4/lz4-java

LZ4 compression for Java. Contribute to lz4/lz4-java development by creating an account on GitHub.

github.com

private static final Unsafe UNSAFE;
private static final int LONG_ARRAY_OFFSET;
static {
    try {
        final Field theUnsafe = Unsafe.class.getDeclaredField("theUnsafe");
        theUnsafe.setAccessible(true);
        UNSAFE = (Unsafe) theUnsafe.get(null);
        LONG_ARRAY_OFFSET = UNSAFE.arrayBaseOffset(long[].class);
    } catch (Exception e) {
        throw new ExceptionInInitializerError("Cannot access Unsafe!");
    }
}

private static void substitute(final long[] buffer) {
    final int limit = LONG_ARRAY_OFFSET + buffer.length * Long.BYTES;
    for (int pos = LONG_ARRAY_OFFSET; pos < limit; ++pos) {
        UNSAFE.putByte(buffer, pos, SBOX[UNSAFE.getByte(buffer, pos) & 0xFF]);
    }
}

Interessanterweise ist diese Lösung bei meinem Test sogar minimal langsamer als:

private static void substitute(final long[] buffer) {
    for (int pos = 0; pos < buffer.length; ++pos) {
        final long value = buffer[pos];
        buffer[pos] =
            ((SBOX[(int)(value >>> 0x00) & 0xFF] & 0xFFL) << 0x00) |
            ((SBOX[(int)(value >>> 0x08) & 0xFF] & 0xFFL) << 0x08) |
            ((SBOX[(int)(value >>> 0x10) & 0xFF] & 0xFFL) << 0x10) |
            ((SBOX[(int)(value >>> 0x18) & 0xFF] & 0xFFL) << 0x18) |
            ((SBOX[(int)(value >>> 0x20) & 0xFF] & 0xFFL) << 0x20) |
            ((SBOX[(int)(value >>> 0x28) & 0xFF] & 0xFFL) << 0x28) |
            ((SBOX[(int)(value >>> 0x30) & 0xFF] & 0xFFL) << 0x30) |
            ((SBOX[(int)(value >>> 0x38) & 0xFF] & 0xFFL) << 0x38);
    }
}

🤔

 

[Robert Zenz]

Ist das ein Java 9+ Grund wieso die da Reflektion machen anstelle von Unsafe.getUnsafe()?

Interessanterweise ist diese Lösung bei meinem Test sogar minimal langsamer als:

Ohne es jetzt probiert zu haben, koennte einige Gruende haben. Zwei die mir einfallen sind die "kuerzere" Schleife beim long Array und moeglicherweise CPU Caches die man bei der Unsafe Methode eher verfehlen wird. Letzteres ist aber geraten und wahrscheinlich falsch. Eventuell hat der Unsafe Zugriff auf den Speicher aber noch andere Auswirkungen, ich weisz dass die JVM Werte durchaus cachen kann je nach Thread, eventuell zerlegt der Unsafe Zugriff dort irgendwas und dann muessen Zustaende invalidiert werden.

 

[KonradN]

Ist das ein Java 9+ Grund wieso die da Reflektion machen anstelle von Unsafe.getUnsafe()?

Guide to sun.misc.Unsafe | Baeldung

Die Methode wirft leider eine SecurityException so dass man die nicht nutzen kann. Daher laut Baeldung der Weg über Reflection.

 

[Robert Zenz]

Guide to sun.misc.Unsafe | Baeldung

Die Methode wirft leider eine SecurityException so dass man die nicht nutzen kann. Daher laut Baeldung der Weg über Reflection.

Ah, okay. Ja, stimmt, habe da gestern wohl schon biszchen geschlafen, in meiner 8 und 16 JDK ist die Pruefung mit dem werfen der Ausnahme drinnen, interessanterweise in der 17 (Corretto) die ich habe, fehlt diese.