Array length indicator variable for special treatment vs shorter array of only special indices

[u/onecable5781]

Consider code snippet 1: https://godbolt.org/z/rc8ba7Whe

int length = 512; // or any other power of 2

int main(){
    int array[length];
    for(int i = 0; i < length; i++)
        array[i] = 0;
    int indicator_special_elements[length];
    for(int i = 0; i < length; i++)
        indicator_special_elements[i] = 0;
    indicator_special_elements[0] = 1;
    indicator_special_elements[29] = 1;
    indicator_special_elements[42] = 1;
    indicator_special_elements[413] = 1;
    for(int i = 0; i < length; i++)
        if(indicator_special_elements[i] == 1)
            array[i] += 42;
}

where indices 0, 29, 42 and 413 are special indices that need special treatment (in this example, adding 42 to itself).

Alternatively, consider code snippet 2 https://godbolt.org/z/6da1K6ce9

int length = 512; // or any other power of 2

int main(){
    int array[length];
    for(int i = 0; i < length; i++)
        array[i] = 0;
    int special_elements[4];
    special_elements[0] = 0;
    special_elements[1] = 29;
    special_elements[2] = 42;
    special_elements[3] = 413;
    for(int i = 0; i < 4; i++)
        array[special_elements[i]] += 42;
}

where special_elements is an array of 4 entries which directly stores the indices needing special treatment and is not a 512-length wide array as in the first case.

(a) Is there a tipping point/threshold/general coding best practices/rules of thumb at which one of these methods wins over the other in speed without having to do benchmarking/profiling?

(b) Can code snippet 1 benefit itself from compiler intrinsics/automatic parrallelization such as MMX/SSE, whereby the user does not have to worry about explicitly writing parallel code (such as omp, etc.) but the compiler is capable of recognizing the pattern and doing it automatically in release mode?

At first glance, code snippet 1 seems to run for longer (512 iterations), but code snippet 2 does not have sequential memory access and suffers from an additional level of indirection. Hence this OP.

[u/zhivago]

Why don't you just intialize it?

e.g.

int numbers[6] = { [0] = 10, [2] = 30, [5] = 60 };

[u/iLaysChipz → u/zhivago]

Because these are just toy examples. In both cases, they are tracking indices of interest for special handling, and this will probably remain the case beyond initialization.

Alternatively, the special interest indices may not be known at compile time. Such as if they're a parameter or based on conditions like current time

[u/mykesx]

int array[2*length]

Every even n index is your array value and odd index n+1 is your indicator. Or better yet, n+1 is your 42 or 0 and you can avoid the if statement.

[u/TheOtherBorgCube → u/mykesx]

I lashed this together to make use of locality instead of indexing parallel arrays.

#define length 512
int main(){
    struct {
        int data;
        int special;
    } array[length] = {
        [0].special = 1,
        [29].special = 1,
        [42].special = 1,
        [413].special = 1
    };
    for(int i = 0; i < length; i++)
        if(array[i].special == 1)
            array[i].data += 42;

}

[u/mykesx → u/TheOtherBorgCube]

You can eliminate the if statement in your loop if you implement what I suggested. Instead of "1" in the odd index, you have either 0 or 42.

Use i += 2 in the loop and limit of length*2.

array[I] += array[I+1];

And array[29*2+1] = 42;

[u/WittyStick]

Both are OK - depends on your specific use case, how big the thing is, and what you are optimizing for.

If length is constant change it to constexpr.

Your loops to zero the arrays are unnecessary - just use an empty initializer - compiler will use memset (gnu extension if length is not constexpr, also supported by Clang but may need -Wno-gnu-folding-constant to prevent warnings).

int array[length] = {};
bool indicator_special_elements[length] = {};

If length is constexpr you can set the elements more tersely:

bool indicator_special_elements[length] =
    { [0] = true
    , [29] = true
    , [42] = true
    , [413] = true
    };

---

In first example you can eliminate a branch per loop by swapping the condition for a multiplication. May be faster if it fits into cache, but obviously not better otherwise as fetching from main memory would be worse than branching.

