RevisionGraph: improve internal structures #11268

gerhardol · 2023-10-12T21:24:03Z

Proposed changes

General changes to improve cpu execution and to
limit allocations. Some changes are very minor like
using for instead of foreach, other changes the data structures.

Separate storage of nodes that has no GitRevision.
This allows to remove a separate node storage and
to simplify the code.

Use ImmutableArray instead of array and list for the ordered caches
to improve allocations.

Force update data grid when revision graph nodes have been modified

The order of nodes in the revision graph may change if the commits are
listed out of order or if artificial commits are inserted.
The revision graph was (normally) invalidated but the data grid was only
refreshed if scrolling.

Use separate counter for revisions to limit
the lock time for _revisionByObjectId.Count

Rename variables and add comments

Remove unused IsRevisionRelative().

--

This is partly a test of how you can use CoPilot to optimize code.
It is maybe 1/5 times you get something that works and 1/10 that something works.
Quite often CoPilot insists on something that is not an improvement.
But that is not so bad, there are improvements in the end.

This code is running when revisions are loaded, so performance is important.
Also minor changes could make a difference.

I will add some comments about decisions in an own review of the code.

Tests mostly on Linux repo, limiting loading to 100K commits.

This reduces the time RevisionDataGridView.Add() runs from about 1000-1400 ms to 400-600ms.
However, the normal load time (as reported by RevisionReader) is mostly unchanged at 3000 - 3400 ms, so it seem like git-log delivers commits slower than they are handled here.
The total time for git-log to write to a file is about 1900 ms so there is something more to it, maybe something with reading the stream (there are changes in .NET7 I will try later).
So there may be a potential for some minor improvements later.
The decreased allocation seem to give more consistent running times (less gc).

