Changeset 18431 in josm

Timestamp:

2022-04-19T19:12:51+02:00 (2 years ago)

Author:

taylor.smock

Message:

VectorTile/MapBox/Feature: Significantly reduce allocations

The area tested can be downloaded with
--download=39.0637818,-108.5670233,39.0660809,-108.5620022.
VectorTile downloads was tested via the Mapillary plugin.

Differences (bytes, from IntelliJ Profiler in IDEA 2022.1):

Class	Method	Original	New	Difference
CommandInteger	init	81,156,792	5,045,360	-76,111,432 (-93.7%)
Feature	parseTagValue	354,995,472	143,200,680	-211,794,792 (-59.6%)
ProtobufPacked	init	458,471,192	189,104,744	-269,366,448 (-58.7%)
ProtobufRecord	init	492,731,416	142,510,112	-350,221,304 (-71.0%)
Feature	init	1,437,014,520	550,452,376	-886,562,144 (-61.7%)

Most of the allocations came from the following sources:

• Array copies
  • List#add (mostly fixed through the use of a ByteArrayOutputStream, as the lists were List<Byte>)
  • Enum#values (this is where the changes to Command and WireType come from)
• Streams (fixed by using a traditional for loop)
• NumberFormat#getNumberInstance (fixed by creating a static instance)

Location:

trunk/src/org/openstreetmap/josm/data

Files:

• imagery/vectortile/mapbox/Command.java (modified) (2 diffs)
• imagery/vectortile/mapbox/CommandInteger.java (modified) (2 diffs)
• imagery/vectortile/mapbox/Feature.java (modified) (2 diffs)
• protobuf/ProtobufPacked.java (modified) (3 diffs)
• protobuf/ProtobufParser.java (modified) (3 diffs)
• protobuf/ProtobufRecord.java (modified) (2 diffs)
• protobuf/WireType.java (modified) (2 diffs)

trunk/src/org/openstreetmap/josm/data/imagery/vectortile/mapbox/Command.java

@@ -23 +23 @@
     ClosePath((byte) 7, (byte) 0);
 
+    private static final Command[] CACHED_VALUES = Command.values();
     private final byte id;
     private final byte parameters;
@@ -46 +47 @@
         return this.parameters;
     }
+
+    /**
+     * Get a pre-calculated array of all {@link Command} values.
+     * @return An array of values, meant as a drop-in replacement for {@link Command#values()}
+     * <i>where the array is not modified</i>! This can significantly reduce allocations, as there is no defensive
+     * array copy.
+     */
+    static Command[] getAllValues() {
+        return CACHED_VALUES;
+    }
 }

trunk/src/org/openstreetmap/josm/data/imagery/vectortile/mapbox/CommandInteger.java

@@ -3 +3 @@
 
 import java.util.Arrays;
