locationtech / geotrellis

GeoTrellis is a geographic data processing engine for high performance applications.
http://geotrellis.io
Other
1.33k stars 360 forks source link

Potential for optimization in BreakMap #1974

Open lossyrob opened 7 years ago

lossyrob commented 7 years ago

BreakMap is currently specialized, but I suspect that the callout to an unspecialized BTree, and potentially it's usage of unspecialized Option and Either, cause it to box.

This issue should track the investigation into the boxing of BreakMap, and potential optimization work.

See: https://github.com/locationtech/geotrellis/blob/2419b48e7f3ab848c4dafe8cbd3e6fb2522ff298/raster/src/main/scala/geotrellis/raster/render/BreakMap.scala#L127, this specialized generic gets pushed into an unspecialized method.

lossyrob commented 7 years ago

Here is the BreakMap bytecode, where there seems to be boxing:

Compiled from "BreakMap.scala"
public class geotrellis.raster.render.BreakMap<A, B> implements scala.Function1<A, B>, scala.Serializable {
  public final geotrellis.raster.render.MapStrategy<B> strategy;

  public final scala.Function1<A, java.lang.Object> noDataCheck;

  public final spire.algebra.Order<A> evidence$1;

  public final spire.algebra.Order<B> evidence$2;

  public final scala.Function2<A, geotrellis.util.BTree<scala.Tuple2<A, B>>, scala.util.Either<scala.Option<geotrellis.util.BTree<scala.Tuple2<A, B>>>, scala.Tuple2<A, B>>> branchPred;

  public boolean apply$mcZD$sp(double);
    Code:
       0: aload_0
       1: dload_1
       2: invokestatic  #137                // Method scala/Function1$class.apply$mcZD$sp:(Lscala/Function1;D)Z
       5: ireturn

  public float apply$mcFD$sp(double);
    Code:
       0: aload_0
       1: dload_1
       2: invokestatic  #144                // Method scala/Function1$class.apply$mcFD$sp:(Lscala/Function1;D)F
       5: freturn

  public int apply$mcID$sp(double);
    Code:
       0: aload_0
       1: dload_1
       2: invokestatic  #149                // Method scala/Function1$class.apply$mcID$sp:(Lscala/Function1;D)I
       5: ireturn

  public long apply$mcJD$sp(double);
    Code:
       0: aload_0
       1: dload_1
       2: invokestatic  #154                // Method scala/Function1$class.apply$mcJD$sp:(Lscala/Function1;D)J
       5: lreturn

  public void apply$mcVD$sp(double);
    Code:
       0: aload_0
       1: dload_1
       2: invokestatic  #159                // Method scala/Function1$class.apply$mcVD$sp:(Lscala/Function1;D)V
       5: return

  public boolean apply$mcZF$sp(float);
    Code:
       0: aload_0
       1: fload_1
       2: invokestatic  #164                // Method scala/Function1$class.apply$mcZF$sp:(Lscala/Function1;F)Z
       5: ireturn

  public double apply$mcDF$sp(float);
    Code:
       0: aload_0
       1: fload_1
       2: invokestatic  #170                // Method scala/Function1$class.apply$mcDF$sp:(Lscala/Function1;F)D
       5: dreturn

  public float apply$mcFF$sp(float);
    Code:
       0: aload_0
       1: fload_1
       2: invokestatic  #175                // Method scala/Function1$class.apply$mcFF$sp:(Lscala/Function1;F)F
       5: freturn

  public int apply$mcIF$sp(float);
    Code:
       0: aload_0
       1: fload_1
       2: invokestatic  #180                // Method scala/Function1$class.apply$mcIF$sp:(Lscala/Function1;F)I
       5: ireturn

  public long apply$mcJF$sp(float);
    Code:
       0: aload_0
       1: fload_1
       2: invokestatic  #185                // Method scala/Function1$class.apply$mcJF$sp:(Lscala/Function1;F)J
       5: lreturn

  public void apply$mcVF$sp(float);
    Code:
       0: aload_0
       1: fload_1
       2: invokestatic  #190                // Method scala/Function1$class.apply$mcVF$sp:(Lscala/Function1;F)V
       5: return

