Market size

[poetix]

Typically in Java you have an interface, and a proxy which delegates calls on that interface's methods to a wrapped implementation, e.g.

Code: Select all

public interface EfficientCollection<T> {

  int getSize();
  T getItem(int index);
  EfficientCollection<T> addItem(T item);
  
}

public class EmptyEfficientCollection<T> implements EfficientCollection<T> {
  @Override
  public int getSize() {
    return 0;
  }
  
  @Override
  public T getItem(int index) {
    return null; // or throw an exception, etc
  }
  
  @Override
  public EfficientCollection<T> addItem(T item) {
    return new SingletonEfficientCollection<T>(item);
  }
}

public class SingletonEfficientCollection<T> implements EfficientCollection<T> {

  private final T item;
  
  public SingletonEfficientCollection(T item) {
    this.item = item;
  }
  
  @Override
  public int getSize() {
    return 1;
  }
  
  @Override
  public T getItem(int index) {
    return index == 0 ? item : null;
  }
  
  @Override
  public EfficientCollection<T> addItem(T item) {
    return new ArrayEfficientCollection<T>((T[]) new Object[] {this.item, item});
  }
}

public class ArrayEfficientCollection<T> implements EfficientCollection<T> {

  private final T[] items;
  
  public SingletonEfficientCollection(T[] items) {
    this.items = items;
  }
  
  @Override
  public int getSize() {
    return items.length;
  }
  
  @Override
  public T getItem(int index) {
    return items[index];
  }
  
  @Override
  public EfficientCollection<T> addItem(T item) {
     // figure out how best to extend the collection storage
  }
}

public class WrappedEfficientCollection<T> implements EfficientCollection<T> {

    private EfficientCollection<T> innerCollection = new EmptyEfficientCollection<T>();
  
    @Override
    public int getSize() {
      return innerCollection.getSize();
    }
  
    @Override
    public T getItem(int index) {
      return innerCollection.getItem(index);
    }
  
    @Override
    public EfficientCollection<T> addItem(T item) {
       innerCollection = innerCollection.addItem(item); // replaces the inner collection with the chosen implementation
       return this; // the user of the wrapper only ever sees the wrapper
    }
}

Lambdas offer a less cumbersome way to do this on a smaller scale, if the implementation you're replacing is just the implementation of a single method rather than a bundle of methods.

[ColinP]

That's really neat.

Thank you very much for taking the time to illustrate how the behaviour I described might be implemented in Java.

Also thanks for the edit, I did suspect the implements interface bits were missing in the original.

This forum really benefits from people like yourself getting involved as many of us here have only escaped from C++ relatively recently and we are still learning the more intricate aspects of Java.

[poetix]

Thanks! Here's a more lightweight example, using lambdas and method references. Suppose to begin with we just use a conditional:

Code: Select all

private boolean isHighQualityFilterSwitchedOn;

public void setHighQualityFilterSwitchedOn(boolean isHighQualityFilterSwitchedOn) {
  this.isHighQualityFilterSwitchedOn = true;
}

public double processSample(double input) {
  if (isHighQualityFilterSwitchedOn) {
    return applyHighQualityFilter(input);
  } else {
    return applyLowQualityFilter(input);
  }
}

private double applyHighQualityFilter(double input) {
  // etc
}

private double applyLowQualityFilter(double input) {
  // etc
}

Every time we pass through processSample we're checking the conditional and branching. But we could "remember" the branch to take, and just take that one:

Code: Select all

private DoubleTransformer filterBehaviour = this::applyLowQualityFilter; // default to low quality

public void setHighQualityFilterSwitchedOn(boolean isHighQualityFilterSwitchedOn) {
   filterBehaviour = isHighQualityFilterSwitchedOn ? this::applyHighQualityFilter : this::applyLowQualityFilter;
}

public double processSample(double input) {
  return filterBehaviour.apply(input);
}

private double applyHighQualityFilter(double input) {
  // etc
}

private double applyLowQualityFilter(double input) {
  // etc
}

Not only is it slightly more concise code, it eliminates the branching in [processSample] - we only branch when the value of the toggle changes, and memoize the outcome in the lambda itself.

DoubleTransformer looks like this, by the way:

Code: Select all

@FunctionalInterface
public interface DoubleTransformer {

  double apply(double value);
  
}

- it's a single-method interface to which any lambda or any method reference having the same signature can be cast. You could just use Function<Double, Double>, which is already defined, but then you're accepting and returning boxed Doubles rather than primitive doubles, which is not ideal.

[ColinP]

But although direct branching as a result of logic is avoided presumably there'e still an indirection occurring. We aren't just flowing to the next instruction, the JVM is presumably loading a pointer to the method and making a call. So in this simple example there's no efficiency improvement as the pipelining still gets messed with right?

But in a more complicated scenario it WOULD be more efficient as there's only one indirection and then we can be executing a specialised version of the code that doesn't have to make any branches because it's predetermined what the logic requires. In other words we can replace multiple branches with one call

[poetix]

The method call is happening inside the branching version as well - we've just "memoised" the choice of method.

I'll run a JMH benchmark on this some time soon and see what the numbers look like. My guess is that for the trivial example there's not much in it...

[ColinP]

But in the conditional branched version the call can be avoided by being automatically inlined.

However I can see that this fairly trivial example is just a demonstration of the concept and in practice one could indeed see significant gains in both efficiency and elegance.