search

ekzhang / crepe

Datalog compiler embedded in Rust as a procedural macro
Apache License 2.0
453 stars 16 forks source link

Minimize and speed up the Collatz conjecture bench #20

Closed ljedrz closed 2 years ago

ljedrz commented 2 years ago

Now that I've had a bit more time to tinker with crepe, I was able to minimize the Collatz conjecture benchmark which, in my opinion, makes it a lot more clear. This also made it a lot faster:

collatz/9               time:   [2.2401 us 2.2420 us 2.2440 us]                       
                        change: [-50.991% -50.896% -50.813%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 12 outliers among 100 measurements (12.00%)
  4 (4.00%) low mild
  5 (5.00%) high mild
  3 (3.00%) high severe
collatz/77031           time:   [37.722 us 37.743 us 37.765 us]                           
                        change: [-47.089% -46.975% -46.839%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 5 outliers among 100 measurements (5.00%)
  2 (2.00%) high mild
  3 (3.00%) high severe
collatz/9780657630      time:   [125.33 us 125.67 us 125.96 us]                               
                        change: [-50.623% -50.390% -50.161%] (p = 0.00 < 0.05)
                        Performance has improved.
ekzhang commented 2 years ago

Nice!! Cool to see that in both cases, the asymptotic time complexity appears to be the same (all are around -50%). I think this means the semi-naive evaluation is probably working.