  public boolean apply$mcZI$sp(int);
    Code:
       0: aload_0
       1: iload_1
       2: invokestatic  #195                // Method scala/Function1$class.apply$mcZI$sp:(Lscala/Function1;I)Z
       5: ireturn

  public double apply$mcDI$sp(int);
    Code:
       0: aload_0
       1: iload_1
       2: invokestatic  #201                // Method scala/Function1$class.apply$mcDI$sp:(Lscala/Function1;I)D
       5: dreturn

  public float apply$mcFI$sp(int);
    Code:
       0: aload_0
       1: iload_1
       2: invokestatic  #206                // Method scala/Function1$class.apply$mcFI$sp:(Lscala/Function1;I)F
       5: freturn

  public long apply$mcJI$sp(int);
    Code:
       0: aload_0
       1: iload_1
       2: invokestatic  #211                // Method scala/Function1$class.apply$mcJI$sp:(Lscala/Function1;I)J
       5: lreturn

  public void apply$mcVI$sp(int);
    Code:
       0: aload_0
       1: iload_1
       2: invokestatic  #216                // Method scala/Function1$class.apply$mcVI$sp:(Lscala/Function1;I)V
       5: return

  public boolean apply$mcZJ$sp(long);
    Code:
       0: aload_0
       1: lload_1
       2: invokestatic  #221                // Method scala/Function1$class.apply$mcZJ$sp:(Lscala/Function1;J)Z
       5: ireturn

  public double apply$mcDJ$sp(long);
    Code:
       0: aload_0
       1: lload_1
       2: invokestatic  #227                // Method scala/Function1$class.apply$mcDJ$sp:(Lscala/Function1;J)D
       5: dreturn

  public float apply$mcFJ$sp(long);
    Code:
       0: aload_0
       1: lload_1
       2: invokestatic  #232                // Method scala/Function1$class.apply$mcFJ$sp:(Lscala/Function1;J)F
       5: freturn

  public int apply$mcIJ$sp(long);
    Code:
       0: aload_0
       1: lload_1
       2: invokestatic  #237                // Method scala/Function1$class.apply$mcIJ$sp:(Lscala/Function1;J)I
       5: ireturn

  public long apply$mcJJ$sp(long);
    Code:
       0: aload_0
       1: lload_1
       2: invokestatic  #242                // Method scala/Function1$class.apply$mcJJ$sp:(Lscala/Function1;J)J
       5: lreturn

  public void apply$mcVJ$sp(long);
    Code:
       0: aload_0
       1: lload_1
       2: invokestatic  #247                // Method scala/Function1$class.apply$mcVJ$sp:(Lscala/Function1;J)V
       5: return

  public <A> scala.Function1<A, B> compose(scala.Function1<A, A>);
    Code:
       0: aload_0
       1: aload_1
       2: invokestatic  #252                // Method scala/Function1$class.compose:(Lscala/Function1;Lscala/Function1;)Lscala/Function1;
       5: areturn

  public <A> scala.Function1<A, A> andThen(scala.Function1<B, A>);
    Code:
       0: aload_0
       1: aload_1
       2: invokestatic  #256                // Method scala/Function1$class.andThen:(Lscala/Function1;Lscala/Function1;)Lscala/Function1;
       5: areturn

  public java.lang.String toString();
    Code:
       0: aload_0
       1: invokestatic  #261                // Method scala/Function1$class.toString:(Lscala/Function1;)Ljava/lang/String;
       4: areturn

  public geotrellis.util.BTree<scala.Tuple2<A, B>> geotrellis$raster$render$BreakMap$$vmTree();
    Code:
       0: aload_0
       1: getfield      #39                 // Field bitmap$0:Z
       4: ifeq          14
       7: aload_0
       8: getfield      #119                // Field geotrellis$raster$render$BreakMap$$vmTree:Lgeotrellis/util/BTree;
      11: goto          18
      14: aload_0
      15: invokespecial #263                // Method geotrellis$raster$render$BreakMap$$vmTree$lzycompute:()Lgeotrellis/util/BTree;
      18: areturn

  public scala.Function2<A, geotrellis.util.BTree<scala.Tuple2<A, B>>, scala.util.Either<scala.Option<geotrellis.util.BTree<scala.Tuple2<A, B>>>, scala.Tuple2<A, B>>> branchPred();
    Code:
       0: aload_0
       1: getfield      #266                // Field branchPred:Lscala/Function2;
       4: areturn

