[weston] gl-renderer: compress pixman bands to simplify geometry

Submitted by Derek Foreman on Oct. 16, 2014, 9:37 p.m.

Details

Message ID 1413495422-29740-1-git-send-email-derekf@osg.samsung.com
State Accepted
Commit f81809864e3e2ddf3edd3c0a2134be2ea1f3d16d
Headers show

Not browsing as part of any series.

Commit Message

Derek Foreman Oct. 16, 2014, 9:37 p.m.
Pixman uses y-x banded rectangles to represent regions.  We use these
y-x banded rectangles to generate triangle fans, resulting in more
geometry than strictly necessary to draw the screen.

This patch combines the bands to reduce geometry for complex scenes.
---
 src/gl-renderer.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++++++---
 1 file changed, 64 insertions(+), 3 deletions(-)

Patch hide | download patch | download mbox

diff --git a/src/gl-renderer.c b/src/gl-renderer.c
index 076c242..40447c7 100644
--- a/src/gl-renderer.c
+++ b/src/gl-renderer.c
@@ -25,6 +25,7 @@ 
 #include <GLES2/gl2.h>
 #include <GLES2/gl2ext.h>
 
+#include <stdbool.h>
 #include <stdlib.h>
 #include <string.h>
 #include <ctype.h>
@@ -296,6 +297,55 @@  calculate_edges(struct weston_view *ev, pixman_box32_t *rect,
 	return n;
 }
 
+static bool
+merge_down(pixman_box32_t *a, pixman_box32_t *b, pixman_box32_t *merge)
+{
+	if (a->x1 == b->x1 && a->x2 == b->x2 && a->y1 == b->y2) {
+		merge->x1 = a->x1;
+		merge->x2 = a->x2;
+		merge->y1 = b->y1;
+		merge->y2 = a->y2;
+		return true;
+	}
+	return false;
+}
+
+static int
+compress_bands(pixman_box32_t *inrects, int nrects,
+		   pixman_box32_t **outrects)
+{
+	bool merged;
+	pixman_box32_t *out, merge_rect;
+	int i, j, nout;
+
+	if (!nrects) {
+		*outrects = NULL;
+		return 0;
+	}
+
+	/* nrects is an upper bound - we're not too worried about
+	 * allocating a little extra
+	 */
+	out = malloc(sizeof(pixman_box32_t) * nrects);
+	out[0] = inrects[0];
+	nout = 1;
+	for (i = 1; i < nrects; i++) {
+		for (j = 0; j < nout; j++) {
+			merged = merge_down(&inrects[i], &out[j], &merge_rect);
+			if (merged) {
+				out[j] = merge_rect;
+				break;
+			}
+		}
+		if (!merged) {
+			out[nout] = inrects[i];
+			nout++;
+		}
+	}
+	*outrects = out;
+	return nout;
+}
+
 static int
 texture_region(struct weston_view *ev, pixman_region32_t *region,
 		pixman_region32_t *surf_region)
@@ -306,11 +356,20 @@  texture_region(struct weston_view *ev, pixman_region32_t *region,
 	GLfloat *v, inv_width, inv_height;
 	unsigned int *vtxcnt, nvtx = 0;
 	pixman_box32_t *rects, *surf_rects;
-	int i, j, k, nrects, nsurf;
-
-	rects = pixman_region32_rectangles(region, &nrects);
+	pixman_box32_t *raw_rects;
+	int i, j, k, nrects, nsurf, raw_nrects;
+	bool used_band_compression;
+	raw_rects = pixman_region32_rectangles(region, &raw_nrects);
 	surf_rects = pixman_region32_rectangles(surf_region, &nsurf);
 
+	if (raw_nrects < 4) {
+		used_band_compression = false;
+		nrects = raw_nrects;
+		rects = raw_rects;
+	} else {
+		nrects = compress_bands(raw_rects, raw_nrects, &rects);
+		used_band_compression = true;
+	}
 	/* worst case we can have 8 vertices per rect (ie. clipped into
 	 * an octagon):
 	 */
@@ -369,6 +428,8 @@  texture_region(struct weston_view *ev, pixman_region32_t *region,
 		}
 	}
 
+	if (used_band_compression)
+		free(rects);
 	return nvtx;
 }
 

Comments

On Thu, 16 Oct 2014 16:37:02 -0500
Derek Foreman <derekf@osg.samsung.com> wrote:

> Pixman uses y-x banded rectangles to represent regions.  We use these
> y-x banded rectangles to generate triangle fans, resulting in more
> geometry than strictly necessary to draw the screen.
> 
> This patch combines the bands to reduce geometry for complex scenes.
> ---
>  src/gl-renderer.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++++++---
>  1 file changed, 64 insertions(+), 3 deletions(-)
> 
> diff --git a/src/gl-renderer.c b/src/gl-renderer.c
> index 076c242..40447c7 100644
> --- a/src/gl-renderer.c
> +++ b/src/gl-renderer.c
> @@ -25,6 +25,7 @@
>  #include <GLES2/gl2.h>
>  #include <GLES2/gl2ext.h>
>  
> +#include <stdbool.h>
>  #include <stdlib.h>
>  #include <string.h>
>  #include <ctype.h>
> @@ -296,6 +297,55 @@ calculate_edges(struct weston_view *ev, pixman_box32_t *rect,
>  	return n;
>  }
>  
> +static bool
> +merge_down(pixman_box32_t *a, pixman_box32_t *b, pixman_box32_t *merge)
> +{
> +	if (a->x1 == b->x1 && a->x2 == b->x2 && a->y1 == b->y2) {
> +		merge->x1 = a->x1;
> +		merge->x2 = a->x2;
> +		merge->y1 = b->y1;
> +		merge->y2 = a->y2;
> +		return true;
> +	}
> +	return false;
> +}
> +
> +static int
> +compress_bands(pixman_box32_t *inrects, int nrects,
> +		   pixman_box32_t **outrects)
> +{
> +	bool merged;
> +	pixman_box32_t *out, merge_rect;
> +	int i, j, nout;
> +
> +	if (!nrects) {
> +		*outrects = NULL;
> +		return 0;
> +	}
> +
> +	/* nrects is an upper bound - we're not too worried about
> +	 * allocating a little extra
> +	 */
> +	out = malloc(sizeof(pixman_box32_t) * nrects);
> +	out[0] = inrects[0];
> +	nout = 1;
> +	for (i = 1; i < nrects; i++) {
> +		for (j = 0; j < nout; j++) {
> +			merged = merge_down(&inrects[i], &out[j], &merge_rect);
> +			if (merged) {
> +				out[j] = merge_rect;
> +				break;
> +			}
> +		}
> +		if (!merged) {
> +			out[nout] = inrects[i];
> +			nout++;
> +		}
> +	}
> +	*outrects = out;
> +	return nout;
> +}
> +
>  static int
>  texture_region(struct weston_view *ev, pixman_region32_t *region,
>  		pixman_region32_t *surf_region)
> @@ -306,11 +356,20 @@ texture_region(struct weston_view *ev, pixman_region32_t *region,
>  	GLfloat *v, inv_width, inv_height;
>  	unsigned int *vtxcnt, nvtx = 0;
>  	pixman_box32_t *rects, *surf_rects;
> -	int i, j, k, nrects, nsurf;
> -
> -	rects = pixman_region32_rectangles(region, &nrects);
> +	pixman_box32_t *raw_rects;
> +	int i, j, k, nrects, nsurf, raw_nrects;
> +	bool used_band_compression;
> +	raw_rects = pixman_region32_rectangles(region, &raw_nrects);
>  	surf_rects = pixman_region32_rectangles(surf_region, &nsurf);
>  
> +	if (raw_nrects < 4) {
> +		used_band_compression = false;
> +		nrects = raw_nrects;
> +		rects = raw_rects;
> +	} else {
> +		nrects = compress_bands(raw_rects, raw_nrects, &rects);
> +		used_band_compression = true;
> +	}
>  	/* worst case we can have 8 vertices per rect (ie. clipped into
>  	 * an octagon):
>  	 */
> @@ -369,6 +428,8 @@ texture_region(struct weston_view *ev, pixman_region32_t *region,
>  		}
>  	}
>  
> +	if (used_band_compression)
> +		free(rects);
>  	return nvtx;
>  }
>  

Hi Derek,

could you explain a bit where I can see the effect of this and how
big an improvement it is?


