Skip to content

Optimize integer-->string conversions#36470

Merged
musm merged 5 commits intoJuliaLang:masterfrom
kimikage:int2str
Oct 1, 2020
Merged

Optimize integer-->string conversions#36470
musm merged 5 commits intoJuliaLang:masterfrom
kimikage:int2str

Conversation

@kimikage
Copy link
Copy Markdown
Contributor

@kimikage kimikage commented Jun 29, 2020 •
edited
Loading

This avoids invalidations caused by invalidating StringVector(::Integer). (cf. PR #36459) (Edit: The problem has been solved by PR #36459.)
This also makes bin(), dec() and hex() slightly faster, but does not change the Printf.

julia> versioninfo() # on WSL
Julia Version 1.6.0-DEV.312
Commit 6185d24ac3 (2020-06-28 22:42 UTC)
Platform Info:
  OS: Linux (x86_64-pc-linux-gnu)
  CPU: Intel(R) Core(TM) i7-8565U CPU @ 1.80GHz
  WORD_SIZE: 64
  LIBM: libopenlibm
  LLVM: libLLVM-9.0.1 (ORCJIT, skylake)

julia> @btime string.(x, base=2) setup=(x=rand(Int64,1000));
  57.300 μs (2001 allocations: 151.67 KiB) # before
  38.400 μs (2001 allocations: 151.69 KiB) # after

julia> @btime string.(x, base=8) setup=(x=rand(Int64,1000));
  34.700 μs (2001 allocations: 117.30 KiB) # before
  34.800 μs (2001 allocations: 117.30 KiB) # after

julia> @btime string.(x, base=10) setup=(x=rand(Int64,1000));
  45.900 μs (2001 allocations: 117.27 KiB) # before
  35.400 μs (2001 allocations: 117.28 KiB) # after

julia> @btime string.(x, base=10) setup=(x=rand(Int32,1000));
  35.300 μs (2001 allocations: 101.69 KiB) # before
  31.300 μs (2001 allocations: 101.69 KiB) # after

julia> @btime string.(x, base=16) setup=(x=rand(Int64,1000));
  38.300 μs (2001 allocations: 115.84 KiB) # before
  33.600 μs (2001 allocations: 115.80 KiB) # after

@JeffBezanson JeffBezanson added the performance Must go faster label Jun 29, 2020
@JeffBezanson
Copy link
Copy Markdown
Member

JeffBezanson commented Jun 29, 2020

Awesome!

StefanKarpinski
StefanKarpinski reviewed Jun 29, 2020
View reviewed changes
timholy
timholy approved these changes Jun 29, 2020
View reviewed changes
Copy link
Copy Markdown
Member

@timholy timholy left a comment

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

This is a pretty performance-sensitive operation, so unrolling those loops is a great idea.

rfourquet
rfourquet reviewed Jun 30, 2020
View reviewed changes
@kimikage
Copy link
Copy Markdown
Contributor Author

kimikage commented Jul 2, 2020

@rfourquet, I appreciate your comment

I added the clamping into the string(), and changed the types of the pad of internal functions (e.g. bin()) from Integer to Int. Although we can leave them as Integer for "compatibility", I think there are no practical advantages.

I don't know the reason, but there is a little slowdown (~1 ns/number) from the original commit, but the unrolling is still effective.

@timholy timholy mentioned this pull request Jul 7, 2020
Merged
@timholy
Copy link
Copy Markdown
Member

timholy commented Aug 2, 2020

Bumping this. I don't have any objections to merging this.

@timholy timholy mentioned this pull request Aug 3, 2020
Merged
@kimikage
Copy link
Copy Markdown
Contributor Author

kimikage commented Aug 8, 2020

Since PR #36459 was merged, the ::Int for leading_zeros(x) doesn't seem to be needed anymore.

@musm
Copy link
Copy Markdown
Contributor

musm commented Sep 19, 2020

Looks like this PR has been approved, is it ok to merge?

@KristofferC KristofferC reopened this Sep 19, 2020
musm
musm reviewed Sep 26, 2020
View reviewed changes
musm
musm reviewed Sep 26, 2020
View reviewed changes
musm
musm reviewed Sep 26, 2020
View reviewed changes
@kimikage
Optimize integer-->string conversions
5ca8669 
This avoids invalidations caused by invalidating `StringVector(::Integer)`.
This also makes `bin()`, `dec`() and `hex()` slightly faster,
but does not change the Printf.
@kimikage
Change pad option handling
6e06b3d
@kimikage
Omit unnecessary type assertions
ba0839e
@kimikage
Add out-of-range base tests
bd69475
@kimikage
Modify multiplication notation
45582ec
@StefanKarpinski
Copy link
Copy Markdown
Member

StefanKarpinski commented Sep 29, 2020

I've kicked off the failed CI runs, which looked unrelated. This seems good once CI passes.

@StefanKarpinski StefanKarpinski added the merge me PR is reviewed. Merge when all tests are passing label Sep 29, 2020
@musm musm merged commit e7872b3 into JuliaLang:master Oct 1, 2020
@kimikage
Copy link
Copy Markdown
Contributor Author

kimikage commented Oct 1, 2020

Thanks!

@kimikage kimikage deleted the int2str branch October 1, 2020 23:43
@kimikage
Copy link
Copy Markdown
Contributor Author

kimikage commented Oct 3, 2020 •
edited
Loading

I'm sorry, but I may have broken something.
cc: @rfourquet
https://github.com/JuliaCI/NanosoldierReports/blob/c1103cd2398e1d0442f115264893823991742a66/pkgeval/by_date/2020-10/01/logs/BitIntegers/1.6.0-DEV-2fe2b43606.log

Edit:
Perhaps the cause is the type of bit shifting.

julia/base/intfuncs.jl

Line 633 in 36effbe

x >>= 0x4

Can you fix this on the BitIntegers.jl side? (cf. rfourquet/BitIntegers.jl#13)

@rfourquet
Copy link
Copy Markdown
Member

rfourquet commented Oct 4, 2020

Perhaps the cause is the type of bit shifting.

@kimikage Thank you for the report, I had no idea this x << 0x4 was broken in BitIntegers.

@DilumAluthge DilumAluthge removed the merge me PR is reviewed. Merge when all tests are passing label Jan 11, 2021
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Reviewers

@StefanKarpinski StefanKarpinski StefanKarpinski left review comments

@rfourquet rfourquet rfourquet left review comments

@timholy timholy timholy approved these changes

+1 more reviewer

@musm musm musm left review comments

Reviewers whose approvals may not affect merge requirements

Assignees

No one assigned

Labels

performance Must go faster

Projects

None yet

Milestone

No milestone

Development

Successfully merging this pull request may close these issues.

8 participants

@kimikage @JeffBezanson @timholy @musm @StefanKarpinski @rfourquet @KristofferC @DilumAluthge