7
\$\begingroup\$

In my OpenCL kernel, I have the following logic:

size_t id = get_global_id(0);
uchar index0 = (id / 32760) % 16;
uchar index1 = (id / 2184) % 15;
uchar index2 = (id / 156) % 14;
uchar index3 = (id / 12) % 13;
uchar index4 = (id / 1) % 12;



if (index1 >= index0) 
    ++index1;


if(index2 >= index0 || 
   index2 >= index1) 
    ++index2; 
if(index2 >= index1 && index2 >= index0) 
    ++index2;


if(index3 >= index0 || 
   index3 >= index1 || 
   index3 >= index2) 
    ++index3;
if(index3 >= index0 && index3 >= index1 || 
   index3 >= index1 && index3 >= index2 || 
   index3 >= index2 && index3 >= index0) 
    ++index3;
if(index3 >= index0 && index3 >= index1 && index3 >= index2) 
    ++index3;


if(index4 >= index0 || 
   index4 >= index1 || 
   index4 >= index2 || 
   index4 >= index3) 
    ++index4;
if(index4 >= index0 && index4 >= index1 || 
   index4 >= index0 && index4 >= index2 || 
   index4 >= index0 && index4 >= index3 || 
   index4 >= index1 && index4 >= index2 || 
   index4 >= index1 && index4 >= index3 || 
   index4 >= index2 && index4 >= index3) 
    ++index4;
if(index4 >= index0 && index4 >= index1 && index4 >= index2 || 
   index4 >= index1 && index4 >= index2 && index4 >= index3 || 
   index4 >= index2 && index4 >= index3 && index4 >= index0 || 
   index4 >= index3 && index4 >= index0 && index4 >= index1) 
    ++index4;
if(index4 >= index0 && index4 >= index1 && index4 >= index2 && index4 >= index3) 
    ++index4;

Now, in my testing, I've verified that this logic is correct and applies correct behavior to my variables. However, it is extremely cumbersome to read and maintain, and I'm looking for a way to optimize it such that it's much easier to read and understand. How can I rewrite this logic so that it's much easier to read, and possibly faster to execute?

The intent of this code is to take an input integer in the range [0, 16*15*14*13*12), and convert it into a permutation of 5 unique indices ranged [0,16). Like I said, this code works, but it's very confusing to read.

There are a few restrictions:

  • No Recursion. I'm aware that most OpenCL compilers will allow limited degrees of recursion by in-lining away recursive function calls, but I want this code to be as portable as possible, and that means adhering to the specifications set by the Official OpenCL spec.
  • Readability is more important than speed. Obviously, getting the algorithm faster would be ideal, but what I really care about is making this code less cumbersome to maintain, particularly if I expand it to add more variables to this algorithm.
  • I have limited access to OOP related functionality. This is OpenCL, so anything object-oriented needs to be compatible with OpenCL 2.0.
\$\endgroup\$
  • \$\begingroup\$ C++ and C are different languages, and should not be used to tag the same question. Either the code is C++ or it is C. It cannot be both. As it looks, uchar is something that is more attributed to C++ than to C, combined with the fact that you have gotten feedback dealing with C++ I am removing the C tag. \$\endgroup\$ – syb0rg Dec 11 '15 at 22:19
  • \$\begingroup\$ @syb0rg Unfortunately, you got it in reverse. The code is written in OpenCL C code, within which uchar is a native data type. But when I tried to use OpenCL as a tag, Stack Exchange complained that I needed a rep of 300 or higher to add the "new" tag. Also, the tag 'kernel' is incorrect, as it refers to Operating System kernels, which this is not. \$\endgroup\$ – Xirema Dec 11 '15 at 22:24
  • \$\begingroup\$ I removed the kernel tag. Your question will remain tagged C++ as that is what @Barry reviewed with respect to. \$\endgroup\$ – syb0rg Dec 11 '15 at 22:28
  • \$\begingroup\$ @syb0rg It would be lovely if you could add OpenCL as a tag, as I cannot do that due to low rep.That's the real code language being used, and the code Barry provided is valid in OpenCL. \$\endgroup\$ – Xirema Dec 11 '15 at 22:30
  • \$\begingroup\$ Done, if you want to edit the tags wiki (which I'm not sure if you're able to do or not), the descriptions will be placed in a queue to be reviewed and hopefully accepted to earn you some more rep. \$\endgroup\$ – syb0rg Dec 11 '15 at 22:32
