forked from opentripplanner/OpenTripPlanner
Experiment: Memory usage statistics
Andrew Byrd edited this page Dec 17, 2014
·
1 revision
Here are some statistics and memory usage of OTP, to evaluate potential (memory) optimizations. The good news is that there is room for improvements. The results were somehow surprising, and we came across some interesting things.
- All graphes are generated without transit data, we are only focusing on street data for now.
- For the string memory size, we use the formula (36 + 2 * avgStrLen) * nStrings.
Some crude statistics regarding memory use and object counts (numbers generated using the "StatisticsGraphBuilder" class created for the test)
Netherlands Paris (IDF) NY state
-----------------------------------------------------
# geometries 4495406 1341581 2149554
Avg points/geom 3.43 3.83 5.66
Total length (km) 444528 146783 494817
Avg length (m) 98.89 109.41 230.20
# edges 4496274 1342044 2149672
PlainStreetEdge 4494910 1341265 2149524
E names char tot 47118843 16866978 27452714
# vertices 1634387 493646 832888
IntersectionVert 1632641 492862 830947
V names char tot 29250011 9130336 15001951
(V label char tot) 29267163 9141941 15002885
-----------------------------------------------------
Graph size 1233299705 378736886 670479076
OSM.pbf size 978920185 120574684 132945693
Calc geom mem 642303609 200271211 383845432
Heap usage 3499899000 1072950000 1777603000
" w/o geom 819542000 1325657000
" geom delta 253408432 451946000
" " " % ~25% ~25%
" w/o edge names 1049099000
" e names delta 23851000
" " " % ~2%
JVM heap/Graph ratio 2.83 2.83 2.65
-----------------------------------------------------
Retained size for all "dominated" (=~owned) objects of a single graph:
Class Name | Objects | Shallow Heap
------------------------------------------------------------------------------------------------
com.vividsolutions.jts.geom.Envelope | 3,326,096 | 159,652,608
org.opentripplanner.routing.edgetype.PlainStreetEdge | 1,341,265 | 118,031,320
char[] | 2,066,417 | 105,789,616
double[] | 1,341,627 | 103,620,544
java.util.HashMap$Entry | 2,834,022 | 90,688,704
org.opentripplanner.routing.util.ElevationProfileSegment | 1,341,265 | 85,840,960
java.lang.String | 2,066,417 | 49,594,008
com.vividsolutions.jts.index.strtree.ItemBoundable | 1,835,227 | 44,045,448
com.vividsolutions.jts.geom.LineString | 1,341,627 | 42,932,064
java.lang.Object[] | 1,137,169 | 40,084,344
org.opentripplanner.common.geometry.PackedCoordinateSequence$Double| 1,341,627 | 32,199,048
java.util.concurrent.locks.ReentrantLock$NonfairSync | 987,293 | 31,593,376
org.opentripplanner.routing.vertextype.IntersectionVertex | 492,862 | 31,543,168
java.lang.Integer | 1,835,436 | 29,366,976
java.util.concurrent.CopyOnWriteArrayList | 987,292 | 23,695,008
java.util.HashMap$Entry[] | 10,868 | 19,743,552
java.util.concurrent.CopyOnWriteArraySet | 987,292 | 15,796,672
java.util.concurrent.locks.ReentrantLock | 987,292 | 15,796,672
java.util.ArrayList | 149,878 | 3,597,072
com.vividsolutions.jts.index.strtree.STRtree$STRtreeNode | 149,290 | 3,582,960
java.util.TreeMap | 11,040 | 529,920
java.util.HashMap | 10,892 | 522,816
java.util.TreeMap$Entry | 11,040 | 441,600
Total: 23 of 68 entries; 45 more | 26,640,230 | 1,049,701,640
------------------------------------------------------------------------------------------------
Note: More details in the Addendum below.
- Serialized graph size is a good predictor of real JVM heap memory usage (multiply by 3). This at least for street-only graphs (if we add transit data this may vary a little).
- Edge name usage is rather small, lots of edges names are shared (if they come from the same OSM way), there is probably no need to optimize them.
- Vertex names and label are mostly sharing the same string instance; they could be replaced by optimized class (most of them only store values such as "osm:node:xxxxx").
- Other strings do not use interning so their memory usage should roughly follow the formula (number of edges * object size).
- String interning would probably be useless (most string values are different). Note: Since Java 7 String intern() use the Heap instead of the PermGen, so there is no limit anymore on String interning See this link.
- We could compact a bit by using a compact string implementation storing only a UTF-8 encoded byte array, saving roughly 50% of the original space.
- Huffman-encoded string could save a bit further (maybe to 25/30% of the original string size) at the expense of complexity.
- Geometry-related instances (JTS: Envelope, double[], LineString, ItemBoundable, PackedCoordSeq...) takes more than 1/3 of all memory, which is a lot.
- Use edge endpoint vertices for storing start/end point
- Use fixed-point precision data
- Use delta coding with variable len
- Share the same geometry for reversed segments
- Use QuadTree (Envelope instance count is roughly divided by 2 compared to STRtree)
- OR Use a simpler/customized spatial index, which does not store directly any Envelope
- Use an external store for the geometry and the spatial index
- Use int bitset for all booleans (back, roundabout, hasBogusName, noThruTraffic, stairs, toll...)
- Use int bitset and floats for ElevationProfileSegment
- Use delta-coding with variable len for elevationProfile (if any)
- Use float for length
- Remove the two Set (notes & wheelchairNotes)
- Use short for carSpeed
- Use 1 or 2 shorts for in/out angle
- Edge names: Use a compact string storing a single char[] of UTF-8 encoded data
- Vertex names and label: Use custom "VertexLabel" classes:
- OSMLabel class storing a single OSM nodes ID as long
- OSMLevelLabel with added OSMlevel
- XxxLabel for other uses Note: This has also the added value of preventing accidental label collisions.
- Object overhead (8)
- Geometry.envelope pointer (8) -- plus Envelope instance
- Geometry.geometryFactory pointer (8)
- Geometry.SRID int (4 or 8)
- Geometry.userData pointer (8)
- LineString.points pointer (8)
- PackedCoordinateSequence:
- Object overhead (8)
- dimension (4 or 8)
- coordRef soft ref (8)
- coords pointer (8 + 8)
- coords data (8 x 2 x len) So the formula becomes 88 + 16 x len. This is confirmed by heap measurements (real memory usage is ~15% more).
Dominators of Envelope (the biggest memory consumer):
Class Name | Objects | Dom. Objects | Shallow Heap | Dom. Shallow Heap
----------------------------------------------------------------------------------------------------------------------
com.vividsolutions.jts.index.strtree.ItemBoundable | 1,835,227 | 1,835,227 | 44,045,448 | 88,090,896
com.vividsolutions.jts.geom.LineString | 1,341,581 | 1,341,581 | 42,930,592 | 64,395,888
com.vividsolutions.jts.index.strtree.STRtree$STRtreeNode| 149,288 | 149,288 | 3,582,912 | 7,165,824
Total: 3 entries | 3,326,096 | 3,326,096 | 90,558,952 | 159,652,608
----------------------------------------------------------------------------------------------------------------------
Note: JTS Envelope contains 4 doubles, JVM size is 48 bytes per object.
Dominators of char[]:
Class Name | Objects | Dom. Objects | Shallow Heap | Dom. Shallow Heap
----------------------------------------------------------------------------------------------------------------------------
org.opentripplanner.routing.edgetype.PlainStreetEdge | 1,341,265 | 1,345,528 | 118,031,320 | 69,790,224
org.opentripplanner.routing.graph.Graph | 1 | 720,576 | 152 | 35,974,656
org.opentripplanner.routing.alertpatch.TranslatedString | 206 | 206 | 3,296 | 20,624
org.opentripplanner.routing.vertextype.TransitStopStreetVertex| 43 | 56 | 3,096 | 2,480
org.opentripplanner.routing.vertextype.ExitVertex | 31 | 31 | 2,232 | 752
org.opentripplanner.routing.vertextype.ParkAndRideVertex | 7 | 14 | 448 | 568
org.opentripplanner.common.MavenVersion | 1 | 6 | 48 | 312
Total: 7 entries | 1,341,554 | 2,066,417 | 118,040,592 | 105,789,616
----------------------------------------------------------------------------------------------------------------------------
Note: Since we filter out java.* classes, most of char[] are really Strings. Note: Most of String instances are shared (as Map keys and labels for example)
Dominators of double[]:
Class Name | Objects | Dom. Objects | Shallow Heap | Dom. Shallow Heap
---------------------------------------------------------------------------------------------------------------------------------
org.opentripplanner.common.geometry.PackedCoordinateSequence$Double| 1,341,627 | 1,341,627 | 32,199,048 | 103,620,544
---------------------------------------------------------------------------------------------------------------------------------
Note: All double arrays are contained in LineString data.
Dominators or Map.Entry:
Class Name | Objects | Dom. Objects | Shallow Heap | Dom. Shallow Heap
------------------------------------------------------------------------------------------------------------------
org.opentripplanner.routing.graph.Graph | 1 | 2,340,285 | 152 | 74,889,120
org.opentripplanner.routing.graph.GraphIndex | 1 | 493,646 | 104 | 15,796,672
org.opentripplanner.routing.edgetype.PlainStreetEdge| 91 | 91 | 8,008 | 2,912
Total: 3 entries | 93 | 2,834,022 | 8,264 | 90,688,704
------------------------------------------------------------------------------------------------------------------
Dominators of String:
Class Name | Objects | Dom. Objects | Shallow Heap | Dom. Shallow Heap
----------------------------------------------------------------------------------------------------------------------------
org.opentripplanner.routing.edgetype.PlainStreetEdge | 1,341,265 | 1,345,528 | 118,031,320 | 32,292,672
org.opentripplanner.routing.graph.Graph | 1 | 720,576 | 152 | 17,293,824
org.opentripplanner.routing.alertpatch.TranslatedString | 206 | 206 | 3,296 | 4,944
org.opentripplanner.routing.vertextype.TransitStopStreetVertex| 43 | 56 | 3,096 | 1,344
org.opentripplanner.routing.vertextype.ExitVertex | 31 | 31 | 2,232 | 744
org.opentripplanner.routing.vertextype.ParkAndRideVertex | 7 | 14 | 448 | 336
org.opentripplanner.common.MavenVersion | 1 | 6 | 48 | 144
Total: 7 entries | 1,341,554 | 2,066,417 | 118,040,592 | 49,594,008
----------------------------------------------------------------------------------------------------------------------------
Note: To really account for complete String size, add char[] and String.
Dominators of Object[]:
Class Name | Objects | Dom. Objects | Shallow Heap | Dom. Shallow Heap
----------------------------------------------------------------------------------------------------------------------------
org.opentripplanner.routing.vertextype.IntersectionVertex | 492,862 | 985,724 | 31,543,168 | 29,492,464
com.vividsolutions.jts.index.strtree.STRtree$STRtreeNode | 149,289 | 149,289 | 3,582,936 | 8,360,184
com.vividsolutions.jts.index.strtree.STRtree | 1 | 1 | 32 | 2,160,888
org.opentripplanner.routing.edgetype.PlainStreetEdge | 587 | 587 | 51,656 | 32,872
org.opentripplanner.routing.vertextype.ExitVertex | 363 | 726 | 26,136 | 17,456
org.opentripplanner.routing.vertextype.ElevatorOffboardVertex | 158 | 316 | 10,112 | 7,584
org.opentripplanner.routing.vertextype.ElevatorOnboardVertex | 158 | 316 | 10,112 | 7,584
org.opentripplanner.routing.vertextype.TransitStopStreetVertex| 98 | 196 | 7,056 | 4,816
org.opentripplanner.routing.vertextype.ParkAndRideVertex | 7 | 14 | 448 | 496
Total: 9 entries | 643,523 | 1,137,169 | 35,231,656 | 40,084,344
----------------------------------------------------------------------------------------------------------------------------
Dominators of ReentrantLock$NonfairSync:
Class Name | Objects | Dom. Objects | Shallow Heap | Dom. Shallow Heap
----------------------------------------------------------------------------------------------------------------------------
org.opentripplanner.routing.vertextype.IntersectionVertex | 492,862 | 985,724 | 31,543,168 | 31,543,168
org.opentripplanner.routing.vertextype.ExitVertex | 363 | 726 | 26,136 | 23,232
org.opentripplanner.routing.vertextype.ElevatorOffboardVertex | 158 | 316 | 10,112 | 10,112
org.opentripplanner.routing.vertextype.ElevatorOnboardVertex | 158 | 316 | 10,112 | 10,112
org.opentripplanner.routing.vertextype.TransitStopStreetVertex| 98 | 196 | 7,056 | 6,272
org.opentripplanner.routing.vertextype.ParkAndRideVertex | 7 | 14 | 448 | 448
org.opentripplanner.routing.graph.Graph | 1 | 1 | 152 | 32
Total: 7 entries | 493,647 | 987,293 | 31,597,184 | 31,593,376
----------------------------------------------------------------------------------------------------------------------------
Note: all instances dominated by Vertex classes are generated by incoming/outgoing CopyOnWriteArraySet.