[Mono-dev] [Patch] Small optimization to String.Replace and StringBuilder.Replace
Hello, Attached you'll find a patch which reduces the number of allocations done in String.Replace and StringBuilder.Replace. All unit tests pass. Please review. - Juraj Index: System/ChangeLog === --- System/ChangeLog (revision 105881) +++ System/ChangeLog (working copy) @@ -1,3 +1,9 @@ +2008-06-16 Juraj Skripsky <[EMAIL PROTECTED]> + + * String.cs (ReplaceUnchecked): Don't stackalloc more than necessary. Return + "this" if it does not contain oldValue. + (Compare): Use Math.Min. + 2008-06-14 Zoltan Varga <[EMAIL PROTECTED]> * Environment.cs: Bump corlib version. Index: System/String.cs === --- System/String.cs (revision 105881) +++ System/String.cs (working copy) @@ -568,17 +568,9 @@ // CompareInfo.Compare will insist that length // <= (string.Length - offset) - int len1 = length; - int len2 = length; + int len1 = Math.Min (length, strA.Length - indexA); + int len2 = Math.Min (length, strB.Length - indexB); - if (length > (strA.Length - indexA)) { -len1 = strA.Length - indexA; - } - - if (length > (strB.Length - indexB)) { -len2 = strB.Length - indexB; - } - // ENHANCE: Might call internal_compare_switch directly instead of doing all checks twice return culture.CompareInfo.Compare (strA, indexA, len1, strB, indexB, len2, compopts); } @@ -1645,7 +1637,8 @@ // because the length of the result would be this.length and length calculation unneccesary } - const int maxValue = 200; // Allocate 800 byte maximum + // Allocate 800 byte maximum + int maxValue = Math.Min ((length + oldValue.Length - 1) / oldValue.Length, 200); int* dat = stackalloc int[maxValue]; fixed (char* source = this, replace = newValue) { int i = 0, count = 0; @@ -1661,6 +1654,9 @@ } i = found + oldValue.length; } +if (count == 0) + return this; + int nlen = this.length + ((newValue.length - oldValue.length) * count); String tmp = InternalAllocateStr (nlen); Index: System.Text/StringBuilder.cs === --- System.Text/StringBuilder.cs (revision 105881) +++ System.Text/StringBuilder.cs (working copy) @@ -310,14 +310,19 @@ throw new ArgumentException ("The old value cannot be zero length."); // TODO: OPTIMIZE! - string replace = _str.Substring(startIndex, count).Replace(oldValue, newValue); + string substr = _str.Substring(startIndex, count); + string replace = substr.Replace(oldValue, newValue); + if ((object) replace == (object) substr) +return this; InternalEnsureCapacity (replace.Length + (_length - count)); - string end = _str.Substring (startIndex + count, _length - startIndex - count ); - + if (replace.Length < count) +String.CharCopy (_str, startIndex + replace.Length, _str, startIndex + count, _length - startIndex - count); + else if (replace.Length > count) +String.CharCopyReverse (_str, startIndex + replace.Length, _str, startIndex + count, _length - startIndex - count); + String.CharCopy (_str, startIndex, replace, 0, replace.Length); - String.CharCopy (_str, startIndex + replace.Length, end, 0, end.Length); _length = replace.Length + (_length - count); Index: System.Text/ChangeLog === --- System.Text/ChangeLog (revision 105881) +++ System.Text/ChangeLog (working copy) @@ -1,3 +1,8 @@ +2008-06-16 Juraj Skripsky <[EMAIL PROTECTED]> + + * StringBuilder.cs (Replace): Do nothing if we don't contain oldValue. + Do the moving of the string end in-place. + 2008-06-01 Juraj Skripsky <[EMAIL PROTECTED]> * StringBuilder.cs (ToString): Use String.SubstringUnchecked instead ___ Mono-devel-list mailing list Mono-devel-list@lists.ximian.com http://lists.ximian.com/mailman/listinfo/mono-devel-list
Re: [Mono-dev] [Patch] Small optimization to String.Replace and StringBuilder.Replace
Did you time/measure this change? - const int maxValue = 200; // Allocate 800 byte maximum + // Allocate 800 byte maximum + int maxValue = Math.Min ((length + oldValue.Length - 1) / oldValue.Length, 200); int* dat = stackalloc int[maxValue]; fixed (char* source = this, replace = newValue) { int i = 0, count = 0; @@ -1661,6 +1654,9 @@ } i = found + oldValue.length; } + if (count == 0) + return this; + int nlen = this.length + ((newValue.length - oldValue.length) * count); String tmp = InternalAllocateStr (nlen); My assumption is that for small (common) cases this may produce a noticable slowdown. I'm fine with the count == 0 shortcut, but the exact calculation will probably hurt performance. Maybe a compromise would be int maxValue = Math.Min (length, 200); Happy Hacking Andreas > -Ursprüngliche Nachricht- > Von: [EMAIL PROTECTED] [mailto:mono-devel-list- > [EMAIL PROTECTED] Im Auftrag von Juraj Skripsky > Gesendet: Montag, 16. Juni 2008 16:38 > An: mono-devel > Betreff: [Mono-dev] [Patch] Small optimization to String.Replace and > StringBuilder.Replace > > Hello, > > Attached you'll find a patch which reduces the number of allocations > done in String.Replace and StringBuilder.Replace. > > All unit tests pass. > Please review. > > - Juraj ___ Mono-devel-list mailing list Mono-devel-list@lists.ximian.com http://lists.ximian.com/mailman/listinfo/mono-devel-list
Re: [Mono-dev] [Patch] Small optimization to String.Replace and StringBuilder.Replace
Hi Andreas, Thanks for looking at my patch. I did a few measurements now with short strings and you're right - we're a tiny bit (4-5%) slower with the calculated stackalloc version. The compromise you proposed is about 2-3% faster than the const version, so I incorporated that one. An updated patch is attached. - Juraj On Mon, 2008-06-16 at 19:20 +0200, Andreas Nahr wrote: > Did you time/measure this change? > > - const int maxValue = 200; // Allocate 800 byte > maximum > + // Allocate 800 byte maximum > + int maxValue = Math.Min ((length + oldValue.Length - > 1) / oldValue.Length, 200); > int* dat = stackalloc int[maxValue]; > fixed (char* source = this, replace = newValue) { > int i = 0, count = 0; > @@ -1661,6 +1654,9 @@ > } > i = found + oldValue.length; > } > + if (count == 0) > + return this; > + > int nlen = this.length + ((newValue.length - > oldValue.length) * count); > String tmp = InternalAllocateStr (nlen); > > My assumption is that for small (common) cases this may produce a noticable > slowdown. > I'm fine with the count == 0 shortcut, but the exact calculation will > probably hurt performance. > Maybe a compromise would be > int maxValue = Math.Min (length, 200); > > Happy Hacking > Andreas > > > -Ursprüngliche Nachricht- > > Von: [EMAIL PROTECTED] [mailto:mono-devel-list- > > [EMAIL PROTECTED] Im Auftrag von Juraj Skripsky > > Gesendet: Montag, 16. Juni 2008 16:38 > > An: mono-devel > > Betreff: [Mono-dev] [Patch] Small optimization to String.Replace and > > StringBuilder.Replace > > > > Hello, > > > > Attached you'll find a patch which reduces the number of allocations > > done in String.Replace and StringBuilder.Replace. > > > > All unit tests pass. > > Please review. > > > > - Juraj > Index: System/ChangeLog === --- System/ChangeLog (revision 105881) +++ System/ChangeLog (working copy) @@ -1,3 +1,9 @@ +2008-06-16 Juraj Skripsky <[EMAIL PROTECTED]> + + * String.cs (ReplaceUnchecked): Don't stackalloc more than necessary. Return + "this" if it does not contain oldValue. + (Compare): Use Math.Min. + 2008-06-14 Zoltan Varga <[EMAIL PROTECTED]> * Environment.cs: Bump corlib version. Index: System/String.cs === --- System/String.cs (revision 105881) +++ System/String.cs (working copy) @@ -568,17 +568,9 @@ // CompareInfo.Compare will insist that length // <= (string.Length - offset) - int len1 = length; - int len2 = length; + int len1 = Math.Min (length, strA.Length - indexA); + int len2 = Math.Min (length, strB.Length - indexB); - if (length > (strA.Length - indexA)) { -len1 = strA.Length - indexA; - } - - if (length > (strB.Length - indexB)) { -len2 = strB.Length - indexB; - } - // ENHANCE: Might call internal_compare_switch directly instead of doing all checks twice return culture.CompareInfo.Compare (strA, indexA, len1, strB, indexB, len2, compopts); } @@ -1645,8 +1637,9 @@ // because the length of the result would be this.length and length calculation unneccesary } - const int maxValue = 200; // Allocate 800 byte maximum - int* dat = stackalloc int[maxValue]; + // Allocate 800 byte maximum + int maxValue = Math.Min (length, 200); + int* dat = stackalloc int [maxValue]; fixed (char* source = this, replace = newValue) { int i = 0, count = 0; while (i < length) { @@ -1661,6 +1654,9 @@ } i = found + oldValue.length; } +if (count == 0) + return this; + int nlen = this.length + ((newValue.length - oldValue.length) * count); String tmp = InternalAllocateStr (nlen); Index: System.Text/StringBuilder.cs === --- System.Text/StringBuilder.cs (revision 105881) +++ System.Text/StringBuilder.cs (working copy) @@ -310,14 +310,19 @@ throw new ArgumentException ("The old value cannot be zero length."); // TODO: OPTIMIZE! - string replace = _str.Substring(startIndex, count).Replace(oldValue, newValue); + string substr = _str.Substring(startIndex, count); + string replace = substr.Replace(oldValue, newValue); + if ((object) replace == (object) substr) +return this; InternalEnsureCapacity (replace.Length +