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
