Optimize Set#&, Set#clone and Set.new #4047
Conversation
|
Am i reading this correct for Sparse & small |
In the the existing code, if you did With the PR, it will always let the small one "lead". The cost is figuring out which is smaller (self.size < other.size)...and while intersecting 1 to 1_000_000 is extreme, the gain should be fairly linear relative to the size difference. |
|
@karlseguin thanks for the detailed explanation 🙏 |
src/set.cr
Outdated
| @@ -37,6 +37,11 @@ struct Set(T) | |||
| @hash = Hash(T, Nil).new(initial_capacity: initial_capacity) | |||
| end | |||
|
|
|||
| # Optimized version of `new` used when `other` is also an `Indexable` | |||
There was a problem hiding this comment.
Small correction: other in this case is a parameter, so use asterisks to wrap instead of backticks *other*.
Mode details on the documentation style here: https://crystal-lang.org/docs/conventions/documenting_code.html
|
Excellent work @karlseguin, let's wait for dev team to review! 😸 |
Set#& will now iterate over the smaller of the two sets (similar to what Set#intersects? does). The new set created by Set#clone and Set#| now gets a proper initial capacity. Added overload to Set.new for Indexable(T) to use Indexable#size to set an initial capacity. improve union performance by sizing the resulting set
|
Thank you again! 💚 |
UPDATE:
I also init the size on a Union now (as the size has to be at least the Max size of the two sets, this has similar gains as changes to clone and new)
Changes to clone and new involve setting the initial capacity. Always in the case of
clone, and an overload forIndexable(T)in the case of new for access to an efficientsize. (I also expect this to generate less garbage, so the real world gain from should be even better)For
&it's the same optimization as whatintersects?does: iterating over the smaller of the two:small is 1 item, and both sparse and dense are in the 10K range.