Feature #8509

Use 128 bit integer type in Bignum

Added by Akira Tanaka 10 months ago. Updated 5 months ago.

[ruby-dev:47413]
Status:Closed
Priority:Normal
Assignee:Akira Tanaka
Category:core
Target version:2.1.0

Description

How about Bignum uses 128 bit integer type?

I found that recent gcc (since gcc 4.6) supports 128 bit integer type,
__int128, on some platforms.
http://gcc.gnu.org/gcc-4.6/changes.html

It seems gcc supports it on x86_64 and not on i386.

Currently Ruby implements Bignum on top of 32 bit integer type (BDIGIT)
and 64 bit integer type (BDIGITDBL).
(Ruby uses two integer types for multiplication.
BDIGIT
DBL can represent any value of BDIGIT * BDIGIT.)

Historically, Ruby supported platforms without 64 bit integer type.
Ruby used 16 bit integer type (BDIGIT) and 32 bit integer type (BDIGIT_DBL)
on such platform.
However I guess no one use such platforms today.

So with gcc 4.6 or later, we can use 64 bit integer type (BDIGIT) and
128 bit integer type (BDIGIT_DBL).

This may gain performance.

I implemented it. (int128-bignum.patch)

Simple benchmark on Debian GNU/Linux 7.0 (wheezy) x86_64:

trunk% time ./ruby -e 'v = 31000; u = 1; 1000.times { u *= v }'
./ruby -e 'v = 3
1000; u = 1; 1000.times { u = v }' 1.64s user 0.00s system 99% cpu 1.655 total
128bit% time ./ruby -e 'v = 3
1000; u = 1; 1000.times { u *= v }'
./ruby -e 'v = 3
*1000; u = 1; 1000.times { u *= v }' 1.21s user 0.01s system 99% cpu 1.222 total

I think larger integer type reduces control overhead and compiler will have more opportunity for optimization.

However the patch has API incompatibility.

BDIGIT and BDIGIT_DBL and related definitions are defined in a public headers,
ruby/defines.h.

So third party extensions may be broken with the change.

Note that BDIGITDBL is a macro (not typedef name), compiler used for third party extension
don't need to support _
int128 unless the extension actually uses BDIGIT_DBL.

If a program try to extract information from a Bignum and assumes BDIGIT is 32 bit integer,
the result may be invalid.
In this situation rbbigpack/rbbigunpack or rbintegerpack/rbintegerunpack may help.

However BDIGIT size change itself may cause problems.

One example I patched is about rbbigpow.
int128-bignum.patch contains following modification for rbbigpow.

  • const long BIGLEN_LIMIT = BITSPERDIG10241024;
  • const long BIGLEN_LIMIT = 3210241024;

BIGLENLIMIT controls the rbbig_pow generates a Bignum or a Float.
If it is not modified, a test causes memory allocation failure.

Another problem is bigdecimal tests.
bigdecimal tests failed with int128-bignum.patch as follows.

1) Failure:
TestBigDecimal#testpowerofthree [/home/akr/tst1/ruby/test/bigdecimal/testbigdecimal.rb:1006]:
<(1/81)> expected but was
<#>.

2) Failure:
TestBigDecimal#testpowerwithprec [/home/akr/tst1/ruby/test/bigdecimal/testbigdecimal.rb:1110]:
<#> expected but was
<#>.

3) Failure:
TestBigDecimal#testpowerwithoutprec [/home/akr/tst1/ruby/test/bigdecimal/testbigdecimal.rb:1103]:
<#> expected but was
<#>.

4) Failure:
TestBigDecimal#testsqrtbigdecimal [/home/akr/tst1/ruby/test/bigdecimal/test_bigdecimal.rb:796]:
expected but was
<#>.

5) Failure:
TestBigMath#testatan [/home/akr/tst1/ruby/test/bigdecimal/testbigmath.rb:60]:
.
<#> expected but was
<#>.

I guess bigdecimal determines precision depend on sizeof(BDIGIT).
I think it is not a good way to use BDIGIT.

How do you think, mrkn?

Also, we cannot define PRIBDIGITDBLPREFIX because
there is no printf directive for _
int128.

Anyway, is Bignum with __int128 worth to support?
Any opinion?

int128-bignum.patch Magnifier (2.69 KB) Akira Tanaka, 06/10/2013 09:59 PM

