Re: Optimize numeric.c mul_var() using the Karatsuba algorithm

On Sun, Jun 30, 2024, at 17:44, Tom Lane wrote:
> "Joel Jacobson" <joel(at)compiler(dot)org> writes:
>> On Sat, Jun 29, 2024, at 17:25, Tom Lane wrote:
>>> (In general I find this patch seriously undercommented.)
>
>> However, I think the comments above split_var_at(),
>> mul_var_karatsuba_full() and mul_var_karatsuba_half()
>> are quite good already, what do you think?
>
> Not remarkably so. For starters, heaven help the reader who has
> no idea what "the Karatsuba algorithm" refers to. Nor is there
> any mention of why (or when) it's better than the traditional
> algorithm. You could at least do people the courtesy of providing
> a link to the wikipedia article that you're assuming they've
> memorized.

Thanks for guidance. New patch attached.

I've added as an introduction to Karatsuba:

+/*
+ * mul_var_karatsuba_full() -
+ *
+ * Multiplication using the Karatsuba algorithm.
+ *
+ * The Karatsuba algorithm is a divide-and-conquer algorithm that reduces
+ * the complexity of large number multiplication. It splits each number
+ * into two halves and performs three multiplications on the parts,
+ * rather than four as in the traditional method. This results in
+ * a significant performance improvement for sufficiently large numbers.
...
+ * For more details on the Karatsuba algorithm, see the Wikipedia article:
+ * https://en.wikipedia.org/wiki/Karatsuba_algorithm

> There's also a discussion to be had about why Karatsuba is
> a better choice than other divide-and-conquer multiplication
> methods. Why not Toom-Cook, for example, which the aforesaid
> wikipedia page says is faster yet? I suppose you concluded
> that the extra complexity is unwarranted, but this is the
> sort of thing I'd expect to see explained in the comments.

I've added this to the end of the comment on mul_var_karatsuba_full():

+ * The Karatsuba algorithm is preferred over other divide-and-conquer methods
+ * like Toom-Cook for this implementation due to its balance of complexity and
+ * performance gains given Numeric's constraints.
+ *
+ * For Toom-Cook to be worth the added complexity, the factors would need to
+ * be much larger than supported by Numeric, making Karatsuba a more
+ * appropriate choice.

Also, I added this comment on the #define's at the beginning:

+/*
+ * Constants used to determine when the Karatsuba algorithm should be used
+ * for multiplication. These thresholds were determined empirically through
+ * benchmarking across various architectures, aiming to avoid performance
+ * regressions while capturing potential gains. The choice of these values
+ * involves trade-offs and balances simplicity and performance.
+ */

As well as this comment on KARATSUBA_CONDITION:

+/*
+ * KARATSUBA_CONDITION() -
+ *
+ * This macro determines if the Karatsuba algorithm should be applied
+ * based on the number of digits in the multiplicands. It checks if
+ * the number of digits in the larger multiplicand exceeds a base limit
+ * and if the sizes of the multiplicands fall within specific ranges
+ * where Karatsuba multiplication is usually beneficial.
+ *
+ * The conditions encapsulated by KARATSUBA_CONDITION are:
+ * 1. The larger multiplicand has more digits than the base limit.
+ * 2. The sizes of the multiplicands fall within low, middle, or high range
+ * conditions which were identified as performance beneficial regions during
+ * benchmarks.
+ *
+ * The macro ensures that the algorithm is applied only when it is likely
+ * to provide performance benefits, considering the size and ratio of the
+ * factors.
+ */

What do you think?

Regards,
Joel