Aligned long views over byte arrays and heap ByteBuffers

[Aleksey Shipilev]

Hi,

In VarHandles, there is a suggested API that can provide wider
operations on some raw and unsuspecting entities, like byte[] and
ByteBuffers, pretty much like Unsafe.getX does. For example, you can
read "long" out of byte[] array:

  static final VarHandle VH =
    MethodHandles.byteArrayViewVarHandle(
      long[].class,
      /* unaligned = */ false,
      ByteOrder.nativeOrder() == ByteOrder.BIG_ENDIAN);

  byte[] storage = ...;
  long v = (long)VH.get(bytes, 0); // reads 8 bytes at index = 0

Note there are two flavors: aligned views and unaligned views. Aligned
view is when we access the underlying storage aligned by "reinterpreted"
element size. E.g. accessing 0-th long is accessing [0..7] bytes, 1-st
long is [8..15] bytes, etc.

Aligned views provide two important advantages: a) we can do atomic
operations (reads, writes, CASes) for larger widths; and b) it maps well
on hardware instructions, especially when hardware cannot make
misaligned accesses (but, Unsafe.getXUnaligned works decently well).

However, aligned views come with an (obvious in hindsight) problem: it
is not guaranteed that array base for byte[] is aligned at 8. In fact,
byte[] array base is coincidentally aligned to 8 for 64-bit HotSpot [1],
but not for 32-bit HotSpot [2], where it is aligned by 4.

This means, we are not able to universally guarantee heap ByteBuffer and
byte[] views are aligned for *long* accesses. We still can do this for
direct ByteBuffers.

So, there are two obvious ways out of this conundrum:

 A) Give up on heap BBs and byte[] views, leave only direct BB. It is
still an improvement over current state of affairs where even direct BB
do not allow atomic ops. This breaks the symmetry between heap and
direct BBs. A variant of this solution is to disallow only 8-byte views,
long[] and double[], leaving others intact.

 B) Force VM to align all array bases to 8. Luckily, 64-bit HotSpot,
which hopefully is the most ubiquitous VM nowadays, is unaffected. This
penalizes current 32-bit HotSpot, and has unknown impact on other VMs
that would try to run VarHandles. Any VM vendors on this list to chime in?

There are completely unexplored alternatives:

 C) Work out an API for heap BBs that allow to "align" their storage,
without getting VM into the picture. John suggested something like
"BB.align(int unit) => returns this if aligned access of size unit
already possible, else restricts the BB to an offset (and size) where
that alignment is possible, using wrap(byte[],int,int)".

 D) Go the other way around, and define the byte views over already
aligned heap LongBuffers, so that you would get both aligned byte-wide
and long-wide accesses.

There is no perfect solution that jumps out immediately, so I'm trolling
for ideas. Thoughts?

Thanks,
-Aleksey

-------------------------------------------------------------------

[1] $ java -cp ~/projects/jol/jol-samples/target/jol-samples.jar
org.openjdk.jol.samples.JOLSample_25_ArrayAlignment

Running 64-bit HotSpot VM.
Using compressed references with 3-bit shift.
Objects are 8 bytes aligned.
Field sizes by type: 4, 1, 1, 2, 2, 4, 4, 8, 8 [bytes]
Array element sizes: 4, 1, 1, 2, 2, 4, 4, 8, 8 [bytes]

[J object internals:
 OFFSET  SIZE  TYPE DESCRIPTION                    VALUE
      0     4       (object header)                ...
      4     4       (object header)                ...
      8     4       (object header)                ...
     12     4       (object header)                ...
     16     0  long [J.<elements>                  N/A
Instance size: 16 bytes (reported by Instrumentation API)
Space losses: 0 bytes internal + 0 bytes external = 0 bytes total

[B object internals:
 OFFSET  SIZE  TYPE DESCRIPTION                    VALUE
      0     4       (object header)                ...
      4     4       (object header)                ...
      8     4       (object header)                ...
     12     4       (object header)                ...
     16     0  byte [B.<elements>                  N/A
Instance size: 16 bytes (reported by Instrumentation API)
Space losses: 0 bytes internal + 0 bytes external = 0 bytes total

-------------------------------------------------------------------

[2] $ java -cp ~/projects/jol/jol-samples/target/jol-samples.jar
org.openjdk.jol.samples.JOLSample_25_ArrayAlignment

Running 32-bit HotSpot VM.
Objects are 8 bytes aligned.
Field sizes by type: 4, 1, 1, 2, 2, 4, 4, 8, 8 [bytes]
Array element sizes: 4, 1, 1, 2, 2, 4, 4, 8, 8 [bytes]

[J object internals:
 OFFSET  SIZE  TYPE DESCRIPTION                    VALUE
      0     4       (object header)                ...
      4     4       (object header)                ...
      8     4       (object header)                ...
     12     4       (alignment/padding gap)        N/A
     16     0  long [J.<elements>                  N/A
Instance size: 16 bytes (reported by Instrumentation API)
Space losses: 4 bytes internal + 0 bytes external = 4 bytes total

[B object internals:
 OFFSET  SIZE  TYPE DESCRIPTION                    VALUE
      0     4       (object header)                ...
      4     4       (object header)                ...
      8     4       (object header)                ...
     12     0  byte [B.<elements>                  N/A
     12     4       (loss due to the next object alignment)
Instance size: 16 bytes (reported by Instrumentation API)
Space losses: 0 bytes internal + 4 bytes external = 4 bytes total