Potential performance benefits of using BigInt?

[Juraj-Masiar]

Hello,
I've been using this library for creating custom base93 string, but the performance was pretty bad for my 200KB inputs.
So I've tried to optimize it a bit manually, and then used modern AI to further improve it (actually, completely rewrite it for my usecase).

For inspiration, this is what I'm using now, including performance comparison:

/**
 * This is a replacement for the 'base-x' library.
 * It's been almost fully generated by AI (Sonnet Thinking 3.7).
 * Using BigInt and bitwise operations, we achieved:
 * Firefox encode: 12530ms vs 4278ms =  2.93x
 * Chrome encode:   6649ms vs 2377ms =  2.80x
 * Firefox decode:  8364ms vs 5408ms =  1.55x
 */

export class BaseX {
  readonly #base = BigInt(this.alphabet.length);

  constructor(readonly alphabet: string) {

  }

  encode(buffer: Uint8Array): string {
    if (buffer.length === 0) return '';
    // Convert buffer to BigInt efficiently using bitwise operations
    let value = 0n;
    for (let i = 0; i < buffer.length; i++) {
      value = (value << 8n) | BigInt(buffer[i]);
    }
    // Convert to baseX string efficiently using array
    const digits: string[] = [];
    if (value === 0n) return this.alphabet[0];
    while (value > 0n) {
      const remainder = Number(value % this.#base);
      digits.push(this.alphabet[remainder]);
      value /= this.#base;
    }
    return digits.reverse().join('');
  }

  decode(data: string): Uint8Array {
    if (data.length === 0) return new Uint8Array(0);
    // Convert the baseX string to a BigInt value
    let value = 0n;
    for (let i = 0; i < data.length; i++) {
      const digit = this.alphabet.indexOf(data[i]);
      if (digit === -1) {
        throw new Error(`Invalid character at position ${i}: ${data[i]}`);
      }
      value = value * this.#base + BigInt(digit);
    }
    // If value is 0, return a single-byte buffer with value 0
    if (value === 0n) {
      return new Uint8Array([0]);
    }
    // Determine buffer size efficiently by counting bytes
    let temp = value;
    let byteLength = 0;
    while (temp > 0n) {
      temp >>= 8n;
      byteLength++;
    }
    // Create buffer and fill it from right to left
    const buffer = new Uint8Array(byteLength);
    for (let i = byteLength - 1; i >= 0; i--) {
      buffer[i] = Number(value & 0xffn);
      value >>= 8n;
    }
    return buffer;
  }
}

[Juraj-Masiar]

Hello again,
It's been a year and AI made a huge progress as you may know.
The solution above works great, but I've noticed it will fail in Firefox for inputs bigger than 128KB due to "RangeError: BigInt is too large to allocate":
https://bugzilla.mozilla.org/show_bug.cgi?id=2026541

So I started to play with it again, and with the modern AI agents, I've decided to try to ask for a faster solution, since I know one could use FFT for much faster base conversion, but I didn't know how, though I hoped AI will know... and it does.

It created this code, which seems to pass my tests and the speed is insane!
I can't believe it's even possible. It can process 200KB input in 0.1s instead of half a minute.

Sadly, Firefox still won't process more than 128KB due to some hardcoded limit.

/**
 * This is a replacement for the 'base-x' library and upgraded BaseX library.
 * It's been fully generated by AI (Gemini 3.1 Pro).
 * The BaseX was already ~3 times faster, so what we see here is madness!
 * The performance comparison with already upgraded BaseX library:
 * 200KB input => 34s VS 0.132s (encode) and 15s VS 0.043s (decode)
 * Real world test:
 * compression base93: 80042 time: 3,260ms  (old)
 * compression base93: 80042 time:   421ms  (new)
 * unzip and decode    80042 time: 2,802ms  (old)
 * unzip and decode    80042 time:   298ms  (new)
 */

export class BaseX {
  readonly #base: bigint;
  readonly alphabet: string;

  constructor(alphabet: string) {
    this.alphabet = alphabet;
    this.#base = BigInt(alphabet.length);
  }

  encode(buffer: Uint8Array<ArrayBuffer>): string {
    if (buffer.length === 0) return '';
    // Fast bytes to BigInt via hex string
    const hex: string[] = [];
    for (let i = 0; i < buffer.length; i++) {
      hex.push(buffer[i].toString(16).padStart(2, '0'));
    }
    const value = BigInt('0x' + (hex.join('') || '0'));

    if (value === 0n) return this.alphabet[0];

    // Divide and conquer base conversion using BigInt
    const powers: bigint[] = [this.#base];
    while (powers[powers.length - 1] <= value) {
      const last = powers[powers.length - 1];
      powers.push(last * last);
    }

    const convert = (val: bigint, powerIndex: number): string => {
      if (val === 0n) return '';
      if (powerIndex < 0) {
        return this.alphabet[Number(val)];
      }
      const p = powers[powerIndex];
      if (val < p) {
        return convert(val, powerIndex - 1);
      }
      const q = val / p;
      const r = val % p;
      const left = convert(q, powerIndex - 1);
      const right = convert(r, powerIndex - 1);
      const expectedLen = 1 << powerIndex;
      return left + right.padStart(expectedLen, this.alphabet[0]);
    };

    const res = convert(value, powers.length - 1);
    // Strip leading zeros
    let start = 0;
    while (start < res.length && res[start] === this.alphabet[0]) {
      start++;
    }
    return res.slice(start) || this.alphabet[0];
  }

  decode(data: string): Uint8Array<ArrayBuffer> {
    if (data.length === 0) return new Uint8Array(0);

    const powers: bigint[] = [this.#base];
    let len = 1;
    while (len < data.length) {
      const last = powers[powers.length - 1];
      powers.push(last * last);
      len *= 2;
    }

    const parse = (str: string, powerIndex: number): bigint => {
      if (str.length === 0) return 0n;
      if (str.length === 1) {
        const digit = this.alphabet.indexOf(str);
        if (digit === -1) throw new Error(`Invalid character: ${str}`);
        return BigInt(digit);
      }
      const halfLen = 1 << (powerIndex - 1);
      if (str.length <= halfLen) {
        return parse(str, powerIndex - 1);
      }
      const leftStr = str.slice(0, str.length - halfLen);
      const rightStr = str.slice(str.length - halfLen);
      const left = parse(leftStr, powerIndex - 1);
      const right = parse(rightStr, powerIndex - 1);
      return left * powers[powerIndex - 1] + right;
    };

    const value = parse(data, powers.length);

    if (value === 0n) return new Uint8Array([0]);

    // Fast BigInt to bytes via hex string
    let hexStr = value.toString(16);
    if (hexStr.length % 2 !== 0) hexStr = '0' + hexStr;

    const buffer = new Uint8Array(hexStr.length / 2);
    for (let i = 0; i < buffer.length; i++) {
      buffer[i] = parseInt(hexStr.slice(i * 2, i * 2 + 2), 16);
    }
    return buffer;
  }
}