www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - Strange CTFE issue, string replacement

reply Jethro <qyzz gr.ff> writes:
I tried to make a string like replacement called fstring which 
uses buffering to avoid lots of little allocations. The problem 
is, that it actually causes the compiler to use 10x the memory 
and about 10 times slower.


It doesn't do anything special but tries to emulate string(so it 
can be a drop in replacement, more or less)



Why would it be so ineffective in CTFE? I know strings are built 
in and the compiler probably has some optimizations, but an order 
of magnitude more memory usage is was not expected(should be 
lower)? I could understand a small speed slowdown, but not 10x.

Any ideas?

class fstring(T = char)
{
	import std.traits;
	T[] buf;	
	int length = 0;
	int Inc = 65535;

	this(int inc = 65535)
	{
		Inc = inc;
		buf.length = Inc;
		for(int i = 0; i < buf.length; i++)	buf[i] = 0;
	}

	// foreach
	ReturnType!(D) opApply(D)(scope D dg)
     {
		ReturnType!(D) result;
		for (int i = 0; i < length; i++)
		{
			result = dg(buf[i]);
			if (result) break;
		}
		return result;
     }

	// Append string to end
	auto Append(S)(S s)
	{
		while (length + s.length >= buf.length) buf.length += Inc;
		for (int i = 0; i < s.length; i++) buf[length + i] = 
cast(T)(s[i]);
		length += s.length;
	}

	// Prepends string to start
	auto Prepend(S)(S s)
	{
		while (length + s.length >= buf.length) buf.length += Inc;
		for (int i = 0; i < length; i++) buf[s.length + length - i - 1] 
= buf[length - i - 1];
		for (int i = 0; i < s.length; i++) buf[i] = cast(T)(s[i]);
		length += s.length;
	}


	auto opOpAssign(string op, S)(S s) if (op == "~") { Append(s); }	
	void opAssign(S)(S s) if (!is(S == typeof(this))) { length = 0; 
Append(s); }
	auto opBinary(string op, S)(S s) if (op == "~") { Append(s); 
return this; }
	auto opBinaryRight(string op, S)(S s) if (op == "~") { 
Prepend(s); return this; }

	bool opEquals(S)(S s)
	{		
		if (buf.length != s.length) return false;
		for(int i = 0; i < buf.length; i++)	if (buf[i] != s[i]) return 
false;
		return true;
	}

