vtgl

Commit: 850094d55c9d8e3463b16a6b37e021363bfc95f8
Parent: 697c5beeccfbfc7fa274f0c31c1c1dd1b067af37
Author: Randy Palamar
Date:   Sat, 24 Aug 2024 21:54:29 -0600

LRU glyph cache

Diffstat:
M
debug.c
 | 
34
++++++++++++++++++++++++++++++++++
M
font.c
 | 
140
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++--------
M
util.h
 | 
17
+++++++++++++----
M
vtgl.c
 | 
12
+++++++++---

4 files changed, 182 insertions(+), 21 deletions(-)
diff --git a/debug.c b/debug.c
@@ -103,3 +103,37 @@ dump_fb_to_file(Term *t)
 	fclose(f);
 }
 
+static void
+dump_glyph_cache_to_file(FontAtlas *fa)
+{
+	char *fname = "fa.text";
+	FILE *f = fopen(fname, "w");
+	if (!f) return;
+	printf("dumping glyph cache to %s\n", fname);
+
+	GlyphCache *gc        = &fa->glyph_cache;
+	GlyphCacheStats stats = get_and_clear_glyph_cache_stats(gc);
+	fputs("Stats:\n", f);
+	fprintf(f, "hit:     %u\n", stats.hit_count);
+	fprintf(f, "miss:    %u\n", stats.miss_count);
+	fprintf(f, "recycle: %u\n", stats.recycle_count);
+
+	u32 count = 0;
+	fputs("\nChain:\n", f);
+	for (u32 i = gc->glyphs[0].next; i; i = gc->glyphs[i].next) {
+		count++;
+		fprintf(f, "%u -> ", i);
+	}
+
+	fprintf(f, "\n\ncount: %u\n\n", count);
+
+	fputs("Glyphs:\n", f);
+	for (u32 i = gc->glyphs[0].next; i; i = gc->glyphs[i].next) {
+		u32 cp = gc->glyphs[i].cp;
+		s8 encoded = utf8_encode(cp);
+		fwrite(encoded.data, 1, encoded.len, f);
+		fputs(" -> ", f);
+	}
+
+	fclose(f);
+}
diff --git a/font.c b/font.c
@@ -52,24 +52,128 @@ err_fc1:
 	return 0;
 }
 
+static u32
+compute_glyph_hash(GlyphCache *gc, u32 cp)
+{
+	/* TODO: better hash function! */
+	u32 result = (((u64)cp * 1111111111111111111) >> 32) & (gc->cache_len - 1);
+	return result;
+}
+
+static void
+recycle_cache(GlyphCache *gc)
+{
+	CachedGlyph *sentinel = gc->glyphs + 0;
+
+	ASSERT(sentinel->prev);
+
+	u32 last_index    = sentinel->prev;
+	CachedGlyph *cg   = gc->glyphs + last_index;
+	CachedGlyph *prev = gc->glyphs + cg->prev;
+	prev->next        = 0;
+	sentinel->prev    = cg->prev;
+
+	u32 hash_slot   = compute_glyph_hash(gc, cg->cp);
+	u32 *next_index = gc->hash_table + hash_slot;
+	while (*next_index != last_index) {
+		ASSERT(*next_index);
+		next_index = &gc->glyphs[*next_index].next_with_same_hash;
+	}
+	ASSERT(*next_index == last_index);
+	*next_index                   = cg->next_with_same_hash;
+	cg->next_with_same_hash       = sentinel->next_with_same_hash;
+	sentinel->next_with_same_hash = last_index;
+
+	cg->g.size = (uv2){0};
+
+	gc->stats.recycle_count++;
+}
+
+static i32
+pop_free_glyph_entry(GlyphCache *gc)
+{
+	CachedGlyph *sentinel = gc->glyphs + 0;
+
+	if (!sentinel->next_with_same_hash)
+		recycle_cache(gc);
+
+	u32 result = sentinel->next_with_same_hash;
+	ASSERT(result);
+
+	CachedGlyph *cg = gc->glyphs + result;
+	sentinel->next_with_same_hash = cg->next_with_same_hash;
+	cg->next_with_same_hash       = 0;
+
+	return result;
+}
+
+static u32
+get_glyph_entry_index(GlyphCache *gc, u32 cp)
+{
+	u32 result    = 0;
+	u32 hash_slot = compute_glyph_hash(gc, cp);
+	u32 entry_idx = gc->hash_table[hash_slot];
+
+	CachedGlyph *cg;
+	while (entry_idx) {
+		cg = gc->glyphs + entry_idx;
+		if (cp == cg->cp) {
+			result = entry_idx;
+			break;
+		}
+		entry_idx = cg->next_with_same_hash;
+	}
+
+	if (result) {
+		CachedGlyph *prev = gc->glyphs + cg->prev;
+		CachedGlyph *next = gc->glyphs + cg->next;
+		prev->next = cg->next;
+		next->prev = cg->prev;
+		gc->stats.hit_count++;
+	} else {
+		result = pop_free_glyph_entry(gc);
+		cg     = gc->glyphs + result;
+		cg->cp = cp;
+		cg->next_with_same_hash   = gc->hash_table[hash_slot];
+		gc->hash_table[hash_slot] = result;
+		gc->stats.miss_count++;
+	}
+
+	ASSERT(result);
+
+	CachedGlyph *sentinel  = gc->glyphs + 0;
+	CachedGlyph *last_next = gc->glyphs + sentinel->next;
+	cg->next               = sentinel->next;
+	cg->prev               = 0;
+	sentinel->next         = result;
+	last_next->prev        = result;
+
+	return result;
+}
+
+static GlyphCacheStats
+get_and_clear_glyph_cache_stats(GlyphCache *gc)
+{
+	GlyphCacheStats	result = gc->stats;
+	gc->stats              = (GlyphCacheStats){0};
+	return result;
+}
+
 static u32 *
