tjungblu commented 1 year ago

This is a breaking change in interface of Porcupine.

This set of commits does:

move state to a generic interface, that must implement Clone, String and Equals
make use of the above methods over the model defined function pointers
use clone before calling step to avoid issues like in #11
use dedicated input/output types for the step function

Note that I'm still looking into refactoring the internal entry's and node'value structure to a union type, this proves to be a little more difficult than anticipated - not sure this is currently even possible with two other generic types in Go.

anishathalye commented 1 year ago

This is interesting, thanks for taking time to make the changes and submit a PR.

Btw, I don't think we can do much better for the entry and node types. Go's type system doesn't support tagged unions, so we're basically manually implementing tagged unions (e.g., the kind field of the entry is the type tag) there without compile-time checking from the type system.

I see several pros and cons of switching over to using generics.

Pros:

Avoiding any all over the place is nice
Does help people from missing that Step() needs to be purely functional
Less casting required in user code
Performance: runtime benefit of avoiding wrapping in interface values in many places

Cons:

Breaking change to API
Requires Go 1.18 for generics
I don't think the types are really necessary here to provide a usable and safe API
Looks a little messy to have a lot of the functions parameterized by [S, I, O]
Performance: this clones the state everywhere, including for read-only operations, and the user can't opt out of the cloning. Step() is on a hot code path.

I was curious about the performance impacts of the change.

Machine stats:

goos: linux
goarch: amd64
pkg: github.com/anishathalye/porcupine
cpu: Intel(R) Core(TM) i7-5930K CPU @ 3.50GHz

$ go version
go version go1.19.3 linux/amd64

Out of curiosity, I added some new tests and benchmarks based on the key/value store data, and using a model with/without partitioning (ee9b49a57b6e3bc7185369ac814506812db43322, 89abd11ef0922e7b7916741b3a19c6016802b762).

EDIT: will share benchmark results below.

codecov-commenter commented 1 year ago

Codecov Report

Base: 88.91% // Head: 88.91% // No change to project coverage :thumbsup:

Coverage data is based on head (89abd11) compared to base (dbc9a3e). Patch has no changes to coverable lines.

:exclamation: Current head 89abd11 differs from pull request most recent head 4ba1f58. Consider uploading reports for the commit 4ba1f58 to get more accurate results

Additional details and impacted files

```diff @@ Coverage Diff @@ ## master #12 +/- ## ======================================= Coverage 88.91% 88.91% ======================================= Files 5 5 Lines 397 397 ======================================= Hits 353 353 Misses 35 35 Partials 9 9 ``` Help us with your feedback. Take ten seconds to tell us [how you rate us](https://about.codecov.io/nps?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Anish+Athalye). Have a feature suggestion? [Share it here.](https://app.codecov.io/gh/feedback/?utm_medium=referral&utm_source=github&utm_content=comment&utm_campaign=pr+comments&utm_term=Anish+Athalye)

:umbrella: View full report at Codecov.
:loudspeaker: Do you have feedback about the report comment? Let us know in this issue.

tjungblu commented 1 year ago

Performance: this clones the state everywhere, including for read-only operations, and the user can't opt out of the cloning. Step() is on a hot code path. I was curious about the performance impacts of the change.

Yep, that's I think the biggest hit to performance. Did you get a good benchmark result already? I'll run it later when rebasing.

tjungblu commented 1 year ago

with generics + cloning I get this result during benchmark:

[tjungblu ~/git/porcupine]$ go test -bench=.
goos: linux
goarch: amd64
pkg: github.com/anishathalye/porcupine
cpu: Intel(R) Core(TM) i7-10850H CPU @ 2.70GHz
BenchmarkEtcdJepsen000-12                       7611        154228 ns/op
BenchmarkEtcdJepsen001-12                       6471        179430 ns/op
BenchmarkEtcdJepsen002-12                          8     138026510 ns/op
BenchmarkEtcdJepsen003-12                      12496         95324 ns/op
BenchmarkEtcdJepsen004-12                      22680         52215 ns/op
BenchmarkEtcdJepsen005-12                       9228        126306 ns/op
BenchmarkEtcdJepsen006-12                      10000        107107 ns/op
BenchmarkEtcdJepsen007-12                         10     104118826 ns/op
BenchmarkEtcdJepsen008-12                      21064         55416 ns/op
BenchmarkEtcdJepsen009-12                      15046         79194 ns/op
BenchmarkEtcdJepsen010-12                      21103         55694 ns/op
BenchmarkEtcdJepsen011-12                       9590        117515 ns/op
BenchmarkEtcdJepsen012-12                      21891         54962 ns/op
BenchmarkEtcdJepsen013-12                      25000         47924 ns/op
BenchmarkEtcdJepsen014-12                      25164         47868 ns/op
BenchmarkEtcdJepsen015-12                      13712         87286 ns/op
BenchmarkEtcdJepsen016-12                      26582         45275 ns/op
BenchmarkEtcdJepsen017-12                      21217         54850 ns/op
BenchmarkEtcdJepsen018-12                       3639        322313 ns/op
BenchmarkEtcdJepsen019-12                       6415        182234 ns/op
BenchmarkEtcdJepsen020-12                      14518         82989 ns/op
BenchmarkEtcdJepsen021-12                      22771         52402 ns/op
BenchmarkEtcdJepsen022-12                      23563         50714 ns/op
BenchmarkEtcdJepsen023-12                      13212         89566 ns/op
BenchmarkEtcdJepsen024-12                      14892         80045 ns/op
BenchmarkEtcdJepsen025-12                      16310         73551 ns/op
BenchmarkEtcdJepsen026-12                      18100         66189 ns/op
BenchmarkEtcdJepsen027-12                      18091         66473 ns/op
BenchmarkEtcdJepsen028-12                      15512         77294 ns/op
BenchmarkEtcdJepsen029-12                      10000        106780 ns/op
BenchmarkEtcdJepsen030-12                      22758         52540 ns/op
BenchmarkEtcdJepsen031-12                      21336         55081 ns/op
BenchmarkEtcdJepsen032-12                      20001         59654 ns/op
BenchmarkEtcdJepsen033-12                      16902         70416 ns/op
BenchmarkEtcdJepsen034-12                      19320         61030 ns/op
BenchmarkEtcdJepsen035-12                      25983         44849 ns/op
BenchmarkEtcdJepsen036-12                      22165         53874 ns/op
BenchmarkEtcdJepsen037-12                       9517        115315 ns/op
BenchmarkEtcdJepsen038-12                      17614         68006 ns/op
BenchmarkEtcdJepsen039-12                      17308         68641 ns/op
BenchmarkEtcdJepsen040-12                        100      11235089 ns/op
BenchmarkEtcdJepsen041-12                      25473         47495 ns/op
BenchmarkEtcdJepsen042-12                      16749         71554 ns/op
BenchmarkEtcdJepsen043-12                      24715         47437 ns/op
BenchmarkEtcdJepsen044-12                       6534        176419 ns/op
BenchmarkEtcdJepsen045-12                      21561         54368 ns/op
BenchmarkEtcdJepsen046-12                      25580         47000 ns/op
BenchmarkEtcdJepsen047-12                      13279         88036 ns/op
BenchmarkEtcdJepsen048-12                      14026         83879 ns/op
BenchmarkEtcdJepsen049-12                      18512         61101 ns/op
BenchmarkEtcdJepsen050-12                      27260         42176 ns/op
BenchmarkEtcdJepsen051-12                      10000        108956 ns/op
BenchmarkEtcdJepsen052-12                      18516         64884 ns/op
BenchmarkEtcdJepsen053-12                        656       1835090 ns/op
BenchmarkEtcdJepsen054-12                      20872         57475 ns/op
BenchmarkEtcdJepsen055-12                      25448         47953 ns/op
BenchmarkEtcdJepsen056-12                       7468        158692 ns/op
BenchmarkEtcdJepsen057-12                         25      47338622 ns/op
BenchmarkEtcdJepsen058-12                      20349         57993 ns/op
BenchmarkEtcdJepsen059-12                      19863         58988 ns/op
BenchmarkEtcdJepsen060-12                      13550         86544 ns/op
BenchmarkEtcdJepsen061-12                       5623        205958 ns/op
BenchmarkEtcdJepsen062-12                      27967         41413 ns/op
BenchmarkEtcdJepsen063-12                      13471         87956 ns/op
BenchmarkEtcdJepsen064-12                      24298         48822 ns/op
BenchmarkEtcdJepsen065-12                      25599         45512 ns/op
BenchmarkEtcdJepsen066-12                      16582         70682 ns/op
BenchmarkEtcdJepsen067-12                      16506         71487 ns/op
BenchmarkEtcdJepsen068-12                      20253         58336 ns/op
BenchmarkEtcdJepsen069-12                      27112         44054 ns/op
BenchmarkEtcdJepsen070-12                      24738         46500 ns/op
BenchmarkEtcdJepsen071-12                       9884        119218 ns/op
BenchmarkEtcdJepsen072-12                      22594         50805 ns/op
BenchmarkEtcdJepsen073-12                       3573        327610 ns/op
BenchmarkEtcdJepsen074-12                      25024         45408 ns/op
BenchmarkEtcdJepsen075-12                         84      18373545 ns/op
BenchmarkEtcdJepsen076-12                       9526        110632 ns/op
BenchmarkEtcdJepsen077-12                      23404         49780 ns/op
BenchmarkEtcdJepsen078-12                      21534         55234 ns/op
BenchmarkEtcdJepsen079-12                      12343         96121 ns/op
BenchmarkEtcdJepsen080-12                        120       8516945 ns/op
BenchmarkEtcdJepsen081-12                      23493         49993 ns/op
BenchmarkEtcdJepsen082-12                      15022         79342 ns/op
BenchmarkEtcdJepsen083-12                      22051         51185 ns/op
BenchmarkEtcdJepsen084-12                      14858         77912 ns/op
BenchmarkEtcdJepsen085-12                        536       2311770 ns/op
BenchmarkEtcdJepsen086-12                      20421         53140 ns/op
BenchmarkEtcdJepsen087-12                       9985        116445 ns/op
BenchmarkEtcdJepsen088-12                      20083         59546 ns/op
BenchmarkEtcdJepsen089-12                       6096        184166 ns/op
BenchmarkEtcdJepsen090-12                      24470         46214 ns/op
BenchmarkEtcdJepsen091-12                      25959         45591 ns/op
BenchmarkEtcdJepsen092-12                      17664         64189 ns/op
BenchmarkEtcdJepsen093-12                      18384         63832 ns/op
BenchmarkEtcdJepsen094-12                      24430         49212 ns/op
BenchmarkEtcdJepsen096-12                      14526         80741 ns/op
BenchmarkEtcdJepsen097-12                        505       3390716 ns/op
BenchmarkEtcdJepsen098-12                       1258        910393 ns/op
BenchmarkEtcdJepsen099-12                         24      45894619 ns/op
BenchmarkEtcdJepsen100-12                      16342         72108 ns/op
BenchmarkEtcdJepsen101-12                      21724         54353 ns/op
BenchmarkEtcdJepsen102-12                      18318         64637 ns/op
BenchmarkKv1ClientOk-12                        15024         80223 ns/op
BenchmarkKv1ClientBad-12                       28113         41833 ns/op
BenchmarkKv10ClientsOk-12                       2353        488401 ns/op
BenchmarkKv10ClientsBad-12                      3513        306512 ns/op
BenchmarkKv50ClientsOk-12                          1    1962944648 ns/op
BenchmarkKv50ClientsBad-12                       132       9128606 ns/op
BenchmarkKvNoPartition1ClientOk-12             15723         72423 ns/op
BenchmarkKvNoPartition1ClientBad-12            32005         35866 ns/op
BenchmarkKvNoPartition10ClientsOk-12               1    79796681374 ns/op
BenchmarkKvNoPartition10ClientsBad-12              1    58994525165 ns/op
PASS
ok      github.com/anishathalye/porcupine   465.842s

running without generics+clone against HEAD:

[tjungblu ~/git/porcupine]$ git checkout master 
Switched to branch 'master'
Your branch is up to date with 'origin/master'.
[tjungblu ~/git/porcupine]$ go test -bench=.
goos: linux
goarch: amd64
pkg: github.com/anishathalye/porcupine
cpu: Intel(R) Core(TM) i7-10850H CPU @ 2.70GHz
BenchmarkEtcdJepsen000-12                       6806        174720 ns/op
BenchmarkEtcdJepsen001-12                       5600        200467 ns/op
BenchmarkEtcdJepsen002-12                          7     159233892 ns/op
BenchmarkEtcdJepsen003-12                      11523        102624 ns/op
BenchmarkEtcdJepsen004-12                      22036         53777 ns/op
BenchmarkEtcdJepsen005-12                       8048        137161 ns/op
BenchmarkEtcdJepsen006-12                       9565        119189 ns/op
BenchmarkEtcdJepsen007-12                          9     126387594 ns/op
BenchmarkEtcdJepsen008-12                      20235         58051 ns/op
BenchmarkEtcdJepsen009-12                      13992         85593 ns/op
BenchmarkEtcdJepsen010-12                      20340         59601 ns/op
BenchmarkEtcdJepsen011-12                       8718        128595 ns/op
BenchmarkEtcdJepsen012-12                      20226         58211 ns/op
BenchmarkEtcdJepsen013-12                      23277         49586 ns/op
BenchmarkEtcdJepsen014-12                      24174         49759 ns/op
BenchmarkEtcdJepsen015-12                      12494         96040 ns/op
BenchmarkEtcdJepsen016-12                      24603         48148 ns/op
BenchmarkEtcdJepsen017-12                      20335         57908 ns/op
BenchmarkEtcdJepsen018-12                       3069        372889 ns/op
BenchmarkEtcdJepsen019-12                       5556        206739 ns/op
BenchmarkEtcdJepsen020-12                      13591         88263 ns/op
BenchmarkEtcdJepsen021-12                      21672         54756 ns/op
BenchmarkEtcdJepsen022-12                      22356         52863 ns/op
BenchmarkEtcdJepsen023-12                      12242         97194 ns/op
BenchmarkEtcdJepsen024-12                      14071         85636 ns/op
BenchmarkEtcdJepsen025-12                      15223         77863 ns/op
BenchmarkEtcdJepsen026-12                      17055         70798 ns/op
BenchmarkEtcdJepsen027-12                      16816         70421 ns/op
BenchmarkEtcdJepsen028-12                      14240         81510 ns/op
BenchmarkEtcdJepsen029-12                      10000        119620 ns/op
BenchmarkEtcdJepsen030-12                      21470         53987 ns/op
BenchmarkEtcdJepsen031-12                      19810         57778 ns/op
BenchmarkEtcdJepsen032-12                      19274         63554 ns/op
BenchmarkEtcdJepsen033-12                      15351         75059 ns/op
BenchmarkEtcdJepsen034-12                      18454         64449 ns/op
BenchmarkEtcdJepsen035-12                      25704         46329 ns/op
BenchmarkEtcdJepsen036-12                      20842         56437 ns/op
BenchmarkEtcdJepsen037-12                       8422        126022 ns/op
BenchmarkEtcdJepsen038-12                      16405         70970 ns/op
BenchmarkEtcdJepsen039-12                      16014         73496 ns/op
BenchmarkEtcdJepsen040-12                        100      16844876 ns/op
BenchmarkEtcdJepsen041-12                      24350         49907 ns/op
BenchmarkEtcdJepsen042-12                      15394         76643 ns/op
BenchmarkEtcdJepsen043-12                      24499         48435 ns/op
BenchmarkEtcdJepsen044-12                       5841        195299 ns/op
BenchmarkEtcdJepsen045-12                      20090         57753 ns/op
BenchmarkEtcdJepsen046-12                      23960         48724 ns/op
BenchmarkEtcdJepsen047-12                      12384         94894 ns/op
BenchmarkEtcdJepsen048-12                      13066         90959 ns/op
BenchmarkEtcdJepsen049-12                      18261         62960 ns/op
BenchmarkEtcdJepsen050-12                      27040         44512 ns/op
BenchmarkEtcdJepsen051-12                       9528        121177 ns/op
BenchmarkEtcdJepsen052-12                      17684         67249 ns/op
BenchmarkEtcdJepsen053-12                        460       3926419 ns/op
BenchmarkEtcdJepsen054-12                      19845         59952 ns/op
BenchmarkEtcdJepsen055-12                      23581         47844 ns/op
BenchmarkEtcdJepsen056-12                       6376        177133 ns/op
BenchmarkEtcdJepsen057-12                         21      54128171 ns/op
BenchmarkEtcdJepsen058-12                      19548         58339 ns/op
BenchmarkEtcdJepsen059-12                      18544         63552 ns/op
BenchmarkEtcdJepsen060-12                      12715         93762 ns/op
BenchmarkEtcdJepsen061-12                       4947        232477 ns/op
BenchmarkEtcdJepsen062-12                      27030         42662 ns/op
BenchmarkEtcdJepsen063-12                      12447         94945 ns/op
BenchmarkEtcdJepsen064-12                      23318         49001 ns/op
BenchmarkEtcdJepsen065-12                      25611         47431 ns/op
BenchmarkEtcdJepsen066-12                      15720         74140 ns/op
BenchmarkEtcdJepsen067-12                      16033         73386 ns/op
BenchmarkEtcdJepsen068-12                      19342         60291 ns/op
BenchmarkEtcdJepsen069-12                      25551         44603 ns/op
BenchmarkEtcdJepsen070-12                      24691         48171 ns/op
BenchmarkEtcdJepsen071-12                       9055        127755 ns/op
BenchmarkEtcdJepsen072-12                      22124         51510 ns/op
BenchmarkEtcdJepsen073-12                       3112        394564 ns/op
BenchmarkEtcdJepsen074-12                      24673         47502 ns/op
BenchmarkEtcdJepsen075-12                         72      23112169 ns/op
BenchmarkEtcdJepsen076-12                       9828        118231 ns/op
BenchmarkEtcdJepsen077-12                      22405         50657 ns/op
BenchmarkEtcdJepsen078-12                      20158         59589 ns/op
BenchmarkEtcdJepsen079-12                       9596        105392 ns/op
BenchmarkEtcdJepsen080-12                        127       9475676 ns/op
BenchmarkEtcdJepsen081-12                      22240         51778 ns/op
BenchmarkEtcdJepsen082-12                      14163         84455 ns/op
BenchmarkEtcdJepsen083-12                      21595         52745 ns/op
BenchmarkEtcdJepsen084-12                      14113         82065 ns/op
BenchmarkEtcdJepsen085-12                        421       2686796 ns/op
BenchmarkEtcdJepsen086-12                      21433         54841 ns/op
BenchmarkEtcdJepsen087-12                       8659        125963 ns/op
BenchmarkEtcdJepsen088-12                      18688         61663 ns/op
BenchmarkEtcdJepsen089-12                       5787        203212 ns/op
BenchmarkEtcdJepsen090-12                      24625         46056 ns/op
BenchmarkEtcdJepsen091-12                      25699         46685 ns/op
BenchmarkEtcdJepsen092-12                      17310         66841 ns/op
BenchmarkEtcdJepsen093-12                      17740         66898 ns/op
BenchmarkEtcdJepsen094-12                      22806         51073 ns/op
BenchmarkEtcdJepsen096-12                      13752         85785 ns/op
BenchmarkEtcdJepsen097-12                        547       2655552 ns/op
BenchmarkEtcdJepsen098-12                       1506        884517 ns/op
BenchmarkEtcdJepsen099-12                         22      50767022 ns/op
BenchmarkEtcdJepsen100-12                      15799         75863 ns/op
BenchmarkEtcdJepsen101-12                      20796         55467 ns/op
BenchmarkEtcdJepsen102-12                      17764         66800 ns/op
BenchmarkKv1ClientOk-12                        14942         80575 ns/op
BenchmarkKv1ClientBad-12                       28414         38036 ns/op
BenchmarkKv10ClientsOk-12                       2504        489597 ns/op
BenchmarkKv10ClientsBad-12                      3240        310970 ns/op
BenchmarkKv50ClientsOk-12                          1    2895008532 ns/op
BenchmarkKv50ClientsBad-12                       100      11290136 ns/op
BenchmarkKvNoPartition1ClientOk-12             18163         63732 ns/op
BenchmarkKvNoPartition1ClientBad-12            36255         33009 ns/op
BenchmarkKvNoPartition10ClientsOk-12               1    77089491571 ns/op
BenchmarkKvNoPartition10ClientsBad-12              1    56238356959 ns/op
PASS
ok      github.com/anishathalye/porcupine   458.314s

also running 1.19.3:

[tjungblu ~/git/porcupine]$ go version
go version go1.19.3 linux/amd64

On the no partition KV tests it's slightly slower:

The partitioned ones are faster for the most part:

On Jepsen it's consistently faster:

sorry, I had to split the charts up as the many benchmarks became unwieldy.

tjungblu commented 1 year ago

running the generics without the cloning on the kv benchmarks

Test	generics ns/op	master ns/op	generics w/o clone ns/op
BenchmarkKvNoPartition1ClientBad-12	35866	33009	29800
BenchmarkKv1ClientBad-12	41833	38036	41479
BenchmarkKvNoPartition1ClientOk-12	72423	63732	58706
BenchmarkKv1ClientOk-12	80223	80575	79227
BenchmarkKv10ClientsBad-12	306512	310970	302989
BenchmarkKv10ClientsOk-12	488401	489597	483574
BenchmarkKv50ClientsBad-12	9128606	11290136	8914428
BenchmarkKv50ClientsOk-12	1962944648	2895008532	1968358789
BenchmarkKvNoPartition10ClientsBad-12	58994525165	56238356959	56662378632
BenchmarkKvNoPartition10ClientsOk-12	79796681374	77089491571	77982079434

as a chart on log scale:

anishathalye commented 1 year ago

Running 20x each, here are the benchstat results:

name                          old time/op  new time/op  delta
EtcdJepsen000-12               441µs ± 4%   396µs ± 4%  -10.29%  (p=0.000 n=18+19)
EtcdJepsen001-12               500µs ± 6%   447µs ± 6%  -10.71%  (p=0.000 n=20+19)
EtcdJepsen002-12               225ms ± 3%   202ms ± 3%  -10.30%  (p=0.000 n=20+19)
EtcdJepsen003-12               270µs ± 4%   248µs ± 4%   -8.15%  (p=0.000 n=20+20)
EtcdJepsen004-12               150µs ± 5%   147µs ± 3%   -2.20%  (p=0.001 n=20+18)
EtcdJepsen005-12               357µs ± 6%   338µs ± 6%   -5.36%  (p=0.000 n=20+20)
EtcdJepsen006-12               303µs ± 6%   283µs ± 4%   -6.60%  (p=0.000 n=20+20)
EtcdJepsen007-12               180ms ± 3%   166ms ± 4%   -7.58%  (p=0.000 n=20+20)
EtcdJepsen008-12               161µs ± 3%   154µs ± 3%   -4.67%  (p=0.000 n=20+20)
EtcdJepsen009-12               227µs ± 5%   219µs ± 5%   -3.57%  (p=0.000 n=20+20)
EtcdJepsen010-12               162µs ± 4%   158µs ± 4%   -2.53%  (p=0.000 n=20+20)
EtcdJepsen011-12               340µs ± 5%   311µs ± 5%   -8.66%  (p=0.000 n=20+20)
EtcdJepsen012-12               162µs ± 5%   154µs ± 4%   -4.94%  (p=0.000 n=20+19)
EtcdJepsen013-12               139µs ± 3%   133µs ± 4%   -4.63%  (p=0.000 n=18+20)
EtcdJepsen014-12               139µs ± 4%   135µs ± 4%   -2.98%  (p=0.000 n=20+20)
EtcdJepsen015-12               253µs ± 3%   234µs ± 4%   -7.22%  (p=0.000 n=19+19)
EtcdJepsen016-12               133µs ± 3%   131µs ± 4%   -1.73%  (p=0.002 n=19+20)
EtcdJepsen017-12               159µs ± 4%   153µs ± 4%   -3.70%  (p=0.000 n=20+20)
EtcdJepsen018-12               871µs ± 4%   780µs ± 9%  -10.49%  (p=0.000 n=20+20)
EtcdJepsen019-12               498µs ± 6%   458µs ± 4%   -8.05%  (p=0.000 n=20+18)
EtcdJepsen020-12               235µs ± 6%   224µs ± 5%   -4.50%  (p=0.000 n=20+20)
EtcdJepsen021-12               155µs ± 6%   151µs ± 4%   -2.18%  (p=0.010 n=20+20)
EtcdJepsen022-12               146µs ± 5%   142µs ± 4%   -2.97%  (p=0.000 n=18+20)
EtcdJepsen023-12               255µs ± 4%   237µs ± 4%   -6.91%  (p=0.000 n=18+20)
EtcdJepsen024-12               226µs ± 4%   217µs ± 3%   -3.70%  (p=0.000 n=19+19)
EtcdJepsen025-12               217µs ± 2%   201µs ± 4%   -7.43%  (p=0.000 n=19+20)
EtcdJepsen026-12               191µs ± 6%   179µs ± 4%   -6.37%  (p=0.000 n=20+20)
EtcdJepsen027-12               194µs ± 4%   185µs ± 3%   -4.30%  (p=0.000 n=20+20)
EtcdJepsen028-12               220µs ± 4%   211µs ± 4%   -4.08%  (p=0.000 n=20+20)
EtcdJepsen029-12               312µs ± 5%   290µs ± 5%   -7.00%  (p=0.000 n=20+20)
EtcdJepsen030-12               153µs ± 4%   148µs ± 4%   -3.30%  (p=0.000 n=20+20)
EtcdJepsen031-12               164µs ± 3%   153µs ± 4%   -6.39%  (p=0.000 n=19+20)
EtcdJepsen032-12               174µs ± 2%   164µs ± 4%   -5.87%  (p=0.000 n=20+20)
EtcdJepsen033-12               207µs ± 2%   195µs ± 3%   -5.75%  (p=0.000 n=18+20)
EtcdJepsen034-12               175µs ± 5%   167µs ± 3%   -4.61%  (p=0.000 n=19+20)
EtcdJepsen035-12               131µs ± 4%   130µs ± 3%     ~     (p=0.072 n=20+20)
EtcdJepsen036-12               158µs ± 3%   151µs ± 3%   -4.21%  (p=0.000 n=19+20)
EtcdJepsen037-12               330µs ± 5%   303µs ± 4%   -8.26%  (p=0.000 n=20+20)
EtcdJepsen038-12               199µs ± 3%   190µs ± 4%   -4.27%  (p=0.000 n=19+20)
EtcdJepsen039-12               196µs ± 3%   188µs ± 4%   -4.14%  (p=0.000 n=20+19)
EtcdJepsen040-12              23.6ms ± 7%  19.8ms ± 4%  -16.13%  (p=0.000 n=20+20)
EtcdJepsen041-12               139µs ± 4%   134µs ± 4%   -3.15%  (p=0.000 n=19+20)
EtcdJepsen042-12               207µs ± 4%   193µs ± 4%   -6.60%  (p=0.000 n=20+20)
EtcdJepsen043-12               136µs ± 4%   133µs ± 3%   -2.37%  (p=0.000 n=20+18)
EtcdJepsen044-12               472µs ± 6%   436µs ± 7%   -7.63%  (p=0.000 n=19+20)
EtcdJepsen045-12               160µs ± 4%   153µs ± 5%   -4.52%  (p=0.000 n=20+20)
EtcdJepsen046-12               137µs ± 3%   133µs ± 4%   -2.48%  (p=0.000 n=19+20)
EtcdJepsen047-12               247µs ± 4%   233µs ± 4%   -5.79%  (p=0.000 n=20+19)
EtcdJepsen048-12               246µs ± 4%   226µs ± 4%   -7.95%  (p=0.000 n=20+19)
EtcdJepsen049-12               181µs ± 5%   172µs ± 2%   -4.74%  (p=0.000 n=20+17)
EtcdJepsen050-12               126µs ± 6%   124µs ± 3%   -1.23%  (p=0.030 n=20+19)
EtcdJepsen051-12               316µs ± 5%   292µs ± 4%   -7.43%  (p=0.000 n=20+20)
EtcdJepsen052-12               186µs ± 4%   172µs ± 3%   -7.31%  (p=0.000 n=20+19)
EtcdJepsen053-12              4.20ms ± 4%  3.46ms ± 6%  -17.69%  (p=0.000 n=20+19)
EtcdJepsen054-12               170µs ± 3%   161µs ± 4%   -4.83%  (p=0.000 n=19+20)
EtcdJepsen055-12               138µs ± 3%   132µs ± 3%   -3.93%  (p=0.000 n=20+20)
EtcdJepsen056-12               441µs ± 7%   403µs ± 4%   -8.68%  (p=0.000 n=20+19)
EtcdJepsen057-12              96.1ms ± 4%  87.1ms ± 1%   -9.35%  (p=0.000 n=18+16)
EtcdJepsen058-12               166µs ± 5%   159µs ± 5%   -4.28%  (p=0.000 n=20+20)
EtcdJepsen059-12               171µs ± 4%   164µs ± 4%   -3.76%  (p=0.000 n=20+20)
EtcdJepsen060-12               251µs ± 4%   232µs ± 4%   -7.66%  (p=0.000 n=20+20)
EtcdJepsen061-12               555µs ± 4%   500µs ± 5%  -10.00%  (p=0.000 n=20+20)
EtcdJepsen062-12               123µs ± 3%   119µs ± 2%   -3.26%  (p=0.000 n=20+19)
EtcdJepsen063-12               252µs ± 4%   236µs ± 5%   -6.48%  (p=0.000 n=20+20)
EtcdJepsen064-12               142µs ± 3%   137µs ± 4%   -3.49%  (p=0.000 n=19+19)
EtcdJepsen065-12               135µs ± 4%   131µs ± 3%   -2.82%  (p=0.000 n=20+18)
EtcdJepsen066-12               200µs ± 4%   188µs ± 4%   -6.12%  (p=0.000 n=20+19)
EtcdJepsen067-12               206µs ± 3%   193µs ± 4%   -6.25%  (p=0.000 n=20+20)
EtcdJepsen068-12               171µs ± 4%   160µs ± 2%   -6.45%  (p=0.000 n=20+18)
EtcdJepsen069-12               131µs ± 3%   126µs ± 3%   -3.49%  (p=0.000 n=20+20)
EtcdJepsen070-12               137µs ± 3%   133µs ± 5%   -2.87%  (p=0.000 n=20+20)
EtcdJepsen071-12               324µs ± 4%   296µs ± 7%   -8.66%  (p=0.000 n=20+20)
EtcdJepsen072-12               150µs ± 3%   142µs ± 3%   -5.18%  (p=0.000 n=19+20)
EtcdJepsen073-12               876µs ± 4%   772µs ± 5%  -11.92%  (p=0.000 n=20+20)
EtcdJepsen074-12               134µs ± 4%   130µs ± 3%   -2.55%  (p=0.000 n=20+20)
EtcdJepsen075-12              41.3ms ± 3%  35.7ms ± 3%  -13.69%  (p=0.000 n=20+20)
EtcdJepsen076-12               318µs ± 4%   290µs ± 4%   -9.04%  (p=0.000 n=20+20)
EtcdJepsen077-12               145µs ± 3%   138µs ± 4%   -4.76%  (p=0.000 n=19+20)
EtcdJepsen078-12               164µs ± 4%   156µs ± 4%   -5.17%  (p=0.000 n=20+20)
EtcdJepsen079-12               272µs ± 5%   250µs ± 4%   -8.38%  (p=0.000 n=20+20)
EtcdJepsen080-12              15.5ms ± 4%  14.2ms ± 5%   -8.72%  (p=0.000 n=20+20)
EtcdJepsen081-12               148µs ± 3%   141µs ± 3%   -4.70%  (p=0.000 n=20+18)
EtcdJepsen082-12               229µs ± 4%   215µs ± 4%   -6.00%  (p=0.000 n=20+20)
EtcdJepsen083-12               152µs ± 2%   144µs ± 4%   -5.64%  (p=0.000 n=19+20)
EtcdJepsen084-12               223µs ± 5%   211µs ± 4%   -5.33%  (p=0.000 n=20+20)
EtcdJepsen085-12              4.91ms ± 4%  4.33ms ± 5%  -11.95%  (p=0.000 n=20+19)
EtcdJepsen086-12               159µs ± 4%   150µs ± 4%   -5.23%  (p=0.000 n=20+20)
EtcdJepsen087-12               330µs ± 4%   305µs ± 3%   -7.46%  (p=0.000 n=20+20)
EtcdJepsen088-12               171µs ± 4%   161µs ± 4%   -5.55%  (p=0.000 n=20+20)
EtcdJepsen089-12               511µs ± 5%   460µs ± 3%   -9.98%  (p=0.000 n=20+19)
EtcdJepsen090-12               135µs ± 3%   132µs ± 3%   -2.91%  (p=0.000 n=20+20)
EtcdJepsen091-12               132µs ± 4%   129µs ± 5%   -2.55%  (p=0.000 n=20+20)
EtcdJepsen092-12               191µs ± 4%   181µs ± 4%   -4.92%  (p=0.000 n=19+20)
EtcdJepsen093-12               184µs ± 4%   173µs ± 4%   -6.03%  (p=0.000 n=20+20)
EtcdJepsen094-12               143µs ± 3%   138µs ± 4%   -3.38%  (p=0.000 n=19+18)
EtcdJepsen096-12               233µs ± 3%   218µs ± 2%   -6.55%  (p=0.000 n=20+19)
EtcdJepsen097-12              4.75ms ± 6%  4.39ms ± 5%   -7.46%  (p=0.000 n=20+20)
EtcdJepsen098-12              1.73ms ± 4%  1.56ms ± 4%   -9.40%  (p=0.000 n=20+20)
EtcdJepsen099-12              89.1ms ± 4%  83.1ms ± 4%   -6.76%  (p=0.000 n=20+20)
EtcdJepsen100-12               206µs ± 5%   196µs ± 4%   -5.17%  (p=0.000 n=20+19)
EtcdJepsen101-12               157µs ± 4%   149µs ± 3%   -5.12%  (p=0.000 n=20+20)
EtcdJepsen102-12               194µs ± 3%   181µs ± 4%   -6.99%  (p=0.000 n=20+20)
Kv1ClientOk-12                 220µs ± 1%   220µs ± 3%     ~     (p=0.904 n=20+20)
Kv1ClientBad-12                107µs ± 2%   108µs ± 2%     ~     (p=0.060 n=20+20)
Kv10ClientsOk-12              1.25ms ± 2%  1.21ms ± 1%   -2.69%  (p=0.000 n=20+20)
Kv10ClientsBad-12              809µs ± 2%   812µs ± 1%     ~     (p=0.496 n=20+18)
Kv50ClientsOk-12               2.68s ± 2%   1.94s ± 3%  -27.55%  (p=0.000 n=20+19)
Kv50ClientsBad-12             13.3ms ± 2%  10.7ms ± 2%  -19.21%  (p=0.000 n=19+20)
KvNoPartition1ClientOk-12      171µs ± 3%   202µs ± 4%  +18.00%  (p=0.000 n=20+20)
KvNoPartition1ClientBad-12    89.1µs ± 4%  99.7µs ± 2%  +11.89%  (p=0.000 n=20+19)
KvNoPartition10ClientsOk-12    89.9s ± 1%   90.5s ± 1%   +0.66%  (p=0.000 n=20+19)
KvNoPartition10ClientsBad-12   63.2s ± 1%   64.1s ± 0%   +1.34%  (p=0.000 n=20+20)

anishathalye commented 1 year ago

At a high level, it's not an easy decision just based on benchmarks; what are your thoughts on the other pros/cons?

tjungblu commented 1 year ago

Whatever you feel like, really. I'm not mad if you reject this PR :)

I can also look into adding a generic version to the side of the existing one, google/BTree took a similar approach https://github.com/google/btree/pull/45

That would at least solve the backward compatibility issue.

Looks a little messy to have a lot of the functions parameterized by [S, I, O]

Indeed, that's not great. Some of this could be solved by moving the Check* functions into the Model itself and extracting an interface from it. Again, also a breaking change.

anishathalye commented 1 year ago

Let's keep things as-is for now; might revisit this in the future. Thank you for taking the time to submit the PR and discuss!

tjungblu commented 1 year ago

No worries, I'll maintain the generic changes for the time being in: https://github.com/tjungblu/porcupine/

just in case somebody else wants to use it.

anishathalye / porcupine

Add support for generics #12

Codecov Report