Alternative protobuf library?

[cldellow]

Do you have any thoughts on switching away from libprotobuf?

It has nice developer ergonomics, but for the OSM use case of "very big structures with lots of strings", it feels like it has bad performance and memory characteristics -- strings get materialized as std::string, which causes a lot of heap churn.

It sounds like MapBox's protozero would be a good alternative (you've mentioned in #60 (comment) and #502 (comment))

We could either roll our own reading on top of protozero, or consider depending on libosmium, who use protozero.

My sense is that libosmium is quite a general, heavyweight tool compared to Tilemaker's use case. For users on distros where it's not packaged, building it might be a hassle. Further, we'd have to have some knowledge of what it's doing under the covers--for example, on a brief skim of its documentation and GitHub issues, I think we'd need to set some configuration options to avoid it trying to do its own threading and kernel page cache handling.

On the other hand, it's potentially quite nice to have a ready-made OM and API for the OSM PBF format.

My instinct is it's probably better to reinvent the wheel and roll our own reading on top of protozero. (And eventually, use vtzero for reading/writing vector tiles, so we can drop libprotobuf entirely.)

[systemed]

Absolutely yes - I'd very much like to move away from libprotobuf to something built on protozero. There'd certainly be a performance boost, and libprotobuf is more complex to build now that Google have shunted it into Abseil.

I had a brief look at it a couple of months back; reconstructing vector tile features for --merge looked like the hardest work. But we could make a start by moving to protozero for .osm.pbf reading. I'd tend to agree that libosmium doesn't bring us much over and above protozero - our use case is fairly specialised.

[cldellow]

Great, I'll have a look at starting with the OSM PBF reading.

I agree that switching out the vector tile protobuf will likely be the more complex of the two tasks. I'm hoping vtzero will help a lot, though.

[pnorman]

On the other hand, it's potentially quite nice to have a ready-made OM and API for the OSM PBF format.

As well as all other formats that it supports.

With all workloads involving geometry, libosmium reading PBFs is never a performance limiter. It's always building or processing geoms or IO stuff.

[cldellow]

Hey Paul, thanks for chiming in!

Re other file formats: my interest is primarily making PBFs faster. For me, the ease of supporting XML tomorrow at the expense of PBF performance today isn't a good tradeoff.

Re "reading PBFs is never a performance limiter" - I find it easier to reason about these things when there are numbers attached.

I tried to read the planet using the osmium_count example.

On a 48-core machine: 180 seconds, ~25% CPU utilization

For me, a libprotobuf replacement ought to use close to 100% CPU in a multithreaded situation, as parsing a PBF is an embarrassingly parallel task. The PBF was entirely cached in the page cache, so this strictly measured parsing, not I/O. (For the case where it's not cached, this machine can do 2 GB/sec of I/O, so I/O wouldn't be a limiting factor compared to 3 minutes of CPU use.)

In some sense, 3 minutes isn't a lot of time. In another sense, it's about 5% of the total time today, so it's a candidate for scrutiny. Yes, there are other parts of tilemaker that take longer -- and I'll get to them, too, in time. :)

Setting aside the count example, Tilemaker has some special requirements:

• in the constrained-memory case, we segment the planet such that we can build index structures that fit in RAM. This requires repeatedly reading the PBF -- so inefficiencies stack up.

• When Sort.Type_then_ID is set for a PBF (which is generally the case), Tilemaker can skip entire PrimitiveBlock structures when looking for nodes, ways and relations. By contrast, it looks like libosmium skips them at the PrimitiveGroup level, which still requires reading and decompressing the PrimitiveBlock structure.

• When Sort.Type_then_ID is set, Tilemaker distributes work to worker threads such that they can build indexes independently, with minimal locking and memory usage. This requires each worker thread to be working on PrimitiveBlock blocks that are far apart from the other threads. By contrast, I think libosmium distributes PrimitiveBlock blocks in a relatively linear fashion as to their location in the source PBF.

It doesn't look like libosmium exposes an interface that operates at the PrimitiveBlock level, nor do their higher-level interfaces do anything differently when Sort.Type_then_ID is present. A recent PR that added random access when this flag was present received pushback from libosmium's maintainer, and ultimately wasn't merged.

None of this detracts from libosmium, in my view. It just means that they solve a much broader task and so have a different set of priorities for which to optimize.

[pnorman]

cc @joto who knows a lot more about libosmium than me.

I think the real question for performance is can the PBF reader feed data quickly enough to the other threads to keep them busy. If you stick a planet file onto sufficiently fast storage (e.g. ramdisk) and do a simple task like osmium_count, you will end up bottlenecked on osmium, but in most real-world cases I've seen other factors are significant.

