You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@mesos.apache.org by Benjamin Bannier <be...@mesosphere.io> on 2017/12/11 13:31:25 UTC
Review Request 64496: Avoided unnecessary work in contains checks in
hashset and hashmap.
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/64496/
-----------------------------------------------------------
Review request for mesos and Michael Park.
Repository: mesos
Description
-------
In order to check whether a key or value was present in a 'hashset' or
'hashmap' we were checking whether the count for that entry was
greater than zero. In order to count elements a complete traversal of
the container is required, while a contains check already has an
answer when the first element has been found.
This patch uses find in contains check for both hashset and hashmap to
avoid the full traversal.
Diffs
-----
3rdparty/stout/include/stout/hashmap.hpp 91085b8d8ad5d35c39c8cc95e3d4765d82d9a8db
3rdparty/stout/include/stout/hashset.hpp 6af209c53185207b53396e7687e3bd7357e57bf1
Diff: https://reviews.apache.org/r/64496/diff/1/
Testing
-------
`make check`
Thanks,
Benjamin Bannier
Re: Review Request 64496: Avoided unnecessary work in contains checks
in hashset and hashmap.
Posted by Andrew Schwartzmeyer <an...@schwartzmeyer.com>.
> On Dec. 11, 2017, 10 a.m., Andrew Schwartzmeyer wrote:
> > Ship It!
Hm, I might take this back. The hypothesis:
> In order to count elements a complete traversal of
the container is required, while a contains check already has an
answer when the first element has been found.
While it sounds right, if you check [unordered_map::count](http://en.cppreference.com/w/cpp/container/unordered_map/count) and [unordered_set::count](http://en.cppreference.com/w/cpp/container/unordered_set/count), it does not work like this as these data structures may have at most one matching element.
> Returns the number of elements with key that compares equal to the specified argument key, which is either 1 or 0 since this container does not allow duplicates.
And the stated complexity is:
> Constant on average, worst case linear in the size of the container.
Which is the same as [find](http://en.cppreference.com/w/cpp/container/unordered_map/count).
- Andrew
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/64496/#review193411
-----------------------------------------------------------
On Dec. 11, 2017, 5:31 a.m., Benjamin Bannier wrote:
>
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://reviews.apache.org/r/64496/
> -----------------------------------------------------------
>
> (Updated Dec. 11, 2017, 5:31 a.m.)
>
>
> Review request for mesos and Michael Park.
>
>
> Repository: mesos
>
>
> Description
> -------
>
> In order to check whether a key or value was present in a 'hashset' or
> 'hashmap' we were checking whether the count for that entry was
> greater than zero. In order to count elements a complete traversal of
> the container is required, while a contains check already has an
> answer when the first element has been found.
>
> This patch uses find in contains check for both hashset and hashmap to
> avoid the full traversal.
>
>
> Diffs
> -----
>
> 3rdparty/stout/include/stout/hashmap.hpp 91085b8d8ad5d35c39c8cc95e3d4765d82d9a8db
> 3rdparty/stout/include/stout/hashset.hpp 6af209c53185207b53396e7687e3bd7357e57bf1
>
>
> Diff: https://reviews.apache.org/r/64496/diff/1/
>
>
> Testing
> -------
>
> `make check`
>
>
> Thanks,
>
> Benjamin Bannier
>
>
Re: Review Request 64496: Avoided unnecessary work in contains checks
in hashset and hashmap.
Posted by Andrew Schwartzmeyer <an...@schwartzmeyer.com>.
-----------------------------------------------------------
This is an automatically generated e-mail. To reply, visit:
https://reviews.apache.org/r/64496/#review193411
-----------------------------------------------------------
Ship it!
Ship It!
- Andrew Schwartzmeyer
On Dec. 11, 2017, 5:31 a.m., Benjamin Bannier wrote:
>
> -----------------------------------------------------------
> This is an automatically generated e-mail. To reply, visit:
> https://reviews.apache.org/r/64496/
> -----------------------------------------------------------
>
> (Updated Dec. 11, 2017, 5:31 a.m.)
>
>
> Review request for mesos and Michael Park.
>
>
> Repository: mesos
>
>
> Description
> -------
>
> In order to check whether a key or value was present in a 'hashset' or
> 'hashmap' we were checking whether the count for that entry was
> greater than zero. In order to count elements a complete traversal of
> the container is required, while a contains check already has an
> answer when the first element has been found.
>
> This patch uses find in contains check for both hashset and hashmap to
> avoid the full traversal.
>
>
> Diffs
> -----
>
> 3rdparty/stout/include/stout/hashmap.hpp 91085b8d8ad5d35c39c8cc95e3d4765d82d9a8db
> 3rdparty/stout/include/stout/hashset.hpp 6af209c53185207b53396e7687e3bd7357e57bf1
>
>
> Diff: https://reviews.apache.org/r/64496/diff/1/
>
>
> Testing
> -------
>
> `make check`
>
>
> Thanks,
>
> Benjamin Bannier
>
>