[mkgmap-dev] Increasing the performance of whole-planet splits.From Chris Miller chris_overseas at hotmail.com on Fri Jun 11 19:15:13 BST 2010
Hello Scott, I was doing some similar back-of-envelope calcs earlier today and came to a similar conclusion. I do think there's a lot of people splitting quite a way below 1,000,000 nodes/tile, but even still a map's far easier to implement than rtrees and is a big win over what we have now so it's probably not worth worrying too much about where the crossover point is. > A 256x256 map would have 65536 cells about 120km on a side. Looking at > the overview map of a max-nodes=1000000 split in qlandkarte, which > shows tile boundaries,.I'd guess the worst case would be 10-15 tiles > in a cell. That would prune away at least 97.5% of the bounds-checks. > > With the planet file, at this nodecount and cell size, an R-tree > traversal would likely have more boundschecks than that. I could see > an r-tree being a win if tilesizes got a lot smaller, say people > started to run max-nodes=50000 splits, or spitted files with insane > node densities, such as contour lines. > > To reduce the memory requirements, sets of candidate areas > would probably need to be pooled and reused across multiple points on > the > density map. > I wouldn't worry too much about memory. Absolute worst case is each > cell has all 255 areas, which would be 4 bytes * 255 areas IntList * > (256*256 cells) =64mb. Use a ByteList and it's 16mb. Bitvector and > it's 2mb. More realistically, I'd expect it to be 1/10th of the worst > case. > > Scott
- Previous message: [mkgmap-dev] Increasing the performance of whole-planet splits.
- Next message: [mkgmap-dev] Increasing the performance of whole-planet splits.
- Messages sorted by: [ date ] [ thread ] [ subject ] [ author ]
More information about the mkgmap-dev mailing list