  public B apply(A);
    Code:
       0: aload_0
       1: getfield      #269                // Field noDataCheck:Lscala/Function1;
       4: aload_1
       5: invokeinterface #271,  2          // InterfaceMethod scala/Function1.apply:(Ljava/lang/Object;)Ljava/lang/Object;
      10: invokestatic  #277                // Method scala/runtime/BoxesRunTime.unboxToBoolean:(Ljava/lang/Object;)Z
      13: ifeq          26
      16: aload_0
      17: getfield      #279                // Field strategy:Lgeotrellis/raster/render/MapStrategy;
      20: invokevirtual #284                // Method geotrellis/raster/render/MapStrategy.noDataValue:()Ljava/lang/Object;
      23: goto          160
      26: aload_0
      27: invokevirtual #286                // Method geotrellis$raster$render$BreakMap$$vmTree:()Lgeotrellis/util/BTree;
      30: aload_1
      31: aload_0
      32: invokevirtual #288                // Method branchPred:()Lscala/Function2;
      35: invokevirtual #292                // Method geotrellis/util/BTree.searchWith:(Ljava/lang/Object;Lscala/Function2;)Lscala/Option;
      38: astore_2
      39: aload_2
      40: instanceof    #294                // class scala/Some
      43: ifeq          73
      46: aload_2
      47: checkcast     #294                // class scala/Some
      50: astore_3
      51: aload_3
      52: invokevirtual #297                // Method scala/Some.x:()Ljava/lang/Object;
      55: ifnull        73
      58: aload_3
      59: invokevirtual #297                // Method scala/Some.x:()Ljava/lang/Object;
      62: checkcast     #49                 // class scala/Tuple2
      65: invokevirtual #300                // Method scala/Tuple2._2:()Ljava/lang/Object;
      68: astore        4
      70: goto          158
      73: getstatic     #305                // Field scala/None$.MODULE$:Lscala/None$;
      76: aload_2
      77: invokevirtual #308                // Method java/lang/Object.equals:(Ljava/lang/Object;)Z
      80: ifeq          149
      83: aload_0
      84: getfield      #279                // Field strategy:Lgeotrellis/raster/render/MapStrategy;
      87: invokevirtual #312                // Method geotrellis/raster/render/MapStrategy.strict:()Z
      90: ifeq          149
      93: getstatic     #317                // Field scala/sys/package$.MODULE$:Lscala/sys/package$;
      96: new           #319                // class scala/StringContext
      99: dup
     100: getstatic     #93                 // Field scala/Predef$.MODULE$:Lscala/Predef$;
     103: iconst_2
     104: anewarray     #321                // class java/lang/String
     107: dup
     108: iconst_0
     109: ldc_w         #323                // String Value
     112: aastore
     113: dup
     114: iconst_1
     115: ldc_w         #325                // String  did not have an associated value.
     118: aastore
     119: checkcast     #95                 // class "[Ljava/lang/Object;"
     122: invokevirtual #329                // Method scala/Predef$.wrapRefArray:([Ljava/lang/Object;)Lscala/collection/mutable/WrappedArray;
     125: invokespecial #333                // Method scala/StringContext."<init>":(Lscala/collection/Seq;)V
     128: getstatic     #93                 // Field scala/Predef$.MODULE$:Lscala/Predef$;
     131: iconst_1
     132: anewarray     #5                  // class java/lang/Object
     135: dup
     136: iconst_0
     137: aload_1
     138: aastore
     139: invokevirtual #337                // Method scala/Predef$.genericWrapArray:(Ljava/lang/Object;)Lscala/collection/mutable/WrappedArray;
     142: invokevirtual #341                // Method scala/StringContext.s:(Lscala/collection/Seq;)Ljava/lang/String;
     145: invokevirtual #345                // Method scala/sys/package$.error:(Ljava/lang/String;)Lscala/runtime/Nothing$;
     148: athrow
     149: aload_0
     150: getfield      #279                // Field strategy:Lgeotrellis/raster/render/MapStrategy;
     153: invokevirtual #348                // Method geotrellis/raster/render/MapStrategy.fallbackValue:()Ljava/lang/Object;
     156: astore        4
     158: aload         4
     160: areturn

