ext/bcmath: Improving `bcpow()` performance #18099

SakiTakamachi · 2025-03-17T15:42:20Z

I ran 500,000 comparisons with PHP 8.3 results. (I would like to perform more comparisons, but PHP 8.3's bcpow() is too heavy and the comparisons never finish.)
No problems were detected.

Benchmarks

The speed difference is especially noticeable when base is less than 1 and there are many leading zeros.
This is because try to eliminate as many zeros as possible during the calculation, and then fill in the missing digits with zeros later.

1:

for ($i = 0; $i < 2000000; $i++) {
    bcpow('123', '4', 0);
}

Benchmark 1: /php-dev/sapi/cli/php /mount/bc/pow/1.php
  Time (mean ± σ):     244.8 ms ±   1.3 ms    [User: 235.5 ms, System: 4.2 ms]
  Range (min … max):   242.8 ms … 247.7 ms    12 runs
 
Benchmark 2: /master/sapi/cli/php /mount/bc/pow/1.php
  Time (mean ± σ):     279.4 ms ±   3.4 ms    [User: 269.1 ms, System: 5.2 ms]
  Range (min … max):   275.7 ms … 287.4 ms    10 runs
 
Summary
  '/php-dev/sapi/cli/php /mount/bc/pow/1.php' ran
    1.14 ± 0.02 times faster than '/master/sapi/cli/php /mount/bc/pow/1.php'

2:

for ($i = 0; $i < 200000; $i++) {
    bcpow('123456.789', '64', 10);
}

Benchmark 1: /php-dev/sapi/cli/php /mount/bc/pow/2.php
  Time (mean ± σ):     360.9 ms ±   1.1 ms    [User: 350.9 ms, System: 4.8 ms]
  Range (min … max):   359.4 ms … 363.2 ms    10 runs
 
Benchmark 2: /master/sapi/cli/php /mount/bc/pow/2.php
  Time (mean ± σ):     506.4 ms ±   4.3 ms    [User: 496.2 ms, System: 4.7 ms]
  Range (min … max):   501.0 ms … 514.3 ms    10 runs
 
Summary
  '/php-dev/sapi/cli/php /mount/bc/pow/2.php' ran
    1.40 ± 0.01 times faster than '/master/sapi/cli/php /mount/bc/pow/2.php'

3:

for ($i = 0; $i < 100000; $i++) {
    bcpow('0.00123456', '120', 10);
}

Benchmark 1: /php-dev/sapi/cli/php /mount/bc/pow/3.php
  Time (mean ± σ):     304.9 ms ±   2.9 ms    [User: 295.4 ms, System: 4.4 ms]
  Range (min … max):   299.9 ms … 308.7 ms    10 runs
 
Benchmark 2: /master/sapi/cli/php /mount/bc/pow/3.php
  Time (mean ± σ):     808.8 ms ±   9.0 ms    [User: 797.4 ms, System: 5.6 ms]
  Range (min … max):   799.3 ms … 827.3 ms    10 runs
 
Summary
  '/php-dev/sapi/cli/php /mount/bc/pow/3.php' ran
    2.65 ± 0.04 times faster than '/master/sapi/cli/php /mount/bc/pow/3.php'

4:

for ($i = 0; $i < 1000; $i++) {
    bcpow('0.00000000000000123456', '2000', 10);
}

Benchmark 1: /php-dev/sapi/cli/php /mount/bc/pow/4.php
  Time (mean ± σ):     433.7 ms ±   1.9 ms    [User: 422.2 ms, System: 6.2 ms]
  Range (min … max):   431.6 ms … 437.6 ms    10 runs
 
Benchmark 2: /master/sapi/cli/php /mount/bc/pow/4.php
  Time (mean ± σ):      6.024 s ±  0.071 s    [User: 6.011 s, System: 0.007 s]
  Range (min … max):    5.986 s …  6.225 s    10 runs
 
  Warning: Statistical outliers were detected. Consider re-running this benchmark on a quiet system without any interferences from other programs. It might help to use the '--warmup' or '--prepare' options.
 
Summary
  '/php-dev/sapi/cli/php /mount/bc/pow/4.php' ran
   13.89 ± 0.18 times faster than '/master/sapi/cli/php /mount/bc/pow/4.php'

SakiTakamachi · 2025-03-18T00:32:36Z

There were still some things I wanted to change, so I reverted it to a draft.

SakiTakamachi · 2025-03-19T16:47:52Z

Ready for review.
The failed tests are irrelevant.

cc: @nielsdos

…dard_vector_mul`.

…e`, and renamed to `bc_square_vector`.

…c_multiply_vector

SakiTakamachi · 2025-03-23T12:06:03Z

I force pushed by mistake.

I'll open it again once I've confirmed the code 🙏

SakiTakamachi · 2025-03-23T14:43:21Z

I reverted to the original code.

nielsdos · 2025-04-26T12:59:05Z

ext/bcmath/libbcmath/src/raise.c

+	}
+
+	size_t base_arr_size = BC_ARR_SIZE_FROM_LEN(base_len);
+	size_t max_power_arr_size =	base_arr_size * exponent;


