Nicolas Pitre <nico@xxxxxxx> writes: >> > Instead of treating the "the last used one happened to be on the >> > horizon -- try not to drop it" special case, I wonder if it >> > makes sense to float the last used delta base object early in >> > the window _after_ it is used. Wouldn't we keep more than one >> > very recently used delta base objects in the window that way? >> >> The attached is my quick-and-dirty one. > > I like this. A LRU sorting of base objects is obviously a good thing to > do. Some comments below. Well, I said it is Q&D, because _I_ didn't like what I did ;-). The original implementation of window as a plain array of "struct unpacked" made perfect sense because its use was strict FIFO. Adding new element and expiring oldest element was just an increment of the "idx" integer, and there was no memmove overhead. If we are to make this into LRU (which I _do_ like), however, the data structure's circular FIFO origin makes the code unnecessary complex and inefficient, I think. - We can always say 0 is the bottom and (window-1) is the top. Then ((idx+1)%window) becomes unnecessary. As a bonus, we do not have to disagree if it should be (window <= idx) or (idx >= window). - Shifting elements down to make room can become a single memmove() if we remove the circular FIFO origin from the window implementation. The Q&D one has tons of structure assignments in each iteration. It might even make sense to change the window itself an array of "struct unpacked *" and make LRU management into just memmove() of bunch of pointers. - To unsubscribe from this list: send the line "unsubscribe git" in the body of a message to majordomo@xxxxxxxxxxxxxxx More majordomo info at http://vger.kernel.org/majordomo-info.html
