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 _______________________________________________ squid-dev mailing list [email protected] http://lists.squid-cache.org/listinfo/squid-dev
