Improve redraw performance by making `Clip` be a `Region` instead of `Rectangle` about terminal.gui HOT 22 OPEN

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!

from terminal.gui.

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.

from terminal.gui.

As for repetitive calculations:

You can perform several hundred operations on the stack in the time just a single operation that involves a heap access takes.

The heap is EXPENSIVE. Avoiding it as much as possible in hot paths is very valuable and is a significant reason most of the changes I've made are faster than the originals.

from terminal.gui.

That 256 number was important, BTW.

• Best to use powers of 2.
• 256 is unlikely to be exceeded.
• 256 * 16 (size of a Rectangle) = 4K, which is one memory page.

from terminal.gui.

Rectangle already has that functionality built-in, no?

from terminal.gui.

Rectangle already has that functionality built-in, no?

I don't think so.

from terminal.gui.

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.

from terminal.gui.

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.

from terminal.gui.

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.

from terminal.gui.

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.

from terminal.gui.

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?

from terminal.gui.

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.

from terminal.gui.

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.

from terminal.gui.

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.

from terminal.gui.

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?

from terminal.gui.

Why not just steal the code from System.Drawing.Region???

from terminal.gui.

Why not just steal the code from System.Drawing.Region???

Because it has many references to specific types of Windows Forms and I preferred to start from scratch adapting it to Terminal.Gui.

from terminal.gui.

Have you looked at some of the other existing drawing/graphics-related libraries out there? There are some that are fantastic and highly optimized. And if only some functionality is needed, specific code can be lifted if the licenses are compatible, to avoid bloat. Or we can just publish single-file and trimmed for the same result.

Even if a gfx library isn't intended for text-mode applications, you can still use the data structures, too. Pretty easy to turn a bitmap in memory into unicode for the screen buffer on the fly.

from terminal.gui.

If implementing from scratch, here are a couple of ideas for what might represent pretty significant but easy-to-code optimizations at very low cost:

One is to keep track of at least some of the negative space, such as just one rectangle of it.

For example, if the region looks like a big L, there would be whatever rectangles make up the L, and one rectangle that is the pre-computed rectangle none of the others touch. Hit testing and drawing could both then pay the cost of one check to that rectangle first, before checking positive space, likely speeding up most operations, especially if the negative space is large.

The other idea is to explicitly cache combined areas into a bitmap or other sort of structure, so that the entire stack of rectangles doesn't have to be computed for each iteration of the loop. You'd add a subscription to any change events on Views to invalidate the cache and only re-compute the cached structure when it's not valid.

These can also be combined.

from terminal.gui.

Another idea:

Create two or more bitmaps/collections of values - One or more of which are metadata for each screen coordinate and one of which is explicit content of that screen coordinate, if any exists. Metadata could be things such as what needs to happen to that pixel (process, skip, composite, etc) or a reference to the top View that would actually be responsible for drawing that character, or anything else that can be used to speed things up.

Such things would also be very vectorizable for SIMD by the compiler without additional work.

from terminal.gui.