2017-10-20 12:21 GMT-02:00 Robin Morisset <[email protected]>: > 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: > > 1. 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. > 2. Implement some interesting benchmark, probably a port of some > crypto library + some miscellaneous arithmetic. > 3. 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). > 4. 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 > 5. 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. > 6. 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 <[email protected]> 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 < > [email protected]> 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 <[email protected]> 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 <[email protected]> >>> wrote: >>> > >>> > On 2017-10-19 03:18, Filip Pizlo wrote: >>> >>> On Oct 18, 2017, at 5:50 PM, Caio Lima <[email protected]> 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 >>> >>> [email protected] >>> >>> https://lists.webkit.org/mailman/listinfo/webkit-dev >>> > >>> >> >> > _______________________________________________ > webkit-dev mailing list > [email protected] > https://lists.webkit.org/mailman/listinfo/webkit-dev > > >
_______________________________________________ webkit-dev mailing list [email protected] https://lists.webkit.org/mailman/listinfo/webkit-dev
