标签: loop-unrolling

我看到 Duff 的设备只是在 C 中进行循环展开。

https://en.wikipedia.org/wiki/Duff%27s_device

我不知道为什么它现在仍然有用。编译器不是应该足够聪明来进行循环展开吗？

免责声明:我对ghc编译管道知之甚少,但我希望通过这篇文章了解更多关于它的信息,例如,如果将命令与功能进行比较与代码编译相关.

如您所知,循环展开通过复制其中的代码来减少循环中的迭代次数.这提高了性能,因为它减少了跳转次数(以及与之相关的惩罚)和AFAIR,创建了更大的代码块,为更好的寄存器重命名优化留出了空间.

我想知道,是否可以使用Loop Unrolling进行函数式编程？我们可以"展开"一个函数,打开/扩展它的定义,首先减少对所述函数的调用次数和/或创建更大的代码块 - 然后为更多的代码重写优化留出空间(比如寄存器重命名,或者一些FP)当量)？

可以"展开"或"扩展"函数定义的东西,例如使用函数评估(可能与某种策略混合),以便在空间与时间之间进行权衡.

我想到的一个例子:

 map1 _ [] = []
 map1 f (x:xs) = (f x): map f xs

将展开

map2 _ [] = []
map2 f (x:x1:xs) = (f x):(f x1):map2 f xs
map2 f (x:xs) = (f x): map2 f xs

再一次:

map4 _ [] = []
map4 f (x:x1:x2:x3:xs) = (f x):(f x1):(f x2):(f x3):map4 f xs
map4 f (x:x1:x2:xs) = (f x):(f x1):(f x2):map4 f xs
map4 …

我对在编译时循环展开的一般解决方案感兴趣(我在SIMD设置中使用它,其中每个函数调用需要特定数量的时钟周期,并且多个调用可以并行执行,所以我需要调整数字使用累加器来减少浪费的周期 - 添加额外的累加器并手动展开会产生显着的改进,但是很费力).

理想情况下,我希望能够写出类似的东西

unroll<N>(f,args...); // with f a pre-defined function
unroll<N>([](...) { ... },args...); // using a lambda

并生成以下内容:

f(1,args...);
f(2,args...);
...
f(N,args...);

到目前为止,我有三个不同的模板元程序解决方案,我想知道不同方法的优点/缺点是什么,特别是关于编译器如何内联函数调用.

方法1(递归函数)

template <int N> struct _int{ };

template <int N, typename F, typename ...Args>
inline void unroll_f(_int<N>, F&& f, Args&&... args) {      
    unroll_f(_int<N-1>(),std::forward<F>(f),std::forward<Args>(args)...);
    f(N,args...);
}
template <typename F, typename ...Args>
inline void unroll_f(_int<1>, F&& f, Args&&... args) {
    f(1,args...);
}

调用语法示例:

