ext/bcmath: optimized `divmod()` and `mod()` take 2 #18058

SakiTakamachi · 2025-03-14T06:02:42Z

Benchmarks

1:

for ($i = 0; $i < 2000000; $i++) {
    bcdiv('1.23', '2', 5);
    // bcdivmod('1.23', '2', 5);
    // bcmod('1.23', '2', 5);
}

2:

for ($i = 0; $i < 2000000; $i++) {
    bcdiv('5.2345678', '2.1234567', 10);
    // bcdivmod('5.2345678', '2.1234567', 10);
    // bcmod('5.2345678', '2.1234567', 10);
}

3:

for ($i = 0; $i < 2000000; $i++) {
    bcdiv('12345678.901234', '1.2345678912', 10);
    // bcdivmod('12345678.901234', '1.2345678912', 10);
    // bcmod('12345678.901234', '1.2345678912', 10);
}

div

In theory, it will be slower because there are more branches, but it seems to make little difference.

1:

Benchmark 1: /php-dev/sapi/cli/php /mount/bc/divmod/1.php
  Time (mean ± σ):     308.9 ms ±   6.5 ms    [User: 297.1 ms, System: 6.0 ms]
  Range (min … max):   300.9 ms … 323.5 ms    10 runs
 
Benchmark 2: /master/sapi/cli/php /mount/bc/divmod/1.php
  Time (mean ± σ):     303.5 ms ±   5.3 ms    [User: 292.3 ms, System: 5.5 ms]
  Range (min … max):   298.1 ms … 313.0 ms    10 runs
 
Summary
  '/master/sapi/cli/php /mount/bc/divmod/1.php' ran
    1.02 ± 0.03 times faster than '/php-dev/sapi/cli/php /mount/bc/divmod/1.php'

2:

Benchmark 1: /php-dev/sapi/cli/php /mount/bc/divmod/2.php
  Time (mean ± σ):     379.5 ms ±   6.8 ms    [User: 370.4 ms, System: 3.6 ms]
  Range (min … max):   368.5 ms … 390.2 ms    10 runs
 
Benchmark 2: /master/sapi/cli/php /mount/bc/divmod/2.php
  Time (mean ± σ):     386.2 ms ±  18.8 ms    [User: 376.2 ms, System: 4.6 ms]
  Range (min … max):   370.3 ms … 432.2 ms    10 runs
 
Summary
  '/php-dev/sapi/cli/php /mount/bc/divmod/2.php' ran
    1.02 ± 0.05 times faster than '/master/sapi/cli/php /mount/bc/divmod/2.php'

3:

Benchmark 1: /php-dev/sapi/cli/php /mount/bc/divmod/3.php
  Time (mean ± σ):     526.3 ms ±  14.4 ms    [User: 514.7 ms, System: 6.2 ms]
  Range (min … max):   507.4 ms … 557.3 ms    10 runs
 
Benchmark 2: /master/sapi/cli/php /mount/bc/divmod/3.php
  Time (mean ± σ):     529.8 ms ±  14.2 ms    [User: 519.3 ms, System: 4.9 ms]
  Range (min … max):   517.2 ms … 553.8 ms    10 runs
 
Summary
  '/php-dev/sapi/cli/php /mount/bc/divmod/3.php' ran
    1.01 ± 0.04 times faster than '/master/sapi/cli/php /mount/bc/divmod/3.php'

divmod

This is faster because there are no extra calculations involved.

1:

Benchmark 1: /php-dev/sapi/cli/php /mount/bc/divmod/1.php
  Time (mean ± σ):     457.5 ms ±   9.5 ms    [User: 446.7 ms, System: 5.2 ms]
  Range (min … max):   448.2 ms … 473.7 ms    10 runs
 
Benchmark 2: /master/sapi/cli/php /mount/bc/divmod/1.php
  Time (mean ± σ):     518.5 ms ±   8.9 ms    [User: 508.0 ms, System: 5.3 ms]
  Range (min … max):   511.2 ms … 535.5 ms    10 runs
 
Summary
  '/php-dev/sapi/cli/php /mount/bc/divmod/1.php' ran
    1.13 ± 0.03 times faster than '/master/sapi/cli/php /mount/bc/divmod/1.php'

2:

