Summary: I need to maintain a large number of things in a sorted structure with iteration, ith insertion and lookup. I'm presently using a Vec but the performance is abysmal. I could really use recommendations on alternative structures to use, fancy tricks.
Hidy folks,
I have an implementation of "Effective Computation of Biased Quantiles Over Data Streams" in my quantiles library that works pretty well if the number of samples you have is low-ish, say a handful of thousands. The implementation is here. CKMS is a data structure that allows you to answer approximate quantile queries on a stream of data in bounded space. The underlying algorithm has this neat trick where the samples stored into the structure are compressed in such a way that any quantile queries post-compression have a guaranteed error bound on then. You save space and get answers with a guaranteed accuracy. Tidy.
Now, the problem I've got is I'm finding a need for CKMS structures with significantly more samples and the insert performance with my implementation is just killing me. I've been fiddling with the implementation, have hit a brick wall and could use some advice on where to go next. I've put together an in-progress branch that has criterion benchmarks and some fiddling micro-optimizations. You can find that branch on Github. I run the benchmarks like cargo bench -- --test --nocapture.
The basic problem I have with my implementation is this: quantiles/CKMS stores its samples, sorted, in a Vec. The algorithm needs access to i-1, i and i+1 elements in the underlying store – which is why I use a Vec – and must be able to perform sorted iteration on the elements.
Here, let's have a look at insertion. The whole function starts here but the important part is:
} else {
// inserting somewhere in the middle
let mut idx = 0;
let mut r = 0;
for smpl in self.samples.iter() {
match smpl.v.partial_cmp(&v).unwrap() {
cmp::Ordering::Less => {
idx += 1;
r += smpl.g
}
_ => break,
}
}
// To insert in the middle we have to know two things:
//
// * the correct point of insertion, 'idx'
// * the sum of all Entry.g prior to 'idx', called 'r'
//
// We could avoid the 'idx' computation if we could get at 'r'
// some other way.
(idx, invariant(r as f64, self.error) - 1)
};
self.samples.insert(
idx,
Entry {
v: v,
g: 1,
delta: delta,
},
);
In the paper v is the value being inserted, g is the difference in ranks between samples i and i-1 and delta is the difference between the lowest and greatest possible ranks of i. Just, you know, incidentally. The important part here is that to insert we have to do a linear trawl through the Vec to compute r so that we can compute delta for the newly inserted item, as the comment points out, and then when we insert all the existing items get scooted down one in the Vec.
Compression – defined here – is much smaller than insertion.
fn compress(&mut self) {
if self.samples.len() < 3 {
return;
}
let mut s_mx = self.samples.len() - 1;
let mut idx = 0;
let mut r: u32 = 1;
while idx < s_mx {
let cur_g = self.samples[idx].g;
let nxt_v = self.samples[idx + 1].v;
let nxt_g = self.samples[idx + 1].g;
let nxt_delta = self.samples[idx + 1].delta;
if cur_g + nxt_g + nxt_delta <= invariant(r as f64, self.error) {
self.samples[idx].v = nxt_v;
self.samples[idx].g += nxt_g;
self.samples[idx].delta = nxt_delta;
self.samples.remove(idx + 1);
s_mx -= 1;
} else {
idx += 1;
}
r += 1;
}
}
We perform a pairwise step through the samples Vec, check against the invariant property the paper defines and, when possible, compress two samples into one (which turns out to be, modify one in-place and remove another from the Vec, incurring more scooting.)
My challenge is this: I can't use BinaryHeap or LinkedList. To the first, I'm maintaining a sorted store, right, so BinaryHeap immediately comes to mind. The tricky bit is on insertion I have to be able to query the structure for all Entry with v less than the to-be-inserted v so that r can be computed. Also, BinaryHeap does not allow sorted iteration – I think – without conversion into a Vec first, trouble for compressing and querying the structure. The paper authors discuss storing their samples in a linkedlist but Rust stdlib LinkedList does not allow insertion at arbitrary points.
I have been looking at BinaryHeap's implementation – specifically its Hole technique – with some interest but I don't know if I'd be barking up the wrong tree there or not. If anyone knows of any better structure than Vec that I could use or any wacky unsafe tricks I could make use of I'd greatly appreciate it.
Boy, if you read this all the way to the end thank you very much.
).