[CSHARP-257] Performance of a BsonArray creation and AddRange method when "values" is either T[], IList<T> or an ICollection Created: 24/Jun/11 Updated: 02/Apr/15 Resolved: 21/Jul/11 |
|
| Status: | Closed |
| Project: | C# Driver |
| Component/s: | None |
| Affects Version/s: | None |
| Fix Version/s: | 1.2 |
| Type: | Improvement | Priority: | Minor - P4 |
| Reporter: | Aristarkh Zagorodnikov | Assignee: | Robert Stam |
| Resolution: | Done | Votes: | 0 |
| Labels: | None | ||
| Remaining Estimate: | Not Specified | ||
| Time Spent: | Not Specified | ||
| Original Estimate: | Not Specified | ||
| Attachments: |
|
| Backwards Compatibility: | Fully Compatible |
| Description |
|
While profiling one of our applications, I encountered that BsonArray implementation was relatively suboptimal when it's initialized with a medium-large sized (100-1000 elements) arrays. So, I created a patch which supports reserving space in internal values array if the amount of elements is known beforehand (if IEnumerable<T> is also an ICollection), along with some iteration improvements for arrays and IList<T> implementations. In my test case this leads to around 40-50% improvement on array creation. I also applied the same improvements to relevant methods (Clone, DeepClone). While I recognized that attached patch is largely untested, I ask you to consider if these improvements are worth including, and either include the changes I propose, or invent some other scheme to improve the T[]->BsonArray conversion process. |
| Comments |
| Comment by Aristarkh Zagorodnikov [ 12/Jul/11 ] |
|
I think that current implementation (Capacity constructor and property) is sufficiently good for most of the cases. If you need my opinion, I believe the issue can be closed. |
| Comment by Aristarkh Zagorodnikov [ 12/Jul/11 ] |
|
Yes, while there are additional performance improvements for creation from an array of items, I think it's too much for the driver. I will keep this patch for our internal use (we maintain a set of patches for middleware we use), I just thought I should share this one even if it's not accepted, for future reference. |
| Comment by Robert Stam [ 12/Jul/11 ] |
|
Ouch. I think that's too many overloads... And I think it still won't be any faster than: var array = new BsonArray(capacity); although this two line version does require the caller to write an extra line of code. I don't think I want to complicate BsonArray this way. |
| Comment by Aristarkh Zagorodnikov [ 12/Jul/11 ] |
|
Latest version of the patch, common cases (T[], List<T>) are always faster, uncommon (pure IEnumerable<T>, such as LINQ results) are a little bit slower (this can be fixed by reverting the AddRange(IEnumerable<T>)). I didn't add tests since I think this patch still needs evaluation. |
| Comment by Robert Stam [ 09/Jul/11 ] |
|
Excellent suggestion. I've gone ahead and added the Capacity property. |
| Comment by Aristarkh Zagorodnikov [ 09/Jul/11 ] |
|
Yes, I agree that this would work, but I ask you to add the Capacity property along with the constructor, to allow for more efficient appending too. |
| Comment by Robert Stam [ 09/Jul/11 ] |
|
I can apparently get the same (or better) performance improvements by only adding a new constructor that lets you specify the initial capacity and replacing: var array = new BsonArray(values); with var array = new BsonArray(capacity); in the client code. The best thing about this simpler approach is that it is faster for all sizes of the values enumerable. It does mean that the caller has to make a small code change if they want to squeak that last bit of performance out of creating new BsonArrays, but it's a much safer approach because it doesn't slow down the most common cases of small BsonArrays (0 to 4 elements). The caller can also guess at an initial capacity even if the values enumerable can't provide a count. |
| Comment by Aristarkh Zagorodnikov [ 09/Jul/11 ] |
|
Thank you for looking at this. I'll unshelve my tests and post the code and the results here. Maybe there was an error in my measurements. |
| Comment by Robert Stam [ 08/Jul/11 ] |
|
I'm experimenting with this and benchmarking and I get slower results with the new code when the number of values passed in is 4 or less. After that I start seeing improved performance. Will keep looking at it to see if there's a way to not slow down the simple cases. |
| Comment by Aristarkh Zagorodnikov [ 25/Jun/11 ] |
|
Actually, added optimizations (except Clone() and DeepClone()) are similar to ones that exist in the BCL List<T>, but are a bit more different, because the internal container is not a simple array, but a List<T> itself. ICollection<T> is2 = collection as ICollection<T>; if (is2 != null) { int count = is2.Count; this._items = new T[count]; is2.CopyTo(this._items, 0); this._size = count; } else { this._size = 0; this._items = new T[4]; using (IEnumerator<T> enumerator = collection.GetEnumerator()) { while (enumerator.MoveNext()) { this.Add(enumerator.Current); } } } } (this one is called from AddRange) public void InsertRange(int index, IEnumerable<T> collection) { if (collection == null) { ThrowHelper.ThrowArgumentNullException(ExceptionArgument.collection); } if (index > this._size) { ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_Index); } ICollection<T> is2 = collection as ICollection<T>; if (this == is2) { Array.Copy(this._items, 0, this._items, index, index); Array.Copy(this._items, (int) (index + count), this._items, (int) (index * 2), (int) (this._size - index)); }else { T[] array = new T[count]; is2.CopyTo(array, 0); array.CopyTo(this._items, index); } this._size += count; } |
| Comment by Aristarkh Zagorodnikov [ 24/Jun/11 ] |
|
I would also like to note that if the constructor accepting capacity is implemented, then a similar property should be added too (proposed patch doesn't include one). |
| Comment by Aristarkh Zagorodnikov [ 24/Jun/11 ] |
|
I noticed a minor inefficiency change (used property instead of a local variable that already contained the needed value), so I uploaded an improved version. |
| Comment by Aristarkh Zagorodnikov [ 24/Jun/11 ] |
|
Fixed minor inefficiency |
| Comment by Aristarkh Zagorodnikov [ 24/Jun/11 ] |
|
Smaller number of elements just get smaller benefits, 4-8 element arrays for example are only ~8-10% faster. There is about 5% penalty only if you provide a "pure" IEnumerable<T> with a small amount of elements (16-element Linq result fit into this category, but if one uses Linq, the performance is already suffering due to delegate invocation and, in complex cases, intermediate buffering). On the other hand, the typical use case where performance matters – feeding a T[] or a List<T> to constructor or an AddRange, is always faster due to preallocation (the only extra operations are two attempted casts and two null checks for worst case) and direct "for" loop iteration instead of foreach for indexable data (no extra operations apart the ones introduced for preallocation). As for the "capacity" constructor, my patch provides one and uses it in Clone() and DeepClone() implementations, as I recognize that adding data to a preallocated BsonArray directly instead of creating an intermediate buffer is the most effective way to create BsonArray filled with data that is generated/calculated on the go. Still, there are often cases that the input data is pre-processed and is contained in an array, list (IList<T>) or a collection (i.e. HashSet<T>), or is added partially and the final size is not known – in this case the existing constructor/AddRange methods are less effective than they could. As for the implementation complication – the BsonArray(IEnumerable<T>) constructors are completely unchanged, the AddRange methods are now uniform (and can be implemented in one line if you consider adding BsonArray return value to proposed AddRange<T>(IEnumerable<T>, Func<T, BsonValue>)), Clone() and DeepClone() are just implemented a little bit more efficiently. |
| Comment by Robert Stam [ 24/Jun/11 ] |
|
How does this patch affect performance when the BsonArray is created with a small number of elements? Perhaps a simpler change is to just added a constructor to create a BsonArray with a certain capacity and the let the client code assign directly to the elements. Something like: var capacity = 1000; This would avoid complicating the implementation of BsonArray constructors and not impact performance of creation of small BsonArrays. |