|
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é.
modified 11-Nov-22 12:24pm.
|
|
|
|
|
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.
|
|
|
|
|
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.
|
|
|
|
|
When the dance is over the piper must be paid. Only two forms of currency are accepted:
- CPU cycles
- Memory (cache aligned)
Loans and credit are not available! 
|
|
|
|
|
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 
"If you just follow the bacon Eddy, wherever it leads you, then you won't have to think about politics." -- Some Bell.
|
|
|
|
|
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.
|
|
|
|
|
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.
|
|
|
|
|
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.
|
|
|
|
|
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?
|
|
|
|
|
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?
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.
|
|
|
|
|
Awesome,
Just giving feedback. It sometimes helps to have other opinions and ideas.
|
|
|
|
|
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.
|
|
|
|
|
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 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.
|
|
|
|
|
I found out there's a bug in Espressif's codebase that prevents my parallel i8080 code from linking against their esp32s3 stuff.
I found out there's a hardware limitation of the esp32s3 and a corresponding bug wherein it just decides to drop data after the first 32KB sent over DMA. It returns success, naturally.
I found out the new decoupled bus framework they have (that I feel like was stolen from me  ) was designed for LVGL and only LVGL, does not support rapid fill ops and does not support reading back from the display.
Leaving me with no clean way to use this new equipment I have, except with LVGL.
I like LVGL, but it's C, and it looks the part. Do you know what a screen composed of widgets looks like when it's built in C? The code is ugly. Handles, EVERYWHERE.
Every avenue I've taken to create new graphics projects on this new equipment has run into some significant barrier, usually that shouldn't be there.
Leaving me at 1:30am with nothing to do. 
To err is human. Fortune favors the monsters.
|
|
|
|
|
Rust to the rescue!
|
|
|
|
|
honey the codewitch wrote: Leaving me at 1:30am with nothing to do.
Most decent folks are asleep at that hour...
Freedom is the freedom to say that two plus two make four. If that is granted, all else follows.
-- 6079 Smith W.
|
|
|
|
|
I have a segmented sleep pattern which leaves me awake at odd hours.
To err is human. Fortune favors the monsters.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
