Terminal.Gui
Terminal.Gui copied to clipboard
gui-cs
Problems in ListWrapper.GetMaxLengthItem (with fixes and improvements)
https://github.com/gui-cs/Terminal.Gui/blob/4cc63391929114a5f9fdb9efbba55addbcfa99ba/Terminal.Gui/Views/ListView.cs#L842
That loop has some problems.
Most importantly, it has a potential null reference exception.
It also has a redundant branch that can never be reached, and has inconsistent behavior for calculating the actual lengths (using string length for some and the string.GetColumns extension method for others).
The NRE bug is fixed in the code shown below through use of conditionals, and the redundant branch is removed. I suspect that was just a leftover from the elimination of ustring, since that's the only difference from V1 there.
But I also didn't really love the code, since it is just slightly hard to grok for what is a pretty basic operation (and one for which there are built-in highly-optimized functions available).
So, I wrote up a couple of quick replacement options, and put them in a test harness for comparison.
See this NUnit test code[^2], which sets up a fairly comprehensive set of stress test cases, ensures a relatively high degree of test fairness (pre-interns the strings and calls GetColumns on all of them, so no implementation has to encounter that code for the first time), and then compares five implementations of that loop (specifically the loop that finds the max):
- The fixed original (last, in the code)
- A PLINQ implementation
- An alternative for loop implementation
- An alternative foreach loop implementation
- A hybrid implementation that uses the foreach for collections with less than 32 elements or the PLINQ method for collections with 32 or more elements
All prove themselves to return the correct result, in the test code, and none involve any API changes, so they are drop-in compatible replacement options for the loop in question.
I ran these all 20000 times[^1] each, with collection sizes of 1, 10, 25, 100, 250, and 500 (for a total of 120000 runs), for some reasonably smooth statistical data.
Some notes about the test results below:
- Test machine has an Intel Xeon W 10855 (2.8GHz 6-core, similar to a core i5 of similar numbering) with hyperthreading enabled.
- Tests were run on optimized Release builds.
- Note that collection size also affects the length of generated strings, which is part of why these scale non-linearly.[^3]
- The VAST majority of the execution time for all of these is the GetColumns method. Just using string lengths cuts them all by a TON, but I used GetColumns in all. It's not important, for the purposes of comparison, however, since they all use it the same way, in the same places, meaning they are fair comparisons.
- The code to get max length for each new item that is used for the new implementations is identical. It is a switch expression for the type check, returning the appropriate length for the given element.
- The separate branches for non-null string and non-string values can even be combined to one, because string.ToString just returns the string without doing anything anyway, but I left them separate for now.
Some results are a bit surprising.
In particular, the fact that the implementation that uses PLINQ unconditionally is sometimes slower than the hybrid implementation (in some smaller collections), when the hybrid uses that same implementation, stands out to me.
My suspicion is that the Count performed when deciding which method to use affects the optimized code in a non-trivial way for collections below a certain size.[^4]
Something else that stands out to me is the significant variation in average execution times, which suggests the compiler or JITer is applying very different optimizations for the different methods, which is a more important thing to be aware of. I suspect that more aggressive parallelization is likely responsible for that.
Here are the results, with times specified in ticks:
ListWrapper_GetMaxLengthItem_LoopImplementationComparisons(1,20000) Success
Method | Total | Average | ΔMax | ΔMin
------------------------------------------------------------------------------------------
PLINQ | 4,936,421 | 247 | 0.00% | 1,012.84%
new for loop | 3,143,579 | 157 | -36.32% | 608.67%
foreach loop | 443,588 | 22 | -91.01% | 0.00%
hybrid PLINQ/foreach | 2,068,516 | 103 | -58.10% | 366.31%
fixed original | 456,169 | 23 | -90.76% | 2.84%
ListWrapper_GetMaxLengthItem_LoopImplementationComparisons(10,20000) Success
Method | Total | Average | ΔMax | ΔMin
------------------------------------------------------------------------------------------
PLINQ | 6,143,167 | 307 | 0.00% | 803.62%
new for loop | 5,488,425 | 274 | -10.66% | 707.31%
foreach loop | 679,842 | 34 | -88.93% | 0.00%
hybrid PLINQ/foreach | 1,059,615 | 53 | -82.75% | 55.86%
fixed original | 722,560 | 36 | -88.24% | 6.28%
ListWrapper_GetMaxLengthItem_LoopImplementationComparisons(25,20000) Success
Method | Total | Average | ΔMax | ΔMin
------------------------------------------------------------------------------------------
PLINQ | 8,177,217 | 409 | 0.00% | 348.47%
new for loop | 6,033,571 | 302 | -26.21% | 230.90%
foreach loop | 1,823,372 | 91 | -77.70% | 0.00%
hybrid PLINQ/foreach | 2,169,222 | 108 | -73.47% | 15.94%
fixed original | 1,836,455 | 92 | -77.54% | 0.72%
ListWrapper_GetMaxLengthItem_LoopImplementationComparisons(50,20000) Success
Method | Total | Average | ΔMax | ΔMin
------------------------------------------------------------------------------------------
PLINQ | 13,057,276 | 653 | 0.00% | 188.55%
new for loop | 6,510,254 | 326 | -50.14% | 43.87%
foreach loop | 6,229,241 | 311 | -52.29% | 37.66%
hybrid PLINQ/foreach | 4,525,169 | 226 | -65.34% | 0.00%
fixed original | 6,279,524 | 314 | -51.91% | 38.77%
ListWrapper_GetMaxLengthItem_LoopImplementationComparisons(100,20000) Success
Method | Total | Average | ΔMax | ΔMin
------------------------------------------------------------------------------------------
PLINQ | 15,987,763 | 799 | -35.71% | 90.84%
new for loop | 24,705,034 | 1,235 | -0.66% | 194.90%
foreach loop | 24,868,117 | 1,243 | 0.00% | 196.84%
hybrid PLINQ/foreach | 8,377,506 | 419 | -66.31% | 0.00%
fixed original | 24,634,156 | 1,232 | -0.94% | 194.05%
ListWrapper_GetMaxLengthItem_LoopImplementationComparisons(250,20000) Success
Method | Total | Average | ΔMax | ΔMin
------------------------------------------------------------------------------------------
PLINQ | 54,416,993 | 2,721 | -72.43% | 27.58%
new for loop | 171,793,234 | 8,590 | -12.97% | 302.77%
foreach loop | 197,391,774 | 9,870 | 0.00% | 362.78%
hybrid PLINQ/foreach | 42,653,375 | 2,133 | -78.39% | 0.00%
fixed original | 185,753,439 | 9,288 | -5.90% | 335.50%
ListWrapper_GetMaxLengthItem_LoopImplementationComparisons(500,20000) Success
Method | Total | Average | ΔMax | ΔMin
------------------------------------------------------------------------------------------
PLINQ | 114,294,453 | 5,715 | -81.02% | 1.06%
new for loop | 602,047,376 | 30,102 | 0.00% | 432.35%
foreach loop | 601,255,573 | 30,063 | -0.13% | 431.65%
hybrid PLINQ/foreach | 113,092,803 | 5,655 | -81.22% | 0.00%
fixed original | 601,954,440 | 30,098 | -0.02% | 432.27%
As the results show, the foreach and fixed for loop implementations generally have nearly identical performance, with the foreach slightly winning overall, by an insignificant margin.
Thus, it's no real surprise that the overall winner is the hybrid which uses the foreach for small collections and the PLINQ for larger collections. This method, of course, could also use the for loop in place of the foreach, if desired.
Anyway...
The key point is the fix, which is provided in the code below, in the "fixed original" scenario.
The rest is just experimentation providing alternative implementations.
using System.Diagnostics;
using System.Globalization;
namespace UnitTests.Terminal.Gui;
/// <summary>
/// Experiments on the <see cref="ListView" /> type and closely associated types/methods.
/// </summary>
/// <remarks>
/// This test fixture is not meant for direct inclusion in TG or TGD.<br /> If committed to source control by accident, feel free to remove.
/// </remarks>
[TestFixture]
[Description( "Experiments on the Terminal.Gui.ListView type and closely associated types/methods, not meant for direct inclusion in TG or TGD. If committed to source control by accident, feel free to remove." )]
[TestOf( typeof( ListView ) )]
[Category( "Terminal.Gui Experiments" )]
[Parallelizable( ParallelScope.All )]
public class ListViewExperiments
{
private const int ImplementationNameColumnWidth = 22;
private const int NumericColumnWidth = 14;
/// <summary>
/// Compares performance of four corrected implementations of the main loop in the <see cref="ListWrapper.GetMaxLengthItem" /> method.
/// </summary>
/// <param name="numberOfRandomStrings">
/// The number of random strings to include in the collection.<br /> This is also the length of the longest string that will be generated.
/// <br /> One random string will be generated for each length from 0 to this value.
/// </param>
/// <param name="loopIterations">The number of times to repeat each loop case, for smoother results.</param>
[Test]
[TestOf( typeof( ListWrapper ) )]
[SetCulture( "en_US" )]
[SetUICulture( "en_US" )]
[Description( "Compares performance of four bug-corrected implementations of the main loop in the ListWrapper.GetMaxLengthItem method." )]
[CancelAfter( 300000 )] // A 5-minute timeout. Adjust if necessary, and you are aware of what that means for the test runner.
public void ListWrapper_GetMaxLengthItem_LoopImplementationComparisons(
[Values( 1, 10, 25, 50, 100, 250, 500 )]
int numberOfRandomStrings,
[Values( 20000 )] int loopIterations )
{
// This creates a test IList that is an array composed of a few non-string values, including null,
// combined with numberOfRandomStrings + 1 strings random strings,
// of every length from 0 (empty string and hence the + 1) to numberOfRandomStrings.
// We will run all the test loops on this collection 500 times (specified by loopIterations)
IList src = new object?[] { 1, 5f, 222222u, long.MaxValue, null, DateTime.UnixEpoch, true, false, double.NaN, decimal.MinusOne }
.Union( Enumerable.Range( 0, numberOfRandomStrings + 1 ).Select( static i => TestContext.CurrentContext.Random.GetString( i ) ) ).ToArray( );
int expectedMaxStringLength = Math.Max( numberOfRandomStrings, DateTime.UnixEpoch.ToString( CultureInfo.CurrentCulture ).GetColumns( ) );
// This is not part of the test yet.
// This loop guarantees that all strings and string representations of non-string items in src have been interned,
// so that none of the test cases pay unfair penalties for the runtime doing that when they run,
// and we are thus isolating the performance test to just the implementation of the method.
foreach ( object? t in src )
{
TestContext.CurrentContext.CancellationToken.ThrowIfCancellationRequested( );
switch ( t )
{
case string s:
{
string interned = string.Intern( s );
Assert.That( string.IsInterned( s ), Is.SameAs( interned ) );
Assume.That( s.GetColumns, Throws.Nothing );
}
continue;
case { }:
{
string interned = string.Intern( t.ToString( )! );
Assume.That( string.IsInterned( t.ToString( )! ), Is.SameAs( interned ) );
Assume.That( interned.GetColumns, Throws.Nothing );
}
continue;
case null:
// Skip null because duh
continue;
}
}
Stopwatch sw = new( );
Assume.That( sw.ElapsedTicks, Is.Zero );
// Now for the tests...
// Here's the PLINQ implementation
// One thing of note is that, if a generic IList<T> were to be used, or even almost anything other than System.Collections.IList, specifically,
// this actually speeds up dramatically.
// They all speed up quite a bit, with generics but this one gets the largest delta from it, and can outperform the others (except the hybrid) more often.
for ( int runCounter = 0; runCounter < loopIterations; runCounter++ )
{
TestContext.CurrentContext.CancellationToken.ThrowIfCancellationRequested( );
sw.Start( );
// Begin actual implementation
int maxLength = src.OfType<object?>( ).AsParallel( ).Max( static item => item switch
{
string s => s.GetColumns( ),
{ } => item.ToString( )?.GetColumns( ) ?? 0,
null => 0
} );
// End actual implementation
sw.Stop( );
Assert.That( maxLength, Is.EqualTo( expectedMaxStringLength ) );
}
long linqTotalTicks = sw.ElapsedTicks;
// Reset and prove it is reset.
sw.Reset( );
Assume.That( sw.ElapsedTicks, Is.Zero );
// The following implementations are loops.
// The first two are slightly different implementations I tried, to see if there was any improvement possible.
// The third is a hybrid approach using a foreach for <32 elements and PLINQ for >=32 elements.
// Here's the first new for loop implementation I tried, which is a bit clearer/more explicit and more compact than the original,
// due to the switch expression and the Math.Max call, which is about as obvious as that operation gets.
for ( int runCounter = 0; runCounter < loopIterations; runCounter++ )
{
TestContext.CurrentContext.CancellationToken.ThrowIfCancellationRequested( );
sw.Start( );
// Begin actual implementation
int maxLength = 0;
for ( int itemIndex = 0; itemIndex < src.Count; itemIndex++ )
{
var item = src[ itemIndex ];
maxLength = Math.Max( maxLength, item switch
{
string s => s.GetColumns( ),
{ } => item.ToString( )?.GetColumns( ) ?? 0,
null => 0
} );
}
// End actual implementation
sw.Stop( );
Assert.That( maxLength, Is.EqualTo( expectedMaxStringLength ) );
}
long loopTotalTicks = sw.ElapsedTicks;
// Reset and prove it is reset.
sw.Reset( );
Assume.That( sw.ElapsedTicks, Is.Zero );
// Here's a foreach loop implementation that is nearly identical to the above for loop,
// but manages to save one line (though that one line can be regained in the above loop by not pulling out the 'item' reference).
// It is nearly always slightly faster than the plain for loops
for ( int runCounter = 0; runCounter < loopIterations; runCounter++ )
{
TestContext.CurrentContext.CancellationToken.ThrowIfCancellationRequested( );
sw.Start( );
// Begin actual implementation
int maxLength = 0;
foreach ( var item in src )
{
maxLength = Math.Max( maxLength, item switch
{
string s => s.GetColumns( ),
{ } => item.ToString( )?.GetColumns( ) ?? 0,
null => 0
} );
}
// End actual implementation
sw.Stop( );
Assert.That( maxLength, Is.EqualTo( expectedMaxStringLength ) );
}
long foreachTotalTicks = sw.ElapsedTicks;
// Reset and prove it is reset.
sw.Reset( );
Assume.That( sw.ElapsedTicks, Is.Zero );
// This is the hybrid loop, using the foreach for collections with fewer than 32 elements and the PLINQ method otherwise
for ( int runCounter = 0; runCounter < loopIterations; runCounter++ )
{
TestContext.CurrentContext.CancellationToken.ThrowIfCancellationRequested( );
sw.Start( );
// Begin actual implementation
int maxLength = 0;
if ( src.Count > 31 )
{
maxLength = src.OfType<object?>( ).AsParallel( ).Max( static item => item switch
{
string s => s.GetColumns( ),
{ } => item.ToString( )?.GetColumns( ) ?? 0,
null => 0
} );
}
else
{
foreach ( var item in src )
{
maxLength = Math.Max( maxLength, item switch
{
string s => s.GetColumns( ),
{ } => item.ToString( )?.GetColumns( ) ?? 0,
null => 0
} );
}
}
// End actual implementation
sw.Stop( );
Assert.That( maxLength, Is.EqualTo( expectedMaxStringLength ) );
}
long hybridTotalTicks = sw.ElapsedTicks;
// Reset and prove it is reset.
sw.Reset( );
Assume.That( sw.ElapsedTicks, Is.Zero );
// Here's the original, with a few fixes applied:
// 1) There was a null reference exception in the else case,
// if the item was null or if ToString() on the item returned null (fixed with conditionals).
// 2) There was a redundant else if block that was impossible to reach (fixed by removing).
// 3) There was inconsistent behavior in the cases,
// as the first case called GetColumns, but none of the others did (fixed by making all call GetColumns()).
// 3a) Note that, if the call to GetColumns is not actually necessary, every one of these implementations speeds
// up by a minimum of 400%, and sometimes as much as over 70000% (yes, 700x).
for ( int runCounter = 0; runCounter < loopIterations; runCounter++ )
{
TestContext.CurrentContext.CancellationToken.ThrowIfCancellationRequested( );
sw.Start( );
// Begin actual implementation
int maxLength = 0;
for ( int i = 0; i < src.Count; i++ )
{
var t = src[ i ];
int l;
if ( t is string u )
{
l = u.GetColumns( );
}
else
{
l = t?.ToString( )?.GetColumns( ) ?? 0;
}
if ( l > maxLength )
{
maxLength = l;
}
}
// End actual implementation
sw.Stop( );
Assert.That( maxLength, Is.EqualTo( expectedMaxStringLength ) );
}
long originalTotalTicks = sw.ElapsedTicks;
// Here we'll make some nice output for each method's:
// total time
// average time per execution
// percentage difference from the slowest method
// percentage difference from the fastest method
long[] allTickCounts = [linqTotalTicks, loopTotalTicks, foreachTotalTicks, originalTotalTicks, hybridTotalTicks];
ref long slowestTime = ref allTickCounts[ allTickCounts.IndexOf( allTickCounts.Max( ) ) ];
ref long fastestTime = ref allTickCounts[ allTickCounts.IndexOf( allTickCounts.Min( ) ) ];
int[] columnWidths = [ImplementationNameColumnWidth, NumericColumnWidth, NumericColumnWidth, NumericColumnWidth, NumericColumnWidth];
TestContext.WriteLine( $"{"Method",-ImplementationNameColumnWidth} | {"Total",NumericColumnWidth} | {"Average",NumericColumnWidth} | {"ΔMax",NumericColumnWidth} | {"ΔMin",NumericColumnWidth}" );
TestContext.WriteLine( new string( '-', columnWidths.Sum( ) + 3 * ( columnWidths.Length - 1 ) ) );
WriteFormattedResultLine( "PLINQ", in linqTotalTicks, in loopIterations, in slowestTime, in fastestTime );
WriteFormattedResultLine( "new for loop", in loopTotalTicks, in loopIterations, in slowestTime, in fastestTime );
WriteFormattedResultLine( "foreach loop", in foreachTotalTicks, in loopIterations, in slowestTime, in fastestTime );
WriteFormattedResultLine( "hybrid PLINQ/foreach", in hybridTotalTicks, in loopIterations, in slowestTime, in fastestTime );
WriteFormattedResultLine( "fixed original", in originalTotalTicks, in loopIterations, in slowestTime, in fastestTime );
}
private static void WriteFormattedResultLine( in string methodName, in long totalTicks, in int loopIterations, in long slowestTime, in long fastestTime )
{
TestContext.WriteLine( $"{methodName,-ImplementationNameColumnWidth} | {totalTicks,NumericColumnWidth:N0} | {totalTicks / (double)loopIterations,NumericColumnWidth:N0} | {( totalTicks - slowestTime ) / (double)slowestTime,NumericColumnWidth:P2} | {( totalTicks - fastestTime ) / (double)fastestTime,NumericColumnWidth:P2}" );
}
}
[^1]: You can adjust the loopIterations parameter for that, by either changing the single value listed or by adding more numbers to the list, which will combinatorially create cases with that parameter for every value of numberOfRandomStrings specified as well, if you want to get crazy. [^2]: I wrote it from the TerminalGuiDesigner test project, since I was investigating an unrelated issue and got distracted down this rabbit hole. XUnit's means of parameterization is not as clean or advanced as NUnit's, and I wanted to be able to turn knobs easily. Plus, the test method itself isn't really intended to be used as a unit test for Terminal.Gui - it's just a performance comparison. If you want to run it yourself, it's easiest just to paste it into the TerminalGuiDesigner code in the v2 branch and just run it as-is. Short cases finish in a few seconds. The longer runs can take a few minutes. There is a time limit on the test method in case things go too long. [^3]: This is because the case generation code simply creates an array of unique random strings of length 0 to the size of the collection, which both gives a range of inputs and provides a testably predictable max string length with non-uniform inputs. [^4]: It's almost certainly not a penalty the first one pays for computation of the expression, because running it 20000 times would smooth that out.
My most important question regarding this is about the GetColumns method.
Is that actually necessary? I am assuming it is, in case some character is wider than one column. And, since strings are UTF-16, if that method is important, it definitely should be used in all cases, because we don't know what a string or some non-string's ToString contains.
However, if it is not, or if there's a way we can short-circuit it in the majority of cases, there's a very real benefit to be realized.
Although strings are UTF-16, there are some that are wider. So some Bmp code points are wider.
Although strings are UTF-16, there are some that are wider. So some Bmp code points are wider.
Cool, so then yes it's good I assumed GetColumns was necessary.
The fixed code uses it for all non-null cases. The original code did not.
I suspect that particular edge case might exist elsewhere, too, based on a hazy recollection of what I saw when looking through the code earlier.
For very big source maybe it could having an option to only consider a indexed range instead of all the data.
And a side note about GetColumns:
I've put an item on my personal to-do list to dive into that method at some point and see if there's anything we can due to optimize it at a high level without changing behavior. The fact that it is as heavy as it is, in the testing I did, makes me suspect we might be able to lighten the load at least a little bit, or perhaps avoid some allocations or something.
Even a small benefit there can have a palpable impact on the user experience in a finished application, especially if there are multiple Views or other elements calling it at every update.
That's actually one place where TG itself could internally benefit from implementing INotifyPropertyChanged and INotifyCollectionChanged, too. Being able to react to actual changes only when they occur can mean skipping a lot of redundant work. That applies in general - not just to GetColumns.
For very big source maybe it could having an option to only consider a indexed range instead of all the data.
Well, it's a per-string thing. Unfortunately, to be accurate, it will always have to check all code points in a given string. I don't see an immediately obvious way, conceptually, to avoid that. 🤔
I'll have to look at the code again to make specific comments, but the general thoughts I have are along the lines of just making sure it isn't algorithmically overcomplicated, makes use of whatever built-in dotnet facilities it can, where relevant, makes use of language features that allow the compiler to optimize more aggressively, and perhaps makes use of parallel execution for strings over some threshold, as it's a highly implicitly parallelizable operation. That's similar to my hybrid implementation above for max length that uses a loop for small collections and parallel code for larger ones - just for strings instead (though string does also implement IEnumerable<char> among others, so it may be quite easy to sprinkle that sort of thing in).
The algorithm itself is always going to scale linearly, in the worst case, on string length, but parallel execution can at least cut it down by a factor of however many threads the runtime elects to use. Tuning of that would have to be by experimentation, as I did for GetMaxItemLength's loop (which I found a cutoff for and then picked the nearest power of 2).
Use of PLINQ also creates an opportunity for the compiler to use SIMD operations, for optimized builds, without any work on our part, which is free performance. 😀
Yes it check for each rune, but if a IListDataSource has 4 millions of items where each one has strings with a variated length, then if we only get the next 100 items based on the current top+ContentArea, more or less, we don't needed to execute the method for all the items of the source.
Yes it check for each rune, but if a
IListDataSourcehas 4 millions of items where each one has strings with a variated length, then if we only get the next 100 items based on the current top+ContentArea, more or less, we don't needed to execute the method for all the items of the source.
Oh OK I got you. You mean in the context of this function/loop, not GetColumns itself.
I have mixed feelings on that, though. On the pro side, it does save a lot of work over that threshold. On the con side, it may not be desired behavior (a user might want all elements considered).
If making it abort early, I would suggest that needs to be a configurable/controllable behavior, probably as a property on whatever View types contain collections for which that operation would need to be run repeatedly, and probably also with the default cutoff exposed in configuration. And whatever the default behavior is should of course be documented, especially if the default were to be early exit.
Oh OK I got you. You mean in the context of this function/loop, not GetColumns itself.
Yes.
I have mixed feelings on that, though. On the pro side, it does save a lot of work over that threshold. On the con side, it may not be desired behavior (a user might want all elements considered).
His problem. The user must have the change to choice how many items he want to get from the source.
If making it abort early, I would suggest that needs to be a configurable/controllable behavior, probably as a property on whatever View types contain collections for which that operation would need to be run repeatedly, and probably also with the default cutoff exposed in configuration. And whatever the default behavior is should of course be documented, especially if the default were to be early exit.
A parametrized method maybe or something. How it works of course it should well documented by who well know do it. 😄
Well. Also... The user can always just explicitly set the width of relevant views anyway, right?
Sorry you are right. I said top+height before but I wanted to say left+width (this is for GetColumns).
Ha alrighty. Well anyway that would be a separate issue if/when it is to be approached.
This issue is for the specific issues mentioned up top.
I'm heading out for a bit right now, but thanks for the mini brainstorming session. 🙂