Runtime: Add Move method to List<T>

[danmosemsft]

Rationale

There are plenty of convenience methods in generic List. But no Move method that can efficiently move an item from one position to another.
What we have to do is RemoveAt and Insert. It means two copies of big chunks of memory instead of one. The worst case is when both from and to are close to each other and to the beginning of a large list. What could be done with one copy of a few items becomes two copies of almost the whole list.

The alternative is saving a copy of the value you want moved and then correctly copying items manually in a for loop with the indexer and finally setting the value you saved to the desired index. This can be tricky as it involves having to consider both when the from index is greater and less than the to index.

Proposed API

 namespace System.Collections.Generic {
     public class List<T> {
+        public void Move(int fromIndex, int toIndex);
+        public void MoveRange(int fromIndex, int toIndex, int count);
     }
     public static class CollectionExtensions {
+        public void Move<T>(this IList<T> list, int fromIndex, int toIndex);
+        public void MoveRange<T>(this IList<T> list, int fromIndex, int toIndex, int count);
     }
 }
 namespace System {
     public abstract class Array {
+        public static void Move(Array array, int fromIndex, int toIndex);
+        public static void MoveRange(Array array, int fromIndex, int toIndex, int count);
     }
 }

API Details

• The CollectionExtensions methods will downcast if possible, otherwise will use the indexer to move items.
• MoveRange was chosen as it better mirrors existing range like methods.

Historical Discussion

@omariom commented on Sun Jun 21 2015

There are plenty of convenience methods in generic List. But no Move method that can efficiently move an item from one position to another.
What we have to do is RemoveAt and Insert. It means two copies of big chunks of memory instead of one. The worst case is when both from and to are close to each other and to the beginning of a large list. What could be done with one copy of a few items becomes two copies of almost the whole list.
In my implementation of ObservableCollection.MoveItem I had to get the underlying List, retrieve via reflection :see_no_evil: its array and do the work myself.

So.. I propose adding new Move method to generic List with the following signature:

``` C#
public void Move(int oldIndex, int newIndex);

@omariom commented on [Sun Jun 21 2015](https://github.com/dotnet/coreclr/issues/1165#issuecomment-113963719)

cc: @KrzysztofCwalina 


---

@OtherCrashOverride commented on [Sun Jun 21 2015](https://github.com/dotnet/coreclr/issues/1165#issuecomment-113967256)

Isn't this what LinkedList is for?


---

@omariom commented on [Mon Jun 22 2015](https://github.com/dotnet/coreclr/issues/1165#issuecomment-114040328)

LinkedList is quite different in its capabilities. Its elements can't be accessed by position, its layout is not cache friendly etc.


---

@hadibrais commented on [Mon Jun 22 2015](https://github.com/dotnet/coreclr/issues/1165#issuecomment-114066363)

While such method can be added to the generic list and is really useful, it cannot be utilized from the existing **ObservableCollection.Move** method you referenced. That's because three state changes have to be reported: **NotifyCollectionChangedAction.Remove**, **NotifyCollectionChangedAction.Add** and **NotifyCollectionChangedAction.Move**. Also the intermediate states have to be captured and made available to any listeners. Regardless, such efficient method is really useful and should be offered by the generic List. It's also easy to implement.


---

@omariom commented on [Mon Jun 22 2015](https://github.com/dotnet/coreclr/issues/1165#issuecomment-114071250)

I mentioned ObservableCollection.MoveItem just as an example where such method could be used.
Actually there are other cases where Move could be beneficial.

> That's because three state changes have to be reported: NotifyCollectionChangedAction.Remove, NotifyCollectionChangedAction.Add and NotifyCollectionChangedAction.Move.

Collection<T> (which is the base class) doesn't report any actions. So  nothing changes in terms of reporting.


---

@OtherCrashOverride commented on [Mon Jun 22 2015](https://github.com/dotnet/coreclr/issues/1165#issuecomment-114083702)

List is not intended for performance with random inserts and deletes.  Adding 'move' would just encourage improper use of the class.  Move is a heavy weight function when type of List<T> is a struct/valuetype.

If there is a language where there is a precedence of having Move on a List it would be worth examining.  Neither C++ std::vector nor Java 8 have any such notion.

> In my implementation of ObservableCollection.MoveItem I had to get the underlying List, retrieve via reflection its array and do the work myself. 

It would also be helpful to post the code somewhere as an example of what is wanted.


---

@omariom commented on [Mon Jun 22 2015](https://github.com/dotnet/coreclr/issues/1165#issuecomment-114095876)

@OtherCrashOverride 
Something like this:

``` C#
public void Move(int oldIndex, int newIndex)
{
    if ((uint)oldIndex >= (uint)_size)
    {
        ThrowArgumentOutOfRange("oldIndex");
    }

    if ((uint)newIndex >= (uint)_size)
    {
        ThrowArgumentOutOfRange("newIndex");
    }

    if (newIndex == oldIndex)
        return;

    T item = _items[oldIndex];

    if (newIndex < oldIndex)
    {
        Array.Copy(_items, newIndex, _items, newIndex + 1, oldIndex - newIndex);
    }
    else
    {
        Array.Copy(_items, oldIndex + 1, _items, oldIndex, newIndex - oldIndex);
    }

    _items[newIndex] = item ;
    _version++;
}