[pnorman]

And I would probably prioritize developer experience if there's no huge performance differences. That matters more than multiple filetype support or a couple percent gain.

[joto]

A few things re libosmium:

@cldellow > For users on distros where it's not packaged, building it might be a hassle.

There is nothing to build, libosmium is a header only library. And I wouldn't describe it as "heavyweight", because due to the header-only-architecture you can just use the parts you need and ignore the others. So libosmium is quite easy to use and integrate. It depends on the use case whether you need other libraries that libosmium uses, if you don't want to parse OSM XML files for instance, you don't have the dependency on expat.

@cldellow > It sounds like MapBox's protozero would be a good alternative

Interestingly enough I developed protozero exactly for the problem you are discussing here, to replace use of Googles protobuf libraries in libosmium because it had too much memory allocation overhead. So I can recommend using protozero, but I am biased. Just keep in mind that protozero is a very low-level library and you really have to understand the details of the Protobuf format to use it properly, it is very easy to shoot yourself in the foot or implement something that will not work in some corner case.

@systemed > I'd tend to agree that libosmium doesn't bring us much over and above protozero - our use case is fairly specialised.

It's interesting that you see it that way, because I created libosmium for exactly your use case (and many others of course). Reading OSM files quickly is what libosmium does and many tools read them several times. If you see the need to reimplement OSM file parsing, then libosmium is failing you in some way and I'd like to improve libosmium so it also works for you. Maybe this is not possible, because libosmium has made some decisions in its architecture which will affect its use too much. For instance it is implemented in a way that it works with all sorts of OSM file formats, hiding the details from the user of the library. Of course you can make some shortcuts, if that is not important to you. In the end there are some tradeoffs here. I'd rather hope you'll spend the time improving OSM file reading in libosmium where many people can use that improvement then rolling your own duplicating effort. But again, I am biased.

@cldellow > I tried to read the planet using the osmium_count example...

As @pnorman mentioned this is not the best example for measuring performance, but there is a problem somewhere in libosmium that limits multi-threading that I haven't found yet. There are circumstances (with large numbers of CPUs) where it seems threads are blocking each other for no reason. Debugging multithreading performance is hard, and it seems I have reached the limits of my capabilities there. (I don't even now how "real" that problem is, even measuring that is hard. Maybe this is just limits of the concurrency of several CPUs having to access the same memory or so.) I'd very much appreciate any help with that, if you can speed up libosmium, many people will benefit from that.

@cldellow > Tilemaker can skip entire PrimitiveBlock structures when looking for nodes, ways and relations. By contrast, it looks like libosmium skips them at the PrimitiveGroup level, which still requires reading and decompressing the PrimitiveBlock structure.

I'd have to look into the details here, its a long time ago that I wrote that code. But it might be one of those corner cases in the format where what you can do depends on whether you implement the spec or whether you implement something that works with the files currently out there. Libosmium tries very hard to make sure it can read any file that is created according to the spec. I believe this is important for compatibility with current and future software. Maybe I am wrong and there is some performance to be gained here, then we should improve libosmium.

(Btw this is not a theoretical problem: We do have problems with some popular PBF reading software that doesn't parse PBFs according to the spec. This makes further development of the PBF format difficult, even though the format has extensibility builtin due to its Protobuf roots, but we can't use that because it breaks that software.)

@cldellow > It doesn't look like libosmium exposes an interface that operates at the PrimitiveBlock level, ...

That's true. This goes back to the "hide the file format" from the user architecture. But I am willing to rethink that, as I told the developer with the PR you mentioned. The reason that PR was not merged was because it was far from ready to be merged as acknowledged by that developer themselve. The PR had some interesting ideas but ultimately the developer gave up on it after some misunderstandings about what I needed from him to push this forward.

So where does that leave us (in my opinion)? Id would be great if we can improve libosmium in a way that it would work for tilemaker. There will always be some (performance and other) tradeoffs using a general library rather than rolling your own, we are all aware of that. I am a big fan of creating libraries, in the short run it always seems to be more work, but in the long run its saves everybody some effort. I created protozero as its own library and didn't just add that code to libosmium, because I thought it works on its own and is reasonably self-contained. And this later allowed other uses like for vtzero. Maybe there is a way to re-write some of the PBF-parsing code in libosmium so it becomes usable outside the wider libosmium context and can stand on its own. So that at least libosmium and tilemaker can share that lower-level PBF code. Maybe inside libosmium, maybe it has to go into an intermediary small library?

[systemed]

