# Can calculation of word wrapping be made notably faster?

I need to re-wrap a text so that it fits a given width, font and DC. The result needs to be an array of lines. I use the following code:

private struct SplitInfo
{
public string Word;

public string SplitChar;

public override string ToString()
{
return Word;
}
}

private static float GetWidth(Graphics gr, string text, Font font)
{
SizeF size = gr.MeasureString(text, font, 10000, StringFormat.GenericTypographic);
return size.Width;
}

public static string[] WrapText(string text, IntPtr hdc, Font font, int textWidthInLoMetric)
{
// Split words at space (functionality for splitting at multiple different chars omitted for simplicity).
// This is also why it needs SplitInfo to store the words.
List<SplitInfo> words = new List<SplitInfo>(text.Split(' ').Select(x => new SplitInfo { SplitChar = " ", Word = x }));

StringBuilder resultText = new StringBuilder();
string currentLine = string.Empty;
SplitInfo lastWord = new SplitInfo { Word = string.Empty, SplitChar = string.Empty };

using (Graphics gr = Graphics.FromHdc(hdc))
{
while (true)
{
string newString = (currentLine + lastWord.SplitChar).TrimStart(' ') + words[0].Word;

if (currentLine != string.Empty && GetWidth(gr, newString, font) > textWidthInLoMetric)
{
// Word no longer fits in line.
resultText.Append(currentLine.TrimEnd() + "\n");
currentLine = string.Empty;
}
else
{
lastWord = words[0];
words.RemoveAt(0);
currentLine = newString;
}

if (words.Count == 0)
{
resultText.Append(currentLine.TrimEnd() + "\n");
break;
}
}
}

return resultText.ToString().TrimEnd().Split('\n');
}


Performance measurement shows that MeasureString is the main time consumer here (~90%). Is there any clever way to reduce the number of MeasureString calls? Other than that, I don't see opportunities to make word wrapping significantly faster.

-
I was just wondering if the width of a rendered word can calculated from the sum of the letters that make it up, if do you could cache one the size of each letter. If not an exact match it could be used an as approximation maybe. – Leopoldo Salvo Apr 9 '14 at 23:36
Nope, that's not enough. It really needs to be accurate and match the actual drawing. – floele Apr 10 '14 at 6:01

## 2 Answers

First, I'd like to say that your code is written very well, and is quite readable.

As for your question - your code runs MeasureString at least once per word in your text. Since a line should be (quite) longer than a single word, I think you can reduce the number of calls substantially.

I can think of two strategies:

## 1. Binary search

• Check if the whole text can fit in one line - if yes - you are done!
• If not - take (about) half of the text, and wrap it.
• Append the last line of the first half to the remaining text (unless it all fit in a single line), and wrap that text

This strategy might need a little refining, but it should reduce the number of calls to MeasureString considerably.

## 2. Approximate line length

• Use your current solution to find the first line. Note the line length (in characters).
• Take next X words in the remaining text whose length is at most the previous line's length, and check if it fits in a single line.
• If it does - continue as before (add a word until it doesn't fit)
• If it does not repeat - take one word out, and try again.
• Wash, rinse, repeat

In this solution all MeasureString calls should be relevant, as they should be around the actual length of each line.

-
"I'd like to say that your code is written very well, and is quite readable." - thx, I'm glad to hear that. I feared that my approach was a bit too simplistic. Based on your suggestions though it seems like without some additional complexity it's not possible to improve the speed a lot. Something like "binary search" was also floating around in my head but I considered it overkill so far and believed that there might be entirely better approches for such a common problem. Maybe I indeed need to try it... – floele Apr 9 '14 at 16:36
I would suggest you start from my second suggestion, while I wrote the binary search solution, I felt that it might have some nasty edge-conditions that I might have missed. The approximate length solution seems easier to describe, so it might also be easier to implement... – Uri Agassi Apr 9 '14 at 16:58

One possibility is to cache the measured length for each word. I do this, when the line breaks need to be recalculated (i.e. when document needs to be reflowed) frequently, for example because the user edits words or the user resizes the width of the control.

A second possibility is to use different APIs, for example:

• A different StringFormat value passed as a parameter
• A different method for example TextRenderer.MeasureText instead of Graphics.MeasureString

My code says ...

        //http://msdn.microsoft.com/en-us/magazine/cc163630.aspx#S7 i.e.
//"Practical Tips For Boosting The Performance Of Windows Forms Apps" in MSDN says,
//
//It's better to use the TextRenderer method overloads that do not get IDeviceContext as an argument.
//These methods are more efficient because they use a cached screen-compatible memory device context
//rather than retrieving the native handle for device context from the internal DeviceContext and
//creating an internal object to wrap it.
//
//My profiling shows that the method without the Graphics parameter takes 0.025 msec instead of 0.1 msec.
//However, the resulting calculation is inaccurate.
Size size = TextRenderer.MeasureText(
m_graphics,
text,
paintStyle.font,
proposedSize,
textFormatFlags);


... and ...

    static TextFormatFlags textFormatFlags =
TextFormatFlags.NoPrefix |
TextFormatFlags.NoPadding |
TextFormatFlags.ExternalLeading |
TextFormatFlags.Left |
TextFormatFlags.Bottom;


This code recalculates dozens of pages in a fraction of a second (and because it caches the measured word sizes it only measures all words once, when the document is first loaded).

The corresponding method which I use for drawing the text is:

        TextRenderer.DrawText(
m_graphics,
text,
paintStyle.font,
drawingPoint,
color,
textFormatFlags);

-
I don't think TextRenderer measurement will match the actual drawing, I need the device context anyway (and it also needs to be somewhat accurate). Can you explain which of these TextFormatFlags should make a difference and why? – floele Apr 9 '14 at 17:08
@floele I updated my answer. The flags are documented; they disable various types of margin which would otherwise be automatically inserted around the text. I don't want that kind of margin around each word (instead I measure my own space between words as the width of " "). – ChrisW Apr 9 '14 at 17:14
Certainly the flags are documented, but I don't think the docs say much about the actual performance difference (if any). Since I measure text drawn by a C++ application, TextRenderer is not used for drawing btw. – floele Apr 9 '14 at 17:16
@floele The article I cited i.e. msdn.microsoft.com/en-us/magazine/cc163630.aspx#S7 comments on performance of the flags, and says that different flags have different performance (which is easy to verify by experiment). – ChrisW Apr 9 '14 at 21:00
Thanks, that seems useful. Will check it out. – floele Apr 9 '14 at 21:02