1
\$\begingroup\$

Background

The following code (part of a natural language processor) was written to eliminate duplicate code by using isLeft as a conditional throughout the method:

private void doInsideChartBinaryRules( boolean isLeft, int state, int start,
                                       int end, int[] narrowLExtent_end,
                                       int[] narrowRExtent_start,
                                       int[] wideLExtent_end,
                                       int[] wideRExtent_start,
                                       float[] iScore_start_end,
                                       float[][] iScore_start,
                                       float[][][] iScore,
                                       boolean lengthNormalization ) {
  int narrowR = narrowRExtent_start[ state ],
      narrowL = narrowLExtent_end[ state ];

  BinaryRule[] rules =
    ( isLeft ) ?
    bg.splitRulesWithLC( state ) :
    bg.splitRulesWithRC( state );

  for( BinaryRule rule : rules ) {
    int leftChild = rule.leftChild;
    int rightChild = rule.rightChild;

    if( isLeft ) {
      narrowL = narrowLExtent_end[ rightChild ];
      // can this right constituent fit next to the left constituent?
      if( narrowL < narrowR ) {
        continue;
      }
    }
    else {
      narrowR = narrowRExtent_start[ leftChild ];
      if( narrowR > narrowL ) {
        continue;
      }
    }

    int min2 =
      ( isLeft ) ? wideLExtent_end[ rightChild ] : wideLExtent_end[ state ];
    int min = ( narrowR > min2 ? narrowR : min2 );
    int max1 =
      ( isLeft ) ? wideRExtent_start[ state ] : wideRExtent_start[ leftChild ];
    int max = ( max1 < narrowL ? max1 : narrowL );

    if( min > max ) {
      continue;
    }

    float pS = rule.score;
    int parentState = rule.parent;
    float oldIScore = iScore_start_end[ parentState ];
    float bestIScore = oldIScore;
    boolean foundBetter;

    if( !lengthNormalization ) {
      // find the split that can use this rule to make the max score
      for( int split = min; split <= max; split++ ) {

        boolean skip = false;
        for( ParserConstraint c : constraints ) {
          if( ( ( start < c.start && end >= c.end ) ||
                ( start <= c.start && end > c.end ) ) && split > c.start &&
              split < c.end ) {
            skip = true;
            break;
          }

          if( ( start == c.start && split == c.end ) ) {
            String tag =
              isLeft ? stateIndex.get( state ) : stateIndex.get( leftChild );
            Matcher m = c.state.matcher( tag );
            if( !m.matches() ) {
              skip = true;
              break;
            }
          }

          if( ( split == c.start && end == c.end ) ) {
            String tag =
              isLeft ? stateIndex.get( rightChild ) : stateIndex.get( state );
            Matcher m = c.state.matcher( tag );
            if( !m.matches() ) {
              skip = true;
              break;
            }
          }
        }

        if( skip ) {
          continue;
        }

        float lS = ( isLeft ) ?
          iScore_start[ split ][ state ] :
          iScore_start[ split ][ leftChild ];

        if( lS == Float.NEGATIVE_INFINITY ) {
          continue;
        }

        float rS = ( isLeft ) ?
          iScore[ split ][ end ][ rightChild ] :
          iScore[ split ][ end ][ state ];

        if( rS == Float.NEGATIVE_INFINITY ) {
          continue;
        }
        float tot = pS + lS + rS;

        if( tot > bestIScore ) {
          bestIScore = tot;
        }
      }

      foundBetter = bestIScore > oldIScore;
    }
    else {
      int bestWordsInSpan = wordsInSpan[ start ][ end ][ parentState ];
      float oldNormIScore = oldIScore / bestWordsInSpan;
      float bestNormIScore = oldNormIScore;

      for( int split = min; split <= max; split++ ) {
        float lS = ( isLeft ) ?
          iScore_start[ split ][ state ] :
          iScore_start[ split ][ leftChild ];

        if( lS == Float.NEGATIVE_INFINITY ) {
          continue;
        }

        float rS = ( isLeft ) ?
          iScore[ split ][ end ][ rightChild ] :
          iScore[ split ][ end ][ state ];

        if( rS == Float.NEGATIVE_INFINITY ) {
          continue;
        }

        float tot = pS + lS + rS;
        int newWordsInSpan = ( isLeft ) ?
          wordsInSpan[ start ][ split ][ state ] +
          wordsInSpan[ split ][ end ][ rightChild ] :
          wordsInSpan[ start ][ split ][ leftChild ] +
          wordsInSpan[ split ][ end ][ state ];
        float normTot = tot / newWordsInSpan;

        if( normTot > bestNormIScore ) {
          bestIScore = tot;
          bestNormIScore = normTot;
          bestWordsInSpan = newWordsInSpan;
        }
      }

      foundBetter = bestNormIScore > oldNormIScore;

      if( foundBetter ) {
        wordsInSpan[ start ][ end ][ parentState ] = bestWordsInSpan;
      }
    }
    if( foundBetter ) {
      iScore_start_end[ parentState ] = bestIScore;

      if( oldIScore == Float.NEGATIVE_INFINITY ) {
        if( start > narrowLExtent_end[ parentState ] ) {
          narrowLExtent_end[ parentState ] = start;
          wideLExtent_end[ parentState ] = start;
        }
        else {
          if( start < wideLExtent_end[ parentState ] ) {
            wideLExtent_end[ parentState ] = start;
          }
        }
        if( end < narrowRExtent_start[ parentState ] ) {
          narrowRExtent_start[ parentState ] = end;
          wideRExtent_start[ parentState ] = end;
        }
        else {
          if( end > wideRExtent_start[ parentState ] ) {
            wideRExtent_start[ parentState ] = end;
          }
        }
      }
    }
  }
}

