Improve performance of Group-Object by powercode · Pull Request #7410 · PowerShell/PowerShell

Staffan Gustafsson (powercode) · 2018-07-30T20:16:27Z

PR Summary

code cleanup
object[] -> IList in PSType.ArrayToTuple signature to reduce allocations.
Sort input before grouping. Use sorting to only consider last group when comparing.
adding DebuggerDisplay for GroupInfo.

PR Checklist

Refactoring only - no functional changes.

This reducing alloctions and object copying.

…hen comparing. Much faster when the number of unique values grows large.

Staffan Gustafsson (powercode) · 2018-07-31T00:34:31Z

Appveyor error seem unrelated to my changes.

Ilya (iSazonov) · 2018-07-31T05:20:55Z

            {
-                if (propValue != null && propValue.PropertyValue != null)
+                var propValuePropertyValue = propValue?.PropertyValue;
+                if (propValuePropertyValue != null)


Is the check really needed?

yes, it is dereferenced in the else clause. #Closed.

Ilya (iSazonov) · 2018-07-31T05:24:56Z

            OrderByPropertyComparer orderByPropertyComparer)
        {
-            if (currentObjectEntry != null && currentObjectEntry.orderValues != null && currentObjectEntry.orderValues.Count > 0)
+            var currentObjectorderValues = currentObjectEntry.orderValues;


Should it be currentObjectOrderValues?

I don't see the fix.

Please address the comment and fix case.

Ilya (iSazonov) · 2018-07-31T05:41:35Z

-                        //add this inputObject to an existing group
-                        currentGroupInfo.Add(currentObjectEntry.inputObject);
-                    }
+                    //add this inputObject to an existing group


Please add space after //.

Ilya (iSazonov) · 2018-07-31T05:55:22Z

-                        foreach (GroupInfo _grp in _groups)
+                        foreach (GroupInfo grp in _groups)
                        {
                            if (AsString)


Make sense to move the cycle into the if (AsString) ?

Not sure i understand what you suggest here.

I meant

if (AsString) { foreach (GroupInfo grp in _groups) { table.Add(grp.Name, grp.Group); } } else { foreach (GroupInfo grp in _groups) { if (grp.Values.Count == 1) { ... } } }

Yes, I think that is clearer.

I thought more about performancethough :-) From this point of view it seems for() better than foreach - less allocations. Is the _groups so much that we can get a win?

Also some additional CodeFactor complaints

Staffan Gustafsson (powercode) · 2018-07-31T16:06:59Z

I would like to fix the parameter sets too.

[Parameter(ParameterSetName = "HashTable", Mandatory = true)]
public SwitchParameter AsHashTable { get; set; }

[Parameter(ParameterSetName = "HashTable")]
public SwitchParameter AsString { get; set; }

Moving parameter checking earlier. Adding back the slow quadratic code path for the cases where we have more than one set of input types.

Ilya (iSazonov) · 2018-08-01T09:04:29Z

I believe we shouldn't mess performance changes with other and it is better fix parameter sets in new PR.

Ilya (iSazonov) · 2018-08-01T09:12:06Z

+                    if (AsHashTable
+                        && !AsString
+                        && (Property != null && Property.Length > 1
+                            || _orderByProperty.MshParameterList.Count > 1))


We'd move this line on previous line.

Ilya (iSazonov)

Leave a comment

