[Mono-dev] [Patch] Small optimization to String.Replace and StringBuilder.Replace

2008-06-16 Thread Juraj Skripsky 
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

2008-06-16 Thread Andreas Nahr 
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

2008-06-17 Thread Juraj Skripsky 
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 +