Skip to content

Instantly share code, notes, and snippets.

@tombentley

tombentley/benchmark.ceylon

Created June 13, 2014 11:06
Show Gist options
  • Save tombentley/18ef2ac7dd7f58d53661 to your computer and use it in GitHub Desktop.
Save tombentley/18ef2ac7dd7f58d53661 to your computer and use it in GitHub Desktop.
Download ZIP
Some benchmarking for optimized iteration depending on runtime type
Raw
benchmark.ceylon
import ceylon.language.meta{type}
Integer dynamicIterationBench({Integer*} iterable) {
variable value sum = 0;
for (int in iterable) {
sum += int;
}
return sum;
}
Integer dynamicIterationBenchNoArrayOpt({Integer*} iterable) {
variable value sum = 0;
@disableOptimization:"ArrayIterationDynamic"
for (int in iterable) {
sum += int;
}
return sum;
}
Integer dynamicIterationBenchNoTupleOpt({Integer*} iterable) {
variable value sum = 0;
@disableOptimization:"TupleIterationDynamic"
for (int in iterable) {
sum += int;
}
return sum;
}
Integer dynamicIterationBenchNoOpts({Integer*} iterable) {
variable value sum = 0;
@disableOptimization
for (int in iterable) {
sum += int;
}
return sum;
}
void dynamicIterationBench_run(Integer n, {Integer*} list) {
String typeName;
if (is Tuple<Anything,Anything,Anything> list) {
typeName = "Tuple";
} else {
typeName = type(list).string;
}
print("``typeName``, list size=``list.size``");
variable value result = 0;
variable value t0 = system.nanoseconds;
for (i in 0..n) {
result = dynamicIterationBench(list);
}
variable value time = (system.nanoseconds-t0)/1_000_000.0;
print("dynamicIterationBench: n=``n``,\ttime=``time``ms,\tresult=``result``");
t0 = system.nanoseconds;
for (i in 0..n) {
result = dynamicIterationBenchNoArrayOpt(list);
}
time = (system.nanoseconds-t0)/1_000_000.0;
print("dynamicIterationBenchNoArrayOpt: n=``n``,\ttime=``time``ms,\tresult=``result``");
t0 = system.nanoseconds;
for (i in 0..n) {
result = dynamicIterationBenchNoTupleOpt(list);
}
time = (system.nanoseconds-t0)/1_000_000.0;
print("dynamicIterationBenchNoTupleOpt: n=``n``,\ttime=``time``ms,\tresult=``result``");
t0 = system.nanoseconds;
for (i in 0..n) {
result = dynamicIterationBenchNoOpts(list);
}
time = (system.nanoseconds-t0)/1_000_000.0;
print("dynamicIterationBenchNoOpts: n=``n``,\ttime=``time``ms,\tresult=``result``");
print("");
}
void dynamicIterationBench_main() {
print("warmup
------");
variable value end = 5;
variable value iterations = 100000;
dynamicIterationBench_run(iterations, [0, *(1..end)]);
dynamicIterationBench_run(iterations, Array<Integer>(0..end));
dynamicIterationBench_run(iterations, [*(0..end)]);
print("
timed
-----");
end = 500;
iterations = 1000;
dynamicIterationBench_run(iterations, [0, *(1..end)]);
dynamicIterationBench_run(iterations, Array<Integer>(0..end));
dynamicIterationBench_run(iterations, [*(0..end)]);
}
Raw
benchmark.java
package com.redhat.ceylon.compiler.java.test.statement.loop.optim;
@.com.redhat.ceylon.compiler.java.metadata.Ceylon(major = 7)
@.com.redhat.ceylon.compiler.java.metadata.Method
final class dynamicIterationBench_ {
private dynamicIterationBench_() {
}
@.com.redhat.ceylon.compiler.java.metadata.TypeInfo("ceylon.language::Integer")
static long dynamicIterationBench(@.com.redhat.ceylon.compiler.java.metadata.Name("iterable")
@.com.redhat.ceylon.compiler.java.metadata.TypeInfo("ceylon.language::Iterable<ceylon.language::Integer,ceylon.language::Null>")
final .ceylon.language.Iterable<? extends .ceylon.language.Integer, ? extends .java.lang.Object> iterable) {
long sum = 0L;
final .ceylon.language.Iterable<? extends .ceylon.language.Integer, ? extends .java.lang.Object> iterable$2 = iterable;
final boolean isArray$3 = iterable$2 instanceof .ceylon.language.Array;
final boolean isTuple$4 = iterable$2 instanceof .ceylon.language.Tuple;
.java.lang.Object elem$0 = null;
final .java.lang.Object array$5;
int i$6 = 0;
final int length$7;
if (isTuple$4) {
array$5 = ((.ceylon.language.Tuple)iterable$2).$getArray$();
i$6 = ((.ceylon.language.Tuple)iterable$2).$getFirst$();
length$7 = i$6 + ((.ceylon.language.Tuple)iterable$2).$getLength$();
} else if (isArray$3) {
array$5 = ((.ceylon.language.Array)iterable$2).toArray();
length$7 = .com.redhat.ceylon.compiler.java.Util.arrayLength(array$5);
} else {
array$5 = null;
length$7 = 0;
}
.ceylon.language.Iterator<? extends .ceylon.language.Integer> $int$iterator$$1 = isTuple$4 || isArray$3 ? null : iterable$2.iterator();
loop_0: while (isTuple$4 || isArray$3 ? i$6 < length$7 : !((elem$0 = $int$iterator$$1.next()) instanceof .ceylon.language.Finished)) {
if (isTuple$4 || isArray$3) elem$0 = .com.redhat.ceylon.compiler.java.Util.getObjectArray(array$5, i$6++);
final long $int = ((.ceylon.language.Integer)elem$0).longValue();
sum += $int;
}
return sum;
}
}
@.com.redhat.ceylon.compiler.java.metadata.Ceylon(major = 7)
@.com.redhat.ceylon.compiler.java.metadata.Method
final class dynamicIterationBenchNoArrayOpt_ {
private dynamicIterationBenchNoArrayOpt_() {
}
@.com.redhat.ceylon.compiler.java.metadata.TypeInfo("ceylon.language::Integer")
static long dynamicIterationBenchNoArrayOpt(@.com.redhat.ceylon.compiler.java.metadata.Name("iterable")
@.com.redhat.ceylon.compiler.java.metadata.TypeInfo("ceylon.language::Iterable<ceylon.language::Integer,ceylon.language::Null>")
final .ceylon.language.Iterable<? extends .ceylon.language.Integer, ? extends .java.lang.Object> iterable) {
long sum = 0L;
final .ceylon.language.Iterable<? extends .ceylon.language.Integer, ? extends .java.lang.Object> iterable$10 = iterable;
final boolean isTuple$11 = iterable$10 instanceof .ceylon.language.Tuple;
.java.lang.Object elem$8 = null;
final .java.lang.Object array$12;
int i$13 = 0;
final int length$14;
if (isTuple$11) {
array$12 = ((.ceylon.language.Tuple)iterable$10).$getArray$();
i$13 = ((.ceylon.language.Tuple)iterable$10).$getFirst$();
length$14 = i$13 + ((.ceylon.language.Tuple)iterable$10).$getLength$();
} else {
array$12 = null;
length$14 = 0;
}
.ceylon.language.Iterator<? extends .ceylon.language.Integer> $int$iterator$$9 = isTuple$11 ? null : iterable$10.iterator();
loop_1: while (isTuple$11 ? i$13 < length$14 : !((elem$8 = $int$iterator$$9.next()) instanceof .ceylon.language.Finished)) {
if (isTuple$11) elem$8 = .com.redhat.ceylon.compiler.java.Util.getObjectArray(array$12, i$13++);
final long $int = ((.ceylon.language.Integer)elem$8).longValue();
sum += $int;
}
return sum;
}
}
@.com.redhat.ceylon.compiler.java.metadata.Ceylon(major = 7)
@.com.redhat.ceylon.compiler.java.metadata.Method
final class dynamicIterationBenchNoTupleOpt_ {
private dynamicIterationBenchNoTupleOpt_() {
}
@.com.redhat.ceylon.compiler.java.metadata.TypeInfo("ceylon.language::Integer")
static long dynamicIterationBenchNoTupleOpt(@.com.redhat.ceylon.compiler.java.metadata.Name("iterable")
@.com.redhat.ceylon.compiler.java.metadata.TypeInfo("ceylon.language::Iterable<ceylon.language::Integer,ceylon.language::Null>")
final .ceylon.language.Iterable<? extends .ceylon.language.Integer, ? extends .java.lang.Object> iterable) {
long sum = 0L;
final .ceylon.language.Iterable<? extends .ceylon.language.Integer, ? extends .java.lang.Object> iterable$17 = iterable;
final boolean isArray$18 = iterable$17 instanceof .ceylon.language.Array;
.java.lang.Object elem$15 = null;
final .java.lang.Object array$19;
int i$20 = 0;
final int length$21;
if (isArray$18) {
array$19 = ((.ceylon.language.Array)iterable$17).toArray();
length$21 = .com.redhat.ceylon.compiler.java.Util.arrayLength(array$19);
} else {
array$19 = null;
length$21 = 0;
}
.ceylon.language.Iterator<? extends .ceylon.language.Integer> $int$iterator$$16 = isArray$18 ? null : iterable$17.iterator();
loop_2: while (isArray$18 ? i$20 < length$21 : !((elem$15 = $int$iterator$$16.next()) instanceof .ceylon.language.Finished)) {
if (isArray$18) elem$15 = .com.redhat.ceylon.compiler.java.Util.getObjectArray(array$19, i$20++);
final long $int = ((.ceylon.language.Integer)elem$15).longValue();
sum += $int;
}
return sum;
}
}
@.com.redhat.ceylon.compiler.java.metadata.Ceylon(major = 7)
@.com.redhat.ceylon.compiler.java.metadata.Method
final class dynamicIterationBenchNoOpts_ {
private dynamicIterationBenchNoOpts_() {
}
@.com.redhat.ceylon.compiler.java.metadata.TypeInfo("ceylon.language::Integer")
static long dynamicIterationBenchNoOpts(@.com.redhat.ceylon.compiler.java.metadata.Name("iterable")
@.com.redhat.ceylon.compiler.java.metadata.TypeInfo("ceylon.language::Iterable<ceylon.language::Integer,ceylon.language::Null>")
final .ceylon.language.Iterable<? extends .ceylon.language.Integer, ? extends .java.lang.Object> iterable) {
long sum = 0L;
.java.lang.Object elem$22;
.ceylon.language.Iterator<? extends .ceylon.language.Integer> $int$iterator$$23 = iterable.iterator();
loop_3: while (!((elem$22 = $int$iterator$$23.next()) instanceof .ceylon.language.Finished)) {
final long $int = ((.ceylon.language.Integer)elem$22).longValue();
sum += $int;
}
return sum;
}
}
@.com.redhat.ceylon.compiler.java.metadata.Ceylon(major = 7)
@.com.redhat.ceylon.compiler.java.metadata.Method
final class dynamicIterationBench_run_ {
private dynamicIterationBench_run_() {
}
@.com.redhat.ceylon.compiler.java.metadata.TypeInfo("ceylon.language::Anything")
static void dynamicIterationBench_run(@.com.redhat.ceylon.compiler.java.metadata.Name("n")
@.com.redhat.ceylon.compiler.java.metadata.TypeInfo("ceylon.language::Integer")
final long n, @.com.redhat.ceylon.compiler.java.metadata.Name("list")
@.com.redhat.ceylon.compiler.java.metadata.TypeInfo("ceylon.language::Iterable<ceylon.language::Integer,ceylon.language::Null>")
final .ceylon.language.Iterable<? extends .ceylon.language.Integer, ? extends .java.lang.Object> list) {
final .java.lang.String typeName;
if (list instanceof .ceylon.language.Tuple) {
typeName = "Tuple";
} else {
typeName = .ceylon.language.meta.type_.<.ceylon.language.Iterable<? extends .ceylon.language.Integer, ? extends .java.lang.Object>>type(.com.redhat.ceylon.compiler.java.runtime.model.TypeDescriptor.klass(.ceylon.language.Iterable.class, .ceylon.language.Integer.$TypeDescriptor$, .ceylon.language.Null.$TypeDescriptor$), (.ceylon.language.Iterable)list).toString();
}
.ceylon.language.print_.print(.ceylon.language.String.instance(new .java.lang.StringBuilder().append(typeName).append(", list size=").append(list.getSize()).toString()));
long result = 0L;
long t0 = .ceylon.language.system_.get_().getNanoseconds();
final long $ceylontmp$start$26 = 0L;
final long $ceylontmp$end$27 = n;
final boolean $ceylontmp$increasing$28 = $ceylontmp$start$26 <= $ceylontmp$end$27;
final long $ceylontmp$incr$29 = $ceylontmp$increasing$28 ? 1L : -1L;
loop_4: for (long i$30 = $ceylontmp$start$26; $ceylontmp$increasing$28 ? i$30 - $ceylontmp$end$27 <= 0L : i$30 - $ceylontmp$end$27 >= 0L; i$30 += $ceylontmp$incr$29) {
final long i = i$30;
result = .com.redhat.ceylon.compiler.java.test.statement.loop.optim.dynamicIterationBench_.dynamicIterationBench(list);
}
double time = (.ceylon.language.system_.get_().getNanoseconds() - t0) / 1000000.0;
.ceylon.language.print_.print(.ceylon.language.String.instance(new .java.lang.StringBuilder().append("dynamicIterationBench: n=").append(n).append(",\ttime=").append(time).append("ms,\tresult=").append(result).toString()));
t0 = .ceylon.language.system_.get_().getNanoseconds();
final long $ceylontmp$start$31 = 0L;
final long $ceylontmp$end$32 = n;
final boolean $ceylontmp$increasing$33 = $ceylontmp$start$31 <= $ceylontmp$end$32;
final long $ceylontmp$incr$34 = $ceylontmp$increasing$33 ? 1L : -1L;
loop_5: for (long i$35 = $ceylontmp$start$31; $ceylontmp$increasing$33 ? i$35 - $ceylontmp$end$32 <= 0L : i$35 - $ceylontmp$end$32 >= 0L; i$35 += $ceylontmp$incr$34) {
final long i = i$35;
result = .com.redhat.ceylon.compiler.java.test.statement.loop.optim.dynamicIterationBenchNoArrayOpt_.dynamicIterationBenchNoArrayOpt(list);
}
time = (.ceylon.language.system_.get_().getNanoseconds() - t0) / 1000000.0;
.ceylon.language.print_.print(.ceylon.language.String.instance(new .java.lang.StringBuilder().append("dynamicIterationBenchNoArrayOpt: n=").append(n).append(",\ttime=").append(time).append("ms,\tresult=").append(result).toString()));
t0 = .ceylon.language.system_.get_().getNanoseconds();
final long $ceylontmp$start$36 = 0L;
final long $ceylontmp$end$37 = n;
final boolean $ceylontmp$increasing$38 = $ceylontmp$start$36 <= $ceylontmp$end$37;
final long $ceylontmp$incr$39 = $ceylontmp$increasing$38 ? 1L : -1L;
loop_6: for (long i$40 = $ceylontmp$start$36; $ceylontmp$increasing$38 ? i$40 - $ceylontmp$end$37 <= 0L : i$40 - $ceylontmp$end$37 >= 0L; i$40 += $ceylontmp$incr$39) {
final long i = i$40;
result = .com.redhat.ceylon.compiler.java.test.statement.loop.optim.dynamicIterationBenchNoTupleOpt_.dynamicIterationBenchNoTupleOpt(list);
}
time = (.ceylon.language.system_.get_().getNanoseconds() - t0) / 1000000.0;
.ceylon.language.print_.print(.ceylon.language.String.instance(new .java.lang.StringBuilder().append("dynamicIterationBenchNoTupleOpt: n=").append(n).append(",\ttime=").append(time).append("ms,\tresult=").append(result).toString()));
t0 = .ceylon.language.system_.get_().getNanoseconds();
final long $ceylontmp$start$41 = 0L;
final long $ceylontmp$end$42 = n;
final boolean $ceylontmp$increasing$43 = $ceylontmp$start$41 <= $ceylontmp$end$42;
final long $ceylontmp$incr$44 = $ceylontmp$increasing$43 ? 1L : -1L;
loop_7: for (long i$45 = $ceylontmp$start$41; $ceylontmp$increasing$43 ? i$45 - $ceylontmp$end$42 <= 0L : i$45 - $ceylontmp$end$42 >= 0L; i$45 += $ceylontmp$incr$44) {
final long i = i$45;
result = .com.redhat.ceylon.compiler.java.test.statement.loop.optim.dynamicIterationBenchNoOpts_.dynamicIterationBenchNoOpts(list);
}
time = (.ceylon.language.system_.get_().getNanoseconds() - t0) / 1000000.0;
.ceylon.language.print_.print(.ceylon.language.String.instance(new .java.lang.StringBuilder().append("dynamicIterationBenchNoOpts: n=").append(n).append(",\ttime=").append(time).append("ms,\tresult=").append(result).toString()));
.ceylon.language.print_.print(.ceylon.language.String.instance(""));
}
}
@.com.redhat.ceylon.compiler.java.metadata.Ceylon(major = 7)
@.com.redhat.ceylon.compiler.java.metadata.Method
final class dynamicIterationBench_main_ {
private dynamicIterationBench_main_() {
}
@.com.redhat.ceylon.compiler.java.metadata.TypeInfo("ceylon.language::Anything")
static void dynamicIterationBench_main() {
.ceylon.language.print_.print(.ceylon.language.String.instance("warmup\n------"));
final .com.redhat.ceylon.compiler.java.language.VariableBoxLong end = new .com.redhat.ceylon.compiler.java.language.VariableBoxLong(5L);
long iterations = 100000L;
.com.redhat.ceylon.compiler.java.test.statement.loop.optim.dynamicIterationBench_run_.dynamicIterationBench_run(iterations, new .ceylon.language.Tuple<.ceylon.language.Integer, .ceylon.language.Integer, .ceylon.language.Range<.ceylon.language.Integer>>(.ceylon.language.Integer.$TypeDescriptor$, new .java.lang.Object[]{.ceylon.language.Integer.instance(0L)}, new .ceylon.language.Range<.ceylon.language.Integer>(.ceylon.language.Integer.$TypeDescriptor$, .ceylon.language.Integer.instance(1L), .ceylon.language.Integer.instance(end.ref))));
.com.redhat.ceylon.compiler.java.test.statement.loop.optim.dynamicIterationBench_run_.dynamicIterationBench_run(iterations, new .ceylon.language.Array<.ceylon.language.Integer>(.ceylon.language.Integer.$TypeDescriptor$, new .ceylon.language.Range<.ceylon.language.Integer>(.ceylon.language.Integer.$TypeDescriptor$, .ceylon.language.Integer.instance(0L), .ceylon.language.Integer.instance(end.ref))));
.com.redhat.ceylon.compiler.java.test.statement.loop.optim.dynamicIterationBench_run_.dynamicIterationBench_run(iterations, new .ceylon.language.Range<.ceylon.language.Integer>(.ceylon.language.Integer.$TypeDescriptor$, .ceylon.language.Integer.instance(0L), .ceylon.language.Integer.instance(end.ref)));
.ceylon.language.print_.print(.ceylon.language.String.instance("\ntimed\n-----"));
end.ref = 500L;
iterations = 1000L;
.com.redhat.ceylon.compiler.java.test.statement.loop.optim.dynamicIterationBench_run_.dynamicIterationBench_run(iterations, new .ceylon.language.Tuple<.ceylon.language.Integer, .ceylon.language.Integer, .ceylon.language.Range<.ceylon.language.Integer>>(.ceylon.language.Integer.$TypeDescriptor$, new .java.lang.Object[]{.ceylon.language.Integer.instance(0L)}, new .ceylon.language.Range<.ceylon.language.Integer>(.ceylon.language.Integer.$TypeDescriptor$, .ceylon.language.Integer.instance(1L), .ceylon.language.Integer.instance(end.ref))));
.com.redhat.ceylon.compiler.java.test.statement.loop.optim.dynamicIterationBench_run_.dynamicIterationBench_run(iterations, new .ceylon.language.Array<.ceylon.language.Integer>(.ceylon.language.Integer.$TypeDescriptor$, new .ceylon.language.Range<.ceylon.language.Integer>(.ceylon.language.Integer.$TypeDescriptor$, .ceylon.language.Integer.instance(0L), .ceylon.language.Integer.instance(end.ref))));
.com.redhat.ceylon.compiler.java.test.statement.loop.optim.dynamicIterationBench_run_.dynamicIterationBench_run(iterations, new .ceylon.language.Range<.ceylon.language.Integer>(.ceylon.language.Integer.$TypeDescriptor$, .ceylon.language.Integer.instance(0L), .ceylon.language.Integer.instance(end.ref)));
}
@.com.redhat.ceylon.compiler.java.metadata.Ignore
public static void main(.java.lang.String[] args) {
.ceylon.language.process_.get_().setupArguments(args);
.com.redhat.ceylon.compiler.java.test.statement.loop.optim.dynamicIterationBench_main_.dynamicIterationBench_main();
}
}
Raw
output.txt
warmup
------
Tuple, list size=6
dynamicIterationBench: n=100000, time=11.710846ms, result=15
dynamicIterationBenchNoArrayOpt: n=100000, time=9.513722ms, result=15
dynamicIterationBenchNoTupleOpt: n=100000, time=31.278022ms, result=15
dynamicIterationBenchNoOpts: n=100000, time=15.073265ms, result=15
ceylon.language::Array<ceylon.language::Integer>, list size=6
dynamicIterationBench: n=100000, time=126.824863ms, result=15
dynamicIterationBenchNoArrayOpt: n=100000, time=43.104664ms, result=15
dynamicIterationBenchNoTupleOpt: n=100000, time=41.290896ms, result=15
dynamicIterationBenchNoOpts: n=100000, time=29.073494ms, result=15
ceylon.language::Range<ceylon.language::Integer>, list size=6
dynamicIterationBench: n=100000, time=10409.864396ms, result=15
dynamicIterationBenchNoArrayOpt: n=100000, time=9770.591351ms, result=15
dynamicIterationBenchNoTupleOpt: n=100000, time=9538.060251ms, result=15
dynamicIterationBenchNoOpts: n=100000, time=9944.887966ms, result=15
timed
-----
Tuple, list size=501
dynamicIterationBench: n=1000, time=1.958198ms, result=125250
dynamicIterationBenchNoArrayOpt: n=1000, time=1.956592ms, result=125250
dynamicIterationBenchNoTupleOpt: n=1000, time=6.23644ms, result=125250
dynamicIterationBenchNoOpts: n=1000, time=13.763609ms, result=125250
ceylon.language::Array<ceylon.language::Integer>, list size=501
dynamicIterationBench: n=1000, time=1.752866ms, result=125250
dynamicIterationBenchNoArrayOpt: n=1000, time=7.474439ms, result=125250
dynamicIterationBenchNoTupleOpt: n=1000, time=1.579102ms, result=125250
dynamicIterationBenchNoOpts: n=1000, time=8.394802ms, result=125250
ceylon.language::Range<ceylon.language::Integer>, list size=501
dynamicIterationBench: n=1000, time=5166.575396ms, result=125250
dynamicIterationBenchNoArrayOpt: n=1000, time=5062.034519ms, result=125250
dynamicIterationBenchNoTupleOpt: n=1000, time=4919.215751ms, result=125250
dynamicIterationBenchNoOpts: n=1000, time=4878.312542ms, result=125250
Raw
remarks.md

This is trying to assess the costs/benefits of different for transformations where we only know the static type of the Iteratable is Iterable (and not anything more specific).

It seems that using a loop transformation which is specialized for the runtime types Array and Tuple does have a small cost (look at the times for the Range argument, it runs in 4878ms if we generate a simple loop, but increases to 5166ms if the loop has optimizations for array and tuple).

On the other hand those optimizations come with significant benefit when the argument is a Tuple (13ms down to 2ms) or Array (8ms down to 2ms).

However, the most obvious question is "Why is Range iteration so slow"? (Note we already have optimizations for when the static type of the for Iterable is a Range). The answer might be the assert(is Enumerable<Element> next) in EnumerableRangeBy.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment