编程小知识之性能优化
版权声明：本文为博主原创文章，未经博主允许不得转载。
本文简述了一种性能优化中常见的思维误区
程序开发总是离不开性能优化,虽然规避不成熟优化的箴言早已有之,但我们又往往会被自己翻涌的思维火花所牵绊,义无反顾的开启自己的性能劣化之旅…
考虑下面的一个简单问题(以 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];
}至此,我们顺利的完成了一次性能劣化…
WTF?
简单编写一个测试程序(给定的字符串参数较短):
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(https://en.wikipedia.org/wiki/Profiling_(computer_programming%29)
参考资料
(CSDN的代码块显示格式缩进总有问题,不知是Bug还是自己使用不当,有知道的朋友麻烦告诉一声~)
腾讯云开发者
