[squid-dev] [PATCH] cleanup external_acl_type cache

[Amos Jeffries]

On 13/04/2017 2:27 a.m., Alex Rousskov wrote:
> On 04/12/2017 06:08 AM, Adam Majer wrote:
>> On 04/12/2017 03:48 AM, Alex Rousskov wrote:
>>> BTW, if you do end up removing this intrusive list, please check whether
>>> its ExternalACLEntry::lru "anchor" member should be removed as a side
>>> effect. Perhaps you already have checked that.
> 
>> Or replaced with list::iterator to allow for O(1) list::erase operation.
> 
> IMO, storing std::list::iterator would combine some of the worst
> features of the two approaches:
> 
> * metadata de/allocation overheads of a non-intrusive std::list
> * anchor awkwardness/risks/limitations of an intrusive list
> 
> One might even be able to formulate a related Rule of Thumb: If all the
> list elements have to store their position in their list (for any
> reason), then a performance-sensitive code should use an intrusive list.
> 

The current O(1) is achieved only through the way dlink requires an
iterator raw-pointer to be stored in the Entry itself, not the list
owner object. That itself is a yuck factor that causes us a lot of
pointer invalidation problems changing this code.

Going a step back to fundamentals. This list is just a part of the full
external ACL caching algoritm. It has a 1:1 pairing with the hash
'cache' member of the same class.

I'm now looking into the LruMap performance to replace the whole system.
I had thought this list replacement was an easy step to get part of the
complexity. But it seems not.

Long term I would like to drop lru_list (and maybe Entry too) from
external_acl in favour of a cache member of type LruMap hiding all the
complex stuff.


> 
>> If you need an intrusive list container for performance reasons, please
>> consider using Boost.Intrusive instead of rolling your own.
>>
>>     http://www.boost.org/doc/libs/1_63_0/doc/html/intrusive/list.html
> 
> The idea of using Boost for Squid has been discussed and, IIRC, rejected
> (for the time being): We have more than enough troubles coping with
> standard C++ features. Dealing with another major library (that should
> penetrate a lot of Squid code to gain the most benefits) without an
> in-house Boost expert is a bad idea, especially when the Squid code
> itself is still too messy to allow for neat/safe conversions like that.
> C++11 reduces the pressure to use Boost by providing some of the Boost
> features.
> 
> To avoid misunderstanding, I have nothing but respect for Boost, I am
> sure that the overall quality of Boost code is much higher than what we
> write, and I hate reinventing the wheel. Unfortunately, the other
> factors are more important in this case.
> 

Ack, same opinion here.

Boost has some nice things but most of that is becomming standardised
faster than we are converting to use C++ properly. :-(

Amos