Skip to content
This repository was archived by the owner on Jan 23, 2023. It is now read-only.

Copy directly to the internal buffer in List.InsertRange#6892

Merged
vancem merged 1 commit intodotnet:masterfrom
jamesqo:list-optimizations
Sep 14, 2016
Merged

Copy directly to the internal buffer in List.InsertRange#6892
vancem merged 1 commit intodotnet:masterfrom
jamesqo:list-optimizations

Conversation

@jamesqo
Copy link

@jamesqo jamesqo commented Aug 24, 2016

List.InsertRange currently allocates an intermediary array to copy the items into, then copies it into the List's buffer. This changes it to copy directly into the List's buffer.

I realize that this was probably intentionally done in case a bad ICollection implementation held on to the array in CopyTo. However, List is already mutable as-is, so the only thing this would let such an implementation do is modify the array's contents without changing _version.

@jkotas Do you think this is a change worth making? I understand it could cause problems with such a faulty implementation, but for other collections (esp. large ones) it seems worth it.

also cc'ing: @omariom @mikedn

@omariom
Copy link

omariom commented Aug 24, 2016

Never thought about such approach of getting access to the internal array :)

@jkotas
Copy link
Member

jkotas commented Aug 24, 2016

@jkotas Do you think this is a change worth making

I do not think so. There are other subtle behavior changes in addition to the one you have mentioned.

@jamesqo
Copy link
Author

jamesqo commented Aug 24, 2016

@jkotas

There are other subtle behavior changes in addition to the one you have mentioned.

Out of curiosity, what are they?

If this is not going to be accepted as-is, perhaps I can detect whether a new buffer was allocated, then use the old buffer as an intermediary the ICollection can copy to, then copy that again to the new one.

@jkotas
Copy link
Member

jkotas commented Aug 24, 2016

Out of curiosity, what are they?

E,g, CopyTo method can be indirectly accessing the list that the items are copied into.

I do not think it is worth it to change anything here. These are slow rarely used convenience methods.

@jamesqo
Copy link
Author

jamesqo commented Aug 24, 2016

@jkotas Ok, then.

@jamesqo jamesqo closed this Aug 24, 2016
@jamesqo jamesqo deleted the list-optimizations branch August 24, 2016 17:33
@jamesqo
Copy link
Author

jamesqo commented Sep 6, 2016

@jkotas TBH, I disagree with your opinion that this is a "rarely used convenience method." InsertRange is called by AddRange since it just inserts into the last index. And AddRange is definitely used in a couple of places throughout LINQ, for example here and here (maybe more places in the future). This means that for code like

collection.Concat(enumerable).ToList();

There will be a duplicate copy of collection since it is AddRange'd to the list, and enumerable as well if it is also an ICollection.

I think it would be worth optimizing this at least if we can fit the collection into the old buffer, and then use that as an intermediary to copy.

@jamesqo
Copy link
Author

jamesqo commented Sep 6, 2016

Also a sidenote: the List constructor directly copies to _items.

@jkotas
Copy link
Member

jkotas commented Sep 6, 2016

The constructor case is a bit different because of the same caller owns both the construction and the enumerable.

I have looked at the history: The extra copy was not in the List<T> code when it was written originally. It was added to fix a bug filled by @KrzysztofCwalina in early 2005. It was discussed whether the same copy has to be done in the constructor as well at that time, and it was found unnecessary.

@jamesqo jamesqo restored the list-optimizations branch September 13, 2016 21:38
@jamesqo jamesqo deleted the list-optimizations branch September 13, 2016 21:38
@jamesqo jamesqo restored the list-optimizations branch September 13, 2016 21:38
@jamesqo jamesqo reopened this Sep 13, 2016
@jamesqo jamesqo closed this Sep 13, 2016
@jamesqo jamesqo reopened this Sep 14, 2016
@jamesqo
Copy link
Author

jamesqo commented Sep 14, 2016

Reopening as per the decision in #7161. 🎉

@vancem
Copy link

vancem commented Sep 14, 2016

LGTM

@vancem vancem merged commit abfc08f into dotnet:master Sep 14, 2016
@jamesqo jamesqo deleted the list-optimizations branch September 15, 2016 00:29
@jkotas
Copy link
Member

jkotas commented Sep 15, 2016

@jamesqo Could you please port the change to CoreRT List as well (it lives in corefx)?

Sign up for free to subscribe to this conversation on GitHub. Already have an account? Sign in.

Labels

None yet

Projects

None yet

Development

Successfully merging this pull request may close these issues.

5 participants