Re: [webkit-dev] BigInt implementation

[Robin Morisset]

Hello,

That sounds good to me.

Best regards,
Robin

> On Oct 20, 2017, at 17:06, Caio Lima  wrote:
> 
> 2017-10-20 12:21 GMT-02:00 Robin Morisset  >:
> Hello,
> 
> I was planning to start implementing the BigInt proposal as soon as I am done 
> optimizing tail calls and tweaking the inliner (probably within a month).
> 
> That's good to know. According the plan you sent, it seems that I could work 
> on item 1 which means implement Parsing,
> naive implementation and spec defined operations. After that, there is a 
> plenty of work to be done on optimization/JIT part, as you mentioned, mainly 
> because Int64 usage is intended to be used with BigInt. On other steps, I 
> also could help you, if you are interested as well. So my proposal is:
> 
> I will start the work on implement parsing and first model of BigInt 
> allocation into JSCell and then go through operations defined by spec, 
> following naive algorithms. I think I could finish it before you start and 
> then we could sync in which part we could work. Does it sound like a plan?
> 
> Regards,
> Caio.
>  
> My plan was to proceed in several steps:
> First a very naive implementation, treating them as fairly new kind of 
> JSCell, with all the data in the butterfly; and very simple algorithms for 
> the arithmetic.
> Implement some interesting benchmark, probably a port of some crypto library 
> + some miscellaneous arithmetic.
> Inline some of the data in the cell itself when we can reasonably estimate 
> its size (takes us from 2 to 1 indirection in the common case).
> For “small” big ints, put them directly in the JSValue, through some encoding 
> trick. Huge gain for most code, but likely to be very tricky in my opinion
> Use fancy, state-of-the art algorithms/operations for the arithmetic 
> operations. This should probably not happen earlier, to avoid baking in the 
> location of the data.
> Add an optimization phase that turns big ints into normal ints when 
> static/dynamic analysis tells us they are guaranteed to be small. This should 
> happen last so it can be benchmarked in realistic conditions since we are not 
> sure it will be a win.
> I am not opposed to the idea of reusing a library, but I am not sure how to 
> make sure it will let us put the data wherever we need (with special cases 
> such as small bigInts fitting inside a single JSValue).
> 
> Best regards,
> Robin
> 
>> On Oct 20, 2017, at 06:49, Jordi Montes > > wrote:
>> 
>> Hello Filip,
>> 
>> I spent some time looking for the perfect library to implement BigInts in JS 
>> some months ago and I did not find any match. Many of the C++ librearies 
>> have or a license problem (GMP, MPFR..), or need the size of the integer at 
>> compile time (ttmath,..) or two indirections header + the number 
>> (libtommath).
>> 
>> I looked for how other programs with GC implemented it. I checked in detail 
>> how Python (CPython) had it implemented and they have something like:
>> 
>> 
>> struct _longobject {
>>  PyObject_VAR_HEAD
>>  digit ob_digit[1];
>> };
>> 
>> So no indirection is needed to interact with the number itself. (Link to 
>> longObject in CPython 
>> )
>> 
>> 
>> As Dan pointed out, I started to implement a library based in 
>> libtommath/CPython BigInts but it is in an early stage. Mozilla is using GMP 
>> because they do not have any license problem but the other browsers do. My 
>> advice would be to start with the V8's implementation as you said.
>> 
>> 
>> Let me know if you need help with anything else, I am glad to help :)
>> 
>> 
>> P.S.: I was not subrscibed toOn 20 October 2017 at 06:44, Jordi Montes 
>> > wrote:
>> Hello Filip,
>> 
>> I spent some time looking for the perfect library to implement BigInts in JS 
>> some months ago and I did not find any match. Many of the C++ librearies 
>> have or a license problem (GMP, MPFR..), or need the size of the integer at 
>> compile time (ttmath,..) or two indirections header + the number 
>> (libtommath).
>> 
>> I looked for how other programs with GC implemented it. I checked in detail 
>> how Python (CPython) had it implemented and they have something like:
>> 
>> 
>> struct _longobject {
>>  PyObject_VAR_HEAD
>>  digit ob_digit[1];
>> };
>> 
>> So no indirection is needed to interact with the number itself. (Link to 
>> longObject in CPython 
>> )
>> 
>> 
>> As Dan pointed out, I started to implement a library based in 
>> libtommath/CPython BigInts but it is in an early stage. Mozilla is using GMP 
>> because they do not have any license problem but the other browsers do. My 
>> advice would be to start with the V8's implementation 

