search

composewell / streamly

High performance, concurrent functional programming abstractions
https://streamly.composewell.com
Other
864 stars 66 forks source link

Variable encoding of Word64 #2575

Open adithyaov opened 1 year ago

adithyaov commented 1 year ago

Benchmarks for variable length unsigned integer (Word64):

default(0) = Word64 (8 bytes)
default(1) = 239 (1 bytes)
default(2) = 2286 (2 bytes)
default(3) = 67822 (3 bytes)
default(4) = 16777214 (4 bytes)
default(5) = 4294967294 (5 bytes)
default(6) = 1099511627774 (6 bytes)
default(7) = 281474976710654 (7 bytes)
default(8) = 72057594037927934 (8 bytes)
default(9) = 72057594037927936 (9 bytes)
Data.Serialize(cpuTime)
Benchmark default(0)(μs) default(1) - default(0)(%) default(2) - default(0)(%) default(3) - default(0)(%) default(4) - default(0)(%) default(5) - default(0)(%) default(6) - default(0)(%) default(7) - default(0)(%) default(8) - default(0)(%) default(9) - default(0)(%)
--------- -------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- --------------------------
peek               27.92                   +1450.49                   +1634.66                   +1932.92                   +1955.52                   +1724.21                   +1883.29                   +1824.89                   +2293.49                   +1830.37
roundtrip         113.82                    +796.47                    +892.05                   +1014.92                   +1057.30                   +1102.11                   +1160.94                   +1199.22                   +1381.92                   +1262.00
poke               27.93                    +736.30                    +940.92                   +1040.31                   +1038.34                   +1027.24                   +1343.51                   +1429.92                   +1635.43                   +1439.14
encode            126.19                    +404.90                    +434.02                    +475.34                    +518.12                    +519.95                    +623.76                    +656.39                    +787.94                    +854.61

Data.Serialize(Allocated)
Benchmark default(0)(Bytes) default(1) - default(0)(%) default(2) - default(0)(%) default(3) - default(0)(%) default(4) - default(0)(%) default(5) - default(0)(%) default(6) - default(0)(%) default(7) - default(0)(%) default(8) - default(0)(%) default(9) - default(0)(%)
--------- ----------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- --------------------------
peek                   0.00                  +Infinity                  +Infinity                  +Infinity                  +Infinity                  +Infinity                  +Infinity                  +Infinity                  +Infinity                  +Infinity
poke                   0.00                  +Infinity                  +Infinity                  +Infinity                  +Infinity                  +Infinity                  +Infinity                  +Infinity                  +Infinity                  +Infinity
roundtrip        2399075.00                    +299.44                    +299.36                    +299.55                    +299.45                    +297.81                    +297.81                    +299.44                    +297.81                    +330.80
encode           2399075.00                     +65.79                     +65.80                     +66.36                     +65.78                     +66.34                     +65.81                     +65.27                     +65.80                     +98.81

Data.Serialize(maxrss)
Benchmark default(0)(MiB) default(1) - default(0)(%) default(2) - default(0)(%) default(3) - default(0)(%) default(4) - default(0)(%) default(5) - default(0)(%) default(6) - default(0)(%) default(7) - default(0)(%) default(8) - default(0)(%) default(9) - default(0)(%)
--------- --------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- --------------------------
poke                18.00                      +5.56                       0.00                       0.00                       0.00                       0.00                       0.00                     +11.11                     +11.11                       0.00
roundtrip           18.00                       0.00                       0.00                     +11.11                       0.00                    -900.00                       0.00                      -5.88                       0.00                       0.00
peek                18.00                       0.00                       0.00                       0.00                       0.00                       0.00                       0.00                       0.00                       0.00                     +11.11
encode              20.00                     -11.11                     -11.11                       0.00                     -11.11                     -11.11                     -11.11                      -5.26                     -11.11                     -11.11
adithyaov commented 1 year ago

Poke can be improved if I assume little endian format. But that way we are specific to little endian. To understand the above comment, you'll need to see the code.

adithyaov commented 1 year ago

With INLINE-ing:

Data.Serialize(cpuTime)
Benchmark     default(0)(μs) default(1) - default(0)(%) default(2) - default(0)(%) default(3) - default(0)(%) default(4) - default(0)(%) default(5) - default(0)(%) default(6) - default(0)(%) default(7) - default(0)(%) default(8) - default(0)(%)
------------- -------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- --------------------------
All.roundtrip         115.02                    +358.38                    +448.35                    +618.31                    +653.10                    +807.02                    +839.68                    +921.77                   +1043.94
All.encode            115.34                    +332.43                    +378.48                    +506.86                    +551.06                    +651.72                    +674.58                    +766.36                    +811.68
All.poke               27.98                     +25.03                    +199.10                    +499.77                    +405.37                    +601.91                    +598.51                    +897.78                    +899.88
All.peek               28.21                      -0.65                    +197.34                    +494.68                    +497.52                    +613.90                    +494.18                    +493.52                    +298.44

Data.Serialize(Allocated)
Benchmark     default(0)(Bytes) default(1) - default(0)(%) default(2) - default(0)(%) default(3) - default(0)(%) default(4) - default(0)(%) default(5) - default(0)(%) default(6) - default(0)(%) default(7) - default(0)(%) default(8) - default(0)(%)
------------- ----------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- --------------------------
All.poke                   0.00                        NaN                        NaN                        NaN                        NaN                        NaN                        NaN                        NaN                        NaN
All.encode           2399075.00                      -1.35                      -1.35                      -1.35                      -1.35                      -1.35                      -2.48                      -0.53                     +33.34
All.peek                   0.00                        NaN                        NaN                        NaN                        NaN                        NaN                        NaN                        NaN                        NaN
All.roundtrip        2399075.00                      -0.53                      -0.53                      -1.35                      -1.35                      -2.48                      -2.48                      -2.48                     +32.79

Data.Serialize(maxrss)
Benchmark     default(0)(MiB) default(1) - default(0)(%) default(2) - default(0)(%) default(3) - default(0)(%) default(4) - default(0)(%) default(5) - default(0)(%) default(6) - default(0)(%) default(7) - default(0)(%) default(8) - default(0)(%)
------------- --------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- -------------------------- --------------------------
All.poke                18.00                     +11.11                       0.00                       0.00                       0.00                       0.00                     +11.11                     +11.11                       0.00
All.roundtrip           18.00                       0.00                       0.00                       0.00                       0.00                       0.00                       0.00                       0.00                       0.00
All.peek                18.00                       0.00                       0.00                       0.00                       0.00                       0.00                       0.00                       0.00                      +5.56
All.encode              20.00                     -11.11                     -11.11                     -11.11                     -11.11                     -11.11                       0.00                     -11.11                     -11.11