Repository: graphhopper/graphhopper
Pull request #1171 (2017-10-03 04:48:29)

Improve PathSimplification Performance and Memory Overhead
As reported in #1162, there are issues with the performance and memory usage.

One issue of memory usage was found in the PathList#copy method. 

I profiled the current master and found that even with 3051eca5683ed9bf1446419fd9e0c4052c33a5a5 a lot of memory is used due to PathList#copy and PathList#add. This PR tries to solve this to solve this issue by creating [shallow copies](https://en.wikipedia.org/wiki/Object_copying#Shallow_copy) of the PathList instead of deep copies. I cannot find the same memory consumption with this PR.

The issue with the shallow copies is that we might see incorrect results if we change the original PointList. For example we have a PointList with 3 points, A,B,C and we create a Shallow copy of this PointList, referencing point A, B. If we now change the underlying PointList, for example reverse it, then the shallow copy references to the points C,B instead of A,B.

We cannot simply lock the PointList, once we create a shallow copy, since we create shallow copies during the PathSimplification after each simplification (see [PathSimplification#reduceLengh](https://github.com/graphhopper/graphhopper/blob/20d6e67bf114543ea6feaabf5510510a14eecc8d/core/src/main/java/com/graphhopper/util/PathSimplification.java#L160), but change the original PointList with each simplification. It might be possible to lock the original PointList once we merge #1138. A partial lock might work, but I am not sure if this becomes too much of an overhead?

I benchmarked the performance of this PR with Apache Bench and the following command: `ab -n 1000 -c 20 "http://localhost:8989/route?point=49.214009%2C8.723145&point=49.203243%2C10.151367&point=47.755945%2C9.695435&point=48.991032%2C9.613037&point=48.026672%2C7.973328&type=json&locale=en-AU&vehicle=car&weighting=fastest&elevation=false&key="`

So it sampled 1000 requests and 20 concurrent requests. The used route is about 750km long.

Master:
```
Concurrency Level:      20
Time taken for tests:   14.157 seconds
Complete requests:      1000
Failed requests:        6
   (Connect: 0, Receive: 0, Length: 6, Exceptions: 0)
Total transferred:      55914988 bytes
HTML transferred:       55505994 bytes
Requests per second:    70.64 [#/sec] (mean)
Time per request:       283.139 [ms] (mean)
Time per request:       14.157 [ms] (mean, across all concurrent requests)
Transfer rate:          3857.08 [Kbytes/sec] received
```

This PR:
```
Concurrency Level:      20
Time taken for tests:   13.346 seconds
Complete requests:      1000
Failed requests:        12
   (Connect: 0, Receive: 0, Length: 12, Exceptions: 0)
Total transferred:      55914976 bytes
HTML transferred:       55505988 bytes
Requests per second:    74.93 [#/sec] (mean)
Time per request:       266.920 [ms] (mean)
Time per request:       13.346 [ms] (mean, across all concurrent requests)
Transfer rate:          4091.46 [Kbytes/sec] received
```

For some reason `./graphhopper.sh measurement` does not produce reproducible results for me. I have not found the reason for this but it might differ +-5% per measurement. So sometimes it seemed this PR would improve the performance, sometimes it seems it does not. With Apache Bench it seems to improve the performance.

karussell: > The issue with the shallow copies is that we might see incorrect results if we change the original PointList. 

This is ugly. But unavoidable IMO. To make it a bit more safe it might be interesting to have an explicit makeReadOnly method after the simplification? So while simplification there is some risk for our internal development but afterwards everything is fine for the end user? To make this more obvious we could rename the method to shallowUnsafeCopy?
karussell: I can confirm that this improves the introduced instructions overhead reported in #1162.

But I can use Measurement. Also I found that the slow down was introduced in commit 

11efb7ae6289a66b7a34644b2b40e12bb49de40f Add Average Speed as PathDetails to Response (#1091)

~3.6ms vs. 4.1ms

Now with this change it is back to 3.7ms but of course only if I delete the newly introduced lines in Measurement:

```java
if (withInstructions)
    req.setPathDetails(Arrays.asList(Parameters.DETAILS.AVERAGE_SPEED));
```

boldtrn: > if (withInstructions)
    req.setPathDetails(Arrays.asList(Parameters.DETAILS.AVERAGE_SPEED));

Ah, this explains a lot :). I forgot that we add PathDetails in der Measurement and didn't change that line.

> To make it a bit more safe it might be interesting to have an explicit makeReadOnly method after the simplification?

Yes I think a write lock would be a good addition here. Will add this.

> To make this more obvious we could rename the method to shallowUnsafeCopy?

Yes, makes sense.
boldtrn: Ok, at first I implemented the `equals` function, that it would also check if the mutability of both PointLists is equal. This made some tests fail, as assertEquals failed. For now I reverted the change but I am not sure, if equals should check for the mutability of the object as well?
karussell: Thanks. One final safety improvement we should discuss: should we make both PointList classes final? Currently one could tweak the PointList endlessly which could introduce methods with which the shallow copy has problems etc
boldtrn: > One final safety improvement we should discuss: should we make both PointList classes final? 

Would this work? The ShallowCopy extends the PointList. I think this would be forbidden if we set the PointList final?
karussell: Ah, ok. That is still a bit ugly. Hmmh.
boldtrn: > Ah, ok. That is still a bit ugly. Hmmh.

I added a hint in the class comment of the PointList. I think if someone tries to extend this class he/she would at least read the class comment. Probably there is not much we can do, if someone incorrectly extends any class of GH, it might break?
karussell: > Probably there is not much we can do, if someone incorrectly extends any class of GH, it might break?

If some classes are not explicitly intended for this we should make them final (I know this is not the case elsewhere in the code base but we should improve step by step :)).

There is the following trick that we could try: create a _PointList class that is package protected and that does what the current PointList does, then create the two **final** classes: `PointList extends _PointList` and `ShallowCopyPointList extends _PointList`. Would this work?
boldtrn: > If some classes are not explicitly intended for this we should make them final (I know this is not the case elsewhere in the code base but we should improve step by step :)).