-import java.util.stream.Stream;
 
 /**
@@ -22 +21 @@
         // Technically, the int is unsigned, but it is easier to work with the long
         final long unsigned = Integer.toUnsignedLong(command);
-        this.type = Stream.of(Command.values()).filter(e -> e.getId() == (unsigned & 0x7)).findAny()
-                .orElseThrow(InvalidMapboxVectorTileException::new);
+        // By avoiding using a stream for getting the Command type, we go from 72 MB to 13 MB.
+        // By using a cached value for Command.values(), we further reduce the allocations to 5 MB (new short[] call
+        // at end of initializer)
+        Command rType = null;
+        for (Command tType : Command.getAllValues()) {
+            if (tType.getId() == (unsigned & 0x7)) {
+                rType = tType;
+                break;
+            }
+        }
+        this.type = rType;
+        if (this.type == null) {
+            throw new InvalidMapboxVectorTileException();
+        }
+
         // This is safe, since we are shifting right 3 when we converted an int to a long (for unsigned).
         // So we <i>cannot</i> lose anything.

trunk/src/org/openstreetmap/josm/data/imagery/vectortile/mapbox/Feature.java

@@ -25 +25 @@
     private static final byte GEOMETRY_TYPE_FIELD = 3;
     private static final byte GEOMETRY_FIELD = 4;
+    /**
+     * The number format instance to use (using a static instance gets rid of quite o few allocations)
+     * Doing this reduced the allocations of {@link #parseTagValue(String, Layer, Number)} from 22.79% of parent to
+     * 12.2% of parent.
+     */
+    private static final NumberFormat NUMBER_FORMAT = NumberFormat.getNumberInstance(Locale.ROOT);
     /**
      * The geometry of the feature. Required.
@@ -112 +118 @@
             if (value instanceof Double || value instanceof Float) {
                 // reset grouping if the instance is a singleton
-                final NumberFormat numberFormat = NumberFormat.getNumberInstance(Locale.ROOT);
-                final boolean grouping = numberFormat.isGroupingUsed();
+
+                final boolean grouping = NUMBER_FORMAT.isGroupingUsed();
                 try {
-                    numberFormat.setGroupingUsed(false);
-                    this.tags.put(key, numberFormat.format(value));
+                    NUMBER_FORMAT.setGroupingUsed(false);
+                    this.tags.put(key, NUMBER_FORMAT.format(value));
                 } finally {
-                    numberFormat.setGroupingUsed(grouping);
+                    NUMBER_FORMAT.setGroupingUsed(grouping);
                 }
             } else {

trunk/src/org/openstreetmap/josm/data/protobuf/ProtobufPacked.java

@@ -2 +2 @@
 package org.openstreetmap.josm.data.protobuf;
 
+import java.io.ByteArrayOutputStream;
 import java.util.ArrayList;
 import java.util.List;
@@ -25 +26 @@
         this.bytes = bytes;
         List<Number> numbersT = new ArrayList<>();
+        // By reusing a ByteArrayOutputStream, we can reduce allocations in nextVarInt from 230 MB to 74 MB.
+        ByteArrayOutputStream byteArrayOutputStream = new ByteArrayOutputStream(4);
         while (this.location < bytes.length) {
-            numbersT.add(ProtobufParser.convertByteArray(this.nextVarInt(), ProtobufParser.VAR_INT_BYTE_SIZE));
+            numbersT.add(ProtobufParser.convertByteArray(this.nextVarInt(byteArrayOutputStream), ProtobufParser.VAR_INT_BYTE_SIZE));
+            byteArrayOutputStream.reset();
         }
 
@@ -44 +48 @@
     }
 
-    private byte[] nextVarInt() {
-        List<Byte> byteList = new ArrayList<>();
+    private byte[] nextVarInt(final ByteArrayOutputStream byteArrayOutputStream) {
+        // In a real world test, the largest List<Byte> seen had 3 elements. Use 4 to avoid most new array allocations.
+        // Memory allocations went from 368 MB to 280 MB by using an initial array allocation. When using a
+        // ByteArrayOutputStream, it went down to 230 MB.
         while ((this.bytes[this.location] & ProtobufParser.MOST_SIGNIFICANT_BYTE)
           == ProtobufParser.MOST_SIGNIFICANT_BYTE) {
             // Get rid of the leading bit (shift left 1, then shift right 1 unsigned)
-            byteList.add((byte) (this.bytes[this.location++] ^ ProtobufParser.MOST_SIGNIFICANT_BYTE));
+            byteArrayOutputStream.write(this.bytes[this.location++] ^ ProtobufParser.MOST_SIGNIFICANT_BYTE);
         }
         // The last byte doesn't drop the most significant bit
-        byteList.add(this.bytes[this.location++]);
-        byte[] byteArray = new byte[byteList.size()];
-        for (int i = 0; i < byteList.size(); i++) {
-            byteArray[i] = byteList.get(i);
-        }
-
-        return byteArray;
+        byteArrayOutputStream.write(this.bytes[this.location++]);
+        return byteArrayOutputStream.toByteArray();
     }
 }

trunk/src/org/openstreetmap/josm/data/protobuf/ProtobufParser.java

@@ -4 +4 @@
 import java.io.BufferedInputStream;
 import java.io.ByteArrayInputStream;
+import java.io.ByteArrayOutputStream;
 import java.io.IOException;
 import java.io.InputStream;
 import java.util.ArrayList;
 import java.util.Collection;
-import java.util.List;
 
 import org.openstreetmap.josm.tools.Logging;
@@ -156 +156 @@
         this.inputStream.mark(16);
         try {
-            return WireType.values()[this.inputStream.read() << 3];
+            return WireType.getAllValues()[this.inputStream.read() << 3];
         } finally {
             this.inputStream.reset();
@@ -212 +212 @@
      */
     public byte[] nextVarInt() throws IOException {
-        List<Byte> byteList = new ArrayList<>();
+        // Using this reduces the allocations from 150 MB to 95 MB.
+        final ByteArrayOutputStream byteArrayOutputStream = new ByteArrayOutputStream(4);
         int currentByte = this.nextByte();
         while ((byte) (currentByte & MOST_SIGNIFICANT_BYTE) == MOST_SIGNIFICANT_BYTE && currentByte > 0) {
             // Get rid of the leading bit (shift left 1, then shift right 1 unsigned)
-            byteList.add((byte) (currentByte ^ MOST_SIGNIFICANT_BYTE));
+            byteArrayOutputStream.write((currentByte ^ MOST_SIGNIFICANT_BYTE));
             currentByte = this.nextByte();
         }
         // The last byte doesn't drop the most significant bit
-        byteList.add((byte) currentByte);
-        byte[] byteArray = new byte[byteList.size()];
-        for (int i = 0; i < byteList.size(); i++) {
-            byteArray[i] = byteList.get(i);
-        }
-
-        return byteArray;
+        byteArrayOutputStream.write(currentByte);
+        return byteArrayOutputStream.toByteArray();
     }
 

