Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

[PATCH] optimize IV -> UV conversions #16761

Closed
p5pRT opened this issue Nov 21, 2018 · 10 comments

Comments

@p5pRT
Copy link
Collaborator

commented Nov 21, 2018

Migrated from rt.perl.org#133677 (status was 'resolved')

Searchable as RT133677$

@p5pRT

This comment has been minimized.

Copy link
Collaborator Author

commented Nov 21, 2018

From @xenu

In 2014 Dave fixed mishandling of IVs equal to IV_MIN in maaaaany places
in the perl codebase (that's why I'm CC-ing him). There were many
commits, for example 53e2bfb.

While the fix was perfectly good, it can be done in a bit more optimal
way. The commit message of my patch should explain the issue​:


  optimize IV -> UV conversions

  This commit replaces all instances of code that looks like this​:
 
  uv = (iv == IV_MIN) ? (UV)iv : (UV)(-iv)

  with simpler and more optimal​:

  uv = -(UV)iv

  While -iv indeed results in an undefined behaviour when iv == IV_MIN,
  -(UV)iv is perfectly well defined and does the right thing.

  C standard guarantees that the result of (UV)iv (for negative iv) is
  equal to iv + UV_MAX + 1 (see 6.3.1.3, paragraph 2 in C11). It also
  guarantees that the result of -uv is UV_MAX - uv + 1 (6.2.5,
  paragraph 9).

  That means that the result of -(UV)iv is UV_MAX - (iv + UV_MAX + 1) + 1
  which is equal to -iv for *all* possible negative values of iv.


I have implemented this change in all places where I found that
construct. One of them was pp_divide, here's an example benchmark of
division (its source code will be attached in the next post)​:

Key​:
  Ir Instruction read
  Dr Data read
  Dw Data write
  COND conditional branches
  IND indirect branches
  _m branch predict miss
  _m1 level 1 cache miss
  _mm last cache (e.g. L3) miss
  - indeterminate percentage (e.g. 1/0)

The numbers represent relative counts per loop iteration, compared to
blead at 100.0%.
Higher is better​: for example, using half as many instructions gives 200%,
while using twice as many gives 50%.

positive_ints
4 / 2

  blead my_patch
  ------ --------
  Ir 100.00 101.40
  Dr 100.00 100.00
  Dw 100.00 100.00
  COND 100.00 100.00
  IND 100.00 100.00

COND_m 100.00 100.00
IND_m 100.00 100.00

Ir_m1 100.00 100.00
Dr_m1 100.00 100.00
Dw_m1 100.00 100.00

Ir_mm 100.00 100.00
Dr_mm 100.00 100.00
Dw_mm 100.00 100.00

one_negative_int
-4 / 2

  blead my_patch
  ------ --------
  Ir 100.00 104.14
  Dr 100.00 100.00
  Dw 100.00 100.00
  COND 100.00 104.00
  IND 100.00 100.00

COND_m 100.00 100.00
IND_m 100.00 100.00

Ir_m1 100.00 100.00
Dr_m1 100.00 100.00
Dw_m1 100.00 100.00

Ir_mm 100.00 100.00
Dr_mm 100.00 100.00
Dw_mm 100.00 100.00

two_negative_ints
-4 / -2

  blead my_patch
  ------ --------
  Ir 100.00 106.90
  Dr 100.00 100.00
  Dw 100.00 100.00
  COND 100.00 104.17
  IND 100.00 100.00

COND_m 100.00 100.00
IND_m 100.00 100.00

Ir_m1 100.00 100.00
Dr_m1 100.00 100.00
Dw_m1 100.00 100.00

Ir_mm 100.00 100.00
Dr_mm 100.00 100.00
Dw_mm 100.00 100.00

AVERAGE

  blead my_patch
  ------ --------
  Ir 100.00 104.10
  Dr 100.00 100.00
  Dw 100.00 100.00
  COND 100.00 102.69
  IND 100.00 100.00

COND_m 100.00 100.00
IND_m 100.00 100.00

Ir_m1 100.00 100.00
Dr_m1 100.00 100.00
Dw_m1 100.00 100.00

Ir_mm 100.00 100.00
Dr_mm 100.00 100.00
Dw_mm 100.00 100.00

@p5pRT

This comment has been minimized.

Copy link
Collaborator Author

commented Nov 21, 2018

From @xenu

The patch and source code of the benchmark are attached.

@p5pRT

This comment has been minimized.

Copy link
Collaborator Author

commented Nov 21, 2018

From @xenu

0001-optimize-IV-UV-conversions.patch
From a617b43437cf2239bab620d09e818953a913956a Mon Sep 17 00:00:00 2001
From: Tomasz Konojacki <me@xenu.pl>
Date: Wed, 21 Nov 2018 09:26:31 +0100
Subject: [PATCH] optimize IV -> UV conversions

This commit replaces all instances of code that looks like this:

  uv = (iv == IV_MIN) ? (UV)iv : (UV)(-iv)

with simpler and more optimal:

  uv = -(UV)iv

While -iv indeed results in an undefined behaviour when iv == IV_MIN,
-(UV)iv is perfectly well defined and does the right thing.

C standard guarantees that the result of (UV)iv (for negative iv) is
equal to iv + UV_MAX + 1 (see 6.3.1.3, paragraph 2 in C11). It also
guarantees that the result of -uv is UV_MAX - uv + 1 (6.2.5,
paragraph 9).

That means that the result of -(UV)iv is UV_MAX - (iv + UV_MAX + 1) + 1
which is equal to -iv for *all* possible negative values of iv.

[perl #133677]
---
 pp.c     | 18 +++++++++---------
 pp_hot.c |  4 ++--
 sv.c     |  4 ++--
 3 files changed, 13 insertions(+), 13 deletions(-)

diff --git a/pp.c b/pp.c
index 6d432acd31..880f266081 100644
--- a/pp.c
+++ b/pp.c
@@ -1319,7 +1319,7 @@ PP(pp_multiply)
 		    auvok = TRUE; /* effectively it's a UV now */
 		} else {
                     /* abs, auvok == false records sign */
-		    alow = (aiv == IV_MIN) ? (UV)aiv : (UV)(-aiv);
+		    alow = -(UV)aiv;
 		}
 	    }
 	    if (buvok) {
@@ -1331,7 +1331,7 @@ PP(pp_multiply)
 		    buvok = TRUE; /* effectively it's a UV now */
 		} else {
                     /* abs, buvok == false records sign */
-		    blow = (biv == IV_MIN) ? (UV)biv : (UV)(-biv);
+		    blow = -(UV)biv;
 		}
 	    }
 
@@ -1462,7 +1462,7 @@ PP(pp_divide)
                     right_non_neg = TRUE; /* effectively it's a UV now */
                 }
 		else {
-                    right = (biv == IV_MIN) ? (UV)biv : (UV)(-biv);
+                    right = -(UV)biv;
                 }
             }
             /* historically undef()/0 gives a "Use of uninitialized value"
@@ -1483,7 +1483,7 @@ PP(pp_divide)
                     left_non_neg = TRUE; /* effectively it's a UV now */
                 }
 		else {
-                    left = (aiv == IV_MIN) ? (UV)aiv : (UV)(-aiv);
+                    left = -(UV)aiv;
                 }
             }
 
@@ -1566,7 +1566,7 @@ PP(pp_modulo)
                     right = biv;
                     right_neg = FALSE; /* effectively it's a UV now */
                 } else {
-                    right = (biv == IV_MIN) ? (UV)biv : (UV)(-biv);
+                    right = -(UV)biv;
                 }
             }
         }
@@ -1596,7 +1596,7 @@ PP(pp_modulo)
                         left = aiv;
                         left_neg = FALSE; /* effectively it's a UV now */
                     } else {
-                        left = (aiv == IV_MIN) ? (UV)aiv : (UV)(-aiv);
+                        left = -(UV)aiv;
                     }
                 }
         }
@@ -1893,8 +1893,8 @@ PP(pp_subtract)
 		    if (aiv >= 0) {
 			auv = aiv;
 			auvok = 1;	/* Now acting as a sign flag.  */
-		    } else { /* 2s complement assumption for IV_MIN */
-			auv = (aiv == IV_MIN) ? (UV)aiv : (UV)-aiv;
+		    } else {
+			auv = -(UV)aiv;
 		    }
 		}
 		a_valid = 1;
@@ -1914,7 +1914,7 @@ PP(pp_subtract)
 		    buv = biv;
 		    buvok = 1;
 		} else
-                    buv = (biv == IV_MIN) ? (UV)biv : (UV)-biv;
+                    buv = -(UV)biv;
 	    }
 	    /* ?uvok if value is >= 0. basically, flagged as UV if it's +ve,
 	       else "IV" now, independent of how it came in.
diff --git a/pp_hot.c b/pp_hot.c
index dc02612042..ace5f0208b 100644
--- a/pp_hot.c
+++ b/pp_hot.c
@@ -1521,7 +1521,7 @@ PP(pp_add)
 			auv = aiv;
 			auvok = 1;	/* Now acting as a sign flag.  */
 		    } else {
-			auv = (aiv == IV_MIN) ? (UV)aiv : (UV)(-aiv);
+			auv = -(UV)aiv;
 		    }
 		}
 		a_valid = 1;
@@ -1541,7 +1541,7 @@ PP(pp_add)
 		    buv = biv;
 		    buvok = 1;
 		} else
-                    buv = (biv == IV_MIN) ? (UV)biv : (UV)(-biv);
+                    buv = -(UV)biv;
 	    }
 	    /* ?uvok if value is >= 0. basically, flagged as UV if it's +ve,
 	       else "IV" now, independent of how it came in.
diff --git a/sv.c b/sv.c
index 983646f335..b10f205033 100644
--- a/sv.c
+++ b/sv.c
@@ -2868,7 +2868,7 @@ S_uiv_2buf(char *const buf, const IV iv, UV uv, const int is_uv, char **const pe
 	uv = iv;
 	sign = 0;
     } else {
-        uv = (iv == IV_MIN) ? (UV)iv : (UV)(-iv);
+        uv = -(UV)iv;
 	sign = 1;
     }
     do {
@@ -12596,7 +12596,7 @@ Perl_sv_vcatpvfn_flags(pTHX_ SV *const sv, const char *const pat, const STRLEN p
                             esignbuf[esignlen++] = plus;
                     }
                     else {
-                        uv = (iv == IV_MIN) ? (UV)iv : (UV)(-iv);
+                        uv = -(UV)iv;
                         esignbuf[esignlen++] = '-';
                     }
                 }
-- 
2.14.1

@p5pRT

This comment has been minimized.

Copy link
Collaborator Author

commented Nov 21, 2018

@p5pRT

This comment has been minimized.

Copy link
Collaborator Author

commented Nov 21, 2018

From @iabyn

On Wed, Nov 21, 2018 at 01​:02​:02AM -0800, Tomasz Konojacki (via RT) wrote​:

In 2014 Dave fixed mishandling of IVs equal to IV_MIN in maaaaany places
in the perl codebase (that's why I'm CC-ing him). There were many
commits, for example 53e2bfb.

While the fix was perfectly good, it can be done in a bit more optimal
way. The commit message of my patch should explain the issue​:

---
optimize IV -> UV conversions

This commit replaces all instances of code that looks like this​:

uv = \(iv == IV\_MIN\) ? \(UV\)iv : \(UV\)\(\-iv\)

with simpler and more optimal​:

uv = \-\(UV\)iv

Thanks, applied as v5.29.5-9-gad9b9a4926

--
In economics, the exam questions are the same every year.
They just change the answers.

@p5pRT

This comment has been minimized.

Copy link
Collaborator Author

commented Nov 21, 2018

The RT System itself - Status changed from 'new' to 'open'

@p5pRT

This comment has been minimized.

Copy link
Collaborator Author

commented Nov 22, 2018

From @tonycoz

On Wed, 21 Nov 2018 05​:42​:27 -0800, davem wrote​:

Thanks, applied as v5.29.5-9-gad9b9a4926

Now closed.

Tony

@p5pRT

This comment has been minimized.

Copy link
Collaborator Author

commented Nov 22, 2018

@tonycoz - Status changed from 'open' to 'pending release'

@p5pRT

This comment has been minimized.

Copy link
Collaborator Author

commented May 22, 2019

From @khwilliamson

Thank you for filing this report. You have helped make Perl better.

With the release today of Perl 5.30.0, this and 160 other issues have been
resolved.

Perl 5.30.0 may be downloaded via​:
https://metacpan.org/release/XSAWYERX/perl-5.30.0

If you find that the problem persists, feel free to reopen this ticket.

@p5pRT

This comment has been minimized.

Copy link
Collaborator Author

commented May 22, 2019

@khwilliamson - Status changed from 'pending release' to 'resolved'

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
1 participant
You can’t perform that action at this time.