[webkit-dev] BigInt implementation

Robin Morisset rmorisset at apple.com
Mon Oct 23 04:19:42 PDT 2017 

Hello,

That sounds good to me.

Best regards,
Robin

> On Oct 20, 2017, at 17:06, Caio Lima <ticaiolima at gmail.com> wrote:
> 
> 2017-10-20 12:21 GMT-02:00 Robin Morisset <rmorisset at apple.com <mailto:rmorisset at apple.com>>:
> 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 <jomsdev at gmail.com <mailto: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 :)
>> 
>> 
>> P.S.: I was not subrscibed toOn 20 October 2017 at 06:44, Jordi Montes <jomsdev at gmail.com <mailto: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 <mailto: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 <mailto: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 <mailto: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/ <http://www.libtom.net/LibTomMath/>
>> > [2] https://github.com/v8/v8/blob/master/src/objects/bigint.cc <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 <mailto:webkit-dev at lists.webkit.org>
>> >>> https://lists.webkit.org/mailman/listinfo/webkit-dev <https://lists.webkit.org/mailman/listinfo/webkit-dev>
>> >
>> 
>> 
>> _______________________________________________
>> webkit-dev mailing list
>> webkit-dev at lists.webkit.org <mailto:webkit-dev at lists.webkit.org>
>> https://lists.webkit.org/mailman/listinfo/webkit-dev <https://lists.webkit.org/mailman/listinfo/webkit-dev>
> 
> 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.webkit.org/pipermail/webkit-dev/attachments/20171023/8fb22c6a/attachment.html>

More information about the webkit-dev mailing list