  public scala.Function2<java.lang.Object, geotrellis.util.BTree<scala.Tuple2<java.lang.Object, B>>, scala.util.Either<scala.Option<geotrellis.util.BTree<scala.Tuple2<java.lang.Object, B>>>, scala.Tuple2<java.lang.Object, B>>> branchPred$mcD$sp();
    Code:
       0: aload_0
       1: invokevirtual #288                // Method branchPred:()Lscala/Function2;
       4: areturn

  public scala.Function2<java.lang.Object, geotrellis.util.BTree<scala.Tuple2<java.lang.Object, B>>, scala.util.Either<scala.Option<geotrellis.util.BTree<scala.Tuple2<java.lang.Object, B>>>, scala.Tuple2<java.lang.Object, B>>> branchPred$mcI$sp();
    Code:
       0: aload_0
       1: invokevirtual #288                // Method branchPred:()Lscala/Function2;
       4: areturn

  public double apply$mcDD$sp(double);
    Code:
       0: aload_0
       1: dload_1
       2: invokestatic  #358                // Method scala/runtime/BoxesRunTime.boxToDouble:(D)Ljava/lang/Double;
       5: invokevirtual #359                // Method apply:(Ljava/lang/Object;)Ljava/lang/Object;
       8: invokestatic  #363                // Method scala/runtime/BoxesRunTime.unboxToDouble:(Ljava/lang/Object;)D
      11: dreturn

  public int apply$mcDI$sp(double);
    Code:
       0: aload_0
       1: dload_1
       2: invokestatic  #358                // Method scala/runtime/BoxesRunTime.boxToDouble:(D)Ljava/lang/Double;
       5: invokevirtual #359                // Method apply:(Ljava/lang/Object;)Ljava/lang/Object;
       8: invokestatic  #367                // Method scala/runtime/BoxesRunTime.unboxToInt:(Ljava/lang/Object;)I
      11: ireturn

  public double apply$mcID$sp(int);
    Code:
       0: aload_0
       1: iload_1
       2: invokestatic  #371                // Method scala/runtime/BoxesRunTime.boxToInteger:(I)Ljava/lang/Integer;
       5: invokevirtual #359                // Method apply:(Ljava/lang/Object;)Ljava/lang/Object;
       8: invokestatic  #363                // Method scala/runtime/BoxesRunTime.unboxToDouble:(Ljava/lang/Object;)D
      11: dreturn

  public int apply$mcII$sp(int);
    Code:
       0: aload_0
       1: iload_1
       2: invokestatic  #371                // Method scala/runtime/BoxesRunTime.boxToInteger:(I)Ljava/lang/Integer;
       5: invokevirtual #359                // Method apply:(Ljava/lang/Object;)Ljava/lang/Object;
       8: invokestatic  #367                // Method scala/runtime/BoxesRunTime.unboxToInt:(Ljava/lang/Object;)I
      11: ireturn

  public boolean specInstance$();
    Code:
       0: iconst_0
       1: ireturn