Benchmark 1: /php-dev/sapi/cli/php /mount/bc/divmod/2.php
  Time (mean ± σ):     487.0 ms ±   9.8 ms    [User: 476.0 ms, System: 4.4 ms]
  Range (min … max):   476.4 ms … 503.4 ms    10 runs
 
Benchmark 2: /master/sapi/cli/php /mount/bc/divmod/2.php
  Time (mean ± σ):     585.8 ms ±   8.8 ms    [User: 576.1 ms, System: 4.2 ms]
  Range (min … max):   576.3 ms … 607.8 ms    10 runs
 
Summary
  '/php-dev/sapi/cli/php /mount/bc/divmod/2.php' ran
    1.20 ± 0.03 times faster than '/master/sapi/cli/php /mount/bc/divmod/2.php'

3:

Benchmark 1: /php-dev/sapi/cli/php /mount/bc/divmod/3.php
  Time (mean ± σ):     581.4 ms ±   4.6 ms    [User: 570.5 ms, System: 5.1 ms]
  Range (min … max):   573.4 ms … 590.0 ms    10 runs
 
Benchmark 2: /master/sapi/cli/php /mount/bc/divmod/3.php
  Time (mean ± σ):     791.4 ms ±  26.3 ms    [User: 780.6 ms, System: 5.2 ms]
  Range (min … max):   771.4 ms … 843.2 ms    10 runs
 
Summary
  '/php-dev/sapi/cli/php /mount/bc/divmod/3.php' ran
    1.36 ± 0.05 times faster than '/master/sapi/cli/php /mount/bc/divmod/3.php'

mod

It's faster for the same reasons as divmod, and it's even faster because it doesn't need to generate bc_num for quot.

1:

Benchmark 1: /php-dev/sapi/cli/php /mount/bc/divmod/1.php
  Time (mean ± σ):     321.5 ms ±  10.3 ms    [User: 311.8 ms, System: 4.4 ms]
  Range (min … max):   311.4 ms … 348.2 ms    10 runs
 
Benchmark 2: /master/sapi/cli/php /mount/bc/divmod/1.php
  Time (mean ± σ):     401.1 ms ±  10.4 ms    [User: 391.1 ms, System: 4.8 ms]
  Range (min … max):   389.9 ms … 426.9 ms    10 runs
 
Summary
  '/php-dev/sapi/cli/php /mount/bc/divmod/1.php' ran
    1.25 ± 0.05 times faster than '/master/sapi/cli/php /mount/bc/divmod/1.php'

2:

Benchmark 1: /php-dev/sapi/cli/php /mount/bc/divmod/2.php
  Time (mean ± σ):     348.5 ms ±   6.4 ms    [User: 338.2 ms, System: 4.7 ms]
  Range (min … max):   337.8 ms … 358.3 ms    10 runs
 
Benchmark 2: /master/sapi/cli/php /mount/bc/divmod/2.php
  Time (mean ± σ):     481.3 ms ±  19.2 ms    [User: 470.4 ms, System: 5.4 ms]
  Range (min … max):   468.1 ms … 528.5 ms    10 runs
 
Summary
  '/php-dev/sapi/cli/php /mount/bc/divmod/2.php' ran
    1.38 ± 0.06 times faster than '/master/sapi/cli/php /mount/bc/divmod/2.php'

3:

Benchmark 1: /php-dev/sapi/cli/php /mount/bc/divmod/3.php
  Time (mean ± σ):     433.1 ms ±   9.3 ms    [User: 422.9 ms, System: 4.7 ms]
  Range (min … max):   424.0 ms … 456.8 ms    10 runs
 
Benchmark 2: /master/sapi/cli/php /mount/bc/divmod/3.php
  Time (mean ± σ):     660.2 ms ±   7.5 ms    [User: 650.1 ms, System: 4.7 ms]
  Range (min … max):   650.9 ms … 673.1 ms    10 runs
 
Summary
  '/php-dev/sapi/cli/php /mount/bc/divmod/3.php' ran
    1.52 ± 0.04 times faster than '/master/sapi/cli/php /mount/bc/divmod/3.php'

…o the correct value.

…ctions to use it.

