Associative Array potential performance pitfall?

[H. S. Teoh]

On Fri, Mar 13, 2020 at 03:40:11AM +0000, Adnan via Digitalmars-d-learn wrote:
> In my machine the following D code compiled with release flag and LDC
> performs over 230ms while the similar Go code performs under 120ms.
> 
> string smallestRepr(const string arg) {
> 	import std.format : format;
> 
> 	const repeated = format!"%s%s"(arg, arg);

.format is dog slow, and not exactly something you want to be calling
every iteration.  Try instead:

	auto repeated = arg ~ arg;


> 	string result;
> 	result.reserve(arg.length);
> 	result = arg;

This does not do what you think it does.  Assigning to a string is a
shallow copy; the call to .reserve is superfluous. In fact, it's
triggering another allocation, only to throw it away immediately. Just
write:

	auto result = arg;


> 	foreach (i; 1 .. arg.length) {
> 		const slice = repeated[i .. i + arg.length];
> 		if (slice < result)
> 			result = slice;
> 	}
> 	return result;
> }
[...]
> Where am I losing performance?

1) Calling .format -- it's dog slow. Just use ~.

2) Calling .reserve only to throw away the results immediately. Just
skip it.

I doubt your AA is the performance bottleneck here.


Try the following implementation of .smallestRepr that avoids (1) and
(2):

	string smallestRepr(const string arg) {
		auto repeated = arg ~ arg;
		string result = arg;
		foreach (i; 1 .. arg.length) {
			const slice = repeated[i .. i + arg.length];
			if (slice < result)
				result = slice;
		}
		return result;
	}

Note that `arg ~ arg` may allocate, but it also may not if the current
buffer for `arg` is big enough to accomodate both. So you might actually
save on some allocations here, that you lose out from calling .format.

On my machine, a quick benchmark shows a 2x performance boost.


T

-- 
That's not a bug; that's a feature!