[webkit-dev] BigInt implementation

Caio Lima ticaiolima at gmail.com
Fri Oct 20 08:06:11 PDT 2017 

2017-10-20 12:21 GMT-02:00 Robin Morisset <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:
>
>    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 <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> 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
>>> >
>>>
>>
>>
> _______________________________________________
> 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/5be0ebb6/attachment.html>

More information about the webkit-dev mailing list