Powershell: Assigning the result of an addition (+ operator) with an IList LHS back to that LHS should preserve the list (collection) type

[mklement0]

The following idioms should work generically with extensible collections that implement the IList interface and therefore have an .Add(Object) method.

# The following should both call $list.Add($newElement) behind the scenes:
$list = $list + $newElement
$list += $newElement

This would match the current _array_ behavior (although a _new_ array is created every time, given that arrays are fixed-size collections), as well as the behavior with _hashtables_ (with hashtables as the RHS values too).

The current behavior is unexpected:

• with an unconstrained variable: quietly converts the LHS to an _array_:

$list = [System.Collections.ArrayList] (1, 2)
$list += 3  # !! Quietly converts the ArrayList to Object[]
$list.GetType().Name . # !! Object[] 

• with a type-constrained variable: creates a _new instance_

[System.Collections.ArrayList] $list = 1, 2 # type-constrained ArrayList
$orgList = $list # save reference to original list
$list += 3  # !! Quietly creates a *new instance*
[object]::ReferenceEquals($list, $orgList) # !! $False

Environment data

PowerShell Core v6.0.0-rc.2 (v6.0.0-rc.2) on macOS 10.13.2

[iSazonov]

😄 Once I opened the case on Connect site and this case was closed "by design". It seems now we ready implement this enhancement.

[iSazonov]

@SteveL-MSFT Could you please consider this on PowerShell committee with #5643?

[bergmeister]

@mklement0 Awesome!

[daxian-dbw]

Does $list + $newElement always result in $list.Add($newElement) and then return $list, or only $list += $newElement and $list = $list + $newElement result in $list.Add($newElement)?

If it's the latter, will $list + $newElement still return an object array? Then comparing $newlist = $list + $newElement with $list = $list + $newElement, the behavior of binary add needs to be different in those two cases, which in my opionion might be pretty hacky in imeplementation.

I thought about having $list + $newElement always result in $list.Add($newElement) and then return $list, when it's able to. The potential problem is that an operand ($list) would be changed in the binary add operation, and I'm not sure whether that would be a bad UX.

We also need to think about the consistency with Hashtable add operation. As shown in the example scripts below, adding two dictionary always creates a new Hashtable instance, and $hash1 += $hash2 will also result in a new Hashtable assigned to $hash1.

$h = @{ name = "hello" }
$s = @{ blah = "world" }
$m = $h + $s # new Hashtable is created
[System.Object]::ReferenceEquals($m, $h) #  False
[System.Object]::ReferenceEquals($m, $s) # False

$oldh = $h
$h += $s # create new Hashtable
[System.Object]::ReferenceEquals($h, $oldh) # False

[mklement0]

Does $list + $newElement always result in $list.Add($newElement)

No - only if you assign back to the same variable; with the exception of the <op>= compound operators, operators shouldn't modify their operands in place as a side effect - that would indeed be unexpected.

---

Yes, even though hashtables commendably do preserve the LHS type, they currently always create a _new_ instance, as you demonstrate.

I suppose one way to resolve this - if it's not too risky in terms of backward compatibility - is to update hashtable LHSs in place too, _if_ self-assignment is involved.

Resolving in the opposite direction - also always creating new instances for _lists_ - would defeat the purpose of allowing efficient, incremental construction of (large) lists via +, as suggested in #5643 (my guess is that this is less of a concern with hashtables, as they typically don't grow too large).

---

Perhaps there are implementation difficulties and even conceptual barriers I'm not considering; I guess we need to decide what specific expression forms to apply the proposed behavior to.

$list += ... is unambiguous, but things get trickier with $list = ...:

$list = $list + ... is the equivalent of the above; $list = ($list + ...) should be the same, but what about other variations, such as $list = $($list + ... ) or $list = @($list + ... )?

There is also the other array-aware operator, * (am I missing others?): $list *= 2 should by analogy also append in place.

In the end it must be reasonably obvious when in-place updating occurs and when not - though casual users may not care.

[SteveL-MSFT]

@PowerShell/powershell-committee reviewed this and agreed that we should adopt only the +=, *=, and -= (if possible) syntax as they are unambiguous. Although technically a breaking change, it should not functionally affect most users other than giving them a perf benefit.

[lzybkr]

Note to whoever decides to implement this - as currently implemented, the binary operation binder knows nothing about assignment, so care is required to restrict this to += and not +.

I do have a slight concern that by adding operator support, we'll make it much easier to make assumptions about how adding to lists works - e.g. if I add 2 lists - is that concatenation? Probably not, but if you don't introduce another operator, it will trip people up.

