On 01/04/2021 22:10, Huw Davies wrote:
On Thu, Apr 01, 2021 at 04:07:00PM +0300, Gabriel Ivăncescu wrote:
On 01/04/2021 10:52, Huw Davies wrote:
On Wed, Mar 31, 2021 at 03:35:58PM +0300, Gabriel Ivăncescu wrote:
Did you consider using a lazy initialization of the lookup table instead?
Huw.
Lazy initialization meaning build it as we scan the image? That would work too.
Yes, build the lookup using rgb_to_pixel_colortable() as needed.
I also thought of caching the color tables globally.
Now I don't know if that's acceptable, but here's my idea since it's what is good in "practice":
Hold a small fixed size global cache (4-5 entries) of color tables, with synchronization in case of multi-threading (just for correctness, I doubt any app will actually multi-thread this). If we go the lazy initialization approach, we'll also keep track which of the entries were not filled yet in the cache.
It would be a global table for all color tables, but since I expect all the performance problems to be using the same color table over and over again in a loop, it would work "in practice".
When we have to discard/replace one, we choose the oldest one that wasn't accessed (we keep some timestamp on each cache). Does that sound feasible?
Maybe if I end up using this global cache, I can discard the lazy init since it complicates things, do you think that's better?
Hooking up the global one is going to be more complicated. I suggest you try the (local) lazy init version first.
Huw.
The lazy init will mostly just help with small images, and may also add some overhead for large images, since now we'll have to check each pixel whether it's been initialized or not.
But the larger concern is that it makes the global cache harder to implement. We'll have to "merge" the tables at the end etc. Actually, the cache itself is pretty simple without lazy init, and can all be contained within the rgb_lookup_colortable_init function.
I think I'll send the cached version first so you can get an idea, maybe it's simpler than you expected.
Also, this will allow later to improve the algorithm so it generates the table faster, like the one I originally had but was wrong, which won't be possible with lazy init. For example, just scan through all six directions (front/back, left/right, up/down) in squares and don't assume distances are smaller, so we still check the distance on each conflict, but when one direction is blocked we stop checking it for that color—which will be the main advantage here.
I'm also thinking of a lookup table to do the walk now, in proper order, depending on how big it becomes.
But anyway I leave that for possibly later, I'll send the cache first so you can get an idea why it's not very complicated without lazy init.