www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - Anything in the review queue?

reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
Since David kindly agreed to work some more on std.parallelism, there is 
now time for carrying one review cycle on another library. I recall 
there's work on:

* std.goodxml (status?)

* std.net (beyond mere libcurl bindings)

* std.path (improvements to path)

* A bunch of almost-finished projects that need some tending (rational 
numbers etc.)

* anything else?

Is there anything ready for a formal review?


Thanks,

Andrei
Mar 20 2011
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
On 3/20/2011 11:10 AM, Andrei Alexandrescu wrote:

 Since David kindly agreed to work some more on std.parallelism, there is
 now time for carrying one review cycle on another library. I recall
 there's work on:

 * std.goodxml (status?)

 * std.net (beyond mere libcurl bindings)

 * std.path (improvements to path)

 * A bunch of almost-finished projects that need some tending (rational
 numbers etc.)

 * anything else?

 Is there anything ready for a formal review?


 Thanks,

 Andrei


Definitely not rational.  I just looked at that and it's going to need 
some work to improve the docs a little and remove some workarounds for 
BigInt bugs that have been fixed.  It doesn't need a lot of work, but 
I'd rather focus on std.parallelism and not have rational on my plate at 
the same time.
Mar 20 2011
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 03/20/2011 10:49 AM, dsimcha wrote:

 On 3/20/2011 11:10 AM, Andrei Alexandrescu wrote:

 Since David kindly agreed to work some more on std.parallelism, there is
 now time for carrying one review cycle on another library. I recall
 there's work on:

 * std.goodxml (status?)

 * std.net (beyond mere libcurl bindings)

 * std.path (improvements to path)

 * A bunch of almost-finished projects that need some tending (rational
 numbers etc.)

 * anything else?

 Is there anything ready for a formal review?


 Thanks,

 Andrei


 Definitely not rational. I just looked at that and it's going to need
 some work to improve the docs a little and remove some workarounds for
 BigInt bugs that have been fixed. It doesn't need a lot of work, but I'd
 rather focus on std.parallelism and not have rational on my plate at the
 same time.


Would you donate the code to someone to finalize?

Andrei
Mar 20 2011
prev sibling next sibling parent Jesse Phillips <jessekphillips+D gmail.com> writes:
Andrei Alexandrescu Wrote:


 Since David kindly agreed to work some more on std.parallelism, there is 
 now time for carrying one review cycle on another library. I recall 
 there's work on:
 
 * std.goodxml (status?)
 
 * std.net (beyond mere libcurl bindings)
 
 * std.path (improvements to path)
 
 * A bunch of almost-finished projects that need some tending (rational 
 numbers etc.)
 
 * anything else?
 
 Is there anything ready for a formal review?
 
 
 Thanks,
 
 Andrei


I'm still looking into taking advantage of David's CSV design for my own
parser. But it isn't ready for review and I don't have a planned schedule for
it.

And I don't think my slicing design will be the appropriate one for including
into Phobos.
Mar 20 2011
prev sibling next sibling parent reply "Lars T. Kyllingstad" <public kyllingen.NOSPAMnet> writes:
On Sun, 20 Mar 2011 10:10:20 -0500, Andrei Alexandrescu wrote:


 Since David kindly agreed to work some more on std.parallelism, there is
 now time for carrying one review cycle on another library. I recall
 there's work on:
 
 * std.goodxml (status?)
 
 * std.net (beyond mere libcurl bindings)
 
 * std.path (improvements to path)
 
 * A bunch of almost-finished projects that need some tending (rational
 numbers etc.)
 
 * anything else?
 
 Is there anything ready for a formal review?
 
 
 Thanks,
 
 Andrei


