Performance issue in font.c #509
Description
The function fontGlyphIndexFromCodePoint is called for every character when drawing text with citro2d, for example.
The system font seems to handle characters using three mappings: CMAP_TYPE_DIRECT, CMAP_TYPE_TABLE, CMAP_TYPE_SCAN
The first two are fine, but for CMAP_TYPE_SCAN libctru currently does a linear search, which may be slow.
It seems that the codepoints of the characters in one CMAP_TYPE_SCAN cmap are monotonically increasing, so we can do a binary search to significantly reduce running time.
In fact, on my JPN 3ds, the mapping of the default font includes one cmap of type CMAP_TYPE_SCAN with 5811 characters in it.
I test on a new 3ds with "龍" (Dragon) which is one of the standard Japanese characters with a large codepoint, and it was only 15k calls/s. This means we can only draw 250 characters if it's 60FPS.
On my test implementation of the binary search, it marked 500k calls/s: 8000 characters/frame
I am curious if you would accept a PR if I did.
Here is my test implementation to see how simple it would be:
Test implementation
Before:
int j;
for (j = 0; j < cmap->nScanEntries; j ++)
if (cmap->scanEntries[j].code == codePoint)
break;
if (j < cmap->nScanEntries)
{
ret = cmap->scanEntries[j].glyphIndex;
break;
}
After:
int l = -1;
int r = cmap->nScanEntries;
while (r - l > 1)
{
int middle = l + (r - l) / 2;
if (cmap->scanEntries[middle].code > codePoint) r = middle;
else l = middle;
}
if (l >= 0 && cmap->scanEntries[l].code == codePoint)
{
ret = cmap->scanEntries[l].glyphIndex;
break;
}