int x = 2;
auto mult = [](int n,int x) { std::cout << n*x …

我在 C 中有这种 Duff 的设备，它工作正常（将文本格式设置为货币）：

#include <stdio.h>
#include <string.h>

char *money(const char *src, char *dst)
{
    const char *p = src;
    char *q = dst;
    size_t len;

    len = strlen(src);
    switch (len % 3) {
        do {
            *q++ = ',';
            case 0: *q++ = *p++;
            case 2: *q++ = *p++;
            case 1: *q++ = *p++;
        } while (*p);
    }
    *q++ = 0;
    return dst;
}

int main(void)
{
    char str[] = "1234567890123";
    char res[32];

    printf("%s\n", money(str, res));
    return 0;
} …

有没有办法“元编程”获得具有以下结构的代码块：

if r1 < R1
   s = 1

   elseif r1 < R2
      s = 2

      ... etc until N

   end
end

谢谢！

我有一个CUDA内核,有一堆我想要展开的循环.现在我做:

void mykernel(int* in, int* out, int baz) {    
    #pragma unroll
    for(int i = 0; i < 4; i++) {
        foo();
    }
    /* ... */
    #pragma unroll
    for(int i = 0; i < 6; i++) {
        bar();
    }
}

等等.我想告诉(提示)我的C/C++编译器展开所有这些循环,而不需要为每个循环单独提示.但是,我不希望在该函数中展开文件中所有代码中的所有循环.

如果这是GCC,我可以这样做:

__attribute__((optimize("unroll-loops")))
void mykernel(int* in, int* out, int baz) {    
    for(int i = 0; i < 4; i++) {
        foo();
    }
    /* ... */
    for(int i = 0; i < 6; i++) {
        bar();
    }
}

或者使用选项push-and-popping.我能用CUDA做些什么吗？

如果我调用该函数

/** Check if all Elements, possibly recursively, of $(D x) are zero. */
bool allZero(T)(in T x) @safe pure nothrow {
    import std.range: isIterable;
    static if (isIterable!T) {
        foreach (ref elt; x) {
            if (!elt.allZero) { return false; }
        }
        return true;
    } else {
        return x == 0;
    }
}

使用静态数组,D会foreach在发布模式下自动为我展开吗？

如果不能

/** Static Iota. */
import std.typetuple: TypeTuple;
template siota(size_t from, size_t to) { alias siotaImpl!(to-1, from) siota; }
private template siotaImpl(size_t to, size_t now) …

想象一下下面的代码：

for (int i = 0; i < 8; ++i) {
    // ... some code
}

我希望这个循环在 MSVC 中展开。在 CLang 中我可以添加#pragma unrollbefore 循环。但是在 MSVC 中如何做同样的事情呢？

我知道无论如何编译器通常会为我展开这个循环，即使没有任何编译指示。但我想真正确定这一点，我想总是展开它。

当然，强制展开的一种方法是使用传入函子的模板化展开函数的递归调用，如以下代码所示：

在线尝试一下！

template <int N, int I = 0, typename F>
inline void Unroll(F const & f) {
    if constexpr(I < N) {
        f.template operator() <I> ();
        Unroll<N, I + 1>(f);
    }
}

void f_maybe_not_unrolled() {
    int volatile x = 0;
    for (int i = 0; i < 8; ++i)
        x = …

我想知道无论我使用哪种编译器,以下两个实现是否会产生完全相同的性能:

template<class T, unsigned int TSIZE> MyClass1
{
    static const unsigned int size_const = 0;
    public:
        inline void Loop()
        {
            for(unsigned int i = 0; i < TSIZE; ++i) {
                /* DO SOMETHING ON DATA */
            }
        }
        T _data[TSIZE];
};

template<class T, unsigned int TSIZE> MyClass2
{
    static const unsigned int size_const = TSIZE;
    public:
        inline void Loop()
        {
            for(unsigned int i = 0; i < size_const; ++i) {
                /* DO SOMETHING ON DATA */
            }
        }
        T _data[size_const]; …

试图优化fun_a1()功能.变量j的范围不会改变fun_a1().因此,对于每个'i'迭代检查j == 1或2或3显然是浪费CPU周期.但是如果我尝试将条件评估带到循环之外,我必须为每个条件编写冗余循环.在C中,我可以通过使用函数指针轻松解决这个问题.但是,C++不允许指向非静态函数.我找到了一些描述神秘的"指向成员指针"的链接.(示例1,示例2)但是我仍然不清楚如何从对象本身内部使用它,例如从fun_a()里面？或者它可以以任何其他方式进行优化？

class A{
    void fun_b(int i);

    void fun_c(int i);

    void fun_d(int i);

    void fun_f(int i);

    void fun_a1(int j){

        for(int i=0; i<1000; i++){

                 if(j==1) fun_b(i);
            else if(j==2) fun_c(i);
            else if(j==3) fun_d(i);

            fun_f(i);           
        }

    }


    void fun_a2(int j){

        if(j==1){           
            for(int i=0; i<1000; i++) { 
                fun_b(i); 
                fun_f(i); 
            }
        }
        else if(j==2){          
            for(int i=0; i<1000; i++) { 
                fun_c(i);
                fun_f(i);
            }            
        }
        else if(j==3){
            for(int i=0; i<1000; i++) { 
                fun_d(i);           
                fun_f(i);
            }           
        } …

更新:

这个讨论比我预期的要进一步,所以当我将这个问题突然出现在脑海中的时候,我正在用我正在处理的代码更新这个.这是一个8到16行代码之间的决定,以确定谁是我的c ++课程入门的井字游戏的赢家.

注意:这是为了与课程在同一水平,

注2:标记是字符x或o或'')

这是一个优化问题.如果这是一个重复,我道歉但我找不到其他地方的答案.

基本上,它归结为以下代码是否会更好地循环:

    char CheckForWinner() {

    //returns the token of the player that satisfies one of the winning requirements
    if (Square[0][0] == Square[0][1] && Square[0][0] == Square[0][2] ) { //If all three tokens in the first row are the same
        return Square[0][0]; //Return the token
    } else if (Square[1][0] == Square[1][1] && Square[1][0] == Square[1][2] ) { //Check the next row
        return Square[1][0]; //Return the token
    } else if (Square[2][0] == Square[2][1] && Square[2][0] …