---

@omariom commented on Sat Jul 02 2016

List is not intended for performance with random inserts and deletes.

Yes, but we already have RemoveAt and Insert methods which allow random inserts and deletes. And they are actually used to implement move semantics.

---

@OtherCrashOverride commented on Mon Jun 22 2015

I would suggesting creating a pull request with the code and some tests. You should also include code to benchmark performance with Move versus RemoveAt / Insert.

---

@masonwheeler commented on Fri Jun 26 2015

@OtherCrashOverride The performance benefits are obvious when you think about worst cases. For example, imagine a list with a few thousand items in it, and the operation you want to perform is Move(10, 20);

With RemoveAt and Insert, you end up having to shift (essentially) all items in the list... twice. With the proposed Move method, you would have to shift 9 items once.

---

@OtherCrashOverride commented on Fri Jun 26 2015

The performance benefits are obvious when you think about worst cases.

We really need to see benchmarks before we start speculating. In theory, it should be faster. The reality will come down to what the runtime does behind the scenes.

For most cases LinkedList is probably a better choice. The use case for this is where you require the data to be sequential in memory. A specific example is when dealing with a GPU. Vertex data is typically very large structs packed into an array. It is also not uncommon to manipulate the data elements in real time. This proposal may benefit that specific scenario. We still require a benchmark to validate the claim.

---

@KrzysztofCwalina commented on Fri Jun 26 2015

I think some kind of "move" API is worth exploring. But I think it would be great if somebody thought about a more general API than simple "move one items from here to there". For example, what if I want to move a slice/range? what if I want to swap two ranges? What if I want to round robin move three items? BTW, I am not proposing that we actually implement all these, often corner case, scenarios, but it would be good to have a good overview of the "move" scenarios and chose to implement the ones that are common and where we can get good performance improvement while preserving simplicity.

---

@OtherCrashOverride commented on Fri Jun 26 2015

Upon further reflection, there is an issue here in that you can not actually get at the sequential data (for p/invoke) without exposing the internal array. With that in mind, maybe 'Move' should be proposed for 'Array'. List could then make use of that functionality without breaking encapsulation as exposing the internal array storage would do.

Alternatively, a new ArrayList (or some other name) class could be introduced that guarantees array storage and exposes the internals. This, however, seems less than ideal.

https://msdn.microsoft.com/en-us/library/system.collections.arraylist%28v=vs.110%29.aspx

---

@AdamSpeight2008 commented on Sat Jun 27 2015

Why not just swap the contents?

``` c#
public void Swap( this T a, T )
{
T tmp = a;
a = b;
b = a;
}

@masonwheeler commented on [Sat Jun 27 2015](https://github.com/dotnet/coreclr/issues/1165#issuecomment-116132546)

@AdamSpeight2008 Because that would only be a valid equivalent if the new index was adjacent to the old index.

Let's say we have a lit of ints, like so:

`0, 1, 2, 3, 4, 5, 6, 7, 8, 9`

Swapping 1 and 5 would result in

`0, 5, 2, 3, 4, 1, 6, 7, 8, 9`

whereas executing the hypothetical `Move(1, 5)` would result in:

`0, 2, 3, 4, 1, 5, 6, 7, 8, 9`

As you can see, they're completely different operations.


---

@AdamSpeight2008 commented on [Sat Jun 27 2015](https://github.com/dotnet/coreclr/issues/1165#issuecomment-116137212)

@masonwheeler  
Should the result of `Move( 1, 5)` be `0, 2, 3, 4, 5, 1, 6, 7, 8, 9`

What should the resulf of `Move( 5, 1)` ? then same?
Or `Move( 1, 1 )`


---

@AdamSpeight2008 commented on [Sat Jun 27 2015](https://github.com/dotnet/coreclr/issues/1165#issuecomment-116149465)

The following extension methods implement the `Move`functionality.

``` vb
Public Module Exts

    <Runtime.CompilerServices.Extension>
    Public Function Move(Of T)(xs As IEnumerable(Of T), ox As Integer, nx As Integer) As IEnumerable(Of T)
        Return _Move(xs, ox, nx)
    End Function

    Private Iterator Function _Move(Of T)(xs As IEnumerable(Of T), ox As Integer, nx As Integer) As IEnumerable(Of T)
        Dim oxd = xs.ElementAt(ox)
        Dim ix = 0
        Dim en = xs.GetEnumerator
        While en.MoveNext
            If ix = ox Then
            ElseIf ix = nx Then
                If ox < nx Then

                Yield en.Current
                Yield oxd
                    Else
                    Yield oxd
                    Yield en.Current
                End If
            Else
                Yield en.Current
            End If
            ix += 1
        End While
    End Function
