Primitive boolean array packing

[B. Blaser]

On Mon, 8 Oct 2018 at 19:18, B. Blaser <bsrbnd at gmail.com> wrote:
>
> 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.

On x86, I guess we have BTS/BTR (bit set and reset) with the LOCK
prefix to assure atomicity.
I'll do some experiment and update the prototype accordingly.

Bernard