  public geotrellis.raster.render.BreakMap(scala.collection.immutable.Map<A, B>, geotrellis.raster.render.MapStrategy<B>, scala.Function1<A, java.lang.Object>, spire.algebra.Order<A>, spire.algebra.Order<B>);
    Code:
       0: aload_0
       1: aload_1
       2: putfield      #41                 // Field breakMap:Lscala/collection/immutable/Map;
       5: aload_0
       6: aload_2
       7: putfield      #279                // Field strategy:Lgeotrellis/raster/render/MapStrategy;
      10: aload_0
      11: aload_3
      12: putfield      #269                // Field noDataCheck:Lscala/Function1;
      15: aload_0
      16: aload         4
      18: putfield      #73                 // Field evidence$1:Lspire/algebra/Order;
      21: aload_0
      22: aload         5
      24: putfield      #75                 // Field evidence$2:Lspire/algebra/Order;
      27: aload_0
      28: invokespecial #378                // Method java/lang/Object."<init>":()V
      31: aload_0
      32: invokestatic  #382                // Method scala/Function1$class.$init$:(Lscala/Function1;)V
      35: aload_0
      36: invokevirtual #384                // Method specInstance$:()Z
      39: ifne          174
      42: aload_0
      43: aload_0
      44: getfield      #279                // Field strategy:Lgeotrellis/raster/render/MapStrategy;
      47: invokevirtual #388                // Method geotrellis/raster/render/MapStrategy.boundary:()Lgeotrellis/raster/render/ClassBoundaryType;
      50: astore        6
      52: getstatic     #393                // Field geotrellis/raster/render/LessThan$.MODULE$:Lgeotrellis/raster/render/LessThan$;
      55: aload         6
      57: invokevirtual #308                // Method java/lang/Object.equals:(Ljava/lang/Object;)Z
      60: ifeq          76
      63: new           #395                // class geotrellis/raster/render/BreakMap$$anonfun$1
      66: dup
      67: aload_0
      68: invokespecial #398                // Method geotrellis/raster/render/BreakMap$$anonfun$1."<init>":(Lgeotrellis/raster/render/BreakMap;)V
      71: astore        7
      73: goto          169
      76: getstatic     #403                // Field geotrellis/raster/render/LessThanOrEqualTo$.MODULE$:Lgeotrellis/raster/render/LessThanOrEqualTo$;
      79: aload         6
      81: invokevirtual #308                // Method java/lang/Object.equals:(Ljava/lang/Object;)Z
      84: ifeq          100
      87: new           #405                // class geotrellis/raster/render/BreakMap$$anonfun$2
      90: dup
      91: aload_0
      92: invokespecial #406                // Method geotrellis/raster/render/BreakMap$$anonfun$2."<init>":(Lgeotrellis/raster/render/BreakMap;)V
      95: astore        7
      97: goto          169
     100: getstatic     #411                // Field geotrellis/raster/render/Exact$.MODULE$:Lgeotrellis/raster/render/Exact$;
     103: aload         6
     105: invokevirtual #308                // Method java/lang/Object.equals:(Ljava/lang/Object;)Z
     108: ifeq          124
     111: new           #413                // class geotrellis/raster/render/BreakMap$$anonfun$3
     114: dup
     115: aload_0
     116: invokespecial #414                // Method geotrellis/raster/render/BreakMap$$anonfun$3."<init>":(Lgeotrellis/raster/render/BreakMap;)V
     119: astore        7
     121: goto          169
     124: getstatic     #419                // Field geotrellis/raster/render/GreaterThanOrEqualTo$.MODULE$:Lgeotrellis/raster/render/GreaterThanOrEqualTo$;
     127: aload         6
     129: invokevirtual #308                // Method java/lang/Object.equals:(Ljava/lang/Object;)Z
     132: ifeq          148
     135: new           #421                // class geotrellis/raster/render/BreakMap$$anonfun$4
     138: dup
     139: aload_0
     140: invokespecial #422                // Method geotrellis/raster/render/BreakMap$$anonfun$4."<init>":(Lgeotrellis/raster/render/BreakMap;)V
     143: astore        7
     145: goto          169
     148: getstatic     #427                // Field geotrellis/raster/render/GreaterThan$.MODULE$:Lgeotrellis/raster/render/GreaterThan$;
     151: aload         6
     153: invokevirtual #308                // Method java/lang/Object.equals:(Ljava/lang/Object;)Z
     156: ifeq          175
     159: new           #429                // class geotrellis/raster/render/BreakMap$$anonfun$5
     162: dup
     163: aload_0
     164: invokespecial #430                // Method geotrellis/raster/render/BreakMap$$anonfun$5."<init>":(Lgeotrellis/raster/render/BreakMap;)V
     167: astore        7
     169: aload         7
     171: putfield      #266                // Field branchPred:Lscala/Function2;
     174: return
     175: new           #432                // class scala/MatchError
     178: dup
     179: aload         6
     181: invokespecial #435                // Method scala/MatchError."<init>":(Ljava/lang/Object;)V
     184: athrow
}
lossyrob commented 7 years ago

Here are some benchmarks that can help with optimization: https://github.com/geotrellis/geotrellis-benchmark/blob/43066060f18f41c6fdc902b54f25c149c9bad691/geotrellis/src/test/scala/geotrellis/raster/render/Render.scala#L49