Repository navigation
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;
}
Activity
windows-server-2003 commentedon Sep 18, 2022
P.S.
Test on old 3DS
Current: 4.1k calls/s = 68 characters/frame
Binary search: 133k calls/s = 2.2k characters/frame
mtheall commentedon Sep 18, 2022
You know I thought about this while implementing bcfnt but the format doesn't guarantee that the glyphs are sorted. Can we assume that they are always sorted? Output from bcfnt will be. We could easily check all the official system fonts. Do we care about fonts from anywhere else?
fincs commentedon Sep 18, 2022
I think we should only care about official system fonts + fonts created by our own mkbcfnt tool.
piepie62 commentedon Sep 18, 2022
Theoretically I could see an argument for caring about game fonts but I find it unlikely that they won't match system fonts; the conversion tool used is very likely the same
WinterMute commentedon Dec 9, 2022
A PR would be very much appreciated if you're still interested in pursuing this.