search

JuliaAlgebra / MultivariatePolynomials.jl

Multivariate polynomials interface
https://juliaalgebra.github.io/MultivariatePolynomials.jl/stable/
Other
135 stars 27 forks source link

0-allocation mutable rem #235

Closed blegat closed 1 year ago

blegat commented 1 year ago

pseudo_rem has now 0 allocation for TypedPolynomials.

It got worse for Rational{BigInt} but that should be fixed by https://github.com/jump-dev/MutableArithmetics.jl/issues/187

Benchmarks on Julia v1.8.4 (ArchLinux 64-bits)

Int64

Benchmark 0

Before

Time Alloc Memory
SIMDPolynomials 756.891 ns 36 2.70 KiB
DynamicPolynomials 11.268 μs 298 17.39 KiB
TypedPolynomials 567.854 ns 32 2.39 KiB

After

Time Alloc Memory
SIMDPolynomials 487.365 ns 16 1.14 KiB
DynamicPolynomials 6.283 μs 194 10.66 KiB
TypedPolynomials 297.865 ns 12 848 bytes

Benchmark 1

Before

Time Alloc Memory
SIMDPolynomials 166.666 μs 3178 2.07 MiB
DynamicPolynomials 1.379 ms 31834 3.61 MiB
TypedPolynomials 151.929 μs 2384 2.20 MiB

After

Time Alloc Memory
SIMDPolynomials 131.935 μs 1981 2.10 MiB
DynamicPolynomials 1.074 ms 24072 3.28 MiB
TypedPolynomials 125.625 μs 1270 2.26 MiB

Benchmark 2

Before

Time Alloc Memory
SIMDPolynomials 5.869 μs 327 48.98 KiB
DynamicPolynomials 62.769 μs 2183 174.41 KiB
TypedPolynomials 13.474 μs 350 84.80 KiB

After

Time Alloc Memory
SIMDPolynomials 5.211 μs 282 45.50 KiB
DynamicPolynomials 53.673 μs 1983 160.86 KiB
TypedPolynomials 12.505 μs 325 81.31 KiB

Benchmark 3

Before

Time Alloc Memory
SIMDPolynomials 776.772 μs 34460 18.16 MiB
DynamicPolynomials 6.199 ms 166189 27.02 MiB
TypedPolynomials 459.932 μs 9763 25.74 MiB

After

Time Alloc Memory
SIMDPolynomials 697.154 μs 31439 17.63 MiB
DynamicPolynomials 5.861 ms 157628 25.91 MiB
TypedPolynomials 389.644 μs 6742 25.04 MiB

BigInt

Benchmark 0

Before

Time Alloc Memory
SIMDPolynomials 1.653 μs 87 3.64 KiB
DynamicPolynomials 11.814 μs 347 18.20 KiB
TypedPolynomials 1.472 μs 83 3.33 KiB

After

Time Alloc Memory
SIMDPolynomials 1.068 μs 50 1.73 KiB
DynamicPolynomials 6.896 μs 234 11.34 KiB
TypedPolynomials 905.559 ns 46 1.42 KiB

Benchmark 1

Before

Time Alloc Memory
SIMDPolynomials 572.458 μs 22329 2.04 MiB
DynamicPolynomials 1.456 ms 44234 3.37 MiB
TypedPolynomials 573.649 μs 21529 2.17 MiB

After

Time Alloc Memory
SIMDPolynomials 456.701 μs 14989 1.94 MiB
DynamicPolynomials 1.167 ms 35450 3.07 MiB
TypedPolynomials 465.160 μs 14192 2.09 MiB

Benchmark 2

Before

Time Alloc Memory
SIMDPolynomials 10.889 μs 495 52.15 KiB
DynamicPolynomials 71.199 μs 2397 178.62 KiB
TypedPolynomials 21.337 μs 509 87.74 KiB

After

Time Alloc Memory
SIMDPolynomials 9.932 μs 446 48.54 KiB
DynamicPolynomials 60.253 μs 2195 165.34 KiB
TypedPolynomials 20.582 μs 460 83.63 KiB

Benchmark 3

Before

Time Alloc Memory
SIMDPolynomials 2.850 ms 89874 19.15 MiB
DynamicPolynomials 7.889 ms 225119 28.16 MiB
TypedPolynomials 3.466 ms 65129 26.73 MiB

After

