DEV Community: Roman

Reversing sort order in Rust

Roman — Tue, 21 Nov 2023 08:19:13 +0000

Rust allows sort items by key easily with .sort_by_key, here is example, it will put important notes to the end:

#[derive(Debug)]
struct Note {
    important: bool,
    title: &'static str,
}
let mut notes = vec![
    Note { important: false, title: "ddd"},
    Note { important: true, title: "aaa"},
    Note { important: false, title: "ccc"},
];
notes.sort_by_key(|k| k.important);
println!("{:?}", notes);

But reversing order of sorting with key may be not so obvious, it is achieved with Reverse helper struct, here is how it can be applied to above example, in order to put important notes first:

use std::cmp::Reverse;
// ...
notes.sort_by_key(|k| Reverse(k.important));
println!("{:?}", notes);

How is it implemented? Let's look at the source code of Rust standard library:

pub struct Reverse<T>(pub T);

impl<T: Ord> Ord for Reverse<T> {
    fn cmp(&self, other: &Reverse<T>) -> Ordering {
        other.0.cmp(&self.0)
    }
}

The implementation is straightforward, it is newtype wrapper for original type, and for types with Ord trait it reimplements Ord but instead of comparing self with other it comparing other with self meaning it will reverse order in the result. Simple and beautiful!

And it will play nicely with complex keys too, lets put important notes first, and sort by title ascending for same importance groups:

notes.sort_by_key(|k| (Reverse(k.important), k.title));
println!("{:?}", notes);

Of course in some cases it is possible to just negate value, like in this example using !k.important will produce same results, but negating is not always possible (eg. strings). Regarding performance I've benchmarked both methods and have not found any difference, both methods require same time if ordering booleans.

My links

I'm making my perfect todo, note-taking app Heaplist, you can try it here heaplist.app
I have a twitter @rsk
And a website rsk

Compact `match` in Rust

Roman — Sun, 17 Sep 2023 14:42:15 +0000

match often used to work with enums, let's look at this example:

enum NextStep {
    TurnLeft,
    TurnRight
}

fn main() {
    let next_step = NextStep::TurnLeft;
    match next_step {
        NextStep::TurnLeft => println!("turn left"),
        NextStep::TurnRight => println!("turn right"),
    }
}

It may not be obvious, but enums in Rust can be brought into the current namespace, allowing for more compact code:

// ...
    use NextStep::*;
    match next_step {
        TurnLeft => println!("turn left"),
        TurnRight => println!("turn right"),
    }
// ...

And, to limit the effect to just match, you will have to set boundaries using {} for an additional scope:

// ...
    {
        use NextStep::*;
        match next_step {
            // ...
        }
    }
// ...

My links

I'm making my perfect todo, note-taking app Heaplist, you can try it here heaplist.app
And I have a twitter @rsk

A useful anti-pattern in Rust

Roman — Wed, 12 Jul 2023 07:00:00 +0000

There is newtype idiom often used in Rust, which gives more control over the data being processed.

Let's imagine a function that works with a list of users, but only if they are administrators, then instead of just passing an array of identifiers, it can be wrapped into newtype to make sure the data is correct:

struct Admins(Vec<u128>);

Now it is possible to use this type:

fn print_admin_count(users: Admins) {
    println!("admins count: {}", users.0.len());
}

This works, but it doesn't look as nice as if array was used directly users.len().

There are traits in Rust Deref/DerefMut that solve this problem, if we implement them for the wrapper type, then this will allow to work with the inner type directly:

impl Deref for Admins{
    //...
}

fn print_admin_count(users: Admins) {
    println!("admins count: {}", users.len());
}

Full snippet

The documentation warns that these traits should be used only for smart pointers, although wider usage becomes more and more popular.

My links

I'm making my perfect todo, note-taking app Heaplist, you can try it here heaplist.app
And I have a twitter @rsk

Rust transpose method

Roman — Mon, 10 Jul 2023 16:18:45 +0000

Rust has a transpose method, sometimes useful, works especially well with anyhow:

use std::str::FromStr;
use anyhow::Context;

fn add(a: Option<&str>, b: Option<&str>) -> anyhow::Result<f32> {
    let a = a.map(f32::from_str).transpose()?.context("not a value")?;
    let b = b.map(f32::from_str).transpose()?.context("not a value")?;
    Ok(a + b)
}

