Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

use Vec to handle out-of-order items #8

Merged
merged 1 commit into from Oct 21, 2022
Merged

Conversation

aawsome
Copy link
Contributor

@aawsome aawsome commented Oct 21, 2022

The # of out-of-order items is IMO bounded by the # of threads.
In any case it is relatively small and I don't see why a HashMap should perform any better than a simple Vec (especially given that the HashMap uses Vec-like buckets which are simple sequentially searched - I could imagine that we typically have a HashMap with just 1 bucket...)

@aawsome
Copy link
Contributor Author

aawsome commented Oct 21, 2022

Here are some benchmarks (master vs. vec-out-of-order):

fibonacci(10)/parallel_map-t1/100                                                                                                      
                 change:                                                                                                               
                        time:   [-3.9826% -1.0928% +1.7553%] (p = 0.47 > 0.05)                                                         
                        thrpt:  [-1.7250% +1.1048% +4.1478%]                                                                           
                        No change in performance detected.
fibonacci(10)/parallel_map-t2/100                                                                             
                 change:
                        time:   [-1.4672% -0.1405% +1.2323%] (p = 0.84 > 0.05)
                        thrpt:  [-1.2173% +0.1407% +1.4890%]
                        No change in performance detected.
fibonacci(10)/parallel_map-t4/100                                                                             
                 change:
                        time:   [-6.5400% -1.9073% +2.8612%] (p = 0.44 > 0.05)
                        thrpt:  [-2.7816% +1.9444% +6.9977%]
                        No change in performance detected.
fibonacci(10)/parallel_map-t1/1000                                                                             
                 change:
                        time:   [-4.9744% -1.0625% +2.9276%] (p = 0.59 > 0.05)
                        thrpt:  [-2.8443% +1.0739% +5.2348%]
                        No change in performance detected.
fibonacci(10)/parallel_map-t2/1000                                                                             
                 change:
                        time:   [-8.3858% -7.4055% -6.4442%] (p = 0.00 < 0.05)
                        thrpt:  [+6.8881% +7.9977% +9.1533%]
                        Performance has improved.
fibonacci(10)/parallel_map-t4/1000                                                                             
                 change:
                        time:   [-13.793% -9.9091% -6.0077%] (p = 0.00 < 0.05)
                        thrpt:  [+6.3917% +10.999% +15.999%]
                        Performance has improved.
fibonacci(10)/parallel_map-t1/10000                                                                              
                 change:
                        time:   [-11.191% -6.3192% -1.2853%] (p = 0.02 < 0.05)
                        thrpt:  [+1.3021% +6.7454% +12.602%]
                        Performance has improved.
fibonacci(10)/parallel_map-t2/10000                                                                              
                 change:
                        time:   [-13.405% -12.363% -11.324%] (p = 0.00 < 0.05)
                        thrpt:  [+12.771% +14.107% +15.480%]
                        Performance has improved.
fibonacci(10)/parallel_map-t4/10000                                                                              
                 change:
                        time:   [-18.851% -16.964% -15.191%] (p = 0.00 < 0.05)
                        thrpt:  [+17.912% +20.429% +23.230%]
                        Performance has improved.

@dpc dpc merged commit b901181 into dpc:master Oct 21, 2022
@dpc
Copy link
Owner

dpc commented Oct 21, 2022

@aawsome I think you're right, good thinking. Thanks!

@dpc
Copy link
Owner

dpc commented Oct 21, 2022

@aawsome If you don't mind, if you could update CHANGELOG and add a comment right next to that Vec about why it's a vec, that would be awesome. Otherwise I'll try to remember to do it later. :)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet

2 participants