Re: [PATCH]: Updated new sparse bitmap patch

[Ian Lance Taylor <iant at google dot com>]

"Daniel Berlin" <dberlin@dberlin.org> writes:

> +   Operations on the entire bitmap are also more efficient than
> +   bitmaps, as they are all operating on contiguous memory, and can be
> +   easily vectorized.  They are all O(number of words) + O(number of
> +   bits that may end up in the destination), as the appropriate
> +   operation is first performed on the word mask, and then only those
> +   elements that may generate results are touched.

Minor point: the first sentence will be slightly clearer if you add
"linked list" before the word "bitmaps."  (And technically I think you
should "linked-list bitmap" rather than "linked list bitmap"
throughout, but it doesn't matter.)

> +   Memory wise, the ebitmap starts out using less memory than the
> +   linked list bitmap, but it's size in memory is technically bounded
> +   by (size of the highest set bit) / (size of a word).  This is
> +   because the mask is non-sparse.  The mask could be transformed into
> +   a sparse bitmap at the cost of making bit testing *theoretically*
> +   slower (real world numbers have not been computed yet as to whether
> +   it matters or not).  */

In the second line, change "it's" to "its".  When you say "size of the
highest bit set" I think it would be clearer to say "index" rather
than "size".  And if I understand correctly I think the size is
bounded by
  ((index of the highest bit set) / (size of a word)
   + (index of the highest bit set) / ((size of a word) * (size of a word)))
if all the bits are set.


> +/* Find the last set bit in EBITMAP map.  */
> +
> +unsigned int
> +ebitmap_last_set_bit (ebitmap map)
> +{
> +  unsigned int i = 0;
> +  ebitmap_iterator ebi;
> +
> +  /* This is not the fastest way to do this, we could simply look for
> +     the popcount, and start there, but this function is not used
> +     anywhere speed critical.  */
> +  EXECUTE_IF_SET_IN_EBITMAP (map, 0, i, ebi);
> +
> +  return i;
> +}

In the comment you should capitalize "map", not "ebitmap".

It seems that this will return 0 if there are no bits set or if only
the first bit is set.  That seems unwise.  sbitmap_last_bit_set will
return -1 if there are no bits set, and this should do the same.  Of
course, that means that the return type should be 'int' rather than
'unsigned int'.


> +ebitmap
> +ebitmap_alloc (unsigned int size)
> +{
> +  ebitmap ret = xmalloc (sizeof (struct ebitmap_def));
> +  if (size == 0)
> +    size = EBITMAP_ELT_BITS;
> +  ebitmap_array_init (ret, size / EBITMAP_ELT_BITS);
> +  ret->wordmask = sbitmap_alloc_with_popcount (size);
> +  sbitmap_zero (ret->wordmask);
> +  ret->numwords = 0;
> +  ret->cache = NULL;
> +  ret->cacheindex = 0;
> +
> +  return ret;
> +}

This function needs a comment.

It's not clear to me what the SIZE parameter means.  It may mean that
the ebitmap should be set up so that it does not additional allocation
for bits indexed from 0 to SIZE - 1.  If that is the case, the
function is missing code to round up SIZE to the next multiple of
EBITMAP_ELT_BITS.

> +/* Clear BIT from ebitmap MAP.  */
> +
> +void
> +ebitmap_clear_bit (ebitmap map, unsigned int bit)
> +{
> +  unsigned int wordindex = bit / EBITMAP_ELT_BITS;
> +  unsigned int eltwordindex;
> +  unsigned int bitindex, shift;
> +
> +  /* If the bit can't exist in our bitmap, just return.  */
> +  if (map->numwords == 0)
> +    return;
> +
> +  if (wordindex >= map->wordmask->n_bits
> +      || !TEST_BIT (map->wordmask, wordindex))
> +    return;
> +
> +  eltwordindex = sbitmap_popcount (map->wordmask, wordindex);
> +
> +  bitindex = bit % EBITMAP_ELT_BITS;
> +  shift = bitindex;
> +
> +  map->elts[eltwordindex] &= ~(((EBITMAP_ELT_TYPE)1) << shift);
> +
> +  /* Clear out the empty words.  */
> +  if (map->elts[eltwordindex] == 0)
> +    {
> +      unsigned int ix;
> +
> +      if (map->cache != NULL && map->cacheindex == eltwordindex)
> +	map->cache = NULL;
> +
> +      RESET_BIT (map->wordmask, wordindex);
> +
> +      for (ix = eltwordindex; ix < map->numwords-1; ix++)
> +	map->elts[ix] = map->elts[ix + 1];
> +      map->numwords--;
> +    }
> +}

Why doesn't this function use the cache?  At least to test if the
cache points to the word from which the bit is being removed?

Why not use memmove rather than an explicit loop?


> +      for (i = map->numwords; i > count; i--)
> +	{
> +	  EBITMAP_ELT_TYPE *newelt;
> +	  newelt = ebitmap_array_grow_get (map, i);
> +	  *newelt = ebitmap_array_get (map, i - 1);
> +	}

Why not just use memmove?


> +/* Perform the operation DST &= SRC.  */
> +
> +void
> +ebitmap_and_into (ebitmap dst, ebitmap src)
> +{
> +  sbitmap_iterator sbi;
> +  unsigned int i;
> +  unsigned int neweltindex = 0;
> +  unsigned int dsteltindex = 0;
> +  unsigned int srceltindex = 0;
> +
> +  gcc_assert (dst != src);
> +
> +  dst->cache = NULL;
> +
> +  /* Short circuit the empty bitmap cases.  */
> +  if (src->numwords == 0 || dst->numwords == 0)
> +    {
> +      ebitmap_clear (dst);
> +      return;
> +    }
> +
> +  /* AND the masks, then walk the words that may actually appear in
> +     the result, AND'ing them.  */
> +  sbitmap_a_and_b (dst->wordmask, dst->wordmask, src->wordmask);
> +
> +  EXECUTE_IF_SET_IN_SBITMAP (dst->wordmask, 0, i, sbi)
> +    {
> +      bool srchasword;
> +
> +      /* If it really made a speed difference, we could iterate both
> +	 masks in parallel so the src testing didn't look like random
> +	 bittests.  */
> +      srchasword = TEST_BIT (src->wordmask, i);

Wait a second.  You just did an and into dst->wordmask.  How could
this bit ever be clear in src->wordmask?

> +
> +      if (srchasword)
> +	{
> +	  EBITMAP_ELT_TYPE tmpword = ebitmap_array_get (src, srceltindex++);
> +	  tmpword &= ebitmap_array_get (dst, dsteltindex++);
> +	  if (tmpword != 0)
> +	    {
> +	      EBITMAP_ELT_TYPE *dstplace;
> +	      dstplace = ebitmap_array_grow_get (dst, neweltindex++);
> +	      *dstplace = tmpword;
> +	    }
> +	  else
> +	    RESET_BIT (dst->wordmask, i);
> +	}
> +      else
> +	{
> +	  dsteltindex++;

A good thing srchasword must be true, since this looks flat wrong.
You're skipping the word without clearing it.

> +	  RESET_BIT (dst->wordmask, i);
> +	}
> +    }
> +#ifdef EBITMAP_DEBUGGING
> +  {
> +    unsigned int i;
> +
> +    for (i = 0; i <  dst->numwords; i++)
> +      gcc_assert (dst->elts[i] != 0);
> +
> +    verify_popcount (dst->wordmask);
> +    gcc_assert (sbitmap_popcount (dst->wordmask,
> +				  dst->wordmask->n_bits) == dst->numwords);
> +    gcc_assert (ebitmap_last_set_bit (dst) < num_ssa_names);

What does num_ssa_names have to do with anything?

> +  }
> +#endif
> +  dst->numwords = neweltindex;
> +}



> +/* Perform the operation DST = SRC1 & SRC2.  */
> +
> +void
> +ebitmap_and (ebitmap dst, ebitmap src1, ebitmap src2)
> +{
> +  sbitmap_iterator sbi;
> +  unsigned int i;
> +  unsigned int neweltindex = 0;
> +  unsigned int src1eltindex = 0;
> +  unsigned int src2eltindex = 0;
> +
> +  dst->cache = NULL;
> +  if (src1->numwords == 0 || src2->numwords == 0)
> +    {
> +      ebitmap_clear (dst);
> +      return;
> +    }
> +
> +  dst->wordmask
> +    = sbitmap_resize (dst->wordmask,
> +		      MAX (src1->wordmask->n_bits, src2->wordmask->n_bits),
> +		      0);

Why not MIN instead of MAX?

> +    gcc_assert (ebitmap_last_set_bit (dst) < num_ssa_names);

Again with the num_ssa_names.


> +/* Perform the operation DST |= SRC.  */
> +
> +bool
> +ebitmap_ior_into (ebitmap dst, ebitmap src)

What does the return value mean?  It should be mentioned in the
comment.

> +  /* We can do without the temp mask if it's faster, but it would mean
> +     touching more words in the actual dense vector.  */
> +  tempmask = sbitmap_alloc (MAX (srcsize, dstsize));
> +  sbitmap_zero (tempmask);
> +  if (srcsize == dstsize)
> +    {
> +      sbitmap_a_or_b (tempmask, dst->wordmask, src->wordmask);
> +    }
> +  else
> +    {
> +      dst->wordmask = sbitmap_resize (dst->wordmask, MAX (srcsize, dstsize),
> +				      0);
> +      if (MAX (srcsize, dstsize) == srcsize)

Just write "if (srcsize >= dstsize)".

> +    gcc_assert (ebitmap_last_set_bit (dst) < num_ssa_names);

Another num_ssa_names.

> +/* Perform the operation DST = SRC1 | SRC2.  */
> +
> +bool
> +ebitmap_ior (ebitmap dst, ebitmap src1, ebitmap src2)
> +{

The comment should describe the return value.

> +  unsigned int src1size = src1->wordmask->n_bits;
> +  unsigned int src2size = src2->wordmask->n_bits;
> +  sbitmap_iterator sbi;
> +  unsigned int i;
> +  sbitmap tempmask;
> +  unsigned int neweltindex = 0;
> +  unsigned int src1eltindex = 0;
> +  unsigned int src2eltindex = 0;
> +  bool changed = false;
> +  EBITMAP_ELT_TYPE *newarray;
> +  unsigned int newarraysize;
> +#ifdef EBITMAP_DEBUGGING
> +  ebitmap dstcopy = ebitmap_alloc (1);
> +  ebitmap_copy (dstcopy, dst);
> +#endif
> +
> +  dst->cache = NULL;
> +  tempmask = sbitmap_alloc_with_popcount (MAX (src1size, src2size));
> +  sbitmap_zero (tempmask);
> +  if (src1size == src2size)
> +    {
> +      sbitmap_a_or_b (tempmask, src1->wordmask, src2->wordmask);
> +    }
> +  else
> +    {
> +      if (MAX (src1size, src2size) == src1size)

"if (src1size >= src2size)"

(If you really want to CSE MAX, then do so explicitly in a local
variable.)

> +      if (src1hasword && src2hasword)
> +	{
> +	  tmpword = ebitmap_array_get (src1, src1eltindex++)
> +	    | ebitmap_array_get (src2, src2eltindex++);

Use parentheses to make emacs do the indentation correctly.

> +	  newarray[neweltindex++] = tmpword;
> +	}
> +      else if (src1hasword)
> +	{
> +	  tmpword = ebitmap_array_get (src1, src1eltindex++);
> +	  newarray [neweltindex++] = tmpword;
> +	}
> +      else
> +	{
> +	  tmpword = ebitmap_array_get (src2, src2eltindex++);
> +	  newarray [neweltindex++] = tmpword;
> +	}
> +
> +      if (i >= dst->wordmask->n_bits ||!TEST_BIT (dst->wordmask, i))

Space after "||".

> +  gcc_assert (ebitmap_last_set_bit (dst) < num_ssa_names);

And another num_ssa_names.

> +/* Perform the operation DST &= ~SRC.  */
> +
> +bool
> +ebitmap_and_compl_into (ebitmap dst, ebitmap src)
> +{

Comment should describe return value.

> +    gcc_assert (ebitmap_last_set_bit (dst) < num_ssa_names);

Another num_ssa_names.


> +/* Perform the operation DST = SRC1 & ~SRC2.  */
> +
> +bool
> +ebitmap_and_compl (ebitmap dst, ebitmap src1, ebitmap src2)
> +{

Comment should describe return value.

> +  unsigned int src1size = src1->wordmask->n_bits;
> +  sbitmap_iterator sbi;
> +  unsigned int i;
> +  sbitmap tempmask;
> +  unsigned int neweltindex = 0;
> +  unsigned int src1eltindex = 0;
> +  bool changed = false;
> +  EBITMAP_ELT_TYPE *newarray;
> +  unsigned int newarraysize;
> +
> +  /* XXX: Optimize like the into version.  */
> +  dst->cache = NULL;
> +  tempmask = sbitmap_alloc_with_popcount (src1size);
> +  sbitmap_zero (tempmask);
> +  sbitmap_copy (tempmask, src1->wordmask);
> +
> +  newarraysize = src1->numwords;
> +  newarray = xmalloc (newarraysize * sizeof (EBITMAP_ELT_TYPE));
> +
> +  EXECUTE_IF_SET_IN_SBITMAP (src1->wordmask, 0, i, sbi)
> +    {
> +      bool src2hasword;
> +      EBITMAP_ELT_TYPE tmpword;
> +
> +      src2hasword = (i < src2->wordmask->n_bits
> +		    && TEST_BIT (src2->wordmask, i));
> +
> +      if (src2hasword)
> +	{
> +	  unsigned int src2count = sbitmap_popcount (src2->wordmask, i);
> +	  tmpword = ebitmap_array_get (src1, src1eltindex++)
> +	    & ~(ebitmap_array_get (src2, src2count));

Add parentheses to get correct indentation.

> +  gcc_assert (ebitmap_last_set_bit (dst) < num_ssa_names);

Another num_ssa_names.


> +/* Perform the operation DST = A | (B & ~C).  */
> +
> +bool
> +ebitmap_ior_and_compl (ebitmap dst, ebitmap a, ebitmap b, ebitmap c)
> +{

Comment should mention return value.

> +/* Return true if ebitmap DST is equal to ebitmap SRC.  */
> +
> +bool
> +ebitmap_equal_p (ebitmap dst, ebitmap src)
> +{
> +  unsigned int i;
> +  unsigned int which = MIN (dst->wordmask->size, src->wordmask->size);
> +
> +  if (dst->numwords != src->numwords)
> +    return false;
> +
> +  /* sbitmap_equal compares up to the size of the first argument, so
> +     if the two sbitmaps are not equally sized, we need to pass the
> +     smaller one as the first argument, or it will crash.  */
> +  if (which == dst->wordmask->size
> +      && !sbitmap_equal (dst->wordmask, src->wordmask))
> +    return false;
> +  else if (which == src->wordmask->size
> +	   && !sbitmap_equal (src->wordmask, dst->wordmask))
> +    return false;
> +
> +  for (i = 0; i < dst->numwords; i++)
> +    {
> +      if (dst->elts[i] != src->elts[i])
> +	return false;
> +    }
> +  return true;
> +}

Just use memcmp for the final loop.


> +#ifndef GCC_EBITMAP_H
> +#define GCC_EBITMAP_H
> +#include "sbitmap.h"

Put a blank line between the #define and the #include.

> +#define EBITMAP_ELT_BITS ((unsigned) HOST_BITS_PER_WIDEST_FAST_INT)
> +#define EBITMAP_ELT_TYPE unsigned HOST_WIDEST_FAST_INT
> +
> +typedef struct ebitmap_def
> +{  
> +  EBITMAP_ELT_TYPE *elts;	/* non-zero element array.  */
> +  unsigned int n_elts;		/* number of elements in the array.  */
> +  sbitmap wordmask;		/* wordmask saying which words are
> +				   non-zero.  */
> +  unsigned int numwords;	/* number of non-zero words.  */
> +  EBITMAP_ELT_TYPE *cache;	/* last tested element, or NULL.  */
> +  unsigned int cacheindex;	/* which word cache is.  */
> +} *ebitmap;

It's probably worth grouping the pointers (including sbitmap) together
to avoid alignment holes on an LP64 architecture.

> +#define ebitmap_empty_p(MAP) ((MAP)->numwords == 0)
> +#define ebitmap_free(MAP)  (free((MAP)->elts), sbitmap_free ((MAP)->wordmask), free((MAP)))

Use a backlash to avoid an overly long line.

> +static inline void
> +ebitmap_iter_next (ebitmap_iterator *i)
> +{
> +  i->word >>= 1;
> +  i->bit_num ++;
> +}

No space before the "++".

> Index: Makefile.in
> ===================================================================
> --- Makefile.in	(revision 123086)
> +++ Makefile.in	(working copy)
> @@ -1152,7 +1152,8 @@ OBJS-common = \
>  	version.o \
>  	vmsdbgout.o \
>  	web.o \
> -	xcoffout.o
> +	xcoffout.o \
> +	ebitmap.o

I just alphabetized all the files.  DON'T MESS IT UP.

> +ebitmap.o: ebitmap.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) $(RTL_H) \
> +    $(FLAGS_H) $(OBSTACK_H) ebitmap.h sbitmap.h

Why does ebitmap.c include rtl.h?

Since ebitmap.h includes sbitmap.h, you are going to save trouble down
the road by adding a Makefile variable EBITMAP_H.

Hope this helps.

Ian