Better bulk adds for List. by jamesqo · Pull Request #8306 · dotnet/coreclr

jamesqo · 2016-11-25T02:10:05Z

This PR optimizes the List(IEnumerable<T>) .ctor and AddRange method for lazy enumerables.

For the constructor, we were previously looping through the sequence and calling Add on each item. This is not very efficient since Add is not inlined. Instead, we can have a tighter loop where we essentially write Add inline and only update fields when we run out of space.
For InsertRange, we check if we are adding at the end of the list first. This is a common case, since AddRange just forwards to InsertRange. If we are, then we call AddEnumerable instead of Insert in a loop.

I ran tests on corefx's System.Collections and everything passes.

Note: I can't test the perf impact these changes have at the moment because of #8266. If/when I am able to, however, I will update this PR.

cc @stephentoub @jkotas

Related: dotnet/corefx#13942 (comment)

jamesqo · 2016-11-25T02:13:38Z

cc @vancem

jamesqo · 2016-11-25T18:31:13Z

@jkotas @stephentoub I managed to workaround the issue I was having. Here are the performance results I got: https://gist.github.com/jamesqo/5ac880d3e46d719c99ec388128ac50a6 Test code: https://github.com/jamesqo/Dotnet/blob/57417b93ed0290444b461b8e7dea2082b441b149/Program.cs#L49

They are not universal, but there is generally about a 10% improvement. I think all of the allocations involved may be dominating the results, and that's why the results are not always consistent.

justinvp · 2016-11-26T00:19:10Z

Won't this introduce a behavior change?

Consider an enumerator that reads lines from a file or from the network that may throw from MoveNext().

Or a contrived example:

public static IEnumerable<int> GetItems()
{
    yield return 1;
    yield return 2;
    yield return 3;
    yield return 4;
    throw new Exception();
}

Before this change, each item successfully enumerated before MoveNext() throws will be added to the list and _size will reflect the number of items successfully added.

After this change, those initial items will be inserted in the array, but then MoveNext() throws, so _size won't be updated to reflect the items that were successfully inserted.

jamesqo · 2016-11-26T15:03:56Z

@jkotas Sorry, can you please review when you have time? Thanks.

jkotas · 2016-11-26T15:21:36Z

@jamesqo I am leaving tweaks of convenience methods like this one to area maintainers to deal with.

@Priya91 @ianhays PTLA

stephentoub · 2016-11-27T02:36:56Z

src/mscorlib/src/System/Collections/Generic/List.cs

