Vectorizing KLL Sketch

[Gourav Kumar <go...@gmail.com>]

Hi All,

Hope you all are keeping well in these COVID times.

I am using KLL Sketch for my project where I need to compute approx
percentile over a stream.
I have gone through the paper Streaming Quantiles Algorithms with Small
Space and Update Time (arxiv.org) <https://arxiv.org/pdf/1907.00236.pdf>.

There in the last section in appendix Figure 11, it has been mentioned that
a significant *amount of time is spend in sorting* after sketch becomes
full and, also the figure shows with sort the update time goes to *50ns(
Opposed to 20ns without sorting)*.

I was wondering if there has been an effort to improve on this using
vectorized instruction (leveragin AVX2, AVX512 instructions) even if it
works just for integers & floats.

There are Sorts like Bitonic Sort which can reduce sorting time with AVX
instructions for smaller arrays, as they use sorting networks.

My Question to team is :

Q1. Some guidance/pointers on any KLL Sketch vectorization effort in this
direction if any? (Specially to reduce the sort time, even if it works just
for integer & float sketches)

I tried to optimize sketch further for integer streams. It was evident in
profiling that 50% of time is spent in sorting. Sorting suffered mostly
because of branch misprediction.

Q2. Do you think any such vectorization effort will be better without lazy
compaction?  As the level boundaries will be fixed, which might help while
loading/storing data into vector registers.

-- 
Regards,
Gourav

Re: Vectorizing KLL Sketch

[Gourav Kumar <go...@gmail.com>]

Hi Edo,

Thanks for the reply.
I would like to help build a prototype. I will experiment with AVX2 &
AVX512 instructions, and see if I get something in experiments.

Thank You,
Gourav

On Mon, 12 Apr 2021 at 23:52, Edo Liberty <ed...@gmail.com> wrote:

> Hi Gourav
> This sounds like a very good idea. I’m sure it will improve the
> performance for KLL. Would you care to help  build a prototype for it?
> Asaik we didn’t experiment with SIMD instruction sets yet.
> Edo
>
>
> On Mon, Apr 12, 2021 at 08:50 Gourav Kumar <go...@gmail.com> wrote:
>
>> Hi All,
>>
>> Hope you all are keeping well in these COVID times.
>>
>> I am using KLL Sketch for my project where I need to compute approx
>> percentile over a stream.
>> I have gone through the paper Streaming Quantiles Algorithms with Small
>> Space and Update Time (arxiv.org) <https://arxiv.org/pdf/1907.00236.pdf>.
>>
>>
>> There in the last section in appendix Figure 11, it has been mentioned
>> that a significant *amount of time is spend in sorting* after sketch
>> becomes full and, also the figure shows with sort the update time goes to *50ns(
>> Opposed to 20ns without sorting)*.
>>
>> I was wondering if there has been an effort to improve on this using
>> vectorized instruction (leveragin AVX2, AVX512 instructions) even if it
>> works just for integers & floats.
>>
>> There are Sorts like Bitonic Sort which can reduce sorting time with AVX
>> instructions for smaller arrays, as they use sorting networks.
>>
>> My Question to team is :
>>
>> Q1. Some guidance/pointers on any KLL Sketch vectorization effort in this
>> direction if any? (Specially to reduce the sort time, even if it works just
>> for integer & float sketches)
>>
>> I tried to optimize sketch further for integer streams. It was evident in
>> profiling that 50% of time is spent in sorting. Sorting suffered mostly
>> because of branch misprediction.
>>
>> Q2. Do you think any such vectorization effort will be better without
>> lazy compaction?  As the level boundaries will be fixed, which might help
>> while loading/storing data into vector registers.
>>
>>
>> --
>> Regards,
>> Gourav
>>
>

-- 
Regards,
Gourav