Re: Normalizing the bitmap APIs.

[Richard Biener <richard dot guenther at gmail dot com>]

On Thu, Oct 11, 2012 at 3:08 AM, Lawrence Crowl <crowl@googlers.com> wrote:
> As part of our effort to make programming in GCC easier, we would like
> to improve the interface to bitmaps.
>
> There are three bitmap types, each with disparate operations and
> function names.  This disparity causes problems
> * when changing a variable from one type to another,
> * when moving one's attention from one type to another.
> We would like to change the existing function names to be more uniform.
>
> The most complicated operations
> are those that produce a bitwise result
> for one or more binary bitwise operations.
> These do work as if written with one of the following forms:
>
>   d = a OP b
>   d = a OP b with reporting of a change to d
>   a OP= b
>   a OP= b with reporting of a change to a
>
>   d = a OP (b OP c)
>   d = a OP (b OP c) with reporting of a change to d
>   a OP= (b OP c)
>   a OP= (b OP c) with reporting of a change to a
>
> where OP is one of
>
>   OP  TAG  operation description
>    &  and  intersection
>    |  ior  union
>    ^  xor  inequivalence
>    -  dif  set difference (reverse relative complement) (a&~b)
>    /  rdf  reverse set difference (relative complement) (~a&b)
>
> One approach is to add operators for the bitmap operations.
> Unfortunately, the straightforward way to do that would introduce
> temporary variables where none exist now, which would result in a net
> loss of performance.  For example,
>   bitmap_a_and_b (dest, a, b);
> written as
>   dest = a & b;
> would result in code that is effectively
>   tmp = a & b;
>   dest = tmp;
> and would require allocation and copying of tmp.
>
> We can avoid this run-time expense by using expression templates
> http://en.wikipedia.org/wiki/Expression_templates.  However, that
> change would require substantial implementation work and substantial
> compile-time effort to untangle the templates.
>
> Also, unfortunately, with C++2003 as the implementation language and
> the existing use of unions in critical data structures like trees,
> the overloading of assignment operators would either be prohibited or
> require a significantly clumsier syntax than one would like.
>
> Instead, I propose a more modest change, preserving the existing call
> syntax, but normalizing it so that function names are predictable and
> general.  By overloading these operations on the type of the bitmap,
> we can use a single name for a single action, regardless of type.
> Doing so eases the task of changing types, as may be desiriable to
> obtain a different performance profile.
>
> For the operations above, I suggest names as follows:
>
>   assign_TAG (d = a OP b)
>   assign_TAG_changed
>   TAG_assign (a OP= b)
>   TAG_assign_changed
>
>   assign_TAG_TAG (d = a OP (b OP c))
>   assign_TAG_TAG_changed
>   TAG_assign_TAG (a OP= (b OP c))
>   TAG_assign_TAG_changed
>
> For example, sbitmap_a_or_b_cg (d, a, b)
> becomes assign_ior_changed (d, a, b);
> and bitmap_ior_and_compl_into (a, b, c)
> becomes ior_assign_dif (a, b, c).
>
> It is not surprising that some expressions using change-returning
> functions do not use the function result.  However, it appears that
> some such functions never have their result used.  I would propose
> using void versions everwhere that the result is not used.  These can
> be implemented with the non-void versions easily enough.
>
> Testing for a change also applies to the single bit clear and set
> routines for bitmap, but not ebitmap or sbitmap.  It would probably
> be prudent to make names for both variants, and implement the testing
> version only when needed.  The non-testing version can be implemented
> via the testing version in the short term.
>
> Other operations are simpler in structure, but still need common
> names.  I propose the following:
>
>   clear (bitmap) -> void
>   clear_range (bitmap, unsigned, unsigned) -> void
>   assign_not (bitmap, const_bitmap) -> void
>   has_intersection (const_bitmap, const_bitmap) -> bool
>   is_subset_of (const_bitmap, const_bitmap) -> bool
>   cardinality (const_bitmap) -> unsigned
>   cardinality_of_range (const_bitmap, unsigned, unsigned) -> unsigned
>   is_empty (const_bitmap) -> bool
>   is_singleton (const_bitmap) -> bool
>   first_set_bit (const_bitmap) -> unsigned
>   last_set_bit (const_bitmap) -> unsigned
>   test_bit (const_bitmap, unsigned) -> bool
>
> I propose to leave the allocation, iteration, vector, debug/dump/print
> and functions alone for the time being.
>
> Comments?

In general unifying the interface to the various bitmap implementations
occured to me as well.  I also quickly settled on function overloads
for this.

Rather than inventing new names I'd pick the most suitable existing
set of names - which is those from bitmap.h.

I'd rather not mix this with any kind of further C++-ification (that is
introduction of member functions or operator overloads).

Just my 2 cents,
Richard.

> --
> Lawrence Crowl