[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
<https://github.com/python/cpython/blob/6f0eb93183519024cb360162bdd81b9faec97ba6/Include/longintrepr.h>
)


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 <
jomsdev at 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
<https://github.com/python/cpython/blob/6f0eb93183519024cb360162bdd81b9faec97ba6/Include/longintrepr.h>
)


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 <fpizlo at apple.com> 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 <littledan at igalia.com>
>> wrote:
>> >
>> > On 2017-10-19 03:18, Filip Pizlo wrote:
>> >>> On Oct 18, 2017, at 5:50 PM, Caio Lima <ticaiolima at gmail.com> 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 at lists.webkit.org
>> >>> https://lists.webkit.org/mailman/listinfo/webkit-dev
>> >
>>
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.webkit.org/pipermail/webkit-dev/attachments/20171020/b5b5a970/attachment.html>