End Module

---

@AdamSpeight2008 commented on Sat Jun 27 2015

Move( 1, 5). Move( 5, 1) should really result in the original list.

---

@omariom commented on Mon Jun 29 2015

@KrzysztofCwalina,

I think two the most practical overloads at the moment are these:

C# public void Move(oldIndex, newIndex); public void Move(sourceIndex, length, destinationIndex);

Or, as an alternative, List could have Copy method with the same semantics as Array.Copy method. Then everyone could implement whatever he needs: moves, shifts, etc.

---

@omariom commented on Fri Sep 25 2015

This is what I have to do.. :scream_cat:

---

@omariom commented on Sat Jul 02 2016

@KrzysztofCwalina
Now that .NET Core 1.0 is out can we change the milestone of the issue from Future to Present? )

---

@KrzysztofCwalina commented on Tue Jul 05 2016

@terrajobst, @weshaggard, are you guys going to triage "future" issues?

---

@danmosemsft commented on Thu Dec 08 2016

API request - moving to CoreFX.

[jnm2]

Both overloads would be welcome.

[AlexRadch]

Is it correct ?

public void Move<T>( int from, int to)
{
T tmp = this[from];
if (to >=from)
  Copy(from+1, from, to-from);
else
  Copy(to, to+1, from-to);
this[to] = tmp;
} 

[AlexRadch]

I sagest implement RotateLeft(from, lenght, shiftCount) then Move will be RotateLeft(from, to-from+1, 1)

[danmosemsft]

@Priya91, @ianhays can you evaluate and give feedback?

[jnm2]

I prefer Move over Rotate. It's more 1:1 with my needs and frame of mind.

[ianhays]

I prefer Move over Rotate. It's more 1:1 with my needs and frame of mind.

Agreed on Move over Rotate.

I think two the most practical overloads at the moment are these:

public void Move(oldIndex, newIndex);
public void Move(sourceIndex, length, destinationIndex);

I like public void Move(oldIndex, newIndex); and think it provides good utility.

I like public void Move(sourceIndex, length, destinationIndex); less, but it seems fine. It doesn't seem nearly as useful as the single element Move, but if the demand is there then I could get behind it.

[ianhays]

Next step here is to submit a formal API proposal and once we nail down the API we can submit it to API review.

[TylerBrinkley]

Rationale

There are plenty of convenience methods in generic List. But no Move method that can efficiently move an item from one position to another.
What we have to do is RemoveAt and Insert. It means two copies of big chunks of memory instead of one. The worst case is when both from and to are close to each other and to the beginning of a large list. What could be done with one copy of a few items becomes two copies of almost the whole list.

The alternative is saving a copy of the value you want moved and then correctly copying items manually in a for loop with the indexer and finally setting the value you saved to the desired index. This can be tricky as it involves having to consider both when the from index is greater and less than the to index.

Proposed API

 namespace System.Collections.Generic {
     public class List<T> {
+        public void Move(int fromIndex, int toIndex);
+        public void MoveRange(int fromIndex, int toIndex, int count);
     }
     public static class CollectionExtensions {
+        public void Move<T>(this IList<T> list, int fromIndex, int toIndex);
+        public void MoveRange<T>(this IList<T> list, int fromIndex, int toIndex, int count);
     }
 }
 namespace System {
     public abstract class Array {
+        public static void Move(Array array, int fromIndex, int toIndex);
+        public static void MoveRange(Array array, int fromIndex, int toIndex, int count);
     }
 }