Problem

This has caused a 10% performance decrease.

Question

How would you refactor the code to eliminate all the checks for isLeft so as to regain (or exceed) the performance that was lost?

Thank you!

\$\endgroup\$
  • \$\begingroup\$ Even if it is already answered, I suggest to think about using objects and/or split the logic in several functions. Such a number of arguments is a good indicator to introduce an object. You could use polymorphism to simplify the code and logic, you could probably remove all of this isLeft flag. Besides that, you should use a profiler and provide a working example if expecting good answers. \$\endgroup\$ – tb- Mar 25 '13 at 0:14
3
\$\begingroup\$

The first thing checked was where and how isLeft is used by removing code repetition around it:

    float rS = ( isLeft ) ?
      iScore[ split ][ end ][ rightChild ] :
      iScore[ split ][ end ][ state ];

became

    float rS = iScore[ split ][ end ][ isLeft ? rightChild : state ];

then it became clear that the same patterns were appearing a bit everywhere : isLeft ? rightChild : state and isLeft ? state : leftChild. Storing these values in a variable as soon as possible could save a few computations. The corresponding code could would be:

private void doInsideChartBinaryRules( boolean isLeft, int state, int start,
        int end, int[] narrowLExtent_end,
        int[] narrowRExtent_start,
        int[] wideLExtent_end,
        int[] wideRExtent_start,
        float[] iScore_start_end,
        float[][] iScore_start,
        float[][][] iScore,
        boolean lengthNormalization ) {
    int narrowR = narrowRExtent_start[ state ],narrowL = narrowLExtent_end[ state ];

    BinaryRule[] rules = isLeft ?  bg.splitRulesWithLC( state ) : bg.splitRulesWithRC( state );

    for( BinaryRule rule : rules ) {
        int leftChild = rule.leftChild;
        int rightChild = rule.rightChild;

        if( isLeft ) {
            narrowL = narrowLExtent_end[ rightChild ];
            // can this right constituent fit next to the left constituent?
            if( narrowL < narrowR ) {
                continue;
            }
        }
        else {
            narrowR = narrowRExtent_start[ leftChild ];
            if( narrowR > narrowL ) {
                continue;
            }
        }

        int state1 = isLeft ? rightChild : state;
        int state2 = isLeft ? state : leftChild;

        int min2 = wideLExtent_end[ state1];
        int min = ( narrowR > min2 ? narrowR : min2 );
        int max1 = wideRExtent_start[ state2 ];
        int max = ( max1 < narrowL ? max1 : narrowL );

        if( min > max ) {
            continue;
        }

        float pS = rule.score;
        int parentState = rule.parent;
        float oldIScore = iScore_start_end[ parentState ];
        float bestIScore = oldIScore;
        boolean foundBetter;

        if( !lengthNormalization ) {
            // find the split that can use this rule to make the max score
            for( int split = min; split <= max; split++ ) {

                boolean skip = false;
                for( ParserConstraint c : constraints ) {
                    if( ( ( start < c.start && end >= c.end ) ||
                                ( start <= c.start && end > c.end ) ) && split > c.start &&
                            split < c.end ) {
                        skip = true;
                        break;
                    }

                    if( ( start == c.start && split == c.end ) ) {
                        String tag = stateIndex.get( state2 );
                        Matcher m = c.state.matcher( tag );
                        if( !m.matches() ) {
                            skip = true;
                            break;
                        }
                    }

                    if( ( split == c.start && end == c.end ) ) {
                        String tag = stateIndex.get( state1 );
                        Matcher m = c.state.matcher( tag );
                        if( !m.matches() ) {
                            skip = true;
                            break;
                        }
                    }
                }

                if( skip ) {
                    continue;
                }

                float lS = iScore_start[ split ][ state2];

                if( lS == Float.NEGATIVE_INFINITY ) {
                    continue;
                }

                float rS = iScore[ split ][ end ][ state1];

                if( rS == Float.NEGATIVE_INFINITY ) {
                    continue;
                }
                float tot = pS + lS + rS;

                if( tot > bestIScore ) {
                    bestIScore = tot;
                }
            }

            foundBetter = bestIScore > oldIScore;
        }
        else {
            int bestWordsInSpan = wordsInSpan[ start ][ end ][ parentState ];
            float oldNormIScore = oldIScore / bestWordsInSpan;
            float bestNormIScore = oldNormIScore;

            for( int split = min; split <= max; split++ ) {
                float lS = iScore_start[ split ][ state2];

                if( lS == Float.NEGATIVE_INFINITY ) {
                    continue;
                }

                float rS = iScore[ split ][ end ][ state1];

                if( rS == Float.NEGATIVE_INFINITY ) {
                    continue;
                }

                float tot = pS + lS + rS;
                int newWordsInSpan = 
                    wordsInSpan[ start ][ split ][ state2] +
                    wordsInSpan[ split ][ end   ][ state1];
                float normTot = tot / newWordsInSpan;

                if( normTot > bestNormIScore ) {
                    bestIScore = tot;
                    bestNormIScore = normTot;
                    bestWordsInSpan = newWordsInSpan;
                }
            }

            foundBetter = bestNormIScore > oldNormIScore;

            if( foundBetter ) {
                wordsInSpan[ start ][ end ][ parentState ] = bestWordsInSpan;
            }
        }
        if( foundBetter ) {
            iScore_start_end[ parentState ] = bestIScore;

            if( oldIScore == Float.NEGATIVE_INFINITY ) {
                if( start > narrowLExtent_end[ parentState ] ) {
                    narrowLExtent_end[ parentState ] = start;
                    wideLExtent_end[ parentState ] = start;
                }
                else {
                    if( start < wideLExtent_end[ parentState ] ) {
                        wideLExtent_end[ parentState ] = start;
                    }
                }
                if( end < narrowRExtent_start[ parentState ] ) {
                    narrowRExtent_start[ parentState ] = end;
                    wideRExtent_start[ parentState ] = end;
                }
                else {
                    if( end > wideRExtent_start[ parentState ] ) {
                        wideRExtent_start[ parentState ] = end;
                    }
                }
            }
        }
    }
}

