artichoke / ferrocarril

🚆 Experiments to embed Ruby on Rails in Rust with mruby
https://artichoke.github.io/ferrocarril/mruby/
MIT License
62 stars 2 forks source link

Cactusref optimize cycle detection #206

Closed lopopolo closed 5 years ago

lopopolo commented 5 years ago

Use a faster hasher by using the hashbrown crate. We're only hashing pointers. We do not care about being cryptographically secure. Switching to the hashbrown simpler Hasher saves 32 bytes on the size of the RcBox.

Properly implement BFS in when detecting cycles to be linear time with the number of nodes. The runtime complexity is O(nodes + links). We need to crawl all the links because we need to compute the cycle-internal strong counts.

This script adds a benchmark. Compared to master, performance is improved about 90% for singly linked and complete graphs of 50 nodes.

$ cargo bench -p cactusref
drop a circular graph/10
                        time:   [19.512 us 19.560 us 19.616 us]
                        change: [-69.879% -69.682% -69.470%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 14 outliers among 100 measurements (14.00%)
  6 (6.00%) high mild
  8 (8.00%) high severe
drop a circular graph/50
                        time:   [223.07 us 223.65 us 224.29 us]
                        change: [-91.266% -91.197% -91.133%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 7 outliers among 100 measurements (7.00%)
  1 (1.00%) low mild
  3 (3.00%) high mild
  3 (3.00%) high severe

drop a fully connected graph/10
                        time:   [61.076 us 61.369 us 61.694 us]
                        change: [-72.808% -72.624% -72.430%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 9 outliers among 100 measurements (9.00%)
  6 (6.00%) high mild
  3 (3.00%) high severe
drop a fully connected graph/50
                        time:   [2.7680 ms 2.7989 ms 2.8381 ms]
                        change: [-87.763% -87.604% -87.423%] (p = 0.00 < 0.05)
                        Performance has improved.
Found 7 outliers among 100 measurements (7.00%)
  4 (4.00%) high mild
  3 (3.00%) high severe