"Use C!" they said. "It will be fun!", they said
-
For this I don't need to drop to assembly or anything fancy. In fact, the generation time for these cached items is such that the cache itself could perform pretty badly and still provide substantial performance improvements. When I wrote that I was more speaking in terms of principle, *except* when it comes to expiring items. That's the one area where it really concerns me because I have to crawl the entire cache.
To err is human. Fortune favors the monsters.
You have two problems here, which should ideally be solved using two mechanisms. Note that an object's handle won't work as an LRU timestamp because it is fixed, and an LRU timestamp won't work as an object's handle because it is subject to change. The LRU cache maintenance can most easily be performed using a doubly-linked list. This is only one more word per cache node than is used for your timestamp method, is easy to implement, and is extremely fast. Searching the cache is a separate problem. A red-black tree sorted by the objects' handles would solve this problem nicely. If memory constraints prevent you from implementing both LRU and search mechanisms, you will have to fall back to a linear search for one of the operations.
Freedom is the freedom to say that two plus two make four. If that is granted, all else follows. -- 6079 Smith W.
-
You have two problems here, which should ideally be solved using two mechanisms. Note that an object's handle won't work as an LRU timestamp because it is fixed, and an LRU timestamp won't work as an object's handle because it is subject to change. The LRU cache maintenance can most easily be performed using a doubly-linked list. This is only one more word per cache node than is used for your timestamp method, is easy to implement, and is extremely fast. Searching the cache is a separate problem. A red-black tree sorted by the objects' handles would solve this problem nicely. If memory constraints prevent you from implementing both LRU and search mechanisms, you will have to fall back to a linear search for one of the operations.
Freedom is the freedom to say that two plus two make four. If that is granted, all else follows. -- 6079 Smith W.
my issue with the linked list is heap frag, and I'm wondering whether or not a red-black tree would be better than a hashtable given i don't need to keep things in sorted order. What I've been doing (although I ran into issues and probably have to try again) is creating a hashtable. I just needed an integer key, and each entry has an age. The age *increases* when you retrieve something. When it needs to make more room it expires items with the smallest age.
To err is human. Fortune favors the monsters.
-
my issue with the linked list is heap frag, and I'm wondering whether or not a red-black tree would be better than a hashtable given i don't need to keep things in sorted order. What I've been doing (although I ran into issues and probably have to try again) is creating a hashtable. I just needed an integer key, and each entry has an age. The age *increases* when you retrieve something. When it needs to make more room it expires items with the smallest age.
To err is human. Fortune favors the monsters.
-
honey the codewitch wrote:
I just needed an integer key
The memory address is already unique. Can't imagine why you'd need to generate another unique key. :)
Because I need to be able to look it up later. Specifically, I'm caching glyph bitmaps I render from a vector font. They cache needs to be keyed to the ID of the glyph.
To err is human. Fortune favors the monsters.
-
Because I need to be able to look it up later. Specifically, I'm caching glyph bitmaps I render from a vector font. They cache needs to be keyed to the ID of the glyph.
To err is human. Fortune favors the monsters.
Hmmm, Maybe I'm looking at the problem differently. Will you have a cache of a TTF glyph? Why wouldn't it just be an [array index](https://developer.apple.com/fonts/TrueType-Reference-Manual/RM06/Chap6Tables.html#BinSrchHeader)?
-
Hmmm, Maybe I'm looking at the problem differently. Will you have a cache of a TTF glyph? Why wouldn't it just be an [array index](https://developer.apple.com/fonts/TrueType-Reference-Manual/RM06/Chap6Tables.html#BinSrchHeader)?
because a glyph index is a 32 bit integer dictated by the TTF font file it is loaded from. They are unicode. There can be thousands and thousands, and may not be contiguous.
To err is human. Fortune favors the monsters.
-
because a glyph index is a 32 bit integer dictated by the TTF font file it is loaded from. They are unicode. There can be thousands and thousands, and may not be contiguous.
To err is human. Fortune favors the monsters.
honey the codewitch wrote:
because a glyph index is a 32 bit integer
You mean the uint16 [numGlyphs](https://developer.apple.com/fonts/TrueType-Reference-Manual/RM06/Chap6maxp.html)? Are there actually TTF files out in the real world with 65535 glyphs? The TTF file format does support it. PNG, JPEG also support huge image data, but I guess IoT libs should read the size before attempting to render it?
-
honey the codewitch wrote:
because a glyph index is a 32 bit integer
You mean the uint16 [numGlyphs](https://developer.apple.com/fonts/TrueType-Reference-Manual/RM06/Chap6maxp.html)? Are there actually TTF files out in the real world with 65535 glyphs? The TTF file format does support it. PNG, JPEG also support huge image data, but I guess IoT libs should read the size before attempting to render it?
okay, so it's 16-bit. I was going by my api which returns it as an int. Still 65535 is prohibitive. So is 32767 So is 10000 if I only need 5000 I don't know that they're contiguous. The way I load JPGs is iteratively, an 8x8 region at a time, top to bottom, left to right, never loading it all at once. So no I don't read the size before rendering it. Anyway, during this back and forth I finished the LRU hashtable and doubled the framerate of the fonts
To err is human. Fortune favors the monsters.
-
okay, so it's 16-bit. I was going by my api which returns it as an int. Still 65535 is prohibitive. So is 32767 So is 10000 if I only need 5000 I don't know that they're contiguous. The way I load JPGs is iteratively, an 8x8 region at a time, top to bottom, left to right, never loading it all at once. So no I don't read the size before rendering it. Anyway, during this back and forth I finished the LRU hashtable and doubled the framerate of the fonts
To err is human. Fortune favors the monsters.
-
Totally. I didn't mean to sound ungrateful. I just knew I needed the hashtable instead of an array in this case.
To err is human. Fortune favors the monsters.
-
I already don't like writing caches. I especially don't like writing "generalized" containers without templates. And yet here I am, needing a glyph cache to bring my font rendering from 6fps closer to 23fps (my target baseline) And debating about whether it's worth it to generalize it in order to save flash space if someone else needs a similar facility in LVGL. The hashtable part is relatively easy. The least recently accessed expiration mechanism is less so. I just don't like writing caches. It combines everything I don't like about writing containers with even more complexity that's easy to get wrong. And it all has to perform or it defeats its own purpose. Meh.
To err is human. Fortune favors the monsters.
-
I am surprised that you have not made a C++ to C generator yet. Or use some of your code generation tools to generate valid cache code in C? Kind of like TypeScript generating JavaScript.
Really it would amount to writing a C++ compiler. Keep in mind the compiler can run functions at compile time.
To err is human. Fortune favors the monsters.