Introduce RenderClusterIterator by skyline75489 · Pull Request #3458 · microsoft/terminal

skyline75489 · 2019-11-06T08:37:54Z

Summary of the Pull Request

This is the successor of #3438 . The idea is based on @miniksa 's comment originally posted here #3438 (comment)

We could perhaps wrap a TextBufferCellIterator into a RenderClusterIterator, tell the RenderClusterIterator that it needs to return operator bool() as false when the underlying TextBufferCellIterator::TextAttr changes on increment, and provides accessors only for the character string and column string into the underlying cell iterator (which is a view directly into the text buffer).

References

#3075 #3438

PR Checklist

Closes #xxx
CLA signed. If not, go over here and sign the CLA
Tests added/passed
Requires documentation to be updated
I've discussed this with core contributors already. If not checked, I'm ready to accept this work might be rejected in favor of a different grand plan. Issue number where discussion took place: #xxx

Detailed Description of the Pull Request / Additional comments

This is still WIP, though. Would love to hear everybody's feedback.

Validation Steps Performed

Just pretty much everything should be validated. Vim, cat, top, cmatrix, and so on.

skyline75489 · 2019-11-06T08:39:25Z

src/renderer/vt/paint.cpp

-    unclusteredString.reserve(clusters.size());
    short totalWidth = 0;
-    for (const auto& cluster : clusters)
+    unclusteredString.reserve(40);


I'm not a fan of magic number. But without reserving space, this will run much slower. Should we pass size alongside clusterIter? I'm not sure about this.

Uh... perhaps preallocate the number of cells width from coord to the right edge of the known dirty rect (see impl of GetDirtyRectInChars)

All of the engines should know a little bit about what area is actually invalid and they're always given a drawing coordinate.

Failing this, instead of allocating and reserving on each call to _Paint*BufferLine, they might be able to allocate the buffer when the StartPaint() comes in as a dirty-rect-wide string/vector and just re-use that one for every row and free it when the EndPaint() comes around. That'd make way fewer allocations per frame than one per call.

skyline75489 · 2019-11-06T08:41:56Z

src/renderer/dx/CustomTextLayout.cpp

    THROW_IF_FAILED(format->GetLocaleName(_localeName.data(), gsl::narrow<UINT32>(_localeName.size())));

-    for (const auto& cluster : clusters)
+    RenderClusterIterator it = clusterIter;


Because we are using RenderClusterIterator const, the copy is needed. It could be RenderClusterIterator& and then it can be modifed by the caller. But that's just kind of implicit to me. I prefer the copying.

Nah, I like what you did. It's constant for the specification of the custom layout, but then the internals of the layout makes the copy to walk through it.

skyline75489 · 2019-11-06T08:46:56Z