It's interesting that you see it that way, because I created libosmium for exactly your use case (and many others of course). Reading OSM files quickly is what libosmium does and many tools read them several times. If you see the need to reimplement OSM file parsing, then libosmium is failing you in some way and I'd like to improve libosmium so it also works for you. Maybe this is not possible, because libosmium has made some decisions in its architecture which will affect its use too much. For instance it is implemented in a way that it works with all sorts of OSM file formats, hiding the details from the user of the library. Of course you can make some shortcuts, if that is not important to you. In the end there are some tradeoffs here. I'd rather hope you'll spend the time improving OSM file reading in libosmium where many people can use that improvement then rolling your own duplicating effort. But again, I am biased.

:)

There's absolutely an argument to say that using libosmium to build tilemaker when the project started in 2015 would have been a plausible way to start - just as it would have been possible to start with GEOS rather than Boost.Geometry (which might have saved a few multipolygon headaches along the way).

But in 2023 we have pretty much everything we need in terms of OSM object handling - which, to be honest, is not that much. Generally we want to get nodes, ways and relations out of the way pretty early on: as far as tilemaker is concerned, they're largely an implementation detail of ingesting PBFs. libosmium does lots of wonderful things, but by and large they're either things we're doing already or things we don't need to do.

Maybe there is a way to re-write some of the PBF-parsing code in libosmium so it becomes usable outside the wider libosmium context and can stand on its own. So that at least libosmium and tilemaker can share that lower-level PBF code. Maybe inside libosmium, maybe it has to go into an intermediary small library?

That's an interesting idea! But I'm honestly not sure the refactoring required would justify it. protozero is a good fit for tilemaker's OSM parsing needs, I think - we want to read a stable schema into our own existing data structures, and that's it. I would worry that building an extra layer, sitting between protozero and either libosmium or tilemaker, would be an extra abstraction without a massive gain for either client.

[cldellow]

Hi Jochen, nice to meet you!

There is nothing to build, libosmium is a header only library.

Yes, when I wrote that, I wasn't yet aware that libosmium was header-only. I do see that it's factored such that you can also avoid dependencies on lz4/bz2 if you just want to parse the typical PBFs that rely on zlib. That's great, and mitigates the building concern.

Based on my new understanding, I'd reframe my concern as "libosmium is higher-level than Tilemaker wants" -- it wants to control threading and memory management, whereas we'd prefer to manage those and just re-use its parsing functions.

So I can recommend using protozero, but I am biased.

Yes, protozero was quite straight-forward to get going, thanks for making it!

I replaced libprotobuf with a proof of concept based on protozero. It gives a runtime reduction of ~10% during our read phase, and a memory reduction of ~26%. I haven't yet fully removed heap allocations for strings that don't fit in the small-string optimization, so I expect to be able to improve on these numbers still.

As @pnorman mentioned this is not the best example for measuring performance,

I feel like I really need to push back here. :)

As I said, reading a PBF is a perfect task for parallelizing. The count example is a cheap way to explore if off-the-shelf libosmium has architectural assumptions that might limit its use in tilemaker, or requires digging in to its internals to understand how best to operate it. It appears that it does.

I do understand that PBF reading is only a part of the puzzle, and the performance of downstream parts of Tilemaker will affect overall results. I have spent some time to ensure that the downstream parts will not be the limiting factor. This seems to be borne out by the decrease in reading time that my proof of concept shows.

The comments I'm hearing seem to be in the vein of "reading the PBF is the easy part, it's the hard part that will take time." I accept that premise, but the logical conclusions to me are (1) if it's the easy part, we ought to be able to do it fast and (2) if I have all these cores for the hard part, it'd be nice if they were used by the easy part.

Apologies if this comes off as prickly - I opened this discussion to ask the maintainer of Tilemaker a question, and now I feel like I'm having to defend whether or not I understand fairly general concepts about software performance while staring at 75% of my cores sitting idle.

There are circumstances (with large numbers of CPUs) where it seems threads are blocking each other for no reason.

What counts as large? My hope is for Tilemaker to be suitable for running on, say, 64 core machines.

Even on my 16-core laptop, I achieve only about 62% CPU usage. I observe many threads blocked on https://github.com/osmcode/libosmium/blob/bf61abd59f3ded669da2bb98fd066ea05ec17c04/include/osmium/thread/pool.hpp#L131.

Tracing around m_work_queue, I see https://github.com/osmcode/libosmium/blob/bf61abd59f3ded669da2bb98fd066ea05ec17c04/include/osmium/thread/pool.hpp#L81-L83 -- perhaps there is a default concurrency of 10 for this?

