持久化的多键映射,使用BerkeleyDB
如前介绍,相当于 std::map<Key1,std::map<Key2,Data> >,但接口也不完全相同,这里只贴代码: 继续阅读
如前介绍,相当于 std::map<Key1,std::map<Key2,Data> >,但接口也不完全相同,这里只贴代码: 继续阅读
使用前面介绍的序列化框架,可以非常简单地将Bekeley DB作为存储层,实现一个易于使用的,强类型的,持久化的map。
这个设计的的基本原则就是:模板作为一个薄的、类型安全的包装层,实现层的代码可以多个模板实例来公用,这样不但加快了编译时间,也减小了生成的代码尺寸。 继续阅读
迄今为止,我还没找到更优雅、更高效的 C++ 序列化方案,包括但不限于 boost.serialization。如果你发现了更快的,或者更易用的C++原生序列化,请告诉我…… 继续阅读
如果一个任务的执行分多个步骤,有些步骤慢,有些步骤快,如果在处理时间长的步骤上使用更多线程,那么因为队列的缓冲作用,在平均处理时间上,这些步骤就可以大致持平了,从而导致更大的吞吐量。
我所了解的泛型实现,也就C++和Java,C++靠的是用代码膨胀来满足性能,Java泛型则只是一个Sugar。
现在使用C++泛型的人越来越多,生成的程序体积也越来越大。一个对10种数据和10种算子使用了泛型算法的程序,代码膨胀的最大可以达到100倍。但实际上,生成的代码“很模板”。现在的C++还没有C++0x 的 closure/auto 等功能,代码膨胀已经达到了很恐怖的程度。——比如使用了 Boost.asio 的程序尺寸就很恐怖。
现在,代码膨胀虽然已经是一个很引起大家注意的问题,但是还没有让大家足够注意。虽然有一些减少代码重复的技巧,但那只是技巧而已,对问题的映射不是很直接,有一定难度,不能得到大范围的应用。可以预见,等到C++0x出世,泛型的语法更加优美,使用更加方便,大家的积极性更高,到那时,代码膨胀可能会成为一个非常残酷的现实问题。
应该有一些途径减少代码膨胀,现代的虚拟机(例如Java虚拟机和.Net虚拟机)可以通过动态优化来提高程序性能,先在运行时解释执行ByteCode,当发现某段ByteCode的执行频率太高时将它优化成NativeCode,这是一种很好的解决方案,虽然在解释执行时增加了程序计数的开销,但这是微不足道的。静态编译语言如C++能否吸收它的优点呢?
我觉得也许可以,但是代价可能比较高。比如对同一个泛型算法实例化100次时,是否可以只生成一个内部框架,而在运行时,用到了哪个实例,再实例化那个泛型算法,也就是运行时由RuntimeEnv按需动态生成NativeCode,而不是在编译时一次生成。对于泛型类型,也类似。实际上,也许有些泛型算法的实例根本不会在执行路径上出现,但是静态编译却必须为它生成代码。
一个简单例子:有很多个html网页,网页的id、title、url、path等信息存在一个数据库表中,网页内容存储在一个磁盘阵列上。现在要把所有网页都读出来,统计其中的html标签、正文等信息,并写入另一个数据库表,怎样的设计最好呢? 继续阅读
C++ 现在最时髦的用法是 template meta programming。booster 们对此非常津津乐道,我本人也是个狂热的booster。到了什么程度?不使用template 就浑身不舒服,不boost一下就感觉对不起C++。但是这种狂热带来的严重后果就是程序编译速度极慢无比,生成的执行程序尺寸超常。
曾经一个 C++ 服务器程序,代码也就10000行左右,编译出来的执行程序竟然20M!编译时间半小时!写的时候感觉不到用了多少template,但是写出来竟然得到这样的结果,不得不让人吃惊!
记得在大学的时候(2000年前后),初学习 template 时,感觉template之间的耦合有点“过于松散”,就像只要有一个螺母,再一个螺栓,就可以往一起套,而不管他们是否一个是塑料,一个是金属,大小粗细是否匹配,螺距是否匹配,所有的这一切,如果只有哪怕一点点不匹配,都会在编译错误中造成一个非常令人费解的超长消息。当初也不知道这一点早已被无数人诟病了,就写了一片文章,自作聪明地提出应该对模板参数有个类似接口声明一样的规格定义(现在C++0x 中的对应物是concept)。当初立即招致骂声一片。现在这一点已经毋庸置疑了,C++0x出世后我们就可以结束这些痛苦了。
但是,前面说的C++的那两个致命缺点,看来短期内很难克服。
编译时间,受制于文件包含这种古老的内存不够用的时代的无奈选择,就像人的阑尾,喉头,视网膜。
程序尺寸,这个缺陷在某些时候也非常致命,举个简单例子,std::sort 使用了多种排序策略,每个sort 的机器码都很大。同时,对每一种数据类型,每一种randiter每一种comparator,都会生成一个sort 的版本,这会造成非常大的代码膨胀。相比之下,C 的 qsort 就没有这种缺陷。如果我们对几十种数据,使用几十个comparator排序,std::sort 的代码尺寸比 qsort 要大几十倍。虽然它在inline方面获得了优势,但是cpucache的失效,甚至是memcache的失效,造成的性能损失要大得多。BS在TCPL中提到的消除代码膨胀的方法,在某些情况下的确有用,但是太繁琐,大约也只有库编写者会使用它。
Java现在也支持泛型,据说不存在代码膨胀问题,但它的泛型只是语法糖,对程序性能好像没有提升。
C++ 怎样平衡代码膨胀和代码性能?是否可以为 template 生成 runtime meta info,用来操纵泛型算法。或甚至使用这些meta info 来在运行时生成真正的机器码。这样甚至可以允许在运行时进行template组装,而不是完全在编译时?这又有些类似于现代虚拟机(如Java HotSpot 虚拟机)的动态优化。
扯太远了,休息下。
– 共有 n 个内部结点,n 个外部结点
– winner 只用于初始化时计算败者树,算完后即丢弃
– winner/loser 的第 0 个单元都不是内部结点,不属于树中的一员
– winner 的第 0 个单元未用
– m_tree 的第 0 个单元用于保存最终的赢者, 其它单元保存败者
– 该初始化需要的 n-1 次比较,总的时间复杂度是 O(n)
– 严蔚敏&吴伟民 的 LoserTree 初始化复杂度是 O(n*log(n)),并且还需要一个 min_key,
但是他们的初始化不需要额外的 winner 数组
– 并且,这个实现比 严蔚敏&吴伟民 的 LoserTree 初始化更强壮
其中引用的一些代码比较长,故未贴出
使用示例:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 |
/** @brief 生成一个比较器(Comparator),兼键提取(KeyExtractor)类 使用这个宏生成的比较器可以作用在不同的对象上,只要这些对象有相同名称的成员, 并且可以作用在类型为成员类型的对象上。 - 假设: - 有 n 个类 class[1], class[2], ... class[n],都有类型为 MemberType ,名称为 MemberName 的数据成员 - 那么以下类型的对象可以使用该类相互比较,并且可以从这些对象中提取出 MemberType 类型的键: class[1] ... class[n], MemberType, 以及所有这些类型的任意级别的指针 @param ComparatorName 比较器类的名字 @param MemberType 要比较的对象的成员类型 @param MemberName 要比较的对象的成员名字,也可以是一个成员函数调用, 前面必须加 '.' 或者 '->', 加 '->' 只是为用于 smart_ptr/iterator/proxy 等重载 '->' 的对象 当用于裸指针时,仍使用 '.',这意味着裸指针和 smart_ptr/iterator/proxy 不能使用同一个生成的 Comparator,虽然裸指针的语法和它们都相同 @param ComparePred 比较准则,这个比较准则将被应用到 XXXX MemberName @note - 这个类不是从 ComparePred 继承,为的是可以允许 ComparePred 是个函数, 但这样(不继承)阻止了编译器进行空类优化 - 不在内部使用 const MemberType&, 而是直接使用 MemberType, 是为了允许 MemberName 是一个函数时,返回一个即时计算出来的 Key; - 当为了效率需要使用引用时,将 const MemberType& 作为 MemberType 传进来 - 当 MemberType 是个指针时,将 Type* 作为 MemberType ,而非 const Type*,即使 MemberType 真的是 const Type* - 注意 C++ 参数推导机制: @code template<T> void f(const T& x) { } // f1 template<T> void f(const T* x) { } // f2 template<T> void g(const T& x) { } // g1 template<T> void g(const T* x) { } // g2 template<T> void g( T& x) { } // g3 template<T> void g( T* x) { } // g4 void foo() { int a; const int b; f(&a); // call f1, T was deduced as int*, and then convert to 'const int*&', so match f1, not f2 f(&b); // call f2, T was deduced as int g(&a); // call g4, T was deduced as int g(&b); // call g2, T was deduced as int } @endcode 在上述代码已经表现得比较明白了,这就是要生成四个不同 deref 版本的原因 - 为了配合上述机制,传入的 MemberType 不要有任何 const 修饰符 */ #define SAME_NAME_MEMBER_COMPARATOR_EX(ComparatorName, MemberType, MemberName, ComparePred) / class ComparatorName / { / ComparePred m_comp; / public: / typedef bool result_type; / typedef MemberType key_type; / typedef boost::integral_constant<bool, / febird::HasTriCompare<ComparePred>::value / > has_tri_compare; / / ComparatorName() {} / ComparatorName(const ComparePred& rhs) / : m_comp(rhs) {} / / template<class T>const T&deref(T*x)const{return*x;} / template<class T>const T&deref(T&x)const{return x;} / template<class T>const T&deref(const T*x)const{return*x;}/ template<class T>const T&deref(const T&x)const{return x;}/ / const MemberType operator()(const MemberType x)const{return x;} / template<class T>const MemberType operator()(const T&x)const{return deref(x)MemberName;}/ / template<class Tx, class Ty> / bool operator()(const Tx&x, const Ty&y) const / { / return m_comp((*this)(x),(*this)(y)); / } / template<class Tx, class Ty> / int compare(const Tx&x, const Ty&y) const / { / return m_comp.compare((*this)(x),(*this)(y)); / } / }; //~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ #endif // #define SAME_NAME_MEMBER_COMPARATOR_EX(ComparatorName, MemberType, MemberName, ComparePred) / // SAME_NAME_MEMBER_COMPARATOR_EX_NO_TRAITS(ComparatorName, MemberType, MemberName, ComparePred)/ // BOOST_TT_AUX_BOOL_TRAIT_SPEC1(HasTriCompare, ComparatorName, HasTriCompare<ComparePred>::value) //! note@ if MemberType must not be a reference, neither const nor non-const #define SAME_NAME_MEMBER_COMPARATOR(ComparatorName, MemberType, MemberName) / SAME_NAME_MEMBER_COMPARATOR_EX(ComparatorName, MemberType, MemberName, std::less<MemberType>) |
用C++写程序经常需要写一些很小的functor,最常见的例子就是 compare functor,排序的,查找的,自己每定义一个数据结构,就要定义一个 compare functor,甚至多个(对不同字段)。甚至,针对指针的,智能指针的……的compare,这件工作很繁琐,很容易使人厌倦。
举个例子,同一个数据结构有M个字段,这些字段有P种类型,还有有N种不同的访问方式(直接提取、通过指针、通过智能指针、甚至通过反序列化等等),要实现所有这些情况的查找/排序,就需要 M×N 个 compare functor 的定义!
从 boost::multi_index 中学到一点,将 KeyExtractor 和 Comparator 分离,这样,只需要写 P 个Comparator,M+N个KeyExtractor,一般情况下,甚至不需要写Comparator,因为字段类型大多是内建类型,Comparator是默认的。举个例子吧:
using namespace std;
using boost::shared_ptr;
//using boost::intrusive_ptr;
struct mydata
{
int d1, d2, d3, d4, d5;
string s1, s2, s3;
};
struct mydata_get_int
{
int offset;
mydata_get_int(int offset) : offset(offset) {}
int operator()(const mydata& x) const
{
return *(int*)(offset + (unsigned char*)&x);
}
// 假定T 就是mydata* 或者智能指针
template<class T>
int operator()(const T& x) const
{
return *(int*)(offset + (unsigned char*)&(*x));
}
};
struct mydata_get_str
{
int offset;
mydata_get_str(int offset) : offset(offset) {}
const string& operator()(const mydata& x) const
{
return *(string*)(offset + (unsigned char*)&x);
}
// 假定T 就是mydata* 或者智能指针
template<class T>
const string& operator()(const T& x) const
{
return *(string*)(offset + (unsigned char*)&(*x));
}
};
class ExtractCompare
{
KeyExtractor m_extractor;
KeyCompare m_comp;
public:
ExtractCompare(const KeyExtractor& ext = KeyExtractor(),
const KeyCompare& comp = KeyCompare())
: m_extractor(ext), m_comp(comp) {}
template<class T1, class T2>
bool operator()(const T1& t1, const T2& t2) const
{
return m_comp(m_extractor(t1), m_extractor(t2));
}
};
int main(int argc, char* argv[])
{
vector<mydata> v1;
vector<mydata*> v2;
vector<shared_ptr<mydata> > v3;
//vector<intrusive_ptr<mydata> > v4;
// …. fill some data to v1, v2, v3
sort(v1.begin(), v1.end(), make_ec(mydata_get_int(FIELD_OFFSET(mydata, d1)), less<int>()));
sort(v2.begin(), v2.end(), make_ec(mydata_get_int(FIELD_OFFSET(mydata, d2)), less<int>()));
sort(v3.begin(), v3.end(), make_ec(mydata_get_str(FIELD_OFFSET(mydata, s3)), less<string>()));
return 0;
}
其中的ExtractCompare和make_ec可以作为公用代码,在多个程序中使用。
使用FIELD_OFFSET,在不降低效率的前提下,避免了代码膨胀。当然,这个例子中因为vector元素类型不同,会生成sort的3个不同版本,但是,如果不使用FIELD_OFFSET,而是直接再写一个extractor,这里会生成sort的4个版本。当然,一般情况下,不会像这样同时使用三个不同类型的vector。
C++0X 问世以后,其中的closure功能或许会使得这种方法显得过时,但是在没有closure的当前编译器上,这种方法还是很实用的。