Associated revisions

Revision 41379
Added by Akira Tanaka 10 months ago

  • configure.in: Check __int128.

  • include/ruby/defines.h (BDIGITDBL): Use uint128t if it is available.
    (BDIGIT): Use uint64t if uint128t is available.
    (SIZEOFBDIGITS): Defined for above case.
    (BDIGIT
    DBLSIGNED): Ditto.
    (PRI
    BDIGIT_PREFIX): Ditto.

  • include/ruby/ruby.h (PRI64PREFIX): Defined.

  • bignum.c (rbbigpow): Don't use BITSPERDIG for the condition which
    rbbigpow returns Float or Bignum.

[Feature #8509]

Revision 41502
Added by Akira Tanaka 10 months ago

  • ext/bigdecimal: Workaround fix for bigdecimal test failures caused
    by [Feature #8509]

  • ext/bigdecimal/bigdecimal.h (BDIGIT): Make it independent from the
    definition for bignum.c.
    (SIZEOFBDIGITS): Ditto.
    (BDIGIT
    DBL): Ditto.
    (BDIGITDBLSIGNED): Ditto.
    (PRIBDIGITPREFIX): Undefine the definition.
    (PRIBDIGITDBL_PREFIX): Ditto.

  • ext/bigdecimal/bigdecimal.c (RBIGNUMZEROP): Use rbbigzerop.
    (bigzerop): Removed.
    (is
    even): Use rbbigpack.

History

#1 Updated by Yui NARUSE 10 months ago

  • Category set to core
  • Status changed from Open to Assigned
  • Assignee set to Akira Tanaka
  • Target version set to 2.1.0

I'm ok about introducing this.

Anyway as far as I confirm, gcc 4.1 supports _int128t and _uint128t on x64.

#2 Updated by Kenta Murata 10 months ago

I think it should be merged.

I'm trying to change the bigdecimal's precision treatment
so that it's independent of the size of internal type (such as BDIGIT).
Bigdecimal's precision should be the number of decimal figures.
After it's done, these failures are removed.

On Mon, Jun 10, 2013 at 11:43 PM, naruse (Yui NARUSE) naruse@airemix.jp wrote:

Issue #8509 has been updated by naruse (Yui NARUSE).

Category set to core
Status changed from Open to Assigned
Assignee set to akr (Akira Tanaka)
Target version set to current: 2.1.0

I'm ok about introducing this.

Anyway as far as I confirm, gcc 4.1 supports _int128t and _uint128t on x64.

Feature #8509: Use 128 bit integer type in Bignum
https://bugs.ruby-lang.org/issues/8509#change-39842

Author: akr (Akira Tanaka)
Status: Assigned
Priority: Normal
Assignee: akr (Akira Tanaka)
Category: core
Target version: current: 2.1.0

How about Bignum uses 128 bit integer type?

I found that recent gcc (since gcc 4.6) supports 128 bit integer type,
__int128, on some platforms.
http://gcc.gnu.org/gcc-4.6/changes.html

It seems gcc supports it on x86_64 and not on i386.

Currently Ruby implements Bignum on top of 32 bit integer type (BDIGIT)
and 64 bit integer type (BDIGITDBL).
(Ruby uses two integer types for multiplication.
BDIGIT
DBL can represent any value of BDIGIT * BDIGIT.)

Historically, Ruby supported platforms without 64 bit integer type.
Ruby used 16 bit integer type (BDIGIT) and 32 bit integer type (BDIGIT_DBL)
on such platform.
However I guess no one use such platforms today.

So with gcc 4.6 or later, we can use 64 bit integer type (BDIGIT) and
128 bit integer type (BDIGIT_DBL).

This may gain performance.

I implemented it. (int128-bignum.patch)

Simple benchmark on Debian GNU/Linux 7.0 (wheezy) x86_64:

trunk% time ./ruby -e 'v = 31000; u = 1; 1000.times { u *= v }'
./ruby -e 'v = 3
1000; u = 1; 1000.times { u = v }' 1.64s user 0.00s system 99% cpu 1.655 total
128bit% time ./ruby -e 'v = 3
1000; u = 1; 1000.times { u *= v }'
./ruby -e 'v = 3
*1000; u = 1; 1000.times { u *= v }' 1.21s user 0.01s system 99% cpu 1.222 total

I think larger integer type reduces control overhead and compiler will have more opportunity for optimization.

However the patch has API incompatibility.

BDIGIT and BDIGIT_DBL and related definitions are defined in a public headers,
ruby/defines.h.

So third party extensions may be broken with the change.

Note that BDIGITDBL is a macro (not typedef name), compiler used for third party extension
don't need to support _
int128 unless the extension actually uses BDIGIT_DBL.

If a program try to extract information from a Bignum and assumes BDIGIT is 32 bit integer,
the result may be invalid.
In this situation rbbigpack/rbbigunpack or rbintegerpack/rbintegerunpack may help.

However BDIGIT size change itself may cause problems.

One example I patched is about rbbigpow.
int128-bignum.patch contains following modification for rbbigpow.

  • const long BIGLEN_LIMIT = BITSPERDIG10241024;
  • const long BIGLEN_LIMIT = 3210241024;

BIGLENLIMIT controls the rbbig_pow generates a Bignum or a Float.
If it is not modified, a test causes memory allocation failure.

Another problem is bigdecimal tests.
bigdecimal tests failed with int128-bignum.patch as follows.

1) Failure:
TestBigDecimal#testpowerofthree [/home/akr/tst1/ruby/test/bigdecimal/testbigdecimal.rb:1006]:
<(1/81)> expected but was
<#>.

2) Failure:
TestBigDecimal#testpowerwithprec [/home/akr/tst1/ruby/test/bigdecimal/testbigdecimal.rb:1110]:
<#> expected but was
<#>.

