-
Notifications
You must be signed in to change notification settings - Fork 25
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Investigate indexing performance #55
Comments
@noffle I sometimes assign to myself (I don't like to be assigned stuff but assigning myself is ok ;) and then I can go and check |
I forgot about that. Thanks @ralphtheninja! ❤️ |
Indexing time is bottlenecked by insertions to kdb-tree-store. I tried plugging in It looks like reading out and parsing the point data from the chunk-store is where the most time is going. As true today as it was in 2015!) |
This is a pretty long response! I was thinking about it as a draft for some kind of technical post for the Dd blog. Big 'ol update!A while ago I spent a few days understanding and trying to optimize kdb-tree-store, which was a major bottleneck in how osm-p2p-db turns its raw data into a fast, queryable geo-spatial index. Here's that PR: peermaps/kdb-tree-store#5 Lo and behold: it's about 3-4x faster at insertions now, and the resulting gain to osm-p2p-db indexing is that it's about 1.7x faster (or, indexes take 57% the time to generate). This is great: my Lenovo Thinkpad with a spinning hard drive went down from 12 minutes of indexing on a big dataset down to 7.4 minutes! Noticably faster, even on my newer Dell XPS 13, which is down from 76 seconds to 43 seconds. Energized by these time savings and by the research I had done on other ways of storing geo-spatial data, I sought to experiment with geohashing and one of @gmaclennan's ideas of a fixed-grid point store. I felt good that I could make even faster geo point stores! First was geohash-point-store, which is very fast at insertions, but can be easily an order of magnitude slower on queries, depending on the size of the query region. I also realized after I wrote it that there's a caveat where I'd actually need to store multiple points at a geohash address potentially, which necessitates an extra For referencing map data, OSM divides the world into 19 layers of fixed-size grids. At zoom level 1, the whole world is a single tile. At zoom level 2, the world is 4 tiles. Each level multiplies the # of tiles by 4. With this, enter grid-point-store. It's a point store that you provide a zoom level to, and it stores points on that fixed grid at whatever zoom. It uses LevelDB underneath, which can do ridiculously fast range queries over sequential keys. Armed with this knowledge, the module converts numeric Net result: grid-point-store blows everything else away! geohash-point-store was faster than kdb-tree-store, but grid-point-store is almost 5 times faster than that! It also has a nicer speed curve as query size goes up compared to the geohashing approach. Naturally I expected this to mean that osm-p2p-db indexing would become at least 5 times faster than before. Ha, not so! In fact, there was no speed increase with grid-point-store compared to my optimized version of kdb-tree-store. After doing some profiling with the very handy built-in This could be seen as a bit of a bummer, but I'm feeling really good about my plans to move osm-p2p-db to be backed by hyperdb in the near-ish future, which has some really great performance characteristics. Once we do that, the indexing machinery's bottleneck should be gone, which will let us tap into that sweet sweet speedy geo-indexing power lying in wait in grid-point-store. All in all time really well spent: I learned a ton about geo math, kdb trees, and node profiling, which is going to serve me really well in the future. Thanks for reading! 👋 ⛵ 🌴 |
@noffle It would be nice with a writeup on profiling in itself, apart from the other technical details. |
profiling@ralphtheninja For me, profiling was the easy part! At first I spent some time fudging with flame graphs. On Linux I installed
Which makes nice little visual representations of where your CPU time is going. I found it kind of complicated and onerous to use, which led me to learning that node (via v8) has a super easy built-in profiling mechanism, which I use via this script:
This text document gives you a breakdown of where ticks (I think libuv ticks) are going. You'll see something like
which goes on and on. You can pretty quickly identify bottlenecks. There is a top-most section for each native dependency. My usual fallback is nothing more than |
Supernice. Thanks 😀
And I guess not putting |
Right on! I usually do something like var accum = 0
var d
for (var i=0; i < 10000; i++) {
d = Date.now()
hotFunc()
accum += Date.now() - d
}
console.log('overall time', accum, 'ms') so that writing to stdout isn't what dominates. |
I'd really like to see faster indexing. Multiple people have brought up how slow it can be. Reminder to myself to do some profiling on the indexing pipeline and find the bottlenecks.
The text was updated successfully, but these errors were encountered: