DEV Community: Max Kray

Filtering a Vector with SIMD Instructions (AVX-2 and AVX-512)

Max Kray — Thu, 01 Sep 2022 10:31:49 +0000

👋 Hi, dev.to!

The problem

For reasons that are outside of the scope of this blog post, I recently had to measure how fast one CPU-core can go through an unsorted list of unsigned 32-bit integers (u32) and output the sorted list of indexes at which the value is within a given interval.

In other words, let's say we get years as an input

[1992, 2018, 1934, 2002, 2022, 1998, 1972, 1996].

Given the interval [1982..2000], we identify that the values within the interval are

[1992, _, _, _, _, 1998, _, 1996]

Our output should therefore be their respective indexes

[0, 5, 7].

In idiomatic rust, such a function could probably look like this

use std::ops::RangeInclusive;

pub fn filter_vec_scalar(
    input: &[u32],
    range: RangeInclusive<u32>,
    output: &mut Vec<u32>)
{
    output.clear();
    output.reserve(input.len());
    output.extend(
        input
            .iter()
            .enumerate()
            .filter(|&(_, el)| range.contains(el))
            .map(|(id, _)| id as u32),
    );
}

This code seems quite trivial. Surely rustc will manage
to vectorize this on its own and this will be a very short blog post, right? Well, not really no.

The generated assembly code is not a fun read (https://godbolt.org/z/x3sK4fvhP), so I won't show it here... but trust me on this. This is just boring scalar code.

On a EC2 c5n.large instance (Intel Xeon Platinum 3 GHz (Skylake 8124)), with 50% elements being retained, this code has a throughput of 170 millions of u32s/secs.

By the end of this blog post, our code will be 20 times faster.

This blog post will show how one can use SIMD instructions to optimize this code
and highlight differences between AVX2 and AVX512.

Branchless

You are eager to jump into SIMD code... I don't blame you. We will get there. As an intermediary step, however, let's see if we can improve this scalar code.

As we have seen in my previous blog post, branch misprediction can really kill CPU performance. If our data is pretty balanced and random, it can still be useful to tweak our code in order to remove branches.

The trick is easy. We will always copy our id at the tail of the output vector, but we will only increment the tail pointer if we actually want to retain this id.
Our code now looks like this.

pub fn filter_vec_nobranch(
    input: &[u32],
    range: RangeInclusive<u32>,
    output: &mut Vec<u32>) {
    output.clear();
    output.resize(input.len(), 0u32);
    let mut output_len = 0;
    for (id, &el) in input.iter().enumerate() {
        output[output_len] = id as u32;
        output_len += if range.contains(&el) { 1 } else { 0 };
    }
    output.truncate(output_len);
}

Note that I resisted the siren's call of using unsafe code here.
It would probably not be that helpful anyway.

Our new code now clocks at 300 millions of u32s/secs.

AVX2

As you probably know, CPUs usually offer special instructions that operate on
several pieces of data all at once. These instructions have been released over the years
in "instruction sets".

An instruction set operates on a specific register with a given bit width. For instance,
SSE2 works on 128-bits registers. Some instructions will treat such a register as 8x16 bits integers,
some instructions will treat this register as 4x32-bits integers, etc.

As a programmer, we usually do not explicitly write assembly. Instead, we call built-in functions called intrinsics. The compiler then takes care of emitting the right assembly instructions on our behalf.
In the following, I will sometimes use the instruction name and sometimes the intrinsics name. Don't worry, I am just trying to confuse you.

AVX2 is a reasonable target for our little problem: nowadays AVX/AVX2 is widely supported across 64bits x86 CPU.
Most x86 Cloud VM will support this instruction set and you can expect everyone's AMD or Intel laptop to handle it.
It operates over 256-bits registers.

Let's hide the gruesome instructions details behind a couple of
well named function, and let's draft the idea behind our SIMD implementation.

// We store 8x32-bits integers in one 256 bits register.
const NUM_LANES: usize = 8;

pub fn filter_vec_avx2(
    input: &[u32],
    range: RangeInclusive<u32>,
    output: &mut Vec<u32>) {
    let mut output_tail = output;
    assert_eq!(input.len() % NUM_LANES, 0);j
    // As we read our input 8 ints at a time, we will store
    // their respective indexes in `ids`.
    let mut ids: __m128i = from_u32s([0, 1, 2, 3, 4, 5, 6, 7]);
    const SHIFT: __m128i = from_u32s([NUM_LANES as u32; NUM_LANES]]);
    for _ in 0..input.len() / 8 {
        // Load 8 ints into our SIMD register.
        let els: __m256i = load_unaligned(input[i * 8..].as_ptr());
        // Identify the elements in the register that we
        // want to keep as 8-bit bitset.
        let keeper_bitset: u8 = compute_filter_bitset(els, range);
        // Compact our elements, putting all of the elements
        // retained on the left.
        let filtered_els: __m256i = compact(els, keeper_bitset);
        // Write all our 8 elements into the output...
        store_unaligned(output_tail, filtered_els);

        let added_len = keeper_bitset.count_ones();
        output_tail = output_tail.offset(added_len);

        idx = op_add(ids, SHIFT);
    }
    let output_len = output_tail.offset_from(output) as usize;
    output.set_len(output_len);
}

Let's unpack this.

Quite expectedly, we use the same trick as in the branchless solution.
At each loop iteration, we load and store one SIMD register worth of data, that is 8-integers.
However, we increment the output_tail pointer depending on the number of retained elements.

We maintain the ids of our current consecutive 8 elements
in a 256-bits register.

We then need a way to

identify the set of values we want to retain, and return that as an 8-bit bitset. We called this operation compute_filter_bitset.
move the values retained by that bitset, and move them to the left of our register. We called that operation compact.

Unfortunately, AVX2 does not offer any obvious ways to implement
compute_filter_mask, nor compact. That's where the funs begins.

SIMD programming really feels like playing lego with a bag of oddly shaped lego bricks.
Intel has a very nice reference website listing the different instructions available.

That's a long list. Let's see if we can filter this list to make it more digestible for us.

While the register can be used as well for floating point operations or integer operations, the intrinsics will refer to the associated datatype as __m256i in integer operations. That's a good keyword for us (irony incoming!).

Compact

Let's start with compact.
AVX2 does not exactly have an instruction for this. In the 128-bits world,
PSHUFB is a powerful instruction that
lets you apply a permutation over the bytes of your register.

That instruction is everyone's most popular toy. Not only is it incredibly versatile, but it also has a throughput of 1 AND a
latency of 1.

Unfortunately, AVX2's grimoire of instructions does not contain such a thing.
The equivalent instruction exists and is called vpshufd, but there is a catch: it only
applies two disjoint permutations within the two 128-bits lanes, which is perfectly useless to us.
This is a very common pattern in AVX2 instructions. Instructions crossing that dreaded 128bit-lane are seldom.
It is a common source of headaches for developers.

Fortunately, applying a permutation over u32s (which is what we need) is actually possible,
via the VPERMPS instruction __mm256_permutevar8x32_epi32.

That instruction has a larger latency than PSHUB (it has a latency of 3), but this did not seem to impact our overall throughput.

Another problem that we have is that it expects a mapping as an input, while what we have in our hands is a bitset.
We need some way to efficiently convert our keeper_bitsets into the mapping our instruction expects.

This is a common problem with a common solution. Our 8-bit bitmask can only take 256 values, so we
can simply precompute this mapping in an array of 256 values and ship it with the code. Converting a bitset into a mapping will then just consist of a lookup.

Our code now looks as follows:


const BITSET_TO_MAPPING: [__m256i] = /* ... */;

#[inline]
unsafe fn compact(data: __m256i, mask: u8) -> DataType {
    let vperm_mask = BITSET_TO_MAPPING[mask as usize];
    _mm256_permutevar8x32_epi32(data, vperm_mask)
}

At this point, we still have to declare our declare const BITSET_TO_MAPPING array of __m256i, but rust does not give us a way to write a literal for it.

Fortunately, @burntsushi (thanks) is sharing the workaround in the rust-lang github issue. The trick is to reinterpret a (non-tagged) union for this.

const fn from_u32x8(vals: [u32; 8]) -> __m256i {
    union U8x32 {
        vector: DataType,
        vals: [u32; __m256i],
    }
    unsafe { U8x32 { vals }.vector }
}

compute_filter_bitset

Compute filter bitset is strangely the one that caused me the most trouble.

In AVX256, it is possible to compare 8 pairs of i32s at a time, using the use _mm256_cmpgt_epi32 intrinsics.

First speed bump: we would have preferred to compare unsigned ints. For my use case, I did not need to support the full range of u32s, so I just added an assert in the code to restrict values to 0..i32::MAX
I believe a common workaround is to flip the most significant bit before the comparison using a xor.
This operation indeed is a monotonic mapping from u32 to i32.

Second speed bump, our operator is actually strictly greater and we would have preferred greater or equal.
I ended up using the negation on the mask to deal with this problem. $$\neg \left(a > b \right) \Leftrightarrow a \leq b$$

The last problem is that the output of the __mm256_cmpgt_epi32 is not a 8 bit mask.
Instead, it leaves us with a __m256 value where all the bits in a given 32 bit lane are 1 if the
left operand was great than the right operand for this given lane.

I could not find an operation to gather a single bit off each lane to form my single byte mask.
I used _mm256_movemask_epi8 to gather the msb of all bytes and then had a few lines of scalar code
to extract my 8-bits mask 32-bits integer off this integer. It was slow and felt lame. Surely there was a better way.

Then I did what every sane engineer should do. I asked Twitter (Ok I am lying a bit, at the time of the tweet I was playing with SSE2).

The tweet unfolds in a magical thread, in which many developers started sharing their tricks.
If you are as old as I am, you might remember the beginning of the internet.
In France, Internet providers were running commercials to let you how the internet -not their service in particular- was awesome. That thread has the same vibes as these commercials.

Eventually, Geoff Langdale jumped in with the perfect answer. The perfect instruction exists. An instruction that extracts the most significant off our 8 x 32 bits lanes and returns a single byte. The instruction is called VMOVMSKPS. I could not find it because it is presented as a floating point instruction to extract the sign of a bunch of 32-bits floats.
Of course, I had not thought of looking into the float intrinsics!

Big shoutout to Geoff. If you read this far, you should probably have a look at his amazing crafty blog in which he discusses CPU optimization and SIMD programming.

Here is our function in the end.

unsafe fn compute_filter_bitset(
    val: __m256i,
    range: RangeInclusive<__m256i>) -> u8 {
    let too_low = op_greater(*range.start(), val);
    let too_high = op_greater(val,*range.end());
    let outside: _m256 = transmute::<_m256i, _m256>(op_or(too_low, too_high));
    255u8 - _mm256_movemask_ps(outside) as u8
}

Putting everything together

use std::arch::x86_64::_mm256_add_epi32 as op_add;
use std::arch::x86_64::_mm256_cmpgt_epi32 as op_greater;
use std::arch::x86_64::_mm256_lddqu_si256 as load_unaligned;
use std::arch::x86_64::_mm256_storeu_si256 as store_unaligned;
use std::arch::x86_64::_mm256_or_si256 as op_or;
use std::arch::x86_64::_mm256_set1_epi32 as set1;
use std::arch::x86_64::_mm256_movemask_ps as extract_msb;
use std::arch::x86_64::_mm256_permutevar8x32_epi32 as permute;
use std::arch::x86_64::{__m256, __m256i};
use std::ops::RangeInclusive;
use std::mem::transmute;

const NUM_LANES: usize = 8;

pub fn filter_vec(
    input: &[u32],
    range: RangeInclusive<u32>,
    output: &mut Vec<u32>) {
    assert_eq!(input.len() % NUM_LANES, 0);
    // We restrict the accepted boundary, because unsigned integers & SIMD don't
    // play well.
    let accepted_range = 0u32..(i32::MAX as u32);
    assert!(accepted_range.contains(range.start()));
    assert!(accepted_range.contains(range.end()));
    output.clear();
    output.reserve(input.len());
    let num_words = input.len() / NUM_LANES;
    unsafe {
        let output_len = filter_vec_avx2_aux(
            input.as_ptr() as *const __m256i,
            range,
            output.as_mut_ptr(),
            num_words,
        );
        output.set_len(output_len);
    }
}

unsafe fn filter_vec_avx2_aux(
    mut input: *const __m256i,
    range: RangeInclusive<u32>,
    output: *mut u32,
    num_words: usize,
) -> usize {
    let mut output_tail = output;
    let range_simd =
        set1(*range.start() as i32)..=set1(*range.end() as i32);
    let mut ids = from_u32x8([0, 1, 2, 3, 4, 5, 6, 7]);
    const SHIFT: __m256i = from_u32x8([NUM_LANES as u32; NUM_LANES]);
    for _ in 0..num_words {
        let word = load_unaligned(input);
        let keeper_bitset = compute_filter_bitset(word, range_simd.clone());
        let added_len = keeper_bitset.count_ones();
        let filtered_doc_ids = compact(ids, keeper_bitset);
        store_unaligned(
            output_tail as *mut __m256i,
            filtered_doc_ids,
        );
        output_tail = output_tail.offset(added_len as isize);
        ids = op_add(ids, SHIFT);
        input = input.offset(1);
    }
    output_tail.offset_from(output) as usize
}

#[inline]
unsafe fn compact(data: __m256i, mask: u8) -> __m256i {
    let vperm_mask = BITSET_TO_MAPPING[mask as usize];
    permute(data, vperm_mask)
}

#[inline]
unsafe fn compute_filter_bitset(
    val: __m256i,
    range: RangeInclusive<__m256i>) -> u8 {
    let too_low = op_greater(*range.start(), val);
    let too_high = op_greater(val,*range.end());
    let outside: __m256 = transmute::<__m256i, __m256>(op_or(too_low, too_high));
    255u8 - extract_msb(outside) as u8
}

const fn from_u32x8(vals: [u32; NUM_LANES]) -> __m256i {
    union U8x32 {
        vector: __m256i,
        vals: [u32; NUM_LANES],
    }
    unsafe { U8x32 { vals }.vector }
}