But wouldn't it be better to offer users the flexibility to extend and change GraphHopper very flexible? Or what is the reason to forbid this explicitly?

> There is the following trick that we could try: create a _PointList class that is package protected and that does what the current PointList does, then create the two final classes: PointList extends _PointList and ShallowCopyPointList extends _PointList. Would this work?

It could work like this, yes. But this makes usages of the PointList class outside of the package ugly. If we would keep the code as it is, we could not simply use the ShallowCopy instead of the PointList and we cannot set the datatype to _PointList as this class is package protected. So we would have to set the PointList of the Instructions to ShallowImmutablePointList and change all interfaces they use together. So maybe we can trick Java to accept this by casting the ShallowCopy to a PointList. Personally, I would prefer to avoid this.
karussell: > But this makes usages of the PointList class outside of the package ...

Ehem, yes ;) ... so this won't work. The only solution left would be to break the API and introduce a PointList interface, but this would be too ugly. Let us keep it this way and make at least the shallow class final.

>  But wouldn't it be better to offer users the flexibility to extend and change GraphHopper very flexible? Or what is the reason to forbid this explicitly?

We can open up our API if we know there really is a good use case. Otherwise if we allow broad usage we later cannot easily migrate to other stuff or implementation OR we have to break this public API.
boldtrn: > Otherwise if we allow broad usage we later cannot easily migrate to other stuff or implementation OR we have to break this public API.

Ah, now I understand :). Ok, makes sense.

> Let us keep it this way and make at least the shallow class final.

Just pushed the change :).