…th_skip()`

SakiTakamachi · 2025-05-23T08:27:33Z

Conflict resolved

nielsdos · 2025-06-27T21:48:35Z

ext/bcmath/libbcmath/src/div.c

@@ -425,9 +425,6 @@ bool bc_divide_ex(bc_num numerator, bc_num divisor, bc_num *quot, bc_num *rem, s
 	_bc_rm_leading_zeros(*quot);
 	if (bc_is_zero(*quot)) {
 		(*quot)->n_sign = PLUS;
-		(*quot)->n_scale = 0;


You no longer reset the scale in this case, but you only removed the leading zeros (on line 425) and not the trailing zeros. Can you explain please?

nielsdos · 2025-06-27T21:49:20Z

ext/bcmath/libbcmath/src/div.c

 	size_t quot_scale = scale;
+	if (use_quot) {


Instead of using a separate argument for use_quot, use_rem. Why not check if quot/rem is a NULL pointer?

nielsdos · 2025-06-27T21:49:53Z

ext/bcmath/libbcmath/src/div.c

+		_bc_rm_leading_zeros(*quot);
+		if (bc_is_zero(*quot)) {
+			(*quot)->n_sign = PLUS;
+			(*quot)->n_scale = 0;


I guess my previous question is answered because this line returned, but you should instead amend the previous commit so that it wasn't deleted in the first place. That keeps the history cleaner.

@nielsdos

Sorry, I think a line was accidentally removed when I rebased and merged in master.

I had only reviewed the final version of the code, so I didn’t notice that one of the intermediate commits included an unintended deletion.

nielsdos · 2025-06-27T21:50:49Z

ext/bcmath/libbcmath/src/convert.h

@@ -111,4 +111,30 @@ static inline void bc_convert_vector_to_char(const BC_VECTOR *vector, char *nptr
 	}
 }

+static inline void bc_convert_vector_to_char_with_skip(const BC_VECTOR *vector, char *nptr, char *nend, size_t arr_size, size_t skip)


This function either needs a better name or a doc block explaining what it does on a high level. What is skip and why is it necessary? I don't know at this point.

@nielsdos

For example, if BC_VECTOR = [7890, 3456, 12], and want to construct a char array like 1234567, need to skip three digits 890 in 7890.

This kind of skipping is necessary when storing the rem (from division) into a char array, especially when the number of digits in BC_VECTOR doesn’t match the required scale for the rem.

↑ Would this explanation be clear enough to convey the intent?

nielsdos · 2025-06-27T21:51:25Z

ext/bcmath/libbcmath/src/div.c

@@ -255,7 +255,8 @@ static inline void bc_standard_div(
 static void bc_do_div(
 	const char *numerator, size_t numerator_size, size_t numerator_readable_size,
 	const char *divisor, size_t divisor_size,
-	bc_num *quot, size_t quot_size
+	bc_num *quot, size_t quot_size,
+	bool use_quot


Same remark about the quot NULL pointer instead of the bool

nielsdos · 2025-06-27T21:57:05Z

ext/bcmath/libbcmath/src/div.c

@@ -443,8 +445,46 @@ bool bc_divide_ex(bc_num numerator, bc_num divisor, bc_num *quot, bc_num *rem, s
 		(*quot)->n_sign = numerator->n_sign == divisor->n_sign ? PLUS : MINUS;
 	}

+	/**


I'm missing the high level explanation here on how you compute the remainder length

nielsdos · 2025-06-27T21:58:09Z

ext/bcmath/libbcmath/src/div.c

+			*rem = bc_copy_num(BCG(_zero_));
+			return;
+		}
+		/* The values after this have already been copied, so just need to set them to 0. */


Copied by whom?

About 10 lines above the line where this function is called, there’s the following line:

memcpy((*rem)->n_value + rem_write_size, numerator->n_value + rem_write_size + numerator_rem_len_diff, copy_size);

The intention here was that everything except the leading zeros has already been copied.

nielsdos · 2025-06-27T21:58:39Z

ext/bcmath/libbcmath/src/div.c

+		char *rptr = (*rem)->n_value;
+		char *rend = rptr + rem_write_size - 1;
+
+		size_t rem_arr_size = (rem_write_size + rem_over_size + BC_VECTOR_SIZE - 1) / BC_VECTOR_SIZE;


Didn't we have a macro for the rounding-up divide ?

nielsdos · 2025-06-27T21:59:21Z

ext/bcmath/libbcmath/src/div.c

+		BC_VECTOR *rem_vectors = numerator_vectors;
+
+		if (rem_over_size > 0) {
+			bc_convert_vector_to_char_with_skip(rem_vectors, rptr, rend, rem_arr_size, rem_over_size);


I still don't understand the skip

SakiTakamachi · 2025-06-28T04:17:49Z

Overall, the way we calculate the number of digits in rem might be a bit too complex.

I’ll think about whether there’s a better approach, or at least a clearer way to explain it in comments.

github-actions bot added Category: Build System Extension: bcmath labels Mar 14, 2025

SakiTakamachi force-pushed the bcmath/mod_divmod branch 3 times, most recently from 345c1ed to d94dcc9 Compare March 14, 2025 06:47

SakiTakamachi force-pushed the bcmath/mod_divmod branch 6 times, most recently from f0e9762 to 783c7e7 Compare April 26, 2025 05:39

SakiTakamachi marked this pull request as ready for review April 26, 2025 06:27

SakiTakamachi requested review from Girgias and nielsdos as code owners April 26, 2025 06:27

SakiTakamachi added 2 commits May 23, 2025 17:22

Added bc_divide_copy_numerator()

03955d6

At the end of the calculation, set the value of numerator_vectors t…

aaf1f6a

…o the correct value.

SakiTakamachi force-pushed the bcmath/mod_divmod branch from 783c7e7 to aa49dc2 Compare May 23, 2025 08:23

SakiTakamachi added 11 commits May 23, 2025 17:26

Changed bc_divide to bc_divide_ex, and changed three division fun…

b2c1b3f

…ctions to use it.

Set the sign of quot efficiently

c0000cd

Use quot only if use_quot == true, in bc_divide_ex

0865562

Added bc_convert_vector_to_char() and `bc_convert_vector_to_char_wi…

