"Use C!" they said. "It will be fun!", they said
-
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 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.
Then I can recommend this movie: Caché.
-
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.
A couple of simple least recently accessed mechanisms that I can think of are - A global integer that increments on every access and is written against the item accessed. When space is needed, free the item(s) with the lowest access values. Low overhead for accesses but could be expensive when freeing space, especially if there are a fair number of items or space often needs to be freed. Also needs to handle the access counter wrapping around. - A two-way queue. When an item is accessed, exqueue it and put it at the front of the queue. When space is needed, free the item(s) at the end of the queue. More expensive for accesses but faster at freeing space. I've got a sense that I don't understand your constraints, because you've probably ruled these approaches out for some reason.
Robust Services Core | Software Techniques for Lemmings | Articles
The fox knows many things, but the hedgehog knows one big thing. -
A couple of simple least recently accessed mechanisms that I can think of are - A global integer that increments on every access and is written against the item accessed. When space is needed, free the item(s) with the lowest access values. Low overhead for accesses but could be expensive when freeing space, especially if there are a fair number of items or space often needs to be freed. Also needs to handle the access counter wrapping around. - A two-way queue. When an item is accessed, exqueue it and put it at the front of the queue. When space is needed, free the item(s) at the end of the queue. More expensive for accesses but faster at freeing space. I've got a sense that I don't understand your constraints, because you've probably ruled these approaches out for some reason.
Robust Services Core | Software Techniques for Lemmings | Articles
The fox knows many things, but the hedgehog knows one big thing.I'm doing the first one, basically. Except instead of a global it's a cache specific incrementer. I was trying to remove some of the crawls by keeping track of the last age I freed but it didn't work. Also I ran into some other issues. It's just annoying not being able to abstract this stuff the way I'd like to.
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.
It was fun, when I could search the memory for a value; say the 366 gold I start with in Pirates! and just change it. The amount of men once I attack Panama? Well, just enough to die after we raid Cartegena to divide up the plunder! It is C#, just more verbose at times.
Bastard Programmer from Hell :suss: "If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
-
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.
honey the codewitch wrote:
And it all has to perform or it defeats its own purpose.
That's the challenge. :) Personally, I treat C as a high-level assembly language. I use it in almost all places that I would have used assembly language 40 years ago, the exceptions being hardware addressing and code that requires extremely high, processor-dependent, levels of optimization. I am aware that some embedded C compilers have extensions that allow hardware addressing, but there is a tendency by some programmers to use those everywhere, rather than just in a hardware interface module. This makes porting the software difficult to impossible. If portability is an issue, forcing programmers to write portable C with a few non-portable assembly language modules works better, IMO.
Freedom is the freedom to say that two plus two make four. If that is granted, all else follows. -- 6079 Smith W.
-
honey the codewitch wrote:
And it all has to perform or it defeats its own purpose.
That's the challenge. :) Personally, I treat C as a high-level assembly language. I use it in almost all places that I would have used assembly language 40 years ago, the exceptions being hardware addressing and code that requires extremely high, processor-dependent, levels of optimization. I am aware that some embedded C compilers have extensions that allow hardware addressing, but there is a tendency by some programmers to use those everywhere, rather than just in a hardware interface module. This makes porting the software difficult to impossible. If portability is an issue, forcing programmers to write portable C with a few non-portable assembly language modules works better, IMO.
Freedom is the freedom to say that two plus two make four. If that is granted, all else follows. -- 6079 Smith W.
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.
-
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.
A technique I have used is to create an index table of hashtables. Multiple hash tables shortens the look up for each. But, indexing them requires some sort of grouping criteria (or than they can just have an index that is also in a hash table but with no collisions lists, but that gets complicated) hashtable[0] = keywords, hashtable[1] = usernames, hashtable[2] = columns, ... I agree "recently used" is always more complicated. One algorithm I have contemplated: tag each hashtable with a length and use count tag each entry in table with use count after some arbitrary hashtable length and use count has been reached then every time a collision list checked (usually hash tables end up with multiple collision lists) remove an entry whose use count is less than some arbitrary use count (say < 2 ). I know I may have missed something, but this is the "gist" of it.
"A little time, a little trouble, your better day" Badfinger
-
I'm doing the first one, basically. Except instead of a global it's a cache specific incrementer. I was trying to remove some of the crawls by keeping track of the last age I freed but it didn't work. Also I ran into some other issues. It's just annoying not being able to abstract this stuff the way I'd like to.
To err is human. Fortune favors the monsters.
-
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.