3) Failure:
TestBigDecimal#testpowerwithoutprec [/home/akr/tst1/ruby/test/bigdecimal/testbigdecimal.rb:1103]:
<#> expected but was
<#>.

4) Failure:
TestBigDecimal#testsqrtbigdecimal [/home/akr/tst1/ruby/test/bigdecimal/test_bigdecimal.rb:796]:
expected but was
<#>.

5) Failure:
TestBigMath#testatan [/home/akr/tst1/ruby/test/bigdecimal/testbigmath.rb:60]:
.
<#> expected but was
<#>.

I guess bigdecimal determines precision depend on sizeof(BDIGIT).
I think it is not a good way to use BDIGIT.

How do you think, mrkn?

Also, we cannot define PRIBDIGITDBLPREFIX because
there is no printf directive for _
int128.

Anyway, is Bignum with __int128 worth to support?
Any opinion?

http://bugs.ruby-lang.org/

--
Kenta Murata
OpenPGP FP = 1D69 ADDE 081C 9CC2 2E54 98C1 CEFE 8AFB 6081 B062

本を書きました!!
『Ruby 逆引きレシピ』 http://www.amazon.co.jp/dp/4798119881/mrkn-22

E-mail: mrkn@mrkn.jp
twitter: http://twitter.com/mrkn/
blog: http://d.hatena.ne.jp/mrkn/

#3 Updated by Akira Tanaka 10 months ago

  • Status changed from Assigned to Closed
  • % Done changed from 0 to 100

This issue was solved with changeset r41379.
Akira, thank you for reporting this issue.
Your contribution to Ruby is greatly appreciated.
May Ruby be with you.


  • configure.in: Check __int128.

  • include/ruby/defines.h (BDIGITDBL): Use uint128t if it is available.
    (BDIGIT): Use uint64t if uint128t is available.
    (SIZEOFBDIGITS): Defined for above case.
    (BDIGIT
    DBLSIGNED): Ditto.
    (PRI
    BDIGIT_PREFIX): Ditto.

  • include/ruby/ruby.h (PRI64PREFIX): Defined.

  • bignum.c (rbbigpow): Don't use BITSPERDIG for the condition which
    rbbigpow returns Float or Bignum.

[Feature #8509]

#4 Updated by Akira Tanaka 10 months ago

I committed the patch at r41379.

I hope mrkn will fix the BigDecimal test failures soon.

#5 Updated by Akira Tanaka 5 months ago

I decided to disable __int128 for Bignum because it is not always faster.

_int128 is still be usable by specifying CPPFLAGS for configure as:
configure CPPFLAGS='-DBDIGIT=uint64
t -DSIZEOFBDIGITS=8 -DBDIGITDBL=uint128t -DBDIGITDBLSIGNED=int128t -DSIZEOFBDIGITDBL=16'

Also available in: Atom PDF