[daxian-dbw]

I can take a stab at += and *= as I have some code for this when working on the ListExpression.

we'll make it much easier to make assumptions about how adding to lists works - e.g. if I add 2 lists - is that concatenation?

Not sure I completely understand what you mean :) Adding two lists is kinda concatenation today -- it creates a new array containing all the elements from those 2 lists. So I think $list += $list2 should be adding the elements from $list2 to $list.

[iSazonov]

If it's the latter, will $list + $newElement still return an object array? Then comparing $newlist = $list + $newElement with $list = $list + $newElement, the behavior of binary add needs to be different in those two cases, which in my opionion might be pretty hacky in imeplementation.

We should document that $list + $newElement and $hash + $newElement always new object.
Maybe make pivot table for all such operations for docs?

[lzybkr]

If you just call List.Add, you have a list of lists. If you concatenate, you need to call AddRange. Would you do that for anything that is enumerable?

I think reasonable people could expect either of the behaviors, and this is why languages with list primitives have a concatenation operator.

[daxian-dbw]

We should document that $list + $newElement and $hash + $newElement always new object.
Maybe make pivot table for all such operations for docs?

To @iSazonov, I agree that we need to document the behavior.

If you just call List.Add, you have a list of lists. If you concatenate, you need to call AddRange. Would you do that for anything that is enumerable?

To @lzybkr, I see your point now. The current behavior of binary add operation is to create a new array containing all element from _left-hand-side_ and _right-hand-side_ as long as both are enumerable. I will mimic that behavior for the implementation of += for now, and we can wait for the feedback later.

[mklement0]

Unfortunately, I did a poor job of separating two distinct aspects:

• (a) the desire to _preserve the type_ of an IList LHS with +, * (when does - come into play?)

• (b) the desire to (additionally) _update the LHS in place_ with +=, *=, -=

I feel that for consistency with existing operator behavior (a) should be implemented either way, whether with or without in-place updating.

As for (b), just to clarify: Is the committee's decision to indeed implement in-place updating for +=, *=, -= (which I hope)?

If so, I feel slightly uneasy about deviating from the equivalence of $l += ... and $l = $l + ....

---

Re .Add() vs. .AddRange() (adding a collection as a single new element vs. concatenating the two collections):

As @daxian-dbw points out, + with _arrays_ already uses _concatenation_ (e.g., 1, 2 + 3, 4 yields 1, 2, 3, 4), so I think users will expect the same behavior by analogy for other collection types.

Note that the IList interface doesn't actually have an .AddRange() method, so iterative .Add() calls may be needed.

[PetSerAl]

How about this:

$a=[Collections.Generic.List[object]]::new((1..3))
$b=$a
$b+=4
$a.Count # expect it to be 3

The fact that at $b+=4 variable $b loose reference to the old list does not mean that no one else have reference to the same list and it is OK to change it. IMO, intention to change collection should be explicit and expressed by calling the Add method.

[mklement0]

@PetSerAl:

Bear in mind that the concept of a _reference_ isn't even on the radar of most PowerShell users, if I were to guess.

A casual user using $a += ... to "append to" an array may not even be aware that a new array instance is created every time and how expensive that is.
That's why switching that plumbing to in-place updating would provide a great, automatic optimization - and would obviate the need for the nontrivial mental switch from PS-native operator syntax (+=) to "foreign" method syntax (.Add(...)).

Yes, advanced users would then need to be aware that =+ performs in-place updating and potentially affects references to the same object held elsewhere - but, in my estimation, that price is worth paying (and clearly documentating that behavior would help).

[PetSerAl]

@mklement0
As far as I understand, in .NET it is expected that operators would not visible modify their arguments. To this point PowerShell follows that rule. I do not see good reasons why it need to deviate from it now.

Bear in mind that the concept of a reference isn't even on the radar of most PowerShell users, if I were to guess.

So, how would you answer to their question: "I change only $b, why does $a also changed?" — without involving reference concept? This change actually require users to be more aware of that concept.

A casual user using $a += ... to "append to" an array may not even be aware that a new array instance is created every time and how expensive that is.

How them benefit of that change? If you do not create List in the first place, then it still will be costly array addition. And, if you know that you need to use List for performance, then you should also have to know how to use it right.

And I do not see how method calling is less native to PowerShell, than operators. It was here from version one. And, after all, object-oriented concept is what make PowerShell different from other shells.