API Details

• The CollectionExtensions methods will downcast if possible, otherwise will use the indexer to move items. This method will not work for collections that ensures item uniqueness such as an OrderedSet.
• MoveRange was chosen as it better mirrors existing range like methods.

Open Questions

• Should the Move method's parameters be named oldIndex and newIndex as ObservableCollection has them named? fromIndex and toIndex were used as they make more sense in the MoveRange methods.

[danmosemsft]

@ianhays @safern for feedback.

I have a slight vote for oldIndex newIndex (or else fromIndex toIndex) since we use index heavily elsewhere, and it is more immediately obvious that we aren't somehow moving to another collection, but another location.

[AlexRadch]

Maybe Shift(int index, int length, ind count) ?

[danmosemsft]

On Array there is precedent for sourceIndex destinationIndex

        public static void ConstrainedCopy(System.Array sourceArray, int sourceIndex, System.Array destinationArray, int destinationIndex, int length) { }
        public static void Copy(System.Array sourceArray, int sourceIndex, System.Array destinationArray, int destinationIndex, int length) { }
        public static void Copy(System.Array sourceArray, long sourceIndex, System.Array destinationArray, long destinationIndex, long length) { }

as well as plenty of startIndex. I guess API review board can decide.

[safern]

Proposal looks good to me and both methods seem reasonable to be added. I think Move and MoveRange would be the appropriate naming to transmit what the API is doing. Shift is different, since Shift to me means, pushing the precedent elements starting from index rather than just moving the element in that index.

I just moved the API Proposal into the issue description and marking as API ready to review. Thanks @TylerBrinkley for putting it together.

[ianhays]

or else fromIndex toIndex

+1 for fromIndex and toIndex. from and to aren't quite descriptive enough.

Proposal looks good, just need to argue about naming :)

[TylerBrinkley]

Another thing to consider is the placement of the count parameter. Should it be in between the two index parameters or at the end like how Array.Copy has the length parameter? Note, the name count was chosen as it mirrors the choice in List.RemoveRange.

[safern]

Another thing to consider is the placement of the count parameter.

I think we should place it at the end like Array.Copy to me it is better to first specify the indexes and at the end the count, it is kind of confusing to have (fromIndex, count, toIndex) if you read a caller without knowing the signature could be confusing. So I would follow the same patterns we already do.

[TylerBrinkley]

I'd be in favor of changing the proposal as @safern suggests, renaming the from and to parameters to fromIndex and toIndex respectively and to move the count parameter to the end of the parameter list.

[safern]

Just updated the proposal in the issue description to have that parameter naming and ordering.

[terrajobst]

It's unclear what the scenario for these APIs are.

@omariom, you said earlier:

This is what I have to do.. 🙀

that involves private reflection over (I think) List<T>. It's unclear what you're trying to achieve.

Alternatively to these APIs, we could expose a method like ​list.Mutate(Span<T> span => /* have fun /*) or ​list.Read(ReadOnlySpan<T> span => /* have fun /*) .

[omariom]

It's unclear what the scenario for these APIs are.

I needed to move large number of items within the list, to more efficiently implement ObservableCollection.MoveItem.

Alternatively to these APIs, we could expose a method like ​list.Mutate(Span span => /* have fun /) or ​list.Read(ReadOnlySpan span => / have fun /*) ..

That would be even better 👍

[TylerBrinkley]

It's unclear what the scenario for these APIs are.

I've had to support this scenario when re-ordering an existing collection of objects to match an updated version of that collection. I could not just swap out collections because users were potentially subscribed to the objects' PropertyChanged event and did not want to lose object identity so I just populate those objects that are matched by an Id property with the updated version of the object.

Alternatively to these APIs, we could expose a method like ​list.Mutate(Span span => /* have fun /) or ​list.Read(ReadOnlySpan span => / have fun /*) .

I like that idea but I think we should also explicitly support at least just the Move API. It wasn't only for performance that this API is proposed but also for correctness which is why there are Array methods as well.

[terrajobst]

@omariom

How large is your collection? Do you have perf numbers that show how much this API would reduce this overhead? I've to be honest, this sounds like a fringe scenario for me. I get it for arrays, but List less, and general interfaces even less so.

[omariom]

How large is your collection?

Hmm.. It was about 70 thousand. Unusual number for ObservableCollection but rewriting to arrays wasn't an option. My initial proposal was List<T>.Move, then List<T>.Copy.