В порядке эксперимента применил АВЛ-дерево для хранения кэша текстур. Скорость рендера тестового текста в 150 слов возросла в пять раз (если сравнивать с субтекстурированием) и в десять раз (если сравнить с обычным текстурированием) и перестала падать с увеличением слов на экране. При этом, естественно, используется обычное текстурирование. Успех налицо!

Исходник дерева скопипастил изпримеров для книги "Алгоритмы и структуры данных", некоторые прикладные моменты подсмотрел вListsDict.

Теперь осталось расширить ключ дерева, добавить стиль шрифта. Или делать "дерево в дереве". Вероятно, полезным окажется префиксное дерево. И добавить темпоральную деградацию дерева, с постепенным уничтожением неиспользуемых текстур.