Also, System.Collections.Generic.List<T> is not only IList type in .NET. How you planning to implement proposed behavior for unknown type of IList? For example IList can be read-only: should += fail, or create new list, should new list be of the same read-only type, what if there are no public constructor?

[mklement0]

So, how would you answer to their question: "I change only $b, why does $a also changed?"

If someone doesn't know about references, that question would arise irrespective of this proposed change: changing $b using _any_ mechanism would cause this confusion.

How them benefit of that change? If you do not create List in the first place, then it still will be costly array addition.

Ah, yes. I guess I still haven't let go of the idea that PowerShell should use lists rather than arrays with @(...). There's always the future!

if you know that you need to use List for performance, then you should also have to know how to use it right.

That's not a matter of right and wrong, but one of _convenience_ and being _PowerShell-like_:

If you only know PowerShell, then all you need to know is that [list] is a mutable data structure you can efficiently append to - you shouldn't have to know about the underlying .NET type and its members.
From a PowerShell perspective, using += to append to that data structure makes sense.

And I do not see how method calling is less native to PowerShell, than operators. It was here from version one.

_Property_ access comes naturally in PowerShell, _method_ calls do not.

Ideally, you never need to call methods - that's what _cmdlets_ are for.

The context switching between PowerShell's argument mode and .NET method syntax is a perennial pain point, even for experienced users.

For example IList can be read-only: should += fail, or create new list?

It should fail.

[PetSerAl]

Ideally, you never need to call methods - that's what cmdlets are for.

So, this would be ideal solution:

Add-ElementToList -List $List -Element $Element

[mklement0]

True, but let's focus on the important parts first:

The cryptic 1 + 1 should really be:

Add-Item -LeftOperand 1 -RightOperand 1

For power users (method actors, if you will):

1.Add(1)

[mklement0]

Kidding aside:

Tcl is an example of a language where _everything_ is invoked with shell-like (argument-mode) syntax and there's something to be said for this simplification.
Clearly, though, that is not the direction PowerShell chose.

Instead, PowerShell uses _operators_ to provide convenient abstractions: Much of what requires _method calls_ in, say, C#, is provided via operators such as -join, -split, -replace, ...

To be clear: I'm not saying that you should _avoid_ method calls - full access to the .NET Framework is a wonderful ability that sets PowerShell apart from other shells - I'm saying that you shouldn't _have to_ call methods for _basic operations_, as calling methods is an _advanced skill_, both for _syntactic reasons_ and having to know another _knowledge domain_.

Let's take PowerShell's _array_ handling, for example:

The wonderfully simple construction of arrays (1, 2) and the ability to concatenate them by _operator_ (1, 2 + 3, 4), to test for membership (1 -in 1, 2), ..., shields you from having to know the underlying [object[]] .NET type, and for most array uses you never need to call its methods.

To combine convenient abstraction with _reasonable performance_ when it comes to _gradually building_ arrays ($a += ...), PowerShell should have implemented all of the above as [List[object]] (or at least [ArrayList]) rather than [object[]] from the get-go, but it sounds like it's too late to change that, at least based on the current assessment (is the future here yet?).

The best we can do now is to provide a _PowerShell-like_ way to construct a list ([list] (1, 2, 3) currently being discussed) and _then provide the same syntactic convenience as for arrays_ - with the notable addition of making += extend the list in place.

---

As an aside: consider how PowerShell's one foray into method syntax has fared; the (confusingly named) .ForEach() and .Where() _collection operators_ never gained traction.

[PetSerAl]

@mklement0
For me what you are proposing is abusing operators. It is like C++ repurpose bit-shift operators for input-output handling. I do not like to have such thing in PowerShell. From previous .NET/C# experience I have expectation (IMO, reasonable), that there are some boundaries for expected operators behavior in .NET environment.

• a += b should be semantically equivalent to a = a + b.
  C#, for example, does not even allows to overload += directly.
• Operators should not visible modify theirs arguments.
  C# guides discourage defining operators for mutable types in the first place.

I would understand breaking that boundaries if in return that provide very good benefits, which can not be achieved otherwise. But what we have there?

You would not get any performance benefits unless user use some other type of collection instead of default array. So, instead of array we can provide for users PowerShell own list implementation, which would be friendly to repeatable += call and does not require sacrifice of operators sanity.

using System;
using System.Collections;
using System.Collections.Generic;
using System.Linq;

public class ListWithFastAddition : IList<object>, IReadOnlyList<object>, IList, ICloneable {
    public static ListWithFastAddition operator +(ListWithFastAddition list, object item) {
        if(list==null) {
            throw new ArgumentNullException(nameof(list));
        }
        ListWithFastAddition result = list.Clone();
        result.Add(item);
        return result;
    }