Patch:
diff --git a/core/src/main/java/com/graphhopper/util/PathSimplification.java b/core/src/main/java/com/graphhopper/util/PathSimplification.java
index 6e8b11210..40aebf84b 100644
--- a/core/src/main/java/com/graphhopper/util/PathSimplification.java
+++ b/core/src/main/java/com/graphhopper/util/PathSimplification.java
@@ -139,6 +139,8 @@ public class PathSimplification {
                 prevPD = list.get(i);
             }
         }
+        // Make sure that the instruction references are not broken
+        pointList.makeImmutable();
         return pointList;
     }
 
@@ -159,7 +161,7 @@ public class PathSimplification {
 
     private void reduceLength(Object o, int index, int startIndex, int newEndIndex) {
         if (o instanceof InstructionList) {
-            ((InstructionList) o).get(index).setPoints(this.pointList.copy(startIndex, newEndIndex));
+            ((InstructionList) o).get(index).setPoints(this.pointList.shallowCopy(startIndex, newEndIndex, false));
         } else if (o instanceof List) {
             PathDetail pd = ((List<PathDetail>) o).get(index);
             pd.setFirst(startIndex);
diff --git a/core/src/main/java/com/graphhopper/util/PointList.java b/core/src/main/java/com/graphhopper/util/PointList.java
index 1f6aeeef7..e00b77fb9 100644
--- a/core/src/main/java/com/graphhopper/util/PointList.java
+++ b/core/src/main/java/com/graphhopper/util/PointList.java
@@ -25,7 +25,9 @@ import com.vividsolutions.jts.geom.LineString;
 import java.util.*;
 
 /**
- * Slim list to store several points (without the need for a point object).
+ * Slim list to store several points (without the need for a point object). Be aware that the PointList is closely
+ * coupled with the {@link ShallowImmutablePointList} if you change it or extend it, you should make sure that your
+ * changes play well with the ShallowImmutablePointList to avoid unexpected issues.
  * <p>
  *
  * @author Peter Karich
@@ -138,12 +140,13 @@ public class PointList implements Iterable<GHPoint3D>, PointAccess {
         }
     };
     private final static DistanceCalc3D distCalc3D = Helper.DIST_3D;
-    private static String ERR_MSG = "Tried to access PointList with too big index!";
+    final static String ERR_MSG = "Tried to access PointList with too big index!";
     protected int size = 0;
     protected boolean is3D;
     private double[] latitudes;
     private double[] longitudes;
     private double[] elevations;
+    private boolean isImmutable = false;
 
     public PointList() {
         this(10, false);
@@ -185,6 +188,7 @@ public class PointList implements Iterable<GHPoint3D>, PointAccess {
     }
 
     public void set(int index, double lat, double lon, double ele) {
+        ensureMutability();
         if (index >= size)
             throw new ArrayIndexOutOfBoundsException("index has to be smaller than size " + size);
 
@@ -216,6 +220,7 @@ public class PointList implements Iterable<GHPoint3D>, PointAccess {
     }
 
     public void add(double lat, double lon, double ele) {
+        ensureMutability();
         int newSize = size + 1;
         incCap(newSize);
         latitudes[size] = lat;
@@ -242,6 +247,7 @@ public class PointList implements Iterable<GHPoint3D>, PointAccess {
     }
 
     public void add(PointList points) {
+        ensureMutability();
         int newSize = size + points.getSize();
         incCap(newSize);
         for (int i = 0; i < points.getSize(); i++) {
@@ -259,11 +265,11 @@ public class PointList implements Iterable<GHPoint3D>, PointAccess {
     }
 
     public int getSize() {
-        return size;
+        return size();
     }
 
     public boolean isEmpty() {
-        return size == 0;
+        return size() == 0;
     }
 
     @Override
@@ -308,6 +314,7 @@ public class PointList implements Iterable<GHPoint3D>, PointAccess {
     }
 
     public void reverse() {
+        ensureMutability();
         // in-place reverse
         int max = size / 2;
         for (int i = 0; i < max; i++) {
@@ -330,10 +337,12 @@ public class PointList implements Iterable<GHPoint3D>, PointAccess {
     }
 
     public void clear() {
+        ensureMutability();
         size = 0;
     }
 
     public void trimToSize(int newSize) {
+        ensureMutability();
         if (newSize > size)
             throw new IllegalArgumentException("new size needs be smaller than old size");
 
@@ -343,17 +352,17 @@ public class PointList implements Iterable<GHPoint3D>, PointAccess {
     @Override
     public String toString() {
         StringBuilder sb = new StringBuilder();
-        for (int i = 0; i < size; i++) {
+        for (int i = 0; i < getSize(); i++) {
             if (i > 0)
                 sb.append(", ");
 
             sb.append('(');
-            sb.append(latitudes[i]);
+            sb.append(getLatitude(i));
             sb.append(',');
-            sb.append(longitudes[i]);
-            if (is3D) {
+            sb.append(getLongitude(i));
+            if (this.is3D()) {
                 sb.append(',');
-                sb.append(elevations[i]);
+                sb.append(getElevation(i));
             }
             sb.append(')');
         }
@@ -369,8 +378,8 @@ public class PointList implements Iterable<GHPoint3D>, PointAccess {
 
     public List<Double[]> toGeoJson(boolean includeElevation) {
 
-        ArrayList<Double[]> points = new ArrayList<Double[]>(size);
-        for (int i = 0; i < size; i++) {
+        ArrayList<Double[]> points = new ArrayList<Double[]>(getSize());
+        for (int i = 0; i < getSize(); i++) {
             if (includeElevation)
                 points.add(new Double[]{
                         Helper.round6(getLongitude(i)), Helper.round6(getLatitude(i)),
@@ -396,28 +405,32 @@ public class PointList implements Iterable<GHPoint3D>, PointAccess {
         if (this.getSize() != other.getSize() || this.is3D() != other.is3D())
             return false;
 
-        for (int i = 0; i < size; i++) {
-            if (!NumHelper.equalsEps(latitudes[i], other.latitudes[i]))
+        for (int i = 0; i < size(); i++) {
+            if (!NumHelper.equalsEps(getLatitude(i), other.getLatitude(i)))
                 return false;
 
-            if (!NumHelper.equalsEps(longitudes[i], other.longitudes[i]))
+            if (!NumHelper.equalsEps(getLongitude(i), other.getLongitude(i)))
                 return false;
 
-            if (is3D && !NumHelper.equalsEps(elevations[i], other.elevations[i]))
+            if (this.is3D() && !NumHelper.equalsEps(getElevation(i), other.getElevation(i)))
                 return false;
         }
         return true;
     }
 
+    /**
+     * Clones this PointList. If this PointList was immutable, the cloned will be mutable. If this PointList was a
+     * ShallowImmutablePointList, the cloned PointList will be a regular PointList.
+     */
     public PointList clone(boolean reverse) {
-        PointList clonePL = new PointList(size, is3D);
-        if (is3D)
-            for (int i = 0; i < size; i++) {
-                clonePL.add(latitudes[i], longitudes[i], elevations[i]);
+        PointList clonePL = new PointList(getSize(), is3D());
+        if (is3D())
+            for (int i = 0; i < getSize(); i++) {
+                clonePL.add(getLatitude(i), getLongitude(i), getElevation(i));
             }
         else
-            for (int i = 0; i < size; i++) {
-                clonePL.add(latitudes[i], longitudes[i]);
+            for (int i = 0; i < getSize(); i++) {
+                clonePL.add(getLatitude(i), getLongitude(i));
             }
         if (reverse)
             clonePL.reverse();
@@ -428,35 +441,48 @@ public class PointList implements Iterable<GHPoint3D>, PointAccess {
      * This method does a deep copy of this object for the specified range.
      *
      * @param from the copying of the old PointList starts at this index
-     * @param end the copying of the old PointList ends at the index before (i.e. end is exclusive)
+     * @param end  the copying of the old PointList ends at the index before (i.e. end is exclusive)
      */
     public PointList copy(int from, int end) {
         if (from > end)
-            throw new IllegalArgumentException("from must be smaller or equals to end");
-        if (from < 0 || end > size)
-            throw new IllegalArgumentException("Illegal interval: " + from + ", " + end + ", size:" + size);
+            throw new IllegalArgumentException("from must be smaller or equal to end");
+        if (from < 0 || end > getSize())
+            throw new IllegalArgumentException("Illegal interval: " + from + ", " + end + ", size:" + getSize());
 
-        PointList copyPL = new PointList(end - from, is3D);
-        if (is3D)
+        PointList copyPL = new PointList(end - from, is3D());
+        if (is3D())
             for (int i = from; i < end; i++) {
-                copyPL.add(latitudes[i], longitudes[i], elevations[i]);
+                copyPL.add(getLatitude(i), getLongitude(i), getElevation(i));
             }
         else
             for (int i = from; i < end; i++) {
-                copyPL.add(latitudes[i], longitudes[i], Double.NaN);
+                copyPL.add(getLatitude(i), getLongitude(i), Double.NaN);
             }
 
         return copyPL;
     }
 
+    /**
+     * Create a shallow copy of this Pointlist from from to end, excluding end.
+     * <p>
+     * The <code>ensureConsistency</code> parameter makes this PointList immutable, so the shallow copy will stay
+     * consistent with this object. If you don't ensure the consistency it might happen that due to changes of this
+     * object, the shallow copy might contain incorrect or corrupt data.
+     */
+    public PointList shallowCopy(final int from, final int end, boolean ensureConsistency) {
+        if (ensureConsistency)
+            this.makeImmutable();
+        return new ShallowImmutablePointList(from, end, this);
+    }
+
     @Override
     public int hashCode() {
         int hash = 5;
-        for (int i = 0; i < latitudes.length; i++) {
-            hash = 73 * hash + (int) Math.round(latitudes[i] * 1000000);
-            hash = 73 * hash + (int) Math.round(longitudes[i] * 1000000);
+        for (int i = 0; i < getSize(); i++) {
+            hash = 73 * hash + (int) Math.round(getLatitude(i) * 1000000);
+            hash = 73 * hash + (int) Math.round(getLongitude(i) * 1000000);
         }
-        hash = 73 * hash + this.size;
+        hash = 73 * hash + this.getSize();
         return hash;
     }
 
@@ -465,18 +491,18 @@ public class PointList implements Iterable<GHPoint3D>, PointAccess {
         double prevLon = Double.NaN;
         double prevEle = Double.NaN;
         double dist = 0;
-        for (int i = 0; i < size; i++) {
+        for (int i = 0; i < size(); i++) {
             if (i > 0) {
-                if (is3D)
-                    dist += distCalc3D.calcDist(prevLat, prevLon, prevEle, latitudes[i], longitudes[i], elevations[i]);
+                if (is3D())
+                    dist += distCalc3D.calcDist(prevLat, prevLon, prevEle, getLat(i), getLon(i), getEle(i));
                 else
-                    dist += calc.calcDist(prevLat, prevLon, latitudes[i], longitudes[i]);
+                    dist += calc.calcDist(prevLat, prevLon, getLat(i), getLon(i));
             }
 
-            prevLat = latitudes[i];
-            prevLon = longitudes[i];
-            if (is3D)
-                prevEle = elevations[i];
+            prevLat = getLat(i);
+            prevLon = getLon(i);
+            if (is3D())
+                prevEle = getEle(i);
         }
         return dist;
     }
@@ -538,4 +564,22 @@ public class PointList implements Iterable<GHPoint3D>, PointAccess {
         }
         return pointList;
     }
+
+    public boolean isImmutable() {
+        return this.isImmutable;
+    }
+
+    /**
+     * Once immutable, there is no way to make this object mutable again. This is done to ensure the consistency of
+     * shallow copies. If you need to modify this object again, you have to create a deep copy of it.
+     */
+    public void makeImmutable() {
+        this.isImmutable = true;
+    }
+
+    private void ensureMutability() {
+        if (this.isImmutable()) {
+            throw new IllegalStateException("You cannot change an immutable PointList");
+        }
+    }
 }
diff --git a/core/src/main/java/com/graphhopper/util/ShallowImmutablePointList.java b/core/src/main/java/com/graphhopper/util/ShallowImmutablePointList.java
new file mode 100644
index 000000000..4f5b2f02c
--- /dev/null
+++ b/core/src/main/java/com/graphhopper/util/ShallowImmutablePointList.java
@@ -0,0 +1,161 @@
+/*
+ *  Licensed to GraphHopper GmbH under one or more contributor
+ *  license agreements. See the NOTICE file distributed with this work for 
+ *  additional information regarding copyright ownership.
+ * 
+ *  GraphHopper GmbH licenses this file to you under the Apache License, 
+ *  Version 2.0 (the "License"); you may not use this file except in 
+ *  compliance with the License. You may obtain a copy of the License at
+ * 
+ *       http://www.apache.org/licenses/LICENSE-2.0
+ * 
+ *  Unless required by applicable law or agreed to in writing, software
+ *  distributed under the License is distributed on an "AS IS" BASIS,
+ *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ *  See the License for the specific language governing permissions and
+ *  limitations under the License.
+ */
+package com.graphhopper.util;
+
+import java.util.List;
+
+/**
+ * This is a shallow copy of a PointList. This class can be used to create a memory efficient copy of a PointList.
+ * You have to be aware, that if the wrapped PointList changes, the shallow copy will change as well. This can lead to
+ * unexpected results. We recommend making the wrapped PointList immutable {@link PointList#makeImmutable()}.
+ *
+ * @author Robin Boldt
+ */
+public final class ShallowImmutablePointList extends PointList {
+
+    private final static String IMMUTABLE_ERR = "This class is immutable, you are not allowed to change it";
+
+    private final int fromOffset;
+    private final int toOffset;
+    private final PointList wrappedPointList;
+
+    public ShallowImmutablePointList(int fromOffset, int toOffset, PointList wrappedPointList) {
+        if (fromOffset > toOffset)
+            throw new IllegalArgumentException("from must be smaller or equal to end");
+        if (fromOffset < 0 || toOffset > wrappedPointList.getSize())
+            throw new IllegalArgumentException("Illegal interval: " + fromOffset + ", " + toOffset);
+        this.fromOffset = fromOffset;
+        this.toOffset = toOffset;
+        this.wrappedPointList = wrappedPointList;
+    }
+
+    @Override
+    public int size() {
+        return toOffset - fromOffset;
+    }
+
+    @Override
+    public int getSize() {
+        return size();
+    }
+
+    @Override
+    public boolean isEmpty() {
+        return size() == 0;
+    }
+
+    @Override
+    public double getLatitude(int index) {
+        if (index > getSize())
+            throw new ArrayIndexOutOfBoundsException(ERR_MSG + " index:" + index + ", size:" + getSize());
+        return wrappedPointList.getLatitude(fromOffset + index);
+    }
+
+    @Override
+    public double getLongitude(int index) {
+        if (index > getSize())
+            throw new ArrayIndexOutOfBoundsException(ERR_MSG + " index:" + index + ", size:" + getSize());
+        return wrappedPointList.getLongitude(fromOffset + index);
+    }
+
+    @Override
+    public double getElevation(int index) {
+        if (index > getSize())
+            throw new ArrayIndexOutOfBoundsException(ERR_MSG + " index:" + index + ", size:" + getSize());
+        return wrappedPointList.getElevation(fromOffset + index);
+    }
+
+    public void makeImmutable() {
+        this.wrappedPointList.makeImmutable();
+    }
+
+    @Override
+    public boolean isImmutable() {
+        return this.wrappedPointList.isImmutable();
+    }
+
+    /*
+    Wrapping Part
+     */
+
+    @Override
+    public boolean is3D() {
+        return wrappedPointList.is3D();
+    }
+
+    @Override
+    public int getDimension() {
+        return wrappedPointList.getDimension();
+    }
+
+
+    /*
+    Immutable forbidden part
+     */
+
+    @Override
+    public void ensureNode(int nodeId) {
+        throw new UnsupportedOperationException(IMMUTABLE_ERR);
+    }
+
+    @Override
+    public void setNode(int nodeId, double lat, double lon) {
+        throw new UnsupportedOperationException(IMMUTABLE_ERR);
+    }
+
+    @Override
+    public void setNode(int nodeId, double lat, double lon, double ele) {
+        throw new UnsupportedOperationException(IMMUTABLE_ERR);
+    }
+
+    @Override
+    public void set(int index, double lat, double lon, double ele) {
+        throw new UnsupportedOperationException(IMMUTABLE_ERR);
+    }
+
+    @Override
+    public void add(double lat, double lon, double ele) {
+        throw new UnsupportedOperationException(IMMUTABLE_ERR);
+    }
+
+    @Override
+    public void add(PointList points) {
+        throw new UnsupportedOperationException(IMMUTABLE_ERR);
+    }
+
+    @Override
+    public void reverse() {
+        throw new UnsupportedOperationException(IMMUTABLE_ERR);
+    }
+
+    @Override
+    public void clear() {
+        throw new UnsupportedOperationException(IMMUTABLE_ERR);
+    }
+
+    @Override
+    public void trimToSize(int newSize) {
+        throw new UnsupportedOperationException(IMMUTABLE_ERR);
+    }
+
+    @Override
+    public void parse2DJSON(String str) {
+        throw new UnsupportedOperationException(IMMUTABLE_ERR);
+    }
+
+}


Test patch:
diff --git a/core/src/test/java/com/graphhopper/util/PathSimplificationTest.java b/core/src/test/java/com/graphhopper/util/PathSimplificationTest.java
index 9bea21eea..c0d012518 100644
--- a/core/src/test/java/com/graphhopper/util/PathSimplificationTest.java
+++ b/core/src/test/java/com/graphhopper/util/PathSimplificationTest.java
@@ -154,6 +154,11 @@ public class PathSimplificationTest {
 
         assertEquals(numberOfPoints, pathWrapper.getPoints().size());
 
+        pathWrapper = new PathWrapper();
+        pathWrapper.setInstructions(wayList);
+        pathWrapper.addPathDetails(details);
+        pathWrapper.setPoints(p.calcPoints());
+
         douglasPeucker.setMaxDistance(100000000);
         ps = new PathSimplification(pathWrapper, douglasPeucker, true);
         ps.simplify();
diff --git a/core/src/test/java/com/graphhopper/util/PointListTest.java b/core/src/test/java/com/graphhopper/util/PointListTest.java
index dcd0d4c22..beaa879c1 100644
--- a/core/src/test/java/com/graphhopper/util/PointListTest.java
+++ b/core/src/test/java/com/graphhopper/util/PointListTest.java
@@ -20,7 +20,11 @@ package com.graphhopper.util;
 import com.graphhopper.util.shapes.GHPoint;
 import org.junit.Test;
 
+import java.util.Arrays;
+
 import static org.junit.Assert.assertEquals;
+import static org.junit.Assert.assertNotEquals;
+import static org.junit.Assert.assertTrue;
 
 /**
  * @author Peter Karich
@@ -110,4 +114,111 @@ public class PointListTest {
         assertEquals(1, copy.getCapacity());
         assertEquals(9, copy.getLongitude(0), .1);
     }
+
+    @Test
+    public void testShallowCopy() {
+        PointList pl1 = new PointList(100, true);
+        for (int i = 0; i < 1000; i++) {
+            pl1.add(i, i, 0);
+        }
+
+        PointList pl2 = pl1.shallowCopy(100, 600, false);
+        assertEquals(500, pl2.size());
+        for (int i = 0; i < pl2.size(); i++) {
+            assertEquals(pl1.getLat(i + 100), pl2.getLat(i), .01);
+        }
+
+        // If you change the original PointList the shallow copy changes as well
+        pl1.set(100, 0, 0, 0);
+        assertEquals(0, pl2.getLat(0), .01);
+
+        // Create a shallow copy of the shallow copy
+        PointList pl3 = pl2.shallowCopy(0, 100, true);
+        // If we create a safe shallow copy of pl2, we have to make pl1 immutable
+        assertTrue(pl1.isImmutable());
+        assertEquals(100, pl3.size());
+        for (int i = 0; i < pl3.size(); i++) {
+            assertEquals(pl2.getLon(i), pl3.getLon(i), .01);
+        }
+
+        PointList pl4 = pl1.shallowCopy(0, pl1.size(), false);
+        assertTrue(pl1.equals(pl4));
+
+        PointList pl5 = pl1.shallowCopy(100, 600, false);
+        assertTrue(pl2.equals(pl5));
+
+    }
+
+    @Test(expected = IllegalStateException.class)
+    public void testImmutable() {
+        PointList pl = new PointList();
+        pl.makeImmutable();
+        pl.add(0, 0, 0);
+    }
+
+    @Test()
+    public void testToString() {
+        PointList pl = new PointList(3, true);
+        pl.add(0, 0, 0);
+        pl.add(1, 1, 1);
+        pl.add(2, 2, 2);
+
+        assertEquals("(0.0,0.0,0.0), (1.0,1.0,1.0), (2.0,2.0,2.0)", pl.toString());
+        assertEquals("(1.0,1.0,1.0), (2.0,2.0,2.0)", pl.shallowCopy(1, 3, false).toString());
+    }
+
+    @Test()
+    public void testClone() {
+        PointList pl = new PointList(3, true);
+        pl.add(0, 0, 0);
+        pl.add(1, 1, 1);
+        pl.add(2, 2, 2);
+
+        PointList shallowPl = pl.shallowCopy(1, 3, false);
+        PointList clonedPl = shallowPl.clone(false);
+
+        assertEquals(shallowPl, clonedPl);
+        clonedPl.setNode(0, 5, 5, 5);
+        assertNotEquals(shallowPl, clonedPl);
+    }
+
+    @Test()
+    public void testCopyOfShallowCopy() {
+        PointList pl = new PointList(3, true);
+        pl.add(0, 0, 0);
+        pl.add(1, 1, 1);
+        pl.add(2, 2, 2);
+
+        PointList shallowPl = pl.shallowCopy(1, 3, false);
+        PointList copiedPl = shallowPl.copy(0, 2);
+
+        assertEquals(shallowPl, copiedPl);
+        copiedPl.setNode(0, 5, 5, 5);
+        assertNotEquals(shallowPl, copiedPl);
+    }
+
+    @Test()
+    public void testCalcDistanceOfShallowCopy() {
+        PointList pl = new PointList(3, true);
+        pl.add(0, 0, 0);
+        pl.add(1, 1, 1);
+        pl.add(2, 2, 2);
+
+        PointList shallowPl = pl.shallowCopy(1, 3, false);
+        PointList clonedPl = shallowPl.clone(false);
+        assertEquals(clonedPl.calcDistance(Helper.DIST_EARTH), shallowPl.calcDistance(Helper.DIST_EARTH), .01);
+    }
+
+    @Test()
+    public void testToGeoJson() {
+        PointList pl = new PointList(3, true);
+        pl.add(0, 0, 0);
+        pl.add(1, 1, 1);
+        pl.add(2, 2, 2);
+
+        assertEquals(3, pl.toGeoJson(true).size());
+        assertEquals(2, pl.shallowCopy(1, 3, false).toGeoJson(true).size());
+    }
+
+
 }