Fastest Gematria calculator

Question

Gematria is an ancient Jewish method to determine a numeric value of a letter sequence, using a fixed value for each letter. Gematria is originally applied to Hebrew letters, but for the context of this challenge, we'll use Latin script instead. There are many ways to implement Gematria in Latin script, but let's define it as a close as it can be to the original standard encoding. The numbering goes as such:

A = 1, B = 2, C = 3, D = 4, E = 5, F = 6, G = 7, H = 8, I = 9, J = 10, K = 20, L = 30, M = 40, N = 50, O = 60, P = 70, Q = 80, R = 90, S = 100, T = 200, U = 300, V = 400, W = 500, X = 600, Y = 700, Z = 800.

Your job is to calculate the Gematria value for each character of a string, sum the result and print it or return it.

Rules

• Lowercase and uppercase letters yield the same value. Anything else equals 0. You can assume the input encoding will always be ASCII.
• You can input the file in whatever method you see fit, be it loading it from a file, piping it in the terminal or baking it into the source code.
• You can use any method you see fit in order to make this go fast, except const evaluation of the input's value and baking that into the binary or a similar method. That would be way too easy. The calculation must happen locally on runtime.

And here's a naïve implementation in Rust to provide an example implementation:

#![feature(exclusive_range_pattern)]
fn char_to_number(mut letter: char) -> u32 {
    // map to lowercase as casing doesn't matter in Gematria
    letter = letter.to_ascii_lowercase();
    // get numerical value relative to 'a', mod 9 and plus 1 because a = 1, not 0.
    // overflow doesn't matter here because all valid ranges ahead have valid values 
    let num_value = ((letter as u32).overflowing_sub('a' as u32).0) % 9 + 1;
    // map according to the Gematria skip rule
    match letter.to_ascii_lowercase() {
        'a'..'j' => num_value, // simply its value: 1, 2, 3...
        'j'..'s' => num_value * 10, // in jumps of 10: 10, 20, 30...
        's'..='z' => num_value * 100, // in jumps of 100: 100, 200, 300...
        _ => 0 // anything else has no value
    }
}

fn gematria(word: &str) -> u64 {
    word
        .chars()
        .map(char_to_number)
        .map(|it| it as u64) // convert to a bigger type before summing
        .sum()
}

In order to measure speed, each implementation will be fed the exact same file: a random 100MB text file from Github: https://github.com/awhipp/100mb-daily-random-text/releases/tag/v20221005

The speed of my implementation, measured with Measure-Command, completes in ~573ms and yields the number 9140634224. I compiled using -O 3 and baked the input text into the source code, and then ran the code on an Intel i5-10400 CPU.

Answer 1

Rust, ≈ 10 ms

Compile with cargo build --release, run with target/release/gematria random-20221005.txt.

Cargo.toml

[package]
name = "gematria"
version = "0.1.0"
edition = "2021"

[dependencies]
memmap = "0.7.0"
rayon = "1.5.3"

src/main.rs

use core::arch::x86_64::*;
use memmap::MmapOptions;
use rayon::prelude::*;
use std::env::args;
use std::fs::File;
use std::io;

