Primitive boolean array packing

[B. Blaser]

On Mon, 8 Oct 2018 at 17:19, Andrew Haley <aph at redhat.com> wrote:
>
> On 10/08/2018 12:16 PM, B. Blaser wrote:
> > The current prototype was intended to scrupulously implement what the
> > JVMS explicitly allows for baload/bastore instructions.
> > But helper intrinsics might be good alternatives too, we could try both.
>
> So I tried it with a rough C++/assembly language test, and it doesn't
> make much sense to use this for default boolean arrays. The update
> sequence on AArch64 is
>
>         0: ldxrb w2, [x0];
>         and w2, w2, w1
>         stxrb w3, w2, [x0]
>         cbnz w3, 0b
>
> (combined with a bunch of uninteresting shifts and logical
> operations.)  We have to load a byte in exclusive state, AND or OR it
> as appropriate, then store it, still in exclusive state. That gets us
> the atomicity we need.
>
> 10**9 random set operations on an 8 Mbit array take 0.550s; with a
> boolean array the time is 0.150s. This is the local overhead of the
> load/store exclusive.

Reducing memory consumption has a price which doesn't seem too
expensive, fortunately.

> > Note that the existing BitSet needs external sync (most probably on
> > the whole set) when used in multi-threaded environments.
> > With packed baload/bastore instructions or dedicated intrinsics, the
> > sync would be on smaller 8-bit blocks or no sync at all on some arch
> > as Roman mentioned (AArch64).
>
> It might help. The question is how much we need large bit
> arrays. They're certainly useful for things like Bloom filters.

As I initially mentioned, this would be useful for large bit arrays or
for a large *number* of smaller bit arrays. We are planning to
refactor javac flags [1] currently using one long value per symbol [2]
which potentially means a huge number of bit arrays (or vectors) of
more than 64 elements.

Bernard

[1] http://mail.openjdk.java.net/pipermail/compiler-dev/2018-September/012504.html
[2] http://hg.openjdk.java.net/jdk/jdk/file/d8aebcc2d3ac/src/jdk.compiler/share/classes/com/sun/tools/javac/code/Symbol.java#l98

> --
> Andrew Haley
> Java Platform Lead Engineer
> Red Hat UK Ltd. <https://www.redhat.com>
> EAC8 43EB D3EF DB98 CC77 2FAD A5CD 6035 332F A671