My variable names are not good because I have no idea what this is all about. Anyway, at this stage, there almost no check related to isLeft anymore.

Then, a little detail I noticed is that rightChild is not used sometimes so we can avoid getting it in the first place by noticing that we could move the variables introduced previously (the check on isLeft ensures that we consider the right value) :

for( BinaryRule rule : rules ) {
    int state1 = isLeft ? rule.rightChild : state;
    int state2 = isLeft ? state : rule.leftChild;

    if( isLeft ) {
        narrowL = narrowLExtent_end[ state1 ];
        // can this right constituent fit next to the left constituent?
        if( narrowL < narrowR ) {
            continue;
        }
    }
    else {
        narrowR = narrowRExtent_start[ state2 ];
        if( narrowR > narrowL ) {
            continue;
        }
    }

Then, a thing to notice in the code above is the duplicated logic which can be extracted :

for( BinaryRule rule : rules ) {
    int state1 = isLeft ? rule.rightChild : state;
    int state2 = isLeft ? state : rule.leftChild;

    if( isLeft ) {
        narrowL = narrowLExtent_end[ state1 ];
    }
    else {
        narrowR = narrowRExtent_start[ state2 ];
    }
    // can this right constituent fit next to the left constituent?
    if( narrowR > narrowL ) {
        continue;
    }

At this stage, everything we've done should be either without effect or with a good effect on performance. I am not so confident that this will be true for the next change but I'd rather give it to you as an option anyway.

One can notice that narrowR is either narrowRExtent_start[ state ] or narrowRExtent_start[ leftChild ] depending on the value of isLeft. In a concise way, narrowR = narrowRExtent_start[isLeft ? state : leftChild] which is narrowR = narrowRExtent_start[state2]. The same applies to narrowL. Thus, the code can be written :

for( BinaryRule rule : rules ) {
    int state1 = isLeft ? rule.rightChild : state;
    int state2 = isLeft ? state : rule.leftChild;

    int narrowL = narrowLExtent_end[ state1 ];
    int narrowR = narrowRExtent_start[ state2 ];

This removes yet another check on isLeft but it comes at a cost.

In the original code, we get values from narrowXExtend_xxx twice at the beginning and then once per iteration. In my case, we don't do it at the beginning but then we do it twice per iteration. If the size of rules is bigger than 2, it could lead to a slightly less efficient code. This might be worth doing it to get rid of any code repetition but this is up to you.

Now, just a comment not related to the logic around isLeft :

            if( end < narrowRExtent_start[ parentState ] ) {
                narrowRExtent_start[ parentState ] = end;
                wideRExtent_start[ parentState ] = end;
            }
            else {
                if( end > wideRExtent_start[ parentState ] ) {
                    wideRExtent_start[ parentState ] = end;
                }
            }

could be rewritten :

            if( end < narrowRExtent_start[ parentState ] ) {
                narrowRExtent_start[ parentState ] = end;
                wideRExtent_start[ parentState ] = end;
            }
            else if( end > wideRExtent_start[ parentState ] ) {
                    wideRExtent_start[ parentState ] = end;
            }

It doesn't change the performances but is easier to read. The same comment applies to different places in the code.

\$\endgroup\$
  • 1
    \$\begingroup\$ I moved BinaryRule[] rules = isLeft ? bg.splitRulesWithLC( state ) : bg.splitRulesWithRC( state ); outside the function (by adding BinaryRule rules[] as an additional parameter) and now see big performance gains. Thank you for all the help and extensive analysis. \$\endgroup\$ – Dave Jarvis Mar 21 '13 at 20:12

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.