Created by: DannyIsFunny
【问题描述】Paddle-Lite有hash_combine
加密方法实现。 在InferShape
函数调用hash_combine
算法验证是否需要执行InferShapeImpl
。业务反馈hash_combine
出现“hash碰撞现象” (即不同的input得到相同的“hash”结果)
【问题定位】hash_combine
实现可靠度低
【本PR工作】改进hash_combine
实现,新实现采用旋转Hash简化实现boost::hash_combine
// A simplified implementation of boost::hash_combine.
template <typename T>
inline void CombineHash(const T& from, size_t* to) {
std::hash<T> h;
*to ^= h(from) + 0x9e3779b9 + (*to << 6) + (*to >> 2);
}
当前实现与Tensor Flow
中的HashCombine
实现一致
【效果】修改后可以避免当前出现的hash碰撞现象。
计算量评估:两hash_combine
实现计算量一致: 两次二进制数据移位(uint64)、三次加法(uint64+uint64)、一次按位异或(uint64^uint64);新的实现方法void型,直接对指针操作,没有返回数据,少了一次内存拷贝
实验验证: vector<uint64_t>(3000000)
内保存了3000000个uint64_t的连续数据,对vector所有数据执行hash_combine操作, 先执行100 0000 次作为warmup, 再执行 100 0000 次作为测试结果
(原有Hash_combine方法记为HashOld,新方法记为HashNew) ,多次测试平均结果如下(测试环境为PC Linux):
CostTime of HashOld :6.3e-05 ms.
CostTime of HashNew :6e-05 ms.
综上可知,本次对Hash_combine函数的修改未降低运行性能