Skip Menu |
Report information
Id: 133691
Status: resolved
Priority: 0/
Queue: perl5

Owner: Nobody
Requestors: me [at] xenu.pl
Cc:
AdminCc:

Operating System: (no value)
PatchStatus: (no value)
Severity: low
Type: unknown
Perl Version: (no value)
Fixed In: (no value)



To: perlbug [...] perl.org
From: Tomasz Konojacki <me [...] xenu.pl>
Date: Wed, 28 Nov 2018 13:39:14 +0100
Subject: [PATCH] faster integer stringification algorithm
CC: public [...] khwilliamson.com
Download (untitled) / with headers
text/plain 4.9k
This patch speed-ups int stringification in perl. The algorithm works on big endian machines (I have tested it on emulated s390x linux), it doesn't cause unaligned reads/writes and I'm 90% sure it will work on EBCDIC platforms (CC-ing Karl to get his opinion). For single digit numbers there's basically no difference in performance, but for larger integers there's a noticeable gain: 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%. one_digit one digit (positive) blead my_patch ------ -------- Ir 100.00 100.84 Dr 100.00 100.41 Dw 100.00 100.00 COND 100.00 99.28 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_digit_neg one digit (negative) blead my_patch ------ -------- Ir 100.00 100.71 Dr 100.00 100.00 Dw 100.00 100.00 COND 100.00 99.26 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_digits two digits (positive) blead my_patch ------ -------- Ir 100.00 102.26 Dr 100.00 100.00 Dw 100.00 100.79 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 two_digits_neg two digits (negative) blead my_patch ------ -------- Ir 100.00 102.13 Dr 100.00 99.60 Dw 100.00 100.79 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 four_digits four digits (positive) blead my_patch ------ -------- Ir 100.00 103.41 Dr 100.00 99.60 Dw 100.00 101.57 COND 100.00 100.75 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 four_digits_neg four digits (negative) blead my_patch ------ -------- Ir 100.00 103.27 Dr 100.00 99.20 Dw 100.00 101.56 COND 100.00 100.75 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 five_digits five digits (positive) blead my_patch ------ -------- Ir 100.00 103.24 Dr 100.00 99.60 Dw 100.00 101.56 COND 100.00 100.74 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 five_digits_neg five digits (negative) blead my_patch ------ -------- Ir 100.00 102.68 Dr 100.00 99.34 Dw 100.00 101.28 COND 100.00 100.64 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 eighteen_digits eighteen digits (positive) blead my_patch ------ -------- Ir 100.00 109.78 Dr 100.00 97.39 Dw 100.00 105.59 COND 100.00 105.06 IND 100.00 100.00 COND_m 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 eighteen_digits_neg eighteen digits (negative) blead my_patch ------ -------- Ir 100.00 109.64 Dr 100.00 97.08 Dw 100.00 105.56 COND 100.00 105.06 IND 100.00 100.00 COND_m 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 103.71 Dr 100.00 99.21 Dw 100.00 101.83 COND 100.00 101.11 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
Subject: Re: [perl #133691] [PATCH] faster integer stringification algorithm
Date: Wed, 28 Nov 2018 13:43:43 +0100
To: perl5-porters [...] perl.org
CC: public [...] khwilliamson.com
From: Tomasz Konojacki <me [...] xenu.pl>
The patch and benchmark's source code are attached.

Message body is not shown because sender requested not to inline it.

Download stringification_bench
application/octet-stream 1.2k

Message body not shown because it is not plain text.

RT-Send-CC: perl5-porters [...] perl.org
Download (untitled) / with headers
text/plain 242b
On Wed, 28 Nov 2018 12:43:59 GMT, me@xenu.pl wrote: Show quoted text
> The patch and benchmark's source code are attached.
Available for smoke-testing in this branch: smoke-me/jkeenan/xenu/133691-integer-stringification -- James E Keenan (jkeenan@cpan.org)
RT-Send-CC: perl5-porters [...] perl.org
On Wed, 28 Nov 2018 14:01:58 GMT, jkeenan wrote: Show quoted text
> On Wed, 28 Nov 2018 12:43:59 GMT, me@xenu.pl wrote:
> > The patch and benchmark's source code are attached.
> > Available for smoke-testing in this branch: > > smoke-me/jkeenan/xenu/133691-integer-stringification
This appears to be failing consistently on -DDEBUGGING builds on smoke-testing rigs that normally PASS. See, e.g., http://perl5.test-smoke.org/report/74928 Configuring on Linux with simply '-des -Dusedevel -DDEBUGGING', 'make' fails for me here: ##### cc -c -DPERL_CORE -fwrapv -DDEBUGGING -fno-strict-aliasing -pipe -fstack-protector-strong -I/usr/local/include -D_LARGEFILE_SOURCE -D_FILE_OFFSET_BITS=64 -std=c89 -O2 -g -Wall -Werror=declaration-after-statement -Werror=pointer-arith -Wextra -Wc++-compat -Wwrite-strings sv.c In file included from perl.h:3399:0, from sv.c:32: sv.c: In function ‘S_uiv_2buf’: sv.c:2889:16: error: invalid operands to binary % (have ‘char *’ and ‘int’) assert(ptr % 2 == 0); ^ makefile:249: recipe for target 'sv.o' failed ##### -- James E Keenan (jkeenan@cpan.org)
CC: perl5-porters [...] perl.org, public [...] khwilliamson.com
From: Tony Cook <tony [...] develop-help.com>
Date: Thu, 29 Nov 2018 11:32:52 +1100
Subject: Re: [perl #133691] [PATCH] faster integer stringification algorithm
To: Tomasz Konojacki <me [...] xenu.pl>
Download (untitled) / with headers
text/plain 466b
On Wed, Nov 28, 2018 at 01:43:43PM +0100, Tomasz Konojacki wrote: Show quoted text
> The patch and benchmark's source code are attached.
This code makes some assumptions about alignment that I don't think we can depend on: - it assumes int2str_table[] will be U16 aligned. - it assumes buf[] will be U16 aligned. I believe neither is guaranteed by the C standard. As James' smoke tests point out, the assertion isn't valid C, since a pointer doesn't have arithmetic type. Tony
Date: Thu, 29 Nov 2018 11:56:39 +0100
Subject: Re: [perl #133691] [PATCH] faster integer stringification algorithm
To: Tony Cook <tony [...] develop-help.com>, perl5-porters [...] perl.org
From: Tomasz Konojacki <me [...] xenu.pl>
Download (untitled) / with headers
text/plain 893b
On Thu, 29 Nov 2018 11:32:52 +1100 Tony Cook <tony@develop-help.com> wrote: Show quoted text
> This code makes some assumptions about alignment that I don't think we > can depend on: > > - it assumes int2str_table[] will be U16 aligned. > > - it assumes buf[] will be U16 aligned. > > I believe neither is guaranteed by the C standard.
Good catch! It is indeed not guaranteed. For some reason I was assuming that stack arrays are aligned in the same way as malloc()ed memory, but that is obviously not the case. Show quoted text
> > As James' smoke tests point out, the assertion isn't valid C, since a > pointer doesn't have arithmetic type.
Argh, that's what I get for not testing last minute changes :( I have attached updated version of the patch. Performance is the same, but the code is now a bit uglier. Unfortunately I'm not aware of a better way to ensure array alignment than using unions with dummy members.
Download updated.patch
text/plain 6.5k

Message body is not shown because sender requested not to inline it.

Date: Thu, 29 Nov 2018 12:27:16 +0100
Subject: Re: [perl #133691] [PATCH] faster integer stringification algorithm
To: perl5-porters [...] perl.org, Tony Cook <tony [...] develop-help.com>
From: Tomasz Konojacki <me [...] xenu.pl>
Download (untitled) / with headers
text/plain 375b
On Thu, 29 Nov 2018 11:56:39 +0100 Tomasz Konojacki <me@xenu.pl> wrote: Show quoted text
> I have attached updated version of the patch. Performance is the same, but > the code is now a bit uglier. Unfortunately I'm not aware of a better > way to ensure array alignment than using unions with dummy members.
Oops, looks like it has introduced a few hard tabs. The fixed version is attached.
Download updated2.patch
text/plain 6.6k

Message body is not shown because sender requested not to inline it.

RT-Send-CC: perl5-porters [...] perl.org
Download (untitled) / with headers
text/plain 515b
On Thu, 29 Nov 2018 03:27:41 -0800, me@xenu.pl wrote: Show quoted text
> On Thu, 29 Nov 2018 11:56:39 +0100 > Tomasz Konojacki <me@xenu.pl> wrote: >
> > I have attached updated version of the patch. Performance is the same, but > > the code is now a bit uglier. Unfortunately I'm not aware of a better > > way to ensure array alignment than using unions with dummy members.
> > Oops, looks like it has introduced a few hard tabs. The fixed version is > attached.
Thanks, applied as dd0a5f5f02475a77bd12a1a4b201e77be6eaa969. Tony
Download (untitled) / with headers
text/plain 313b
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.


This service is sponsored and maintained by Best Practical Solutions and runs on Perl.org infrastructure.

For issues related to this RT instance (aka "perlbug"), please contact perlbug-admin at perl.org