[m-rev.] for review: Use a better algorithm for unwinding version_arrays.

[Paul Bone]

On Wed, Aug 06, 2014 at 02:27:37PM +1000, Peter Wang wrote:
> On Tue, 29 Jul 2014 14:59:53 +1000, Paul Bone <paul at bone.id.au> wrote:
> > Use a better algorithm for unwinding version_arrays.
> > 
> > For review by Peter Wang.
> > 
> > Branches: master, version-14_01-branch.
> > 
> > This is an alternative implementation to something I've recently put on the
> > release branch.  If we beleive that this is better and/or less risky than my
> > previous change then it could go onto the release branch too.
> > 
> > ---
> > 
> > The old version_array rewind code used linear stack space in order to
> > perform it's updates in the right order (newest to oldest) by following the
> > structure's next pointers (which are a oldest to newest list).  I previously
> > introduced week prev pointers so that walking over this structure newest to
> > oldest could be done with constant stack space.  However that is less
> > efficient than the method suggested by Peter Wang.
> > 
> > Peter suggested using a bitmap and traversing oldest-to-newest, marking
> > each update in the bitmap and checking the bitmap before making any update.
> > Thus preserving older values over newer ones (which is good, this code
> > _rewinds_ updates).  This patch implements Peter's suggestion and removes
> > the prev pointers from the structure for C and Java backends.
> 
> Will you attempt the C# implementation?  I think mono has a non-Boehm GC
> option which you could try, if that's the problem.

I'm not sure that I know C# well enough to implement this myself.  At least
not right now.  Using a non-Boehm GC version of mono would help me over only
the first barrier.  I can try it but if someone else wants to give it a go
i'm happy to let them.

> > diff --git a/java/runtime/MercuryBitmap.java b/java/runtime/MercuryBitmap.java
> > new file mode 100644
> > index 0000000..5a83023
> > --- /dev/null
> > +++ b/java/runtime/MercuryBitmap.java
> > @@ -0,0 +1,83 @@
> > +//
> > +// Copyright (C) 2001-2002, 2004-2007, 2009-2011 The University of Melbourne
> > +// Copyright (C) 2014 The Mercury Team.
> > +// This file may only be copied under the terms of the GNU Library General
> > +// Public License - see the file COPYING.LIB in the Mercury distribution.
> > +//
> > +
> > +package jmercury.runtime;
> > +
> > +/**
> > + * Simple bitmap implementation.
> > + * This bitmap class is mainly used by bitmap.m in the standard library.  It
> > + * is also used by version_array.m which is why it is part of the
> > + * jmercury.runtime package rather than being internal to bitmap.m
> > + */
> > +public class MercuryBitmap implements java.io.Serializable {
> > +    public static final int BITS_PER_BYTE = 8;
> > +    public int num_bits;
> > +    public byte[] elements;
> > +
> > +    public MercuryBitmap(int numBits) {
> > +        this.num_bits = numBits;
> > +        this.elements = new byte[numBits / 8 + (((numBits % 8) != 0) ? 1 : 0)];
> > +    }
> 
> int numBytes = (numBits + BITS_PER_BYTE - 1) / BITS_PER_BYTE;
> 
> > +
> > +    public MercuryBitmap(int numBits, byte[] elements) {
> > +        // This is provided so that foreign code can construct bitmaps from an
> > +        // existing byte array.
> > +        this.num_bits = numBits;
> > +        this.elements = elements;
> > +    }
> 
> This constructor is not used anywhere that I can see.  I suggest
> deleting it.  As it is, it looks like an invitation for users to use the
> class directly.  In my opinion all of java/runtime is off-limits unless
> documented, i.e. we have no obligation to maintain compatibility with
> anything in there.

Fair enough.  I moved the class into java/runtime and otherwise changed it
minimally, so I didn't review code like this, I assumed it was correct
already :-).  I'm happy to remove it.


> > +
> > +    public byte getByte(int byteno)
> > +    {
> > +        return elements[byteno];
> > +    }
> > +
> > +    public boolean getBit(int bit)
> > +    {
> > +        return (getByte(byteIndexForBit(bit))
> > +            & (1 << bitIndexWithinByte(bit))) != 0;
> > +    }
> > +
> > +    public void setBit(int bit)
> > +    {
> > +        byte b;
> > +
> > +        b = getByte(byteIndexForBit(bit));
> > +        b |= 1 << bitIndexWithinByte(bit);
> > +        elements[byteIndexForBit(bit)] = b;
> > +    }
> > +
> > +    public void clearBit(int bit)
> > +    {
> > +        byte b;
> > +
> > +        b = getByte(byteIndexForBit(bit));
> > +        b &= ~(1 << bitIndexWithinByte(bit));
> > +        elements[byteIndexForBit(bit)] = b;
> > +    }
> 
> getByte and clearBit have no users so, again, I would delete them.
> Up to you.

I'd rather leave clearBit there because it's counterpart setBit is there.
Rather than removing getByte I've choosen to make the elements array private
and require bitmap.m to use getByte rather than using the array directly.
Same with num_bits.


> 
> I think it would be better to update the C# backend at the same time.
> If you can't test it then make a best effort and post an updated patch,
> then I can fix any minor compilation problems.
> 

Right now I can't even run the mono compiler.  So I'll have to fix this
before I can make any reasonable amount of progress.

Thanks.


-- 
Paul Bone