标签： STL

std::inner_product的简单性能测试

最近团队产品中用到了一些机器学习方面的算法，涉及到求向量内积，采取的是最朴素的实现方式（元素乘积循环相加）。有一天路上想到 STL 提供了一个模板函数 std::inner_product ，就好奇 libstdc++ 实现上是否对该算法做了什么优化呢？

于是做了个简单的实验：1000 维 double 类型向量乘积，用 std::inner_product 和朴素方法分别计算10000次，g++ -O2优化。第一轮使用原生 double 类型数组，第二轮使用 vector<double> 容器，分别在三个机器环境下进行了计算。

// Processors | physical = 2, cores = 32, virtual = 12, hyperthreading = no
//     Speeds | 12x2400.186
//     Models | 12xIntel(R) Xeon(R) CPU E5645 @ 2.40GHz
//     Caches | 12x256 KB
//        GCC | version 3.4.5 20051201 (Red Hat 3.4.5-2)
	   
a*b     : std::inner_product(27.934ms), for loop(40.061ms)
a_v*b_v : std::inner_product(27.878ms), for loop(40.04ms)

// Processors | physical = 2, cores = 12, virtual = 12, hyperthreading = no
//     Speeds | 12x2100.173
//     Models | 12xAMD Opteron(tm) Processor 4170 HE
//     Caches | 12x512 KB
//        GCC | version 3.4.5 20051201 (Red Hat 3.4.5-2)

a*b     : std::inner_product(31.242ms), for loop(47.853ms)
a_v*b_v : std::inner_product(31.301ms), for loop(47.815ms)

// Processors | physical = 1, cores = 0, virtual = 1, hyperthreading = no
//     Speeds | 1x2572.652
//     Models | 1xIntel(R) Core(TM) i5-3320M CPU @ 2.60GHz
//     Caches | 1x6144 KB
//        GCC | version 4.7.2 (Ubuntu/Linaro 4.7.2-2ubuntu1)

a*b     : std::inner_product(41.76ms), for loop(33.165ms)
a_v*b_v : std::inner_product(35.913ms), for loop(32.881ms)

可以看出不同环境下 std::inner_product 的表现不尽相同，与朴素的方式相比有优有劣。瞄了一眼 gcc 4.8 的 libstdc++ 的代码，没有注意到 std::inner_product 对基本类型做什么 SSE 指令的优化。不过倒是有个并行计算的版本，可能对超大的向量计算有帮助。

虽然从性能上没有看到明显的优势，但毕竟 std::inner_product 可以简化一个循环的编码，至少可以少测一个分支嘛。而且配合重载函数的后两个 functor 参数，可以做一些有趣的事情，比如算一组数的平方和，比较两个字符串相同字符的数量等。以后呢可以多尝试一下用标准库的算法而不是自己写循环。

std::sort 的仿函数参数

因为习惯了 qsort 的函数指针参数，以前用 std::sort 的时候一般也是传函数指针而不是仿函数（functor）。从很多示例程序来看，貌似没有什么大的不同。但是直到今天我才醒悟，原来是示例太简单了啊！

具体来说，我今天遇到了一个问题：要对一个表进行排序，每个字段可能是升序，可能是降序，也有不同的类型，所以排序的时候需要根据这些信息进行比较。比较函数不能是类成员函数，但我又的确要用到类成员的信息，函数接口又不能变，着实发愁。愁了就只能 Google，发现原来仿函数可以轻松地搞定这件事情。

// 来自 http://stackoverflow.com/a/1902360
class MyClass{

   // ...
   struct doCompare
   {
       doCompare( const MyClass& info ) : m_info(info) { } // only if you really need the object state
       const MyClass& m_info;

       bool operator()( const int & i1, const int & i2  )
       {
            // comparison code using m_info
       }
   };

    doSort()
    { std::sort( arr, arr+someSize, doCompare(*this) ); }
};

简单点儿说，因为仿函数是个类，也可以有成员变量，构造的时候可以传参进去初始化，这样就能实现更灵活的比较方法。这么简单的道理，为什么之前我就是想不到呢？

此外值得一提的是，std::sort 要求比较的结果是 strict weak order，就是说要严格小于才返回 true。这就意味着，仅仅对比较结果取反，是无法实现逆序的。因为小于的取反不是大于，而是大于等于。

我们有过经验，如果相等的时候也返回 true，可能会导致某些标准库实现的 sort 函数指针越界，导致程序出错。所以要千万避免犯这个错误。