Robbepop / stevia

A simple (unfinished) SMT solver for QF_ABV.
Other
36 stars 5 forks source link

[stevia_ast] Optimize children iterators #15

Closed Robbepop closed 5 years ago

Robbepop commented 5 years ago

Performance improvements of all children iterators. Also adds the following new APIs to all expression nodes:

fn children_slice(&self) -> &[AnyExpr];
fn children_slice_mut(&mut self) -> &mut [AnyExpr];
fn into_children_vec(self) -> Vec<AnyExpr>;

Also recursive children iterator is less memory demanding and performs slightly better.

TODO

Benchmark Results

 name                       target/benches/benches_before_8.txt ns/iter  benches_after_22.bench ns/iter  diff ns/iter   diff %  speedup 
 children::binary           14                                           10                                        -4  -28.57%   x 1.40 
 children::nary             14                                           12                                        -2  -14.29%   x 1.17 
 children::rec_binary_big   1,509                                        906                                     -603  -39.96%   x 1.67 
 children::rec_nary_big     2,199                                        1,633                                   -566  -25.74%   x 1.35 
 children::rec_ternary_big  1,126                                        924                                     -202  -17.94%   x 1.22 
 children::rec_unary_big    2,130                                        1,114                                 -1,016  -47.70%   x 1.91 
 children::ternary          13                                           10                                        -3  -23.08%   x 1.30 
 children::unary            11                                           4                                         -7  -63.64%   x 2.75 
 clone::binary              24                                           23                                        -1   -4.17%   x 1.04 
 clone::nary                54                                           51                                        -3   -5.56%   x 1.06 
 clone::ternary             38                                           37                                        -1   -2.63%   x 1.03 
 clone::unary               15                                           17                                         2   13.33%   x 0.88 
 into_children::binary      58                                           38                                       -20  -34.48%   x 1.53 
 into_children::nary        147                                          76                                       -71  -48.30%   x 1.93 
 into_children::ternary     84                                           58                                       -26  -30.95%   x 1.45 
 into_children::unary       34                                           26                                        -8  -23.53%   x 1.31
coveralls commented 5 years ago

Coverage Status

Coverage increased (+0.5%) to 82.745% when pulling ea09da39db904d185114e7f65100f23484e650e7 on children-refactor into 263f53b64bc382e3ea5f41a4e59efe1259459394 on master.

codecov-io commented 5 years ago

Codecov Report

Merging #15 into master will decrease coverage by <.01%. The diff coverage is 65.33%.

Impacted file tree graph

@@            Coverage Diff             @@
##           master      #15      +/-   ##
==========================================
- Coverage   82.73%   82.73%   -0.01%     
==========================================
  Files          91       92       +1     
  Lines       10549    10287     -262     
==========================================
- Hits         8728     8511     -217     
+ Misses       1821     1776      -45
Impacted Files Coverage Δ
stevia_ast/src/terms/arithmetic/mul.rs 0% <ø> (-75%) :arrow_down:
stevia_ast/src/terms/arithmetic/add.rs 0% <ø> (-75%) :arrow_down:
stevia_ast/src/lib.rs 100% <ø> (ø) :arrow_up:
stevia_ast/src/terms/bitwise/bitor.rs 0% <ø> (-75%) :arrow_down:
stevia_ast/src/terms/arithmetic/smod.rs 0% <ø> (ø) :arrow_up:
...evia_ast/src/terms/shift/arithmetic_shift_right.rs 0% <ø> (-75%) :arrow_down:
stevia_ast/src/formulas/xor.rs 0% <ø> (-75%) :arrow_down:
stevia_ast/src/terms/shift/logical_shift_right.rs 0% <ø> (-75%) :arrow_down:
stevia_ast/src/terms/bitwise/bitand.rs 0% <ø> (-75%) :arrow_down:
stevia_ast/src/formulas/and.rs 0% <ø> (-75%) :arrow_down:
... and 44 more

Continue to review full report at Codecov.

Legend - Click here to learn more Δ = absolute <relative> (impact), ø = not affected, ? = missing data Powered by Codecov. Last update 263f53b...ea09da3. Read the comment docs.