Good point, I went ahead and ditched he comment. If we need to improve this in future, we'll do it.
Ethan On Wed, Sep 4, 2013 at 2:40 PM, Ben Pfaff <b...@nicira.com> wrote: > On Wed, Sep 04, 2013 at 12:37:35PM -0700, Ethan Jackson wrote: >> Managing eviction groups from threads was going to be difficult to do >> in a performant thread-safe manner, so this patch punts the problem to >> the main thread. >> >> Signed-off-by: Ethan Jackson <et...@nicira.com> > > I think that the comment is slightly pessimistic in that > heap_rebuild() has O(n) cost whereas any sort would have O(n lg n) > cost. The difference might not be significant. >> + /* XXX: The heap isn't giving us much here. It would be much >> + * simpler to maintain the rules in loosely sorted order and >> once a >> + * second used qsort() to enforce the invariant. We've >> effectively >> + * implemented heap sort here instead. */ > > Instead of a sort-based algorithm, one can imagine something much > simpler and probabilistic. For example: randomly choose three > different rules from the largest eviction group, then evict the one > that was least recently used. (I don't know whether this would be > acceptable in practice, since it has a chance of evicting a recently > used rule.) > > Acked-by: Ben Pfaff <b...@nicira.com> _______________________________________________ dev mailing list dev@openvswitch.org http://openvswitch.org/mailman/listinfo/dev