+                {
+                    // Make a final update to _size and _version after we've finished adding.
+                    _size = size;
+                    _version++;


These attempted optimizations around _size, _items, _version, etc. break code like:

var list = new List<int>(); list.AddRange(Enumerable.Range(0, 5).Select(i => { list.Add(i); return i; }));

@stephentoub Interesting. I don't think it's going to be very common to modify the list in a selector, but seeing it in an invalid state/having items overwritten is pushing it.

I can remove the optimizations around _size, and write to _version before we do any copying. AFAICS caching _items is harmless though, because the field is always up-to-date, it's just the local variable we're updating.

AFAICS caching _items is harmless though

How so? If the iterator adds an element that causes the list to grow, or otherwise increases its capacity, _items will end up pointing to a different array than items points to, and AddRange will start storing the values into a garbage array.

@stephentoub EnsureCapacity always updates _items, and we always update the local variable via items = _items after that. Unless an exception of some sort is thrown between those lines, in which case we stop copying anyways, the two are always equal.

EnsureCapacity always updates _items, and we always update the local variable via items = _items after that

But those lines aren't relevant to the case I'm talking about. If the call to MoveNext increases the capacity of the list, items will now be different from _items, we won't enter that if block (as we will already have enough capacity since it was just resized), and we'll store the items into the wrong array.

@stephentoub Add is not inlined. That is why the numbers show improvements.

cc @AndyAyersMS

Manual inlining is double edged sword. You can get a small improvement in a lot of places by manually inlining and always show there is a performance improvement in microbenchmark. However if you have done manual inlining enough times, the real world workloads would likely get slower because of the code size increase from manual inlining would overwhelm the benefits.

We may want to be more data driven for manual inlining - only do it if there is real-world workload where it makes a dent, and leave profile guided optimizations to take care of the rest.

However if you have done manual inlining enough times, the real world workloads would likely get slower because of the code size increase from manual inlining would overwhelm the benefits.

I think it makes sense in this case. This in a loop and it's part of the bottleneck. It's also frequently used (directly, or indirectly by Linq).

We may want to be more data driven for manual inlining - only do it if there is real-world workload where it makes a dent,

It just came up in corefx in a frequently-used method. See the PR I linked to: dotnet/corefx#13942 (comment)

Ok, looks reasonable in this case.

BTW: I have checked traces from full .NET Framework, collected on mix of real world workloads (ASP.NET, WFP, WinForms, ...), for the List constructor that you are changing:

~8500 out of 11200 samples is called on empty ICollection

~2600 out of 11200 samples is called on non-empty ICollection

~100 out of 11200 samples is the rest (IEnumerable that is not ICollection), the average length is 9

This data suggests that the most impactful part of this change on real world workloads is not what you think it is. The path that you are changing is not executed that frequently. However, since you are moving the enumerator out into separate method, the prolog/epilog of the frequently hit path gets tighter and it is where the most improvement for the real world workloads will likely come from.

@jamesqo Did you happen look into why Add is not getting inlined? It would be worth understanding that since at least from source it looks small enough that it should have been considered.

Also would be nice to see before/after disassembly in case the jit is just missing out on some obvious optimization.

jamesqo · 2016-11-29T02:44:22Z

Test OSX x64 Checked Build and Test

justinvp · 2016-12-01T03:29:34Z

src/mscorlib/src/System/Collections/Generic/List.cs

+
+            using (IEnumerator<T> en = enumerable.GetEnumerator())
+            {
+                _version++; // Even if the enumerable has no items, we can update _version.


InsertRange already increments _version. Can we remove the increment here?

The other caller of this method is the .ctor, which shouldn't need the _version increment.

@justinvp It is just in case if this is called by another method later on, or e.g. the increment to _version is accidentally removed in InsertRange. It is just one write anyway, so I don't think it should cost much relative to all the other stuff going on in the method.

jamesqo · 2016-12-03T01:34:41Z

@ianhays, @Priya91, @stephentoub Sorry, do you think you could merge these changes when you have time? Thanks.

edit: Also, @vancem

Better bulk adds for List. Commit migrated from dotnet/coreclr@78d2ea0

…clr#20471) Commit migrated from dotnet/coreclr@4b98caf

Better bulk adds for List.

27dfc25

dnfclas added the cla-already-signed label Nov 25, 2016

jamesqo added 2 commits November 25, 2016 21:10

Handle exceptions from MoveNext and Current.

d000206

Fix typo.

8f69673

jkotas assigned Priya91 and ianhays Nov 26, 2016

stephentoub reviewed Nov 27, 2016

View reviewed changes

jamesqo added 3 commits November 27, 2016 12:35

Revert some potentially breaking aspects

a2a8951

Move the write to _version before the copy.

c39ff48

Do not cache _items.

9dd876f

jkotas approved these changes Dec 1, 2016

View reviewed changes

justinvp reviewed Dec 1, 2016

View reviewed changes

ianhays approved these changes Dec 5, 2016

View reviewed changes

ianhays merged commit 78d2ea0 into dotnet:master Dec 5, 2016

jamesqo deleted the better-bulk-add branch December 5, 2016 22:02

jamesqo mentioned this pull request Dec 5, 2016

Specialize the single-selector overload of SelectMany. dotnet/corefx#13942

Merged

karelz modified the milestone: 2.0.0 Aug 28, 2017

stephentoub added a commit to stephentoub/coreclr that referenced this pull request Oct 18, 2018

Revert List.InsertRange changes from dotnet#8306

70c1de4

stephentoub added a commit to stephentoub/coreclr that referenced this pull request Oct 18, 2018

Revert List.InsertRange changes from dotnet#8306

6b66c20

jkotas pushed a commit that referenced this pull request Oct 18, 2018

Revert List.InsertRange changes from #8306 (#20471)

4b98caf

A-And pushed a commit to A-And/coreclr that referenced this pull request Nov 20, 2018

Revert List.InsertRange changes from dotnet#8306 (dotnet#20471)

a796df1

jamesqo mentioned this pull request Jan 31, 2020

Improve test coverage for List..ctor(IEnumerable<T>) and AddRange dotnet/runtime#19476

Closed

jkotas mentioned this pull request Mar 7, 2020

Creating a list from an IEnumerable<T> is inefficient dotnet/runtime#33339

Closed

picenka21 pushed a commit to picenka21/runtime that referenced this pull request Feb 18, 2022

Merge pull request dotnet/coreclr#8306 from jamesqo/better-bulk-add

f40fcb0

Better bulk adds for List. Commit migrated from dotnet/coreclr@78d2ea0

picenka21 pushed a commit to picenka21/runtime that referenced this pull request Feb 18, 2022

Revert List.InsertRange changes from dotnet/coreclr#8306 (dotnet/core…

e24c28d

…clr#20471) Commit migrated from dotnet/coreclr@4b98caf

Conversation

jamesqo commented Nov 25, 2016

Uh oh!

jamesqo commented Nov 25, 2016

Uh oh!

jamesqo commented Nov 25, 2016

Uh oh!

justinvp commented Nov 26, 2016

Uh oh!

jamesqo commented Nov 26, 2016

Uh oh!

jkotas commented Nov 26, 2016

Uh oh!

Choose a reason for hiding this comment

Uh oh!

jamesqo Nov 27, 2016 • 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!

stephentoub Nov 27, 2016 • 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!

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!

jkotas Nov 29, 2016 • 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!

Choose a reason for hiding this comment

Uh oh!

jamesqo commented Nov 29, 2016

Uh oh!

justinvp Dec 1, 2016 • 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!

Choose a reason for hiding this comment

Uh oh!

jamesqo commented Dec 3, 2016 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

9 participants

jamesqo Nov 27, 2016 •

edited

Loading

stephentoub Nov 27, 2016 •

edited

Loading

jkotas Nov 29, 2016 •

edited

Loading

justinvp Dec 1, 2016 •

edited

Loading

jamesqo commented Dec 3, 2016 •

edited

Loading