BIND 10 #192: Data source hotspot cache

[BIND 10 Development]

#192: Data source hotspot cache
-------------------------+--------------------------------------------------
 Reporter:  each         |        Owner:  jinmei                                        
     Type:  enhancement  |       Status:  reviewing                                     
 Priority:  major        |    Milestone:  05. 3rd Incremental Release: Serious Secondary
Component:  b10-auth     |   Resolution:                                                
 Keywords:               |    Sensitive:  0                                             
-------------------------+--------------------------------------------------

Comment(by jinmei):

 Replying to [comment:32 each]:

 > > See the attached patch.  This is what I'd do if I were to use
 std::list for this purpose.  This version doesn't have the performance
 problem you raised.
 >
 > If you're certain of that, then I have no objection.

 This is true.  See http://www.cplusplus.com/reference/stl/list/erase/

   Complexity: Linear on the number of elements erased (destructors).

 Since in our case the number of elements is 1, it's constant.
 push_front() and push_back() are also constant-time operations (as we can
 reasonably expect for lists).

 > I sort of disagree about the readability; I find the C-like version
 easier to understand--but that's just because I understand C and don't
 really understand STL very well.  Take this, for example:
 >
 > {{{
 >     lru_.erase(node->lru_entry_);
 >     lru_.push_front(node);
 >     node->lru_entry_ = lru_.begin();
 > }}}
 >
 > I accept your assurance that it does the right thing, but I would never
 have guessed it did.  An old iterator can be preserved through list state
 changes and still be meaningful?  I'm surprised to learn this, but if it
 works, I'm happy with it.

 It's difficult to parse the question...but if I understnad it correctly,
 the answer is yes.  Again, see
 http://www.cplusplus.com/reference/stl/list/erase/

   lists are sequence containers specifically designed to be efficient
 inserting and removing elements in any position, even in the middle of the
 sequence. Compared to the other base sequence containers (vector and
 deque), lists are the most efficient container erasing at some position
 other than the beginning or the end of the sequence, and, unlike in these,
 all of the previously obtained iterators and references remain valid after
 the erasing operation and refer to the same elements they were referring
 before (except, naturally, for those referring to erased elements).

 Overall, std::list is carefully designed so that it ensures the properties
 we'd expect for "a list".

 Admittedly, though, the validity of iterators on modification to the list
 may not be so obvious, especially because it's not the case for
 std::vector.

-- 
Ticket URL: <https://bind10.isc.org/ticket/192#comment:34>
BIND 10 Development <http://bind10.isc.org>
BIND 10 Development