samth commented 7 months ago

Eliminates contracts in favor of inline checks.
Specializes multiple-value code to improve single-value performance (see racket/racket#4942).
Use simpler non-recursive growth computation (taken from Rust's Vector implementation).
Avoid duplicate work in core operations.
Add #:capacity arguments.
Use unsafe operations.
Use vector-extend from racket/racket#4943.

sorawee commented 7 months ago

18 is linked to this PR, as if it fixes the issue. But if I understand correctly, the issue is not fixed, right? `make-gvector` still checks that the capacity must satisfy `exact-positive-integer?`.

samth commented 7 months ago

18 is linked to this PR, as if it fixes the issue. But if I understand correctly, the issue is not fixed, right? make-gvector still checks that the capacity must satisfy exact-positive-integer?.

Ah, I thought I had fixed that but now I did for real.

samth commented 7 months ago

Performance compared to mut-treelist before:

1000000 of length 10
+ for/mut-treelist  cpu time: 156 real time: 156 gc time: 6
+ mut-treelist-add! cpu time: 206 real time: 206 gc time: 2
+ for/gvector       cpu time: 475 real time: 475 gc time: 1
+ gvector-add!      cpu time: 939 real time: 939 gc time: 3
+ gvector-add! cap  cpu time: 963 real time: 963 gc time: 3
! gvector-set!/fx   cpu time: 459 real time: 459 gc time: 1
! gvector-set!/lit  cpu time: 454 real time: 454 gc time: 1
! gvector-set!/ptr  cpu time: 469 real time: 469 gc time: 1
! mut-tree-set!/fx  cpu time: 201 real time: 201 gc time: 0
! mut-tree-set!/lit cpu time: 198 real time: 198 gc time: 0
! mut-tree-set!/ptr cpu time: 218 real time: 218 gc time: 0
^ in-mut-treelist   cpu time: 82 real time: 82 gc time: 0
^ in-gvector        cpu time: 78 real time: 78 gc time: 0
^ mut-tree-ref      cpu time: 213 real time: 213 gc time: 0
^ gvector-ref       cpu time: 377 real time: 377 gc time: 1
100000 of length 100
+ for/mut-treelist  cpu time: 260 real time: 260 gc time: 3
+ mut-treelist-add! cpu time: 340 real time: 340 gc time: 4
+ for/gvector       cpu time: 501 real time: 501 gc time: 1
+ gvector-add!      cpu time: 771 real time: 771 gc time: 3
+ gvector-add! cap  cpu time: 711 real time: 711 gc time: 2
! gvector-set!/fx   cpu time: 440 real time: 440 gc time: 1
! gvector-set!/lit  cpu time: 435 real time: 435 gc time: 1
! gvector-set!/ptr  cpu time: 451 real time: 451 gc time: 1
! mut-tree-set!/fx  cpu time: 200 real time: 200 gc time: 0
! mut-tree-set!/lit cpu time: 194 real time: 194 gc time: 0
! mut-tree-set!/ptr cpu time: 211 real time: 211 gc time: 0
^ in-mut-treelist   cpu time: 64 real time: 64 gc time: 0
^ in-gvector        cpu time: 58 real time: 58 gc time: 0
^ mut-tree-ref      cpu time: 211 real time: 211 gc time: 0
^ gvector-ref       cpu time: 361 real time: 361 gc time: 1
100 of length 100000
+ for/mut-treelist  cpu time: 826 real time: 826 gc time: 46
+ mut-treelist-add! cpu time: 899 real time: 899 gc time: 56
+ for/gvector       cpu time: 512 real time: 512 gc time: 25
+ gvector-add!      cpu time: 754 real time: 754 gc time: 36
+ gvector-add! cap  cpu time: 687 real time: 687 gc time: 16
! gvector-set!/fx   cpu time: 444 real time: 444 gc time: 1
! gvector-set!/lit  cpu time: 438 real time: 438 gc time: 1
! gvector-set!/ptr  cpu time: 468 real time: 468 gc time: 13
! mut-tree-set!/fx  cpu time: 227 real time: 227 gc time: 0
! mut-tree-set!/lit cpu time: 227 real time: 227 gc time: 0
! mut-tree-set!/ptr cpu time: 240 real time: 240 gc time: 0
^ in-mut-treelist   cpu time: 71 real time: 71 gc time: 0
^ in-gvector        cpu time: 60 real time: 60 gc time: 0
^ mut-tree-ref      cpu time: 242 real time: 242 gc time: 0
^ gvector-ref       cpu time: 369 real time: 369 gc time: 1
10 of length 1000000
+ for/mut-treelist  cpu time: 1042 real time: 1042 gc time: 114
+ mut-treelist-add! cpu time: 1131 real time: 1131 gc time: 142
+ for/gvector       cpu time: 732 real time: 732 gc time: 173
+ gvector-add!      cpu time: 993 real time: 993 gc time: 200
+ gvector-add! cap  cpu time: 801 real time: 801 gc time: 93
! gvector-set!/fx   cpu time: 519 real time: 519 gc time: 25
! gvector-set!/lit  cpu time: 516 real time: 516 gc time: 25
! gvector-set!/ptr  cpu time: 560 real time: 560 gc time: 54
! mut-tree-set!/fx  cpu time: 328 real time: 328 gc time: 13
! mut-tree-set!/lit cpu time: 327 real time: 327 gc time: 13
! mut-tree-set!/ptr cpu time: 339 real time: 339 gc time: 13
^ in-mut-treelist   cpu time: 172 real time: 172 gc time: 13
^ in-gvector        cpu time: 126 real time: 126 gc time: 14
^ mut-tree-ref      cpu time: 342 real time: 342 gc time: 13
^ gvector-ref       cpu time: 446 real time: 446 gc time: 25

After:

1000000 of length 10
+ for/mut-treelist  cpu time: 165 real time: 165 gc time: 8
+ mut-treelist-add! cpu time: 206 real time: 206 gc time: 2
+ for/gvector       cpu time: 95 real time: 95 gc time: 0
+ gvector-add!      cpu time: 92 real time: 92 gc time: 0
+ gvector-add! cap  cpu time: 93 real time: 93 gc time: 0
! gvector-set!/fx   cpu time: 247 real time: 247 gc time: 0
! gvector-set!/lit  cpu time: 240 real time: 240 gc time: 0
! gvector-set!/ptr  cpu time: 260 real time: 260 gc time: 0
! mut-tree-set!/fx  cpu time: 188 real time: 188 gc time: 0
! mut-tree-set!/lit cpu time: 186 real time: 186 gc time: 0
! mut-tree-set!/ptr cpu time: 206 real time: 206 gc time: 0
^ in-mut-treelist   cpu time: 80 real time: 80 gc time: 0
^ in-gvector        cpu time: 30 real time: 30 gc time: 0
^ mut-tree-ref      cpu time: 201 real time: 201 gc time: 0
^ gvector-ref       cpu time: 195 real time: 196 gc time: 0
100000 of length 100
+ for/mut-treelist  cpu time: 303 real time: 303 gc time: 4
+ mut-treelist-add! cpu time: 365 real time: 365 gc time: 4
+ for/gvector       cpu time: 97 real time: 97 gc time: 0
+ gvector-add!      cpu time: 96 real time: 96 gc time: 0
+ gvector-add! cap  cpu time: 77 real time: 77 gc time: 0
! gvector-set!/fx   cpu time: 227 real time: 227 gc time: 0
! gvector-set!/lit  cpu time: 222 real time: 222 gc time: 0
! gvector-set!/ptr  cpu time: 241 real time: 241 gc time: 0
! mut-tree-set!/fx  cpu time: 183 real time: 183 gc time: 0
! mut-tree-set!/lit cpu time: 181 real time: 181 gc time: 0
! mut-tree-set!/ptr cpu time: 198 real time: 198 gc time: 0
^ in-mut-treelist   cpu time: 62 real time: 62 gc time: 0
^ in-gvector        cpu time: 14 real time: 14 gc time: 0
^ mut-tree-ref      cpu time: 195 real time: 195 gc time: 0
^ gvector-ref       cpu time: 183 real time: 183 gc time: 0
100 of length 100000
+ for/mut-treelist  cpu time: 786 real time: 786 gc time: 46
+ mut-treelist-add! cpu time: 865 real time: 865 gc time: 56
+ for/gvector       cpu time: 105 real time: 105 gc time: 10
+ gvector-add!      cpu time: 107 real time: 107 gc time: 12
+ gvector-add! cap  cpu time: 83 real time: 83 gc time: 2
! gvector-set!/fx   cpu time: 226 real time: 226 gc time: 0
! gvector-set!/lit  cpu time: 221 real time: 221 gc time: 0
! gvector-set!/ptr  cpu time: 240 real time: 240 gc time: 0
! mut-tree-set!/fx  cpu time: 209 real time: 209 gc time: 0
! mut-tree-set!/lit cpu time: 209 real time: 209 gc time: 0
! mut-tree-set!/ptr cpu time: 222 real time: 222 gc time: 0
^ in-mut-treelist   cpu time: 68 real time: 68 gc time: 0
^ in-gvector        cpu time: 14 real time: 14 gc time: 0
^ mut-tree-ref      cpu time: 223 real time: 223 gc time: 0
^ gvector-ref       cpu time: 176 real time: 176 gc time: 0
10 of length 1000000
+ for/mut-treelist  cpu time: 983 real time: 983 gc time: 115
+ mut-treelist-add! cpu time: 1078 real time: 1078 gc time: 142
+ for/gvector       cpu time: 274 real time: 274 gc time: 129
+ gvector-add!      cpu time: 266 real time: 266 gc time: 127
+ gvector-add! cap  cpu time: 107 real time: 107 gc time: 28
! gvector-set!/fx   cpu time: 252 real time: 252 gc time: 10
! gvector-set!/lit  cpu time: 247 real time: 247 gc time: 10
! gvector-set!/ptr  cpu time: 269 real time: 269 gc time: 10
! mut-tree-set!/fx  cpu time: 306 real time: 306 gc time: 12
! mut-tree-set!/lit cpu time: 302 real time: 302 gc time: 12
! mut-tree-set!/ptr cpu time: 313 real time: 313 gc time: 12
^ in-mut-treelist   cpu time: 161 real time: 161 gc time: 12
^ in-gvector        cpu time: 40 real time: 40 gc time: 10
^ mut-tree-ref      cpu time: 315 real time: 315 gc time: 12
^ gvector-ref       cpu time: 204 real time: 204 gc time: 10

mflatt commented 7 months ago

This is ready to merge, right?

samth commented 7 months ago

From my perspective yes although I was hoping for a review from @rmculpepper

racket / data

Revise for better performance. #34

18 is linked to this PR, as if it fixes the issue. But if I understand correctly, the issue is not fixed, right? `make-gvector` still checks that the capacity must satisfy `exact-positive-integer?`.

18 is linked to this PR, as if it fixes the issue. But if I understand correctly, the issue is not fixed, right? `make-gvector` still checks that the capacity must satisfy `exact-positive-integer?`.

racket / data

Revise for better performance. #34

18 is linked to this PR, as if it fixes the issue. But if I understand correctly, the issue is not fixed, right? make-gvector still checks that the capacity must satisfy exact-positive-integer?.

18 is linked to this PR, as if it fixes the issue. But if I understand correctly, the issue is not fixed, right? make-gvector still checks that the capacity must satisfy exact-positive-integer?.

18 is linked to this PR, as if it fixes the issue. But if I understand correctly, the issue is not fixed, right? `make-gvector` still checks that the capacity must satisfy `exact-positive-integer?`.

18 is linked to this PR, as if it fixes the issue. But if I understand correctly, the issue is not fixed, right? `make-gvector` still checks that the capacity must satisfy `exact-positive-integer?`.