技术聊天记录: 关于TAttributeSet减少lookup的改进方法的讨论

wooce:
我仔细思考了一下:
1)  如果不能把Server端和Client端的程序放在一起编译,  或者是由程序员定义一个include某AttributeSet中
会出现的所有键值的enum放在某头文件里,  在server端和client端所有用到某attributeset的地方都引用这个头文件,  总之必
须让所有用到attributeset的地方都知道这个attributeset里所有可能的键值, 要在编译时就完全决定
Get("abc")是Get  AttributeSet中的第几项, 是难以做到的. 
不论编译器(或发明/下载的特殊的程序预处理器)如何地聪明,  若单独编译client端的程序,  因为
client端不一定用到server端put入的所有key值,  所以server端发送过来的attributeset里存在有
编译client程序时未知的key,   编译client程序时要把这些未知的字符串类型的key映射到AttributeSet
中的某个位置上,  不论我们去找多少花哨的程序设计技巧, 实质都要归结为把一个字符串集合中的某个字
符串唯一映射到一个整数上(不同的字符串必须映射到不同的整数) ,  显然并不存在这样的映射, 那些如
HASH方法总难免把几个字符串映射到同一个整数上. 
2)  如果不想采用在server端和client端所有用到某attributeset的地方都引用包含其中的所有键值的头文件的方法,
又想提高lookup的效率而同时保持原来的弹性,  显然必须修改我们的通讯协议,  client端在接收某个AttributeSet的时侯, 如果
此前从未接收过此attributeset,  则必须和server端进行协商,  建立一张attributeset的各个key在client端的
Get()所用的整数index值和server端以后发送过来的此attributeset的相对应的存储位置的对照表, 这样client端在Get("abc")
时实际上是执行取Values[ convert[i] ] 的操作,  不再需要lookup字符串了,  提高了效率.
在一些细节上:  
    现在的使用attributeset的程序一般是:
OnRequest()
{
....
    TProtocol *pProtocol;
    XNew(pProtocol, TProtocol(....));
    pProtocol->SvrReceive(comm, asRequest);
    TAttributeSet asRequest, asResponse;
    int cmd = asRequest.Get("Cmd").AsInt();
    asRequest.Get("abc").AsString();
    asRequest.Get("efg").As....();
....
}
    可以看出要保持这种写法的弹性, 又能在第一次GET一个attributeset的时侯插入和server协商建立对照表的代码有点
麻烦. 
    我觉得比较好的改法是变上面的pProtocol->SvrReceive(comm, asRequest);为asRequest.SetCommProtocol(comm,pProtocol);
里面并不执行通讯操作,  在其后执行的第一条asRequest.Get("...")代码中, 根据某变量知道还未建立对照表,  然后调用
类似pProtocol->SvrReceive(comm, asRequest);原来的代码get到server端发来的attributeset的全部内容和全部key,  由于在编译
第一条Get语句的时侯并不知道后面的其他Get语句的键的字符串,  所以此时对照表还不能完全建立的,  只能先
        static int i=0;
        存储位置j = find(attributeset from server, "Cmd") ;
        对照表convert.Put(i, j);
        return Values[ convert[i++] ];
然后在第二条
asRequest.Get("...")上,  执行上面同样的代码(不需和Server协商了) ,
最后当get完所有key的时侯, 就知道对照表已建立好.  但如果client端不需要get其中所有的key的时侯,  那就需要在所有Get()方法后
加个asRequest.End()的方法来显式标志对照表已建立了.

XXX:


其实昨天我说那个想法的意思是,attributeset可以考虑的优化方面的东西很多,那样只是其中的一个,而且不一定可行的,我是想让你具体想想是否还有其他想法,或者那个想法是否可行:
1.attributeset目前key在程序中都是通过#define做的,实际上,
    1.1.可以考虑直接提供int类型的key(特别是内部使用的场合)
    1.2.提供const char * 的接口方式