	// Forward replaces string a with string b in place(no memory 
allocations) and greedily(as they are found from left to right)
	auto replace(A, B)(A a, B b)
	{
		if (length < a.length || a.length == 0 || b.length == 0) return 
this;
		auto small = (a.length >= b.length);
		int idx = 0;
		int count = 0; // number of matches, used when b.length > 
a.length to determine how much to overallocate(which depends on 
the number of matches)
		for(int i = 0; i <= length - a.length; i++)
		{
			if (buf[i] == a[0])
			{
				auto found = true;
				for(int j = 1; j < a.length; j++)	// Work backwards as more 
likely to be a mismatch(faster)
					if (buf[i + a.length - j] != a[a.length - j])
					{
						found = false;
						break;
					}

				if (found)
				{
					count++;
					i += a.length - 1;	// dec by 1 because for loop will inc
					if (small) for(int j = 0; j < b.length; j++) buf[idx++] = 
b[j];
					continue;
				}
			}

			if (small) buf[idx++] = buf[i]; 			
		}

		int extra = -count*(a.length - b.length);
		if (small) { length += extra; if (buf.length > length) 
buf[length] = 0; return this; }

		// We now know the count so the (a.length - b.length)*count is 
the amount to expand/contract buf		
		auto end = length + extra;
		if (end >= buf.length) buf.length += Inc;


		// shift the string to make space at the head, this allows us 
to use essentially the same algorithm as above, the difference is 
that we must first know the number of matches to overallocate the 
buffer if necessary(could do dynamically) and to shift the string 
ahead
		for(int i = 0; i < length; i++)	
			buf[end - 1 - i] = buf[length - i - 1];

		idx = 0;		
		for(int i = extra; i <= length - a.length + extra; i++)
		{
			if (buf[i] == a[0])
			{
				auto found = true;
				for(int j = 1; j < a.length; j++)	// Work backwards as more 
likely to be a mismatch(faster)
					if (buf[i + a.length - j] != a[a.length - j])
					{
						found = false;
						break;
					}

				if (found)
				{
					count--;
					i += a.length - 1;	// dec by 1 because for loop will inc
					for(int j = 0; j < b.length; j++)
						buf[idx++] = b[j];
					if (count == 0) break;
					continue;
				}
			}

			buf[idx++] = buf[i]; 			
		}

		length = length + extra;
		assert(count == 0, "fstring: Programmatic Bug - Replace String 
Error!");
		return this;
	}

	// Strips away the begining(dir = -1), the end(dir = 1), or 
both(dir = 0) that match s
	auto strip(int dir = 0, Args...)(Args s)
	{

		int start = 0, end = length;
                 if (dir <= 0)
		for(int i = 0; i <= length/2 + 1; i++)
		{
			bool anyFound = false;
			foreach(ss; s)
			{			
				
				auto found = true;
				for(int j = 0; j < ss.length; j++)
				{
					if (i + j >= length) break;
					if (buf[i + j] != ss[j])
						found = false;
				}
				anyFound = anyFound | found;

				if (found) i += ss.length - 1;
			}

			if (anyFound)
				start = i+1;
			else
				break;
		}

	        if (dir >= 0)	
		for(int i = length/2; i < length; i++)
		{
			bool anyFound = false;
			foreach(ss; s)
			{			
				auto found = true;
				for(int j = 0; j < ss.length; j++)
				{
					if (i + j >= length) break;
					if (buf[i + j] != ss[j])
						found = false;
				}
				anyFound = anyFound | found;

				if (found) i += ss.length - 1;
			}

			if (!anyFound)
				end = i+1;
		}
		
		for(int i = start; i < end; i++)
			buf[i - start] = buf[i];
		length = end - start;
		return this;
	}

	auto opSlice(int start, int end) { return buf[start..end]; }
	 property int opDollar(size_t dim : 0)() { return length; }
	auto opIndex() { return buf[0..length]; }
	auto opIndex(size_t i) { return buf[i]; }
	auto opIndexAssign(S)(S v, size_t i) { buf[i] = v; }
	override string toString() { return to!string(buf[0..length]); }

}
Apr 09 2017
parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Sunday, 9 April 2017 at 19:38:33 UTC, Jethro wrote:
 I tried to make a string like replacement called fstring which 
 uses buffering to avoid lots of little allocations. The problem 
 is, that it actually causes the compiler to use 10x the memory 
 and about 10 times slower.


 It doesn't do anything special but tries to emulate string(so 
 it can be a drop in replacement, more or less)



 Why would it be so ineffective in CTFE? I know strings are 
 built in and the compiler probably has some optimizations, but 
 an order of magnitude more memory usage is was not 
 expected(should be lower)? I could understand a small speed 
 slowdown, but not 10x.

 Any ideas?

 class fstring(T = char)
 {
 	import std.traits;
 	T[] buf;	
 	int length = 0;
 	int Inc = 65535;

 	this(int inc = 65535)
 	{
 		Inc = inc;
 		buf.length = Inc;
 		for(int i = 0; i < buf.length; i++)	buf[i] = 0;
 	}

 	// foreach
 	ReturnType!(D) opApply(D)(scope D dg)
     {
 		ReturnType!(D) result;
 		for (int i = 0; i < length; i++)
 		{
 			result = dg(buf[i]);
 			if (result) break;
 		}
 		return result;
     }

 	// Append string to end
 	auto Append(S)(S s)
 	{
 		while (length + s.length >= buf.length) buf.length += Inc;
 		for (int i = 0; i < s.length; i++) buf[length + i] = 
 cast(T)(s[i]);
 		length += s.length;
 	}

 	// Prepends string to start
 	auto Prepend(S)(S s)
 	{
 		while (length + s.length >= buf.length) buf.length += Inc;
 		for (int i = 0; i < length; i++) buf[s.length + length - i - 
 1] = buf[length - i - 1];
 		for (int i = 0; i < s.length; i++) buf[i] = cast(T)(s[i]);
 		length += s.length;
 	}


 	auto opOpAssign(string op, S)(S s) if (op == "~") { Append(s); 
 }	
 	void opAssign(S)(S s) if (!is(S == typeof(this))) { length = 
 0; Append(s); }
 	auto opBinary(string op, S)(S s) if (op == "~") { Append(s); 
 return this; }
 	auto opBinaryRight(string op, S)(S s) if (op == "~") { 
 Prepend(s); return this; }

 	bool opEquals(S)(S s)
 	{		
 		if (buf.length != s.length) return false;
 		for(int i = 0; i < buf.length; i++)	if (buf[i] != s[i]) 
 return false;
 		return true;
 	}

 	// Forward replaces string a with string b in place(no memory 
 allocations) and greedily(as they are found from left to right)
 	auto replace(A, B)(A a, B b)
 	{
 		if (length < a.length || a.length == 0 || b.length == 0) 
 return this;
 		auto small = (a.length >= b.length);
 		int idx = 0;
 		int count = 0; // number of matches, used when b.length > 
 a.length to determine how much to overallocate(which depends on 
 the number of matches)
 		for(int i = 0; i <= length - a.length; i++)
 		{
 			if (buf[i] == a[0])
 			{
 				auto found = true;
 				for(int j = 1; j < a.length; j++)	// Work backwards as more 
 likely to be a mismatch(faster)
 					if (buf[i + a.length - j] != a[a.length - j])
 					{
 						found = false;
 						break;
 					}

 				if (found)
 				{
 					count++;
 					i += a.length - 1;	// dec by 1 because for loop will inc
 					if (small) for(int j = 0; j < b.length; j++) buf[idx++] = 
 b[j];
 					continue;
 				}
 			}

 			if (small) buf[idx++] = buf[i]; 			
 		}

 		int extra = -count*(a.length - b.length);
 		if (small) { length += extra; if (buf.length > length) 
 buf[length] = 0; return this; }

 		// We now know the count so the (a.length - b.length)*count 
 is the amount to expand/contract buf		
 		auto end = length + extra;
 		if (end >= buf.length) buf.length += Inc;


 		// shift the string to make space at the head, this allows us 
 to use essentially the same algorithm as above, the difference 
 is that we must first know the number of matches to 
 overallocate the buffer if necessary(could do dynamically) and 
 to shift the string ahead
 		for(int i = 0; i < length; i++)	
 			buf[end - 1 - i] = buf[length - i - 1];

 		idx = 0;		
 		for(int i = extra; i <= length - a.length + extra; i++)
 		{
 			if (buf[i] == a[0])
 			{
 				auto found = true;
 				for(int j = 1; j < a.length; j++)	// Work backwards as more 
 likely to be a mismatch(faster)
 					if (buf[i + a.length - j] != a[a.length - j])
 					{
 						found = false;
 						break;
 					}

 				if (found)
 				{
 					count--;
 					i += a.length - 1;	// dec by 1 because for loop will inc
 					for(int j = 0; j < b.length; j++)
 						buf[idx++] = b[j];
 					if (count == 0) break;
 					continue;
 				}
 			}

 			buf[idx++] = buf[i]; 			
 		}

 		length = length + extra;
 		assert(count == 0, "fstring: Programmatic Bug - Replace 
 String Error!");
 		return this;
 	}

 	// Strips away the begining(dir = -1), the end(dir = 1), or 
 both(dir = 0) that match s
 	auto strip(int dir = 0, Args...)(Args s)
 	{

 		int start = 0, end = length;
                 if (dir <= 0)
 		for(int i = 0; i <= length/2 + 1; i++)
 		{
 			bool anyFound = false;
 			foreach(ss; s)
 			{			
 				
 				auto found = true;
 				for(int j = 0; j < ss.length; j++)
 				{
 					if (i + j >= length) break;
 					if (buf[i + j] != ss[j])
 						found = false;
 				}
 				anyFound = anyFound | found;

 				if (found) i += ss.length - 1;
 			}

 			if (anyFound)
 				start = i+1;
 			else
 				break;
 		}

 	        if (dir >= 0)	
 		for(int i = length/2; i < length; i++)
 		{
 			bool anyFound = false;
 			foreach(ss; s)
 			{			
 				auto found = true;
 				for(int j = 0; j < ss.length; j++)
 				{
 					if (i + j >= length) break;
 					if (buf[i + j] != ss[j])
 						found = false;
 				}
 				anyFound = anyFound | found;

 				if (found) i += ss.length - 1;
 			}

 			if (!anyFound)
 				end = i+1;
 		}
 		
 		for(int i = start; i < end; i++)
 			buf[i - start] = buf[i];
 		length = end - start;
 		return this;
 	}

 	auto opSlice(int start, int end) { return buf[start..end]; }
 	 property int opDollar(size_t dim : 0)() { return length; }
 	auto opIndex() { return buf[0..length]; }
 	auto opIndex(size_t i) { return buf[i]; }
 	auto opIndexAssign(S)(S v, size_t i) { buf[i] = v; }
 	override string toString() { return to!string(buf[0..length]); 
 }

 }