fn gematria(bytes: &[u8]) -> u64 {
    let (prefix, vecs, suffix) = unsafe { bytes.align_to::<__m256i>() };

    let (mut sum0, mut sum10, mut sum19) = vecs
        .par_chunks(2048)
        .map(|chunk| unsafe {
            let splat32 = _mm256_set1_epi8(32);
            let splat123 = _mm256_set1_epi8(123);
            let splat229 = _mm256_set1_epi8(-27);
            let splat0 = _mm256_set1_epi8(0);
            let splat10 = _mm256_set1_epi8(10);
            let splat19 = _mm256_set1_epi8(19);

            let mut sum0 = splat0;
            let mut sum10 = splat0;
            let mut sum19 = splat0;

            for &vec in chunk {
                let x = _mm256_subs_epu8(
                    _mm256_sub_epi8(_mm256_or_si256(vec, splat32), splat123),
                    splat229,
                );
                sum0 = _mm256_add_epi64(sum0, _mm256_sad_epu8(x, splat0));
                sum10 = _mm256_add_epi64(sum10, _mm256_sad_epu8(x, splat10));
                sum19 = _mm256_add_epi64(sum19, _mm256_sad_epu8(x, splat19));
            }

            (
                (_mm256_extract_epi64(sum0, 0)
                    + _mm256_extract_epi64(sum0, 1)
                    + _mm256_extract_epi64(sum0, 2)
                    + _mm256_extract_epi64(sum0, 3)) as u64,
                (_mm256_extract_epi64(sum10, 0)
                    + _mm256_extract_epi64(sum10, 1)
                    + _mm256_extract_epi64(sum10, 2)
                    + _mm256_extract_epi64(sum10, 3)) as u64,
                (_mm256_extract_epi64(sum19, 0)
                    + _mm256_extract_epi64(sum19, 1)
                    + _mm256_extract_epi64(sum19, 2)
                    + _mm256_extract_epi64(sum19, 3)) as u64,
            )
        })
        .reduce(
            || (0, 0, 0),
            |(a0, a10, a19), (b0, b10, b19)| (a0 + b0, a10 + b10, a19 + b19),
        );

    for affix in [prefix, suffix] {
        for &byte in affix {
            let x = (byte | 32).wrapping_sub(123).saturating_sub(229);
            sum0 += x as u64;
            sum10 += x.abs_diff(10) as u64;
            sum19 += x.abs_diff(19) as u64;
        }
    }

    (101 * sum0 + 9 * sum10) / 2 + 45 * sum19 - 900 * bytes.len() as u64
}

fn main() -> io::Result<()> {
    let [_, filename]: [String; 2] = Vec::from_iter(args()).try_into().expect("missing filename");
    let file = File::open(filename)?;
    let mmap = unsafe { MmapOptions::new().map(&file)? };
    println!("{}", gematria(&mmap[..]));
    Ok(())
}

Answer 2

C++ (clang), ~21 ms on my Linux machine

#include <array>
#include <chrono>
#include <fcntl.h>
#include <iostream>
#include <numeric>
#include <thread>
#include <vector>
#include <unistd.h>

constexpr std::array<unsigned long, 128> numbering {
    // ASCII NUL to @
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
    // A to Z
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60,
    70, 80, 90, 100, 200, 300, 400, 500, 600, 700, 800,
    // [ \ ] ^ _ `
    0, 0, 0, 0, 0, 0,
    // a to z
    1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60,
    70, 80, 90, 100, 200, 300, 400, 500, 600, 700, 800,
    // all the rest up to 127
    0, 0, 0, 0, 0
};

struct accumulate_block
{
    void operator()(const char* first, const char* last, std::vector<unsigned long>::reference result) {
        result = 0;
        for (const char* str = first; str < last; ++str)
            result += numbering[*str];
    }
};

int main() {
    const auto start = std::chrono::high_resolution_clock::now();
    
    auto fd = open("random-20221005.txt", O_RDONLY);
    posix_fadvise(fd, 0, 0, 1);

    constexpr std::size_t buffer_size = 4 * 1024 * 1024;
    constexpr unsigned long num_threads = 8;
    constexpr unsigned long min_per_thread = buffer_size / num_threads;
    std::vector<unsigned long> results(num_threads);
    std::vector<std::thread> threads(num_threads - 1);
    char buffer[buffer_size];

    unsigned long count = 0;
    while (const std::size_t bytes_read = read(fd, buffer, buffer_size)) {
        const char* block_start = buffer;
        unsigned long const block_size = bytes_read / num_threads;
        for(unsigned long i = 0; i < num_threads - 1; ++i) {
            const char* block_end = block_start + block_size;
            threads[i] = std::thread(accumulate_block(), block_start, block_end, std::ref(results[i]));
            block_start = block_end;
        }
        accumulate_block()(block_start, buffer + bytes_read, results[num_threads - 1]);
        for(auto& entry: threads) {
            entry.join();
        }
        count = std::accumulate(results.begin() , results.end(), count);
    }

    const auto finish = std::chrono::high_resolution_clock::now();

    constexpr unsigned long expected = 9140634224L;
    const char* checker[] = {"\xE2\x9C\x95", "\xE2\x9C\x93"};
    std::cout << "count = " << count << " " << checker[count == expected] << "\n";

    const auto ms_interval = std::chrono::duration_cast<std::chrono::milliseconds>(finish - start);
    const std::chrono::duration<double, std::milli> ms_double = finish - start;
    std::cout << ms_interval.count() << " ms\n";
    std::cout << ms_double.count() << " ms\n";

    return 0;
}

