On Fri, Feb 22, 2019 at 05:21:51PM -0800, Han Zhou wrote: > On Fri, Feb 22, 2019 at 3:04 PM Ben Pfaff <[email protected]> wrote: > > > > Using HMAP_FOR_EACH_SAFE_WITH_HASH tends to imply that an hmap can have > > more than one item with a given key. Nothing prevents that, and it will > > otherwise work, but it is unusual and it normally makes sense to use an > > hindex instead of an hmap for efficiency's sake if it is going to happen > > very often. Does the data structure in question often have duplicates? > > Should we change it to an hindex? > > Hi Ben, I think you are asking if there can be more than one item with > a given "hash value". Yes it is possible, but it should not be often > for the data structure in question here - the json cache. The key is > uuid of the change set combined with monitor version, and the hash is > the uuid_hash. So conflicts of uuid_hash should be rare. When there > are different versions (e.g. monitor v1, v2, v3) of clients referring > same change sets we do get more items with same hash value, but there > were at most 2 versions and I am adding 1 more in next patches in the > series, and I guess it is not likely we add too many versions of > monitors in the future, and even that is possible, it is unlikely that > many different versions of clients co-exists in same environment. So I > don't think it has a real impact to performance. > > The reason for using HMAP_FOR_EACH_SAFE_WITH_HASH instead of > HMAP_FOR_EACH_WITH_HASH is just because the node is going to be > removed and freed in the loop. It needs to be safe regardless of the > probability of hash conflicts.
It's important to be clear about the difference between hashes and keys. The hash is what's stored in the hmap_node (that is, the uuid_hash() return value in this case), the key in this case is what uuid_equals() compares. I *think* you are saying there can be a small number of duplicate keys in the hmap in this case. Is that correct? _______________________________________________ dev mailing list [email protected] https://mail.openvswitch.org/mailman/listinfo/ovs-dev
