Skip to content

Add shortcircuit in iteration if we yielded all elements#338

Merged
bors merged 1 commit intorust-lang:masterfrom
AngelicosPhosphoros:master
Jun 3, 2022
Merged

Add shortcircuit in iteration if we yielded all elements#338
bors merged 1 commit intorust-lang:masterfrom
AngelicosPhosphoros:master

Conversation

@AngelicosPhosphoros
Copy link
Contributor

@AngelicosPhosphoros AngelicosPhosphoros commented May 20, 2022

Current implementation works little slower than set.iter().take(set.len()).
See my comment here.

So why not avoid extra integer which added by Iterator::take if we can add limiting logic into our iterator itself?

I don't really know how this change affects reflect_toogle_full and implementation of FusedIterator. Maybe I should make inner iterator "jump" to the end of its memory block?

@Amanieu
Copy link
Member

Amanieu commented May 23, 2022

I do have some concerns:

  1. The comment just below your change becomes incorrect: items can no longer be eliminated by the compiler since it is now used to check for termination.
  2. Since the item count is now being checked, the check against end can be eliminated from RawIterRange, perhaps via a new next_unchecked method.

@AngelicosPhosphoros
Copy link
Contributor Author

AngelicosPhosphoros commented May 24, 2022

OK, I would fix improve my PR tomorrow.

@AngelicosPhosphoros
Copy link
Contributor Author

AngelicosPhosphoros commented May 31, 2022 •
edited
Loading

@Amanieu I have a question about this lines:
https://github.com/rust-lang/hashbrown/blob/3dbcdcce09028b39e1640f8a6e4fc8e69a372844/src/raw/mod.rs#L1945..L1952

What this comment means and what should be here in version without end pointer check?

@Amanieu
Copy link
Member

Amanieu commented May 31, 2022

You should leave this code and comment as it is. The only change needed is removing the check against self.end above.

@AngelicosPhosphoros
Copy link
Contributor Author

AngelicosPhosphoros commented May 31, 2022

Updated.

I decided to remove check using constant flag, compiler should remove checks during compilation.

