寡人写代码的那些事，分享一下

wlmqgzm

我最近做一个大约１万行的代码，８０％的精力都是在性能优化，也是全部自己写的代码
主要目标是代替memcache的模块，提供多数据表table, 加载保存和日志等功能，指令集在memcahe的基础上有不少扩展，包括类似 like 'aaa%'这样的语句，以及几种全表扫描的语句，
最早计划是１个半月完成，就是１０月底完成。结果做完就不断的优化，不优化的话，单连接性能比memcache低，
基本上把所有可以优化的地方重新都做了一遍，实际用了３个半月，现在实现的版本已经比memcache略快了，而且内存分配是new/delete，全部动态申请内存，
整个底层库全部优化测试了一遍，
包括　spin_lock自己实现一个通用版本 ,主要使用C++１４atomic，支持yield, 性能更高
std::unordered_map自己实现的circular_hash_map用环形队列重写了一个通用库版本，比std库提高了至少７０％以上的性能，并且内存自动扩展和收缩
主要的优化思路是：
１）当在hash值对应的空间寻找，被占用则到下一个空间，依次类推，这个设计方案主要的优势是cache友好，因为是顺序查找。最大可以占用８５％的空间，超过则自动扩展一倍。
２）hash值的缓存，这样扩展或者收缩的时候不用重新计算hash节约了一点计算量
３）hash计算采用SSE4.2实现
４）使用了一些标志位进行性能优化，包括限制查询次数等。。。。
５）参考linux核心kqueue的设计，使用２的N次方的长度，就可以利用与操作代替除法操作，进行最后的匹配，提高性能

command语句解析最早用boost::spirit做，觉得性能不够好，用自己的逻辑重写了一个版本，比spirit版本快了大约３倍
另外还要考虑高并发的情况，按照最大支持２５６个CPU并发的要求，将circular_hash_map分为２５６个组，
........
中间还支持过其他项目组框架设计，各种会议。。。。。
。。。。现在还在收尾，　手册已经写了７０多页（小四字体），还没有写完。。。。。。。。。。

wlmqgzm

lxyscls 发表于 2016-12-26 14:07
开发寻址？线性查找，还是二次查找？如果是二次的话，cache也没啥亲和性了吧，第一次不命中，第二次 ...

线性查找，其实，等效于std::vector的连续查找，

是　开放寻址法　的一个实现，与类似算法的一个重要区别是：我的算法中每个hash都有　单独的最大搜索长度的限制，这样可以进一步提高性能，

wlmqgzm

lxyscls 发表于 2016-12-26 16:31
请问这个“最大搜索长度限制”怎么理解呢？
insert()的时候，不就是要找到尾巴上可以插入的地方吗？难道 ...

请问这个“最大搜索长度限制”怎么理解呢？
insert()的时候，一直按顺序找啊找，找到可以插入的地方，插入数据，
比较原始hash对应的bucket桶　最大搜索旧长度，如果更大，则存储新的最大搜索长度限制。否则，不保存。

search()的时候，一直按顺序找啊找，
每找下一个地址比较一下是否到达最大搜索长度，如果到达最大搜索长度还没有找到，说明根本就没有这个数据，可以提前返回了。

每个hash bucket桶　都有一个　单独的最大搜索长度的限制，这样可以进一步提高性能

wlmqgzm

windoze 发表于 2016-12-29 00:17
open addressing最大的问题是必须预留两个元素，一个表示未占用，另一个表示已删除。
cache友好就不要想了 ...

对的，常规的　open addressin　有　两个元素，一个表示未占用，另一个表示已删除，所以，觉得不够优化。
修改为　unsigned int  uint_distance;　其中拿出一个bit表示　未占用或者已经删除，　其余bit表示最大搜索长度，这样在数据比较满的情况下有更好的性能。
步进长度为１，所以cache友好

template<typename KEY, typename VALUE>
class  Struct_circular_hash_map_record
{
   public:
     Struct_circular_hash_map_record( void );

     #ifdef  CIRCULAR_HASH_MAP_HAS_MEMORY_COUNT
     size_t  capacity( void );
     #endif // CIRCULAR_HASH_MAP_HAS_MEMORY_COUNT

     #ifdef   CIRCULAR_HASH_MAP_VALUE_HAS_VERSION
     void     init_version( void );
     void     increase_version( void );
     unsigned int  uint_version;
     #endif // CIRCULAR_HASH_MAP_VALUE_HAS_VERSION

     unsigned int  uint_distance;
     unsigned int  uint_hash;
     KEY  key;
     VALUE  value;
};

wlmqgzm

lxyscls 发表于 2016-12-30 09:53
线性探查

没有实际写过，只能搬一下《算法导论》里面的描述：容易出现群集现象

主要是hash计算出的数据是否足够　平均分布，　而不是挤在一起，我觉得基于intel SSE4.2指令集的 crc32c的算法，算比较优秀，　即使是８５％以上的容量占用，性能也还是很好。