Improve redraw performance by making `Clip` be a `Region` instead of `Rectangle`

[tig]

TUI apps need to be performant under highly-constrained conditions, such as over SSH. Currently the Terminal.Gui system for drawing tries to optimize/reduce redraws via ConsoleDriver.Clip which is a rectangle. This works ok but a system based on an irregular Region could be far more efficient.

Ages ago I experimented with re-implementing Clip using a list of rectangles in this PR:

• Adds "Clip Region" clipping to ConsoleDriver #2606

Note I somehow overwrote the goodness in that PR, but much of the work is in older commits, but the essence was:

		/// <summary>
		/// Gets or sets the clip rectangle that <see cref="AddRune(Rune)"/> and <see cref="AddStr(ustring)"/> are 
		/// subject to. Setting this property is equivalent to calling <see cref="ClearClipRegion()"/>
		/// and <see cref="AddToClipRegion(Rect)"/>.
		/// </summary>
		/// <value>The rectangle describing the bounds of <see cref="ClipRegion"/>.</value>
		public Rect Clip {
			get {
				if (ClipRegion.Count == 0) {
					return new Rect (0, 0, Cols, Rows);
				}

				int minX = ClipRegion.Min (rect => rect.X);
				int minY = ClipRegion.Min (rect => rect.Y);
				int maxX = ClipRegion.Max (rect => rect.X + rect.Width);
				int maxY = ClipRegion.Max (rect => rect.Y + rect.Height);

				return new Rect (minX, minY, maxX - minX, maxY - minY);
			}
			set {
				ClearClipRegion ();
				AddToClipRegion (value);
			}
		}

		List<Rect> _clipRegion = new List<Rect> ();

I abandoned that PR because, at the time, ConsoleDriver and all the implementations were too fragile with way too much duplicated code. I also realized my "list of rectangles" idea was too naive and I was re-inventing the wheel: System.Drawing.Region already exists.

At some point, tackling this PR will be worthy.

If we can't get to it before releasing v2, at the least we should ensure the current View.SetClip API can be forward-compatible so fixing this Issue is not a breaking change to v2.

Other Discussions

I don't think an array of Rectangles is the right approach. I think we want to build the next-gen clipping support on a Region class that is either directly this:

https://learn.microsoft.com/en-us/dotnet/api/system.drawing.region?view=dotnet-plat-ext-8.0

Or, is a clone of it.

So, unless you built your experiment on Region, no.

By chance I noticed the Region class but I didn't use it to avoid having to add another library. I created a RectangleExtensions class to manipulate its Rectangle methods with the array. But since it didn't solve the problem with flickering and I didn't use the Region class, I'm going to give up on continuing with my PR.

Originally posted by @BDisp in #3408 (comment)

[dodexahedron]

Rectangle already has that functionality built-in, no?

[BDisp]

Rectangle already has that functionality built-in, no?

I don't think so.

[BDisp]

The Rectangle class can only return the union, intersection of two rectangles, but not greater than two. This requires more work and manipulation.
But in reality Region is composed of rectangles in which RegionData encapsulates the data contained in that region. It's actually a much more elaborate model in that it customizes the entire process into classes instead just of creating a static RectangleExtensions class.

[BDisp]

But it is not possible to use the System.Drawing.Common package because it involves installing Microsoft.Win32.SystemEvents. Will it be compatible with other platforms? I don't think so.
A lot of CA1416: Validate platform compatibility messages appears.

[BDisp]

In any case, the Region class works differently in relation to the static RectangleExtensions class that I created. Region initializes with an area defined by the constructor and in the class I created I can use several arbitrary areas in any area of the screen. Therefore, as long as a cell is within the limits of a certain area, it will be drawn.

In this case, instead of creating a Rectangle array I have to create a Region array, which will have the same effect, with the advantage of containing the RegionData.
@tig I could start working on this but just in case you haven't started any PRs in this regard yet.

[tig]

In any case, the Region class works differently in relation to the static RectangleExtensions class that I created. Region initializes with an area defined by the constructor and in the class I created I can use several arbitrary areas in any area of the screen. Therefore, as long as a cell is within the limits of a certain area, it will be drawn.

In this case, instead of creating a Rectangle array I have to create a Region array, which will have the same effect, with the advantage of containing the RegionData. @tig I could start working on this but just in case you haven't started any PRs in this regard yet.

Go for it!

[dodexahedron]

Cache locality is important to maintain for something like this.

Be sure to allocate the arrays from Memory<T> and use the pool to avoid excessive heap activity and fragmentation.

[BDisp]

Cache locality is important to maintain for something like this.

Be sure to allocate the arrays from Memory<T> and use the pool to avoid excessive heap activity and fragmentation.

I'm using HashSet<T> to avoid duplicates Rectangle/RectangleF. Does Memory<T> avoids duplicates entries?

[dodexahedron]

If using HashSet, then just using the ArrayPool is fine.

Be sure to over-allocate up front to avoid re-allocation. Rectangles are cheap (16 bytes).

Example, whenever the HashSet is initially created:

HashSet<Rectangle> rectangleHashSet = [..ArrayPool<Rectangle>.Shared.Rent (256)];

This will occupy one page in memory (4K). Cheap, easy, unlikely to re-allocate, and very cache-friendly.

[dodexahedron]

But also, note that duplicates are really cheap and likely to cost less than advantages you can gain by being able to operate over Spans and slices of Memory and such, depending on what a duplicate means.

[dodexahedron]

Another thought:

Any time you have to enumerate the entire set, copy it to a span first and enumerate that. It makes a HUGE difference.

[BDisp]

I want to prevent entering repeated values to avoid unnecessary repetitive recalculations.
Can you explain to me what you said about ArrayPool<T>? Does that mean I have to use it or does HashSet<T> use it internally?

[dodexahedron]

ArrayPool exists for more efficient allocation of arrays and reduced garbage collector activity.

All you need to do, in this case, is exactly as shown, when constructing the HashSet. After that, you don't have further control over what the HashSet will do, internally (and that's another reason you want to over-allocate as shown).

HashSet deals with arrays, under the hood, like most built-in collections. And, like most built-in collections, you can tell it the array to back itself with, initially, in the constructor. It still only contains as many elements as the HashSet itself is aware of - you've just pre-allocated the storage in a contiguous block and avoided internal re-allocation unless the collection grows beyond the initial allocation.

So nope - no extra work required beyond that. There are additional things you can do, but this is a perfectly good starting point.