public inbox for [email protected]  

help / color / mirror / Atom feed

From: Joel Jacobson <[email protected]>
To: Dagfinn Ilmari Mannsåker <[email protected]>
Cc: pgsql-hackers <[email protected]>
Subject: Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands.
Date: Mon, 01 Jul 2024 15:11:43 +0200
Message-ID: <[email protected]> (raw)
In-Reply-To: <[email protected]>
References: <[email protected]>
	<[email protected]>

On Mon, Jul 1, 2024, at 14:25, Dagfinn Ilmari Mannsåker wrote:
> div_var() also has an optimisation for 3- and 4-digit operands under
> HAVE_INT128 (added in commit 0aa38db56bf), would that make sense in
> mul_var() too?

I considered it, but it only gives a marginal speed-up on Intel Core i9-14900K,
and is actually slower on Apple M3 Max.
Not really sure why. Maybe the code I tried can be optimized further:

```
#ifdef HAVE_INT128
	/*
	 * If var1 and var2 are up to four digits, their product will fit in
	 * an int128 can be computed directly, which is significantly faster.
	 */
	if (var2ndigits <= 4)
	{
		int128		product = 0;

		switch (var1ndigits)
		{
			case 1:
				product = var1digits[0];
				break;
			case 2:
				product = var1digits[0] * NBASE + var1digits[1];
				break;
			case 3:
				product = ((int128) var1digits[0] * NBASE + var1digits[1])
						* NBASE + var1digits[2];
				break;
			case 4:
				product = (((int128) var1digits[0] * NBASE + var1digits[1])
						* NBASE + var1digits[2]) * NBASE + var1digits[3];
				break;
		}

		switch (var2ndigits)
		{
			case 1:
				product *= var2digits[0];
				break;
			case 2:
				product *= var2digits[0] * NBASE + var2digits[1];
				break;
			case 3:
				product = ((int128) var2digits[0] * NBASE + var2digits[1])
						* NBASE + var2digits[2];
				break;
			case 4:
				product = (((int128) var2digits[0] * NBASE + var2digits[1])
						* NBASE + var2digits[2]) * NBASE + var2digits[3];
				break;
		}

		alloc_var(result, res_ndigits);
		res_digits = result->digits;
		for (i = res_ndigits - 1; i >= 0; i--)
		{
			res_digits[i] = product % NBASE;
			product /= NBASE;
		}
		Assert(product == 0);

		/*
		 * Finally, round the result to the requested precision.
		 */
		result->weight = res_weight;
		result->sign = res_sign;

		/* Round to target rscale (and set result->dscale) */
		round_var(result, rscale);

		/* Strip leading and trailing zeroes */
		strip_var(result);

		return;
	}
#endif
```

Benchmark 1, testing 2 ndigits * 2 ndigits:

SELECT
   timeit.pretty_time(total_time_a / 1e6 / executions,3) AS execution_time_a,
   timeit.pretty_time(total_time_b / 1e6 / executions,3) AS execution_time_b,
   total_time_a::numeric/total_time_b AS performance_ratio
FROM timeit.cmp(
   'numeric_mul',
   'numeric_mul_patched',
   input_values := ARRAY[
      '11112222',
      '33334444'
   ],
   min_time := 1000000,
   timeout := '10 s'
);

Apple M3 Max:

 execution_time_a | execution_time_b | performance_ratio
------------------+------------------+--------------------
 32.2 ns          | 20.5 ns          | 1.5700112246809388
(1 row)

Intel Core i9-14900K:

 execution_time_a | execution_time_b | performance_ratio
------------------+------------------+--------------------
 30.2 ns          | 21.4 ns          | 1.4113042510107371
(1 row)

So 57% and 41% faster.

Benchmark 2, testing 4 ndigits * 4 ndigits:

SELECT
   timeit.pretty_time(total_time_a / 1e6 / executions,3) AS execution_time_a,
   timeit.pretty_time(total_time_b / 1e6 / executions,3) AS execution_time_b,
   total_time_a::numeric/total_time_b AS performance_ratio
FROM timeit.cmp(
   'numeric_mul',
   'numeric_mul_patched',
   input_values := ARRAY[
      '1111222233334444',
      '5555666677778888'
   ],
   min_time := 1000000,
   timeout := '10 s'
);

Apple M3 Max:

 execution_time_a | execution_time_b |   performance_ratio
------------------+------------------+------------------------
 41.9 ns          | 51.3 ns          | 0.81733655797170943614
(1 row)

Intel Core i9-14900K:

 execution_time_a | execution_time_b | performance_ratio
------------------+------------------+--------------------
 40 ns            | 38 ns            | 1.0515610914706320
(1 row)

So 18% slower on Apple M3 Max and just 5% faster on Intel Core i9-14900K.

/Joel

view thread (3+ messages)

reply

Reply instructions:

You may reply publicly to this message via plain-text email
using any one of the following methods:

* Reply to all the recipients using the --to and --cc options:
  reply via email

  To: [email protected]
  Cc: [email protected], [email protected]
  Subject: Re: Optimize numeric multiplication for one and two base-NBASE digit multiplicands.
  In-Reply-To: <[email protected]>

* Save the following mbox file, import it into your mail client,
  and reply-to-all from there: mbox

This inbox is served by agora; see mirroring instructions
for how to clone and mirror all data and code used for this inbox