Ilya (iSazonov) · 2018-08-02T04:38:13Z

    {
        internal GroupInfoNoElement(OrderByPropertyEntry groupValue)
-            : base(groupValue)
+        : base(groupValue)


Please move to previous line 115.

Ilya (iSazonov) · 2018-08-02T04:39:05Z

        /// <summary>
        /// Gets or sets the AsString parameter.
        /// </summary>
+        /// <value></value>


Please remove the empty XML comment.

Ilya (iSazonov) · 2018-08-02T04:39:36Z

            OrderByPropertyComparer orderByPropertyComparer)
        {
-            if (currentObjectEntry != null && currentObjectEntry.orderValues != null && currentObjectEntry.orderValues.Count > 0)
+            var currentObjectorderValues = currentObjectEntry.orderValues;


Please address the comment and fix case.

Ilya (iSazonov)

LGTM with two minor comments.

Ilya (iSazonov) · 2018-08-07T06:30:29Z

                    else
                    {
-                        sb.Append(string.Format(CultureInfo.InvariantCulture, "{0}, ", propValue.PropertyValue.ToString()));
+                        sb.Append(string.Format(CultureInfo.InvariantCulture, "{0}, ", propValuePropertyValue.ToString()));


Seems string.Format was optimized in .Net Core 2 but we could still use AppendFormat() here and in line 160 to get more readable code and exclude extra method calls.

This definitely should use AppendFormat()

Ilya (iSazonov) · 2018-08-07T06:35:15Z

            OrderByPropertyComparer orderByPropertyComparer)
        {
-            if (currentObjectEntry != null && currentObjectEntry.orderValues != null && currentObjectEntry.orderValues.Count > 0)
+            var currentObjectorderValues = currentObjectEntry.orderValues;


currentObjectorderValues should be currentObjectOrderValues.

Dan Travison (dantraMSFT) · 2018-08-07T22:45:18Z

        {
            Diagnostics.Assert(inputObjects != null, "inputObjects is null");
-            Diagnostics.Assert(inputObjects.Length > 0, "inputObjects is empty");
+            Diagnostics.Assert(inputObjects.Count > 0, "inputObjects is empty");


This assert is redundant. ArrayToTuple(IList, int> has the exact same code. Suggest removing both Assert statements.

Dan Travison (dantraMSFT) · 2018-08-07T22:45:57Z

        {
            Diagnostics.Assert(inputObjects != null, "inputObjects is null");
-            Diagnostics.Assert(inputObjects.Length > 0, "inputObjects is empty");
+            Diagnostics.Assert(inputObjects.Count > 0, "inputObjects is empty");


These asserts should be backed up with runtime checks. Either document it as returning NULL when constraints are not met for throw the appropriate exceptions.

This is a fairly common pattern in the engine, that there are asserts, but no backing runtime checks. I have always wondered about it...

I guess the thinking is that since it's an internal class, the usage can be demonstrated to be safe and the error checking skipped.

Since we don't have an official policy around Assert, I'll not hold up the PR for it and you can ignore the rest. :)

I've been involved in three different threads recently where Dbg.Assert in internal code is hit in debug builds. In two cases, crashes were occurring the release build and the third the lack of the check was masking a bug in another component.

IMHO: Since we don't test debug builds, Dbg.Assert is a placebo at best without a release check.

Dan Travison (dantraMSFT) · 2018-08-07T22:51:13Z

                    else
                    {
-                        sb.Append(string.Format(CultureInfo.InvariantCulture, "{0}, ", propValue.PropertyValue.ToString()));
+                        sb.Append(string.Format(CultureInfo.InvariantCulture, "{0}, ", propValuePropertyValue.ToString()));


This definitely should use AppendFormat()

Dan Travison (dantraMSFT) · 2018-08-07T22:57:59Z

+        /// <param name="groups">List containing Groups.</param>
+        /// <param name="groupInfoDictionary">Dictionary used to keep track of the groups with hash of the property values being the key.</param>
+        /// <param name="orderByPropertyComparer">The Comparer to be used while comparing to check if new group has to be created.</param>
+        internal static void DoOrderedGrouping(


Shouldn't this be private

It was internal, and I just kept it so, but I'm happy to make it private.

Dan Travison (dantraMSFT) · 2018-08-07T23:27:17Z


-                GroupInfo currentGroupInfo = null;
-                if (groupInfoDictionary.TryGetValue(currentTupleObject, out currentGroupInfo))
+                if (groupInfoDictionary.TryGetValue(currentTupleObject, out var currentGroupInfo))


What's the use case for currentGroupInfo being null in the groupInfoDictionary? If it is expected, a comment is needed; otherwise, it looks like currentObjectEntry.inputObject is dropped on the floor.

I don't think that is a case that will ever occur. Just defensive programming.

Both cases are behaving as the original implementation.

One could argue for removing the null check as it is a condition that shouldn't occur, and if it does, it is a bug that should be fixed.

Dan Travison (dantraMSFT) · 2018-08-07T23:29:31Z

+                if (groupInfoDictionary.TryGetValue(currentTupleObject, out var currentGroupInfo))
+                {
+                    // add this inputObject to an existing group
+                    currentGroupInfo?.Add(currentObjectEntry.inputObject);


same as above, when is currentTupleObject present but currentGroupInfo is null.

Yeah, I'm removing the null checks.

Removing unnecessary call to .ToArray(). Making internal methods private.

Dongbo Wang (daxian-dbw) · 2018-08-09T18:35:05Z

Dan Travison (@dantraMSFT) Can you please take another look?

Dan Travison (dantraMSFT)

LGTM

Ilya (iSazonov) · 2018-08-10T03:26:43Z

Staffan Gustafsson (@powercode) Many thanks for the great perf improvement!

Initial cleanup.

dec4513

Refactoring only - no functional changes.

Staffan Gustafsson (powercode) requested review from Bruce Payette (BrucePay), James Truher (JamesWTruher), Paul Higinbotham (PaulHigin), Dan Travison (dantraMSFT) and Dongbo Wang (daxian-dbw) as code owners July 30, 2018 20:16

Gustafsson, Staffan and others added 6 commits July 31, 2018 01:48

object[] -> IList<T> in PSType.ArrayToTuple signature

c1602e7

This reducing alloctions and object copying.

Adding DebuggerDisplay for GroupInfo

47c0bd5

Sort input before grouping. Use sorting to only consider last group w…

6ae93d8

…hen comparing. Much faster when the number of unique values grows large.

Fixing DebuggerDisplay for CommandInfo.

13ee3cd

Addressing code-factor issues

41fb917

Using a stable sort algorithm so that Group order is maintained.

bdd6bb8

Staffan Gustafsson (powercode) force-pushed the groupobj branch from 9421ab5 to bdd6bb8 Compare July 30, 2018 23:52

More code factor fixes

963ac55

Ilya (iSazonov) reviewed Jul 31, 2018

View reviewed changes

Addressing review comments

bb618bf

Also some additional CodeFactor complaints

Refactoring Group-Object logic.

f1ccbed

Moving parameter checking earlier. Adding back the slow quadratic code path for the cases where we have more than one set of input types.

Staffan Gustafsson (powercode) changed the title ~~Improve performance of Group-Object~~ WIP: Improve performance of Group-Object Jul 31, 2018

Staffan Gustafsson (powercode) changed the title ~~WIP: Improve performance of Group-Object~~ Improve performance of Group-Object Jul 31, 2018

Fixing error with determining if there are multiple types involved.

88039a1

Ilya (iSazonov) reviewed Aug 1, 2018

View reviewed changes

Staffan Gustafsson (powercode) added 3 commits August 1, 2018 20:35

Merge branch 'master' into groupobj

cc42c0c

Reverting ParametersetName changes.

10e8525

CodeFactor fixes.

3d4b7ff

Ilya (iSazonov) reviewed Aug 2, 2018

View reviewed changes

Addressing review comments

152d1eb

Staffan Gustafsson (powercode) force-pushed the groupobj branch from 7b43e70 to 152d1eb Compare August 2, 2018 22:40

Dongbo Wang (daxian-dbw) self-assigned this Aug 3, 2018

Ilya (iSazonov) approved these changes Aug 7, 2018

View reviewed changes

Dongbo Wang (daxian-dbw) approved these changes Aug 7, 2018

View reviewed changes

Add new line at the end of file

e41c6b8

Dan Travison (dantraMSFT) suggested changes Aug 7, 2018

View reviewed changes

Staffan Gustafsson (powercode) added 2 commits August 8, 2018 10:02

Addressing review comments from dantraMSFT and iSazonov.

8329b33

Addressing review comments.

7454fe0

Removing unnecessary call to .ToArray(). Making internal methods private.

Dan Travison (dantraMSFT) approved these changes Aug 9, 2018

View reviewed changes

Dongbo Wang (daxian-dbw) merged commit 037e12e into PowerShell:master Aug 9, 2018

Thatgfsj (Thatgfsj) pushed a commit to Thatgfsj-contribs/PowerShell that referenced this pull request Aug 6, 2026

Improve the performance of 'Group-Object' (PowerShell#7410)

a9af044

Uh oh!

Conversation

Staffan Gustafsson (powercode) commented Jul 30, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

PR Summary

PR Checklist

Uh oh!

Staffan Gustafsson (powercode) commented Jul 31, 2018

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Staffan Gustafsson (powercode) Jul 31, 2018 • edited by iSazonov Loading Uh oh! There was an error while loading. Please reload this page.

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!

Staffan Gustafsson (powercode) commented Jul 31, 2018

Uh oh!

Ilya (iSazonov) commented Aug 1, 2018

Uh oh!

Ilya (iSazonov) Aug 1, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Ilya (iSazonov) 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!

Ilya (iSazonov) 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!

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!

Staffan Gustafsson (powercode) Aug 8, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Staffan Gustafsson (powercode) commented Jul 30, 2018 •

edited

Loading

Staffan Gustafsson (powercode) Jul 31, 2018 •

edited by iSazonov

Loading

Ilya (iSazonov) Aug 1, 2018 •

edited

Loading

Staffan Gustafsson (powercode) Aug 8, 2018 •

edited

Loading

Dan Travison (dantraMSFT) Aug 7, 2018 •

edited

Loading