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.

Sign up for GitHub

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

Jump to bottom

[POC] Remove Arc wrapping of keys and values in Vector and RedBlackTree #22

Closed
wants to merge 1 commit into from
Closed

[POC] Remove Arc wrapping of keys and values in Vector and RedBlackTree #22

wants to merge 1 commit into from

Conversation

Marwes
Copy link
Contributor

@Marwes Marwes commented Apr 2, 2018

Vectors seem promising but the RedBlackTree regresses in get and iterate which is rather odd... Need to investigate further.

 name                  old ns/iter  new ns/iter  diff ns/iter   diff %  speedup 
 vector_drop_last      120,354,099  95,403,062    -24,951,037  -20.73%   x 1.26 
 vector_drop_last_mut  7,469,591    5,451,750      -2,017,841  -27.01%   x 1.37 
 vector_get            2,969,756    2,909,477         -60,279   -2.03%   x 1.02 
 vector_iterate        1,411,878    1,269,607        -142,271  -10.08%   x 1.11 
 vector_push_back      131,497,470  103,677,766   -27,819,704  -21.16%   x 1.27 
 vector_push_back_mut  14,291,589   9,912,382      -4,379,207  -30.64%   x 1.44

(10k elements)

 name                        old_tree ns/iter  new_tree ns/iter  diff ns/iter   diff %  speedup 
 red_black_tree_map_get      624,572           667,942                 43,370    6.94%   x 0.94 
 red_black_tree_map_insert   17,937,010        15,219,633          -2,717,377  -15.15%   x 1.18 
 red_black_tree_map_iterate  172,588           197,880                 25,292   14.65%   x 0.87 
 red_black_tree_map_remove   22,687,565        18,574,023          -4,113,542  -18.13%   x 1.22

@orium
Copy link
Owner

orium commented Apr 8, 2018

I would rather have this configurable, in the same way we can have the smart pointer between node links configurable. So, basically, the user can configure the value wrapper to be Rc/Arc/InPlace and the link wrapper to be Rc/Arc. (The default would be Rc for both.)

This also allows for the simplification you mention on #7 (comment), since there would be two new type parameters.

If you are willing I would be happy to review and merge something like this.

@Marwes
Copy link
Contributor Author

Marwes commented Apr 9, 2018

That seems fair, given that there is actually a regression due to Entry not being wrapped in Arc anymore (though I am still confused as to why that is the case, copying 2 * usize shouldn't be that much more expensive than copying 1 incrementing a reference count...).

Not sure when I can get around to that approach though, got a bunch of other PRs I want to complete.

@orium
Copy link
Owner

orium commented Jul 8, 2018

I'm now working on #36. I will do a release after I finish it.

@orium orium mentioned this pull request Jul 8, 2018
Open
9 tasks
@orium orium force-pushed the master branch 2 times, most recently from fcdc771 to a5896df Compare March 6, 2019 10:49
@orium orium force-pushed the master branch 2 times, most recently from eb7a94d to 2d27d9b Compare September 11, 2019 10:13
@orium
Copy link
Owner

orium commented Sep 11, 2019

Implemented pointer type parameterization in rpds 0.7.

@orium orium closed this Sep 11, 2019
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.
2 participants
@Marwes @orium