技术头条 - 一个快速在微博传播文章的方式     搜索本站
您现在的位置首页 --> 算法 --> 数组的优化循环展开与分割

数组的优化循环展开与分割

浏览:2491次  出处信息

    数组的循环与分割, 利用了计算机系统的两个特点:

    1. 有多块高速缓存;

    2. Cpu是可以多指令并行执行(要求多条指令之间 没有数据相关性)。

    在我们的例子中:

    数组切分: 将1个数组切分为2个数组。 这样就能用2块高速缓存来存数据 , 高速缓存的访问速度是内存的 10倍以上

    循环展开: 我们将的步进设置为4,每次处理的数据之间 没有任何关系,这样就能并行执行起来。

    数据无关性: 就是下一次计算指令不受之前执行指令的结果影响。在我们的例子里面, 将对 i 的操作 提到前面, 这样后面的赋值操作和i没有关系,我们再赋值的时候同时可以进行 下一次循环了。

/**
 * 批量追加 docId 到结尾
 * @param thiz
 * @param docId_arr   docid 的数组
 * @param num         数组元素个数
 * @return
 */
Ret docArray_batch_append(DocArray* thiz, UINT_32 docId_arr[], int num)
{
    return_val_if_fail(thiz != NULL && num > 0, RET_INVALID_PARAMS);
    if (LIKELY(docArray_expand(thiz, num) == RET_OK))
    {
        register int  size = thiz->size;
        register int  i    = 0;
        register int  i1   = 0;
        register int  i2   = 0;
        register int  i3   = 0;
        // 去掉后2位
        register int  bn   = (num >> 3) << 2;
        // 做循环分割和循环展开
        DOC*     data       = &(thiz->data[size]);
        // 取其中的一半, 切分成2个数组
        DOC*     data2      = &(data[bn]);
        UINT_32* docId_arr2 = &(docId_arr[bn]);
        for (i = 0; LIKELY(i < bn); i = i + 4)
        {
            data[i].docId   = docId_arr[i];
            // 特意提到前面后续的操作和i没有关系,提高并行度。
            data2[i].docId  = docId_arr2[i];
            i1 = i + 1;
            i2 = i + 2;
            i3 = i + 3;
            data[i1].docId  = docId_arr[i1];
            data[i2].docId  = docId_arr[i2];
            data[i3].docId  = docId_arr[i3];
            data2[i1].docId = docId_arr2[i1];
            data2[i2].docId = docId_arr2[i2];
            data2[i3].docId = docId_arr2[i3];
        }
        for (i = (bn << 1); i < num; ++i)
        {
            data[i].docId = docId_arr[i];
        }
        thiz->size = size + num;
    }
    return RET_OK;
}

建议继续学习:

  1. 在C++中实现foreach循环,比for_each更简洁!    (阅读:8629)
  2. 为什么数组标号是从0开始的?    (阅读:4940)
  3. C语言结构体里的成员数组和指针    (阅读:4855)
  4. 将数组定义为常量    (阅读:4566)
  5. for 循环为何可恨?    (阅读:4459)
  6. 循环、迭代、遍历和递归    (阅读:4454)
  7. C/C++循环获取文件中的每行数据(别以为很简单!)    (阅读:3882)
  8. Tips of Linux C programming    (阅读:3966)
  9. xml转数组的方法    (阅读:3494)
  10. javascript扩展Array(数组)类    (阅读:3236)
QQ技术交流群:445447336,欢迎加入!
扫一扫订阅我的微信号:IT技术博客大学习
后一篇:Treelink算法介绍 >>
© 2009 - 2024 by blogread.cn 微博:@IT技术博客大学习

京ICP备15002552号-1