什么是“Nabialek trick”？
现在是时候了，经过这些天的学习和尝试，我终于知道boost.spirit里谈到的Nabialek trick是什么东西了，当然应该大方的与大家分享。
这个Nabialek trick其实并不是编译期间的技巧，而是利用查表的方式将一些静态的类型推导变成简单的运行时调用，用性能损失换取编译期间的复杂，是一种相反的过程。可以说，Nabialek trick给人的感觉是完完全全的没有意义，要知道C++的template就是为了提升运行时性能而增加编译期间运算，这个反其道而行意义何在？其实说白了，意义就在于：消除模板技巧带来的疯狂的自动类型推导，以及解除对某些类型的静态绑定。前者意义在于可以提升编译速度，而且也可以避免达到模板嵌套上限（比如MSVC 7.1，最多只能嵌套256层，这已经算不错了），后者意义在于可以让复杂的表达式变得更容易匹配、更快的执行和更加灵活（所谓的将“线性非决定式”转化为“决定式”，将“或”逻辑从表达式中剔除，避免不必要回溯以加快速度），但是由于创建查找表的过程涉及到内存分配，所以后者并不能总是达到很好效果。
我们再从正面来想想Expression Templates给编程带来的困难，请看下面的示例代码（来自boost.spirit的帮助/libs/spirit/doc/techniques.html，我做了一些简化和修改）：
r =
"//" >> *(anychar_p - 'n') >> 'n'
| "/*" >> *(anychar_p - "*/") >> "*/"
;
在这里，r的类型就是：
alternative<sequence<sequence<strlit<const char*>, kleene_star<difference<anychar_parser, chlit<char> > > >, chlit<char> >, sequence<sequence<
strlit<const char*>, kleene_star<difference<anychar_parser, strlit<const char*> > > >, strlit<const char*> > >
是的，我没指望任何人能够看懂……不过假如做一下的赋值：
line1 = "//" >> *(anychar_p - 'n') >> 'n';
line2 = "/*" >> *(anychar_p - "*/") >> "*/";
r = line1 | line2;
这样的代码应该好理解一些，但是没有本质不同。再来改改：
line1 = "//" >> *(anychar_p - 'n') >> 'n';
line2 = "/*" >> *(anychar_p - "*/") >> "*/";
some_helper helper; // some_helper并不是boost.spirit的类，是我虚构出来的。
helper.add("//", &line1);
helper.add("/*", &line2);
r = helper;
这里可以清晰地看到，只要这个some_helper的add()能够支持line1和line2类型，并且line1和line2的类型都实现了一个公共的抽象接口，那么r的类型就很单纯了。不过boost.spirit出于各种考虑，整个类体系非常复杂，包括rule<>、parser<>、abstract_parser<>、sequence<>等，它们的关系我花了好几天终于弄明白了，不过要说清楚恐怕还要花费写口舌，我等以后有时间以后再来详细介绍吧。
有了这个helper（在boost.spirit里面实际上是symbols<>），我们就可以抛弃“或”逻辑，表达式匹配也就没有回溯的问题，提高匹配的速度。同时可以看出，这种“优化”在很大程度上似乎并不是特别必要，毕竟Expression Templates是可以在编译期间决定这种优化方式的（甚至于可以通过模板的偏特化优化运算顺序），所以我真的觉得这种技巧在这种应用环境里面恐怕不会存在太久……
有话想说？请留下评论吧~~如果喜欢我的blog，欢迎订阅~~
评论
还没有任何评论。
留下评论