Re: [webkit-dev] BigInt implementation

[Robin Morisset]

Hello,

I was planning to start implementing the BigInt proposal as soon as I am done 
optimizing tail calls and tweaking the inliner (probably within a month).
My plan was to proceed in several steps:
First a very naive implementation, treating them as fairly new kind of JSCell, 
with all the data in the butterfly; and very simple algorithms for the 
arithmetic.
Implement some interesting benchmark, probably a port of some crypto library + 
some miscellaneous arithmetic.
Inline some of the data in the cell itself when we can reasonably estimate its 
size (takes us from 2 to 1 indirection in the common case).
For “small” big ints, put them directly in the JSValue, through some encoding 
trick. Huge gain for most code, but likely to be very tricky in my opinion
Use fancy, state-of-the art algorithms/operations for the arithmetic 
operations. This should probably not happen earlier, to avoid baking in the 
location of the data.
Add an optimization phase that turns big ints into normal ints when 
static/dynamic analysis tells us they are guaranteed to be small. This should 
happen last so it can be benchmarked in realistic conditions since we are not 
sure it will be a win.
I am not opposed to the idea of reusing a library, but I am not sure how to 
make sure it will let us put the data wherever we need (with special cases such 
as small bigInts fitting inside a single JSValue).

Best regards,
Robin

> On Oct 20, 2017, at 06:49, Jordi Montes  wrote:
> 
> Hello Filip,
> 
> I spent some time looking for the perfect library to implement BigInts in JS 
> some months ago and I did not find any match. Many of the C++ librearies have 
> or a license problem (GMP, MPFR..), or need the size of the integer at 
> compile time (ttmath,..) or two indirections header + the number (libtommath).
> 
> I looked for how other programs with GC implemented it. I checked in detail 
> how Python (CPython) had it implemented and they have something like:
> 
> 
> struct _longobject {
>   PyObject_VAR_HEAD
>   digit ob_digit[1];
> };
> 
> So no indirection is needed to interact with the number itself. (Link to 
> longObject in CPython 
> )
> 
> 
> As Dan pointed out, I started to implement a library based in 
> libtommath/CPython BigInts but it is in an early stage. Mozilla is using GMP 
> because they do not have any license problem but the other browsers do. My 
> advice would be to start with the V8's implementation as you said.
> 
> 
> Let me know if you need help with anything else, I am glad to help :)
> 
> 
> P.S.: I was not subrscibed toOn 20 October 2017 at 06:44, Jordi Montes 
> > wrote:
> Hello Filip,
> 
> I spent some time looking for the perfect library to implement BigInts in JS 
> some months ago and I did not find any match. Many of the C++ librearies have 
> or a license problem (GMP, MPFR..), or need the size of the integer at 
> compile time (ttmath,..) or two indirections header + the number (libtommath).
> 
> I looked for how other programs with GC implemented it. I checked in detail 
> how Python (CPython) had it implemented and they have something like:
> 
> 
> struct _longobject {
>   PyObject_VAR_HEAD
>   digit ob_digit[1];
> };
> 
> So no indirection is needed to interact with the number itself. (Link to 
> longObject in CPython 
> )
> 
> 
> As Dan pointed out, I started to implement a library based in 
> libtommath/CPython BigInts but it is in an early stage. Mozilla is using GMP 
> because they do not have any license problem but the other browsers do. My 
> advice would be to start with the V8's implementation as you said.
> 
> 
> Let me know if you need help with anything else, I am glad to help :)
> 
> 
> Jordi.
> 
> the mailing list, sorry if you recived this message more than once.
> 
> Jordi.
> 
> 
> 
> 
> On 19 October 2017 at 15:32, Filip Pizlo  > wrote:
> Seems like V8’s is an ok place to start. Maybe all you’d have to do is remove 
> the accurate GC artifacts (Handle and such).
> 
> -Filip
> 
> > On Oct 19, 2017, at 2:31 AM, Daniel Ehrenberg  > > wrote:
> >
> > On 2017-10-19 03:18, Filip Pizlo wrote:
> >>> On Oct 18, 2017, at 5:50 PM, Caio Lima  >>> > wrote:
> >>>
> >>> Hi WebKittens.
> >>>
> >>> I’m planning to start implement JS BigInt proposal on JSC, however I
> >>> would like to sync with you the way you are planning to implement such
> >>> feature.
> >>>
> >>> Right now, I’m thinking in implement BigInt operations into C++
> >>> (possibly on WTF?) and make the JSBigInt use this implementation.
> >>
> >> We need something GC-optimized from the start since that 