Thanks,
pq
On 19/11/14 08:33 AM, Pekka Paalanen wrote:
> On Thu, 16 Oct 2014 16:37:02 -0500
> Derek Foreman <derekf@osg.samsung.com> wrote:
> 
>> Pixman uses y-x banded rectangles to represent regions.  We use these
>> y-x banded rectangles to generate triangle fans, resulting in more
>> geometry than strictly necessary to draw the screen.
>>
>> This patch combines the bands to reduce geometry for complex scenes.
>> ---
>>  src/gl-renderer.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++++++---
>>  1 file changed, 64 insertions(+), 3 deletions(-)
>>
>> diff --git a/src/gl-renderer.c b/src/gl-renderer.c
>> index 076c242..40447c7 100644
>> --- a/src/gl-renderer.c
>> +++ b/src/gl-renderer.c
>> @@ -25,6 +25,7 @@
>>  #include <GLES2/gl2.h>
>>  #include <GLES2/gl2ext.h>
>>  
>> +#include <stdbool.h>
>>  #include <stdlib.h>
>>  #include <string.h>
>>  #include <ctype.h>
>> @@ -296,6 +297,55 @@ calculate_edges(struct weston_view *ev, pixman_box32_t *rect,
>>  	return n;
>>  }
>>  
>> +static bool
>> +merge_down(pixman_box32_t *a, pixman_box32_t *b, pixman_box32_t *merge)
>> +{
>> +	if (a->x1 == b->x1 && a->x2 == b->x2 && a->y1 == b->y2) {
>> +		merge->x1 = a->x1;
>> +		merge->x2 = a->x2;
>> +		merge->y1 = b->y1;
>> +		merge->y2 = a->y2;
>> +		return true;
>> +	}
>> +	return false;
>> +}
>> +
>> +static int
>> +compress_bands(pixman_box32_t *inrects, int nrects,
>> +		   pixman_box32_t **outrects)
>> +{
>> +	bool merged;
>> +	pixman_box32_t *out, merge_rect;
>> +	int i, j, nout;
>> +
>> +	if (!nrects) {
>> +		*outrects = NULL;
>> +		return 0;
>> +	}
>> +
>> +	/* nrects is an upper bound - we're not too worried about
>> +	 * allocating a little extra
>> +	 */
>> +	out = malloc(sizeof(pixman_box32_t) * nrects);
>> +	out[0] = inrects[0];
>> +	nout = 1;
>> +	for (i = 1; i < nrects; i++) {
>> +		for (j = 0; j < nout; j++) {
>> +			merged = merge_down(&inrects[i], &out[j], &merge_rect);
>> +			if (merged) {
>> +				out[j] = merge_rect;
>> +				break;
>> +			}
>> +		}
>> +		if (!merged) {
>> +			out[nout] = inrects[i];
>> +			nout++;
>> +		}
>> +	}
>> +	*outrects = out;
>> +	return nout;
>> +}
>> +
>>  static int
>>  texture_region(struct weston_view *ev, pixman_region32_t *region,
>>  		pixman_region32_t *surf_region)
>> @@ -306,11 +356,20 @@ texture_region(struct weston_view *ev, pixman_region32_t *region,
>>  	GLfloat *v, inv_width, inv_height;
>>  	unsigned int *vtxcnt, nvtx = 0;
>>  	pixman_box32_t *rects, *surf_rects;
>> -	int i, j, k, nrects, nsurf;
>> -
>> -	rects = pixman_region32_rectangles(region, &nrects);
>> +	pixman_box32_t *raw_rects;
>> +	int i, j, k, nrects, nsurf, raw_nrects;
>> +	bool used_band_compression;
>> +	raw_rects = pixman_region32_rectangles(region, &raw_nrects);
>>  	surf_rects = pixman_region32_rectangles(surf_region, &nsurf);
>>  
>> +	if (raw_nrects < 4) {
>> +		used_band_compression = false;
>> +		nrects = raw_nrects;
>> +		rects = raw_rects;
>> +	} else {
>> +		nrects = compress_bands(raw_rects, raw_nrects, &rects);
>> +		used_band_compression = true;
>> +	}
>>  	/* worst case we can have 8 vertices per rect (ie. clipped into
>>  	 * an octagon):
>>  	 */
>> @@ -369,6 +428,8 @@ texture_region(struct weston_view *ev, pixman_region32_t *region,
>>  		}
>>  	}
>>  
>> +	if (used_band_compression)
>> +		free(rects);
>>  	return nvtx;
>>  }
>>  
> 
> Hi Derek,
> 
> could you explain a bit where I can see the effect of this and how
> big an improvement it is?

