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

[Peter Wang]

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.

> library/version_array.m:
>     As above.
> 
> runtime/mercury_bitmap.h:
>     Add some macros for initialising bitmaps and testing, setting and clearing
>     their bits.
> 
> library/bitmap.m:
> java/runtime/MercuryBitmap.java:
>     Move the MercuryBitmap class into the runtime library.  This makes it
>     easier for other standard library modules to use this Java
>     class.
> 
> tests/hard_coded/version_array_test.exp:
> tests/hard_coded/version_array_test.m:
>     Ensure that the test verifies that rolling back updates to a version
>     array rolls back changes in the correct order: If two updates modify the
>     same cell, then the older one should be visible in the result.
> 
>     Use longer arrays so that the bitmap used in the rollback code is more
>     than one byte in length.

> 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.

> +
> +    @Override
> +    public boolean equals(Object that) {
> +        if (this == that) {
> +            return true;
> +        }
> +        if (that instanceof MercuryBitmap) {
> +            MercuryBitmap other = (MercuryBitmap)that;
> +            return this.num_bits == other.num_bits
> +                && java.util.Arrays.equals(this.elements, other.elements);
> +        }
> +        return false;
> +    }
> +
> +    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.

> +
> +    public static int byteIndexForBit(int bit) {
> +        return bit / BITS_PER_BYTE;
> +    }
> +
> +    public static int bitIndexWithinByte(int bit) {
> +        return bit % BITS_PER_BYTE;
> +    }
> +
> +}

> diff --git a/runtime/mercury_bitmap.h b/runtime/mercury_bitmap.h
> index 64427eb..94f5240 100644
> --- a/runtime/mercury_bitmap.h
> +++ b/runtime/mercury_bitmap.h
> @@ -159,9 +159,42 @@ MR_String MR_bitmap_to_quoted_string_saved_hp(MR_ConstBitmapPtr,
>  #define MR_bitmap_length_in_bytes(bits)                                 \
>          (((bits) / MR_BITS_PER_BYTE) + (((bits) % MR_BITS_PER_BYTE) != 0))
>  
> +#define MR_bitmap_byte_index_for_bit(bit) \
> +    ((bit) / MR_BITS_PER_BYTE)
> +#define MR_bitmap_bit_index_within_byte(bit) \
> +    ((bit) % MR_BITS_PER_BYTE)

Line up the backslashes.

> +
> +#define MR_bitmap_zero(bitmap)                                          \
> +    do {                                                                \
> +        size_t bytes = MR_bitmap_length_in_bytes((bitmap)->num_bits);   \
> +        memset((bitmap)->elements, 0, bytes);                           \
> +    } while(0);

Delete semicolons (two more below)

> +#define MR_bitmap_get(bitmap, bit)                                      \
> +    (!!(((bitmap)->elements[MR_bitmap_byte_index_for_bit(bit)]) &       \
> +        (1 << MR_bitmap_bit_index_within_byte(bit))))

MR_bitmap_get_bit ?

> +#define MR_bitmap_set(bitmap, bit)                                      \
> +    do {                                                                \
> +        MR_uint_least8_t    byte;                                       \
> +                                                                        \
> +        byte = (bitmap)->elements[MR_bitmap_byte_index_for_bit(bit)];   \
> +        byte |= 1 << MR_bitmap_bit_index_within_byte(bit);              \
> +        (bitmap)->elements[MR_bitmap_byte_index_for_bit(bit)] = byte;   \
> +    } while (0);

MR_bitmap_set_bit ?

> +#define MR_bitmap_clear(bitmap, bit)                                    \
> +    do {                                                                \
> +        MR_uint_least8_t    byte;                                       \
> +                                                                        \
> +        byte = (bitmap)->elements[MR_bitmap_byte_index_for_bit(bit)];   \
> +        byte &= ~(1 << MR_bitmap_bit_index_within_byte(bit));           \
> +        (bitmap)->elements[MR_bitmap_byte_index_for_bit(bit)] =  byte;  \
> +    } while (0);

MR_bitmap_clear_bit ?

Again, unused.

>  /*
> -** void MR_allocate_bitmap_msg(MR_String ptr, size_t bytes,
> -**          int bits_in_last_byte, MR_Code *proclabel):
> +** void MR_allocate_bitmap_msg(MR_BitmapPtr ptr, size_t bits,
> +**          MR_Code *proclabel):
>  ** Allocate enough word aligned memory to hold `bytes' bytes.  Also

Please fix this sentence as well.

>  ** record for memory profiling purposes the location, proclabel, of the
>  ** allocation if profiling is enabled.

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.

Peter