const BITSET_TO_MAPPING: [__m256i; 256] = [
    from_u32x8([0, 0, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 0, 0, 0, 0, 0, 0, 0]),
    from_u32x8([1, 0, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 0, 0, 0, 0, 0, 0]),
    from_u32x8([2, 0, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 2, 0, 0, 0, 0, 0, 0]),
    from_u32x8([1, 2, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 2, 0, 0, 0, 0, 0]),
    from_u32x8([3, 0, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 3, 0, 0, 0, 0, 0, 0]),
    from_u32x8([1, 3, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 3, 0, 0, 0, 0, 0]),
    from_u32x8([2, 3, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 2, 3, 0, 0, 0, 0, 0]),
    from_u32x8([1, 2, 3, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 2, 3, 0, 0, 0, 0]),
    from_u32x8([4, 0, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 4, 0, 0, 0, 0, 0, 0]),
    from_u32x8([1, 4, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 4, 0, 0, 0, 0, 0]),
    from_u32x8([2, 4, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 2, 4, 0, 0, 0, 0, 0]),
    from_u32x8([1, 2, 4, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 2, 4, 0, 0, 0, 0]),
    from_u32x8([3, 4, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 3, 4, 0, 0, 0, 0, 0]),
    from_u32x8([1, 3, 4, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 3, 4, 0, 0, 0, 0]),
    from_u32x8([2, 3, 4, 0, 0, 0, 0, 0]),
    from_u32x8([0, 2, 3, 4, 0, 0, 0, 0]),
    from_u32x8([1, 2, 3, 4, 0, 0, 0, 0]),
    from_u32x8([0, 1, 2, 3, 4, 0, 0, 0]),
    from_u32x8([5, 0, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 5, 0, 0, 0, 0, 0, 0]),
    from_u32x8([1, 5, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 5, 0, 0, 0, 0, 0]),
    from_u32x8([2, 5, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 2, 5, 0, 0, 0, 0, 0]),
    from_u32x8([1, 2, 5, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 2, 5, 0, 0, 0, 0]),
    from_u32x8([3, 5, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 3, 5, 0, 0, 0, 0, 0]),
    from_u32x8([1, 3, 5, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 3, 5, 0, 0, 0, 0]),
    from_u32x8([2, 3, 5, 0, 0, 0, 0, 0]),
    from_u32x8([0, 2, 3, 5, 0, 0, 0, 0]),
    from_u32x8([1, 2, 3, 5, 0, 0, 0, 0]),
    from_u32x8([0, 1, 2, 3, 5, 0, 0, 0]),
    from_u32x8([4, 5, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 4, 5, 0, 0, 0, 0, 0]),
    from_u32x8([1, 4, 5, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 4, 5, 0, 0, 0, 0]),
    from_u32x8([2, 4, 5, 0, 0, 0, 0, 0]),
    from_u32x8([0, 2, 4, 5, 0, 0, 0, 0]),
    from_u32x8([1, 2, 4, 5, 0, 0, 0, 0]),
    from_u32x8([0, 1, 2, 4, 5, 0, 0, 0]),
    from_u32x8([3, 4, 5, 0, 0, 0, 0, 0]),
    from_u32x8([0, 3, 4, 5, 0, 0, 0, 0]),
    from_u32x8([1, 3, 4, 5, 0, 0, 0, 0]),
    from_u32x8([0, 1, 3, 4, 5, 0, 0, 0]),
    from_u32x8([2, 3, 4, 5, 0, 0, 0, 0]),
    from_u32x8([0, 2, 3, 4, 5, 0, 0, 0]),
    from_u32x8([1, 2, 3, 4, 5, 0, 0, 0]),
    from_u32x8([0, 1, 2, 3, 4, 5, 0, 0]),
    from_u32x8([6, 0, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 6, 0, 0, 0, 0, 0, 0]),
    from_u32x8([1, 6, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 6, 0, 0, 0, 0, 0]),
    from_u32x8([2, 6, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 2, 6, 0, 0, 0, 0, 0]),
    from_u32x8([1, 2, 6, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 2, 6, 0, 0, 0, 0]),
    from_u32x8([3, 6, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 3, 6, 0, 0, 0, 0, 0]),
    from_u32x8([1, 3, 6, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 3, 6, 0, 0, 0, 0]),
    from_u32x8([2, 3, 6, 0, 0, 0, 0, 0]),
    from_u32x8([0, 2, 3, 6, 0, 0, 0, 0]),
    from_u32x8([1, 2, 3, 6, 0, 0, 0, 0]),
    from_u32x8([0, 1, 2, 3, 6, 0, 0, 0]),
    from_u32x8([4, 6, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 4, 6, 0, 0, 0, 0, 0]),
    from_u32x8([1, 4, 6, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 4, 6, 0, 0, 0, 0]),
    from_u32x8([2, 4, 6, 0, 0, 0, 0, 0]),
    from_u32x8([0, 2, 4, 6, 0, 0, 0, 0]),
    from_u32x8([1, 2, 4, 6, 0, 0, 0, 0]),
    from_u32x8([0, 1, 2, 4, 6, 0, 0, 0]),
    from_u32x8([3, 4, 6, 0, 0, 0, 0, 0]),
    from_u32x8([0, 3, 4, 6, 0, 0, 0, 0]),
    from_u32x8([1, 3, 4, 6, 0, 0, 0, 0]),
    from_u32x8([0, 1, 3, 4, 6, 0, 0, 0]),
    from_u32x8([2, 3, 4, 6, 0, 0, 0, 0]),
    from_u32x8([0, 2, 3, 4, 6, 0, 0, 0]),
    from_u32x8([1, 2, 3, 4, 6, 0, 0, 0]),
    from_u32x8([0, 1, 2, 3, 4, 6, 0, 0]),
    from_u32x8([5, 6, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 5, 6, 0, 0, 0, 0, 0]),
    from_u32x8([1, 5, 6, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 5, 6, 0, 0, 0, 0]),
    from_u32x8([2, 5, 6, 0, 0, 0, 0, 0]),
    from_u32x8([0, 2, 5, 6, 0, 0, 0, 0]),
    from_u32x8([1, 2, 5, 6, 0, 0, 0, 0]),
    from_u32x8([0, 1, 2, 5, 6, 0, 0, 0]),
    from_u32x8([3, 5, 6, 0, 0, 0, 0, 0]),
    from_u32x8([0, 3, 5, 6, 0, 0, 0, 0]),
    from_u32x8([1, 3, 5, 6, 0, 0, 0, 0]),
    from_u32x8([0, 1, 3, 5, 6, 0, 0, 0]),
    from_u32x8([2, 3, 5, 6, 0, 0, 0, 0]),
    from_u32x8([0, 2, 3, 5, 6, 0, 0, 0]),
    from_u32x8([1, 2, 3, 5, 6, 0, 0, 0]),
    from_u32x8([0, 1, 2, 3, 5, 6, 0, 0]),
    from_u32x8([4, 5, 6, 0, 0, 0, 0, 0]),
    from_u32x8([0, 4, 5, 6, 0, 0, 0, 0]),
    from_u32x8([1, 4, 5, 6, 0, 0, 0, 0]),
    from_u32x8([0, 1, 4, 5, 6, 0, 0, 0]),
    from_u32x8([2, 4, 5, 6, 0, 0, 0, 0]),
    from_u32x8([0, 2, 4, 5, 6, 0, 0, 0]),
    from_u32x8([1, 2, 4, 5, 6, 0, 0, 0]),
    from_u32x8([0, 1, 2, 4, 5, 6, 0, 0]),
    from_u32x8([3, 4, 5, 6, 0, 0, 0, 0]),
    from_u32x8([0, 3, 4, 5, 6, 0, 0, 0]),
    from_u32x8([1, 3, 4, 5, 6, 0, 0, 0]),
    from_u32x8([0, 1, 3, 4, 5, 6, 0, 0]),
    from_u32x8([2, 3, 4, 5, 6, 0, 0, 0]),
    from_u32x8([0, 2, 3, 4, 5, 6, 0, 0]),
    from_u32x8([1, 2, 3, 4, 5, 6, 0, 0]),
    from_u32x8([0, 1, 2, 3, 4, 5, 6, 0]),
    from_u32x8([7, 0, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 7, 0, 0, 0, 0, 0, 0]),
    from_u32x8([1, 7, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 7, 0, 0, 0, 0, 0]),
    from_u32x8([2, 7, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 2, 7, 0, 0, 0, 0, 0]),
    from_u32x8([1, 2, 7, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 2, 7, 0, 0, 0, 0]),
    from_u32x8([3, 7, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 3, 7, 0, 0, 0, 0, 0]),
    from_u32x8([1, 3, 7, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 3, 7, 0, 0, 0, 0]),
    from_u32x8([2, 3, 7, 0, 0, 0, 0, 0]),
    from_u32x8([0, 2, 3, 7, 0, 0, 0, 0]),
    from_u32x8([1, 2, 3, 7, 0, 0, 0, 0]),
    from_u32x8([0, 1, 2, 3, 7, 0, 0, 0]),
    from_u32x8([4, 7, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 4, 7, 0, 0, 0, 0, 0]),
    from_u32x8([1, 4, 7, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 4, 7, 0, 0, 0, 0]),
    from_u32x8([2, 4, 7, 0, 0, 0, 0, 0]),
    from_u32x8([0, 2, 4, 7, 0, 0, 0, 0]),
    from_u32x8([1, 2, 4, 7, 0, 0, 0, 0]),
    from_u32x8([0, 1, 2, 4, 7, 0, 0, 0]),
    from_u32x8([3, 4, 7, 0, 0, 0, 0, 0]),
    from_u32x8([0, 3, 4, 7, 0, 0, 0, 0]),
    from_u32x8([1, 3, 4, 7, 0, 0, 0, 0]),
    from_u32x8([0, 1, 3, 4, 7, 0, 0, 0]),
    from_u32x8([2, 3, 4, 7, 0, 0, 0, 0]),
    from_u32x8([0, 2, 3, 4, 7, 0, 0, 0]),
    from_u32x8([1, 2, 3, 4, 7, 0, 0, 0]),
    from_u32x8([0, 1, 2, 3, 4, 7, 0, 0]),
    from_u32x8([5, 7, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 5, 7, 0, 0, 0, 0, 0]),
    from_u32x8([1, 5, 7, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 5, 7, 0, 0, 0, 0]),
    from_u32x8([2, 5, 7, 0, 0, 0, 0, 0]),
    from_u32x8([0, 2, 5, 7, 0, 0, 0, 0]),
    from_u32x8([1, 2, 5, 7, 0, 0, 0, 0]),
    from_u32x8([0, 1, 2, 5, 7, 0, 0, 0]),
    from_u32x8([3, 5, 7, 0, 0, 0, 0, 0]),
    from_u32x8([0, 3, 5, 7, 0, 0, 0, 0]),
    from_u32x8([1, 3, 5, 7, 0, 0, 0, 0]),
    from_u32x8([0, 1, 3, 5, 7, 0, 0, 0]),
    from_u32x8([2, 3, 5, 7, 0, 0, 0, 0]),
    from_u32x8([0, 2, 3, 5, 7, 0, 0, 0]),
    from_u32x8([1, 2, 3, 5, 7, 0, 0, 0]),
    from_u32x8([0, 1, 2, 3, 5, 7, 0, 0]),
    from_u32x8([4, 5, 7, 0, 0, 0, 0, 0]),
    from_u32x8([0, 4, 5, 7, 0, 0, 0, 0]),
    from_u32x8([1, 4, 5, 7, 0, 0, 0, 0]),
    from_u32x8([0, 1, 4, 5, 7, 0, 0, 0]),
    from_u32x8([2, 4, 5, 7, 0, 0, 0, 0]),
    from_u32x8([0, 2, 4, 5, 7, 0, 0, 0]),
    from_u32x8([1, 2, 4, 5, 7, 0, 0, 0]),
    from_u32x8([0, 1, 2, 4, 5, 7, 0, 0]),
    from_u32x8([3, 4, 5, 7, 0, 0, 0, 0]),
    from_u32x8([0, 3, 4, 5, 7, 0, 0, 0]),
    from_u32x8([1, 3, 4, 5, 7, 0, 0, 0]),
    from_u32x8([0, 1, 3, 4, 5, 7, 0, 0]),
    from_u32x8([2, 3, 4, 5, 7, 0, 0, 0]),
    from_u32x8([0, 2, 3, 4, 5, 7, 0, 0]),
    from_u32x8([1, 2, 3, 4, 5, 7, 0, 0]),
    from_u32x8([0, 1, 2, 3, 4, 5, 7, 0]),
    from_u32x8([6, 7, 0, 0, 0, 0, 0, 0]),
    from_u32x8([0, 6, 7, 0, 0, 0, 0, 0]),
    from_u32x8([1, 6, 7, 0, 0, 0, 0, 0]),
    from_u32x8([0, 1, 6, 7, 0, 0, 0, 0]),
    from_u32x8([2, 6, 7, 0, 0, 0, 0, 0]),
    from_u32x8([0, 2, 6, 7, 0, 0, 0, 0]),
    from_u32x8([1, 2, 6, 7, 0, 0, 0, 0]),
    from_u32x8([0, 1, 2, 6, 7, 0, 0, 0]),
    from_u32x8([3, 6, 7, 0, 0, 0, 0, 0]),
    from_u32x8([0, 3, 6, 7, 0, 0, 0, 0]),
    from_u32x8([1, 3, 6, 7, 0, 0, 0, 0]),
    from_u32x8([0, 1, 3, 6, 7, 0, 0, 0]),
    from_u32x8([2, 3, 6, 7, 0, 0, 0, 0]),
    from_u32x8([0, 2, 3, 6, 7, 0, 0, 0]),
    from_u32x8([1, 2, 3, 6, 7, 0, 0, 0]),
    from_u32x8([0, 1, 2, 3, 6, 7, 0, 0]),
    from_u32x8([4, 6, 7, 0, 0, 0, 0, 0]),
    from_u32x8([0, 4, 6, 7, 0, 0, 0, 0]),
    from_u32x8([1, 4, 6, 7, 0, 0, 0, 0]),
    from_u32x8([0, 1, 4, 6, 7, 0, 0, 0]),
    from_u32x8([2, 4, 6, 7, 0, 0, 0, 0]),
    from_u32x8([0, 2, 4, 6, 7, 0, 0, 0]),
    from_u32x8([1, 2, 4, 6, 7, 0, 0, 0]),
    from_u32x8([0, 1, 2, 4, 6, 7, 0, 0]),
    from_u32x8([3, 4, 6, 7, 0, 0, 0, 0]),
    from_u32x8([0, 3, 4, 6, 7, 0, 0, 0]),
    from_u32x8([1, 3, 4, 6, 7, 0, 0, 0]),
    from_u32x8([0, 1, 3, 4, 6, 7, 0, 0]),
    from_u32x8([2, 3, 4, 6, 7, 0, 0, 0]),
    from_u32x8([0, 2, 3, 4, 6, 7, 0, 0]),
    from_u32x8([1, 2, 3, 4, 6, 7, 0, 0]),
    from_u32x8([0, 1, 2, 3, 4, 6, 7, 0]),
    from_u32x8([5, 6, 7, 0, 0, 0, 0, 0]),
    from_u32x8([0, 5, 6, 7, 0, 0, 0, 0]),
    from_u32x8([1, 5, 6, 7, 0, 0, 0, 0]),
    from_u32x8([0, 1, 5, 6, 7, 0, 0, 0]),
    from_u32x8([2, 5, 6, 7, 0, 0, 0, 0]),
    from_u32x8([0, 2, 5, 6, 7, 0, 0, 0]),
    from_u32x8([1, 2, 5, 6, 7, 0, 0, 0]),
    from_u32x8([0, 1, 2, 5, 6, 7, 0, 0]),
    from_u32x8([3, 5, 6, 7, 0, 0, 0, 0]),
    from_u32x8([0, 3, 5, 6, 7, 0, 0, 0]),
    from_u32x8([1, 3, 5, 6, 7, 0, 0, 0]),
    from_u32x8([0, 1, 3, 5, 6, 7, 0, 0]),
    from_u32x8([2, 3, 5, 6, 7, 0, 0, 0]),
    from_u32x8([0, 2, 3, 5, 6, 7, 0, 0]),
    from_u32x8([1, 2, 3, 5, 6, 7, 0, 0]),
    from_u32x8([0, 1, 2, 3, 5, 6, 7, 0]),
    from_u32x8([4, 5, 6, 7, 0, 0, 0, 0]),
    from_u32x8([0, 4, 5, 6, 7, 0, 0, 0]),
    from_u32x8([1, 4, 5, 6, 7, 0, 0, 0]),
    from_u32x8([0, 1, 4, 5, 6, 7, 0, 0]),
    from_u32x8([2, 4, 5, 6, 7, 0, 0, 0]),
    from_u32x8([0, 2, 4, 5, 6, 7, 0, 0]),
    from_u32x8([1, 2, 4, 5, 6, 7, 0, 0]),
    from_u32x8([0, 1, 2, 4, 5, 6, 7, 0]),
    from_u32x8([3, 4, 5, 6, 7, 0, 0, 0]),
    from_u32x8([0, 3, 4, 5, 6, 7, 0, 0]),
    from_u32x8([1, 3, 4, 5, 6, 7, 0, 0]),
    from_u32x8([0, 1, 3, 4, 5, 6, 7, 0]),
    from_u32x8([2, 3, 4, 5, 6, 7, 0, 0]),
    from_u32x8([0, 2, 3, 4, 5, 6, 7, 0]),
    from_u32x8([1, 2, 3, 4, 5, 6, 7, 0]),
    from_u32x8([0, 1, 2, 3, 4, 5, 6, 7]),
];

Our AVX2 code clocks at 3.65 billions of elements per second.
Sweet. This is actually 8 times faster than the branchless scalar solution.

AVX-512 to the rescue

Recent Intel CPUs and the upcoming AMD Zen 4 CPUs handle a new instruction set
called AVX-512. It operates over 16 x 32-bits integers at a time.

But AVX-512 is not just about doubling the number of lanes to play with!
It adds a lot of new instructions to make our life easier.

For instance, _mm512_cmple_epi32_mask is an intrinsics that compares the 16 x 32 bits integers
of two __m512i. The output is now exactly what we expected: it's a 16-bit bitset.

What about compression, and our ugly map? AVX-512 comes with an instruction (the intrinsics is called _mm512_mask_compressstoreu_epi32) that does exactly what we want!

use std::arch::x86_64::_mm512_add_epi32 as op_add;
use std::arch::x86_64::_mm512_cmple_epi32_mask as op_less_or_equal;
use std::arch::x86_64::_mm512_loadu_epi32 as load_unaligned;
use std::arch::x86_64::_mm512_set1_epi32 as set1;
use std::arch::x86_64::_mm512_mask_compressstoreu_epi32 as compress;
use std::arch::x86_64::__m512i;
use std::ops::RangeInclusive;

const NUM_LANES: usize = 16;

pub fn filter_vec(input: &[u32], range: RangeInclusive<u32>, output: &mut Vec<u32>) {
    assert_eq!(input.len() % NUM_LANES, 0);
    // We restrict the accepted boundary, because unsigned integers & SIMD don't
    // play well.
    let accepted_range = 0u32..(i32::MAX as u32);
    assert!(accepted_range.contains(range.start()));
    assert!(accepted_range.contains(range.end()));
    output.clear();
    output.reserve(input.len());
    let num_words = input.len() / NUM_LANES;
    unsafe {
        let output_len = filter_vec_aux(
            input.as_ptr(),
            range,
            output.as_mut_ptr(),
            num_words,
        );
        output.set_len(output_len);
    }
}

pub unsafe fn filter_vec_aux(
    mut input: *const u32,
    range: RangeInclusive<u32>,
    output: *mut u32,
    num_words: usize,
) -> usize {
    let mut output_end = output;
    let range_simd =
        set1(*range.start() as i32)..=set1(*range.end() as i32);
    let mut ids = from_u32x16([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]);
    const SHIFT: __m512i = from_u32x16([NUM_LANES as u32; NUM_LANES]);
    for _ in 0..num_words {
        let word = load_unaligned(input as *const i32);
        let keeper_bitset = compute_filter_bitset(word, range_simd.clone());
        compress(output_end as *mut u8, keeper_bitset, ids);
        let added_len = keeper_bitset.count_ones();
        output_end = output_end.offset(added_len as isize);
        ids = op_add(ids, SHIFT);
        input = input.offset(1);
    }
    output_end.offset_from(output) as usize
}

#[inline]
unsafe fn compute_filter_bitset(
    val: __m512i,
    range: RangeInclusive<__m512i>) -> u16 {
    let low = op_less_or_equal(*range.start(), val);
    let high = op_less_or_equal(val, *range.end());
    low & high
}

const fn from_u32x16(vals: [u32; NUM_LANES]) -> __m512i {
    union U8x64 {
        vector: __m512i,
        vals: [u32; NUM_LANES],
    }
    unsafe { U8x64 { vals }.vector }
}

This version is considerably simpler and now runs at 8.6 billions of integers per second.

Conclusion

AVX512 is really sucking the fun out of SIMD programming.
My code ended up being both considerably simpler and faster.

Thank you everyone for reading the blog post! It was originally written by our co-founder, Paul Masurel

Top 5 Open-Source Log Shippers (alternatives to Logstash) in 2022

Max Kray — Wed, 17 Aug 2022 11:30:00 +0000

This is a list of the top 5 open-source log shippers to fit your needs.

Many of these can be considered as “Logstash alternatives” in different ways. For those of you who don’t know it yet, Logstash is highly popular among DevOps for the possibility of ingesting data from different sources, dynamic data transformation, and much more.

However, it might not be the right choice for everyone. If you are looking for open-source alternatives and to choose what’s best for you - this guide is here to help you.

Here is the quick list:

Logstash
Vector
Filebeat
FluentD
Promtail

For each log shipper, I also took some of the core criteria, like number of plugins and configuration difficulty, and you can find the full comparison table at the end of this blog post.

Logstash

The issue with Logstash

Let’s start with the king of log collectors. If you know about Logstash, feel free to scroll lower for other options.

As commonly known, Logstash is part of the famous ELK stack and acts as a workhorse in it. It is used to collect, parse, and ship your logs. However, due to its high workload, it shows low figures in performance tests (see ref.1 below) compared to other, more lightweight options.

As noted in the blog post by Logz.io, one of the reasons for low performance is that Logstash requires JVM to run, this dependency causes significant memory consumption. This is especially true when you have many data pipelines and advanced filtering. That is one of the reasons why Filebeat was created, and I will discuss more on that later on, however feel free to dive into the blog post by Logz.io, which compares Filebeat and Logstash in detail.

As for the performance comparison of Logstash vs others, Vector has an insightful benchmark TCP To Blackhole Performance Test (ref.1) that compares Vector, Logstash, FluentD, and FluentBit.



$ bin/compare -t tcp_to_blackhole_performance