fn main() {
    println!("{:?}", add(Some("12"), Some("1.2")));
    println!("{:?}", add(Some("a"), Some("1.2")));
    println!("{:?}", add(None, Some("1.2")));
}

output:

Ok(13.2)
Err(invalid float literal)
Err(not a value)

My links

I'm making my perfect todo, note-taking app Heaplist, you can try it here heaplist.app
And I have a twitter @rsk

Optimization of u128 decoding from base62

Roman — Fri, 30 Jun 2023 21:19:47 +0000

In the previous article, we looked at u128 to base62 encoding, now we will implement and optimize the inverse operation of decoding u128 from base62, this can be useful, for example, for more compact storage in memory or database.

In order to understand which optimizations can be applied, let's start with a simple, naive implementation:

const BASE62_N: usize = 62;

pub fn base62_to_u128_naive(base62_str: &str) -> Option<u128> {
    let base62_str: [u8; 22] = base62_str.as_bytes().try_into().ok()?;
    let mut n: u128 = 0;
    for digit in &base62_str {
        let number = match digit {
            d if (b'0'..=b'9').contains(d) => d - 48,
            d if (b'A'..=b'Z').contains(d) => d - 55,
            d if (b'a'..=b'z').contains(d) => d - 61,
            _ => return None,
        };
        n = n
            .checked_mul(BASE62_N as u128)
            .and_then(|n| n.checked_add(number as u128))?;
    }
    Some(n)
}

Let's analyze what is happening here, the function signature shows that we accept a string and get an optional u128 number as a result, since in case of incorrect data in the string we will not be able to decode it:

fn base62_to_u128_naive(base62_str: &str) -> Option<u128>

All identifiers must be 22 characters long, confirm this condition:

let base62_str: [u8; 22] = base62_str.as_bytes().try_into().ok()?;

Next, we calculate the value of the number in a loop from the digits of the base62 string:

for digit in &base62_str

We need to convert each digit to decimal, for example "B" would be "11" in decimal, we do this in match, checking each of the possible intervals of allowed characters:

let number = match digit

Now we calculate the number by multiplying by the base 62 and adding the next digit. A 22-character number in base 62 holds more numbers than a 128-bit number, so we need to check for overflow when converting:

n = n.checked_mul(BASE62_N as u128).and_then(|n| n.checked_add(number as u128))?;

We got the result, returning:

Some(n)

Let's look at the benchmark results, what the first version of the function is capable of (CPU i5-4690):

bench_base62_to_u128_naive 1000000: 0.121s 125.75Mib/s, 8240895.48/s

Not bad, the speed is already a little bit faster than the speed of even the optimized encoder from the first article. All due to the fact that there are no expensive division operations during decoding, but we can do better!

Let's start with optimization. We will start by getting rid of match. Instead of checking the intervals and subtracting the offset, we can create an array with all possible variants, the byte representation of the character from the base62 string will be the offset (index), and the value is a digit in decimal:

const BASE62_MAP: [u8; 123] = [
    255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
    255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
    255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 255, 255, 255,
    255, 255, 255, 255, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28,
    29, 30, 31, 32, 33, 34, 35, 255, 255, 255, 255, 255, 255, 36, 37, 38, 39, 40, 41, 42, 43, 44,
    45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61,
];

Now, for conversion, it is enough to take the value by index, for example, BASE62_MAP[b'A'] will be 10.

The next step is to deal with multiplication and addition in a loop. These overflow-checked operations (checked variants) require more instructions than normal unchecked operations. Since overflow is only possible at the last step, we can move its check outside the loop by converting only the first 21 characters in the loop, and the last one after the loop:

for digit in &base62_str[..21] {
        // ...
        n = n * BASE62_N as u128 + number as u128;
}

Another problem here is that the multiplication itself (as well as addition) of 128-bit numbers is more expensive than, for example, multiplying 64-bit numbers, which is easy to see by looking at the generated assembler for both of these operations. In the previous article, we replaced 128-bit division with 64-bit division, but here we will do the same for multiplication and addition. To do this, we will split the original base62 number into several blocks along the digit boundaries, convert each block separately, then collect the entire number from these parts:

3322222222221111111111 -> 33 2222222222 1111111111
                          n3         n2         n1
n = n3 * 62^20 + n2 * 62^10 + n1

So the final optimized version of the decoder, which we got, looks like this:

const BASE62_N: usize = 62;
const BASE62_POW_10: u128 = (BASE62_N as u128).pow(10);
const BASE62_POW_20: u128 = (BASE62_N as u128).pow(20);
const BASE62_MAP: [u8; 123] = [
    255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
    255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
    255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 255, 255, 255,
    255, 255, 255, 255, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28,
    29, 30, 31, 32, 33, 34, 35, 255, 255, 255, 255, 255, 255, 36, 37, 38, 39, 40, 41, 42, 43, 44,
    45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61,
];

pub fn base62_to_u128(base62_str: &str) -> Option<u128> {
    let base62_str: [u8; 22] = base62_str.as_bytes().try_into().ok()?;
    let mut n_section: u64 = 0;
    for digit in &base62_str[12..22] {
        let number = *BASE62_MAP.get(*digit as usize).filter(|it| **it <= 61)?;
        n_section = n_section * BASE62_N as u64 + number as u64;
    }
    let mut n = n_section as u128;
    n_section = 0;
    for digit in &base62_str[2..12] {
        let number = *BASE62_MAP.get(*digit as usize).filter(|it| **it <= 61)?;
        n_section = n_section * BASE62_N as u64 + number as u64;
    }
    n += n_section as u128 * BASE62_POW_10;
    n_section = 0;
    for digit in &base62_str[0..2] {
        let number = *BASE62_MAP.get(*digit as usize).filter(|it| **it <= 61)?;
        n_section = n_section * BASE62_N as u64 + number as u64;
    }
    n.checked_add((n_section as u128).checked_mul(BASE62_POW_20)?)
}

Some clarifications for the code. Here we calculate a number based on blocks of digits (less significant digits at the end of a string):

for digit in &base62_str[12..22]
// ...
for digit in &base62_str[2..12]
// ...
for digit in &base62_str[0..2]
// ..

This line converts a base 62 digit to a decimal number. At the same time, since the data may be incorrect, a check is added that digit is in the allowed range:

let number = *BASE62_MAP.get(*digit as usize).filter(|it| **it <= 61)?;

We make sure that the top 2 digits do not cause overflow:

n.checked_add((n_section as u128).checked_mul(BASE62_POW_20)?)

Let's check the benchmark, was it worth our efforts?

bench_base62_to_u128 10000000: 0.182s 836.24Mib/s, 54803747.40/s

Wow that's impressive! I even had to increase the number of iterations by a factor of 10 to get stable measurements. As a result, the improvement compared to the original version is 6.65 times.

My links

I'm making my perfect todo, note-taking app Heaplist, you can try it here heaplist.app
And I have a twitter @rsk

Optimization of u128 to base62 encoding

Roman — Mon, 26 Jun 2023 17:33:47 +0000

While working on my note-taking application Heaplist, when I got to saving data to the database, I started using uuid4 identifiers to identify records, which usually look something like this when represented as a string:

32dca18531a1435480461f99837a5b1d

For some reasons, I didn't really like using uuid:

it is a rather long string of 32 characters, and I will need to show it to users sometimes
6 bits in uuid4 are not used, they are constants, wasteful

constant bits in uuid4:

uuid.uuid4().bytes[6] & 0b11110000 #   == 64
uuid.uuid4().bytes[8] & 0b11000000 #   == 128

I decided to explore other options. Guid implementations like ulid, ksuid have some popularity. But they did not suit me either, mainly due to the fact that they include a timestamp.

My choice is completely random 128-bit identifiers, which I encode to a base62 string. Why base62? They contain only letters and numbers, so they can be selected by double-clicking (and, for example, base64 is not). Identifiers have become shorter, now they are 22-character strings, for example:

4xT8QKx8f3BwZP06VKSEMy

But there is a problem! Encoding to a number system that is not a power of two is a rather slow process, due to the fact that it is involves the division operation. For decoding (base62 to u128) there is no such problem, since there will be no division, only multiplication and addition.

So, first let's try the naive encoder implementation written in Rust:

const BASE62_N: usize = 62;
const BASE62_DIGITS: &[u8; BASE62_N] =
    b"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
// how many base62 numbers do we need to store u128?
// you can calculate this number like this, python: math.ceil(math.log(2**128, 62))
const U128_BASE62_ENCODED_LEN: usize = 22;

