Skip to content

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.

Test assumptions

  • 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.

StatisticsGraphBuilder results

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
-----------------------------------------------------

Memory analyzer results (IDF graph)

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.

Conclusions

  • 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.

Possible optimizations

Potential Geometry optimizations

  • 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

Potential PlainStreetEdge optimizations

  • 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

Potential String optimizations

  • 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.

Addendum and notes

Details of LineString memory size computation

  • 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).

Memory Analyzer results (cont'd)

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.

The documentation on this wiki is outdated and should not be used

unless you are intentionally working with legacy versions of OpenTripPlanner. Please consult the current documentation at readthedocs

Clone this wiki locally