3

编程小知识之性能优化

 2 years ago
source link: https://blog.csdn.net/tkokof1/article/details/85013000
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
编程小知识之性能优化_tkokof1的专栏-CSDN博客

本文简述了一种性能优化中常见的思维误区

程序开发总是离不开性能优化,虽然规避不成熟优化的箴言早已有之,但我们又往往会被自己翻涌的思维火花所牵绊,义无反顾的开启自己的性能劣化之旅…

考虑下面的一个简单问题(以 C# 为例):

  • 编写一个字符串修饰函数:给定一个字符串,为其添加一个固定的字符串后缀

这个函数在譬如文件处理过程中很常用,代码也非常简单:

const string SUFFIX = ".suffix";
public string Decorate(string str)
{
	return str + SUFFIX;
}

考虑到字符串拼接操作比较耗费资源(一次内存分配操作和两次字符串拷贝操作),函数添加的后缀又是固定的(静态),我们大可以将结果进行缓存(假设内存是充足的),于是我们有了新的 Decorate 函数实现:

const string SUFFIX = ".suffix";
Dictionary<string, string> s_buffer = new Dictionary<string, string>();
public string DecorateCache(string str)
{
	if (!s_buffer.ContainsKey(str))
	{
		s_buffer.Add(str, str + SUFFIX);
	}
	
	return s_buffer[str];
}

至此,我们顺利的完成了一次性能劣化

简单编写一个测试程序(给定的字符串参数较短):

int perfCount = 1000000;
string path = "path";
			
{
	var stopWatch = Stopwatch.StartNew();
	
	for (int i = 0; i < perfCount; ++i)
	{
		StringUtil.Decorate(path);
	}
	
	Console.WriteLine("perf1 time " + stopWatch.ElapsedMilliseconds);
}

{
	var stopWatch = Stopwatch.StartNew();
	
	for (int i = 0; i < perfCount; ++i)
	{
		StringUtil.DecorateCache(path);
	}
	
	Console.WriteLine("perf2 time " + stopWatch.ElapsedMilliseconds);
}

发现 DecorateCache 函数的运行时间是 Decorate 函数的 1.5 倍!实际上,只有当添加的后缀字符串(SUFFIX) 较长时(给定的字符串参数较短), Decorate 函数的运行时间才会高于 DecorateCache 函数,但进一步的测试表明,添加的后缀字符串长度需要 >= 80 才会出现这种情况,这在实际中基本是不会出现的,相反,给定的字符串参数却往往很长(譬如文件路径),所以更加符合实际的测试代码应该是这样的(给定的字符串参数较长):

int perfCount = 1000000;
string path = "longlonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglonglongpath";
			
{
	var stopWatch = Stopwatch.StartNew();
	
	for (int i = 0; i < perfCount; ++i)
	{
		StringUtil.Decorate(path);
	}
	
	Console.WriteLine("perf1 time " + stopWatch.ElapsedMilliseconds);
}

{
	var stopWatch = Stopwatch.StartNew();
	
	for (int i = 0; i < perfCount; ++i)
	{
		StringUtil.DecorateCache(path);
	}
	
	Console.WriteLine("perf2 time " + stopWatch.ElapsedMilliseconds);
}

这种情况下, DecorateCache 函数的运行时间是 Decorate 函数的 2 倍!

造成这种情况的原因其实是个偏工程的问题: Dictionary 的 indexer 和 ContainsKey 都涉及的内部函数 FindEntry 的实现.

这里我们不去深入细节,只要知道 FindEntry 其实是个时间复杂度为 O(n) 的操作即可(n为给定字符串参数的长度),而之前的 Decorate 函数虽然时间复杂度也是 O(n),但由于工程实现问题,实际上的运行速度是要更快的.

这里还有一个变量: Decorate 函数涉及的一次内存分配.这导致我们不能简单的对 Decorate 函数和 DecorateCache 函数做性能比较.

但我们仍然可以认为,一般情况下, Decorate 函数是优于 DecorateCache 函数的!

于是我们又回归了最初的函数实现:

const string SUFFIX = ".suffix";
public string Decorate(string str)
{
	return str + SUFFIX;
}

小结 : 对于性能优化,大胆假设,小心求证,信自己,更要信 Profiling

(CSDN的代码块显示格式缩进总有问题,不知是Bug还是自己使用不当,有知道的朋友麻烦告诉一声~)


About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK