Thread: Determining operator at run time efficiently (without "if')

  1. #1
    Registered User sonnichs's Avatar
    Join Date
    Jul 2011
    Posts
    30

    Determining operator at run time efficiently (without "if')

    I have the stretch of pseudocode below. We have a very long running loop and the code needs to be highly efficient. We need to run the function using either "<" or ">" depending upon circumstances at runtime when is called.
    The first construct with two separate functions works fine. Except it is very verbose having to clone a lot of code for each function.
    The 2nd construct combines both functions and determines the < or > at runtime based upon a parameter. This works but is very slow due to the "if" statement.
    I thought C++ may solve this with a lambda function as shown. But apparently this is recalling the function each time and this is equally slow.
    Is there some "nice" way to combine my functions and efficiently determine the "< ,>" parameter at runtime?

    Thanks
    Fritz
    Code:
    PSUEDOCODE
    //Assume loop is very long. Efficiency is important here.
    (1) coding two separate functions for GT and LT: efficient but lengthy with redundant code
    funct1()
    {
     loop:
       [lots of code]
       if (a < b) blah-blah
       [lots more code]
    }
    
    funct2()
    {
     loop:
       [lots of code]
       if (a > b) blah-blah
       [lots more code]
    }
    
    //(2) consolidate into one function. works but "if" statement takes too much time for large loop.
    funct(char optype)
    {
     loop:
       [lots of code]
       if(optype == 'L' (a < b) {blah-blah}
            else (a > b) {blah-blah}
       [lots more code]
    }
    
    //(3) attempt to use lambda function. runs slow-probably lamda is execute over and over
    
    funct(char optype)
       auto greater = [&](auto a, auto b) -> bool
       {
            if(optype == 'L')  return a < b;
            else return a > b;
       };
    
     loop:
       [lots of code]
            if (greater(a, b)) {blah-blah}
            else (a > b) {blah-blah}
     [lots more code]
    }

  2. #2
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    I don't fully understand, but perhaps you could just swap(a, b) before the loop under some condition. Does that make sense?
    A little inaccuracy saves tons of explanation. - H.H. Munro

  3. #3
    C++ Witch laserlight's Avatar
    Join Date
    Oct 2003
    Location
    Singapore
    Posts
    28,413
    Quote Originally Posted by sonnichs
    I thought C++ may solve this with a lambda function as shown. But apparently this is recalling the function each time and this is equally slow.
    What probably happened is that the lambda function was inlined, so the end result was the same.

    john.c's swapping idea might work, but if you're doing something a bit more complex, another possibility to try might be:
    Code:
    functBlahBlahL()
    {
        if (a < b) blah-blah
    }
    
    functBlahBlahG()
    {
        if (a > b) blah-blah
    }
    
    template<functBlahBlah>
    funct()
    {
    loop:
       [lots of code]
       functBlahBlah()
       [lots more code]
    }
    
    funct<functBlahBlahL>()
    So my idea is that the blah-blah code to execute depending on the comparison is placed into functions, then you turn the original function into a function template and pass these functions as template arguments depending on whether you want GT or LT. If the blah-blah code is inlined in both cases (I'm assuming they're different hence the swap idea wouldn't work), then you basically end up with your original two big functions, but now as a single function template.
    Last edited by laserlight; 11-21-2021 at 09:08 PM.
    Quote Originally Posted by Bjarne Stroustrup (2000-10-14)
    I get maybe two dozen requests for help with some sort of programming or design problem every day. Most have more sense than to send me hundreds of lines of code. If they do, I ask them to find the smallest example that exhibits the problem and send me that. Mostly, they then find the error themselves. "Finding the smallest program that demonstrates the error" is a powerful debugging tool.
    Look up a C++ Reference and learn How To Ask Questions The Smart Way

  4. #4
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    I fail to see how a single "if" can have a performance impact compared to "lots of code".

    Is this backed up by some actual profiling data, or just finger in the air guessing.

    > Assume loop is very long. Efficiency is important here.
    Maybe that's the problem.
    Compilers can struggle with very large bloatware.
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

  5. #5
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    Yeah, now that I read this again, it doesn't make sense. Maybe you implemented it wrong and that somehow led to a longer runtime. For instance, it seems that your code (2) above should be more like this:
    Code:
    funct(char optype)
    {
     loop:
       [lots of code]
       if (optype == 'L')
       {
           if (a < b) {blah-blah}
       }
       else
       {
           if (a > b) {blah-blah}
       }
       [lots more code]
    }
    A little inaccuracy saves tons of explanation. - H.H. Munro

  6. #6
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    For instance, if you mistakenly implemented it like:
    Code:
      if (optype == 'L' && a < b) {blah-blah}
      else if (a > b)             {blah-blah}
    Then if optype == 'L' is true and a < b is false, the > test will also be tested (and probably be true) , which is not what you want. That would increase the runtime.
    Last edited by john.c; 11-22-2021 at 12:06 AM.
    A little inaccuracy saves tons of explanation. - H.H. Munro

  7. #7
    Registered User
    Join Date
    Dec 2017
    Posts
    1,626
    Another possible mistaken implementation is leaving out the braces to delimit the outer "if" block like this:
    Code:
       if (optype == 'L')
           if (a < b) {blah-blah}
       else
           if (a > b) {blah-blah}
    The above actually means this:
    Code:
       if (optype == 'L')
           if (a < b)
               {blah-blah}
           else if (a > b)
               {blah-blah}
    which is again not what you want and would cause a call of the function with optype == 'L' to take a longer time than the original code while a call with optype != 'L' would take a shorter time.
    A little inaccuracy saves tons of explanation. - H.H. Munro

  8. #8
    Registered User sonnichs's Avatar
    Join Date
    Jul 2011
    Posts
    30
    Sorry for the delay here-I spent most of yesterday dealing with an errant 3D printer. At any rate I was trying save you having you look at my code using pseudo code but it lead to confusion and I apologize. I am attaching one example of the actual code here (there are several similar ones in about 10,000 lines). This type of pattern-copying the same code for both the GT and LT condition-- occurs a lot and I want to condense the code for simplicity. (if you search on the "<" sign you will find the statement in question)
    Keep in mind that the user calls the appropriate routine dynamically so it cannot be "hard compiled" with a #define for example.
    I have tested the code with timers and the addition of an "if" statement takes up to 20% extra time depending matrix size and upon which compiler I use ranging from the gnu with O1 and O3 to the MPLAB. More important however is that this raises a general question regarding the ability of C++ to have a function that shares all code except perhaps one line. It does this type of thing with Class overloading but not, to my knowledge, for functions.
    My 3rd example in the attachment shows my attempt to use the "lambda" but I cannot really find documentation to clarify this method and perhaps it is not even the right way to go.

    cheers
    Fritz

    Code:
      //======================================== colsort_bubble =================================
      IRIS_EU_STATUS Matrix::colsort_bubble()
      {
       uint32_t ii, jj, kk;
       Data_t holdsw;
       bool swapped;
    
      for (jj = 0; jj < ncols; jj++)
      {
       for (ii = 0; ii < mrows - 1; ii++)
       {
         swapped = false;
         for (kk = 0; kk < mrows-ii-1; kk++)
         {
            if (pDataBuffer[kk*ncols + jj] > pDataBuffer[kk*ncols + jj + ncols] )
            {
               holdsw = pDataBuffer[kk*ncols + jj]; //swap elements
               pDataBuffer[kk*ncols + jj] = pDataBuffer[kk*ncols + jj + ncols ];
               pDataBuffer[kk*ncols + jj + ncols ] = holdsw;
               swapped = true;
            } //end if
         } //end for(kk)
         if (swapped == false) break;
       } //end for(ii)
      } //end for(jj)
    
        return(0);
      } //end colsort_bubble
    
      //======================================== colsort_bubble descending ======================
     IRIS_EU_STATUS Matrix::colsort_bubble_desc()
      {
            //This function reverse sorts the matrix on a column by column basis. Specifying Matrix X(N,1) will
            //allow use as a col vector sort.
       uint32_t ii, jj, kk;
       Data_t holdsw;
       bool swapped;
    
      for (jj = 0; jj < ncols; jj++)
      {
       for (ii = 0; ii < mrows - 1; ii++)
       {
         swapped = false;
         for (kk = 0; kk < mrows-ii-1; kk++)
         {
            if (pDataBuffer[kk*ncols + jj] < pDataBuffer[kk*ncols + jj + ncols] )
            {
               holdsw = pDataBuffer[kk*ncols + jj]; //swap elements
               pDataBuffer[kk*ncols + jj] = pDataBuffer[kk*ncols + jj + ncols ];
               pDataBuffer[kk*ncols + jj + ncols ] = holdsw;
               swapped = true;
            } //end if
         } //end for(kk)
         if (swapped == false) break;
       } //end for(ii)
      } //end for(jj)
    
        return(0);
      } //end colsort_bubble
    
    
      //======================================== colsort_bubble both ways ========================
      IRIS_EU_STATUS Matrix::colsort_bubble_both(char dir)
      {
       uint32_t ii, jj, kk;
       Data_t holdsw;
       bool swapped;
    
       auto greater = [&](auto a, auto b) -> bool
       {
            if(dir == 'd')  return a < b;
            else return a > b;
       };
    
      for (jj = 0; jj < ncols; jj++)
      {
       for (ii = 0; ii < mrows - 1; ii++)
       {
         swapped = false;
         for (kk = 0; kk < mrows-ii-1; kk++)
         {
            //if (pDataBuffer[kk*ncols + jj] > pDataBuffer[kk*ncols + jj + ncols] )
            if (    greater(   pDataBuffer[kk*ncols + jj] , pDataBuffer[kk*ncols + jj + ncols]   )     )
            {
               holdsw = pDataBuffer[kk*ncols + jj]; //swap elements
               pDataBuffer[kk*ncols + jj] = pDataBuffer[kk*ncols + jj + ncols ];
               pDataBuffer[kk*ncols + jj + ncols ] = holdsw;
               swapped = true;
            } //end if
         } //end for(kk)
         if (swapped == false) break;
       } //end for(ii)
      } //end for(jj)
    
        return(0);
      } //end colsort_bubble

  9. #9
    and the hat of int overfl Salem's Avatar
    Join Date
    Aug 2001
    Location
    The edge of the known universe
    Posts
    39,660
    Well there's your problem!
    Expecting "performance" out of a bubble sort.

    std::sort - cppreference.com
    If you dance barefoot on the broken glass of undefined behaviour, you've got to expect the occasional cut.
    If at first you don't succeed, try writing your phone number on the exam paper.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Overloading bracket "[]" operator in a templated array class
    By silentkarma in forum C++ Programming
    Replies: 2
    Last Post: 01-21-2012, 05:40 AM
  2. the operator "="error in class "String"
    By boyhailong in forum C++ Programming
    Replies: 9
    Last Post: 07-27-2011, 08:39 PM
  3. Determining if a string has an "s" at the end
    By Seany242 in forum C Programming
    Replies: 8
    Last Post: 04-20-2011, 03:06 PM
  4. Replies: 9
    Last Post: 03-31-2009, 04:23 PM
  5. Replies: 3
    Last Post: 12-06-2002, 10:02 AM

Tags for this Thread