Re: [webkit-dev] BigInt implementation

[Jordi Montes]

Hello Filip,

I spent some time looking for the perfect library to implement BigInts in
JS some months ago and I did not find any match. Many of the C++ librearies
have or a license problem (GMP, MPFR..), or need the size of the integer at
compile time (ttmath,..) or two indirections header + the number
(libtommath).

I looked for how other programs with GC implemented it. I checked in detail
how Python (CPython) had it implemented and they have something like:


struct _longobject {
 PyObject_VAR_HEAD
 digit ob_digit[1];
};

So no indirection is needed to interact with the number itself. (Link to
longObject in CPython

)


As Dan pointed out, I started to implement a library based in
libtommath/CPython BigInts but it is in an early stage. Mozilla is using
GMP because they do not have any license problem but the other browsers do.
My advice would be to start with the V8's implementation as you said.


Let me know if you need help with anything else, I am glad to help :)


P.S.: I was not subrscibed toOn 20 October 2017 at 06:44, Jordi Montes <
joms...@gmail.com> wrote:
Hello Filip,

I spent some time looking for the perfect library to implement BigInts in
JS some months ago and I did not find any match. Many of the C++ librearies
have or a license problem (GMP, MPFR..), or need the size of the integer at
compile time (ttmath,..) or two indirections header + the number
(libtommath).

I looked for how other programs with GC implemented it. I checked in detail
how Python (CPython) had it implemented and they have something like:


struct _longobject {
 PyObject_VAR_HEAD
 digit ob_digit[1];
};

So no indirection is needed to interact with the number itself. (Link to
longObject in CPython

)


As Dan pointed out, I started to implement a library based in
libtommath/CPython BigInts but it is in an early stage. Mozilla is using
GMP because they do not have any license problem but the other browsers do.
My advice would be to start with the V8's implementation as you said.


Let me know if you need help with anything else, I am glad to help :)


Jordi.

the mailing list, sorry if you recived this message more than once.

Jordi.



