List iterator question...
Jeffrey Peacock
this discussion but let me post it here too.
Given:
for (int i=0; i < list.size(); i++) {
}
OR
final int size = list.size();
for (int i=0; i < size; i++) {
}
Assume the iterator construct is disallowed for reasons that become
evident in the content of the loop -- i.e., you need i, the index,
for something else.
So which construct is better?
I'll start it off: construct 1 is patently wrong. And the religious
argument that is about to erupt over this will surprise you.
Background:
I am in the process of looking for work and I am discovering that how I
think about coding is different than others. But I have also noticed it
even when I am working with others, and of course teaching. Some of it
can be traced to the path of languages I have used: ASM, BASIC, Lisp,
Pascal, Fortran, PL/I, C, C++, Java (I think that covers it). The rest
can be traced to experience, the core principle being: "Don't ever
assume that will not happen."
Anyway, some of my coding has raised eyebrows in the interview process,
and sometimes in day-to-day work. I am noticing that it comes from
mostly from younger, less experienced crowd. So, am I to old to be
relevant? Or am I too senior to be respected by less experienced
engineers because:
1) They have learned the "best way" to do something, due to what they
needed to answer on tests to get their degree, and I must be wrong
because that is not what they were taught,
OR
2) My experience allows me to see things differently than they do which
has a greater, or at least different value?
Furthermore, I see this difference as working against me. Decisions are
being made by simple things, as well as things like above.
Mind you this is just the tip of the iceberg, the simplest example I
could find/remember. I have several more. Mostly from time reviewing
code for a larger projects.
Anyway, please share your thoughts.
/J
Wolf Paulus
package com.techcasita.cs;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
/**
* Created by wolf on 1/17/17.
*/
public class Loop {
final List<String> list = new ArrayList(Arrays.asList("A", "B", "C"));
public static void main(final String[] args) {
final Loop l = new Loop();
l.loop1();
l.loop2();
}
void loop1() {
for (int i = 0; i < list.size(); i++) {
System.out.println(list.get(i));
}
}
void loop2() {
final int size = list.size();
for (int i = 0; i < size; i++) {
System.out.println(list.get(i));
}
}
}
--
You received this message because you are subscribed to the Google Groups "SoCal Android Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to socal-androi...@googlegroups.com.
To post to this group, send email to socal-...@googlegroups.com.
To view this discussion on the web visit https://groups.google.com/d/msgid/socal-android/93ff6f49-6171-6a06-1870-0ee99b04a3c3%40JeffreyPeacock.com.
For more options, visit https://groups.google.com/d/optout.
Jeffrey Peacock
In general I agree with you. However, experience across a number of platforms, especially embedded and constrained hardware (e.g., not desktops) has biased my thinking to:
"Look for efficiency and then implement that WRT readability
and maintainability"
Benchmark code (please check my work/math):So, I am not a byte-code-optimizer, JIT, or HotSpot guru, but I would argue that list.size() within the loop expression cannot be optimized away by the optimizer.
It is likely that you are all assuming 2 things:
1) List<Item> list = new ListOFItems<>();
This implies that the variable list is a reference to an object that implements the List interface.
2) You are assuming the list.size() evaluates in the list object as { return size; }
So 1: an interface says nothing about the implementation. The implementation of list.size() is unknown.
For 2: I think there is an assumption that the optimizer can look ahead, and that is partially true, but it is not infallible. Also, Java is a "write once, run everywhere language". The 1st thing that should jump out is that not all JVM's will be the same.
Even if you assume the origin of list is: List<Item> list = new ArrayList<>(); You cannot assume the implementation of ArrayList is optimal or well implemented. This becomes more obvious when we consider List<Item> list = new PerverseLinkedList<>(); where list.size() is not implemented as a simple reply like { return size; } but a calculation, perhaps traversing all the elements of the list. Then the performance of list.size() takes on a new meaning the becomes more obvious. However, for (int i=0; i < list.size(); i++) -- i.e., expression evaluation in the loop expression - should be its own red flag.
Undoubtedly someone will argue that the PerverseLinkedList, or anything like it, will ever happen. Well, consider that the method signature wrapping that snippet of code is:
public void doSomething(final List<Item> list) {This alone shows that you cannot make any assumption regarding the class that implements the List interface, as it should be, and was implied in the snippet I provided.
}
So let me sum up my thinking so far:
1. We know nothing about the implementation of List, and we rarely do, even when we think we do. And what we think we know does not mean it will remain constant over the life of the code.
2. It is not safe to assume the compiler or the JVM optimizer will fix all the things you think it will.
If someone were to benchmark the differences of the two snippets, assuming an ArrayList as the underlying class, or even a dumb class optimized for the benchmark, and a sufficiently large list, you'll find some surprising results.
/J
On 01/17/2017 03:40 PM, Daniel Webster wrote:
Most modern compilers will introduce the temp variable for you as an optimization. HotSpot almost certainly will. Actually, for a fixed loop of short length, HotSpot probably unrolls the loop and there is no "loop" at runtime anyway.
DW
package benchmarks;
/**
* @author Jeffrey Peacock (je...@wonkware.com)
*/
public final class Loops
{
public static void main (final String[] args) {
final SpecialList list = new SpecialList();
long startTime = System.currentTimeMillis();
for (int i=0; i < list.size(); i++) {
final Object obj = list.get(i);
}
long endTime = System.currentTimeMillis();
final long elapsed_1 = endTime - startTime;
startTime = System.currentTimeMillis();
final int size = list.size();
for (int i=0; i < size; i++) {
final Object obj = list.get(i);
}
endTime = System.currentTimeMillis();
final long elapsed_2 = endTime - startTime;
System.out.println("Elpased 1 = "+ elapsed_1);
System.out.println("Elpased 2 = "+ elapsed_2);
if (elapsed_1 > elapsed_2) {
final double diff = elapsed_1 - elapsed_2;
final double pdiff = (diff / elapsed_1) * 100.00D;
System.out.println("Idiom 2 is faster by " + pdiff +"%");
}
else {
final double diff = elapsed_2 - elapsed_1;
final double pdiff = (diff / elapsed_2) * 100.00D;
System.out.println("Idiom 1 is faster by " + pdiff +"%");
}
}
static class SpecialList
{
final int size = 1000000000;
final Object obj = new Object();
public int size() {
return size;
}
public Object get(final int index) {
return obj;
}
}
}
To view this discussion on the web visit https://groups.google.com/d/msgid/socal-android/5A51DC14-E86A-469D-8E5C-EA5EA884351C%40wolfpaulus.com.
Jeffrey Peacock
A better benchmark is below. Typical values for runs I did are:
Elpased 1 = 131ms
Elpased 2 = 115ms
Elpased 3 = 42ms
Idiom 1 is slower than 2 by 1.00x
Idiom 2 is faster than 1 by 12.21%
Idiom 2 is slower than 3 by 2.00x
Idiom 3 is faster than 2 by 63.48%
Idiom 1 is slower than 3 by 3.00x
Idiom 3 is faster than 1 by 67.94%
package benchmarks;
import java.text.DecimalFormat;
import java.util.Iterator;
/**
* @author Jeffrey Peacock (je...@wonkware.com)
*/
public final class Loops
{
private static final DecimalFormat formatter = new DecimalFormat("0.00");
public static void main (final String[] args) {
final BenchmarkList<Item> list = new BenchmarkList<Item>(new Item());
// construct 1
long startTime = System.currentTimeMillis();
for (final Item item : list) {
// Be sure to do some minimal work in the loop to
// ensure a NOOP statement which the compiler/optimizer
// might catch. The "work" should be the same across
// all test cases.
final Item obj = item.get(0);
obj.setValue(1);
}
long endTime = System.currentTimeMillis();
final long elapsed_1 = endTime - startTime;
// construct 2
startTime = System.currentTimeMillis();
for (int i=0; i < list.size(); i++) {
final Item obj = list.get(i);
obj.setValue(1);
}
endTime = System.currentTimeMillis();
final long elapsed_2 = endTime - startTime;
// construct 3
startTime = System.currentTimeMillis();
final int size = list.size();
for (int i=0; i < size; i++) {
final Item obj = list.get(i);
obj.setValue(1);
}
endTime = System.currentTimeMillis();
final long elapsed_3 = endTime - startTime;
System.out.println("Elpased 1 = "+ elapsed_1 + "ms");
System.out.println("Elpased 2 = "+ elapsed_2 + "ms");
System.out.println("Elpased 3 = "+ elapsed_3 + "ms");
if (elapsed_1 > elapsed_2) {
final double diff = elapsed_1 - elapsed_2;
final double pdiff = (diff / elapsed_1) * 100.00D;
System.out.println("Idiom 1 is slower than 2 by " + formatter.format(elapsed_1/elapsed_2) + "x");
System.out.println("Idiom 2 is faster than 1 by " + formatter.format(pdiff) +"%");
}
if (elapsed_2 > elapsed_3) {
final double diff = elapsed_2 - elapsed_3;
final double pdiff = (diff / elapsed_2) * 100.00D;
System.out.println("Idiom 2 is slower than 3 by " + formatter.format(elapsed_2/elapsed_3) + "x");
System.out.println("Idiom 3 is faster than 2 by " + formatter.format(pdiff) +"%");
}
if (elapsed_1 > elapsed_3) {
final double diff = elapsed_1 - elapsed_3;
final double pdiff = (diff / elapsed_1) * 100.00D;
System.out.println("Idiom 1 is slower than 3 by " + formatter.format(elapsed_1/elapsed_3) + "x");
System.out.println("Idiom 3 is faster than 1 by " + formatter.format(pdiff) +"%");
}
}
static class BenchmarkList<T> implements Iterable<T>
{
private final int size = (int)Math.pow(10, 12);
private final T obj;
public BenchmarkList(final T obj) {
this.obj = obj;
}
public int size() {
return size;
}
public T get(final int index) {
return obj;
}
@Override
public Iterator<T> iterator() {
return new BenchmarkIterable<T>(size, obj);
}
}
static class BenchmarkIterable<T> implements Iterator<T>
{
private int size;
private final T obj;
public BenchmarkIterable (final int size, final T obj) {
this.size = size;
this.obj = obj;
}
public boolean hasNext() {
if (size-- > 0) {
return true;
}
return false;
}
public T next() {
return obj;
}
public void remove() {
//implement... if supported.
}
}
static class Item {
private final Item obj = this;
public Item get(final int index) {
return obj;
}
private int value = 0;
public void setValue(final int value) {
this.value = value;
}
public int getValue() {
return value;
}
}
}
To view this discussion on the web visit https://groups.google.com/d/msgid/socal-android/f8047b1e-ffc9-946a-f5a7-8b800eb46bdf%40JeffreyPeacock.com.