2.由于目前程序还没有被广泛使用,所以可以考虑修改通信协议来优化
3.实际上目前attributeset的存贮结构决定了:
    3.1.即使有key lookup的优化,实际上每次还需要对buffer进行parse,知道每一块的物理位置(就时说即使知道"abc"就是1也需要知道1对应在物理buffer的哪里
    3.2.如果需要parse实际上在parse的时候已经可以做完key的lookup了,而字符串的比较在parse过程中,实际上不会比int比较慢太多的,所以简单这样的优化意义不大
    3.3.基于3.1.,3.2.实际上要做key lookup的优化,最终必须改协议增加索引表,这样实际上就是tim说的问题了,而反过来实际上通过1.1.的方式就可以优化了部分的过程,所以不一定需要做那么复杂的事情.
4.由于"内存分配"操作相对而言是比较耗费资源的(相对strcmp之类的东西),所以减少内存分配的次数实际上是优化的一个原则,这个已经体现在了TRefAttributeSet里面了,但是我觉的这样反而不好,多了一个东西别人反而不知道应该用哪一个,所以需要考虑能否把两个东西合并成为一个优化了的TAttributeSet
5.下面是我的一些想法:
    5.1.确定attributeset的使用的限制:
        至少有:每一个数据项的长度不大,如果数据项可能比较大的,通过其他方式包装,Tprotocol可以兼容
    5.2.AttributeSet内部同时存在两种态性(两种数据):一种是打包好的数据(a),一种是分散的hash或者其他的方便管理的数据(b):
        所有Get的操作,如果b里面有,就返回b里面的,否则就在a中直接查找返回,同时根据某些规则判断(比如attribute有多少)是否加入b中
        如果Put的操作,直接增加在hash列表中,
        当需要输出的时候,merge两部分数据:如只有b,就通过b生成a,如果只有a,就直接输出,否则就以b优先,和现有的a比较,生成新的a然后输出
        这样做的目的是,实际上现在很多数据get回来之后只是pass给别人,或者自己只用一两项,所以没有必要全部parse出来,另外如果只有10个以下的attribut实际上直接查找比建立hash或者list还要快
    5.3.为了优化查找,可以考虑生成的数据包里面的数据已经通过排序或者hash的规则放置:
        因为毕竟打包的操作肯定是最少的,所以这个地方的处理复杂也是可以理解的:
        考虑按hash放置,提供一个hash的index在整个attributeset前面,然后可以直接根据hash找到对应的列表然后顺序查找(打包的数据分成桶,由于数据是每次打包完成,所以不需要太复杂的管理,否则就变成DB了:))
        考虑按key排序,同时每一个Attribute附上二分查找需要的信息(其实就是一些offset,保证可以找到key值为中间的那个attribute)
       
    由于我对attributeset的了解有限,所以希望你对我上面说的东西提提意见,最好是提出更新的想法

Wooce:

1.  在打包数据里 lookup的时侯我们执行的是strstr,  并不是strcmp,  ,      我测试了一下,     已经有char p[1024]; 的情况,  p1 = new char[1024]; memcpy(p1,p)的开销不见得比strstr( p,  "...")的开销高,   特别是所lookup的字符串是在char p[1024]; 的后半段或者根本不存在的情况,    所以lookup执行strstr的开销也不能忽视,   不过幸好打包数据的格式是keyname1  ->    value1.size   ->    value1.content   -> ....  ,  所以我们可以凭借value1.size 移动跳过一大段数据,  只会比较keyname,   而不是strstr( 打包数据,key)这么做,    所以你说的节约parse的开销还是有效的.

2.   同时存在两种态性的数据的想法的确很有创造性,    //admire. 
     1)   这想法应该确能起到优化性能的作用.
     2)  存在以下复杂性:
         a.   嵌套情况,  即一个attributeset里面有另一个attributeset作为其attribute的情况. 
         b.   方便管理的结构b如果象TAttributeSet那么以HASH存储,  可能往b里存数据后,  需要处理一个不完整的树的情况.  虽然很少出现, 但既然没有做限制,
       我们就必须对其做出考虑.

3.    现在的协议的打包数据是按      keyname1  ->    value1.size   ->    value1.content   ->    keyname2   -> value2.size   ->    value2.content ....  的形式依次存储的,  本来keyname等本身就是作为索引的,   现在这样的打包方式, 使我们不知道这些keyname本身的位置,   所以你又提出来在整个打包数据前面再加一个这些keyname的hash索引的方法.   
       其实我想,    可以干脆把打包数据分成纯粹的索引和纯粹的attribute value数据两部分. 
       即:      打包数据  =  [索引][纯数据]
                 索引  =  keyname1  offset1  keyname2  offset2  .....     
                 纯数据 =  value1.content   value2.content   value3.content   ......
      索引的keyname1 offset1 .....   的前面是仍然可以再加上你所说的HASH索引的.
      这样带来的好处:  
           1)  接收attributeset方可以快速获得一个长度不会太大的包含了所有keyname和其offset的索引数据,  不会出现在一个很大的打包数据里移动的情况(在put了落入同一HASH桶的多个keyname进去attributeset的情况会如此).    这样你所说的5.1的使用限制应该可以避免. 
           2)  接收attributeset方要修改attributeset,  再put入新的attribute到其中的情况,   很显然,   在考虑按key排序的时侯,   我们在上面所说的索引数据中排序, 并且把新put入的值简单直接加到纯数据段的后面,    要比把一个key和value混合间杂的数据重新组织排序容易得多,  也会有较好的性能.
           3)  发送attributeset方以put多次创建一个 attributeset的时侯,   如果以原来的格式,  我们可以知道必须把每次put入的数据先clone进"易管理的结构b",   最后打包的时侯又必须依次从"易管理的结构"里取出来clone到生成的打包数据里面,     而按纯索引和纯数据分开的格式,  我们每次put入的数据是可以一次性直接clone进最后所生成的打包数据的.    所以又节省了一笔开销.  
           4)   在嵌套的情况,    我们仍然可以把索引定义成比较线性化的规整的形式.   使编程简单.