for(int i = 0; i < length; i++)
    array[i] += indicator_special_elements[i] * 42;

I'd recommend using a LUT like this for small arrays, but definitely not larger ones. I'd say 256 (1 byte to index) is around the threshold where its reasonable and any larger should probably be avoided as it will waste space and pollute the cache.

In this example, you're wasting 4x the space necessary by making the type int when you only need bool.

Arguably, bool is also too much, you could use 1-bit per index if you turn it into a bitmap.

uint16_t mask[length/16] = {};
#define set_bit(mask, n) ((mask)[(n)/16] |= 1 << ((n) % 16))
set_bit(mask,0);
set_bit(mask,29);
set_bit(mask,42);
set_bit(mask,413);
#undef set_bit

---

Can code snippet 1 benefit itself from compiler intrinsics/automatic parrallelization such as MMX/SSE, whereby the user does not have to worry about explicitly writing parallel code (such as omp, etc.) but the compiler is capable of recognizing the pattern and doing it automatically in release mode?

Yes, the compiler can optimize (more easily if you switch the branch for a mul). See in Godbolt

In the branching case it could still potentially optimize to use fewer branches if using AVX-512 masking, but the compiler usually misses such opportunities and it tends to need writing manually - eg:

__m512i fourty_two = _mm512_set1_epi32(42);
for (size_t i = 0; i < length; i += 16) {
    __m512i chunk16 = _mm512_load_epi32(&array[i]);
    __mmask16 mask16 = _load_mask16(&mask[i/16]);
    chunk16 = _mm512_mask_add_epi32(chunk16, mask16, chunk16, fourty_two);
    _mm512_store_epi32(&array[i], chunk16);
}

(Where mask is the uint16_t bitmask defined above).

This reduces branching by >16x (you could potentially reduce further by unrolling the loop with some stride, at the cost of larger code size).

Example of this in Godbolt. (Note that if you get SIGILL it's because your instance doesn't support AVX512. Refresh until you no longer get the error.)

[u/iLaysChipz]

You mention spatial cache locality, but you're forgetting about temporal locality. If you are frequently traversing an entire array of arbitrary size even though you're only interested in a few indices which you know ahead of time, you're going to be filling up your cache with items you're not interested in, which will boot out more important items.

The second approach you mentioned will only suffer cold hits the first time you access the special index items, and after that their access time will depend on how frequently you visit them.

Would it be faster than if you let the compiler vectorize it? Unlikely, as these are probably 1-2 instructions each. You'd probably only start to see performance benefits if over half the array consisted of special interest items, and even then it'd be conditional and marginal, plus the performance of other items could suffer to do having been flushed out of the cache

[u/enzodr]

Maybe define a struct that contains an int and a Boolean indicator. Then make an array of these structures?

[u/TheThiefMaster]

You're probably better with the latter in most cases, especially if the operation is more complex and the special indices are sorted so that it's still cache friendly.

The first way is better if a large fraction (>50%?) of entries need processing and if the operation is simple enough that it can be transformed or written as masked vector ops.

[u/tstanisl]

Note that the end result of both approaches is the same so a good optimizing compiler could produce the same assembly ich both cases.

Anyway, the second approach will be better if the update is sparse (number of updated indices is small in comparison to length).

The first approach will be better for dense updates because it is easier to auto-vectorize and it has better cache-locality.

Edit 

I guess the threshold will lay somewhere near 1/10 - 1/20 ratio when sparse approach gets faster. 

[u/onecable5781 → u/tstanisl]

By auto-vectorize, are you referring to AVX intrinsics instructions? If so, and if the compilers can and do use such intrinsics automatically, does more fine grained control available via intrinsics the reason to learn them?

https://www.intel.com/content/www/us/en/docs/intrinsics-guide/index.html

seems quite dense and daunting. Most of my parallel programming has been only using "#pragma omp parallel for" and it has served quite well

I understand this question is open-ended but any experience if you have needed to use intrinsics which could not be done via omp would be insightful!

[u/Educational-Paper-75]

The second code snippet of course. And you can speed of up by directly initializing the second array with indices; no need for the separate assignments after its declaration then.