Merge may result in index out of bounds panic

[danielnelson]

I've been working on a feature for the metrics crate (metrics-rs/metrics#306) that uses the DDSketch::merge function, but under load I am frequently getting panics:

index out of bounds: the len is 10939 but the index is 10939', /usr/local/cargo/registry/src/github.com-1ecc6299db9ec823/sketches-ddsketch-0.1.3/src/store.rs:155:22

I have written a randomized test program:

use rand::prelude::*;
use rand::rngs::StdRng;
use sketches_ddsketch::{Config, DDSketch};

fn main() {
    let config = Config::new(0.0001, 32_768, 1.0e-9);
    let mut sketches = vec![
        DDSketch::new(config),
        DDSketch::new(config),
        DDSketch::new(config)];


    let mut rng: StdRng = rand::SeedableRng::seed_from_u64(42);
    let mut i = 1;
    loop {
        let samples = rng.gen_range(0..20000);
        sketches[0] = DDSketch::new(config);
        for _ in 0..samples {
            let rv: i64 = rng.gen_range(0..8000000000);
            sketches[0].add(rv as f64);
        }

        let mut merged = DDSketch::new(config);
        for sketch in &sketches {
            merged.merge(sketch).unwrap();
        }
        sketches.rotate_right(1);

        if i % 1000 == 0 {
            print!(".");
        }
        i += 1;
    }
}

For me, when run in release mode, this program crashes after a few seconds with:

thread 'main' panicked at 'index out of bounds: the len is 32768 but the index is 18446744073709551613', /home/dbn/.cargo/registry/src/github.com-1ecc6299db9ec823/sketches-ddsketch-0.1.3/src/store.rs:170:21

This is a different line than the panics in my original program, so I'm not sure if it is the same issue.

[mheffner]

@danielnelson Thanks for this issue. I haven't spent much time in this code recently so I'll need to re-familiarize myself, but having a test case will help a lot. Cheers!

[danielnelson]

I've been looking at this issue further, without much luck. I know what happens but I don't understand why the code does what it does now. I feel like it would be helpful if the code mirrored other implementations more closely. Would you be open to a PR where I make a change like this?

[mheffner]

I've pushed version 0.2.0 of this crate with your fix. Thanks again!

[danielnelson]

ty!