Can this overflow?

Added check for base->n_len * exponent.
So guaranteed not to overflow here. I added a comment.
b96f2d9

nielsdos · 2025-04-26T12:59:25Z

ext/bcmath/libbcmath/src/raise.c

+	size_t max_power_arr_size =	base_arr_size * exponent;
+
+	/* The allocated memory area is reused on a rotational basis, so the same size is required. */
+	BC_VECTOR *buf = safe_emalloc(max_power_arr_size * 3, sizeof(BC_VECTOR), 0);


Should probably be safe_emalloc(max_power_arr_size, 3 * sizeof(BC_VECTOR), 0); for safety

Fixed in 2556951

nielsdos · 2025-04-26T13:00:18Z

ext/bcmath/libbcmath/src/raise.c

+	/* Remove the leading zeros as they will be filled in later. */
+	while (*base_ptr++ == 0) {
+		base_len--;
+	}


This will already move base_ptr even if the first element is not 0. Did you mean this?

Suggested change

/* Remove the leading zeros as they will be filled in later. */

while (*base_ptr++ == 0) {

base_len--;

}

/* Remove the leading zeros as they will be filled in later. */

while (*base_ptr == 0) {

base_ptr++;

base_len--;

}

Ah, damn, you're absolutely right. Thanks!
Fixed in 2556951

nielsdos · 2025-04-26T13:01:41Z

ext/bcmath/libbcmath/src/raise.c

-		bc_square_ex(power, &power, pwrscale);
-		exponent = exponent >> 1;
+	size_t base_len = base->n_len + base->n_scale;
+	size_t power_len = base->n_len * exponent;


I wonder which of these can overflow

Added check in b96f2d9
Thanks!

nielsdos · 2025-04-26T13:04:31Z

ext/bcmath/libbcmath/src/raise.c