trunk/src/org/openstreetmap/josm/data/protobuf/ProtobufRecord.java

@@ -4 +4 @@
 import java.io.IOException;
 import java.nio.charset.StandardCharsets;
-import java.util.stream.Stream;
 
 import org.openstreetmap.josm.tools.Utils;
@@ -32 +31 @@
         // 7 is 111 (so last three bits)
         byte wireType = (byte) (number.longValue() & 7);
-        this.type = Stream.of(WireType.values()).filter(wType -> wType.getTypeRepresentation() == wireType).findFirst()
-          .orElse(WireType.UNKNOWN);
+        // By not using a stream, we reduce the number of allocations (for getting the WireType) from 257 MB to 40 MB.
+        // (The remaining 40 MB is from WireType#values). By using the cached getAllValues(), we drop the 40 MB.
+        WireType tType = null;
+        for (WireType wType : WireType.getAllValues()) {
+            if (wType.getTypeRepresentation() == wireType) {
+                tType = wType;
+                break;
+            }
+        }
+        this.type = tType;
 
         if (this.type == WireType.VARINT) {

trunk/src/org/openstreetmap/josm/data/protobuf/WireType.java

@@ -45 +45 @@
     UNKNOWN(Byte.MAX_VALUE);
 
+    private static final WireType[] CACHED_VALUES = values();
+
     private final byte type;
 
@@ -59 +61 @@
         return this.type;
     }
+
+    /**
+     * Get a pre-calculated array of all {@link WireType} values.
+     * @return An array of values, meant as a drop-in replacement for {@link WireType#values()}
+     * <i>where the array is not modified</i>! This can significantly reduce allocations, as there is no defensive
+     * array copy.
+     */
+    static WireType[] getAllValues() {
+        return CACHED_VALUES;
+    }
 }