用于 x86 和 +1 移位的快速 memmove（用于移到前面变换）
对于快速 MTF ( http://en.wikipedia.org/wiki/Move-to- front_transform ）我需要更快的版本将一个字符从数组内部移动到它的前面：
char mtfSymbol[256], front;
char i;
for(;;) { \\ a very big loop
...
i=get_i(); \\ i is in 0..256 but more likely to be smaller.
front=mtfSymbol[i];
memmove(mtfSymbol+1, mtfSymbol, i);
mtfSymbol[0]=front;
}
cachegrind显示，对于memmove来说，这里有很多分支错误预测。
对于代码的其他版本（不是第一个示例中的 memmove，而是这个），
do
{
mtfSymbol[i] = mtfSymbol[i-1];
} while ( --i );
有很多字节读/写、条件分支和分支错误预测
i 不是很大，因为它是用于“良好”输入的 MTF -经过 BWT（Burrows–Wheeler 变换）编译器后的文本文件
是 GCC。
For fast MTF ( http://en.wikipedia.org/wiki/Move-to-front_transform ) i need faster version of moving a char from inside the array into the front of it:
char mtfSymbol[256], front;
char i;
for(;;) { \\ a very big loop
...
i=get_i(); \\ i is in 0..256 but more likely to be smaller.
front=mtfSymbol[i];
memmove(mtfSymbol+1, mtfSymbol, i);
mtfSymbol[0]=front;
}
cachegrind shows, that for memmove there are lot of branch mispredictions here.
For the other version of code (not a memmove in the first example, but this one)
do
{
mtfSymbol[i] = mtfSymbol[i-1];
} while ( --i );
there are lot of byte reads/writes, conditional branches and branch mispredictions
i is not very big, as it is MTF used for "good" input - a text file after a BWT ( Burrows–Wheeler transform )
Compiler is GCC.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（2）
如果您预先分配的缓冲区大于您需要的大小，并将初始数组放在中间的某个位置（或者放在最后，如果您永远不需要以这种方式扩展它），那么您可以附加通过更改数组开头的地址而不是移动所有元素来更改项目（最多可达限制）。
显然，您需要跟踪您向后移动了多远，因此，如果您确实超出了现有分配的开始位置，则可以重新分配，但这仍然比移动所有数组条目要快。
If you pre-allocate your buffer bigger than you're going to need it, and put your initial array somewhere in the middle (or at the end, if you're never going to have to extend it that way) then you can append items (up to a limit) by changing the address of the start of the array rather than by moving all the elements.
You'll obviously need to keep track of how far back you've moved, so you can re-allocate if you do fall off the start of your existing allocation, but this should still be quicker than moving all of your array entries around.
您还可以使用专用数据结构而不是数组来加速正向变换。
可以使用链表列表构建快速实现，以避免数组元素完全移动。
请参阅 http://code.google。 com/p/kanzi/source/browse/java/src/kanzi/transform/MTFT.java
对于逆变换，事实证明数组与链表一样快。
You can also use a dedicated data structure rather than an array to speed up the forward transform.
A fast implementation can be built with a list of linked lists to avoid the array element moves altogether.
See http://code.google.com/p/kanzi/source/browse/java/src/kanzi/transform/MTFT.java
For inverse transform, it turns out that arrays are as fast as linked lists.