+
+	/* Pad with leading zeros if necessary. */
+	while (power_leading_zeros > sizeof(uint32_t)) {
+		bc_write_bcd_representation(0, pptr);


This is an inefficient way of writing the zeros, better use one call to memset instead of this while+for loops actually.

I had seen somewhere that memset was slow, so I had been avoiding it.
I've now updated the code to use memset.

in 2556951

nielsdos · 2025-04-27T09:48:11Z

ext/bcmath/bcmath.c

-	if (!bc_raise(first, exponent, &result, scale)) {
-		zend_throw_exception_ex(zend_ce_division_by_zero_error, 0, "Negative power of zero");
-		goto cleanup;
+	switch (bc_raise(first, exponent, &result, scale)) {


The code to handle the errors is duplicated. I think it would be great to have a separate function that throws the correct exception when bc_raise fails. Then, here and in bcmath_number_pow_internal you can call that function is bc_raise return value != BC_RAISE_STATUS_OK.

Fixed in 20c9309

nielsdos · 2025-04-27T09:48:37Z

ext/bcmath/libbcmath/src/bcmath.h

@@ -74,6 +74,10 @@ typedef struct bc_struct {
 #define MAX(a, b)      ((a)>(b)?(a):(b))
 #define MIN(a, b)      ((a)>(b)?(b):(a))

+#ifndef SIZE_T_MAX


There's a standard macro SIZE_MAX in limits.h

Fixed in 54729fd

nielsdos · 2025-04-27T09:49:47Z

ext/bcmath/libbcmath/src/raise.c

+	/* check overflow */
+	if (UNEXPECTED(base->n_len > SIZE_T_MAX / exponent)) {
+		bc_free_num (result);
+		*result = bc_copy_num(BCG(_one_));


Why is it necessary to return a number in result anyway after this check fails? (Same question below)

Indeed, there was nothing that required action here.

Fixed in 91e3890

github-actions bot added the Extension: bcmath label Mar 17, 2025

SakiTakamachi force-pushed the bcmath/pow branch from cff64b6 to 511010a Compare March 17, 2025 16:36

SakiTakamachi marked this pull request as ready for review March 18, 2025 00:06

SakiTakamachi requested review from Girgias and nielsdos as code owners March 18, 2025 00:06

SakiTakamachi marked this pull request as draft March 18, 2025 00:31

SakiTakamachi force-pushed the bcmath/pow branch 2 times, most recently from 33bfabf to f303bd5 Compare March 19, 2025 15:09

SakiTakamachi marked this pull request as ready for review March 19, 2025 16:46

SakiTakamachi added 6 commits March 23, 2025 18:55

Removed bc_fast_square and bc_standard_square.

3ff726a

Merged bc_mul_finish_from_vector into bc_standard_mul

788a884

The calculation process of BC_VECTOR was separated inline as `bc_stan…

186214b

…dard_vector_mul`.

Removed the conversion process of bc_num and BC_VECTOR from `bc_squar…

c1568f1

…e`, and renamed to `bc_square_vector`.

Changed bc_square_vector to normal multiplication and renamed it to b…

a42d2e1

…c_multiply_vector

If base is 0, return early.

f303d7d

SakiTakamachi force-pushed the bcmath/pow branch 2 times, most recently from a1f6bbf to 76d0e61 Compare March 23, 2025 10:01

SakiTakamachi marked this pull request as draft March 23, 2025 12:04

SakiTakamachi force-pushed the bcmath/pow branch from 76d0e61 to 6d00b7b Compare March 23, 2025 12:26

optimized bc_raise

757e3bc

SakiTakamachi force-pushed the bcmath/pow branch from 6d00b7b to 757e3bc Compare March 23, 2025 12:33

SakiTakamachi marked this pull request as ready for review March 23, 2025 14:41

Use const appropriately

d203371

nielsdos requested changes Apr 26, 2025

View reviewed changes

SakiTakamachi added 2 commits April 27, 2025 14:05

Address comments

2556951

Added overflow check

b96f2d9

nielsdos requested changes Apr 27, 2025

View reviewed changes

SakiTakamachi added 4 commits April 28, 2025 09:14

use SIZE_MAX

54729fd

On failure, do nothing with the return value

91e3890

Error handling is separated as a static function

20c9309

Fixed an error in enum type

9e5c9a4

nielsdos approved these changes Apr 29, 2025

View reviewed changes

SakiTakamachi merged commit c5f3281 into php:master Apr 29, 2025
9 checks passed

SakiTakamachi deleted the bcmath/pow branch April 29, 2025 23:05

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

ext/bcmath: Improving `bcpow()` performance #18099

ext/bcmath: Improving `bcpow()` performance #18099

SakiTakamachi commented Mar 17, 2025 •

edited

Loading

SakiTakamachi commented Mar 18, 2025

SakiTakamachi commented Mar 19, 2025

SakiTakamachi commented Mar 23, 2025

SakiTakamachi commented Mar 23, 2025

nielsdos Apr 26, 2025

SakiTakamachi Apr 27, 2025

nielsdos Apr 26, 2025

SakiTakamachi Apr 27, 2025

nielsdos Apr 26, 2025

SakiTakamachi Apr 27, 2025

nielsdos Apr 26, 2025

SakiTakamachi Apr 27, 2025

nielsdos Apr 26, 2025

SakiTakamachi Apr 27, 2025

nielsdos Apr 27, 2025

SakiTakamachi Apr 28, 2025

nielsdos Apr 27, 2025

SakiTakamachi Apr 28, 2025

nielsdos Apr 27, 2025

SakiTakamachi Apr 27, 2025

SakiTakamachi Apr 28, 2025

ext/bcmath: Improving bcpow() performance #18099

ext/bcmath: Improving bcpow() performance #18099

Conversation

SakiTakamachi commented Mar 17, 2025 • edited Loading

Benchmarks

SakiTakamachi commented Mar 18, 2025

SakiTakamachi commented Mar 19, 2025

SakiTakamachi commented Mar 23, 2025

SakiTakamachi commented Mar 23, 2025

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

Choose a reason for hiding this comment

ext/bcmath: Improving `bcpow()` performance #18099

ext/bcmath: Improving `bcpow()` performance #18099

SakiTakamachi commented Mar 17, 2025 •

edited

Loading