Why does loop fission make sense in this case?
The code without fission looks like this:
    
    int check(int * res, char * map, int n, int * keys){
        int ret = 0;
        for(int i = 0; i < n; ++i){
            res[ret] = i;
            ret += map[hash(keys[i])]
        }
        return ret;
    }

With fission:

    int check(int * res, char * map, int n, int * keys){
        int ret = 0;
        for(int i = 0; i < n; ++i){
            tmp[i] = map[hash(keys[i])];
        }
        for(int i = 0; i < n; ++i){
            res[ret] = i;
            ret += tmp[i];
        }
        return ret;
    }


Notes:

- The bottleneck is map[hash(keys[i])] which accesses memory randomly.

- normally, it would be <i>if(tmp[i]) res[ret++] = i;</i> to avoid the if, I'm using <i>ret += tmp[i]</i>

The fission version is usually significantly faster and I am trying to explain why. My best guess is that <i>ret += map[..]</i> still introduces some dependency and that prevents speculative execution.

I would like to hear if anyone has a better explanation.
Why does loop fission make sense in this case?
===

The code without fission looks like this:
    
    int check(int * res, char * map, int n, int * keys){
        int ret = 0;
        for(int i = 0; i < n; ++i){
            res[ret] = i;
            ret += map[hash(keys[i])]
        }
        return ret;
    }

With fission:

    int check(int * res, char * map, int n, int * keys){
        int ret = 0;
        for(int i = 0; i < n; ++i){
            tmp[i] = map[hash(keys[i])];
        }
        for(int i = 0; i < n; ++i){
            res[ret] = i;
            ret += tmp[i];
        }
        return ret;
    }


Notes:

- The bottleneck is map[hash(keys[i])] which accesses memory randomly.

- normally, it would be <i>if(tmp[i]) res[ret++] = i;</i> to avoid the if, I'm using <i>ret += tmp[i]</i>

The fission version is usually significantly faster and I am trying to explain why. My best guess is that <i>ret += map[..]</i> still introduces some dependency and that prevents speculative execution.

I would like to hear if anyone has a better explanation.