I tried again with OSMIUM_MAX_WORK_QUEUE_SIZE=16, but did not observe a change in behaviour.

Oh, I think this is perhaps the pending buffer of Blobs to be parsed, so the number probably ought to be much more than the number of workers in the interests of not stalling the producer. Even if I try, say, 4096, I do not observe a change in behaviour.

It looks like this queue is fed by parse_data_blobs.

It looks like this is a single-producer, multiple-consumer queue where the producer is also responsible for doing the I/O and memory allocations for the entire Blob rather than delegating that work to the consumer? That could be an issue.

I also see that the work queue uses a custom queue implementation where both the producer and consumers are contending the same resource. Indeed, in my stack traces, I see the producer blocked on the queue mutex. That is likely an issue.

Some approaches that can reduce lock contention here might be:

• maintain two queues: have the producer publish to one and the consumers read from the other. Periodically swap the queues. Now you only need the producer and consumers to contend the same resource when the consumers run out of work, not in the happy path when there is work available
• maintain N queues: the producer can write to an arbitrary queue, the consumers can read from an arbitrary queue. In the special case where a consumer finds no work, it can search the full set of queues.

Maybe this is just limits of the concurrency of several CPUs having to access the same memory or so.

Yes, I think libosmium's current approach has lock contention issues.

At a high-level: 72 GB across 48 cores over 180 seconds implies that each core processed 9MB/sec. Computers can read memory faster than 9MB/sec, which is why I expected 100% CPU usage.

Tilemaker avoids this issue by structuring its work such that the threads don't need to coordinate.

The reason that PR was not merged

Yes, I tried to word my comment about that very carefully! :) The developer in question produced a very large change without a lot of consultation, and then got frustrated when the interaction didn't go as they wished. I totally understand the outcome!

But it might be one of those corner cases in the format where what you can do depends on whether you implement the spec or whether you implement something that works with the files currently out there.

I believe what we're doing complies with the spec. We do three things that are important for our performance:

1. We build a list of positions of PrimitiveBlocks in the PBF. This requires only reading the BlobHeader objects, which are quite small and simple to parse.

2. When Sort.Type_then_ID is present, we do a binary search over those blocks to find the first block with a way/relation, and the first block with a relation. This lets future passes skip reading/decompressing blocks that we know will not have any OSM entities that are relevant to the pass.

3. Where libosmium's unit of work is the Blob message (~GBs of size, cumulatively), tilemaker's unit of work is a list of positions of PrimitiveBlocks (~KBs of size, cumulatively). This provides two benefits: (a) it's very cheap for the producer to feed the work queue, and (b) it means consumers see a run of PrimitiveBlocks that are in order. This is important for us when building indexes - it means each worker can build a portion of the index without coordinating with each other.

These are fairly benign optimizations, IMO. They just depend on having knowledge of the existence of PrimitiveBlocks.

Maybe there is a way to re-write some of the PBF-parsing code in libosmium so it becomes usable outside the wider libosmium context and can stand on its own. So that at least libosmium and tilemaker can share that lower-level PBF code. Maybe inside libosmium, maybe it has to go into an intermediary small library?

Sounds sensible! I think the path forward in the near-term is for Tilemaker to do its own thing on protozero. This will prove out the merit, if any, of the idea. If it ends up being useful, it will provide real-world feedback on what API surface Tilemaker would need from libosmium or a potential PBF-specific library.

I imagine that it'd be easy to replace Tilemaker's potential protozero code with a potential future libosmium/PBF-specific API -- it's fairly low-level and solves a fairly constrained problem (as evidenced by the time it took to make a protozero POC).

Thanks for sharing your thoughts!

[joto]

@cldellow Thanks for the analysis of the lock contention issue. I was always wondering if I am doing something wrong with the mutexes or so, but maybe it is just the way they are and I have to look into working around that. Your ideas for new approaches are definitely very interesting.

I like your thinking on the "path forward". Its better to have something working first and then maybe iterate on that than trying to come up with a design up-front.

[cldellow]

I do like the idea of contributing back to libosmium, though! I might take a stab at some PRs that try to tackle the queue contention.

For some broader context--as part of this discussion, I reviewed some of the libosmium code. It frankly seems to be written to a much higher level of quality than what I can currently write. :) So when I consider the task of proposing an architecture change that is suitable for a general-purpose library plus implementing that change to a suitable level of quality before I can unblock my immediate task, I find myself thinking I should start with something less ambitious.

[joto]

Thanks for kudos. Mostly I think that's because libosmium has been around for a long time and that code got refactored many times. In my experience code never starts out really great, you just have to keep working on it.