3
\$\begingroup\$

Use your words

Let's start with what you're actually accomplishing in all those if statements. It looks like what you're doing is incrementing each index by the number of smaller indices, for each possible such count.

That translates itself naturally to using arrays:

uchar index[5] = {(id / 32760) % 16,
                  (id / 2184) % 15,
                  (id / 156) % 14,
                  (id / 12) % 13,
                  (id / 1) % 12};

And writing that idea as a loop:

// for each index
for (int i=1; i<5; ++i) {
    // for each possible count of smaller indices
    for (int cnt=1; cnt<=i; ++cnt) {
       // count the number of smaller indices
       int k=0;
       for (int j=0; j<i; ++j) {
           k += (index[i] >= index[j]);
       }

       // and increment if necessary
       if (k >= cnt) {
           ++index[i];
       }
    }
}

This can be translated into the sort-of-more/sort-of-less readable (YMMV) C++11 version:

for (int& i : index) {
    for (int cnt=1; cnt <= std::distance(index, &i); ++cnt) {
        i += std::count_if(index, &i, [i](int j){return i >= j; }) >= cnt;
    }
}
\$\endgroup\$
  • \$\begingroup\$ I like what you're going for, but this produces incorrect logic: i.imgur.com/NXHvvJP.png?1 (FYI, all the indexes in this output file are incremented once from their state in internal memory) Indexes 2 and 4 received the same index under this code. My requirement is that each of the indexes be unique. id = 0 should produce starting indexes of {0,1,2,3,4,<remaining indexes not used in this context>} But under your code, it produces {0,1,1,1,1,<remaining indexes not used in this context>} \$\endgroup\$ – Xirema Dec 11 '15 at 21:14
  • \$\begingroup\$ @Xirema Ah, I see. Yeah it's very difficult to understand what it is your code is supposed to be doing. Here's an improved iteration. \$\endgroup\$ – Barry Dec 11 '15 at 21:33
  • \$\begingroup\$ Alright. The new version of the code works. I can't use the C++11 version because this is GPU-local OpenCL C code, but it's producing all the correct indexes now without my obnoxiously difficult to maintain code. Thank you! \$\endgroup\$ – Xirema Dec 11 '15 at 21:44
0
\$\begingroup\$

Firstly, it's hard to read the code because of the indentation. Instead of using hanging indents, which implies nesting, use blank spaces. Group into "blocks" related code. It looks to me that you are resetting the indents when you move to the logic for incrementing the next index# variable. Remove the indents, and group them in blocks separated by blank lines, instead.

You can also format your conditions so that they are multi-line. Long continuous run-on statements are hard to read. Instead of this:

if(index3 >= index0 || index3 >= index1 || index3 >= index2) ++index3;

Consider this:

if (index3 >= index0 || 
    index3 >= index1 || 
    index3 >= index2) {
  ++index3;
}

Finally,

How familiar are you with Discrete Mathematic concepts? I assume (hope) you have some background, by virtue of being a programmer.

In situations like this, I think back to the principles covered when discussing logical proofs. You might be able to simplify some of the logic by determining which conditions are always true when previous conditions are always true.

For instance, in a very simplistic example, you can simplify a check for all factors of a given number n by iterating from 2 through sqrt(n), rather than looping through all integers [1..n]. This is due to the fact that x * y = y * x, so therefore if x divides into n for y number of times with no remainder, then y divides into n for x number of times and therefore doing the same check on y would be redundant.

Build a truth table with each condition and see if you find some overlap. Perhaps you don't need some of these checks. Perhaps you can nest some of these rather than creating new if statements each time.

\$\endgroup\$
  • 1
    \$\begingroup\$ Too hypothetical, We only review concrete, working code. \$\endgroup\$ – Caridorc Dec 11 '15 at 21:28
  • \$\begingroup\$ Not that talking about concepts is forbidden, but this talking should be linked to a way to clearly improve the code. \$\endgroup\$ – Caridorc Dec 11 '15 at 21:49
  • \$\begingroup\$ You are welcome :) I am sure you will make one great answer one of these days, you have the potential \$\endgroup\$ – Caridorc Dec 14 '15 at 17:41
  • \$\begingroup\$ Haha, thanks. I am new to this particular site, as you can see. :) \$\endgroup\$ – Ben Richards Dec 14 '15 at 17:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.