pub fn u128_to_base62_naive(mut n: u128) -> String {
    // padding occurs from lower digits to higher ones, unfilled high digits will remain zero
    let mut b62_str = vec![b'0'; U128_BASE62_ENCODED_LEN];
    let mut i = U128_BASE62_ENCODED_LEN;
    while n > 0 {
        i -= 1;
        let digit_index = (n % BASE62_N as u128) as usize;
        b62_str[i] = BASE62_DIGITS[digit_index];
        n /= BASE62_N as u128;
    }
    // the variable is guaranteed to contain a valid utf-8 string, there is no need to additionally check it
    unsafe { String::from_utf8_unchecked(b62_str) }
}

In fact, this is a conversion from a decimal number system to a number system with base 62. To do this, we divide the original number by a new base into which we translate, the remainder of the division is the next digit in the new number system, we divide the quotient again, and so on in a cycle .

Let's look at the speed of the algorithm, the benchmark result is (i5-4690 3.50GHz): bench_u128_to_base62_naive 1000000: 32.86Mib/s, 2153250.28/s

Sad numbers, right? For comparison, base64 encoder works at 309.35Mib/s, hex encoder 645.34Mib/s.

Why is that? Since 62 is not a power of two, for conversion we have to re-divide the entire 128-bit number on each cycle, each bit of the original number affects each subsequent digit of the result. Let's look at the assembler generated by the Rust compiler godbolt, here you can see that two functions are used for division:

__umodti3
__udivti3

These are the functions implemented in runtime (llvm) for division of 128-bit numbers (designations "u" - unsigned, "ti" - 128 bit). And of course they will be relatively slow.

We need to simplify work for the processor. As you know, any number in the base BASE can be represented as: HIGH * BASE^R + LOW, for example decimal 1111222 = 1111 * 10^3 + 222, what does this give us? We divide both parts by 10^3 by integer division, we get 1111 = 1111, the remainder of the division will be 222 = 222, so this representation allows us, when converting between bases, to divide not the whole number but only its part. As you probably already guessed, we will replace the division of 128-bit numbers with the division of 64-bit numbers.

So, first we need to choose the power to which we will raise 62, the optimal one will be R, under which the condition 62^R <= 2^64 < 62^(R+1) is satisfied, it can be calculated by the formula:

math.floor(math.log(2**64, 62)) #   == 10

Now let's write a new implementation in Rust, it looks like this:

const BASE62_N: usize = 62;
const BASE62_DIGITS: &[u8; BASE62_N] =
    b"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const U128_BASE62_ENCODED_LEN: usize = 22;
const BASE62_POW_10: u128 = (BASE62_N as u128).pow(10);

pub fn u128_to_base62(mut n: u128) -> String {
    let mut b62_str = vec![b'0'; U128_BASE62_ENCODED_LEN];
    // `nlow` will generate the lower 10 digits in base62
    let mut nlow = (n % BASE62_POW_10) as u64;
    let mut i = U128_BASE62_ENCODED_LEN;
    // convert number in three steps:
    //   0000000000001111111111
    // + 0022222222220000000000
    // + 3300000000000000000000
    // = 3322222222221111111111
    for _ in 0..2 {
        // here is the same algorithm for converting a number to a new base, but now using 64-bit division
        for _ in 0..10 {
            i -= 1;
            let digit_index = (nlow % BASE62_N as u64) as usize;
            b62_str[i] = BASE62_DIGITS[digit_index];
            nlow /= BASE62_N as u64;
        }
        // move on to the next block of digits
        n /= BASE62_POW_10;
        nlow = (n % BASE62_POW_10) as u64;
    }
    // finish by converting the 2 remaining digits
    for _ in 0..2 {
        i -= 1;
        let digit_index = (nlow % BASE62_N as u64) as usize;
        b62_str[i] = BASE62_DIGITS[digit_index];
        nlow /= BASE62_N as u64;
    }
    unsafe { String::from_utf8_unchecked(b62_str) }
}

Let's look at the result assembler godbolt, now, the div instruction is used for 64-bit division. And in optimized build it will be replaced by multiplication and shifts.

As a result it was __umodti3 x 22, __udivti3 x 22, became __umodti3 x 3, __udivti3 x 2, div x 44. This is what the benchmark shows: bench_u128_to_base62 1000000: 112.18Mib/s, 7351959.26/s. Speed up by 3.5 times!

Ready.

and yes, I've tried to replace the u64 division with the u32 division, there was no significant increase in performance, it was about 2% faster

My links

I'm making my perfect todo, note-taking app Heaplist, you can try it here heaplist.app
And I have a twitter @rsk