lev-rs 0.6.0

An extremely fast Levenshtein distance and similarity ratio, also available for Python.
Documentation 
1
2
3
4
5
6
7
8
9
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
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
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104

//! Kernels scheduled for Arm Neoverse cores (Graviton, Ampere, Azure Cobalt,
//! and the N2 behind GitHub's AArch64 runners).  They use only the baseline
//! AArch64 ISA and differ from [`super::apple`] in two latencies: on
//! Neoverse N1/N2/V1/V2 a logical op with a shifted operand takes one cycle
//! (two on Apple cores) and a two-register `extr` three (one on Apple).
//!
//! Both kernels are plain Rust, compiled and tested on every target.  Where
//! LLVM would undo the schedule, a value passes through [`opaque`], which
//! only hides it from the optimizer on AArch64 and is the identity
//! elsewhere.

use crate::kernels::{delta, EDGE_ROW0};

/// `x`, opaque to LLVM on AArch64: an empty `asm!` stops it from fusing
/// the ops on either side into a form that is slower on Neoverse.
#[inline(always)]
fn opaque(x: u64) -> u64 {
    #[cfg(target_arch = "aarch64")]
    {
        let mut x = x;
        // SAFETY: an empty template; the register is passed through.
        unsafe {
            std::arch::asm!(
                "/* {0} */",
                inout(reg) x,
                options(pure, nomem, nostack, preserves_flags),
            );
        }
        x
    }
    #[cfg(not(target_arch = "aarch64"))]
    x
}

/// [`crate::kernels::portable::myers_step`] scheduled for Arm Neoverse cores.
///
/// Uses the identities `!ph_s = (X << 1) & !(vn << 1)` and
/// `!(xv | ph_s) = (X << 1) & !(xv | (vn << 1))` with `X = sum | vp | eq`
/// (from PR #221), removing the `| 1` constant off the critical recurrence
/// path.  On Neoverse N1/N2/V1/V2, logical ops with a shifted operand take
/// one cycle, allowing `m = xv | (vn << 1)`, `s = xs & !(vn << 1)`, and
/// `vp' = (mh << 1) | a` to execute as single-cycle shifted instructions
/// (`orr ..., lsl #1` and `bic ..., lsl #1`).
#[cfg_attr(
    not(all(target_arch = "aarch64", not(target_vendor = "apple"))),
    allow(dead_code)
)]
#[inline(always)]
pub(crate) fn myers_step(eq: u64, vp: u64, vn: u64) -> (u64, u64) {
    let sum = (eq & vp).wrapping_add(vp);
    let x = sum | vp | eq;
    let mh = vp & (eq | !sum);
    let xv = eq | vn;
    let m = xv | (vn << 1);
    let xs = x << 1;
    let s = xs & !(vn << 1);
    let a = xs & !m;
    ((mh << 1) | a, xv & !s)
}

/// [`crate::kernels::multiword`] in the short-chain step of
/// [`crate::kernels::portable::myers_step`], with the bits shifted in at the
/// bottom of a word kept as 0/1 values.  LLVM turns `ph << 1 | below >> 63`
/// into a funnel shift (`extr`, 3 cycles on Neoverse, on the chain of every
/// word but the first); with the shifted-out bits made [`opaque`] it is a
/// 1-cycle `lsr` off the chain and one `orr` with a shifted operand on it.
/// `mh_s` is opaque as well, so that `vp'` is one `orn` rather than an
/// `mvn` and an `orr` with `mh << 1` folded in.  That takes the chain of a
/// word from `vp` to `vp` from 11-12 cycles (portable form) to 7, for about
/// the same number of ops.
#[cfg_attr(
    not(all(target_arch = "aarch64", not(target_vendor = "apple"))),
    allow(dead_code)
)]
#[inline(always)]
pub(crate) fn multiword<const W: usize, I: Iterator<Item = [u64; W]>>(
    m: usize,
    pm_iter: I,
    mut edges: Option<&mut [u8]>,
) -> isize {
    let mut vp = [!0u64; W];
    let mut vn = [0u64; W];
    for (j, pm_row) in pm_iter.enumerate() {
        let e = edges.as_ref().map_or(EDGE_ROW0, |e| e[j]);
        let mut carry = e & 1 != 0;
        let (mut below_ph, mut below_mh) = ((e >> 1 & 1) as u64, (e >> 2) as u64);
        for k in 0..W {
            let (eq, v_p, v_n) = (pm_row[k], vp[k], vn[k]);
            let (sum, nc) = (eq & v_p).carrying_add(v_p, carry);
            carry = nc;
            let ph = v_n | !(sum | (v_p | eq));
            let mh = v_p & (eq | !sum);
            let xv = eq | v_n;
            let ph_s = ph << 1 | below_ph;
            vp[k] = opaque(mh << 1 | below_mh) | !(xv | ph_s);
            vn[k] = ph_s & xv;
            (below_ph, below_mh) = (opaque(ph >> 63), opaque(mh >> 63));
        }
        if let Some(e) = edges.as_deref_mut() {
            e[j] = carry as u8 | (below_ph as u8) << 1 | (below_mh as u8) << 2;
        }
    }
    delta(vp, vn, m)
}