Enhance Decoding Performance

[malvidin]

I am having performance issues decoding large inputs (>10KB). The issue may be with bs58-rs, not this project.

function	decode 1M (seconds)	decode 256B, timeit 5k (seconds)
gmpy2.mpz(data, base=58)	0.0387	0.0472
recursive_base58_decode(data)	0.256	0.508
based58.b58decode(data)	21.6	0.251
base58.b58decode(data)	86.4	1.13

I don't know if there is a base58 project that uses rug or similar for better large integer performance.

[kevinheavey]

Thanks for raising. This library is a very thin wrapper around bs58-rs so I'm not sure if there's anything that can be done on our side, but I'll leave this open in case anyone has any ideas

[malvidin]

This nested loop is the upstream issue: https://github.com/Nullus157/bs58-rs/blob/pr%C4%ABmum/src/decode.rs#L307

for byte in &mut output[..index] {
    val += (*byte as usize) * 58;
    *byte = (val & 0xFF) as u8;
    val >>= 8;
}

Using rug or num_bigint would almost certainly be better. rug has an unsafe method, assign_bytes_radix_unchecked(), and num_bigint has from_radix_be(). I expect assign_bytes_radix_unchecked() would be faster for very large inputs, but I don't know what additional input cleaning of the input would be required.

let translated_input = vec![1u8, 1, 1];
let b58_biguint = BigUint::from_radix_be(&translated_input, 58).unwrap();
let decoded_vec = b58_biguint.to_bytes_be();
assert_eq!(decoded_vec, "\r_".as_bytes());

Cleaning the input once, using BigUint, and moving the data back into the output appears to significantly faster for the 256_bytes/decode_bs58 benchmark.