-render_glyph(FontAtlas *fa, Arena a, u32 cp, Glyph *out_glyph, i32 *out_idx)
+render_glyph(FontAtlas *fa, Arena a, u32 cp, Glyph *out_glyph, u32 *out_idx)
 {
 	/* NOTE: first check if glyph is in the cache and valid */
-	/* TODO: better hash function! */
-	u32 idx  = (((u64)cp * 1111111111111111111) >> 32) & (GLYPH_CACHE_LEN - 1);
-	*out_idx = idx;
+	u32 idx         = get_glyph_entry_index(&fa->glyph_cache, cp);
 	CachedGlyph *cg = fa->glyph_cache.glyphs + idx;
 
-	if (cg->cp == cp) {
+	*out_idx = idx;
+	/* TODO: implement a way of ensuring the glyph is actually uploaded to the GPU */
+	if (cg->g.size.w) {
 		*out_glyph = cg->g;
 		return NULL;
-	} else {
-		if (cg->cp != 0)
-			cg->collision_count++;
-		cg->cp = cp;
 	}
 
+	/* TODO: lookup with Font Config */
 	FT_GlyphSlot gs = NULL;
 	for (u32 i = 0; i < fa->nfonts; i++) {
 		FT_Face face = fa->fonts[i].face;
@@ -113,7 +217,7 @@ update_font_metrics(Term *t)
 	t->fa.size.w = 0;
 	t->fa.deltay = 0;
 	Glyph g;
-	i32 index;
+	u32 index;
 	for (u32 i = ' '; i <= '~'; i++) {
 		render_glyph(&t->fa, t->arena_for_frame, i, &g, &index);
 		t->fa.size.h = MAX(t->fa.size.h,  g.size.h);
@@ -126,10 +230,13 @@ update_font_metrics(Term *t)
 }
 
 static void
-invalidate_font_cache(FontAtlas *fa)
+initialize_glyph_cache(GlyphCache *gc)
 {
-	mem_clear((u8 *)fa->glyph_cache.glyphs, 0,
-	          sizeof(*fa->glyph_cache.glyphs) * GLYPH_CACHE_LEN);
+	mem_clear((u8 *)gc->glyphs,     0, sizeof(*gc->glyphs) * gc->cache_len);
+	mem_clear((u8 *)gc->hash_table, 0, sizeof(*gc->hash_table) * gc->cache_len);
+	for(u32 i = 0; i < gc->cache_len - 1; i++)
+		gc->glyphs[i].next_with_same_hash = i + 1;
+	get_and_clear_glyph_cache_stats(gc);
 }
 
 static i32
@@ -163,5 +270,10 @@ init_fonts(Term *t, Arena *a)
 		die("init_fonts: no valid font patterns\n");
 	}
 
-	t->fa.glyph_cache.glyphs = alloc(a, CachedGlyph, GLYPH_CACHE_LEN);
+	static_assert(ISPOWEROFTWO(GLYPH_CACHE_LEN), "GLYPH_CACHE_LEN must be a power of two!");
+	t->fa.glyph_cache.cache_len  = GLYPH_CACHE_LEN;
+	t->fa.glyph_cache.glyphs     = alloc(a, CachedGlyph, t->fa.glyph_cache.cache_len);
+	t->fa.glyph_cache.hash_table = alloc(a, u32,         t->fa.glyph_cache.cache_len);
+
+	initialize_glyph_cache(&t->fa.glyph_cache);
 }
diff --git a/util.h b/util.h
@@ -32,6 +32,8 @@
 #define ISSPACE(c)       ((c) == ' ' || (c) == '\n' || (c) == '\t')
 #define ISPRINT(c)       BETWEEN((c), ' ', '~')
 
+#define ISPOWEROFTWO(a) (((a) & ((a) - 1)) == 0)
+
 /* NOTE: GLFW does not sequentially number keys so switch statement will never be optimized */
 #define ENCODE_KEY(action, mod, key) (((action) << 24) | ((mod) << 16) | ((key) & 0xFFFF))
 
@@ -273,14 +275,21 @@ typedef struct {
 typedef struct {
 	Glyph g;
 	u32   cp;
+	u32   next_with_same_hash;
 	u16   prev, next;
-	u32   collision_count;
 } CachedGlyph;
 
 typedef struct {
-	CachedGlyph *glyphs;
-	u32          mru_index;
-	u32          lru_index;
+	u32 hit_count;
+	u32 miss_count;
+	u32 recycle_count;
+} GlyphCacheStats;
+
+typedef struct {
+	CachedGlyph     *glyphs;
+	u32             *hash_table;
+	u32              cache_len;
+	GlyphCacheStats  stats;
 } GlyphCache;
 
 typedef struct {
diff --git a/vtgl.c b/vtgl.c
@@ -123,13 +123,14 @@ update_font_textures(Term *t)
 	             MAX_FONT_SIZE, MAX_FONT_SIZE, TEXTURE_GLYPH_COUNT,
 	             0, GL_RED, GL_UNSIGNED_BYTE, 0);
 
-	invalidate_font_cache(&t->fa);
+	initialize_glyph_cache(&t->fa.glyph_cache);
 
 	for (u32 i = ' '; i <= '~'; i++) {
-		i32 depth_idx;
+		u32 depth_idx;
 		Glyph g;
 		u32 *data = render_glyph(&t->fa, t->arena_for_frame, i, &g, &depth_idx);
 		if (data) {
+			ASSERT(depth_idx);
 			glTexSubImage3D(GL_TEXTURE_2D_ARRAY, 0, 0, 0, depth_idx,
 			                MAX_FONT_SIZE, MAX_FONT_SIZE, 1, GL_RGBA,
 			                GL_UNSIGNED_BYTE, data);
@@ -171,9 +172,10 @@ update_uniforms(Term *t, enum shader_stages stage)
 static i32
 get_gpu_glyph_index(Term *t, u32 codepoint, Glyph *out_glyph)
 {
-	i32 depth_idx;
+	u32 depth_idx;
 	u32 *data = render_glyph(&t->fa, t->arena_for_frame, codepoint, out_glyph, &depth_idx);
 	if (data) {
+		ASSERT(depth_idx);
 		glTexSubImage3D(GL_TEXTURE_2D_ARRAY, 0, 0, 0, depth_idx,
 		                MAX_FONT_SIZE, MAX_FONT_SIZE, 1, GL_RGBA,
 		                GL_UNSIGNED_BYTE, data);
@@ -553,6 +555,10 @@ key_callback(GLFWwindow *win, i32 key, i32 sc, i32 act, i32 mods)
 		dump_fb_to_file(t);
 		return;
 	}
+	if (key == GLFW_KEY_F3 && act == GLFW_PRESS) {
+		dump_glyph_cache_to_file(&t->fa);
+		return;
+	}
 	#endif
 
 	if (mods & GLFW_MOD_CONTROL && key < 0x80) {