Optimizing WordWrap Algorithm

Question

I have a word-wrap algorithm that basically generates lines of text that fit the width of the text. Unfortunately, it gets slow when I add too much text.

I was wondering if I oversaw any major optimizations that could be made. Also, if anyone has a design that would still allow strings of lines or string pointers of lines that is better I'd be open to rewriting the algorithm.

Thanks

void AguiTextBox::makeLinesFromWordWrap()
{
    textRows.clear();
    textRows.push_back("");
    std::string curStr;
    std::string curWord;

    int curWordWidth = 0;
    int curLetterWidth = 0;
    int curLineWidth = 0;

    bool isVscroll = isVScrollNeeded();
    int voffset = 0;
    if(isVscroll)
    {
        voffset = pChildVScroll->getWidth();
    }
    int AdjWidthMinusVoffset = getAdjustedWidth() - voffset;
    int len = getTextLength();
    int bytesSkipped = 0;
    int letterLength = 0;
    size_t ind = 0;

    for(int i = 0; i < len; ++i)
    {

        //get the unicode character
        letterLength = _unicodeFunctions.bringToNextUnichar(ind,getText());
        curStr = getText().substr(bytesSkipped,letterLength);


        bytesSkipped += letterLength;

        curLetterWidth = getFont().getTextWidth(curStr);

        //push a new line
        if(curStr[0] == '\n')
        {
            textRows.back() += curWord;
            curWord = "";
            curLetterWidth = 0;
            curWordWidth = 0;
            curLineWidth = 0;
            textRows.push_back("");
            continue;
        }



            //ensure word is not longer than the width
            if(curWordWidth + curLetterWidth >= AdjWidthMinusVoffset && 
                curWord.length() >= 1)
            {
                textRows.back() += curWord;

                textRows.push_back("");
                curWord = "";
                curWordWidth = 0;
                curLineWidth = 0;
            }

            //add letter to word
            curWord += curStr;
            curWordWidth += curLetterWidth;


        //if we need a Vscroll bar start over
        if(!isVscroll && isVScrollNeeded())
        {
            isVscroll = true;
            voffset = pChildVScroll->getWidth();
            AdjWidthMinusVoffset = getAdjustedWidth() - voffset;
            i = -1;
            curWord = "";
            curStr = "";
            textRows.clear();
            textRows.push_back("");
            ind = 0;

            curWordWidth = 0;
            curLetterWidth = 0;
            curLineWidth = 0;

            bytesSkipped = 0;
            continue;
        }

        if(curLineWidth + curWordWidth >= 
            AdjWidthMinusVoffset && textRows.back().length() >= 1)
        {
            textRows.push_back("");
            curLineWidth = 0;
        }

        if(curStr[0] == ' ' || curStr[0] == '-')
        {
            textRows.back() += curWord;
            curLineWidth += curWordWidth;
            curWord = "";
            curWordWidth = 0;
        }
    }

    if(curWord != "")
    {
        textRows.back() += curWord;
    }

    updateWidestLine();
}

Answer 1

I have some high-level advice based on a cursory read of your code. It would really help if you could refactor it into multiple methods as this function is too long and does too much. That won't help your speed, but it will make it easier for others to grok your code and provide more advice.

Profile your code

You can't hope to make things faster in an orderly fashion without finding out what parts take the most time. Yes, you can devise a faster algorithm, but you might end up spending days optimizing an O(n^2) algorithm to O(log n) only to find out that part took 1ms anyway.

Split each word first

If you only split at word boundaries, you may as well seek forward for a boundary and extract the substring in one call.

Calculate word widths instead of letter widths

First, when I wrote a similar function in Java many years ago, the cost of calling calculating the width of a string had a fairly high overhead that didn't change with the length of the string. Getting the width a character at a time was significantly more costly than calculating the length of a word. Also, since there may be kerning involved that adjusts the space between letters based on the letter pairs, you can't add up the character widths to arrive at the word width.

If you end up needing to split a word midway, use a binary search to find the cutoff point

This goes with the two above, but you won't really know the best route until you profile.

Make sure you're not using a linked list

You add the string to the list (vector?) and modify it for each character. If this is a linked list instead of an array, it will be very costly. I'm not very familiar with the STL if that's what you're using (those declarations would help), so maybe it maintains a tail pointer. In any case, I would build each line and add it to the list only once it's complete even if you're using an array-based vector. It just seems cleaner.

Show a disabled scroll bar instead of restarting once you determine that scrolling is necessary

Really, a disabled scroll bar isn't that horrendous. ;)

Calculate the widest line as you wrap

I'm betting that the work done in updateWidestLine() is very similar to what you're already doing in makeLinesFromWordWrap(). Take advantage of that and maintain a maxLength local variable as you do the wrapping.

Answer 2

One obvious improvement would be to store an array of split points instead of text rows. Say we have this string:

This is some text

We find a break point between "some" and "text". In this algorithm, you have the following stored:

Original string = "This is some text"
textRows[0] = "This is some"
textRows[1] = "text"

The repetition isn't necessary and creating the textRows vector involves a lot of pointless string copying. It'd be better to store this instead:

Original string = "This is some text"
textSplit[0] = 12
textSplit[1] = 16

To print the text:

lastSplit = 0
for i = 0 to len(textSplit)
    print original text from lastSplit to textSplit[i]
    print linebreak
    lastSplit = textSplit[i]