[PATCH 2/2] gdi32: Generate and use a lookup cache when looking up RGB values for a color table.

[Gabriel Ivăncescu]

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.