5e4b175

…th_skip()`

Use quot only if use_quot == true, in other funcs

13a98ae

Roughly write code using use_rem

b949c5e

Using rem in bc_divide_by_one

484d9df

Create a process to initialize bc_num of rem

2d63079

Using rem in bc_divide_by_pow_10

c7916b5

Using rem in bc_do_div

a2ba77c

fixed raisemod

d3a5713

SakiTakamachi force-pushed the bcmath/mod_divmod branch from aa49dc2 to d3a5713 Compare May 23, 2025 08:26

nielsdos requested changes Jun 27, 2025

View reviewed changes

Provide feedback

Saved searches

Use saved searches to filter your results more quickly

Uh oh!

ext/bcmath: optimized `divmod()` and `mod()` take 2 #18058

ext/bcmath: optimized `divmod()` and `mod()` take 2 #18058

SakiTakamachi commented Mar 14, 2025 •

edited

Loading

Uh oh!

SakiTakamachi commented May 23, 2025

Uh oh!

nielsdos Jun 27, 2025

Uh oh!

nielsdos Jun 27, 2025

Uh oh!

nielsdos Jun 27, 2025

Uh oh!

SakiTakamachi Jun 28, 2025

Uh oh!

nielsdos Jun 27, 2025

Uh oh!

SakiTakamachi Jun 28, 2025

Uh oh!

nielsdos Jun 27, 2025

Uh oh!

nielsdos Jun 27, 2025

Uh oh!

nielsdos Jun 27, 2025

Uh oh!

SakiTakamachi Jun 28, 2025

Uh oh!

nielsdos Jun 27, 2025

Uh oh!

nielsdos Jun 27, 2025

Uh oh!

SakiTakamachi commented Jun 28, 2025

Uh oh!

Uh oh!

ext/bcmath: optimized divmod() and mod() take 2 #18058

Are you sure you want to change the base?

ext/bcmath: optimized divmod() and mod() take 2 #18058

Conversation

SakiTakamachi commented Mar 14, 2025 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Benchmarks

div

divmod

mod

Uh oh!

SakiTakamachi commented May 23, 2025

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

SakiTakamachi commented Jun 28, 2025

Uh oh!

Uh oh!

ext/bcmath: optimized `divmod()` and `mod()` take 2 #18058

ext/bcmath: optimized `divmod()` and `mod()` take 2 #18058

SakiTakamachi commented Mar 14, 2025 •

edited

Loading