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

shang2010

性能优化不是工期的重点，主要是实现功能（大概消耗70-80%的精力，干活的累）

然后处理新代码功能与原来代码仓库的各种issue或者上层业务bug问题
（这个环节狠考验人，总是有同事出来找茬，当然他们也没什么水平，——很屌丝被各种虐，还不给钱，倒是时时刻刻都活得提心吊胆的）

性能优化往往没机会到这个环节，有一次项目，领导属于放任管理，所以我这边才有机会做优化，
大概花了25%的时间，但是只消耗了10%的精力（测试活没有写代码的累）

shang2010

为什么性能优化只消耗10%的精力呢，原因很简单，

所有的代码都是我写的，所有的细节都清楚，只要摸对方向，性能问题分分钟钟被教育怎么做人

爻易

因为是自主的，所以是可发展的

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分为２５６个组，
........
中间还支持过其他项目组框架设计，各种会议。。。。。
。。。。现在还在收尾，　手册已经写了７０多页（小四字体），还没有写完。。。。。。。。。。

lxyscls

wlmqgzm 发表于 2016-12-26 13:21
我最近做一个大约１万行的代码，８０％的精力都是在性能优化，也是全部自己写的代码
主要目标是代替memcac ...

当在hash值对应的空间寻找，被占用则到下一个空间，依次类推，这个设计方案主要的优势是cache友好

开发寻址？线性查找，还是二次查找？如果是二次的话，cache也没啥亲和性了吧，第一次不命中，第二次就跳好远，除非hash很小

另外还要考虑高并发的情况，按照最大支持２５６个CPU并发的要求，将circular_hash_map分为２５６个组

MPMC？是不是通常的都是这么个思路啊，Java里面的ConcurrentHashMap以前也是这么个思路

concurrencykit里面有一个支持SPMC的Hash，就是开发寻址的

wlmqgzm

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

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

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

lxyscls

wlmqgzm 发表于 2016-12-26 15:49
线性查找，其实，等效于std::vector的连续查找，

是　开放寻址法　的一个实现，与类似算法的一个重要 ...

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

请问这个“最大搜索长度限制”怎么理解呢？
insert()的时候，不就是要找到尾巴上可以插入的地方吗？难道因为位移长了就不插入了？

search()，本来hash里面有的，总不能因为“最大长度限制”返回个nullptr吧

wlmqgzm

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

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

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

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

shang2010

回复 4# wlmqgzm

看出来了，你们这边做的系统比较复杂，
我的只是一段小代码逻辑服务，查询缓存的，代码量整体有一两千行，自己手写的大概只有两三百行。
整个周期前后只有一个月，其中最后环节是上级主管做主要的测试工作的，然后我根据反馈进一步改进代码逻辑


如果做大又复杂的系统难免会大量采用第三方工业代码，例如std/boost等等，
不一样。你们整个周期差不多利索的话应该超过半年，甚至两三年的也有

windoze

open addressing最大的问题是必须预留两个元素，一个表示未占用，另一个表示已删除。
cache友好就不要想了，除非步进长度为1。
总而言之用是可以用的，但是有些坑。