My std.path proposal is pretty much ready, but the deadline for my PhD 
thesis is in less than two weeks, and I have very little time for 
anything else right now. :(

-Lars
Mar 20 2011
next sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 03/20/2011 11:50 AM, Lars T. Kyllingstad wrote:

 On Sun, 20 Mar 2011 10:10:20 -0500, Andrei Alexandrescu wrote:


 Since David kindly agreed to work some more on std.parallelism, there is
 now time for carrying one review cycle on another library. I recall
 there's work on:

 * std.goodxml (status?)

 * std.net (beyond mere libcurl bindings)

 * std.path (improvements to path)

 * A bunch of almost-finished projects that need some tending (rational
 numbers etc.)

 * anything else?

 Is there anything ready for a formal review?


 Thanks,

 Andrei


 My std.path proposal is pretty much ready, but the deadline for my PhD
 thesis is in less than two weeks, and I have very little time for
 anything else right now. :(

 -Lars


Good luck!!!

Andrei
Mar 20 2011
prev sibling parent "Simen kjaeraas" <simen.kjaras gmail.com> writes:
On Sun, 20 Mar 2011 17:50:59 +0100, Lars T. Kyllingstad  
<public kyllingen.nospamnet> wrote:


 On Sun, 20 Mar 2011 10:10:20 -0500, Andrei Alexandrescu wrote:


 Since David kindly agreed to work some more on std.parallelism, there is
 now time for carrying one review cycle on another library. I recall
 there's work on:

 * std.goodxml (status?)

 * std.net (beyond mere libcurl bindings)

 * std.path (improvements to path)

 * A bunch of almost-finished projects that need some tending (rational
 numbers etc.)

 * anything else?

 Is there anything ready for a formal review?


 Thanks,

 Andrei


 My std.path proposal is pretty much ready, but the deadline for my PhD
 thesis is in less than two weeks, and I have very little time for
 anything else right now. :(


Good luck!


-- 
Simen
Mar 20 2011
prev sibling next sibling parent "Robert Jacques" <sandford jhu.edu> writes:
On Sun, 20 Mar 2011 11:10:20 -0400, Andrei Alexandrescu  
<SeeWebsiteForEmail erdani.org> wrote:


 Since David kindly agreed to work some more on std.parallelism, there is  
 now time for carrying one review cycle on another library. I recall  
 there's work on:

 * std.goodxml (status?)

 * std.net (beyond mere libcurl bindings)

 * std.path (improvements to path)

 * A bunch of almost-finished projects that need some tending (rational  
 numbers etc.)

 * anything else?

 Is there anything ready for a formal review?


 Thanks,

 Andrei


I've been working on an update to std.variant/std.json and recently an  
patch to the put/isOutputRange/Appender triad, to fix a major scaling  
issue. Regarding status, I need to add trivial function to json, but  
otherwise am happy with it. I've been struggling with Variant's compile  
times, but have finally gotten them somewhat acceptable. I still have a  
few features I wish to add, and need to improve/update the documentation  
and unit tests. So nothing ready for formal review yet.
Mar 20 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
 Since David kindly agreed to work some more on std.parallelism, there is
 now time for carrying one review cycle on another library. I recall
 there's work on:
 
 * std.goodxml (status?)
 
 * std.net (beyond mere libcurl bindings)
 
 * std.path (improvements to path)
 
 * A bunch of almost-finished projects that need some tending (rational
 numbers etc.)
 
 * anything else?
 
 Is there anything ready for a formal review?


It would take a couple of days to be ready given what I've got going at the 
moment (I had assumed that std.parallelism and std.path would be ahead in 
line), but I have been intending to take the portions of assertPred which 
won't end up in an improved assert, split them into the appropriate functions, 
and put those up for review. And it likely wouldn't need to be a long review 
process either, since I suspect that it would primarily be take it or leave it 
for the most part (either you like a particular function or you don't) - at 
most a few tweaks might be necessary. We could choose to vote on functions 
individually (making it take it or leave it per function as opposed to the 
whole), but I doubt that there would be a lot of review necessary simply 
because the functions are fairly simple and versions of them have been looked 
at before.

So, I could get that ready for review within a couple of days.

- Jonathan M Davis
Mar 20 2011
prev sibling next sibling parent reply Jonas Drewsen <jdrewsen nospam.com> writes:
On 20/03/11 16.10, Andrei Alexandrescu wrote:

 Since David kindly agreed to work some more on std.parallelism, there is
 now time for carrying one review cycle on another library. I recall
 there's work on:

 * std.goodxml (status?)

 * std.net (beyond mere libcurl bindings)

 * std.path (improvements to path)

 * A bunch of almost-finished projects that need some tending (rational
 numbers etc.)

 * anything else?

 Is there anything ready for a formal review?


 Thanks,

 Andrei


I've committet the review fixes for the curl C declarations. I wonder if 
the pull request has been resent after I updated the commit to be 
pulled. Anyone got notified?

Regarding the libcurl wrapper I'm working on the improvement requests I 
got from the curl RFC thread.

/Jonas
Mar 20 2011
parent Jonathan M Davis <jmdavisProg gmx.com> writes:
 On 20/03/11 16.10, Andrei Alexandrescu wrote:

 Since David kindly agreed to work some more on std.parallelism, there is
 now time for carrying one review cycle on another library. I recall
 there's work on:
 
 * std.goodxml (status?)
 
 * std.net (beyond mere libcurl bindings)
 
 * std.path (improvements to path)
 
 * A bunch of almost-finished projects that need some tending (rational
 numbers etc.)
 
 * anything else?
 
 Is there anything ready for a formal review?
 
 
 Thanks,
 
 Andrei


 
 I've committet the review fixes for the curl C declarations. I wonder if
 the pull request has been resent after I updated the commit to be
 pulled. Anyone got notified?


Anyone participating in the pull request should get notified whenever an 
update to it is made - be it a comment or commit (the only time that everyone 
with commit access to Phobos gets notified is with the creation of the initial 
pull request).

- Jonathan M Davis
Mar 20 2011
prev sibling next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
On 3/20/2011 11:10 AM, Andrei Alexandrescu wrote:

 Since David kindly agreed to work some more on std.parallelism, there is
 now time for carrying one review cycle on another library. I recall
 there's work on:

 * std.goodxml (status?)

 * std.net (beyond mere libcurl bindings)

 * std.path (improvements to path)

 * A bunch of almost-finished projects that need some tending (rational
 numbers etc.)

 * anything else?

 Is there anything ready for a formal review?


 Thanks,

 Andrei


On second thought, given the difficulty finding anything else, rational 
may be the thing that's most ready.  I'll offer it up for review now 
under the following caveats, since it's a relatively simple module that 
I doubt will have nearly as many issues as std.parallelism.  This may 
also be good because it won't overwhelm the community, so I can continue 
getting feedback about the much more complex std.parallelism in parallel.

Caveats:

1.  If anyone with less other stuff on their plate has something they 
want reviewed (so far noone seems to) their stuff can take precedence.

2.  If major changes are suggested, we may have to "git stash" rational 
in a couple weeks to un-stash std.parallelism.

Code:

https://github.com/dsimcha/Rational

Docs:

http://cis.jhu.edu/~dsimcha/d/phobos/std_rational.html
Mar 20 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
dsimcha:


 On second thought, given the difficulty finding anything else, rational 
 may be the thing that's most ready.  I'll offer it up for review now 


It's good to have rationals in Phobos, thank you.

Is this GCD? There is already a gcd in Phobos. Is this efficient when numbers
gets very large?
CommonInteger!(I1,I2) gcf(I1, I2)(I1 num1, I2 num2);


An alternative is to give the number of binary digits of precision for the
mantissa (see std.math.feqrel):
Rational!(Int) toRational(Int)(real floatNum, real epsilon = 1e-08);

Bye,
bearophile
Mar 20 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
On 3/20/2011 10:26 PM, bearophile wrote:

 dsimcha:


 On second thought, given the difficulty finding anything else, rational
 may be the thing that's most ready.  I'll offer it up for review now


 It's good to have rationals in Phobos, thank you.

 Is this GCD? There is already a gcd in Phobos. Is this efficient when numbers
gets very large?
 CommonInteger!(I1,I2) gcf(I1, I2)(I1 num1, I2 num2);


I knew someone was going to ask this, so I probably should have answered 
it pre-emptively.  std.numeric.gcd doesn't work with BigInts.  I'm 
considering making my implementation private and eventually fixing 
std.numeric rather than having duplicate public functionality.


 An alternative is to give the number of binary digits of precision for the
mantissa (see std.math.feqrel):
 Rational!(Int) toRational(Int)(real floatNum, real epsilon = 1e-08);


That's worth considering.  The only reason I did it the way I did is 
because the Maxima computer algebra system did it this way and, when in 
doubt, I generally do what Maxima does in this library.  I also think 
absolute error is the better metric for this case.  If you do:

auto foo = toRational!BigInt(1e-200);

Do we really want to return some ridiculously huge number (that possibly 
overflows in the case of fixed width integers) for the denominator in 
this case?
Mar 20 2011
parent reply Don <nospam nospam.com> writes:
dsimcha wrote:

 On 3/20/2011 10:26 PM, bearophile wrote:

 dsimcha:


 On second thought, given the difficulty finding anything else, rational
 may be the thing that's most ready.  I'll offer it up for review now


 It's good to have rationals in Phobos, thank you.

 Is this GCD? There is already a gcd in Phobos. Is this efficient when 
 numbers gets very large?
 CommonInteger!(I1,I2) gcf(I1, I2)(I1 num1, I2 num2);


 
 I knew someone was going to ask this, so I probably should have answered 
 it pre-emptively.  std.numeric.gcd doesn't work with BigInts.  I'm 
 considering making my implementation private and eventually fixing 
 std.numeric rather than having duplicate public functionality.
 

 An alternative is to give the number of binary digits of precision for 
 the mantissa (see std.math.feqrel):
 Rational!(Int) toRational(Int)(real floatNum, real epsilon = 1e-08);


 
 That's worth considering.  The only reason I did it the way I did is 
 because the Maxima computer algebra system did it this way and, when in 
 doubt, I generally do what Maxima does in this library.  I also think 
 absolute error is the better metric for this case.  If you do:
 
 auto foo = toRational!BigInt(1e-200);
 
 Do we really want to return some ridiculously huge number (that possibly 
 overflows in the case of fixed width integers) for the denominator in 
 this case?


The original plan for BigInt was to have a BigRational type. Suppose 
that such a thing existed -- would it affect plans for this library?

I'm not sure that it is realistic to have a single templated type that 
does both BigInt rationals, together with rationals based on built-in 
integral types. The algorithms are different in a few respects:
(1) copying built-ins is practically zero cost;
(2) operations on BigInts depend on the size of the number (whereas for 
builtins, all operations are O(1));
(3) BigInts cannot overflow.
In particular, gcd algorithms for arbitrary precision types are quite 
different to gcd for built-ins.

I guess the primary question is:
If there were a BigRational type, would you still want rational?
Ie, are there use cases for rational over built-in types (rather than it 
just being a workaround for a lack of a BigRational type)?

If the answer to this question is yes, then I suspect that the semantics 
for rational over built-ins are so different to the semantics for 
BigRational, that the two could be relatively independent.
Mar 21 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
On 3/21/2011 3:59 AM, Don wrote:

 The original plan for BigInt was to have a BigRational type. Suppose
 that such a thing existed -- would it affect plans for this library?

 I'm not sure that it is realistic to have a single templated type that
 does both BigInt rationals, together with rationals based on built-in
 integral types. The algorithms are different in a few respects:
 (1) copying built-ins is practically zero cost;


Doesn't BigInt use COW rather than eager copying?


 (2) operations on BigInts depend on the size of the number (whereas for
 builtins, all operations are O(1));


I don't understand how this is relevant.


 (3) BigInts cannot overflow.
 In particular, gcd algorithms for arbitrary precision types are quite
 different to gcd for built-ins.


Ok, I don't know much about how BigInts work under the hood.  I used a 
fairly simple implementation of Euler's algorithm here.  Is there 
something much more efficient for BigInts?


 I guess the primary question is:
 If there were a BigRational type, would you still want rational?
 Ie, are there use cases for rational over built-in types (rather than it
 just being a workaround for a lack of a BigRational type)?


My thoughts were that Rational would be **primarily** used with BigInt, 
but occasionally, if you really know what you're doing with regard to 
overflow, you could used fixed width as an optimization.


 If the answer to this question is yes, then I suspect that the semantics
 for rational over built-ins are so different to the semantics for
 BigRational, that the two could be relatively independent.
Mar 21 2011
next sibling parent KennyTM~ <kennytm gmail.com> writes:
On Mar 21, 11 21:54, dsimcha wrote:

 (3) BigInts cannot overflow.
 In particular, gcd algorithms for arbitrary precision types are quite
 different to gcd for built-ins.


 Ok, I don't know much about how BigInts work under the hood.  I used a
 fairly simple implementation of Euler's algorithm here.  Is there
 something much more efficient for BigInts?


http://en.wikipedia.org/wiki/Lehmer%27s_GCD_algorithm
Mar 21 2011
prev sibling parent reply Don <nospam nospam.com> writes:
dsimcha wrote:

 On 3/21/2011 3:59 AM, Don wrote:

 The original plan for BigInt was to have a BigRational type. Suppose
 that such a thing existed -- would it affect plans for this library?

 I'm not sure that it is realistic to have a single templated type that
 does both BigInt rationals, together with rationals based on built-in
 integral types. The algorithms are different in a few respects:
 (1) copying built-ins is practically zero cost;


 
 Doesn't BigInt use COW rather than eager copying?


Yes, but it operations which create temporaries are still expensive.


 

 (2) operations on BigInts depend on the size of the number (whereas for
 builtins, all operations are O(1));


 
 I don't understand how this is relevant.


With a built-in type, multiplication and addition are equally cheap - eg 
on x86, multiply is only about half as slow as an addition.
For BigInt, addition is O(N) while multiplication is O(N^^2) decreasing 
to say O(N^^1.5) for large numbers. This means that you really want to 
avoid multiplication with BigInts. Interestingly, division of builtins 
is really slow (~20 * multiply), but division of a BigInt is only a few 
times slower than a multiply.


 

 (3) BigInts cannot overflow.
 In particular, gcd algorithms for arbitrary precision types are quite
 different to gcd for built-ins.


 
 Ok, I don't know much about how BigInts work under the hood.  I used a 
 fairly simple implementation of Euler's algorithm here.  Is there 
 something much more efficient for BigInts?


Yes. Euler's algorithm performs very poorly for BigInts. In fact, you 
probably want to use the BinaryGCD algorithm even for builtins.
There is a sub-quadratic algorithm for GCD, but it's very complicated.
(It's not the one Kenny posted).



 I guess the primary question is:
 If there were a BigRational type, would you still want rational?
 Ie, are there use cases for rational over built-in types (rather than it
 just being a workaround for a lack of a BigRational type)?


 
 My thoughts were that Rational would be **primarily** used with BigInt, 
 but occasionally, if you really know what you're doing with regard to 
 overflow, you could used fixed width as an optimization.


This isn't sounding so promising.
I hate to be saying that.
Mar 21 2011
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Don (nospam nospam.com)'s article

 dsimcha wrote:

 On 3/21/2011 3:59 AM, Don wrote:

 The original plan for BigInt was to have a BigRational type. Suppose
 that such a thing existed -- would it affect plans for this library?

 I'm not sure that it is realistic to have a single templated type that
 does both BigInt rationals, together with rationals based on built-in
 integral types. The algorithms are different in a few respects:
 (1) copying built-ins is practically zero cost;


 Doesn't BigInt use COW rather than eager copying?


 Yes, but it operations which create temporaries are still expensive.

 (2) operations on BigInts depend on the size of the number (whereas for
 builtins, all operations are O(1));


 I don't understand how this is relevant.


 With a built-in type, multiplication and addition are equally cheap - eg
 on x86, multiply is only about half as slow as an addition.
 For BigInt, addition is O(N) while multiplication is O(N^^2) decreasing
 to say O(N^^1.5) for large numbers. This means that you really want to
 avoid multiplication with BigInts. Interestingly, division of builtins
 is really slow (~20 * multiply), but division of a BigInt is only a few
 times slower than a multiply.

 (3) BigInts cannot overflow.
 In particular, gcd algorithms for arbitrary precision types are quite
 different to gcd for built-ins.


 Ok, I don't know much about how BigInts work under the hood.  I used a
 fairly simple implementation of Euler's algorithm here.  Is there
 something much more efficient for BigInts?


 Yes. Euler's algorithm performs very poorly for BigInts. In fact, you
 probably want to use the BinaryGCD algorithm even for builtins.
 There is a sub-quadratic algorithm for GCD, but it's very complicated.
 (It's not the one Kenny posted).

 I guess the primary question is:
 If there were a BigRational type, would you still want rational?
 Ie, are there use cases for rational over built-in types (rather than it
 just being a workaround for a lack of a BigRational type)?


 My thoughts were that Rational would be **primarily** used with BigInt,
 but occasionally, if you really know what you're doing with regard to
 overflow, you could used fixed width as an optimization.


 This isn't sounding so promising.
 I hate to be saying that.


That's ok.  Rational was a very small side project for me.  I didn't have tons
of
time invested in it or anything (probably an order of magnitude less than
std.parallelism).  I do think it's interesting to decouple the Rational
representation from the underlying integer type.  Whether it's practical and
warrants inclusion in Phobos is a different question.

As far as BinaryGCD, would that be efficiently implementable using only the
public
interface of BigInt?  If not, it might make sense to change the public interface
of BigInt to make it implementable.  (Or it might not.  I have no idea what's
involved here.  Please comment.)
Mar 21 2011
parent Don <nospam nospam.com> writes:
dsimcha wrote:

 == Quote from Don (nospam nospam.com)'s article

 dsimcha wrote:

 On 3/21/2011 3:59 AM, Don wrote:

 The original plan for BigInt was to have a BigRational type. Suppose
 that such a thing existed -- would it affect plans for this library?

 I'm not sure that it is realistic to have a single templated type that
 does both BigInt rationals, together with rationals based on built-in
 integral types. The algorithms are different in a few respects:
 (1) copying built-ins is practically zero cost;


 Doesn't BigInt use COW rather than eager copying?


 Yes, but it operations which create temporaries are still expensive.

 (2) operations on BigInts depend on the size of the number (whereas for
 builtins, all operations are O(1));


 I don't understand how this is relevant.


 With a built-in type, multiplication and addition are equally cheap - eg
 on x86, multiply is only about half as slow as an addition.
 For BigInt, addition is O(N) while multiplication is O(N^^2) decreasing
 to say O(N^^1.5) for large numbers. This means that you really want to
 avoid multiplication with BigInts. Interestingly, division of builtins
 is really slow (~20 * multiply), but division of a BigInt is only a few
 times slower than a multiply.

 (3) BigInts cannot overflow.
 In particular, gcd algorithms for arbitrary precision types are quite
 different to gcd for built-ins.


 Ok, I don't know much about how BigInts work under the hood.  I used a
 fairly simple implementation of Euler's algorithm here.  Is there
 something much more efficient for BigInts?


 Yes. Euler's algorithm performs very poorly for BigInts. In fact, you
 probably want to use the BinaryGCD algorithm even for builtins.
 There is a sub-quadratic algorithm for GCD, but it's very complicated.
 (It's not the one Kenny posted).

 I guess the primary question is:
 If there were a BigRational type, would you still want rational?
 Ie, are there use cases for rational over built-in types (rather than it
 just being a workaround for a lack of a BigRational type)?


 My thoughts were that Rational would be **primarily** used with BigInt,
 but occasionally, if you really know what you're doing with regard to
 overflow, you could used fixed width as an optimization.


 This isn't sounding so promising.
 I hate to be saying that.


 
 That's ok.  Rational was a very small side project for me.  I didn't have tons
of
 time invested in it or anything (probably an order of magnitude less than
 std.parallelism).  I do think it's interesting to decouple the Rational
 representation from the underlying integer type.  Whether it's practical and
 warrants inclusion in Phobos is a different question.
 
 As far as BinaryGCD, would that be efficiently implementable using only the
public
 interface of BigInt?  If not, it might make sense to change the public
interface
 of BigInt to make it implementable.  (Or it might not.  I have no idea what's
 involved here.  Please comment.)


ExtendedGCD should be a part of the BigInt internals. (The other missing 
low-level BigInt function is square root). These functions should take 
care of switching algorithms from the naive version to ones with better 
big-O performance but large overheads, when the length is long.
I had planned to implement it, but then got distracted by fixing 
compiler bugs. I've been distracted for a long time <g>.
Mar 21 2011
prev sibling parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Don (nospam nospam.com)'s article

 Ok, I don't know much about how BigInts work under the hood.  I used a
 fairly simple implementation of Euler's algorithm here.  Is there
 something much more efficient for BigInts?


 Yes. Euler's algorithm performs very poorly for BigInts. In fact, you
 probably want to use the BinaryGCD algorithm even for builtins.
 There is a sub-quadratic algorithm for GCD, but it's very complicated.
 (It's not the one Kenny posted).

 I guess the primary question is:
 If there were a BigRational type, would you still want rational?
 Ie, are there use cases for rational over built-in types (rather than it
 just being a workaround for a lack of a BigRational type)?


 My thoughts were that Rational would be **primarily** used with BigInt,
 but occasionally, if you really know what you're doing with regard to
 overflow, you could used fixed width as an optimization.


 This isn't sounding so promising.
 I hate to be saying that.


I've thought about this some more.  The following **may** be a good way to
proceed.  I'd like Don's input, since I don't know in detail what he was
planning.

1.  Review the design of my rational lib with a focus on whether sufficient
infrastructure for creating specializations without introducing breaking changes
is available.

2.  If no issues not related to the lack of specialization for BigInt are
raised,
accept Rational into Phobos for now.

3.  At his leisure, Don can write a specialization of Rational specifically for
BigInt (or even just a specialization of gcd, if that's all that's needed). 
Once
this is done, we include it as an optimization, but without changes to the
interface.  Every integer type except BigInt still uses the generic
implementation.

4.  Maybe we provide hooks for specializing certain performance-critical things
like GCD, in case someone wants to use their own custom BigInt type with
Rational
without having to modify the code for Phobos.  For example, a BigInt type might
optionally define a gcd() method.  Rational would look for this and use it if it
exists, or use the generic fallback algorithm otherwise.
Mar 21 2011
parent reply Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/21/11 12:18 PM, dsimcha wrote:

 == Quote from Don (nospam nospam.com)'s article

 Ok, I don't know much about how BigInts work under the hood.  I used a
 fairly simple implementation of Euler's algorithm here.  Is there
 something much more efficient for BigInts?


 Yes. Euler's algorithm performs very poorly for BigInts. In fact, you
 probably want to use the BinaryGCD algorithm even for builtins.
 There is a sub-quadratic algorithm for GCD, but it's very complicated.
 (It's not the one Kenny posted).

 I guess the primary question is:
 If there were a BigRational type, would you still want rational?
 Ie, are there use cases for rational over built-in types (rather than it
 just being a workaround for a lack of a BigRational type)?


 My thoughts were that Rational would be **primarily** used with BigInt,
 but occasionally, if you really know what you're doing with regard to
 overflow, you could used fixed width as an optimization.


 This isn't sounding so promising.
 I hate to be saying that.


 I've thought about this some more.  The following **may** be a good way to
 proceed.  I'd like Don's input, since I don't know in detail what he was
planning.

 1.  Review the design of my rational lib with a focus on whether sufficient
 infrastructure for creating specializations without introducing breaking
changes
 is available.

 2.  If no issues not related to the lack of specialization for BigInt are
raised,
 accept Rational into Phobos for now.

 3.  At his leisure, Don can write a specialization of Rational specifically for
 BigInt (or even just a specialization of gcd, if that's all that's needed). 
Once
 this is done, we include it as an optimization, but without changes to the
 interface.  Every integer type except BigInt still uses the generic
implementation.

 4.  Maybe we provide hooks for specializing certain performance-critical things
 like GCD, in case someone wants to use their own custom BigInt type with
Rational
 without having to modify the code for Phobos.  For example, a BigInt type might
 optionally define a gcd() method.  Rational would look for this and use it if
it
 exists, or use the generic fallback algorithm otherwise.


I think by and large failure to define rational for BigInt in a way that 
has many commonalities with rational for built-in integrals reflects a 
failure of BigInt. By its very design, BigInt is supposed to 
transparently replace integers. If this is largely the case, the design 
has succeeded. If the design of anything must be reworked essentially 
from scratch to work with BigInt instead of int et al, then the 
abstraction may be too porous to be useful.

There are a few approaches we can take from here. One is to define 
certain traits that differentiate BigInt from other integrals (e.g. 
preferAdditionToMultiplication or whatnot), and then design Rational to 
use those traits. Another is of course to specialize the entire Rational 
on BigInt. Third would be to specialize certain core routines (gcd and 
friends) for BigInt and keep Rational agnostic.

Anyhow, BigInt should be cheap to copy (i.e. use refcounting). If there 
are good reasons for which that's impossible, we should give up on the 
dream of enacting that assumption throughout Phobos. Don?


Andrei
Mar 21 2011
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
On 3/21/2011 8:33 PM, Andrei Alexandrescu wrote:

 I think by and large failure to define rational for BigInt in a way that
 has many commonalities with rational for built-in integrals reflects a
 failure of BigInt. By its very design, BigInt is supposed to
 transparently replace integers. If this is largely the case, the design
 has succeeded. If the design of anything must be reworked essentially
 from scratch to work with BigInt instead of int et al, then the
 abstraction may be too porous to be useful.

 There are a few approaches we can take from here. One is to define
 certain traits that differentiate BigInt from other integrals (e.g.
 preferAdditionToMultiplication or whatnot), and then design Rational to
 use those traits. Another is of course to specialize the entire Rational
 on BigInt. Third would be to specialize certain core routines (gcd and
 friends) for BigInt and keep Rational agnostic.

 Anyhow, BigInt should be cheap to copy (i.e. use refcounting). If there
 are good reasons for which that's impossible, we should give up on the
 dream of enacting that assumption throughout Phobos. Don?


 Andrei


The biggest perf issue, though, seems to be Euler's algorithm instead of 
BinaryGCD.  This is definitely going to get fixed eventually by me, 
since I've read up on BinaryGCD and it doesn't look hard to implement 
generically.  I naively thought Euler's algorithm was pretty darn 
efficient when I wrote the first version, not knowing much about how 
BigInts work under the hood.  I'm not sure if Don had something even 
more efficient than a good generic BinaryGCD implementation in mind, or 
if there are other areas where a templated Rational is a Bad Idea, though.
Mar 21 2011
parent reply "Simen kjaeraas" <simen.kjaras gmail.com> writes:
On Tue, 22 Mar 2011 02:08:39 +0100, dsimcha <dsimcha yahoo.com> wrote:


 The biggest perf issue, though, seems to be Euler's algorithm instead of  
 BinaryGCD.  This is definitely going to get fixed eventually by me,  
 since I've read up on BinaryGCD and it doesn't look hard to implement  
 generically.  I naively thought Euler's algorithm was pretty darn  
 efficient when I wrote the first version, not knowing much about how  
 BigInts work under the hood.  I'm not sure if Don had something even  
 more efficient than a good generic BinaryGCD implementation in mind, or  
 if there are other areas where a templated Rational is a Bad Idea,  
 though.


The algorithmic complexity is the same for BinaryGCD as it is for normal
GCD. What Don had in mind was sub-quadratic. Might have been something
 from this paper:

http://www.lysator.liu.se/~nisse/archive/S0025-5718-07-02017-0.pdf

Page 10 onwards claims subquadratic performance.

-- 
Simen
Mar 21 2011
parent Don <nospam nospam.com> writes:
Simen kjaeraas wrote:

 On Tue, 22 Mar 2011 02:08:39 +0100, dsimcha <dsimcha yahoo.com> wrote:
 

 The biggest perf issue, though, seems to be Euler's algorithm instead 
 of BinaryGCD.  This is definitely going to get fixed eventually by me, 
 since I've read up on BinaryGCD and it doesn't look hard to implement 
 generically.  I naively thought Euler's algorithm was pretty darn 
 efficient when I wrote the first version, not knowing much about how 
 BigInts work under the hood.  I'm not sure if Don had something even 
 more efficient than a good generic BinaryGCD implementation in mind, 
 or if there are other areas where a templated Rational is a Bad Idea, 
 though.


 
 The algorithmic complexity is the same for BinaryGCD as it is for normal
 GCD. What Don had in mind was sub-quadratic. Might have been something
 from this paper:
 
 http://www.lysator.liu.se/~nisse/archive/S0025-5718-07-02017-0.pdf
 
 Page 10 onwards claims subquadratic performance.
 


Yes, and there's been a couple of improved algorithmic tweaks since 
then. The best algorithms are described in "Modern Computer Arithmetic" 
which was published just a few months back.
But this stuff doesn't really matter terribly much, as these algorithms 
are only beneficial for very large numbers. The most important thing, 
really, is to avoid Euclid's algorithm.
Mar 22 2011
prev sibling next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Andrei:


 By its very design, BigInt is supposed to 
 transparently replace integers.


Small missing parts:
http://d.puremagic.com/issues/show_bug.cgi?id=5765
To allow them in switch too:
http://d.puremagic.com/issues/show_bug.cgi?id=596

Bye,
bearophile
Mar 21 2011
prev sibling parent reply Don <nospam nospam.com> writes:
Andrei Alexandrescu wrote:

 On 3/21/11 12:18 PM, dsimcha wrote:

 == Quote from Don (nospam nospam.com)'s article

 Ok, I don't know much about how BigInts work under the hood.  I used a
 fairly simple implementation of Euler's algorithm here.  Is there
 something much more efficient for BigInts?


 Yes. Euler's algorithm performs very poorly for BigInts. In fact, you
 probably want to use the BinaryGCD algorithm even for builtins.
 There is a sub-quadratic algorithm for GCD, but it's very complicated.
 (It's not the one Kenny posted).

 I guess the primary question is:
 If there were a BigRational type, would you still want rational?
 Ie, are there use cases for rational over built-in types (rather 
 than it
 just being a workaround for a lack of a BigRational type)?


 My thoughts were that Rational would be **primarily** used with BigInt,
 but occasionally, if you really know what you're doing with regard to
 overflow, you could used fixed width as an optimization.


 This isn't sounding so promising.
 I hate to be saying that.


 I've thought about this some more.  The following **may** be a good 
 way to
 proceed.  I'd like Don's input, since I don't know in detail what he 
 was planning.

 1.  Review the design of my rational lib with a focus on whether 
 sufficient
 infrastructure for creating specializations without introducing 
 breaking changes
 is available.

 2.  If no issues not related to the lack of specialization for BigInt 
 are raised,
 accept Rational into Phobos for now.

 3.  At his leisure, Don can write a specialization of Rational 
 specifically for
 BigInt (or even just a specialization of gcd, if that's all that's 
 needed).  Once
 this is done, we include it as an optimization, but without changes to 
 the
 interface.  Every integer type except BigInt still uses the generic 
 implementation.

 4.  Maybe we provide hooks for specializing certain 
 performance-critical things
 like GCD, in case someone wants to use their own custom BigInt type 
 with Rational
 without having to modify the code for Phobos.  For example, a BigInt 
 type might
 optionally define a gcd() method.  Rational would look for this and 
 use it if it
 exists, or use the generic fallback algorithm otherwise.


 
 I think by and large failure to define rational for BigInt in a way that 
 has many commonalities with rational for built-in integrals reflects a 
 failure of BigInt. By its very design, BigInt is supposed to 
 transparently replace integers.If this is largely the case, the design
 has succeeded. If the design of anything must be reworked essentially 
 from scratch to work with BigInt instead of int et al, then the 
 abstraction may be too porous to be useful.
 
 There are a few approaches we can take from here. One is to define 
 certain traits that differentiate BigInt from other integrals (e.g. 
 preferAdditionToMultiplication or whatnot),  and then design Rational to
 use those traits. Another is of course to specialize the entire Rational 
 on BigInt. Third would be to specialize certain core routines (gcd and 
 friends) for BigInt and keep Rational agnostic.


You're missing something important here. Rational big integers are a 
very well defined area of research, with its own set of algorithms.
Although you can pretend a BigInt behaves as an int, and make a rational 
type, the performance will be pathetic, and everyone will laugh at you.


 Anyhow, BigInt should be cheap to copy (i.e. use refcounting). If there 
 are good reasons for which that's impossible, we should give up on the 
 dream of enacting that assumption throughout Phobos. Don?


Well, it uses copy-on-write so copying itself isn't expensive.
But temporaries are never going to be cheap. Things like bigint *= 
bigint is  NEVER an in-place operation (the size is twice as big, so a 
memory allocation is always required). Even bigint += bigint may trigger 
a memory allocation.
Refcounting might be better than copy-on-write, in the end, but probably 
not a huge win.
One thing which I will do eventually is implement the small-integer 
optimisation (so anything smaller than 31 bits/63 bits is stored inside 
the pointer and doesn't have any memory allocation at all). But that 
doesn't help the general case.
Mar 21 2011
next sibling parent reply dsimcha <dsimcha yahoo.com> writes:
On 3/22/2011 1:25 AM, Don wrote:

 There are a few approaches we can take from here. One is to define
 certain traits that differentiate BigInt from other integrals (e.g.
 preferAdditionToMultiplication or whatnot), and then design Rational to
 use those traits. Another is of course to specialize the entire
 Rational on BigInt. Third would be to specialize certain core routines
 (gcd and friends) for BigInt and keep Rational agnostic.


 You're missing something important here. Rational big integers are a
 very well defined area of research, with its own set of algorithms.
 Although you can pretend a BigInt behaves as an int, and make a rational
 type, the performance will be pathetic, and everyone will laugh at you.


I fully understand this based on your previous posts.  I therefore agree 
that Rational doesn't belong in Phobos exactly as-is.  I'm trying to 
understand which of the following scenarios is true, though:

Scenario A:  Making BigInt efficient would require changes only in a few 
small places, like GCD.  If we provide hooks for arbitrary precision 
types to specialize these, and provide specializations for 
std.bigint.BigInt, all will be well.

Scenario B:  Making BigInt efficient would have ripple effects all over 
the implementation, require rethinking of every operation, etc., but in 
a way that wouldn't bleed out into the interface.  It might make sense 
to get the interface and a generic implementation right first, then 
specialize it to improve performance later.

Scenario C:  Making BigInt efficient would have ripple effects for both 
the interface and the implementation.  In this case, we probably 
shouldn't provide a generic implementation because the arbitrary 
precision one is much more generally useful and the fixed width one 
would mostly add clutter.

BTW, does BigInt over-allocate initially to allow certain operations 
(like +=) to be done in-place more frequently?
Mar 22 2011
parent reply Don <nospam nospam.com> writes:
dsimcha wrote:

 On 3/22/2011 1:25 AM, Don wrote:

 There are a few approaches we can take from here. One is to define
 certain traits that differentiate BigInt from other integrals (e.g.
 preferAdditionToMultiplication or whatnot), and then design Rational to
 use those traits. Another is of course to specialize the entire
 Rational on BigInt. Third would be to specialize certain core routines
 (gcd and friends) for BigInt and keep Rational agnostic.


 You're missing something important here. Rational big integers are a
 very well defined area of research, with its own set of algorithms.
 Although you can pretend a BigInt behaves as an int, and make a rational
 type, the performance will be pathetic, and everyone will laugh at you.


 
 I fully understand this based on your previous posts.  I therefore agree 
 that Rational doesn't belong in Phobos exactly as-is.  I'm trying to 
 understand which of the following scenarios is true, though:
 
 Scenario A:  Making BigInt efficient would require changes only in a few 
 small places, like GCD.  If we provide hooks for arbitrary precision 
 types to specialize these, and provide specializations for 
 std.bigint.BigInt, all will be well.
 
 Scenario B:  Making BigInt efficient would have ripple effects all over 
 the implementation, require rethinking of every operation, etc., but in 
 a way that wouldn't bleed out into the interface.  It might make sense 
 to get the interface and a generic implementation right first, then 
 specialize it to improve performance later.
 
 Scenario C:  Making BigInt efficient would have ripple effects for both 
 the interface and the implementation.  In this case, we probably 
 shouldn't provide a generic implementation because the arbitrary 
 precision one is much more generally useful and the fixed width one 
 would mostly add clutter.


 From the BigInt side, the only real change is the addition of gcd and 
gcdExtended.
(gcdExtended returns x, y such that a*x + b*y = gcd(a, b) ).

I believe that is the only low-level algorithm which is missing; pretty 
much everything else remains unchanged.

However, the other case which is interesting is when BigInt is replaced 
with FixedInt!n (maybe someone can come up with a better name for this?) 
-- an integer with a length of a fixed number of ints.
Unlike BigInt, this has basically the same semantics as built-in integer 
types. In fact, FixedInt!1 == int, FixedInt!2 == long, FixedInt!4 == cent.
This is possibly even more relevant for Rational. I haven't thought much 
about the implications though.


 BTW, does BigInt over-allocate initially to allow certain operations 
 (like +=) to be done in-place more frequently?


No, it doesn't. As long as it uses copy-on-write, there's no benefit to 
doing so.
Reference counting would clearly be superior for FixedInt, but I'm not 
at all sure that it would be a win for BigInt. But of course FixedInt 
wouldn't need to over-allocate.

Using TempAlloc would have a far greater effect on performance.
Mar 23 2011
parent reply bearophile <bearophileHUGS lycos.com> writes:
Don:


 However, the other case which is interesting is when BigInt is replaced 
 with FixedInt!n (maybe someone can come up with a better name for this?) 
 -- an integer with a length of a fixed number of ints.
 Unlike BigInt, this has basically the same semantics as built-in integer 
 types. In fact, FixedInt!1 == int, FixedInt!2 == long, FixedInt!4 == cent.
 This is possibly even more relevant for Rational. I haven't thought much 
 about the implications though.
 

 BTW, does BigInt over-allocate initially to allow certain operations 
 (like +=) to be done in-place more frequently?


 
 No, it doesn't. As long as it uses copy-on-write, there's no benefit to 
 doing so.
 Reference counting would clearly be superior for FixedInt, but I'm not 
 at all sure that it would be a win for BigInt. But of course FixedInt 
 wouldn't need to over-allocate.


Are FixedInt fully allocated on the stack?

Bye,
bearophile
Mar 23 2011
parent Don <nospam nospam.com> writes:
bearophile wrote:

 Don:
 

 However, the other case which is interesting is when BigInt is replaced 
 with FixedInt!n (maybe someone can come up with a better name for this?) 
 -- an integer with a length of a fixed number of ints.
 Unlike BigInt, this has basically the same semantics as built-in integer 
 types. In fact, FixedInt!1 == int, FixedInt!2 == long, FixedInt!4 == cent.
 This is possibly even more relevant for Rational. I haven't thought much 
 about the implications though.


 BTW, does BigInt over-allocate initially to allow certain operations 
 (like +=) to be done in-place more frequently?


 No, it doesn't. As long as it uses copy-on-write, there's no benefit to 
 doing so.
 Reference counting would clearly be superior for FixedInt, but I'm not 
 at all sure that it would be a win for BigInt. But of course FixedInt 
 wouldn't need to over-allocate.


 
 Are FixedInt fully allocated on the stack?


Note that they don't currently exist (though I heard someone is working 
on it) but the implementation I would envisage is:
If size <= long.sizeof, alias to built-in type.
If size < threshold (maybe 2*cent.sizeof), allocate on the stack.
Otherwise, implement as a pointer to reference counted heap memory.
Mar 23 2011
prev sibling parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/21/11 10:25 PM, Don wrote:

 Andrei Alexandrescu wrote:

 I think by and large failure to define rational for BigInt in a way
 that has many commonalities with rational for built-in integrals
 reflects a failure of BigInt. By its very design, BigInt is supposed
 to transparently replace integers.If this is largely the case, the design
 has succeeded. If the design of anything must be reworked essentially
 from scratch to work with BigInt instead of int et al, then the
 abstraction may be too porous to be useful.

 There are a few approaches we can take from here. One is to define
 certain traits that differentiate BigInt from other integrals (e.g.
 preferAdditionToMultiplication or whatnot), and then design Rational to
 use those traits. Another is of course to specialize the entire
 Rational on BigInt. Third would be to specialize certain core routines
 (gcd and friends) for BigInt and keep Rational agnostic.


 You're missing something important here. Rational big integers are a
 very well defined area of research, with its own set of algorithms.
 Although you can pretend a BigInt behaves as an int, and make a rational
 type, the performance will be pathetic, and everyone will laugh at you.


Interesting. Thanks for the insight (missed this post for a while).

Andrei
Mar 23 2011
prev sibling parent reply Jacob Carlborg <doob me.com> writes:
On 2011-03-20 16:10, Andrei Alexandrescu wrote:

 Since David kindly agreed to work some more on std.parallelism, there is
 now time for carrying one review cycle on another library. I recall
 there's work on:

 * std.goodxml (status?)

 * std.net (beyond mere libcurl bindings)

 * std.path (improvements to path)

 * A bunch of almost-finished projects that need some tending (rational
 numbers etc.)

 * anything else?

 Is there anything ready for a formal review?


 Thanks,

 Andrei


I have the std.net.isemail module almost ready for review. Just need to 
generate the documentation, make sure it looks good and make it 
available online.

-- 
/Jacob Carlborg
Mar 21 2011
parent Andrei Alexandrescu <SeeWebsiteForEmail erdani.org> writes:
On 3/21/11 3:15 AM, Jacob Carlborg wrote:

 On 2011-03-20 16:10, Andrei Alexandrescu wrote:

 Since David kindly agreed to work some more on std.parallelism, there is
 now time for carrying one review cycle on another library. I recall
 there's work on:

 * std.goodxml (status?)

 * std.net (beyond mere libcurl bindings)

 * std.path (improvements to path)

 * A bunch of almost-finished projects that need some tending (rational
 numbers etc.)

 * anything else?

 Is there anything ready for a formal review?


 Thanks,

 Andrei


 I have the std.net.isemail module almost ready for review. Just need to
 generate the documentation, make sure it looks good and make it
 available online.


Let's make this next. Please finalize, find a manager, and submit. Good 
luck!

Andrei
Mar 21 2011