Time Alloc Memory
SIMDPolynomials 2.739 ms 84291 18.53 MiB
DynamicPolynomials 7.386 ms 205446 26.83 MiB
TypedPolynomials 3.241 ms 59546 25.94 MiB

Rational{BigInt}

Benchmark 0

Before

Time Alloc Memory
SIMDPolynomials 4.745 μs 224 30.89 KiB
DynamicPolynomials 10.068 μs 409 40.30 KiB
TypedPolynomials 4.665 μs 220 30.58 KiB

After

Time Alloc Memory
SIMDPolynomials 3.156 μs 225 6.08 KiB
DynamicPolynomials 8.258 μs 384 14.98 KiB
TypedPolynomials 2.967 μs 221 5.77 KiB

Benchmark 1

Before

Time Alloc Memory
SIMDPolynomials 1.831 ms 79864 4.99 MiB
DynamicPolynomials 2.695 ms 100499 6.13 MiB
TypedPolynomials 1.851 ms 79228 5.13 MiB

After

Time Alloc Memory
SIMDPolynomials 1.632 ms 72688 4.14 MiB
DynamicPolynomials 2.378 ms 87892 5.28 MiB
TypedPolynomials 1.637 ms 72052 4.30 MiB

Benchmark 2

Before

Time Alloc Memory
SIMDPolynomials 19.508 μs 1051 84.46 KiB
DynamicPolynomials 81.559 μs 3095 215.84 KiB
TypedPolynomials 29.377 μs 1061 120.20 KiB

After

Time Alloc Memory
SIMDPolynomials 19.282 μs 1035 81.00 KiB
DynamicPolynomials 72.224 μs 2898 201.97 KiB
TypedPolynomials 29.254 μs 1045 116.23 KiB

Benchmark 3

Before

Time Alloc Memory
SIMDPolynomials 6.106 ms 234056 31.93 MiB
DynamicPolynomials 12.385 ms 388052 41.32 MiB
TypedPolynomials 8.042 ms 207249 39.56 MiB

After

Time Alloc Memory
SIMDPolynomials 6.093 ms 243254 31.15 MiB
DynamicPolynomials 12.210 ms 341419 38.91 MiB
TypedPolynomials 7.650 ms 216447 38.60 MiB

Old

Benchmark 0

Before

Time Alloc Memory
SIMDPolynomials 4.838 μs 224 30.89 KiB
DynamicPolynomials 10.394 μs 409 40.30 KiB
TypedPolynomials 4.603 μs 220 30.58 KiB

After

Time Alloc Memory
SIMDPolynomials 4.911 μs 254 31.14 KiB
DynamicPolynomials 10.012 μs 409 40.30 KiB
TypedPolynomials 4.699 μs 234 30.39 KiB

Benchmark 1

Before

Time Alloc Memory
SIMDPolynomials 1.902 ms 79864 4.99 MiB
DynamicPolynomials 2.704 ms 100499 6.13 MiB
TypedPolynomials 1.856 ms 79236 5.13 MiB

After

Time Alloc Memory
SIMDPolynomials 1.910 ms 83714 5.04 MiB
DynamicPolynomials 2.672 ms 98083 6.18 MiB
TypedPolynomials 1.942 ms 81896 5.16 MiB

Benchmark 2

Before

Time Alloc Memory
SIMDPolynomials 5.929 μs 327 48.98 KiB
DynamicPolynomials 63.777 μs 2183 174.41 KiB
TypedPolynomials 13.320 μs 354 84.86 KiB

After

Time Alloc Memory
SIMDPolynomials 5.517 μs 286 45.91 KiB
DynamicPolynomials 55.233 μs 1992 161.52 KiB
TypedPolynomials 13.200 μs 338 82.22 KiB

Benchmark 3

Before

Time Alloc Memory
SIMDPolynomials 758.299 μs 34460 18.16 MiB
DynamicPolynomials 6.517 ms 166189 27.02 MiB
TypedPolynomials 463.647 μs 9779 25.74 MiB

After

Time Alloc Memory
SIMDPolynomials 816.231 μs 31790 17.84 MiB
DynamicPolynomials 6.357 ms 157720 25.92 MiB
TypedPolynomials 393.523 μs 7093 25.35 MiB

Part of https://github.com/JuliaAlgebra/MultivariatePolynomials.jl/issues/194