Outputs:

count = 9140634224 ✓
21 ms
21.8556 ms   

Compiled with clang++ \$14.0.0\$ using -O3 -march=native -std=gnu++20

Answer 3

C# (.NET Core 6), ~60 ms on my Windows machine

var sw = new System.Diagnostics.Stopwatch();
sw.Start();
var data = File.ReadAllBytes("random-20221005.txt");
sw.Stop();
var readTime = sw.ElapsedMilliseconds;

sw.Restart();
var list = new List<long>();
long taskCount = 16;
long taskSize = data.Length / taskCount;
for (long i = 0; i < taskCount; i++)
    list.Add(i * taskSize);

long grandTotal = 0;
Parallel.ForEach(list, start =>
{
    var lookup = new long[] {
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 300, 400, 500, 600, 700, 800,
        0, 0, 0, 0, 0, 0,
        1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 200, 300, 400, 500, 600, 700, 800,
        0, 0, 0, 0, 0
    };
    long total = 0;
    long end = start + taskSize;
    for (long i = start; i < end; i++)
        total += lookup[data[i]];
    grandTotal += total;
});

sw.Stop();
var calcTime = sw.ElapsedMilliseconds;

Console.WriteLine($"read time: {readTime} ms");
Console.WriteLine($"calc time: {calcTime} ms");
Console.WriteLine($"total time: {readTime + calcTime} ms");
Console.WriteLine($"result: {grandTotal}");

Output:

read time: 48 ms
calc time: 12 ms
total time: 60 ms
result: 9140634224

Ouput without parallelization:

read time: 48 ms
calc time: 64 ms
total time: 112 ms
result: 9140634224

Answer 4

Julia 1.0, 140 bytes

!x=sum(getindex.((Dict(Char.([1:255...]).=>[zeros(Int,64)...,1:9...,10:10:90...,100:100:800...,zeros(Int,165)...]),),collect(uppercase(x))))

Try it online!

Answer 5

Python (multithreaded + numpy + numba) <30ms total

windows i7-8750H windows laptop, imdisk ramdisk

import numpy as np
from numba import jit
import os
from concurrent.futures import ThreadPoolExecutor

@jit(nogil=True, fastmath=True)
def counter(full_dict, bytearr):
    total = 0
    for i in bytearr:
        total += full_dict[i]
    return total
_ = counter(np.zeros((128,), dtype=np.int32), b'abc') #to compile

def final_fast_gematria(filename, chunksize=600000, max_threads=4):
    maindict = {65: 1, 66: 2, 67: 3, 68: 4, 69: 5, 70: 6, 71: 7, 72: 8, 73: 9, 74: 10, \
                75: 20, 76: 30, 77: 40, 78: 50, 79: 60, 80: 70, 81: 80, 82: 90, 83: 100, \
                84: 200, 85: 300, 86: 400, 87: 500, 88: 600, 89: 700, 90: 800}
    full_dict = {**{i:0 for i in range(128)}, **maindict, **{key+32:val for key,val in maindict.items()}}
    full_dict = np.array(tuple(full_dict.values()), dtype=np.int32)    
    threads = []
    with ThreadPoolExecutor(max_workers=max_threads) as executor:
        with open(filename, 'rb', 0) as f:
            filesize = os.fstat(f.fileno()).st_size
            for _ in range(filesize//chunksize - 1):
                threads.append(executor.submit(counter, full_dict, f.read(chunksize)))
            return counter(full_dict, f.read()) + sum(thread.result() for thread in threads)

---

print(final_fast_gematria("E:/random-20221005.txt"))

---

9140634224

---

%%timeit -n 2 -r 10
final_fast_gematria("E:/random-20221005.txt")

---

27.9 ms ± 1.11 ms per loop (mean ± std. dev. of 10 runs, 2 loops each)

---

Read time

def only_read(filename, chunksize=600000):
with open(filename, 'rb', chunksize) as f:
    filesize = os.fstat(f.fileno()).st_size
    for _ in range(1 + filesize//chunksize):
        f.read(600000)

---

%%timeit -n 1 -r 10
only_read("E:/random-20221005.txt")

---

22.6 ms ± 985 µs per loop (mean ± std. dev. of 10 runs, 1 loop each)

notebook with other variants link