| Metric          | fluentbit | fluentd   | logstash  | vector    |
|:----------------|:----------|:----------|:----------|:----------|
| IO Thrpt (avg)  | 64.4MiB/s | 27.7MiB/s | 40.6MiB/s | 86MiB/s W |
| CPU sys (max)   | 4         | 3.5 W     | 6.1       | 6.5       |
| CPU usr (max)   | 53.2      | 50.8 W    | 91.5      | 96.5      |
| Load 1m (avg)   | 0.5 W     | 0.8       | 1.8       | 1.7       |
| Mem used (max)  | 614.8MiB  | 294MiB    | 742.5MiB  | 181MiB W  |
| Disk read (sum) | 9MiB      | 2.6MiB W  | 2.6MiB    | 2.6MiB    |
| Disk writ (sum) | 14.8MiB   | 13.7MiB   | 11.6MiB   | 11MiB W   |
| Net recv (sum)  | 3.9gib    | 1.7gib    | 2.4gib    | 5.1gib W  |
| Net send (sum)  | 7.9MiB    | 5.7MiB    | 2.6MiB    | 9MiB      |
| TCP estab (avg) | 663       | 664       | 665       | 664       |
| TCP sync (avg)  | 0         | 0         | 0         | 0         |
| TCP close (avg) | 1         | 2         | 7         | 4         |
-------------------------------------------------------------------------------------------------------------
W = winner
fluentbit = 1.1.0
fluentd = 3.3.0-1
logstash = 7.0.1
vector = 0.2.0-6-g434bed8

Reference 1, TCP to Blackhole Performance Test, Source: Vector Repo

Logstash Pros & Cons

Here is a list of pros & cons for Logstash (in comparison to other log shippers in this guide):

Pros	Cons
Input plugins: Many	Configuration difficulty: High
Output plugins: Many	Resource-usage: High
Configuration capabilities: High	Documentation: Complex
Community activity: High (68 PRs over the last month)

Vector

Vector is a tool used to collect, transform, and route all your logs and metrics. It was created by TimberIO in 2019, and acquired by Datadog in 2021.

Even though Vector is an end-to-end agent & aggregator, it can still be used as a log shipper/collector, and with its impressive benchmarks, it could become a significant tool in your stack.

The great part about Vector is that it is written in Rust, which is known for its performance, memory safety, and is designed for high-intensity work. Vector also provides distributed, centralized, and stream-based deployment.

To compare Vector based on features with other log shippers, the Vector repo has a good side-by-side comparison (reference 2 below) with Beats, Fluentbit, FluentD, Logstash, Splunk UF, and Splunk HF, which I added below for the reference.

Reference 2, Vector’s Features, Source: Vector Repo

The previously discussed benchmark especially caught my eye and it's a great foundation to compare Vector's performance against other log shippers. In short, Vector wins Logstash, FluentD, and Fluentbit in IO Thrpt (avg), Mem used (max), Disk writ (sum), and Net recv (sum) in TCP to Blackhole test.

Vector Pros & Cons

Here is a list of pros & cons for Vector (in comparison to other log shippers in this guide):

Pros	Cons
Resource-usage: Low	Input plugins: Fewer
Configuration difficulty: Low	Output plugins: Fewer
Configuration capabilities: High
Documentation: Simple
Community activity: High (220 PRs over the last month)

Filebeat

Another option is Filebeat. This one was created with a goal in mind to be a lightweight alternative to Logstash, if you don’t need advanced tuning. Even though you can use both Logstash and Filebeat, you do have an option to send your logs directly with Filebeat to your centralized logging platform. As you get more familiar or require additional features, you can always connect Logstash later on to your process.

If you want to collect logs on remote machines, Filebeat is a great option. And if you don’t need to make transformations to your data then you are free to send it straight to Elasticsearch! But more often than not, if you need more than just timestamp and message fields, you will need Logstash.

Overall, it is a much simpler option compared to Logstash. This makes it more reliable for new users, as you have less gears and handles to spin.

For scaling Filebeat, most likely than not you would still require Logstash in your stack. However, in this case, it is important to have a well-designed / architectured cluster.

For your stack, you might not only use Filebeat. This is especially useful if you are considering scaling. Below is a representation of what your process might look like at scale with Beats, Logstash, Elasticsearch, and Kibana.

Source: Elastic.co, Guide on Deploying and Scaling Logstash

Filebeat Pros & Cons

Here is a list of pros & cons for Filebeat (in comparison to other log shippers in this guide):

Pros	Cons
Resource-usage: Low	Input plugins: Fewer
Configuration difficulty: Low	Output plugins: Fewer
Documentation: Simple	Configuration capabilities: Low
Community activity: High (220 PRs over the last month)

FluentD

This one was built with the idea in mind to structure data in JSON as much as possible. FluentD claims that this method allows for a Unified Logging Layer (in other words, unifying logging infrastructure).

Due to a vast number of plugins, FluentD is a great choice for those that have data from different or unique sources.

Fluentbit is also an option to consider if you are looking for something that fits more small devices & distributed systems. Just like FluentBit, it was created by Treasure Data, but later on in 2015. There is a Side by Side comparison of FluentD and Fluentbit by Logz.io, which I advise you to check out.

There is an insightful article with multiple tests comparing FluentD and FluentBit, one of which is Forwarding 5,000 1KB events per second, which resulted in 80% CPU and 120MB Memory for FluentD, but 27% CPU and 26MB Memory for FluentBit.

However, when comparing FluentD to other log shippers in this guide, it performs quite well.

FluentD Pros & Cons

Here is a list of pros & cons for FluentD (in comparison to other log shippers in this guide):

Pros	Cons
Resource-usage: Low	Configuration difficulty: High
Input plugins: Many	Community activity: Low (6 PRs over the last month)
Output plugins: Many	Documentation: Complex
Configuration capabilities: High

Promtail

For those that know Loki, you have probably heard of Promtail. Its use case is specifically tailored to Loki, and it can collect logs both locally and for Kubernetes pods.

As for comparison, you could refer to an article by CrashLaker, which compares Loki vs ELK vs Splunk. On top of it, there is also an insightful Medium article by Ronen Schaffer, which analyses Promtail including write path performance, read path performance, and much more.

Promtail Pros & Cons

Here is a list of pros & cons for Promtail (in comparison to other log shippers in this guide):

Pros	Cons
Resource-usage: Low	Input plugins: Fewer
Configuration difficulty: Low	Output plugins: Fewer
Documentation: Simple	Configuration capabilities: Low
	Community activity: Low (people wait for months to receive a reply and only 8 PRs over the last month)

Conclusion

Let’s conclude with a comparison table that includes all of the above mentioned log shippers:

	Logstash	Vector	Filebeat	FluentD	Promtail
Resource-usage	High	Low	Low	Medium	Low
Input plugins	High	Fewer	Fewer	Fewer	Little
Output plugins	Many	Fewer	Fewer	Many	Fewer
Configuration capabilities	High	High	Low	High	Low
Configuration difficulty	High	Low	Low	High	Low
Documentation	Complex	Simple	Simple	Complex	Simple
Community activity	High	High	High	Low	Low

I hope this guide helped you to analyse just the surface of features for top log shippers, as to see which solution you should explore further and add to your stack.

Let me know if you have any questions about any of the tools, I will see the comment and reply asap! Thanks for reading.

Quickwit 0.3 is released! An Open-Source Log Management alternative to Elasticsearch

Max Kray — Tue, 31 May 2022 00:00:00 +0000

Hey, everyone!

We just released Quickwit 0.3 and we are excited to share it with Dev.to community.

At Quickwit, we aim to provide developers with the cost-efficient software for log management. Even when it comes to petabytes of logs. Quickwit achieves that through decoupled compute & storage, where logs are stored on an object storage instead of local hardware. There is many more features we have added over the 2 years, so feel free to check them out to see if Quickwit fits your user-case.

But for now, we will dive deeper into Quickwit 0.3.

Five months have passed since our last release, and our team has been working hard to deliver the next version of Quickwit. This new feature-rich version introduces:

An embedded UI
Schemaless indexing
Aggregations (Elasticsearch-compatible API)
Ingest API (Elasticsearch-compatible)
Support for Amazon Kinesis

For readers in a hurry, we suggest you go through our revised quick start guide to try 0.3 out now!

If you’re still reading, let’s go through the new functionalities brought by Quickwit 0.3 in greater detail.

Embedded UI

For advanced dashboarding and data exploration, our long-term plan is to offer a data source plugin for Grafana. However, we also wanted to provide our users with an out-of-the-box solution to search and visualize their logs without installing and configuring another third-party software.

We developed this front-end application using Typescript with React, and the interface consists of two sections: Discover and Admin.

Discover

The discover section is dedicated to searching and exploring indexes. This page consists of an index selection panel on the left, a search box and a date range picker at the top, and a data table at the center to inspect matching documents. We are not trying to reinvent the wheel here, and this layout should feel very familiar: select an index, type your query, hit the run button (or use the shortcut cmd/ctrl + enter), and matching hits magically appear a few milliseconds later.

Admin

The admin section is dedicated to administration tasks. The indexes page lists and displays the properties (doc mapping, sources, splits) of the indexes managed by Quickwit. The cluster page lists and shows the properties of each node comprising a cluster. We will enrich this section with additional information and increase the number of functionalities (update or delete an index, stop a node) available for use in the coming releases.

Schemaless indexing

In the wild, many events cannot be mapped to a strict schema. For instance, in structured logging, each line describes an event in the application, and some JSON fields are present in all log lines (e.g. server, timestamp, event_type). However, some of the JSON fields are specific to the event type and are often subject to change.

Quickwit 0.3 makes it possible to define a strict schema for the former and handle the latter in a schemaless manner.

You can read more about how this works in our schemaless guide.

Let your data tell a story with aggregation queries

Aggregations summarize your data as metrics or statistics and help answer questions such as:

How many errors occurred in the last hour?
What was the average response latency per service in the previous 15 minutes?

With the addition of aggregations, Quickwit isn’t exclusively for search anymore; it’s now a powerful analytics engine that lets you unlock the hidden value of your business data.

The aggregations API is Elasticsearch-search compatible and documented here.

Two new ways to ingest data with Quickwit

Quickwit 0.3 delivers two new ways to load data into indexes:

Ingest API
Amazon Kinesis

Ingest API

Quickwit 0.3 ships with a new HTTP endpoint for ingesting newline-delimited JSON documents in batches:

POST api/v1/<index ID>/ingest
{"timestamp": 1653068019, "message": "Hello, World!"}
{"timestamp": 1653068020, "message": "Bonjour, monde!"}

We take data durability seriously, and records are persisted into a write-ahead log (WAL) before acknowledging any write request.

Elasticsearch-compatible bulk endpoint

Furthermore, we added an Elasticsearch-compatible bulk endpoint enabling log shippers such as FluentD, Logstash, or Vector to support Quickwit natively. As a result, you can start shipping logs to Quickwit today simply by updating one line in your current log collector configuration!

This tutorial provides an example of how to use Vector to ship logs to Quickwit.

Support for Amazon Kinesis

After Apache Kafka, Quickwit 0.3 supports a second distributed message queue: Amazon Kinesis. Amazon Kinesis is a fully managed service that offers an alternative to companies that may not have the in-house knowledge, or resources, to manage and operate a Kafka cluster.

Discover how to ingest data from Amazon Kinesis in this tutorial.

With this new release, there are now four ways to load data into Quickwit:

Ingest API
Amazon Kinesis
Apache Kafka
Files

Better under the hood

In addition to packing a lot of user-facing features, Quickwit is also getting better under the hood. This release features performance improvements, notably in the doc mapper (the class responsible for parsing raw JSON objects into Tantivy documents). Additionally, we switched our cluster membership algorithm from SWIM to Scuttlebutt, which we described extensively in this blog post.

What’s next?

While you’re enjoying the value delivered by Quickwit 0.3, we are already focused on the next release. Key features that you can expect are:

Native support for Kubernetes
Datetime field
IP address field
Range queries
Sort
Retention policies

We plan to deliver the next version in August. Our roadmap is public, and you can follow our progress in this GitHub project.

In the meantime, we invite you to check out this quick start guide to ingest your first dataset with Quickwit.

Finally, if you have any questions regarding Quickwit or encounter any issues, feel free to start a discussion or open an issue on GitHub or contact us directly on Discord.

How to investigate memory usage of your rust program

Max Kray — Fri, 18 Mar 2022 00:00:00 +0000

Hallo everyone, Pascal is here, a software engineer at Quickwit.

At Quickwit we have a mindset to create memory efficient and fast software, something that resonates with me personally. I love to create fast software and optimize it, since
it has a really satisfying feedback cycle.

Memory consumption can easily become a problem, when indexing and merging data due to the large data volume being processed.
In my opinion, occasionally measuring your application is indispensable to get valuable insights.

Target audience of this blogpost are people who are interested in software optimization. Some rust and search engine knowledge may be beneficial to follow some parts, but is not strictly required.

Heaptrack

heaptrack is a nice utility to visualize memory consumption on a timescale, and it is dead-easy to use.
It only tracks heap-allocations though. It also ships with debian. If you have a recent enough distro, install it with:

sudo apt-get install heaptrack

So let's install and run quickwit to index our data and see what heaptrack can tell us about our memory consumption.
The dataset is a 16GB hdfs log with the following hdfs_index_config.yaml.

version: 0 # File format version.

index_id: "hdfs"

doc_mapping:
  field_mappings:
    - name: timestamp
      type: i64
      fast: true
    - name: severity_text
      type: text
      tokenizer: raw
    - name: body
      type: text
      tokenizer: default
      record: position
    - name: resource
      type: object
      field_mappings:
        - name: service
          type: text
          tokenizer: raw
  tag_fields: ["resource.service"]

indexing_settings:
  timestamp_field: timestamp

search_settings:
  default_search_fields: [severity_text, body]


quickwit index create --index-config ./hdfs_index_config.yaml --config=quickwit_config.json

cat hdfs-log.json | heaptrack quickwit index ingest --index hdfs --config=quickwit_config.json

heaptrack --analyze heaptrack.quickwit.2109522.gz

600MB max heap memory consumption for 16Gb data, that looks pretty good, right? Even my raspberry pi could index this.

Fair enough, but what is this ugly peak, and can we maybe like remove it?

Let's try to investigate. heaptrack comes bundled with another tool heaptrack_print, that generates a summary of the profile.

heaptrack_print heaptrack.quickwit.2109522.gz



PEAK MEMORY CONSUMERS
528.00MB peak memory consumed over 686242304 calls from
0x56135a16f5c4
  in /home/pascal/.cargo/bin/quickwit