src/renderer/base/renderer.cpp

        // This outer loop will continue until we reach the end of the text we are trying to draw.
        while (it)
        {
+            TextBufferCellIterator runStartIt(it);


When is inner loop is over clusterIter will be exhausted. So I copy it and keep the start of the run here.

skyline75489 · 2019-11-06T08:48:21Z

src/renderer/base/renderer.cpp

                // Advance the cluster and column counts.
-                const auto columnCount = clusters.back().GetColumns();
-                it += columnCount > 0 ? columnCount : 1; // prevent infinite loop for no visible columns
+                const auto columnCount = (*clusterIter).GetColumns();


Calculating the cols is cumbersome. , I don't know how to do this in a more elegant way.

Oh. This might actually justify making the PaintBufferLine's first arg be a & instead.

Save a copy of it on the way in, let the engine increment it, then add a method that lets you difference the two of them.

Diff the resultant one you get back versus the one you initially created and it should tell you how many columns it walked. Then you don't have to cycle through the loop multiple times.

That's what I did for the cell/text iterators with .GetCellDistance and whatnot.

I'm not sure. I don't think it's enough to justify this. Making it & sounds very error-prone and implicit.

Make two of them? Take a const input and then have a second & as the output one?

It's not uncommon to use an Inout parameter, but if you think its safer to have an explicit In and Out (given we can't use the return code as it's always HRESULT for these thing), it seems OK.

skyline75489 · 2019-11-06T08:49:33Z

src/renderer/gdi/paint.cpp

    try
    {
-        const auto cchLine = clusters.size();
+        size_t cchLine = 120;


Again, without size I can't make use of length to init arrays.

Again, decent estimate is coord to right edge of dirty rect.

An estimate is not enough, though. I need the exact size here.

Iterating it two times, could it be that bad? I'm stucked...

Not strictly. You could replace things like auto pwsPoly = std::make_unique<wchar_t>(cchLine) instead with a std::wstring and .reserve() it up to the "estimate" of _rcInvalid.Right - coord.X. Same goes for the rgdxPoly with a vector of ints or something. (or use vectors for both).

The first phase with the for loop has to iterate the whole thing anyway to condense the clusters back into a string. Either you'll get lucky in the majority case and the estimate won't resize the vectors, or you'll get unlucky in the uncommon case and you'll resize up once or twice. (And if resizing up happens a lot, we can use an estimate function like the CustomTextLayout::_EstimateGlyphCount does to reduce the potential resizes.)

By the end of the for loop (lines 316-325), you should be able to know the exact widths required for all the functions further down PaintBufferLine and have only iterated once. E.g. you should have calculated cchLine exactly by iterating once and also filled a vector pwsPoly and vector rgdxPoly with the condensed version. That should be enough information to finish the draw operation.

However, now that I look at this further. The loop in this specific GDI renderer only allows a maximum of one wchar_t per unit because of GDI limitation. (comment on L322 where cluster.GetTextAsSingle() is called. So the "estimate" used for .reserve() above should actually be the exact column count as a Cluster is a console grid unit described by one-or-more-wchar_t and the vectors wouldn't auto-resize.

The last problem is that the vectors would free when going out of scope. There isn't really a detach to the vectors. We could just hold a reference to them that is freed inside _FlushBufferLines after PolyTextOut is called.

Member variables on the class like:
std::vector<std::vector<wchar_t>> _polyStrings and std::vector<std::vector<int>> _polyWidths, push a new vector into those on each PaintBufferLine, take the .data() of the line and stuff it into the pPolyTextLine fields, and then clear them out on _FlushBufferLines.

That might make _FlushBuferLines a little cleaner than raw delete[]s of bare pointers as well.

skyline75489 · 2019-11-06T13:42:37Z

I don't know what I did wrong but I'm getting the same error as CI build:

src\buffer\out\TextColor.h(37,10): Error C1083: Cannot open include file: 'WexTestClass.h': No such file or directory (compiling source file ..\paint.cpp)

miniksa

This is exactly the direction I was hoping you would go with this. Pretty much perfectly what I was envisioning with the comment I left yesterday. Thank you!

miniksa · 2019-11-06T18:00:10Z

src/renderer/vt/paint.cpp

-    unclusteredString.reserve(clusters.size());
    short totalWidth = 0;
-    for (const auto& cluster : clusters)
+    unclusteredString.reserve(40);


Uh... perhaps preallocate the number of cells width from coord to the right edge of the known dirty rect (see impl of GetDirtyRectInChars)

All of the engines should know a little bit about what area is actually invalid and they're always given a drawing coordinate.

Failing this, instead of allocating and reserving on each call to _Paint*BufferLine, they might be able to allocate the buffer when the StartPaint() comes in as a dirty-rect-wide string/vector and just re-use that one for every row and free it when the EndPaint() comes around. That'd make way fewer allocations per frame than one per call.

miniksa · 2019-11-06T18:03:11Z

src/renderer/inc/Cluster.hpp

        Cluster(const std::wstring_view text, const size_t columns);

-        const wchar_t GetTextAsSingle() const noexcept;
+        wchar_t GetTextAsSingle() const noexcept;


Why did we lose consts here?

miniksa · 2019-11-06T18:04:32Z

src/renderer/dx/CustomTextLayout.cpp

    THROW_IF_FAILED(format->GetLocaleName(_localeName.data(), gsl::narrow<UINT32>(_localeName.size())));

-    for (const auto& cluster : clusters)
+    RenderClusterIterator it = clusterIter;


Nah, I like what you did. It's constant for the specification of the custom layout, but then the internals of the layout makes the copy to walk through it.

miniksa · 2019-11-06T18:04:59Z

src/host/ut_host/VtRendererTests.cpp

        }

-        VERIFY_SUCCEEDED(engine->PaintBufferLine({ clusters.data(), clusters.size() }, { 1, 1 }, false));
+        // VERIFY_SUCCEEDED(engine->PaintBufferLine({ clusters.data(), clusters.size() }, { 1, 1 }, false));


TBD I presume

miniksa · 2019-11-06T18:10:56Z

src/renderer/dx/DxRenderer.cpp

-                                _dwriteFontFace.Get(),
-                                { &cluster, 1 },
-                                _glyphCell.cx);
+        //// Create the text layout


Also TBD, I presume

miniksa · 2019-11-06T18:11:36Z

src/renderer/gdi/paint.cpp

    try
    {
-        const auto cchLine = clusters.size();
+        size_t cchLine = 120;


Again, decent estimate is coord to right edge of dirty rect.

miniksa · 2019-11-06T18:14:50Z

src/renderer/base/renderer.cpp

                // Advance the cluster and column counts.
-                const auto columnCount = clusters.back().GetColumns();
-                it += columnCount > 0 ? columnCount : 1; // prevent infinite loop for no visible columns
+                const auto columnCount = (*clusterIter).GetColumns();


Oh. This might actually justify making the PaintBufferLine's first arg be a & instead.

Save a copy of it on the way in, let the engine increment it, then add a method that lets you difference the two of them.

Diff the resultant one you get back versus the one you initially created and it should tell you how many columns it walked. Then you don't have to cycle through the loop multiple times.

That's what I did for the cell/text iterators with .GetCellDistance and whatnot.

miniksa · 2019-11-06T18:19:17Z

Just overall, did you check a trace on this (can I see)? I presume it's better than the original but maybe not as perfect as the more memory-intense previous iteration.

skyline75489 · 2019-11-07T12:51:00Z

src/host/ut_host/VtRendererTests.cpp


-        VERIFY_SUCCEEDED(engine->PaintBufferLine({ clusters1.data(), clusters1.size() }, { 0, 0 }, false));
-        VERIFY_SUCCEEDED(engine->PaintBufferLine({ clusters2.data(), clusters2.size() }, { 0, 1 }, false));
+        const COORD screenBufferSize{ 119, 9029 };


This is just way too much ... kinda hurtful.

What do you mean?

It's suppose to be a unit test that focuses on this certain VT thing. Now I dragged all the other units like TextBuffer. I'm not a fan of this..

skyline75489 · 2019-11-08T08:43:01Z

src/renderer/gdi/gdirenderer.hpp

-        static const size_t s_cPolyTextCache = 80;
-        POLYTEXTW _pPolyText[s_cPolyTextCache];
+        static constexpr size_t s_cPolyTextCache = 80;
+        std::array<POLYTEXTW, s_cPolyTextCache> _polyText;


I figured that all those containers have exact same fixed size. Using std::array is more reasonable

skyline75489 · 2019-11-08T08:44:23Z

src/renderer/gdi/paint.cpp

-        // Exit early if there are no lines to draw.
-        RETURN_HR_IF(S_OK, 0 == cchLine);
-
+        const size_t preallocateSize = (_rcInvalid.right - _rcInvalid.left) / 8;


I found that 8 is the magic number needed here to get the correct size? Any GDI+ reference that explains this?

skyline75489 · 2019-11-08T08:46:44Z

src/renderer/gdi/paint.cpp

-            }
-        }
-
+        _polyStrings = {};