The constructor is nuts. You do not need to zero the string! Also avoid templates if you can.
Apr 09 2017
parent reply Jethro <qyzz gr.ff> writes:
On Sunday, 9 April 2017 at 19:55:57 UTC, Stefan Koch wrote:
 On Sunday, 9 April 2017 at 19:38:33 UTC, Jethro wrote:
 [...]
The constructor is nuts. You do not need to zero the string! Also avoid templates if you can.
Please don't criticize banal stuff by choosing one meaningless line and calling the whole thing "nuts". It's a waste of time. I zero'ed it because it helps in debugging and for other errors.(if used in C terminated like string usage it helps to have the string actually terminate at some point) My questions still stand though. Why is it 10x the speed and memory?!?!
Apr 09 2017
parent Stefan Koch <uplink.coder googlemail.com> writes:
On Sunday, 9 April 2017 at 20:20:55 UTC, Jethro wrote:
 On Sunday, 9 April 2017 at 19:55:57 UTC, Stefan Koch wrote:
 On Sunday, 9 April 2017 at 19:38:33 UTC, Jethro wrote:
 [...]
The constructor is nuts. You do not need to zero the string! Also avoid templates if you can.
Please don't criticize banal stuff by choosing one meaningless line and calling the whole thing "nuts". It's a waste of time. I zero'ed it because it helps in debugging and for other errors.(if used in C terminated like string usage it helps to have the string actually terminate at some point) My questions still stand though. Why is it 10x the speed and memory?!?!
The short answer is because the current (soon to be replaced) CTFE implementation has a number of issues.
Apr 09 2017