402.65MB consumed over 69 calls from:
    alloc::raw_vec::RawVec$LT$T$C$A$GT$::reserve::do_reserve_and_handle::h2b5cd3c6459cd557
      in /home/pascal/.cargo/bin/quickwit
    _$LT$alloc..vec..Vec$LT$T$GT$$u20$as$u20$alloc..vec
    ..spec_from_iter..SpecFromIter$LT$T$C$I$GT$$GT$::from_iter::h5fe32505140f85a0
      in /home/pascal/.cargo/bin/quickwit
    tantivy::indexer::merger::IndexMerger::write::hf2f8719e6428e59e
      in /home/pascal/.cargo/bin/quickwit
    tantivy::indexer::segment_updater::merge::hd71502b462dbb343
      in /home/pascal/.cargo/bin/quickwit
    _$LT$core..future..from_generator..GenFuture$LT$T$GT$$u20$as$u20$core
    ..future..future..Future$GT$::poll::hd6e25d15cec97c4f
      in /home/pascal/.cargo/bin/quickwit
    futures_executor::thread_pool::PoolState::work::h98556dbe39869ced
      in /home/pascal/.cargo/bin/quickwit
    std::sys_common::backtrace::__rust_begin_short_backtrace::h54c13adaa4af2bc9
      in /home/pascal/.cargo/bin/quickwit
    core::ops::function::FnOnce::call_once$u7b$$u7b$vtable.shim$u7d$$u7d$::hd16673a142e56ed8
      in /home/pascal/.cargo/bin/quickwit
    _$LT$alloc..boxed..Box$LT$F$C$A$GT$$u20$as$u20$core..ops..function
    ..FnOnce$LT$Args$GT$$GT$::call_once::h59eef3b9c8a82350
      at /rustc/73422130ee96c09e7214c876a3600ac1f32aa8c8/library/alloc/src/boxed.rs:1638
      in /home/pascal/.cargo/bin/quickwit
    _$LT$alloc..boxed..Box$LT$F$C$A$GT$$u20$as$u20$core..ops..function
    ..FnOnce$LT$Args$GT$$GT$::call_once::hb5bbe017c347469c
      at /rustc/73422130ee96c09e7214c876a3600ac1f32aa8c8/library/alloc/src/boxed.rs:1638
    std::sys::unix::thread::Thread::new::thread_start::h62931528f61e35f5
      at library/std/src/sys/unix/thread.rs:106
    start_thread
      in /lib/x86_64-linux-gnu/libpthread.so.0
    __clone
      in /lib/x86_64-linux-gnu/libc.so.6

In the snippet above we can see a potential culprit (402.65MB consumed over 69 calls).
But looking at the stacktrace: It ends at IndexMerger::write. This is the toplevel entry function to the merging section in tantivy. Thanks for nothing I guess, investigation finished.

Well ok, not so fast, the reason the stacktrace is incomplete is likely due to inlining. In the final binary the function does simply not exists because its content is moved into the parent function,
so it cannot be traced.
So what happens if we would tell the compiler not to inline any function called by the merge function? Actually we can and it's really simple with #[inline(never)]!

When inlining code prefer to use #[inline] and use #[inline(always)] only when you are really sure (backed by benchmarks). The compiler does a pretty good job on inlining most of the time, and when #[inline(always)] is applied on the wrong level
it may mess up the compilers inline heuristics, so that some functions may not be inlined anymore.

This time let's use the gui, because it allows drill downs.

So here finally we have the culprit, consumer of memory, destroyer of flat memory profiles: get_doc_id_from_concatenated_data. Who made this?

Turns out it was me! (classic)
This function is part of index-sorting introduced in tantivy v0.15. A more detailed introduction is part of the tantivy repo.

As a short summary: An index in tantivy can be sorted by a field. During the merge of segments, the sorting is applied. The sorting is applied via a SegmentDocIdMapping that is basically a list of Vec<(Old Docid, New Segment)>, where index is the new Docid.

SegmentDocIdMapping is causing the memory consumption.
Looking at the code there are 3 things we can do:

Reduce space used by the elements in the vec of SegmentDocIdMapping
Avoid oversizing the vec
Use an enum to not create the mapping in the not sort case

Reduce space used by the elements in the doc id mapping

Let's have a look at the SegmentDocIdMapping, which is generated by get_doc_id_from_concatenated_data.
Currently we consume 16 bytes per entry (DocId 4bytes, SegmentReader 8bytes, SegmentOrdinal 4bytes).
But SegmentReader is actually just a convenience accessor and could be replaced by always using ordinal. That saves us 8 bytes per element!

/// Struct to provide mapping from new doc_id to old doc_id and segment.
#[derive(Clone)]
pub(crate) struct SegmentDocIdMapping<'a> {
    new_doc_id_to_old_and_segment: Vec<(DocId, SegmentReaderWithOrdinal<'a>)>,
    is_trivial: bool,
}

#[derive(Clone, Copy)]
pub(crate) struct SegmentReaderWithOrdinal<'a> {
    pub reader: &'a SegmentReader,
    pub ordinal: SegmentOrdinal,
}

/// Struct to provide mapping from new doc_id to old doc_id and segment.
#[derive(Clone)]
pub(crate) struct SegmentDocIdMapping {
    new_doc_id_to_old_and_segment: Vec<(DocId, SegmentOrdinal)>,
    is_trivial: bool,
}

SegmentOrdinal is 4bytes wide, but we will hardly have the need to address 4_294_967_296 segments right? 2bytes should do it, which sets the max segments we can merge at once to 65536.
Now if you expect that we've saved another 2bytes, that is not the case.
Due to struct padding the struct will still consume 8bytes.

Actually rust provides something for that case via alignment modifiers. But there is a real downside, padding is added for performance reasons (and sometimes correctness).
Accessing a u32 on a 2 bytes boundary is unaligned memory access something that the cpu isn't optimized for! Now we are entering the very
interesting realm of trading memory for performance. As we are already infinitely fast and consume basically no memory, it is hard to decide what to optimize for? (minor exaggeration here :))

A qualified answer can only be provided by benchmarking. SegmentOrdinal in the mapping is used extensively in the merge, so let's postpone this and see where we are now and what optimization we can apply without any trade-off.

The compiler adds paddings to structs, so that the biggest element is aligned to its boundaries.
That also means there may be free space in your struct.
E.g. having u64 in a struct means the compiler will add padding so that the u64 can be 8-byte aligned.
(memory alignment rules are a little more complex and simplified here.)

Well this looks great already! We are down to 360MB peak heap consumption.

Avoid oversizing the vec

Currently when creating the SegmentDocIdMapping, we simply collect into a vec. Vectors double in size when they reallocate.
After doubling, we can expect to only use 50% on average of that newly allocated space.
Let me calculate this on my ridiculous oversized calculator I always carry with me (due to lack of image, I'll leave this up to your imagination): In total that means we waste 25% space on average.

There are cases where rust reserves enough space when using collect() via the SpecExtend specialization. But this requires us to implement size_hint and TrustedLen on our doc_ids_alive Iterator. TrustedLen is nightly currently, so we will take the conservative approach of reserving space on the vec ourselves.

let mapping: Vec<_> = self
    .readers
    .iter()
    .enumerate()
    .map(|(reader_ordinal, reader)| {
        reader
            .doc_ids_alive()
            .map(move |doc_id| (doc_id, reader_ordinal as SegmentOrdinal))
    })
    .flatten()
    .collect();
Ok(SegmentDocIdMapping::new(mapping, true))

let total_num_new_docs = self
    .readers
    .iter()
    .map(|reader| reader.num_docs() as usize)
    .sum();

let mut mapping = Vec::with_capacity(total_num_new_docs);

mapping.extend(
    self.readers
        .iter()
        .enumerate()
        .map(|(reader_ordinal, reader)| {
            reader
                .doc_ids_alive()
                .map(move |doc_id| (doc_id, reader_ordinal as SegmentOrdinal))
        })
        .flatten(),
);
Ok(SegmentDocIdMapping::new(mapping, true))

Now, the merge doesn't add overhead compared to regular indexing in this scenario. This is great.
I will stop here and continue optimizing offline, because continuing here feels more like:

I hope you found these insights of a typical workflow in optimizing memory consumption interesting.
Make sure to like our beautiful, open-sourced, distributed and cost-effective search engine on github.

Feel free to join our community in discord where you can follow our development and participate.