linear-builder
linear-builder copied to clipboard
Bodigrim
Add support for unbounded integrals
Currently this package supports only finite integrals, but Integer and Natural are also common.
Add support for unbounded integrals:
- [x] Decimal
- [ ] Hexadecimal
Also add related tests and benchmarks.
Currently a draft for early feedback. Although the benchmark results are already quite good, the current implementation allocates too much. I have some idea for a better implementation.
Note that I wanted to try a newtype for Integer and write a FiniteBits instance, but it is too tricky and does not benefit from optimizations.
Hexadecimal formatting pending.
Fixed exactIntegerDecLen being slow.
Attempted a faster algorithm for unsafePrependUnboundedDec inspired by fast-digits, but it does not improve performance 😅
@Bodigrim new implementation. I am quite happy with the benchmark:
Benchmark results
GHC 9.2.8, Linux, 8 × AMD Ryzen 5 2500UAll
Decimal
Unbounded
Small
1
Data.Text.Lazy.Builder: OK
263 ns ± 5.4 ns, 807 B allocated, 0 B copied, 15 MB peak memory
Data.ByteString.Builder: OK
491 ns ± 18 ns, 4.9 KB allocated, 1 B copied, 18 MB peak memory, 1.87x
Text.Builder: OK
1.85 μs ± 93 ns, 6.8 KB allocated, 3 B copied, 18 MB peak memory, 7.03x
ByteString.StrictBuilder: OK
653 ns ± 32 ns, 2.5 KB allocated, 1 B copied, 18 MB peak memory, 2.48x
Data.Text.Builder.Linear: OK
160 ns ± 8.1 ns, 486 B allocated, 0 B copied, 18 MB peak memory, 0.61x
10
Data.Text.Lazy.Builder: OK
2.63 μs ± 83 ns, 5.9 KB allocated, 3 B copied, 18 MB peak memory
Data.ByteString.Builder: OK
2.15 μs ± 86 ns, 7.9 KB allocated, 1 B copied, 19 MB peak memory, 0.82x
Text.Builder: OK
18.9 μs ± 847 ns, 71 KB allocated, 103 B copied, 19 MB peak memory, 7.19x
ByteString.StrictBuilder: OK
8.15 μs ± 437 ns, 24 KB allocated, 50 B copied, 19 MB peak memory, 3.10x
Data.Text.Builder.Linear: OK
1.25 μs ± 61 ns, 3.2 KB allocated, 1 B copied, 19 MB peak memory, 0.47x
100
Data.Text.Lazy.Builder: OK
227 μs ± 3.3 μs, 795 KB allocated, 1.9 KB copied, 19 MB peak memory
Data.ByteString.Builder: OK
32.5 μs ± 1.6 μs, 60 KB allocated, 113 B copied, 19 MB peak memory, 0.14x
Text.Builder: OK
221 μs ± 13 μs, 752 KB allocated, 8.4 KB copied, 19 MB peak memory, 0.97x
ByteString.StrictBuilder: OK
95.5 μs ± 4.8 μs, 267 KB allocated, 4.6 KB copied, 19 MB peak memory, 0.42x
Data.Text.Builder.Linear: OK
24.4 μs ± 1.2 μs, 47 KB allocated, 25 B copied, 19 MB peak memory, 0.11x
1000
Data.Text.Lazy.Builder: OK
4.48 ms ± 88 μs, 8.4 MB allocated, 474 KB copied, 19 MB peak memory
Data.ByteString.Builder: OK
371 μs ± 11 μs, 704 KB allocated, 12 KB copied, 19 MB peak memory, 0.08x
Text.Builder: OK
4.00 ms ± 143 μs, 7.8 MB allocated, 885 KB copied, 19 MB peak memory, 0.89x
ByteString.StrictBuilder: OK
1.49 ms ± 42 μs, 2.8 MB allocated, 518 KB copied, 19 MB peak memory, 0.33x
Data.Text.Builder.Linear: OK
256 μs ± 8.0 μs, 431 KB allocated, 92 B copied, 19 MB peak memory, 0.06x
10000
Data.Text.Lazy.Builder: OK
76.1 ms ± 4.2 ms, 85 MB allocated, 11 MB copied, 21 MB peak memory
Data.ByteString.Builder: OK
6.01 ms ± 206 μs, 6.6 MB allocated, 1.2 MB copied, 21 MB peak memory, 0.08x
Text.Builder: OK
80.1 ms ± 4.0 ms, 82 MB allocated, 17 MB copied, 37 MB peak memory, 1.05x
ByteString.StrictBuilder: OK
93.7 ms ± 2.2 ms, 29 MB allocated, 29 MB copied, 48 MB peak memory, 1.23x
Data.Text.Builder.Linear: OK
2.84 ms ± 123 μs, 5.2 MB allocated, 877 B copied, 48 MB peak memory, 0.04x
100000
Data.Text.Lazy.Builder: OK
725 ms ± 41 ms, 861 MB allocated, 119 MB copied, 57 MB peak memory
Data.ByteString.Builder: OK
131 ms ± 2.0 ms, 67 MB allocated, 30 MB copied, 63 MB peak memory, 0.18x
Text.Builder: OK
779 ms ± 6.2 ms, 870 MB allocated, 179 MB copied, 249 MB peak memory, 1.07x
ByteString.StrictBuilder: OK
1.083 s ± 18 ms, 323 MB allocated, 329 MB copied, 514 MB peak memory, 1.49x
Data.Text.Builder.Linear: OK
46.2 ms ± 757 μs, 50 MB allocated, 11 KB copied, 514 MB peak memory, 0.06x
Big
1
Data.Text.Lazy.Builder: OK
23.1 μs ± 790 ns, 83 KB allocated, 51 B copied, 514 MB peak memory
Data.ByteString.Builder: OK
3.19 μs ± 68 ns, 8.4 KB allocated, 1 B copied, 514 MB peak memory, 0.14x
Text.Builder: OK
27.9 μs ± 955 ns, 90 KB allocated, 194 B copied, 514 MB peak memory, 1.21x
ByteString.StrictBuilder: OK
15.8 μs ± 908 ns, 44 KB allocated, 81 B copied, 514 MB peak memory, 0.68x
Data.Text.Builder.Linear: OK
1.86 μs ± 87 ns, 3.4 KB allocated, 2 B copied, 514 MB peak memory, 0.08x
10
Data.Text.Lazy.Builder: OK
241 μs ± 8.5 μs, 824 KB allocated, 1.2 KB copied, 514 MB peak memory
Data.ByteString.Builder: OK
27.6 μs ± 1.0 μs, 40 KB allocated, 37 B copied, 514 MB peak memory, 0.11x
Text.Builder: OK
287 μs ± 7.4 μs, 906 KB allocated, 5.5 KB copied, 514 MB peak memory, 1.19x
ByteString.StrictBuilder: OK
163 μs ± 6.7 μs, 438 KB allocated, 7.8 KB copied, 514 MB peak memory, 0.68x
Data.Text.Builder.Linear: OK
20.8 μs ± 765 ns, 34 KB allocated, 11 B copied, 514 MB peak memory, 0.09x
100
Data.Text.Lazy.Builder: OK
3.69 ms ± 162 μs, 8.1 MB allocated, 310 KB copied, 514 MB peak memory
Data.ByteString.Builder: OK
282 μs ± 9.9 μs, 467 KB allocated, 2.4 KB copied, 514 MB peak memory, 0.08x
Text.Builder: OK
4.91 ms ± 223 μs, 8.9 MB allocated, 935 KB copied, 514 MB peak memory, 1.33x
ByteString.StrictBuilder: OK
2.34 ms ± 112 μs, 4.3 MB allocated, 794 KB copied, 514 MB peak memory, 0.63x
Data.Text.Builder.Linear: OK
200 μs ± 7.9 μs, 353 KB allocated, 90 B copied, 514 MB peak memory, 0.05x
1000
Data.Text.Lazy.Builder: OK
59.3 ms ± 3.5 ms, 80 MB allocated, 8.5 MB copied, 514 MB peak memory
Data.ByteString.Builder: OK
3.15 ms ± 132 μs, 4.2 MB allocated, 241 KB copied, 514 MB peak memory, 0.05x
Text.Builder: OK
71.5 ms ± 3.0 ms, 89 MB allocated, 15 MB copied, 514 MB peak memory, 1.21x
ByteString.StrictBuilder: OK
109 ms ± 629 μs, 43 MB allocated, 30 MB copied, 514 MB peak memory, 1.84x
Data.Text.Builder.Linear: OK
2.00 ms ± 71 μs, 3.4 MB allocated, 596 B copied, 514 MB peak memory, 0.03x
10000
Data.Text.Lazy.Builder: OK
542 ms ± 29 ms, 806 MB allocated, 92 MB copied, 514 MB peak memory
Data.ByteString.Builder: OK
57.8 ms ± 2.4 ms, 43 MB allocated, 7.1 MB copied, 514 MB peak memory, 0.11x
Text.Builder: OK
728 ms ± 1.5 ms, 902 MB allocated, 152 MB copied, 514 MB peak memory, 1.34x
ByteString.StrictBuilder: OK
1.193 s ± 24 ms, 436 MB allocated, 323 MB copied, 514 MB peak memory, 2.20x
Data.Text.Builder.Linear: OK
43.1 ms ± 2.3 ms, 42 MB allocated, 8.6 KB copied, 514 MB peak memory, 0.08x
Huge
1
Data.Text.Lazy.Builder: OK
262 μs ± 15 μs, 873 KB allocated, 1.3 KB copied, 514 MB peak memory
Data.ByteString.Builder: OK
27.4 μs ± 1.2 μs, 38 KB allocated, 40 B copied, 514 MB peak memory, 0.10x
Text.Builder: OK
630 μs ± 20 μs, 1.6 MB allocated, 24 KB copied, 514 MB peak memory, 2.40x
ByteString.StrictBuilder: OK
502 μs ± 21 μs, 1.1 MB allocated, 17 KB copied, 514 MB peak memory, 1.92x
Data.Text.Builder.Linear: OK
29.8 μs ± 1.3 μs, 40 KB allocated, 11 B copied, 514 MB peak memory, 0.11x
10
Data.Text.Lazy.Builder: OK
3.79 ms ± 187 μs, 8.4 MB allocated, 316 KB copied, 514 MB peak memory
Data.ByteString.Builder: OK
289 μs ± 7.7 μs, 450 KB allocated, 2.0 KB copied, 514 MB peak memory, 0.08x
Text.Builder: OK
9.68 ms ± 570 μs, 16 MB allocated, 1.4 MB copied, 514 MB peak memory, 2.55x
ByteString.StrictBuilder: OK
9.82 ms ± 224 μs, 11 MB allocated, 2.0 MB copied, 514 MB peak memory, 2.59x
Data.Text.Builder.Linear: OK
304 μs ± 11 μs, 415 KB allocated, 150 B copied, 514 MB peak memory, 0.08x
100
Data.Text.Lazy.Builder: OK
61.3 ms ± 933 μs, 85 MB allocated, 9.0 MB copied, 514 MB peak memory
Data.ByteString.Builder: OK
3.12 ms ± 121 μs, 4.1 MB allocated, 182 KB copied, 514 MB peak memory, 0.05x
Text.Builder: OK
105 ms ± 4.3 ms, 161 MB allocated, 17 MB copied, 514 MB peak memory, 1.71x
ByteString.StrictBuilder: OK
133 ms ± 6.3 ms, 110 MB allocated, 32 MB copied, 514 MB peak memory, 2.18x
Data.Text.Builder.Linear: OK
3.01 ms ± 43 μs, 4.2 MB allocated, 1.5 KB copied, 514 MB peak memory, 0.05x
1000
Data.Text.Lazy.Builder: OK
560 ms ± 9.3 ms, 851 MB allocated, 95 MB copied, 514 MB peak memory
Data.ByteString.Builder: OK
55.2 ms ± 3.1 ms, 41 MB allocated, 5.3 MB copied, 514 MB peak memory, 0.10x
Text.Builder: OK
1.057 s ± 44 ms, 1.6 GB allocated, 166 MB copied, 514 MB peak memory, 1.89x
ByteString.StrictBuilder: OK
1.518 s ± 49 ms, 1.1 GB allocated, 323 MB copied, 514 MB peak memory, 2.71x
Data.Text.Builder.Linear: OK
39.9 ms ± 1.5 ms, 40 MB allocated, 14 KB copied, 514 MB peak memory, 0.07x
This is not optimal, because it does not scale as good as the ByteString builder, but it does beat it both in time and space for numbers < 1019265. For 10900, it is 2 times faster. So I guess this is quite acceptable.
Of course these numbers are not crazily big, but I wonder if there are real use cases with bigger numbers.
This is not optimal, because it does not scale as good as the
ByteStringbuilder,
(I have not looked at the implementation yet) What's the reason it does not scale as good as bytestring?
Fixed detailed benchmarks: finally they are not as good as I thought… I realized that the simple benchmark had differences with the detailed one for the config. I needed to inline the benchmark builder to get consistency between the two benchmarks. Benchmarking is so tricky! It seems this implementation still beats ByteString builder < 101450 on my machine.
What's the reason it does not scale as good as
bytestring?
@Bodigrim it’s because of the same reason than previous comment highlighted, although at a different scale.
The question is: does it matter? I am not satisfied with a suboptimal solution, but on the other hand, are there use cases to format really huge numbers and where the perf of the formatting matters? I mean, the current Text builder is even worst and is still widely used.
I will investigate other options, now that the benchmarks seems to display correct results.
I did try to implement the bytestring algorithm, but was not convinced by the perf.
(Aside: My current workaround for printing Integers and Naturals is shoving in a Show constraint and doing fromString (show n), which feels kinda bad. I moved to linear-text-builder for performance & ergonomics, so I'd love to see this get merged.)
The question is: does it matter? I am not satisfied with a suboptimal solution, but on the other hand, are there use cases to format really huge numbers and where the perf of the formatting matters?
It is not a blocker indeed.
So after reading the Core dump, it seems that in the specific benchmark for unbounded integers:
- Data.ByteString.Builder: in
B.integerDec i <> (acc <> B.integerDec i),B.integerDec iis shared. - Data.Text.Builder.Linear: in
i $$<| (acc |>$$ i)work is not shared, even with different implementation. UsingBuilderinstead ofBufferdoes not fix that.
Example of benchmark result using the patterns `-p unbounded -p Huge1`
All
Decimal: detailed unbounded
Append
Huge1
1
Data.ByteString.Builder: OK
19.1 μs ± 406 ns, 32 KB allocated, 14 B copied, 20 MB peak memory
Data.Text.Builder.Linear: OK
10.1 μs ± 457 ns, 11 KB allocated, 10 B copied, 20 MB peak memory, 0.53x
10
Data.ByteString.Builder: OK
191 μs ± 10 μs, 324 KB allocated, 187 B copied, 20 MB peak memory
Data.Text.Builder.Linear: OK
105 μs ± 1.9 μs, 115 KB allocated, 49 B copied, 20 MB peak memory, 0.55x
100
Data.ByteString.Builder: OK
1.85 ms ± 28 μs, 2.9 MB allocated, 3.7 KB copied, 20 MB peak memory
Data.Text.Builder.Linear: OK
1.09 ms ± 58 μs, 1.1 MB allocated, 331 B copied, 20 MB peak memory, 0.59x
Prepend
Huge1
1
Data.ByteString.Builder: OK
19.4 μs ± 657 ns, 32 KB allocated, 17 B copied, 20 MB peak memory
Data.Text.Builder.Linear: OK
10.1 μs ± 179 ns, 11 KB allocated, 10 B copied, 20 MB peak memory, 0.52x
10
Data.ByteString.Builder: OK
188 μs ± 4.1 μs, 325 KB allocated, 177 B copied, 20 MB peak memory
Data.Text.Builder.Linear: OK
104 μs ± 2.3 μs, 113 KB allocated, 63 B copied, 20 MB peak memory, 0.55x
100
Data.ByteString.Builder: OK
1.86 ms ± 22 μs, 2.9 MB allocated, 3.5 KB copied, 20 MB peak memory
Data.Text.Builder.Linear: OK
1.04 ms ± 58 μs, 1.1 MB allocated, 361 B copied, 20 MB peak memory, 0.56x
Both
Huge1
1
Data.ByteString.Builder: OK
21.5 μs ± 768 ns, 30 KB allocated, 19 B copied, 20 MB peak memory
Data.Text.Builder.Linear: OK
20.8 μs ± 491 ns, 25 KB allocated, 19 B copied, 20 MB peak memory, 0.97x
10
Data.ByteString.Builder: OK
221 μs ± 7.2 μs, 330 KB allocated, 1.2 KB copied, 20 MB peak memory
Data.Text.Builder.Linear: OK
220 μs ± 12 μs, 258 KB allocated, 70 B copied, 20 MB peak memory, 1.00x
100
Data.ByteString.Builder: OK
2.35 ms ± 68 μs, 3.2 MB allocated, 106 KB copied, 20 MB peak memory
Data.Text.Builder.Linear: OK
2.23 ms ± 47 μs, 2.7 MB allocated, 543 B copied, 23 MB peak memory, 0.95x
So while I can find implementations that beat ByteString builder for either prepending or appending, it seems that doing both cannot perform better that the ByteString builder after reaching big enough numbers.
Do you have some advice to improve the situation and enable sharing to work? Or is it just a corner case and we should use a fairer benchmark?
Using the following function makes the benchmark a bit fairer:
benchUnboundedLinearBuilder ∷ Integer → Int → T.Text
benchUnboundedLinearBuilder k m = runBuffer (\b → go b m)
where
go ∷ Buffer ⊸ Int → Buffer
go !acc 0 = acc
go !acc n = case newEmptyBuffer acc of
(# acc', e #) → case dupBuffer ((fromIntegral n * k) $$<| e) of
(# l, r #) → go (l >< (acc' >< r)) (n - 1)
Do you have some advice to improve the situation and enable sharing to work? Or is it just a corner case and we should use a fairer benchmark?
Yeah, that's a corner case. I'd change the benchmark to i $$<| (acc |>$$ (i + 1)) or similar.
New (fair) benchmark
All
Decimal: detailed unbounded
Both
Small
1
Data.ByteString.Builder: OK
487 ns ± 7.8 ns, 4.9 KB allocated, 3 B copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
148 ns ± 1.4 ns, 375 B allocated, 0 B copied, 28 MB peak memory, 0.30x
10
Data.ByteString.Builder: OK
2.17 μs ± 25 ns, 8.5 KB allocated, 6 B copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
1.07 μs ± 20 ns, 2.2 KB allocated, 3 B copied, 28 MB peak memory, 0.49x
100
Data.ByteString.Builder: OK
44.5 μs ± 441 ns, 84 KB allocated, 374 B copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
22.4 μs ± 123 ns, 37 KB allocated, 65 B copied, 28 MB peak memory, 0.50x
Big01
1
Data.ByteString.Builder: OK
1.49 μs ± 28 ns, 6.3 KB allocated, 8 B copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
369 ns ± 6.1 ns, 678 B allocated, 1 B copied, 28 MB peak memory, 0.25x
10
Data.ByteString.Builder: OK
12.1 μs ± 110 ns, 23 KB allocated, 42 B copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
4.01 μs ± 26 ns, 6.2 KB allocated, 16 B copied, 28 MB peak memory, 0.33x
100
Data.ByteString.Builder: OK
116 μs ± 892 ns, 227 KB allocated, 745 B copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
43.1 μs ± 594 ns, 61 KB allocated, 89 B copied, 28 MB peak memory, 0.37x
Big02
1
Data.ByteString.Builder: OK
2.82 μs ± 40 ns, 8.1 KB allocated, 8 B copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
787 ns ± 13 ns, 1.4 KB allocated, 3 B copied, 28 MB peak memory, 0.28x
10
Data.ByteString.Builder: OK
25.4 μs ± 233 ns, 41 KB allocated, 109 B copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
8.80 μs ± 89 ns, 14 KB allocated, 43 B copied, 28 MB peak memory, 0.35x
100
Data.ByteString.Builder: OK
256 μs ± 3.4 μs, 421 KB allocated, 1.8 KB copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
86.5 μs ± 1.5 μs, 143 KB allocated, 203 B copied, 28 MB peak memory, 0.34x
Big03
1
Data.ByteString.Builder: OK
5.10 μs ± 90 ns, 12 KB allocated, 21 B copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
1.61 μs ± 20 ns, 3.0 KB allocated, 9 B copied, 28 MB peak memory, 0.32x
10
Data.ByteString.Builder: OK
46.2 μs ± 383 ns, 74 KB allocated, 214 B copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
17.8 μs ± 300 ns, 31 KB allocated, 74 B copied, 28 MB peak memory, 0.38x
100
Data.ByteString.Builder: OK
474 μs ± 3.2 μs, 805 KB allocated, 4.7 KB copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
174 μs ± 2.2 μs, 316 KB allocated, 746 B copied, 28 MB peak memory, 0.37x
Big04
1
Data.ByteString.Builder: OK
7.63 μs ± 94 ns, 16 KB allocated, 52 B copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
2.67 μs ± 50 ns, 4.9 KB allocated, 25 B copied, 28 MB peak memory, 0.35x
10
Data.ByteString.Builder: OK
75.0 μs ± 674 ns, 155 KB allocated, 546 B copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
28.7 μs ± 211 ns, 51 KB allocated, 142 B copied, 28 MB peak memory, 0.38x
100
Data.ByteString.Builder: OK
734 μs ± 11 μs, 1.2 MB allocated, 8.5 KB copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
280 μs ± 3.4 μs, 524 KB allocated, 1.4 KB copied, 28 MB peak memory, 0.38x
Big05
1
Data.ByteString.Builder: OK
9.87 μs ± 189 ns, 19 KB allocated, 69 B copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
3.99 μs ± 15 ns, 7.3 KB allocated, 44 B copied, 28 MB peak memory, 0.40x
10
Data.ByteString.Builder: OK
94.4 μs ± 1.5 μs, 184 KB allocated, 718 B copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
41.3 μs ± 418 ns, 75 KB allocated, 240 B copied, 28 MB peak memory, 0.44x
100
Data.ByteString.Builder: OK
924 μs ± 13 μs, 1.5 MB allocated, 12 KB copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
404 μs ± 5.9 μs, 770 KB allocated, 2.1 KB copied, 28 MB peak memory, 0.44x
Big06
1
Data.ByteString.Builder: OK
11.6 μs ± 182 ns, 22 KB allocated, 91 B copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
5.48 μs ± 69 ns, 7.7 KB allocated, 48 B copied, 28 MB peak memory, 0.47x
10
Data.ByteString.Builder: OK
115 μs ± 726 ns, 220 KB allocated, 922 B copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
55.4 μs ± 880 ns, 81 KB allocated, 248 B copied, 28 MB peak memory, 0.48x
100
Data.ByteString.Builder: OK
1.12 ms ± 8.4 μs, 1.8 MB allocated, 15 KB copied, 28 MB peak memory
Data.Text.Builder.Linear: OK
537 μs ± 5.5 μs, 829 KB allocated, 2.3 KB copied, 29 MB peak memory, 0.48x
Big07
1
Data.ByteString.Builder: OK
15.1 μs ± 197 ns, 27 KB allocated, 127 B copied, 29 MB peak memory
Data.Text.Builder.Linear: OK
6.51 μs ± 113 ns, 9.2 KB allocated, 63 B copied, 29 MB peak memory, 0.43x
10
Data.ByteString.Builder: OK
149 μs ± 1.9 μs, 274 KB allocated, 1.2 KB copied, 29 MB peak memory
Data.Text.Builder.Linear: OK
66.9 μs ± 1.3 μs, 96 KB allocated, 310 B copied, 29 MB peak memory, 0.45x
100
Data.ByteString.Builder: OK
1.47 ms ± 22 μs, 2.4 MB allocated, 22 KB copied, 29 MB peak memory
Data.Text.Builder.Linear: OK
655 μs ± 3.6 μs, 991 KB allocated, 2.6 KB copied, 29 MB peak memory, 0.44x
Big08
1
Data.ByteString.Builder: OK
17.3 μs ± 272 ns, 30 KB allocated, 127 B copied, 29 MB peak memory
Data.Text.Builder.Linear: OK
8.11 μs ± 77 ns, 11 KB allocated, 43 B copied, 29 MB peak memory, 0.47x
10
Data.ByteString.Builder: OK
173 μs ± 968 ns, 305 KB allocated, 1.5 KB copied, 29 MB peak memory
Data.Text.Builder.Linear: OK
81.2 μs ± 1.3 μs, 114 KB allocated, 344 B copied, 29 MB peak memory, 0.47x
100
Data.ByteString.Builder: OK
1.71 ms ± 33 μs, 2.7 MB allocated, 26 KB copied, 29 MB peak memory
Data.Text.Builder.Linear: OK
800 μs ± 6.7 μs, 1.1 MB allocated, 3.2 KB copied, 30 MB peak memory, 0.47x
Big09
1
Data.ByteString.Builder: OK
19.4 μs ± 251 ns, 33 KB allocated, 156 B copied, 30 MB peak memory
Data.Text.Builder.Linear: OK
9.38 μs ± 126 ns, 13 KB allocated, 49 B copied, 30 MB peak memory, 0.48x
10
Data.ByteString.Builder: OK
194 μs ± 2.2 μs, 340 KB allocated, 1.7 KB copied, 30 MB peak memory
Data.Text.Builder.Linear: OK
95.1 μs ± 744 ns, 133 KB allocated, 435 B copied, 30 MB peak memory, 0.49x
100
Data.ByteString.Builder: OK
1.92 ms ± 30 μs, 3.0 MB allocated, 33 KB copied, 30 MB peak memory
Data.Text.Builder.Linear: OK
949 μs ± 17 μs, 1.3 MB allocated, 4.5 KB copied, 31 MB peak memory, 0.49x
Big10
1
Data.ByteString.Builder: OK
22.1 μs ± 396 ns, 37 KB allocated, 194 B copied, 31 MB peak memory
Data.Text.Builder.Linear: OK
11.1 μs ± 218 ns, 14 KB allocated, 65 B copied, 31 MB peak memory, 0.50x
10
Data.ByteString.Builder: OK
218 μs ± 1.7 μs, 379 KB allocated, 2.0 KB copied, 31 MB peak memory
Data.Text.Builder.Linear: OK
110 μs ± 1.1 μs, 149 KB allocated, 528 B copied, 31 MB peak memory, 0.51x
100
Data.ByteString.Builder: OK
2.16 ms ± 32 μs, 3.4 MB allocated, 37 KB copied, 31 MB peak memory
Data.Text.Builder.Linear: OK
1.09 ms ± 9.6 μs, 1.5 MB allocated, 4.9 KB copied, 31 MB peak memory, 0.51x
Big11
1
Data.ByteString.Builder: OK
24.2 μs ± 351 ns, 40 KB allocated, 231 B copied, 31 MB peak memory
Data.Text.Builder.Linear: OK
12.7 μs ± 137 ns, 16 KB allocated, 85 B copied, 31 MB peak memory, 0.52x
10
Data.ByteString.Builder: OK
243 μs ± 2.2 μs, 409 KB allocated, 2.4 KB copied, 31 MB peak memory
Data.Text.Builder.Linear: OK
127 μs ± 1.3 μs, 168 KB allocated, 638 B copied, 31 MB peak memory, 0.52x
100
Data.ByteString.Builder: OK
2.40 ms ± 43 μs, 3.7 MB allocated, 44 KB copied, 31 MB peak memory
Data.Text.Builder.Linear: OK
1.26 ms ± 25 μs, 1.7 MB allocated, 6.0 KB copied, 31 MB peak memory, 0.53x
Huge01
1
Data.ByteString.Builder: OK
39.5 μs ± 187 ns, 57 KB allocated, 347 B copied, 31 MB peak memory
Data.Text.Builder.Linear: OK
21.8 μs ± 221 ns, 26 KB allocated, 143 B copied, 31 MB peak memory, 0.55x
10
Data.ByteString.Builder: OK
399 μs ± 6.2 μs, 593 KB allocated, 3.8 KB copied, 31 MB peak memory
Data.Text.Builder.Linear: OK
220 μs ± 4.2 μs, 268 KB allocated, 1.0 KB copied, 31 MB peak memory, 0.55x
100
Data.ByteString.Builder: OK
4.32 ms ± 52 μs, 5.8 MB allocated, 107 KB copied, 31 MB peak memory
Data.Text.Builder.Linear: OK
2.22 ms ± 23 μs, 2.7 MB allocated, 11 KB copied, 31 MB peak memory, 0.51x
Huge02
1
Data.ByteString.Builder: OK
51.2 μs ± 500 ns, 72 KB allocated, 440 B copied, 31 MB peak memory
Data.Text.Builder.Linear: OK
28.7 μs ± 404 ns, 37 KB allocated, 156 B copied, 31 MB peak memory, 0.56x
10
Data.ByteString.Builder: OK
532 μs ± 6.4 μs, 796 KB allocated, 5.3 KB copied, 31 MB peak memory
Data.Text.Builder.Linear: OK
289 μs ± 4.4 μs, 389 KB allocated, 1.6 KB copied, 31 MB peak memory, 0.54x
100
Data.ByteString.Builder: OK
6.52 ms ± 65 μs, 7.5 MB allocated, 261 KB copied, 32 MB peak memory
Data.Text.Builder.Linear: OK
2.94 ms ± 47 μs, 3.9 MB allocated, 19 KB copied, 32 MB peak memory, 0.45x
Huge03
1
Data.ByteString.Builder: OK
124 μs ± 1.8 μs, 187 KB allocated, 1.1 KB copied, 32 MB peak memory
Data.Text.Builder.Linear: OK
78.5 μs ± 1.4 μs, 84 KB allocated, 441 B copied, 32 MB peak memory, 0.63x
10
Data.ByteString.Builder: OK
1.23 ms ± 12 μs, 1.6 MB allocated, 14 KB copied, 32 MB peak memory
Data.Text.Builder.Linear: OK
795 μs ± 9.6 μs, 879 KB allocated, 4.5 KB copied, 32 MB peak memory, 0.64x
100
Data.ByteString.Builder: OK
17.5 ms ± 217 μs, 15 MB allocated, 1.3 MB copied, 43 MB peak memory
Data.Text.Builder.Linear: OK
9.31 ms ± 64 μs, 8.8 MB allocated, 43 KB copied, 43 MB peak memory, 0.53x
Huge04
1
Data.ByteString.Builder: OK
223 μs ± 3.4 μs, 271 KB allocated, 1.7 KB copied, 43 MB peak memory
Data.Text.Builder.Linear: OK
154 μs ± 2.5 μs, 155 KB allocated, 917 B copied, 43 MB peak memory, 0.69x
10
Data.ByteString.Builder: OK
2.23 ms ± 17 μs, 2.4 MB allocated, 24 KB copied, 43 MB peak memory
Data.Text.Builder.Linear: OK
1.57 ms ± 22 μs, 1.6 MB allocated, 10 KB copied, 43 MB peak memory, 0.70x
100
Data.ByteString.Builder: OK
31.9 ms ± 367 μs, 24 MB allocated, 2.2 MB copied, 43 MB peak memory
Data.Text.Builder.Linear: OK
18.8 ms ± 161 μs, 16 MB allocated, 98 KB copied, 44 MB peak memory, 0.59x
Huge05
1
Data.ByteString.Builder: OK
299 μs ± 2.9 μs, 344 KB allocated, 2.3 KB copied, 44 MB peak memory
Data.Text.Builder.Linear: OK
250 μs ± 1.8 μs, 167 KB allocated, 870 B copied, 44 MB peak memory, 0.84x
10
Data.ByteString.Builder: OK
2.99 ms ± 25 μs, 3.1 MB allocated, 33 KB copied, 44 MB peak memory
Data.Text.Builder.Linear: OK
2.53 ms ± 37 μs, 1.7 MB allocated, 9.3 KB copied, 44 MB peak memory, 0.85x
100
Data.ByteString.Builder: OK
41.7 ms ± 515 μs, 31 MB allocated, 3.2 MB copied, 44 MB peak memory
Data.Text.Builder.Linear: OK
28.3 ms ± 382 μs, 17 MB allocated, 90 KB copied, 45 MB peak memory, 0.68x
Huge06
1
Data.ByteString.Builder: OK
475 μs ± 4.7 μs, 443 KB allocated, 3.0 KB copied, 45 MB peak memory
Data.Text.Builder.Linear: OK
322 μs ± 3.6 μs, 206 KB allocated, 1.0 KB copied, 45 MB peak memory, 0.68x
10
Data.ByteString.Builder: OK
4.75 ms ± 82 μs, 4.0 MB allocated, 30 KB copied, 45 MB peak memory
Data.Text.Builder.Linear: OK
3.28 ms ± 47 μs, 2.1 MB allocated, 10 KB copied, 45 MB peak memory, 0.69x
100
Data.ByteString.Builder: OK
63.0 ms ± 97 μs, 40 MB allocated, 3.7 MB copied, 45 MB peak memory
Data.Text.Builder.Linear: OK
38.3 ms ± 459 μs, 21 MB allocated, 102 KB copied, 47 MB peak memory, 0.61x
Huge07
1
Data.ByteString.Builder: OK
661 μs ± 11 μs, 568 KB allocated, 4.1 KB copied, 47 MB peak memory
Data.Text.Builder.Linear: OK
576 μs ± 9.6 μs, 304 KB allocated, 1.5 KB copied, 47 MB peak memory, 0.87x
10
Data.ByteString.Builder: OK
6.77 ms ± 34 μs, 5.5 MB allocated, 46 KB copied, 47 MB peak memory
Data.Text.Builder.Linear: OK
5.84 ms ± 100 μs, 3.1 MB allocated, 15 KB copied, 47 MB peak memory, 0.86x
100
Data.ByteString.Builder: OK
87.3 ms ± 1.3 ms, 55 MB allocated, 5.4 MB copied, 47 MB peak memory
Data.Text.Builder.Linear: OK
64.1 ms ± 755 μs, 31 MB allocated, 159 KB copied, 54 MB peak memory, 0.73x
Huge08
1
Data.ByteString.Builder: OK
1.22 ms ± 11 μs, 864 KB allocated, 6.0 KB copied, 54 MB peak memory
Data.Text.Builder.Linear: OK
883 μs ± 4.0 μs, 427 KB allocated, 2.2 KB copied, 54 MB peak memory, 0.72x
10
Data.ByteString.Builder: OK
13.4 ms ± 129 μs, 8.2 MB allocated, 184 KB copied, 54 MB peak memory
Data.Text.Builder.Linear: OK
9.00 ms ± 142 μs, 4.3 MB allocated, 22 KB copied, 54 MB peak memory, 0.67x
100
Data.ByteString.Builder: OK
154 ms ± 1.4 ms, 82 MB allocated, 7.8 MB copied, 54 MB peak memory
Data.Text.Builder.Linear: OK
96.0 ms ± 962 μs, 44 MB allocated, 221 KB copied, 55 MB peak memory, 0.62x
Huge09
1
Data.ByteString.Builder: OK
4.90 ms ± 68 μs, 2.4 MB allocated, 18 KB copied, 55 MB peak memory
Data.Text.Builder.Linear: OK
4.46 ms ± 46 μs, 1.3 MB allocated, 6.2 KB copied, 55 MB peak memory, 0.91x
10
Data.ByteString.Builder: OK
59.1 ms ± 519 μs, 24 MB allocated, 1.9 MB copied, 55 MB peak memory
Data.Text.Builder.Linear: OK
47.6 ms ± 874 μs, 14 MB allocated, 59 KB copied, 55 MB peak memory, 0.80x
100
Data.ByteString.Builder: OK
579 ms ± 5.4 ms, 246 MB allocated, 25 MB copied, 60 MB peak memory
Data.Text.Builder.Linear: OK
459 ms ± 7.9 ms, 143 MB allocated, 599 KB copied, 117 MB peak memory, 0.79x
Huge10
1
Data.ByteString.Builder: OK
10.0 ms ± 161 μs, 4.1 MB allocated, 29 KB copied, 117 MB peak memory
Data.Text.Builder.Linear: OK
9.37 ms ± 180 μs, 2.1 MB allocated, 9.1 KB copied, 117 MB peak memory, 0.93x
10
Data.ByteString.Builder: OK
117 ms ± 1.4 ms, 42 MB allocated, 3.5 MB copied, 117 MB peak memory
Data.Text.Builder.Linear: OK
98.7 ms ± 1.3 ms, 24 MB allocated, 126 KB copied, 117 MB peak memory, 0.85x
100
Data.ByteString.Builder: OK
1.159 s ± 8.8 ms, 420 MB allocated, 43 MB copied, 117 MB peak memory
Data.Text.Builder.Linear: OK
956 ms ± 2.0 ms, 251 MB allocated, 1.1 MB copied, 133 MB peak memory, 0.82x
Huge11
1
Data.ByteString.Builder: OK
25.3 ms ± 189 μs, 8.4 MB allocated, 62 KB copied, 133 MB peak memory
Data.Text.Builder.Linear: OK
23.9 ms ± 241 μs, 4.8 MB allocated, 23 KB copied, 133 MB peak memory, 0.94x
10
Data.ByteString.Builder: OK
281 ms ± 5.4 ms, 84 MB allocated, 7.8 MB copied, 133 MB peak memory
Data.Text.Builder.Linear: OK
244 ms ± 3.1 ms, 50 MB allocated, 246 KB copied, 133 MB peak memory, 0.87x
100
Data.ByteString.Builder: OK
2.772 s ± 35 ms, 855 MB allocated, 86 MB copied, 144 MB peak memory
Data.Text.Builder.Linear: OK
2.411 s ± 6.6 ms, 518 MB allocated, 2.2 MB copied, 233 MB peak memory, 0.87x
Huge12
1
Data.ByteString.Builder: OK
476 ms ± 3.9 ms, 88 MB allocated, 4.7 MB copied, 233 MB peak memory
Data.Text.Builder.Linear: OK
450 ms ± 5.2 ms, 52 MB allocated, 256 KB copied, 233 MB peak memory, 0.94x
10
Data.ByteString.Builder: OK
4.828 s ± 22 ms, 894 MB allocated, 83 MB copied, 233 MB peak memory
Data.Text.Builder.Linear: OK
4.473 s ± 81 ms, 545 MB allocated, 2.3 MB copied, 233 MB peak memory, 0.93x
100
Data.ByteString.Builder: This benchmark takes more than 100 seconds. Consider setting --timeout, if this is unexpected (or to silence this warning).
OK
48.086 s ± 417 ms, 8.7 GB allocated, 883 MB copied, 1.2 GB peak memory
Data.Text.Builder.Linear: This benchmark takes more than 100 seconds. Consider setting --timeout, if this is unexpected (or to silence this warning).
OK
44.617 s ± 448 ms, 5.4 GB allocated, 22 MB copied, 1.9 GB peak memory, 0.93x
1e20
1
Data.ByteString.Builder: OK
880 ns ± 11 ns, 5.3 KB allocated, 29 B copied, 1.9 GB peak memory
Data.Text.Builder.Linear: OK
238 ns ± 714 ps, 575 B allocated, 4 B copied, 1.9 GB peak memory, 0.27x
10
Data.ByteString.Builder: OK
5.70 μs ± 100 ns, 13 KB allocated, 70 B copied, 1.9 GB peak memory
Data.Text.Builder.Linear: OK
2.29 μs ± 28 ns, 4.0 KB allocated, 34 B copied, 1.9 GB peak memory, 0.40x
100
Data.ByteString.Builder: OK
53.5 μs ± 531 ns, 126 KB allocated, 808 B copied, 1.9 GB peak memory
Data.Text.Builder.Linear: OK
22.8 μs ± 423 ns, 37 KB allocated, 197 B copied, 1.9 GB peak memory, 0.43x
1e100
1
Data.ByteString.Builder: OK
2.36 μs ± 43 ns, 7.3 KB allocated, 29 B copied, 1.9 GB peak memory
Data.Text.Builder.Linear: OK
620 ns ± 6.2 ns, 1.5 KB allocated, 11 B copied, 1.9 GB peak memory, 0.26x
10
Data.ByteString.Builder: OK
20.1 μs ± 349 ns, 34 KB allocated, 223 B copied, 1.9 GB peak memory
Data.Text.Builder.Linear: OK
6.73 μs ± 66 ns, 15 KB allocated, 102 B copied, 1.9 GB peak memory, 0.33x
100
Data.ByteString.Builder: OK
197 μs ± 2.7 μs, 344 KB allocated, 2.6 KB copied, 1.9 GB peak memory
Data.Text.Builder.Linear: OK
64.6 μs ± 856 ns, 148 KB allocated, 570 B copied, 1.9 GB peak memory, 0.33x
1e300
1
Data.ByteString.Builder: OK
4.09 μs ± 61 ns, 11 KB allocated, 57 B copied, 1.9 GB peak memory
Data.Text.Builder.Linear: OK
2.21 μs ± 28 ns, 5.1 KB allocated, 44 B copied, 1.9 GB peak memory, 0.54x
10
Data.ByteString.Builder: OK
38.7 μs ± 665 ns, 109 KB allocated, 535 B copied, 1.9 GB peak memory
Data.Text.Builder.Linear: OK
23.3 μs ± 195 ns, 52 KB allocated, 248 B copied, 1.9 GB peak memory, 0.60x
100
Data.ByteString.Builder: OK
360 μs ± 3.9 μs, 776 KB allocated, 7.0 KB copied, 1.9 GB peak memory
Data.Text.Builder.Linear: OK
231 μs ± 2.0 μs, 535 KB allocated, 2.3 KB copied, 1.9 GB peak memory, 0.64x
1e500
1
Data.ByteString.Builder: OK
7.01 μs ± 110 ns, 15 KB allocated, 87 B copied, 1.9 GB peak memory
Data.Text.Builder.Linear: OK
2.85 μs ± 55 ns, 5.7 KB allocated, 70 B copied, 1.9 GB peak memory, 0.41x
10
Data.ByteString.Builder: OK
67.4 μs ± 529 ns, 153 KB allocated, 843 B copied, 1.9 GB peak memory
Data.Text.Builder.Linear: OK
28.7 μs ± 304 ns, 60 KB allocated, 266 B copied, 1.9 GB peak memory, 0.43x
100
Data.ByteString.Builder: OK
635 μs ± 5.3 μs, 1.2 MB allocated, 8.8 KB copied, 1.9 GB peak memory
Data.Text.Builder.Linear: OK
271 μs ± 3.2 μs, 629 KB allocated, 3.0 KB copied, 1.9 GB peak memory, 0.43x
1e1000
1
Data.ByteString.Builder: OK
12.9 μs ± 192 ns, 25 KB allocated, 165 B copied, 1.9 GB peak memory
Data.Text.Builder.Linear: OK
7.70 μs ± 115 ns, 12 KB allocated, 72 B copied, 1.9 GB peak memory, 0.60x
10
Data.ByteString.Builder: OK
126 μs ± 1.7 μs, 261 KB allocated, 1.6 KB copied, 1.9 GB peak memory
Data.Text.Builder.Linear: OK
75.0 μs ± 1.4 μs, 129 KB allocated, 573 B copied, 1.9 GB peak memory, 0.59x
100
Data.ByteString.Builder: OK
1.24 ms ± 15 μs, 2.2 MB allocated, 28 KB copied, 1.9 GB peak memory
Data.Text.Builder.Linear: OK
748 μs ± 12 μs, 1.3 MB allocated, 6.0 KB copied, 1.9 GB peak memory, 0.60x
FWIW I don't think there is demand for unbounded hexadecimal numbers, so maybe we can skip them.
It's not a blocker, but I raised https://github.com/Bodigrim/tasty-bench-fit/issues/3. Haskell ecosystem should have an automated method to find thresholds to switch between algorithms.
I'm largely happy with the direction of this PR and really appreciate the effort, but unlikely to have time for in-depth review untill I'm fully back from vacation, which is mid-June.
@wismill could you please run the following program using https://github.com/Bodigrim/tasty-bench-fit/commit/54599f597eb684b949d338fb70d176ba98d02f00?
module Main (main) where
import Data.Bits
import Data.Foldable
import Data.Text (Text)
import Data.Text.Builder.Linear.Buffer
import Data.Text.Builder.Linear.Dec.Unbounded
import Test.Tasty.Bench.Equalize (equalize, mkEqualizeConfig)
mkFunc :: Strategy -> Word -> Text
mkFunc s = (\p -> runBuffer (\b -> prependUnboundedDecimal s ((1 :: Integer) `shiftL` fromIntegral (p * 64 - 1)) b))
main :: IO ()
main = do
putStrLn "SmallOnly vs. BigOnly"
xs <- equalize $ mkEqualizeConfig (mkFunc SmallOnly) (mkFunc BigOnly) (1, 10000)
traverse_ print xs
putStrLn "BigOnly vs. HugeOnly"
ys <- equalize $ mkEqualizeConfig (mkFunc BigOnly) (mkFunc HugeOnly) (1, 10000)
traverse_ print ys
On my machine (aarch64) output is:
SmallOnly vs. BigOnly
(1,10000)
(1,5000)
(1,2500)
(1,2500)
(1,1250)
(1,625)
(1,625)
(1,313)
(1,157)
(1,79)
(1,79)
(1,40)
(1,40)
(1,20)
(1,20)
(1,20)
(1,10)
(5,10)
(5,10)
(5,10)
(5,7)
(6,7)
BigOnly vs. HugeOnly
(1,10000)
(1,10000)
(1,10000)
(1,5000)
(1,2500)
(1,1250)
(1,1250)
(1,625)
(1,313)
(1,313)
(1,157)
(1,157)
(1,79)
(1,40)
(1,20)
(1,20)
(1,20)
(1,10)
(5,10)
(7,10)
(8,10)
(8,9)
which means that we should switch from SmallOnly to BigOnly between 6 and 7 words, and from BigOnly to HugeOnly between 8 and 9 words.
Results on x86_64 (11th Gen Intel(R) Core(TM) i7-1165G7 @ 2.80GHz):
SmallOnly vs. BigOnly
"mid = 5000"
"(mean1, stdev1) = (4.59778374e-2,6.869815298e-3)"
"(mean2, stdev2) = (1.1318263e-2,1.774845416e-3)"
(1,10000)
"mid = 2500"
"(mean1, stdev1) = (1.30445774e-2,1.552743044e-3)"
"(mean2, stdev2) = (3.5654868e-3,1.431598695e-3)"
(1,5000)
"mid = 1250"
"(mean1, stdev1) = (4.052621e-3,2.029681139e-3)"
"(mean2, stdev2) = (1.0750009e-3,6.83627025e-4)"
(1,2500)
"mid = 1250"
"(mean1, stdev1) = (3.845191e-3,1.35691313e-3)"
"(mean2, stdev2) = (9.787834e-4,3.40131206e-4)"
(1,2500)
"mid = 1250"
"(mean1, stdev1) = (4.0347557e-3,7.21174631e-4)"
"(mean2, stdev2) = (8.40476875e-4,1.54848685e-4)"
(1,2500)
"mid = 625"
"(mean1, stdev1) = (9.33000725e-4,1.71546551e-4)"
"(mean2, stdev2) = (3.02076375e-4,4.2430787e-5)"
(1,1250)
"mid = 313"
"(mean1, stdev1) = (2.09292009e-4,2.8501893e-5)"
"(mean2, stdev2) = (8.6656032e-5,2.1335519e-5)"
(1,625)
"mid = 157"
"(mean1, stdev1) = (5.824842e-5,1.1770319e-5)"
"(mean2, stdev2) = (3.196024e-5,4.978011e-6)"
(1,313)
"mid = 157"
"(mean1, stdev1) = (4.5800997e-5,4.711628e-6)"
"(mean2, stdev2) = (2.6569551e-5,1.393567e-6)"
(1,313)
"mid = 79"
"(mean1, stdev1) = (1.3171081e-5,3.66954e-7)"
"(mean2, stdev2) = (9.424467e-6,1.025084e-6)"
(1,157)
"mid = 40"
"(mean1, stdev1) = (4.45294e-6,3.33314e-7)"
"(mean2, stdev2) = (3.551998e-6,1.12638e-7)"
(1,79)
"mid = 20"
"(mean1, stdev1) = (1.639029e-6,1.11781e-7)"
"(mean2, stdev2) = (1.565136e-6,4.5408e-8)"
(1,40)
"mid = 20"
"(mean1, stdev1) = (1.514367e-6,6.9813e-8)"
"(mean2, stdev2) = (1.571898e-6,6.865e-8)"
(1,40)
"mid = 20"
"(mean1, stdev1) = (1.528486e-6,4.4288e-8)"
"(mean2, stdev2) = (1.551439e-6,3.4133e-8)"
(1,40)
"mid = 20"
"(mean1, stdev1) = (1.520118e-6,1.9841e-8)"
"(mean2, stdev2) = (1.577131e-6,2.0555e-8)"
(1,40)
"mid = 20"
"(mean1, stdev1) = (1.488753e-6,1.137e-8)"
"(mean2, stdev2) = (1.574141e-6,1.097e-8)"
(1,40)
"mid = 30"
"(mean1, stdev1) = (2.699753e-6,7.182e-9)"
"(mean2, stdev2) = (2.383338e-6,1.7019e-8)"
(20,40)
"mid = 25"
"(mean1, stdev1) = (2.087846e-6,5.455e-9)"
"(mean2, stdev2) = (1.909271e-6,1.4156e-8)"
(20,30)
"mid = 22"
"(mean1, stdev1) = (1.700908e-6,1.2959e-8)"
"(mean2, stdev2) = (1.752982e-6,6.47e-9)"
(20,25)
"mid = 23"
"(mean1, stdev1) = (1.809347e-6,1.1846e-8)"
"(mean2, stdev2) = (1.81101e-6,1.3703e-8)"
(22,25)
"mid = 23"
"(mean1, stdev1) = (1.830558e-6,3.956e-9)"
"(mean2, stdev2) = (1.862179e-6,4.214e-9)"
(22,25)
"mid = 24"
"(mean1, stdev1) = (1.965187e-6,4.73e-10)"
"(mean2, stdev2) = (1.991907e-6,7.025e-9)"
(23,25)
(24,25)
BigOnly vs. HugeOnly
"mid = 5000"
"(mean1, stdev1) = (1.0889588e-2,2.542252765e-3)"
"(mean2, stdev2) = (5.2572238e-3,3.108475712e-3)"
(1,10000)
"mid = 5000"
"(mean1, stdev1) = (1.12586338e-2,1.382673975e-3)"
"(mean2, stdev2) = (5.8357845e-3,1.517858595e-3)"
(1,10000)
"mid = 5000"
"(mean1, stdev1) = (1.61702436e-2,2.115097147e-3)"
"(mean2, stdev2) = (5.6585553e-3,8.00919523e-4)"
(1,10000)
"mid = 2500"
"(mean1, stdev1) = (3.56934835e-3,4.36860153e-4)"
"(mean2, stdev2) = (2.142532825e-3,2.62033849e-4)"
(1,5000)
"mid = 1250"
"(mean1, stdev1) = (9.54141525e-4,1.38920446e-4)"
"(mean2, stdev2) = (8.12730925e-4,1.70330186e-4)"
(1,2500)
"mid = 1250"
"(mean1, stdev1) = (7.65532706e-4,4.5347891e-5)"
"(mean2, stdev2) = (6.07254071e-4,4.73267e-5)"
(1,2500)
"mid = 1250"
"(mean1, stdev1) = (7.77719309e-4,2.3674844e-5)"
"(mean2, stdev2) = (6.06289525e-4,1.2483223e-5)"
(1,2500)
"mid = 625"
"(mean1, stdev1) = (2.29466555e-4,6.500419e-6)"
"(mean2, stdev2) = (2.20277333e-4,9.088741e-6)"
(1,1250)
"mid = 625"
"(mean1, stdev1) = (2.32611464e-4,6.672685e-6)"
"(mean2, stdev2) = (2.16242526e-4,4.012154e-6)"
(1,1250)
"mid = 625"
"(mean1, stdev1) = (2.29562364e-4,2.424142e-6)"
"(mean2, stdev2) = (2.1925526e-4,2.980394e-6)"
(1,1250)
"mid = 625"
"(mean1, stdev1) = (2.30760653e-4,8.5751e-7)"
"(mean2, stdev2) = (2.1911469e-4,1.249151e-6)"
(1,1250)
"mid = 313"
"(mean1, stdev1) = (7.0739582e-5,4.37465e-7)"
"(mean2, stdev2) = (7.957536e-5,4.73354e-7)"
(1,625)
"mid = 469"
"(mean1, stdev1) = (1.38272649e-4,5.27541e-7)"
"(mean2, stdev2) = (1.279945e-4,2.79331e-7)"
(313,625)
"mid = 391"
"(mean1, stdev1) = (1.01884223e-4,4.58801e-7)"
"(mean2, stdev2) = (1.00837992e-4,4.7356e-7)"
(313,469)
"mid = 391"
"(mean1, stdev1) = (1.02182493e-4,2.74346e-7)"
"(mean2, stdev2) = (1.00028144e-4,3.48375e-7)"
(313,469)
"mid = 352"
"(mean1, stdev1) = (8.5664813e-5,2.84613e-7)"
"(mean2, stdev2) = (8.8228922e-5,2.6671e-7)"
(313,391)
"mid = 371"
"(mean1, stdev1) = (9.2891435e-5,2.21306e-7)"
"(mean2, stdev2) = (9.3815449e-5,8.8113e-8)"
(352,391)
"mid = 381"
"(mean1, stdev1) = (9.6993513e-5,2.28939e-7)"
"(mean2, stdev2) = (9.7232281e-5,1.03502e-7)"
(371,391)
"mid = 381"
"(mean1, stdev1) = (9.7472642e-5,9.8546e-8)"
"(mean2, stdev2) = (9.7706649e-5,1.77847e-7)"
(371,391)
"mid = 381"
I stopped it there because it was repeating the same range.
Benchmarks for less performant laptop CPU Intel(R) Core(TM) i5-5200U CPU @ 2.20GHz:
SmallOnly vs. BigOnly
(1,10000)
(1,5000)
(1,2500)
(1,1250)
(1,1250)
(1,1250)
(1,1250)
(1,1250)
(1,625)
(1,313)
(1,157)
(1,157)
(1,79)
(1,40)
(1,40)
(20,40)
(20,30)
(20,25)
(22,25)
(23,25)
(24,25)
BigOnly vs. HugeOnly
(1,10000)
(1,5000)
(1,2500)
(1,2500)
(1,2500)
(1,2500)
(1,2500)
(1,2500)
(1250,2500)
(1250,1875)
(1250,1562)
(1250,1562)
(1250,1562)
(1250,1406)
(1328,1406)
(1328,1406)
(1367,1406)
(1386,1406)
(1386,1406)
(1386,1406)
Late to the party: 8 × AMD Ryzen 5 2500U @ 2GHz
SmallOnly vs. BigOnly
(1,10000)
(1,5000)
(1,2500)
(1,2500)
(1,1250)
(1,1250)
(1,625)
(1,313)
(1,157)
(1,157)
(1,79)
(1,79)
(1,79)
(1,40)
(20,40)
(20,40)
(20,30)
(20,30)
(25,30)
(25,30)
(25,30)
(27,30)
(27,28)
BigOnly vs. HugeOnly
(1,10000)
(1,10000)
(1,10000)
(1,5000)
(1,5000)
(1,2500)
(1,2500)
(1,2500)
(1,1250)
(1,1250)
(625,1250)
(625,937)
(625,781)
(625,703)
(625,703)
(625,703)
(625,703)
(625,664)
(644,664)
Rebased, added/fixed notes required by review and the (optional) benchmark. The latter requires setting cabal.project.local for tasty-bench-fit.
I pondered about algorithmic complexity of long multiplication / division and still cannot figure a reason why would a range exist (on x86_64) where prependBigNat is optimal. The only explanation I can come up with is that prependHugeNat somehow has an unexpectedly large constant factor. Could we try building a list of powers of 10 (instead of building recursive closures (Bool → DigitsWriter# s)) there?
Could we try building a list of powers of 10 (instead of building recursive closures
(Bool → DigitsWriter# s)) there?
@Bodigrim I already tried using lists as bytestring does and could not come with a good solution. Frankly I dedicated far too much time here and may have lost myself on the way (fun ride though). Right now I would like to focus on other tasks. If there is no obvious solution we can still consider using the bytestring builder at some threshold and comment/revert the suspicious code. I would not like either to use code in the library if its perf is not clear.
Right now the feature is missing in the library, so maybe take the safest path now and give it another try in a follow-up PR.
Fair enough, I appreciate a lot the insane amount of work you already put into this. If you remove FIXME commit, I'm happy to merge.
@Bodigrim done, thanks for the quick fix. I think the last 6-7 commits could be squashed, but it’s up to you.
Thanks for the monumental work, @wismill. Let me merge as is; I'll check I wish to change anything later.
(FWIW I'm increasingly inclined to drop prependBigNat algorithm)
This is now released as text-builder-linear-0.1.3, thanks again @wismill!
(Aside: My current workaround for printing
Integers andNaturals is shoving in aShowconstraint and doingfromString (show n), which feels kinda bad. I moved to linear-text-builder for performance & ergonomics, so I'd love to see this get merged.)
@raehik could you possibly update text-builder-linear and give it a try?