>
> On 19 October 2017 at 15:32, Filip Pizlo  wrote:
>
>> Seems like V8’s is an ok place to start. Maybe all you’d have to do is
>> remove the accurate GC artifacts (Handle and such).
>>
>> -Filip
>>
>> > On Oct 19, 2017, at 2:31 AM, Daniel Ehrenberg 
>> wrote:
>> >
>> > On 2017-10-19 03:18, Filip Pizlo wrote:
>> >>> On Oct 18, 2017, at 5:50 PM, Caio Lima  wrote:
>> >>>
>> >>> Hi WebKittens.
>> >>>
>> >>> I’m planning to start implement JS BigInt proposal on JSC, however I
>> >>> would like to sync with you the way you are planning to implement such
>> >>> feature.
>> >>>
>> >>> Right now, I’m thinking in implement BigInt operations into C++
>> >>> (possibly on WTF?) and make the JSBigInt use this implementation.
>> >>
>> >> We need something GC-optimized from the start since that will
>> >> determine a lot of the details. So, I don’t think that a WTF
>> >> implementation is appropriate. It should be a JSCell from day one.
>> >>
>> >>> As I
>> >>> have checked with some other implementors, some of them are going to
>> >>> use libgmp (SpiderMonkey case), but I don’t think its license (GPLv2)
>> >>> aligns with WebKit’s license and I heard that V8 is implementing their
>> >>> BigInt lib as well. By now, I’m thinking in implement a proof of
>> >>> concept and then, optimize the BigInt lib part. So, what I would like
>> >>> to collect from you is: Is there any problem start work on that
>> >>> feature?
>> >>
>> >> We should do a GC-optimized bigint. If there was a great library that
>> >> had the right license, we could port it to allocate using our GC. I
>> >> don’t have a strong view on whether we should write our own from
>> >> scratch or use somebody else’s as a starting point (so long as the
>> >> license is ok).
>> >
>> > I'm not sure if there is such a great library. The other programming
>> > languages I've seen BigInt implementations in were either based on
>> > external libraries and didn't have GC integration, or were based on
>> > writing their own BigInt library or forking it from another programming
>> > language. I'm not aware of an existing BigInt library which permits GC
>> > integration.
>> >
>> > If GC optimization weren't needed,then libtommath [1] could be a good
>> > choice. However, this does not store BigInts in a single contiguous
>> > memory region, but rather has a header and discontiguous payload. I
>> > believe Jordi Montes (cc'd) is working on a library based on libtommath
>> > which would work more like this, but I'm not sure how far along it is,
>> > or how well it would integrate 

Re: [webkit-dev] BigInt implementation

[Michael Catanzaro]

On Wed, Oct 18, 2017 at 7:50 PM, Caio Lima  wrote:
As I have checked with some other implementors, some of them are 
going to use libgmp (SpiderMonkey case), but I don’t think its 
license (GPLv2) aligns with WebKit’s license and I heard that V8 is 
implementing their BigInt lib as well.


This license of GMP is (LGPLv3+ or GPLv2+). But yes, that means it's 
not an acceptable dependency for WebKit unfortunately.


___
webkit-dev mailing list
webkit-dev@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-dev

Re: [webkit-dev] BigInt implementation

[Filip Pizlo]

Seems like V8’s is an ok place to start. Maybe all you’d have to do is remove 
the accurate GC artifacts (Handle and such). 

-Filip

> On Oct 19, 2017, at 2:31 AM, Daniel Ehrenberg  wrote:
> 
> On 2017-10-19 03:18, Filip Pizlo wrote:
>>> On Oct 18, 2017, at 5:50 PM, Caio Lima  wrote:
>>> 
>>> Hi WebKittens.
>>> 
>>> I’m planning to start implement JS BigInt proposal on JSC, however I
>>> would like to sync with you the way you are planning to implement such
>>> feature.
>>> 
>>> Right now, I’m thinking in implement BigInt operations into C++
>>> (possibly on WTF?) and make the JSBigInt use this implementation.
>> 
>> We need something GC-optimized from the start since that will
>> determine a lot of the details. So, I don’t think that a WTF
>> implementation is appropriate. It should be a JSCell from day one.
>> 
>>> As I
>>> have checked with some other implementors, some of them are going to
>>> use libgmp (SpiderMonkey case), but I don’t think its license (GPLv2)
>>> aligns with WebKit’s license and I heard that V8 is implementing their
>>> BigInt lib as well. By now, I’m thinking in implement a proof of
>>> concept and then, optimize the BigInt lib part. So, what I would like
>>> to collect from you is: Is there any problem start work on that
>>> feature?
>> 
>> We should do a GC-optimized bigint. If there was a great library that
>> had the right license, we could port it to allocate using our GC. I
>> don’t have a strong view on whether we should write our own from
>> scratch or use somebody else’s as a starting point (so long as the
>> license is ok).
> 
> I'm not sure if there is such a great library. The other programming
> languages I've seen BigInt implementations in were either based on
> external libraries and didn't have GC integration, or were based on
> writing their own BigInt library or forking it from another programming
> language. I'm not aware of an existing BigInt library which permits GC
> integration.
> 
> If GC optimization weren't needed,then libtommath [1] could be a good
> choice. However, this does not store BigInts in a single contiguous
> memory region, but rather has a header and discontiguous payload. I
> believe Jordi Montes (cc'd) is working on a library based on libtommath
> which would work more like this, but I'm not sure how far along it is,
> or how well it would integrate into JSC GC.
> 
> If you want to follow the tradition of forking another library, one
> option would be to start with V8's. It's relatively new and not quite
> finished, but the nice thing is that it implements the same operations
> that will be needed in JSC. [2]
> 
> [1] http://www.libtom.net/LibTomMath/
> [2] https://github.com/v8/v8/blob/master/src/objects/bigint.cc
>> 
>> I don’t have any objection to you working on this.
>> 
>> -Filip
>> 
>>> 
>>> It is one of the proposals that I’ve made to my Coding Experience at
>>> Igalia, so I will also have the support of developers from there,
>>> since they are implementing it on SpiderMonkey and the spec champion
>>> is also in the team.
>>> 
>>> Regards,
>>> Caio.
>>> ___
>>> webkit-dev mailing list
>>> webkit-dev@lists.webkit.org
>>> https://lists.webkit.org/mailman/listinfo/webkit-dev
> 
___
webkit-dev mailing list
webkit-dev@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-dev

Re: [webkit-dev] BigInt implementation

[Filip Pizlo]

> On Oct 18, 2017, at 5:50 PM, Caio Lima  wrote:
> 
> Hi WebKittens.
> 
> I’m planning to start implement JS BigInt proposal on JSC, however I
> would like to sync with you the way you are planning to implement such
> feature.
> 
> Right now, I’m thinking in implement BigInt operations into C++
> (possibly on WTF?) and make the JSBigInt use this implementation.

We need something GC-optimized from the start since that will determine a lot 
of the details. So, I don’t think that a WTF implementation is appropriate. It 
should be a JSCell from day one. 

> As I
> have checked with some other implementors, some of them are going to
> use libgmp (SpiderMonkey case), but I don’t think its license (GPLv2)
> aligns with WebKit’s license and I heard that V8 is implementing their
> BigInt lib as well. By now, I’m thinking in implement a proof of
> concept and then, optimize the BigInt lib part. So, what I would like
> to collect from you is: Is there any problem start work on that
> feature?

We should do a GC-optimized bigint. If there was a great library that had the 
right license, we could port it to allocate using our GC. I don’t have a strong 
view on whether we should write our own from scratch or use somebody else’s as 
a starting point (so long as the license is ok). 

I don’t have any objection to you working on this.

-Filip

> 
> It is one of the proposals that I’ve made to my Coding Experience at
> Igalia, so I will also have the support of developers from there,
> since they are implementing it on SpiderMonkey and the spec champion
> is also in the team.
> 
> Regards,
> Caio.
> ___
> webkit-dev mailing list
> webkit-dev@lists.webkit.org
> https://lists.webkit.org/mailman/listinfo/webkit-dev
___
webkit-dev mailing list
webkit-dev@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-dev

[webkit-dev] BigInt implementation

[Caio Lima]

Hi WebKittens.

I’m planning to start implement JS BigInt proposal on JSC, however I
would like to sync with you the way you are planning to implement such
feature.

Right now, I’m thinking in implement BigInt operations into C++
(possibly on WTF?) and make the JSBigInt use this implementation. As I
have checked with some other implementors, some of them are going to
use libgmp (SpiderMonkey case), but I don’t think its license (GPLv2)
aligns with WebKit’s license and I heard that V8 is implementing their
BigInt lib as well. By now, I’m thinking in implement a proof of
concept and then, optimize the BigInt lib part. So, what I would like
to collect from you is: Is there any problem start work on that
feature?

It is one of the proposals that I’ve made to my Coding Experience at
Igalia, so I will also have the support of developers from there,
since they are implementing it on SpiderMonkey and the spec champion
is also in the team.

Regards,
Caio.
___
webkit-dev mailing list
webkit-dev@lists.webkit.org
https://lists.webkit.org/mailman/listinfo/webkit-dev