search

poanetwork / vdf

An implementation of Verifiable Delay Functions in Rust
Apache License 2.0
169 stars 53 forks source link

sieve with bit-vec #12

Closed burdges closed 5 years ago

burdges commented 5 years ago

I believe this improves sieve cache performance with the bit-vec crate, although I've some hiccup with cargo bench for testing this. This also fixes the confusing reference in #11

burdges commented 5 years ago

Just fyi my benchmarks look like:

     Running /Users/jeff/Projects/PolakaDot/vdf/target/release/deps/classgroup_bench-101ad79d6fa635b8
Gnuplot not found, disabling plotting
thread 'main' panicked at 'bug in calling script', src/libcore/option.rs:1038:5
stack backtrace:
   0: std::sys::unix::backtrace::tracing::imp::unwind_backtrace
   1: std::sys_common::backtrace::_print
   2: std::panicking::default_hook::{{closure}}
   3: std::panicking::default_hook
   4: std::panicking::rust_panic_with_hook
   5: std::panicking::continue_panic_fmt
   6: rust_begin_unwind
   7: core::panicking::panic_fmt
   8: core::option::expect_failed
   9: classgroup_bench::main
  10: std::rt::lang_start::{{closure}}
  11: std::panicking::try::do_call
  12: __rust_maybe_catch_panic
  13: std::rt::lang_start_internal
  14: main
error: bench failed
burdges commented 5 years ago

Just running time cargo test create_discriminant shows no concrete improvements, so maybe worth fixing the benchmarks.

burdges commented 5 years ago

There was a BitVec in std way back https://doc.rust-lang.org/1.2.0/std/collections/struct.BitVec.html but never got stabilized due to limits on indexing https://github.com/Gankro/rfcs/blob/collections2/text/0000-collections-reform-part-2.md

vkomenda commented 5 years ago

Just fyi my benchmarks look like

Well, my benchmarks don't look like yours. :smile: 

$ ./bench.sh 123456
   Compiling clap v2.32.0
   Compiling criterion v0.2.10
   Compiling vdf v0.1.0 (/home/vk/src/poanetwork/vdf/vdf)
    Finished release [optimized] target(s) in 30.75s
     Running target/release/deps/classgroup_bench-992367e616934bab
square with seed 123456: 512                                                                             
                        time:   [16.155 us 16.186 us 16.223 us]
Found 8 outliers among 100 measurements (8.00%)
  3 (3.00%) high mild
  5 (5.00%) high severe

multiply with seed 123456: 512                                                                             
                        time:   [20.729 us 20.802 us 20.915 us]
Found 7 outliers among 100 measurements (7.00%)
  1 (1.00%) high mild
  6 (6.00%) high severe

square with seed 123456: 1024                                                                             
                        time:   [36.114 us 36.209 us 36.356 us]
Found 11 outliers among 100 measurements (11.00%)
  4 (4.00%) high mild
  7 (7.00%) high severe

multiply with seed 123456: 1024                                                                             
                        time:   [46.264 us 46.401 us 46.593 us]
Found 11 outliers among 100 measurements (11.00%)
  4 (4.00%) high mild
  7 (7.00%) high severe

square with seed 123456: 2048                                                                            
                        time:   [89.324 us 89.647 us 90.055 us]
Found 8 outliers among 100 measurements (8.00%)
  3 (3.00%) high mild
  5 (5.00%) high severe

multiply with seed 123456: 2048                                                                            
                        time:   [115.92 us 116.10 us 116.32 us]
Found 4 outliers among 100 measurements (4.00%)
  3 (3.00%) high mild
  1 (1.00%) high severe
burdges commented 5 years ago

Oddly this may even cause a regression: https://github.com/w3f/vdf/commit/961caee8c9730f5b245ef6e3492d358e1a29fb44

burdges commented 5 years ago

I see, cargo bench in the vdf directory does not work, but so far the bench.sh script seemingly works. Thanks!

burdges commented 5 years ago

Cool. I suppose this allocation must be being optimized away, which supports the regression in that other branch https://github.com/w3f/vdf/commit/961caee8c9730f5b245ef6e3492d358e1a29fb44 for which I did not send a pull request. Anyways..