@AngelicosPhosphoros
Add shortcircuit in iteration if we yielded all elements
ea120c7 
Current implementation works little slower than `set.iter().take(set.len())`.
See my comment [here](rust-lang/rust#97215 (comment)).

So why not avoid extra integer which added by `Iterator::take` if we can add limiting logic into our iterator itself?

Also, removed end pointer check if we can limit iteration by counting items yielded.
@Amanieu
Copy link
Member

Amanieu commented Jun 2, 2022

Nice work! Have you tried running the benchmarks to compare performance before/after?

@AngelicosPhosphoros
Copy link
Contributor Author

AngelicosPhosphoros commented Jun 3, 2022 •
edited
Loading

I forgot :D

Reminder: this is the bench for almost empty hash sets.

HashTableIteration/HashTableIterationFull/64
                        time:   [136.94 ns 138.14 ns 139.48 ns]
                        change: [-31.564% -29.632% -27.330%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 9 outliers among 100 measurements (9.00%)
  4 (4.00%) high mild
  5 (5.00%) high severe
Benchmarking HashTableIteration/HashTableIterationFull/256: Collecting 100 samples in estimated 5.0065 s (3.5M iteration                                                                                                                        HashTableIteration/HashTableIterationFull/256
                        time:   [275.24 ns 275.67 ns 276.16 ns]
                        change: [-26.684% -25.640% -24.632%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 4 outliers among 100 measurements (4.00%)
  1 (1.00%) high mild
  3 (3.00%) high severe
Benchmarking HashTableIteration/HashTableIterationFull/1024: Collecting 100 samples in estimated 5.0015 s (1.2M iteratio                                                                                                                        HashTableIteration/HashTableIterationFull/1024
                        time:   [516.69 ns 517.95 ns 519.52 ns]
                        change: [-13.304% -12.422% -11.469%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 6 outliers among 100 measurements (6.00%)
  2 (2.00%) high mild
  4 (4.00%) high severe
Benchmarking HashTableIteration/HashTableIterationFull/4096: Collecting 100 samples in estimated 5.0622 s (394k iteratio                                                                                                                        HashTableIteration/HashTableIterationFull/4096
                        time:   [641.24 ns 642.72 ns 644.54 ns]
                        change: [-32.432% -31.616% -30.706%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 14 outliers among 100 measurements (14.00%)
  2 (2.00%) high mild
  12 (12.00%) high severe
Benchmarking HashTableIteration/HashTableIterationFull/16384: Collecting 100 samples in estimated 5.0527 s (141k iterati                                                                                                                        HashTableIteration/HashTableIterationFull/16384
                        time:   [1.2190 us 1.2247 us 1.2317 us]
                        change: [-59.855% -59.188% -58.579%] (p = 0.00 < 0.05)
                        Performance has improved.
Benchmarking HashTableIteration/HashTableIterationLimited/64: Collecting 100 samples in estimated 5.0011 s (4.1M iterati                                                                                                                        HashTableIteration/HashTableIterationLimited/64
                        time:   [114.96 ns 115.14 ns 115.34 ns]
                        change: [-40.720% -39.669% -38.076%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 8 outliers among 100 measurements (8.00%)
  4 (4.00%) high mild
  4 (4.00%) high severe
Benchmarking HashTableIteration/HashTableIterationLimited/256: Collecting 100 samples in estimated 5.0077 s (2.8M iterat                                                                                                                        HashTableIteration/HashTableIterationLimited/256
                        time:   [261.74 ns 266.07 ns 270.04 ns]
                        change: [-28.749% -27.626% -26.307%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 20 outliers among 100 measurements (20.00%)
  14 (14.00%) high mild
  6 (6.00%) high severe
Benchmarking HashTableIteration/HashTableIterationLimited/1024: Collecting 100 samples in estimated 5.0066 s (1.1M itera                                                                                                                        HashTableIteration/HashTableIterationLimited/1024
                        time:   [508.83 ns 510.89 ns 513.35 ns]
                        change: [-13.444% -12.164% -10.693%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 11 outliers among 100 measurements (11.00%)
  5 (5.00%) high mild
  6 (6.00%) high severe
Benchmarking HashTableIteration/HashTableIterationLimited/4096: Collecting 100 samples in estimated 5.0214 s (667k itera                                                                                                                        HashTableIteration/HashTableIterationLimited/4096
                        time:   [640.38 ns 650.84 ns 663.10 ns]
                        change: [-32.123% -30.388% -28.722%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 11 outliers among 100 measurements (11.00%)
  5 (5.00%) high mild
  6 (6.00%) high severe
Benchmarking HashTableIteration/HashTableIterationLimited/16384: Collecting 100 samples in estimated 5.0954 s (217k iter                                                                                                                        HashTableIteration/HashTableIterationLimited/16384
                        time:   [1.1984 us 1.2041 us 1.2109 us]
                        change: [-60.842% -59.932% -58.933%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 14 outliers among 100 measurements (14.00%)
  12 (12.00%) high mild
  2 (2.00%) high severe

@Amanieu
Copy link
Member

Amanieu commented Jun 3, 2022

@bors r+

@bors
Copy link
Contributor

bors commented Jun 3, 2022

📌 Commit ea120c7 has been approved by Amanieu

@bors
Copy link
Contributor

bors commented Jun 3, 2022

⌛ Testing commit ea120c7 with merge d11a701...

@bors
Copy link
Contributor

bors commented Jun 3, 2022

☀️ Test successful - checks-actions
Approved by: Amanieu
Pushing d11a701 to master...

@bors bors merged commit d11a701 into rust-lang:master Jun 3, 2022
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

No reviews

Assignees

No one assigned

Labels

None yet

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

3 participants

@AngelicosPhosphoros @Amanieu @bors