* refactor NodeStore
I'd like to add an alternative NodeStore that can be used when the
`Type_then_ID` property is present in the PBF.
First, a small (?) refactor:
- make `NodeStore` an interface, with two concrete implementations
- extract the NodeStore related things to their own files
- this will cause some churn, as they'll depend on things that also
need to get extracted to their own files. Short term pain, hopefully
long term gain in faster compile times.
Changing the invocations of the functions to be virtual may have impact
on performance. Will need to revisit that before committing to virtual
methods.
* change how work is assigned for ReadPhase::Nodes
Currently, when a worker needs work, it gets the next unprocessed block.
This means blocks are read sequentially at a global level, but from
the perspective of each worker, there are gaps in the blocks they see.
For nodes, we'd prefer to give each worker thread contiguous blocks
from the underlying PBF. This will enable a more efficient storage
for PBFs with the `Sort.Type_then_ID` flag.
* add SortedNodeStore
SortedNodeStore is uesful for PBFs with the `Sort.Type_then_ID`
property, e.g. the planet and Geofabrik exports.
It stores nodes in a hierarchy:
- Level 1 is groups: there are 256K groups
- Level 2 is chunks: each group has 256 chunks
- Level 3 is nodes: each chunk has 256 nodes
This allows us to store 2^34 nodes, with a fixed overhead of
only 2M -- the space required for the level 1 pointers.
Groups and chunks store their data sparsely. If a group has 7 chunks,
it only uses storage for 7 chunks.
On Great Britain's 184M node PBF, it needs ~9.13 bytes per node.
Looking up a node can be done in fixed time:
First, get some offsets:
- Group: `nodeID / 65536`
- Chunk: `(nodeID / 65536) / 256`
- Position within chunk: `nodeID % 256`
For example, Cape Chignecto Provincial Park has ID 4855703, giving:
- Group 74
- Chunk 23
- Offset 151
Group 74's chunks may be sparse. To map chunk 23 to its physical
location, each group has a 256-bit bitmask indicating which
chunks are present.
Use its physical location to get its `chunkOffset`. That allows you
to get to the `ChunkInfo` struct.
From there, do the same thing to get the node data.
This design should also let us do some interesting things down the road,
like efficiently compressing each chunk using something like delta
encoding, zigzag encoding and bit packing. Then, to avoid paying a
decompression cost, we'd likely give each worker a cache of uncompressed
chunks.
* cmake build
* tidy up
* tweak
* tweak
* derp
* mac/windows build
* fix build?
I don't understand why these can't be passed as a copy in the Windows
and Mac builds. Whatever, try passing a reference.
* fix --store
I think nested containers may not be wired up quite correctly.
Instead, manage the char* buffers directly, rather than as
`std::vector<char>`
I'll fixup the other aspects (attributing libpopcnt, picking
Sorted vs BinarySearch on the fly) later
* attribution for libpopcnt
* simplify read_pbf
All read phases use the same striding-over-batches-of-blocks approach.
This required changing how progress is reported, as block IDs are no
longer globally montonically increasing.
Rather than thread the state into ReadBlock, I just adopted 2 atomic
counters for the whole class -- the progress reporter already assumes
that it's the only thing dumping to stdout, so the purity of avoiding
class-global doesn't buy us anything.
* clear allocatedMemory
* use scale factor 16, not 8
D'oh, if you get a full group where each chunk is full, you need to be
able to express a value _ever so slightly_ larger than 65,536.
North America and Europe have examples of this.
Use a scale factor of 16, not 8. This'll mean some chunks have up to 15
wasted bytes, but it's not a huge deal. (And I have some thoughts on how
to claw it back.)
* comment out debug stats
* windows build
* derp
* use SortedNodeStore if PBFs have Sort.Type_then_ID
* add --compress-nodes
If the user passes `--compress-nodes`, we use [streamvbyte](https://github.com/lemire/streamvbyte)
to compress chunks of nodes in memory.
The impact on read time is not much:
- GB with `--compress-nodes`: 1m42s
- without: 1m35s
But the impact on memory is worthwhile, even across very different
extracts:
North America - 5.52 bytes/node vs 8.48 bytes/node
169482 groups, 18364343 chunks, 1757589784 nodes, needed 9706167278 bytes
169482 groups, 18364343 chunks, 1757589784 nodes, needed 14916095182 bytes
Great Britain - 5.97 bytes/node vs 9.25 bytes/node
163074 groups, 4871807 chunks, 184655287 nodes, needed 1104024510 bytes
163074 groups, 4871807 chunks, 184655287 nodes, needed 1708093150 bytes
Nova Scota - 5.81 bytes/node vs 8.7 bytes/node
26777 groups, 157927 chunks, 12104733 nodes, needed 70337950 bytes
26777 groups, 157927 chunks, 12104733 nodes, needed 105367598 bytes
Monaco - 10.43 bytes/node vs 13.52 bytes/node
1196 groups, 2449 chunks, 30477 nodes, needed 318114 bytes
1196 groups, 2449 chunks, 30477 nodes, needed 412258 bytes
* build
* build
* remove __restrict__ to satisfy windows build
* remove debug print, small memory optimization
* use an arena for small groups
* omit needless words
* better short-circuiting for Type-then-ID PBFs
Track metadata about which blocks have nodes, ways and relations.
By default, we assume any block may contain nodes, ways or relations.
If the PBF supports Type-then-ID PBFs, do a binary search to find the first
blocks with ways and relations.
This means ReadPhase::Nodes can stop without scanning ways/relations.
In addition to avoiding needless work, it makes it easier to assign
each worker a balanced amount of work -- now each worker has only
blocks with nodes, which are about the same effort computationally.
It also makes ReadPhase::ScanRelations faster, as it scans exactly the
blocks with relations, skipping the blocks with ways.
Similarly, ReadPhase::Ways is a bit faster, as it doesn't have to read
the blocks with relations.
For North America, this reduces the time to complete the Nodes and
RelationsScan phase from 2m30s to 1m20s.
For GB, it reduces the time from 22s to 9s.
* ReadPhase::Relations - more parallelism
When processing relations for small extracts, there are often fewer
blocks than cores.
Instead, divide the work more granularly, assigning each of the N
threads 1/Nth of the block to process.
This saves 4-5 seconds (which is cumulatively ~20% of runtime) for
the Canadian province of Nova Scotia.
* extract WayStore, BinarySearchWayStore
* stub in SortedWayStore
...it just throws a lot of exceptions at the moment.
* put SortedNodeStore in a namespace
Also replace some `#define`s with `const`s.
I'm likely going to reuse some names in SortedWayStore, so namespacing
to avoid conflicts.
* don't use SortedWayStore if LocationsOnWays present
* stub in insertLatpLons/insertNodes
* change at() to return a non mmap vector
SortedWayStore won't create mmaped vectors, so we need to return the
lowest common denominator.
This pessimizes performance of BinarySearchWayStore, since it'll have
to allocate vectors on demand.
Longer term: it might be better to return an iterator that hides the heavy
lifting.
* begin drawing the rest of the owl
* flesh out types
* add unit test framework
* naive encoding of ways
Checkpointing since I have something that works.
Future optimizations:
- when all high ints are the same, don't encode them
- compression
* more efficient if high ints are all the same
* extract mmap_allocator.cpp
This is needed to unit test the way store without dragging
in osm_store.
* progress on publishGroup
checkpointing, going to extract a populateMask(...) function
* add populateMask function
* finish publishGroup
* SortedWayStore: implement at
* pass node store into SortedWayStore
* fix alignment
* better logs
* way stores should throw std::out_of_range
This is part of the contract, client code will catch it and reject
relations that have missing ways.
* sortednodestore: throw std::out_of_range
* support way compression
* remove dead code, robust against empty ways
* implement clear()
* maybe fix windows build?
very unclear why this is needed, but we seem to be getting C2131 on this
line.
* don't use variable-length arrays on stack
Workaround for MSVC
* avoid more variable-length arrays
* make the other vectors as thread-local
* --no-compress-ways, --no-compress-nodes
* Rely on packaged rapidjson dependency
* Add rapidjson to cmake
* Add -pthread option to LIB flags variable in Makefile.
* Allow environment setting of CXXFLAGS.
* Avoid git during build
* Github CI build using ubuntu 18.04
Co-authored-by: Felix Delattre <felix@delattre.de>
- Define inputs for Github Action
- Add description into README
- If '--config' or '--process' are not being set, use configuration of
OpenMapTiles by default
Richard Fairhurst