www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - BigInt foreach loop

reply Q. Schroll <qs.il.paperinik gmail.com> writes:
One can do
   BigInt n = returnsBigInt();
   foreach (i; BigInt(0) .. n)
   { .. }
How is this implemented? The code for BigInt is very large and I 
didn't find it.
And is it more efficient than
   for (BigInt i = 0; i < n; ++i)
   { .. }
as incrementing is a costly operation?
Aug 04
next sibling parent Stefan Koch <uplink.coder googlemail.com> writes:
On Friday, 4 August 2017 at 12:49:30 UTC, Q. Schroll wrote:
 One can do
   BigInt n = returnsBigInt();
   foreach (i; BigInt(0) .. n)
   { .. }
 How is this implemented? The code for BigInt is very large and 
 I didn't find it.
 And is it more efficient than
   for (BigInt i = 0; i < n; ++i)
   { .. }
 as incrementing is a costly operation?
you can see what the code is lowerd to with -vcg-ast The hand-written for is as effective as foreach usually.
Aug 04
prev sibling parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 8/4/17 8:49 AM, Q. Schroll wrote:
 One can do
    BigInt n = returnsBigInt();
    foreach (i; BigInt(0) .. n)
    { .. }
 How is this implemented? The code for BigInt is very large and I didn't 
 find it.
 And is it more efficient than
    for (BigInt i = 0; i < n; ++i)
    { .. }
Any foreach range statement like this: foreach(var; A .. B) is treated as if you wrote: for(auto var = A; var < B; ++var) So it's pretty much exactly like what you wrote, just the initializer is different but the result is the same.
 as incrementing is a costly operation?
Here is increment in bigint: https://github.com/dlang/phobos/blob/master/std/bigint.d#L563 And addOrSubInt: https://github.com/dlang/phobos/blob/master/std/internal/math/biguintcore.d#L508 I think there is room for improvement, as incrementing or decrementing by 1 is probably something that can be optimized. -Steve
Aug 04
parent reply Stefan Koch <uplink.coder googlemail.com> writes:
On Friday, 4 August 2017 at 13:09:55 UTC, Steven Schveighoffer 
wrote:

 Any foreach range statement like this:

 foreach(var; A .. B)

 is treated as if you wrote:

 for(auto var = A; var < B; ++var)

 So it's pretty much exactly like what you wrote, just the 
 initializer is different but the result is the same.

 as incrementing is a costly operation?
Here is increment in bigint: https://github.com/dlang/phobos/blob/master/std/bigint.d#L563 And addOrSubInt: https://github.com/dlang/phobos/blob/master/std/internal/math/biguintcore.d#L508 I think there is room for improvement, as incrementing or decrementing by 1 is probably something that can be optimized. -Steve
Not quite, foreach(x;A .. B) it's lowerd to auto limit = B; auto key = A; for(auto x = key;key < limit;++key) { // use x }
Aug 04
parent reply Q. Schroll <qs.il.paperinik gmail.com> writes:
On Friday, 4 August 2017 at 16:40:08 UTC, Stefan Koch wrote:
 [..]

 foreach(x;A .. B)
 it's lowerd to
 auto limit = B;
 auto key = A;
 for(auto x = key;key < limit;++key)
 {
  // use x
 }
That's enough to know that the foreach loop does not reuse the space for the iteration variable. That was what I cared about.
Aug 09
parent reply "H. S. Teoh via Digitalmars-d-learn" <digitalmars-d-learn puremagic.com> writes:
On Wed, Aug 09, 2017 at 09:34:26PM +0000, Q. Schroll via Digitalmars-d-learn
wrote:
 On Friday, 4 August 2017 at 16:40:08 UTC, Stefan Koch wrote:
 [..]
 
 foreach(x;A .. B)
 it's lowerd to
 auto limit = B;
 auto key = A;
 for(auto x = key;key < limit;++key)
 {
  // use x
 }
That's enough to know that the foreach loop does not reuse the space for the iteration variable. That was what I cared about.
Note that using BigInt as iteration variable will probably cause a BigInt allocation per iteration, because operations on BigInt in general will allocate a new BigInt result. So `++key` will probably create a new instance of BigInt each time it's executed. T -- To provoke is to call someone stupid; to argue is to call each other stupid.
Aug 09
parent reply Steven Schveighoffer <schveiguy yahoo.com> writes:
On 8/9/17 5:40 PM, H. S. Teoh via Digitalmars-d-learn wrote:
 On Wed, Aug 09, 2017 at 09:34:26PM +0000, Q. Schroll via Digitalmars-d-learn
wrote:
 On Friday, 4 August 2017 at 16:40:08 UTC, Stefan Koch wrote:
 [..]

 foreach(x;A .. B)
 it's lowerd to
 auto limit = B;
 auto key = A;
 for(auto x = key;key < limit;++key)
 {
   // use x
 }
That's enough to know that the foreach loop does not reuse the space for the iteration variable. That was what I cared about.
Note that using BigInt as iteration variable will probably cause a BigInt allocation per iteration, because operations on BigInt in general will allocate a new BigInt result. So `++key` will probably create a new instance of BigInt each time it's executed.
Right, but this is not a limitation of the API, just the implementation. It could be improved. https://issues.dlang.org/show_bug.cgi?id=17736 -Steve
Aug 09
parent Steven Schveighoffer <schveiguy yahoo.com> writes:
On 8/9/17 9:08 PM, Steven Schveighoffer wrote:
 Right, but this is not a limitation of the API, just the implementation. 
 It could be improved.
 
 https://issues.dlang.org/show_bug.cgi?id=17736
Based on H.S. Teoh's comment in the bug report, this actually is invalid. That's a tough requirement. -Steve
Aug 09