Skip to content
Permalink

Comparing changes

Choose two branches to see what’s changed or to start a new pull request. If you need to, you can also or learn more about diff comparisons.

Open a pull request

Create a new pull request by comparing changes across two branches. If you need to, you can also . Learn more about diff comparisons here.
base repository: jruby/jruby
Failed to load repositories. Confirm that selected base ref is valid, then try again.
Loading
base: 6ea39ea4d718
Choose a base ref
...
head repository: jruby/jruby
Failed to load repositories. Confirm that selected head ref is valid, then try again.
Loading
compare: 46aca6c47934
Choose a head ref
  • 5 commits
  • 2 files changed
  • 2 contributors

Commits on Nov 16, 2016

  1. add Kahan's compensated algorithm for Floats

    Fixes part of a bug identified in #4297
    phluid61 committed Nov 16, 2016
    Copy the full SHA
    be05f1b View commit details
  2. make Array#sum use Enumerable's addition logic

    Partially addresses a bug in #4297
    phluid61 committed Nov 16, 2016
    Copy the full SHA
    343028a View commit details

Commits on Nov 17, 2016

  1. change Array#sum to better match MRI

    Fixes most of the tests that weren't perfect in #4297.
    phluid61 committed Nov 17, 2016
    Copy the full SHA
    8a78908 View commit details
  2. fix Array#sum to handle Fixnum overflow

    This passes the final MRI test, referenced in #4297
    phluid61 committed Nov 17, 2016
    Copy the full SHA
    e49d272 View commit details
  3. Merge pull request #4309 from phluid61/feature/optimise-enumerable-sum

    fix Array#sum and Enumerable#sum
    headius authored Nov 17, 2016
    Copy the full SHA
    46aca6c View commit details
Showing with 231 additions and 16 deletions.
  1. +171 −12 core/src/main/java/org/jruby/RubyArray.java
  2. +60 −4 core/src/main/java/org/jruby/RubyEnumerable.java
183 changes: 171 additions & 12 deletions core/src/main/java/org/jruby/RubyArray.java
Original file line number Diff line number Diff line change
@@ -71,6 +71,7 @@

import java.io.IOException;
import java.lang.reflect.Array;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Collection;
import java.util.Comparator;
@@ -4327,25 +4328,183 @@ public IRubyObject sum(final ThreadContext context, IRubyObject init, final Bloc
return sumCommon(context, init, block);
}

/* FIXME: optimise for special types (e.g. Integer)? */
/* NB: MRI says "Array#sum method may not respect method redefinition of "+" methods such as Integer#+." */
public IRubyObject sumCommon(final ThreadContext context, IRubyObject init, final Block block) {
final Ruby runtime = context.runtime;
final IRubyObject result[] = new IRubyObject[] { init };
IRubyObject result = init;

/*
* This state machine is simple: it assumes all elements are the same type,
* and transitions to a later state when that assumption fails.
*
* The order of states is:
*
* - is_fixnum => { is_bignum | is_rational | is_float | other }
* - is_bignum => { is_rational | is_float | other }
* - is_rational => { is_float | other }
* - is_float => { other }
* - other [terminal]
*/
boolean is_fixnum=false, is_bignum=false, is_rational=false, is_float=false;

if (block.isGiven()) {
for (int i = 0; i < realLength; i++) {
IRubyObject value = block.yield(context, eltOk(i));
result[0] = result[0].callMethod(context, "+", value);
if (result instanceof RubyFixnum) {
is_fixnum = true;
} else if (result instanceof RubyBignum) {
is_bignum = true;
} else if (result instanceof RubyRational) {
is_rational = true;
} else if (result instanceof RubyFloat) {
is_float = true;
}

int i = 0;
IRubyObject value = null;

if (is_fixnum) {
long sum = ((RubyFixnum) result).getLongValue();
fixnum_loop:
for (; i < realLength; value=null, i++) {
if (value == null) {
value = eltOk(i);
if (block.isGiven()) {
value = block.yield(context, value);
}
}

if (value instanceof RubyFixnum) {
/* should not overflow long type */
long other = ((RubyFixnum) value).getLongValue();
long sum2 = sum + other;
if (Helpers.additionOverflowed(sum, other, sum2)) {
is_bignum = true;
break fixnum_loop;
} else {
sum = sum2;
}
} else if (value instanceof RubyBignum) {
is_bignum = true;
break fixnum_loop;
} else if (value instanceof RubyRational) {
is_rational = true;
break fixnum_loop;
} else {
is_float = value instanceof RubyFloat;
break fixnum_loop;
}
}
} else {
for (int i = 0; i < realLength; i++) {
IRubyObject value = eltOk(i);
result[0] = result[0].callMethod(context, "+", value);

if (is_bignum) {
result = RubyBignum.newBignum(runtime, sum);
} else if (is_rational) {
result = RubyRational.newRationalCanonicalize(context, sum, 1);
} else if (is_float) {
result = RubyFloat.newFloat(runtime, (double) sum);
} else {
result = RubyFixnum.newFixnum(runtime, sum);
}
}
if (is_bignum) {
BigInteger sum = ((RubyBignum) result).getBigIntegerValue();
bignum_loop:
for (; i < realLength; value=null, i++) {
if (value == null) {
value = eltOk(i);
if (block.isGiven()) {
value = block.yield(context, value);
}
}

if (value instanceof RubyFixnum) {
final RubyFixnum ival = (RubyFixnum) value;
final long lval = ival.getLongValue();
final BigInteger bval = BigInteger.valueOf(lval);
sum = sum.add(bval);
} else if (value instanceof RubyBignum) {
final RubyBignum ival = (RubyBignum) value;
final BigInteger bval = ival.getBigIntegerValue();
sum = sum.add(bval);
} else if (value instanceof RubyRational) {
is_rational = true;
break bignum_loop;
} else {
is_float = value instanceof RubyFloat;
break bignum_loop;
}
}

if (is_rational) {
result = RubyRational.newRationalCanonicalize(context, RubyBignum.newBignum(runtime, sum), RubyFixnum.one(runtime));
} else if (is_float) {
result = RubyFloat.newFloat(runtime, sum.doubleValue());
} else {
result = RubyBignum.newBignum(runtime, sum);
}
}
if (is_rational) {
rational_loop:
for (; i < realLength; value=null, i++) {
if (value == null) {
value = eltOk(i);
if (block.isGiven()) {
value = block.yield(context, value);
}
}

return result[0];
if (value instanceof RubyFixnum || value instanceof RubyBignum || value instanceof RubyRational) {
result = ((RubyRational) result).op_add(context, value);
} else if (value instanceof RubyFloat) {
result = RubyFloat.newFloat(runtime, ((RubyRational) result).getDoubleValue(context));
is_float = true;
break rational_loop;
} else {
break rational_loop;
}
}
}
if (is_float) {
double f = ((RubyFloat) result).getDoubleValue();
double c = 0.0;
double x, y, t;
float_loop:
for (; i < realLength; value=null, i++) {
if (value == null) {
value = eltOk(i);
if (block.isGiven()) {
value = block.yield(context, value);
}
}

if (value instanceof RubyFixnum) {
x = ((RubyFixnum) value).getDoubleValue();
} else if (value instanceof RubyBignum) {
x = ((RubyBignum) value).getDoubleValue();
} else if (value instanceof RubyRational) {
x = ((RubyRational) value).getDoubleValue(context);
} else if (value instanceof RubyFloat) {
x = ((RubyFloat) value).getDoubleValue();
} else {
break float_loop;
}
// Kahan's compensated summation algorithm
y = x - c;
t = f + y;
c = (t - f) - y;
f = t;
}
result = new RubyFloat(runtime, f);
}
//object_loop:
for (; i < realLength; value=null, i++) {
if (value == null) {
value = eltOk(i);
if (block.isGiven()) {
value = block.yield(context, value);
}
}

result = result.callMethod(context, "+", value);
}

return result;
}

public IRubyObject find(ThreadContext context, IRubyObject ifnone, Block block) {
64 changes: 60 additions & 4 deletions core/src/main/java/org/jruby/RubyEnumerable.java
Original file line number Diff line number Diff line change
@@ -919,18 +919,18 @@ public static IRubyObject sum(ThreadContext context, IRubyObject self, IRubyObje
return sumCommon(context, self, init, block);
}

/* FIXME: optimise for special types (e.g. Integer)? */
/* NB: MRI says "Enumerable#sum method may not respect method redefinition of "+" methods such as Integer#+." */
/* TODO: optimise for special types (e.g. Range, Hash, ...) */
public static IRubyObject sumCommon(final ThreadContext context, IRubyObject self, IRubyObject init, final Block block) {
final Ruby runtime = context.runtime;
final IRubyObject result[] = new IRubyObject[] { init };
final double memo[] = new double[] { 0.0 };

if (block.isGiven()) {
callEach(runtime, context, self, Signature.OPTIONAL, new BlockCallback() {
public IRubyObject call(ThreadContext ctx, IRubyObject[] largs, Block blk) {
IRubyObject larg = packEnumValues(ctx, largs);
IRubyObject val = block.yieldArray(ctx, larg, null);
result[0] = result[0].callMethod(context, "+", val);
result[0] = sumAdd(ctx, result[0], val, memo);

return ctx.nil;
}
@@ -939,7 +939,7 @@ public IRubyObject call(ThreadContext ctx, IRubyObject[] largs, Block blk) {
callEach(runtime, context, self, Signature.OPTIONAL, new BlockCallback() {
public IRubyObject call(ThreadContext ctx, IRubyObject[] largs, Block blk) {
IRubyObject larg = packEnumValues(ctx, largs);
result[0] = result[0].callMethod(context, "+", larg);
result[0] = sumAdd(ctx, result[0], larg, memo);

return ctx.nil;
}
@@ -949,6 +949,62 @@ public IRubyObject call(ThreadContext ctx, IRubyObject[] largs, Block blk) {
return result[0];
}

/* FIXME: optimise for special types (e.g. Integer)? */
/* NB: MRI says "Enumerable#sum method may not respect method redefinition of "+" methods such as Integer#+." */
public static IRubyObject sumAdd(final ThreadContext ctx, IRubyObject lhs, IRubyObject rhs, final double c[]) {
boolean floats = false;
double f = 0.0;
double x = 0.0, y, t;
if (lhs instanceof RubyFloat) {
if (rhs instanceof RubyFloat) {
f = ((RubyFloat) lhs).getValue();
x = ((RubyFloat) rhs).getValue();
floats = true;
} else if (rhs instanceof RubyFixnum) {
f = ((RubyFloat) lhs).getValue();
x = ((RubyFixnum) rhs).getDoubleValue();
floats = true;
} else if (rhs instanceof RubyBignum) {
f = ((RubyFloat) lhs).getValue();
x = ((RubyBignum) rhs).getDoubleValue();
floats = true;
} else if (rhs instanceof RubyRational) {
f = ((RubyFloat) lhs).getValue();
x = ((RubyRational) rhs).getDoubleValue(ctx);
floats = true;
}
} else if (rhs instanceof RubyFloat) {
if (lhs instanceof RubyFixnum) {
c[0] = 0.0;
f = ((RubyFixnum) lhs).getDoubleValue();
x = ((RubyFloat) rhs).getValue();
floats = true;
} else if (lhs instanceof RubyBignum) {
c[0] = 0.0;
f = ((RubyBignum) lhs).getDoubleValue();
x = ((RubyFloat) rhs).getValue();
floats = true;
} else if (lhs instanceof RubyRational) {
c[0] = 0.0;
f = ((RubyRational) lhs).getDoubleValue();
x = ((RubyFloat) rhs).getValue();
floats = true;
}
}

if (!floats) {
return lhs.callMethod(ctx, "+", rhs);
}

// Kahan's compensated summation algorithm
y = x - c[0];
t = f + y;
c[0] = (t - f) - y;
f = t;

return new RubyFloat(ctx.runtime, f);
}

public static IRubyObject injectCommon(final ThreadContext context, IRubyObject self, IRubyObject init, final Block block) {
final Ruby runtime = context.runtime;
final IRubyObject result[] = new IRubyObject[] { init };