This certainly is safer and better than raw delete[].

skyline75489 · 2019-11-08T09:59:04Z

src/renderer/base/RenderClusterIterator.cpp

+    return !(*this == it);
+}
+
+RenderClusterIterator& RenderClusterIterator::operator+=(const ptrdiff_t& movement)


Currently RenderClusterIterator is not aware of the dbcs columns. Caller must use clusterIter += cols > 0 ? cols : 1 to skip dbcs trailing char. I've tried to let RenderClusterIterator handle this itself, but failed to do so because the code gets too complicated and implicit.

skyline75489 · 2019-11-08T10:17:09Z

Plain catting is a lot faster with this PR. The trace is I think as good as #3438, if not better.

I found something interesting. Plain cmatrix performance is actually worse with this PR. I think that render thread speeding up saves time so that the output thread can write more data, which backfires itself, causing render thread to be even more busy. That is probably where differential drawing will come in handy.

Update: With #3480 merged, cmatrix is smooth again.

skyline75489 · 2019-11-08T12:30:02Z

src/renderer/vt/ut_lib/vt.unittest.vcxproj

  <!-- Careful reordering these. Some default props (contained in these files) are order sensitive. -->
  <Import Project="$(SolutionDir)src\common.build.post.props" />
-  <!-- <Import Project="$(SolutionDir)src\common.build.tests.props" /> -->
+  <Import Project="$(SolutionDir)src\common.build.tests.props" />