The incorrect insertion of artificial commits (that #11266 made more visible) is fixed at least.
I still get some visual issues when scrolling a lot, but better than before.
Similar with no grid when rebasing, I have not seen that lately.
More changes may be needed lock-cache-refresh handling, this is a step forward.

Test methodology

There are tests for graph loading.

Merge strategy

I agree that the maintainer squash merge this PR (if the commit message is clear).

✒️ I contribute this code under The Developer Certificate of Origin.

gerhardol · 2023-10-12T21:31:24Z

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs

@@ -16,9 +17,18 @@ public class RevisionGraph : IRevisionGraphRowProvider
        internal const int MaxLanes = 40;
        private const int _straightenLanesLookAhead = 20;

-        // Some unordered collections with raw data
-        private ConcurrentDictionary<ObjectId, RevisionGraphRevision> _nodeByObjectId = new();


Removal of this data structure is the majority of the decreased runtime.
Updating an ImmutableList will reallocate, so a lot of OH are removed.

gerhardol · 2023-10-12T21:35:51Z

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs

-                    Array.Sort(localOrderedNodesCache, (x, y) => x.Score.CompareTo(y.Score));
-                    _orderedNodesCache = localOrderedNodesCache;
-                    if (localOrderedNodesCache.Length > 0)
+                    RevisionGraphRevision[] n = _nodeByObjectId.Values.ToArray();


Using a builder was slightly slow in this scenario (85 vs 65 ms), not what I expected.
The following was about 35 ms:

_orderedNodesCache = _nodeByObjectId.Values .OrderBy(revision => revision.Score) .ToImmutableArray();

The array has the least allocation here, so it was chosen.

Reverted to this code anyway, got an exception in tests while sorting.

gerhardol · 2023-10-12T21:36:34Z

GitUI/UserControls/RevisionGrid/Graph/LaneInfo.cs

@@ -2,22 +2,25 @@
 {
    public class LaneInfo
    {
-        public LaneInfo(RevisionGraphSegment startSegment, LaneInfo? derivedFrom)


No functionality change, just separating the two cases.

gerhardol · 2023-10-12T21:52:33Z

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs

+        /// and the first page is to be displayed, very quick.
+        /// The second time is when all revisions are loaded, that may require 50 ms to build.
+        /// </remarks>
+        private ImmutableArray<RevisionGraphRevision> _orderedNodesCache = ImmutableArray<RevisionGraphRevision>.Empty;


An ImmutableArray is accessed about as fast as a normal array, and _orderedNodesCache is never changed when in use.
It is normally created two times so it seems the correct choice. (Immutable would allow parallel processing but that is not really an improvement here).

For _orderedRowCache other data structures could be a better choice. It was updated quicker in the creation scenario (like 150 ms if I recall correctly) but the scrolling could give more allocations.
I cannot see any slowdowns or obvious fragmentation.

Used ImmutableArray for row cache too, handle locking in a much cheaper way and only allocates when scrolling.

gerhardol · 2023-10-12T21:56:04Z

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs

+        /// <summary>
+        /// The number of revisions added, potentially nodes in the graph.
+        /// </summary>
+        public int Count => _nodeByObjectId.Count;


This is a potential performance issue, _nodeByObjectId.Count is locking a ConcurrentDictionary
But accesses from other threads when loading (adding) the revisions is low and there are few so critical concurrent accesses after. A separate counter does not seem to be worth it.

gerhardol · 2023-10-12T21:57:38Z

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs

-        {
-            return _nodeByObjectId.TryGetValue(objectId, out revision);
-        }
+            => _nodeByObjectId.TryGetValue(objectId, out revision);


CoPilot insists that Contains() is faster here but it mixes up Contains+Get vs TryGetValue

gerhardol · 2023-10-12T22:01:38Z

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs

            {
                // This revision was added earlier, but is now found in the log.
                // Increase the score to the current maxScore to keep the order intact.
                revisionGraphRevision.EnsureScoreIsAbove(nextScore);
+                revisionGraphRevision.GitRevision = revision;


Will remove this assigment, done below (was accidentally kept when splitting the modified insert artificial for #11267

gerhardol · 2023-10-12T22:06:09Z

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs


-            if (localOrderedRowCache is null || IsRowCacheDirty(localOrderedRowCache, orderedNodesCache))
+            int capacity = Math.Max(currentRowIndex, lastOrderedNodeIndex) + 1;
+            ImmutableArray<RevisionGraphRow>.Builder localOrderedRowCache = ImmutableArray.CreateBuilder<RevisionGraphRow>(capacity);


Will move this allocation to after line 349/374

gerhardol · 2023-10-12T22:07:49Z

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs

-                    Array.Sort(localOrderedNodesCache, (x, y) => x.Score.CompareTo(y.Score));
-                    _orderedNodesCache = localOrderedNodesCache;
-                    if (localOrderedNodesCache.Length > 0)
+                    RevisionGraphRevision[] n = _nodeByObjectId.Values.ToArray();


_nodeByObjectId.Values will make a consistent snapshot

gerhardol · 2023-10-15T22:54:13Z

Plan to tune this some more, but most will likely not change. (The row cache is not always invalidated.)

mstv · 2023-10-19T19:09:41Z

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs

+                int i = 0;
+                foreach (RevisionGraphRevision node in _revisionGraph._nodeByObjectId.Values)
                {
-                    foreach (RevisionGraphRevision parent in node.Parents)


int i = 0 and i++ are obsolete as well.

Merge issue after the first var PR.
Fixed in the new rebase after the second var PR, removed the (new) line 656. i is used in printouts only.

gerhardol · 2023-10-19T22:53:22Z

will investigate the data structure for _orderedRowCache again before removing draft (no other changes planned)

gerhardol · 2023-10-21T19:40:35Z

I believe this is working now, will test some more myself before changing from draft.
At that point, I will merge #11267 and squash this PR before removing draft.

After the latest changes #9223 got worse in a certain scenario on the Linux repo. I believe this issue is now fix. Also, it may handle some of the intermittently failing tests as well. There should have been display issues when git-log sorted commits in topo order too.
There are two parts of it.

The first was that the ordered list were not consistently updated and could be modified in parallel.

The second is more complex. Commits are added with a score to define the order. Parents are normally after the child and are just given a new score. For topo order or when artificial commits are inserted, the node cache were invalidated for the case where artificial were inserted which will cause the row cache to be updated, but the grid was still using the previous cached data. Topo order and tests did not invalidate the caches at all (so it worked if caches were not yet updated).
To solve this, the results for modified scores were propagated to the data grid so a refresh flag could be set. The workaround for this issue was to scroll forward and then back to force the update.

mstv

Review of the first commit including its fixes

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs

gerhardol · 2023-10-23T21:59:11Z

Changed the row cache to ImmutableArray. The row cache is only updated from one thread but need to be consistent when accessed in other threads. I got a few errors with the previous setup.
This will allocate every time the cache is updated (in chunks of 1500), so there will be some garbage collection if scrolled to the end.
Still better than to copy the List<> when inserting every new revision.
I tried using a lock() instead, but that was much slower.
(Current implementation uses Immutable for the nodes list, so it allocates a new array for every revision added, not just a new allocation every 1500 if you scroll so the new implementation is some magnitudes better in the normal use case).

I still get some visual issues when scrolling a lot, but better than before.
Similar with no grid when rebasing, I have not seen that lately.
More changes may be needed lock-cache-refresh handling, this is a step forward.

Plan to squash and remove draft for this tomorrow.

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs

GitUI/UserControls/RevisionGrid/RevisionDataGridView.cs

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs

RussKie

🤯🤯🤯

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs

mstv

Almost done

mstv · 2023-10-25T20:32:47Z

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs

+        /// <summary>
+        /// The number of revisions in <see cref="_revisionByObjectId"/>, potentially nodes in the graph.
+        /// </summary>
+        public int Count => _revisionCount;


❔

Suggested change

/// <summary>

/// The number of revisions in <see cref="_revisionByObjectId"/>, potentially nodes in the graph.

/// </summary>

public int Count => _revisionCount;

/// <summary>

/// The number of revisions in <see cref="_revisionByObjectId"/>, potential nodes in the graph.

/// </summary>

public int Count { get; private set; }

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs

mstv

👍 have not run

gerhardol · 2023-10-26T11:50:26Z

🤯🤯🤯

👍 have not run

I would like to merge soon this to get some usage and see if the refresh issues are solved or at least improved.
I can some issues still when scrolling in a specific way in specific situations in linux repo so we may need to go back to this.

The slowdown in updating the grid is in StraightenLanes(), that is separate from this issue but it is nice to have this as a base when trying to improve that. (@mstv knows this better than me but he is busy but still put a good effort in reviewing this series of PRs, so I guess we will be in touch).

General changes to improve cpu execution and to limit allocations. Some changes are very minor like using for instead of foreach, other changes the data structures. Separate storage of nodes that has no GitRevision. This allows to remove a separate node storage and to simplify the code. Use ImmutableArray instead of array and list for the ordered caches to improve lock handling. Force update data grid when revision graph nodes have been modified The order of nodes in the revision graph may change if the commits are listed out of order or if artificial commits are inserted. The revision graph was (normally) invalidated but the data grid was only refreshed if scrolling. Use separate counter for revisions to limit the lock time for _revisionByObjectId.Count Rename variables and add comments Remove unused IsRevisionRelative(). and a merge error in tests

mstv · 2023-10-26T20:22:03Z

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs

-            if (minScore <= _orderedUntilScore)
+            if (!_orderedNodesCacheInvalid)
            {
-                _reorder = true;
+                ImmutableArray<RevisionGraphRevision> localOrderedNodesCache = _orderedNodesCache;
+                if (localOrderedNodesCache.Length > 0 && minScore <= localOrderedNodesCache[^1].Score)
+                {
+                    _orderedNodesCacheInvalid = true;
+                }
            }


I have analyzed this moved code multiple times. I do still not see why it causes an empty revision grid for many seconds when switching to the Linux repo.

mstv · 2023-10-26T20:29:34Z

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs

-                    _orderedUntilScore = int.MinValue;
-                    _reorder = false;


Found it right after writing the previous comment:
The necessary replacement for _orderedUntilScore = int.MinValue; is _orderedNodesCache = ImmutableArray<RevisionGraphRevision>.Empty;

Good catch, I did not see that
Squashed existing, added this with updated commit message

RussKie · 2023-10-26T20:41:39Z

If you think it's ready and *is working* - merge it

General changes to improve cpu execution and to limit allocations. Some changes are very minor like using for instead of foreach, other changes the data structures. Separate storage of nodes that has no GitRevision. This allows to remove a separate node storage and to simplify the code. Use ImmutableArray instead of array and list for the ordered caches to improve locking without excessive allocations. Force update data grid when revision graph nodes have been modified The order of nodes in the revision graph may change if the commits are listed out of order or if artificial commits are inserted. The revision graph was (normally) invalidated but the data grid was only refreshed if scrolling. Use separate counter for revisions to limit the lock time for _revisionByObjectId.Count Rename variables and add comments Remove unused IsRevisionRelative().

mstv

works for me

gerhardol · 2023-10-27T20:24:24Z

This does not completely solve #9223, but it is an improvement.

There are two separate issues from here:

Find what is the problem with the refreshing. That is RevisionDataGridView interacting with RevisionGraph. Row nodes are OK but the column or RevisionGraphRow data is incorrect
Speedup the lane handling that is slower after 4.1

ghost assigned gerhardol Oct 12, 2023

gerhardol commented Oct 12, 2023

View reviewed changes

gerhardol force-pushed the feature/improve-revgrid-loading branch from c0f3349 to 31360a4 Compare October 15, 2023 22:48

gerhardol force-pushed the feature/improve-revgrid-loading branch from 31360a4 to 2913758 Compare October 17, 2023 19:18

gerhardol mentioned this pull request Oct 18, 2023

RevisionGrid: Separate add/insert of artificial commits #11267

Merged

mstv reviewed Oct 19, 2023

View reviewed changes

gerhardol force-pushed the feature/improve-revgrid-loading branch from d9e8c25 to cd53095 Compare October 19, 2023 22:49

gerhardol force-pushed the feature/improve-revgrid-loading branch 2 times, most recently from 65b77d7 to e28354c Compare October 21, 2023 19:40

gerhardol mentioned this pull request Oct 21, 2023

RevisionGrid not refreshed correctly after interactive rebase operations #9223

Closed

gerhardol force-pushed the feature/improve-revgrid-loading branch from e28354c to a577c1b Compare October 21, 2023 21:33

gerhardol mentioned this pull request Oct 21, 2023

Loading revision graph is slow in 4.2 #11292

Closed

mstv reviewed Oct 23, 2023

View reviewed changes

gerhardol force-pushed the feature/improve-revgrid-loading branch from 130837b to 3ccd613 Compare October 24, 2023 21:13

mstv reviewed Oct 24, 2023

View reviewed changes

gerhardol marked this pull request as ready for review October 24, 2023 22:36

RussKie reviewed Oct 25, 2023

View reviewed changes

mstv reviewed Oct 25, 2023

View reviewed changes

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs Show resolved Hide resolved

GitUI/UserControls/RevisionGrid/Graph/RevisionGraph.cs Show resolved Hide resolved

mstv reviewed Oct 25, 2023

View reviewed changes

mstv approved these changes Oct 25, 2023

View reviewed changes

mstv reviewed Oct 26, 2023

View reviewed changes

gerhardol force-pushed the feature/improve-revgrid-loading branch from 9b6179f to 21c7754 Compare October 26, 2023 21:24

gerhardol merged commit 1ffedca into gitextensions:master Oct 27, 2023

ghost added this to the vNext milestone Oct 27, 2023

gerhardol deleted the feature/improve-revgrid-loading branch October 27, 2023 19:56

mstv approved these changes Oct 27, 2023

View reviewed changes

Uh oh!

RevisionGraph: improve internal structures #11268

RevisionGraph: improve internal structures #11268

Uh oh!

Conversation

gerhardol commented Oct 12, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Proposed changes

Test methodology

Merge strategy

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!

gerhardol commented Oct 15, 2023

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

gerhardol commented Oct 19, 2023

Uh oh!

gerhardol commented Oct 21, 2023

Uh oh!

mstv left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

gerhardol commented Oct 23, 2023 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

Uh oh!

RussKie left a comment

Choose a reason for hiding this comment

Uh oh!

Uh oh!

Uh oh!

mstv 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

gerhardol commented Oct 12, 2023 •

edited

Loading

gerhardol commented Oct 23, 2023 •

edited

Loading

RussKie commented Oct 26, 2023 via email •

edited by ghost

Loading