    private List<object> list;
    private int count;

    public ListWithFastAddition() : this(new List<object>(), -1) { }
    private ListWithFastAddition(List<object> list, int count) {
        this.list = list;
        this.count = count;
    }

    public object this[int index] {
        get => index<Count ? list[index] : throw new ArgumentOutOfRangeException(nameof(index));
        set {
            if(OwnList) {
                list[index] = value;
            } else if(index>=0 && index<count) {
                list = list.GetRange(0, count);
                count = -1;
                list[index] = value;
            } else {
                throw new ArgumentOutOfRangeException(nameof(index));
            }
        }
    }
    public int Count => OwnList ? list.Count : count;
    public bool IsReadOnly => false;
    private bool OwnList => count==-1;

    public void Add(object item) {
        if(OwnList) {
            list.Add(item);
        } else if(count==list.Count) {
            list.Add(item);
            count = list.Count;
        } else {
            list = list.GetRange(0, count);
            count = -1;
            list.Add(item);
        }
    }
    public void Clear() {
        if(OwnList) {
            list.Clear();
        } else {
            list = new List<object>();
            count = -1;
        }
    }
    public ListWithFastAddition Clone() {
        if(OwnList) {
            count = list.Count;
        }
        return new ListWithFastAddition(list, count);
    }
    public bool Contains(object item) => IndexOf(item) >= 0;
    public void CopyTo(object[] array, int index) => list.CopyTo(0, array, index, Count);
    public IEnumerator<object> GetEnumerator() => OwnList ? list.GetEnumerator() : list.Take(count).GetEnumerator();
    public int IndexOf(object item) => list.IndexOf(item, 0, Count);
    public void Insert(int index, object item) {
        if(OwnList) {
            list.Insert(index, item);
        } else if(index==count && count==list.Count) {
            list.Insert(index, item);
            count = list.Count;
        } else if(index>=0 && index<=count) {
            list = list.GetRange(0, count);
            count = -1;
            list.Insert(index, item);
        } else {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
    }
    public bool Remove(object item) {
        if(!OwnList) {
            list = list.GetRange(0, count);
            count = -1;
        }
        return list.Remove(item);
    }
    public void RemoveAt(int index) {
        if(OwnList) {
            list.RemoveAt(index);
        } else if(index>=0 && index<count) {
            list = list.GetRange(0, count);
            count = -1;
            list.RemoveAt(index);
        } else {
            throw new ArgumentOutOfRangeException(nameof(index));
        }
    }

    bool IList.IsFixedSize => false;
    int IList.Add(object item) {
        Add(item);
        return Count-1;
    }
    void IList.Remove(object item) => Remove(item);
    bool ICollection.IsSynchronized => false;
    object ICollection.SyncRoot => throw new NotImplementedException();
    void ICollection.CopyTo(Array array, int index) => CopyTo((object[])array, index);
    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
    object ICloneable.Clone() => Clone();
}

public class ListWithFastAdditionWrapper {
    public static ListWithFastAdditionWrapper operator +(ListWithFastAdditionWrapper wrapper, object item) {
        if(wrapper==null) {
            throw new ArgumentNullException(nameof(wrapper));
        }
        return new ListWithFastAdditionWrapper(wrapper.list+item);
    }

    private readonly ListWithFastAddition list;

    public ListWithFastAdditionWrapper() : this(new ListWithFastAddition()) { }
    public ListWithFastAdditionWrapper(ListWithFastAddition list) {
        if(list==null) {
            throw new ArgumentNullException(nameof(list));
        }
        this.list = list;
    }