I don't know why but I need this to make CI and my local VS happy. Wonder why master is still green without it

skyline75489 · 2019-11-10T03:57:03Z

Mostly this is ready now. Tests are finally green.

skyline75489 · 2019-11-13T05:37:39Z

This needs to hold, until #3546 is solved. I'm seeing even worse result with this PR.

skyline75489 · 2019-11-13T08:16:49Z

OK this PR is not the cause of the regression. It's probabaly #3474. But still let's hold this until the regression is solved.

skyline75489 · 2020-05-06T05:09:13Z

Now that #778 is closed, this does not seem necessary. Close this for now,

miniksa · 2020-05-06T17:04:45Z

Thanks for this anyway, @skyline75489. I do want to get this done at some point in the future and will likely use this as a template whenever that time comes. But you're right, it's not as critical right now anymore.

skyline75489 mentioned this pull request Nov 6, 2019

[WIP] Perf: construct & reuse clusters in output thread #3438

Closed

5 tasks

skyline75489 commented Nov 6, 2019

View reviewed changes

miniksa reviewed Nov 6, 2019

View reviewed changes

skyline75489 force-pushed the fix/renderClusterIter branch from d0d432e to e9a785f Compare November 7, 2019 11:08

skyline75489 commented Nov 7, 2019

View reviewed changes

skyline75489 commented Nov 8, 2019

View reviewed changes

src/renderer/gdi/paint.cpp

}

}

_polyStrings = {};

Copy link

Collaborator Author

skyline75489 Nov 8, 2019

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This certainly is safer and better than raw delete[].

skyline75489 commented Nov 8, 2019

View reviewed changes

skyline75489 force-pushed the fix/renderClusterIter branch from d9e896e to d1f4634 Compare November 8, 2019 11:08

skyline75489 commented Nov 8, 2019

View reviewed changes

skyline75489 force-pushed the fix/renderClusterIter branch from 3dbb0bc to dcb9bd6 Compare November 10, 2019 02:30

skyline75489 force-pushed the fix/renderClusterIter branch from 93df594 to 544c21c Compare November 10, 2019 04:07

skyline75489 mentioned this pull request Nov 15, 2019

Try to fix unicode layout issue #3578

Closed

5 tasks

zadjii-msft requested review from DHowett-MSFT, carlos-zamora, leonMSFT and miniksa December 16, 2019 21:10

zadjii-msft added Area-Performance Performance-related issue Area-Rendering Text rendering, emoji, complex glyph & font-fallback issues labels Dec 16, 2019

zadjii-msft self-requested a review December 16, 2019 21:10

skyline75489 added 13 commits January 7, 2020 13:42

Init RenderClusterIterator

85f1acc

Change for review

29e2089

What is this...

6d2a99b

Tests

f8df455

Try to make GDI work

6c16878

Make GDI+ work

a6dc9ab

Make use of _Inout_ parameter

6cec21f

Take care of GDI+

c0df551

Try to make test work

dd7ac04

Tests are green now

7d0ec5c

Docs

cf115b9

More docs

aca7641

Fix

fe96309

skyline75489 force-pushed the fix/renderClusterIter branch from 544c21c to fe96309 Compare January 7, 2020 05:44

skyline75489 mentioned this pull request Jan 7, 2020

Fix column count issues with certain ligature. #4081

Merged

5 tasks

skyline75489 mentioned this pull request Apr 27, 2020

Improve cluster construction performance #5584

Merged

5 tasks

skyline75489 closed this May 6, 2020

skyline75489 deleted the fix/renderClusterIter branch January 25, 2021 02:58

Conversation

skyline75489 commented Nov 6, 2019

Summary of the Pull Request

References

PR Checklist

Detailed Description of the Pull Request / Additional comments

Validation Steps Performed

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

skyline75489 commented Nov 6, 2019

Uh oh!

miniksa left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

miniksa commented Nov 6, 2019

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

skyline75489 commented Nov 8, 2019 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Choose a reason for hiding this comment

Uh oh!

skyline75489 commented Nov 10, 2019

Uh oh!

skyline75489 commented Nov 13, 2019

Uh oh!

skyline75489 commented Nov 8, 2019 •

edited

Loading