|
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.
|
|
|
|
|
I read a study that people that live without sun/circadian reference fall into a 28 hour cycle. So I tried living a 6 day week at 28 hours/ day.
My employer was not too thrilled. I also missed my 2 day weekend!
|
|
|
|
|
#Worldle #246 1/6 (100%)
🟩🟩🟩🟩🟩🎉
https://worldle.teuteuf.fr
|
|
|
|
|
#Worldle #246 1/6 (100%)
🟩🟩🟩🟩🟩🎉
https://worldle.teuteuf.fr
"A little time, a little trouble, your better day"
Badfinger
|
|
|
|
|
🟩🟩🟩🟩🟩🎉
Life should not be a journey to the grave with the intention of arriving safely in a pretty and well-preserved body, but rather to skid in broadside in a cloud of smoke, thoroughly used up, totally worn out, and loudly proclaiming “Wow! What a Ride!" - Hunter S Thompson - RIP
|
|
|
|
|
#Worldle #245 5/6 (100%)
🟩⬜⬜⬜⬜⬅️
🟩🟩🟩🟩🟨↙️
🟩🟩🟩🟩⬜↘️
🟩🟩🟩🟩🟨↖️
🟩🟩🟩🟩🟩🎉
https://worldle.teuteuf.fr
Had to do several binary searches and the map.
"A little time, a little trouble, your better day"
Badfinger
|
|
|
|
|
Yep. That's the one which made me give up playing it. Let's be honest, it wouldn't show up on the map of a large town, so how the heck you are supposed to find it with no sense of scale on a world map without using a map and triangulation I dunno.
And there will be more like this as they start to run out of "real countries" to work with...
Nope, I'll stick to Wordle!
"I have no idea what I did, but I'm taking full credit for it." - ThisOldTony
"Common sense is so rare these days, it should be classified as a super power" - Random T-shirt
AntiTwitter: @DalekDave is now a follower!
|
|
|
|
|
It is also true that the number of choices for Worldle are much less than the number for Wordle. There are only 190+ countries in the world, and this means that even if they cover all the "registered countries", then they will have to repeat after 190+ days. So, perhaps they want to include the smallest of the small countries in their game.
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