    public ListWithFastAddition List => list;
}

Here is some performance measurements (I use ListWithFastAdditionWrapper as PowerShell v5.1 do not want to use overloaded + operator for collection. Do not test on current Core version yet):

1..100 | % {
    $a = [System.Collections.Generic.List[object]]::new()
    Measure-Command {
        for($i=0; $i -lt 100000; ++$i) { $a.Add($i) }
    } | % TotalMilliseconds
} | Measure-Object -Minimum -Maximum -Average |
% { '{0}|{2}|{1}' -f $_.Minimum, $_.Maximum, $_.Average }
# 414,3723|476,15554|926,0292

1..100 | % {
    $a = [System.Collections.ObjectModel.Collection[object]]::new()
    Measure-Command {
        for($i=0; $i -lt 100000; ++$i) { $a.Add($i) }
    } | % TotalMilliseconds
} | Measure-Object -Minimum -Maximum -Average |
% { '{0}|{2}|{1}' -f $_.Minimum, $_.Maximum, $_.Average }
# 417,773|473,210506|788,7197

1..100 | % {
$a = [ListWithFastAddition]::new()
    Measure-Command {
        for($i=0; $i -lt 100000; ++$i) { $a.Add($i) }
    } | % TotalMilliseconds
} | Measure-Object -Minimum -Maximum -Average |
% { '{0}|{2}|{1}' -f $_.Minimum, $_.Maximum, $_.Average }
# 420,6408|539,701283|930,5778

1..100 | % {
$a = [ListWithFastAddition]::new()
    Measure-Command {
        for($i=0; $i -lt 100000; ++$i) { $a=[ListWithFastAddition]::op_Addition($a, $i) }
    } | % TotalMilliseconds
} | Measure-Object -Minimum -Maximum -Average |
% { '{0}|{2}|{1}' -f $_.Minimum, $_.Maximum, $_.Average }
# 487,4737|554,867155|794,9613

1..100 | % {
    $a = [ListWithFastAdditionWrapper]::new()
    Measure-Command {
        for($i=0; $i -lt 100000; ++$i) { $a+=$i }
    } | % TotalMilliseconds
} | Measure-Object -Minimum -Maximum -Average |
% { '{0}|{2}|{1}' -f $_.Minimum, $_.Maximum, $_.Average }
# 1241,2363|1317,614091|1632,8237

1..10 | % {
    $a = @()
    Measure-Command {
        for($i=0; $i -lt 100000; ++$i) { $a+=$i }
    } | % TotalMilliseconds
} | Measure-Object -Minimum -Maximum -Average |
% { '{0}|{2}|{1}' -f $_.Minimum, $_.Maximum, $_.Average }
# 891699,4145|914223,93279|955229,7854

For me that is pretty reasonable performance.

So, if PowerShell would provide its own list implementation, then calling methods would be no more advanced, than choosing different collection type to work with. In that case having += as shortcut for calling Add method would be unreasonable abuse of operators, IMO.

[mklement0]

@PetSerAl

a += b should be semantically equivalent to a = a + b.

I agree.

Operators should not visible modify theirs arguments.

That's certainly preferable; my hitherto unstated assumption was that, regrettably, in-place modification was _the only way to achieve reasonable performance_.

It sounds like you're saying that you found a way to achieve reasonable performance even _without_ in-place modification.

I can confirm that your code achieves a very impressive speed-up compared to the current use of += with arrays (by a factor of _hundreds_).

• I haven't analyzed your code yet; can you summarize succinctly how you achieved that?

• If there are no gotchas, your solution definitely has my vote:

  • Why shouldn't we try it in PowerShell Core yet?

  • What would it take to make [ListWithFastAdditionWrapper] unnecessary so that += can be used directly with [ListWithFastAddition]? Given the wrapper's performance impact (a factor of about 3, though arguably still negligible compared to current += performance), would that go away?

[PetSerAl]

@mklement0

I haven't analyzed your code yet; can you summarize succinctly how you achieved that?

Basically it use shared list internally, but remembers how much items from shared list it owns.

Why shouldn't we try it in PowerShell Core yet?

Sorry my bad English. I mean I did not test it in Core yet.

What would it take to make [ListWithFastAdditionWrapper] unnecessary so that += can be used directly with [ListWithFastAddition]? Given the wrapper's performance impact (a factor of about 3, though arguably still negligible compared to current += performance), would that go away?

PowerShell should pick up overloaded + operation for collections, then using wrapper would be unnecessary. Although, my measurements shows that 3x performance impact caused by +=, but not by wrapper. If you call [ListWithFastAdditionWrapper]::op_Addition directly rather then +=, then it is as fast as [ListWithFastAddition]::op_Addition.

Updated version of ListWithFastAddition.

[mklement0]

@SteveL-MSFT:

Unless someone sees a (fundamental) flaw in @PetSerAl's implementation, can I suggest we revisit this issue based on the following proposal?

• make _this_ issue just about preserving the LHS collection _type_ - _without_ in-place extending

• make @PetSerAl's list implementation the basis for the PowerShell-native list implementation proposed in #5643

[iSazonov]

@mklement0 Could you please make a Pester test prototype for first point?

[SteveL-MSFT]

cc @BrucePay

[mklement0]

@iSazonov: I think I'd rather hold off until we have consensus on the way forward.

[Jaykul]

This:

PowerShell should pick up overloaded + operation for collections, then using wrapper would be unnecessary