If you turn on triangle fan debug (something like shift+mod+space
followed by f) then open a few windows you can see the difference.

The easiest way is to just open two terminals, put them side by side,
run "yes" or something that constantly refreshes one, then drag the
other one up and down beside it (but far enough away that the shadows
don't overlap)

Before my patch you'll see extra triangles inserted where the horizontal
boundaries of one window project across the other window.

If you've got a copy of pixman's src lying around, the comments near the
top of pixman-region.c explain how regions are split.

The patch can result in a fairly dramatic reduction in polygon count in
certain cases, but the smaller set of polygons will have the same coverage.

Honestly, I'm not sure how to benchmark this.


Since we're sort of on the topic, is there anywhere we gain anything
from y-x banded regions?  I'm wondering if it would be worthwhile to
replace pixman's region code with something that doesn't band.  I think
this would let us drop the pixman dependency when not building the
pixman renderer...
Hi,

On 19 November 2014 14:58, Derek Foreman <derekf@osg.samsung.com> wrote:

> Since we're sort of on the topic, is there anywhere we gain anything
> from y-x banded regions?  I'm wondering if it would be worthwhile to
> replace pixman's region code with something that doesn't band.  I think
> this would let us drop the pixman dependency when not building the
> pixman renderer...


Not really, no. Pixman only does it because the X server requires regions
to be marked as YX-banded to be deigned valid (or 'complete', as an FBO
analogy), and a number of the rendering algorithms in the server depend on
it.

We don't have any of that, so can happily do without banding. A patch to
Pixman which would optionally drop the strict banding would be nice, but if
there's a small enough region implementation we could use instead, that
could work.

Cheers,
Dan
On Wed, Nov 19, 2014 at 7:22 AM, Daniel Stone <daniel@fooishbar.org> wrote:

> Hi,
>
> On 19 November 2014 14:58, Derek Foreman <derekf@osg.samsung.com> wrote:
>
>> Since we're sort of on the topic, is there anywhere we gain anything
>> from y-x banded regions?  I'm wondering if it would be worthwhile to
>> replace pixman's region code with something that doesn't band.  I think
>> this would let us drop the pixman dependency when not building the
>> pixman renderer...
>
>
> Not really, no. Pixman only does it because the X server requires regions
> to be marked as YX-banded to be deigned valid (or 'complete', as an FBO
> analogy), and a number of the rendering algorithms in the server depend on
> it.
>
> We don't have any of that, so can happily do without banding. A patch to
> Pixman which would optionally drop the strict banding would be nice, but if
> there's a small enough region implementation we could use instead, that
> could work.
>

It's more that the algorithms for combining regions only work in the case
where you have a vertically-sorted list of horizontal bands. So, you would
have to come up with an entirely new algorithm for pixman_region_union,
pixman_region_subtract, etc. if want some other format.

What's the format you're suggesting? If we flip the axes (horizontally
sorted list of vertical bands), then it will work fine for the move up/down
case, but break for the left/right case.

Derek's approach of post-processing the bands to make a minimal set of
overall rectangles seems fine to me.

If we only need union, then we could very simply create our own region
class that did what we wanted. [0]

[0] Or steal
http://cgit.freedesktop.org/plymouth/tree/src/libply/ply-region.c


> Cheers,
> Dan
>
> _______________________________________________
> wayland-devel mailing list
> wayland-devel@lists.freedesktop.org
> http://lists.freedesktop.org/mailman/listinfo/wayland-devel
>
>
On Wed, 19 Nov 2014 09:03:31 -0800
"Jasper St. Pierre" <jstpierre@mecheye.net> wrote:

> On Wed, Nov 19, 2014 at 7:22 AM, Daniel Stone <daniel@fooishbar.org> wrote:
> 
> > Hi,
> >
> > On 19 November 2014 14:58, Derek Foreman <derekf@osg.samsung.com> wrote:
> >
> >> Since we're sort of on the topic, is there anywhere we gain anything
> >> from y-x banded regions?  I'm wondering if it would be worthwhile to
> >> replace pixman's region code with something that doesn't band.  I think
> >> this would let us drop the pixman dependency when not building the
> >> pixman renderer...
> >
> >
> > Not really, no. Pixman only does it because the X server requires regions
> > to be marked as YX-banded to be deigned valid (or 'complete', as an FBO
> > analogy), and a number of the rendering algorithms in the server depend on
> > it.
> >
> > We don't have any of that, so can happily do without banding. A patch to
> > Pixman which would optionally drop the strict banding would be nice, but if
> > there's a small enough region implementation we could use instead, that
> > could work.
> >
> 
> It's more that the algorithms for combining regions only work in the case
> where you have a vertically-sorted list of horizontal bands. So, you would
> have to come up with an entirely new algorithm for pixman_region_union,
> pixman_region_subtract, etc. if want some other format.
> 
> What's the format you're suggesting? If we flip the axes (horizontally
> sorted list of vertical bands), then it will work fine for the move up/down
> case, but break for the left/right case.
> 
> Derek's approach of post-processing the bands to make a minimal set of
> overall rectangles seems fine to me.
> 
> If we only need union, then we could very simply create our own region
> class that did what we wanted. [0]
> 
> [0] Or steal
> http://cgit.freedesktop.org/plymouth/tree/src/libply/ply-region.c

$ git grep -E 'pixman_region.._.+\(' | egrep -o 'pixman_region.._.+\(' | sort | uniq -c | sort -n
      1 pixman_region32_contains_point (
      1 pixman_region32_equal(
      1 pixman_region32_init_rects(
      1 pixman_region32_translate(&final_region, (int)view_x, (
      3 pixman_region32_init_with_extents(
      3 pixman_region32_intersect_rect(
      8 pixman_region32_clear(
     10 pixman_region32_contains_point(
     12 pixman_region32_translate(
     14 pixman_region32_intersect(
     15 pixman_region32_extents(
     15 pixman_region32_rectangles(
     15 pixman_region32_union(
     15 pixman_region32_union_rect(
     17 pixman_region32_not_empty(
     23 pixman_region32_subtract(
     25 pixman_region32_copy(
     26 pixman_region32_init_rect(
     63 pixman_region32_init(
     88 pixman_region32_fini(

We even have wl_region.subtract in the core protocol, so union only is
not enough.


Thanks,
pq
On Wed, 19 Nov 2014 08:58:14 -0600
Derek Foreman <derekf@osg.samsung.com> wrote:

> On 19/11/14 08:33 AM, Pekka Paalanen wrote:
> > On Thu, 16 Oct 2014 16:37:02 -0500
> > Derek Foreman <derekf@osg.samsung.com> wrote:
> > 
> >> Pixman uses y-x banded rectangles to represent regions.  We use these
> >> y-x banded rectangles to generate triangle fans, resulting in more
> >> geometry than strictly necessary to draw the screen.
> >>
> >> This patch combines the bands to reduce geometry for complex scenes.
> >> ---
> >>  src/gl-renderer.c | 67 ++++++++++++++++++++++++++++++++++++++++++++++++++++---
> >>  1 file changed, 64 insertions(+), 3 deletions(-)

> > 
> > Hi Derek,
> > 
> > could you explain a bit where I can see the effect of this and how
> > big an improvement it is?
> 
> If you turn on triangle fan debug (something like shift+mod+space
> followed by f) then open a few windows you can see the difference.
> 
> The easiest way is to just open two terminals, put them side by side,
> run "yes" or something that constantly refreshes one, then drag the
> other one up and down beside it (but far enough away that the shadows
> don't overlap)
> 
> Before my patch you'll see extra triangles inserted where the horizontal
> boundaries of one window project across the other window.
> 
> If you've got a copy of pixman's src lying around, the comments near the
> top of pixman-region.c explain how regions are split.
> 
> The patch can result in a fairly dramatic reduction in polygon count in
> certain cases, but the smaller set of polygons will have the same coverage.
> 
> Honestly, I'm not sure how to benchmark this.

Oh yeah, I see it now if I use the DRM backend. On X11 backend I think
it always paints everything which means the mesh is a lot more messy.

One way to measure would be to print the vertex count of a repaint
cycle. I'd expect the difference in performance to be negligible. I
believe the only difference would be in CPU time, the overhead of
submitting draws to the GPU is probably a lot more than what a few less
vertices does, and the fragment count would be roughly the same anyway.

Maybe it could be profiled with 'perf', since the effect should be on
CPU time?

There is an Acked-by from Jasper, and Tested-by me, but I'm still not
sure this is worth the code it adds... to be honest, it feels like
premature optimization to me.

OTOH, it reduces the box-count, which reduces both calculate_edges and
glDrawArrays calls, so...

Pushed!


Thanks,
pq
On 21/11/14 04:32 AM, Pekka Paalanen wrote:
> On Wed, 19 Nov 2014 09:03:31 -0800
> "Jasper St. Pierre" <jstpierre@mecheye.net> wrote:
> 
>> On Wed, Nov 19, 2014 at 7:22 AM, Daniel Stone <daniel@fooishbar.org> wrote:
>>
>>> Hi,
>>>
>>> On 19 November 2014 14:58, Derek Foreman <derekf@osg.samsung.com> wrote:
>>>
>>>> Since we're sort of on the topic, is there anywhere we gain anything
>>>> from y-x banded regions?  I'm wondering if it would be worthwhile to
>>>> replace pixman's region code with something that doesn't band.  I think
>>>> this would let us drop the pixman dependency when not building the
>>>> pixman renderer...
>>>
>>>
>>> Not really, no. Pixman only does it because the X server requires regions
>>> to be marked as YX-banded to be deigned valid (or 'complete', as an FBO
>>> analogy), and a number of the rendering algorithms in the server depend on
>>> it.
>>>
>>> We don't have any of that, so can happily do without banding. A patch to
>>> Pixman which would optionally drop the strict banding would be nice, but if
>>> there's a small enough region implementation we could use instead, that
>>> could work.
>>>
>>
>> It's more that the algorithms for combining regions only work in the case
>> where you have a vertically-sorted list of horizontal bands. So, you would
>> have to come up with an entirely new algorithm for pixman_region_union,
>> pixman_region_subtract, etc. if want some other format.
>>
>> What's the format you're suggesting? If we flip the axes (horizontally
>> sorted list of vertical bands), then it will work fine for the move up/down
>> case, but break for the left/right case.
>>
>> Derek's approach of post-processing the bands to make a minimal set of
>> overall rectangles seems fine to me.
>>
>> If we only need union, then we could very simply create our own region
>> class that did what we wanted. [0]
>>
>> [0] Or steal
>> http://cgit.freedesktop.org/plymouth/tree/src/libply/ply-region.c
> 
> $ git grep -E 'pixman_region.._.+\(' | egrep -o 'pixman_region.._.+\(' | sort | uniq -c | sort -n
>       1 pixman_region32_contains_point (
>       1 pixman_region32_equal(
>       1 pixman_region32_init_rects(
>       1 pixman_region32_translate(&final_region, (int)view_x, (
>       3 pixman_region32_init_with_extents(
>       3 pixman_region32_intersect_rect(
>       8 pixman_region32_clear(
>      10 pixman_region32_contains_point(
>      12 pixman_region32_translate(
>      14 pixman_region32_intersect(
>      15 pixman_region32_extents(
>      15 pixman_region32_rectangles(
>      15 pixman_region32_union(
>      15 pixman_region32_union_rect(
>      17 pixman_region32_not_empty(
>      23 pixman_region32_subtract(
>      25 pixman_region32_copy(
>      26 pixman_region32_init_rect(
>      63 pixman_region32_init(
>      88 pixman_region32_fini(
> 
> We even have wl_region.subtract in the core protocol, so union only is
> not enough.

Yup, we've got union, subtract and intersect.  It's possible that all
our intersection usage is region + rect or region + region containing a
single rect.  I'm not sure if this lack of generality makes anything
easier though.

Jasper's link is a great start, shame about the license.

Some internal discussion over here has turned up some resentment towards
the pixman dependency, so I think re-implementing the region code can
have a couple of benefits:
Losing the y-x bandedness
Losing the pixman dependency (when not building the pixman renderer)

If there's any interest, I'm willing to code it up and see how it turns
out - should be pretty easy to make a test case that links pixman and
does identical (random) operations with both implementations to test
correctness, performance, and resulting number of regions...