On Thu, Oct 27, 2011 at 4:56 AM, GerdP <gpetermann_muenchen@hotmail.com> wrote:
Hello list,
since a few days I try to understand the idea of the class SparseInt2ShortMapInline in splitter because this seems to waste memory although it is documented to save it. If I got this right, the amount of needed memory directly depends on the highest id that is saved, thus for example the data for a small country like german "bundesland" saarland (from geofabrik) is not processed with java -Xmx700 -jar splitter.jar --max-areas=2 --max-nodes=200000 e:\dwnload\saarland.osm.pbf
There are two main algorithms. O(A*# distinct ID's), using a hash table, with A being around 64 bits (with 32 bit node IDs) or 100 bits (with 64 bit node IDs) But, this would result in too much memory usage for a whole planet due to the constant factor of the A. The current algorithm is O(B*#maximum_id) with the constant But, factor B is a lot smaller than A, around 4 bits unused entry and 20 bytes per used entry For a whole planet split, this is a third or half of the memory of the first choice.
I tried that with R181 and R180. The program runs without problems when I change the code so that SparseInt2ShortMultiMap always uses Int2ShortOpenHashMap and not SparseInt2ShortMapInline. Was this code optimized for a special input (e.g.with small id values) ?
No. The code is tuned for whole-planet splits, where minimizing memory consumption is paramount. The right algorithm would adapt the number of nodes, using Int2ShortOpenHashMap when for small splits (say, country-sized or smaller) and SparseInt2ShortMapInline for whole planet splits. Maybe do it as a command line option? I recommend against your proposed change later in the thread because it will increase the memory usage by at least 500mb for whole-planet splits. (1.5B nodes requires at least 25M Storers, with 8 bytes object overhead + 4 bytes hashtable key + 4 bytes hashtable value pointer + 50% hashtable overhead, or about 20 bytes each) Scott