Marking used one thread per reader, so input that was read serially,
which all goes to the first reader, was marked by a single thread.
Instead, use the readers' indexes to divide all the geometry into
ranges of about the same size at feature boundaries, and have each
thread take the next unmarked range until there are none left.
With 4 CPUs and input read by one reader, this makes marking about
3x faster.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01P2nBqZisxNQfmEmon3vE9v
encode_vertex() computed exactly the same thing as encode_quadkey(),
so there is no reason to have both. Give encode_quadkey() the branch-free
implementation, which also speeds up the default encode_index, and have
the shared node code call it directly. The unit test now compares it
against the old bit-at-a-time loop and checks that decode_quadkey()
reverses it.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01P2nBqZisxNQfmEmon3vE9v
Encode the shared nodes as quadkeys, as the comment on struct node
already said they were, with a branch-free bit interleave, so that
vertices that are near each other are near each other in the sorted list
too. Search the list with an inlined std::lower_bound instead of bsearch.
Size the Bloom filter by the number of nodes, at about 16 bits each and
at most 32MB, instead of always using 34MB, so that it can usually stay
in the cache, and set three bits for each node, chosen by a mixing hash,
within a single 64-bit word, so that each check still touches only one
cache line but has far fewer false positives than a single bit.
In the pass that marks the vertices with whether they are shared nodes,
this is about 1.7x faster with 70 thousand nodes and 1.9x faster with
3 million.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01P2nBqZisxNQfmEmon3vE9v
Points that clipping creates along a feature's edges, other than at the
existing vertices, and the vertices of tiny polygon placeholders, are
not vertices of the original geometry, so they are now marked as not
being shared nodes instead of being looked up in the global list of
shared nodes when they are simplified. This could only change the output
where a vertex of some other feature happens to fall exactly on one of
these new points, and in practice none of them ever turned out to be
shared nodes.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01P2nBqZisxNQfmEmon3vE9v
Geometry that was clipped to --clip-bounding-box while it was being
serialized can already have node states in its operation bytes, so the
unmasked comparison against VT_MOVETO and VT_LINETO failed to recognize
those vertices and lost track of where the following vertices began.
Also stop with an error instead of continuing if the operation is not
one that can appear in serialized geometry.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01P2nBqZisxNQfmEmon3vE9v
Vertices that are already going to be kept, because they begin a ring
or are on the tile boundary, can't be affected by whether they are also
global shared nodes, so skip looking them up. These are most of the
vertices that clipping creates, which don't know their node state.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01P2nBqZisxNQfmEmon3vE9v
With --no-simplification-of-shared-nodes, simplify_lines() used to offset
every vertex of every feature to world coordinates and check it against
the Bloom filter and the global sorted list of shared nodes, in every
tile at every zoom level.
Whether a vertex is a shared node depends only on its world coordinates,
so now it is found once, after the list of shared nodes has been made
and before the geometry is sorted, by a parallel pass over each reader's
geometry that marks each vertex in place, in the upper bits of its
serialized operation byte. Decoding puts that state into a new field of
draw (which still fits in 16 bytes), and it is carried through clipping,
the copies across the antimeridian at z0, and the geometry written for
the next zoom level. Polygon cleaning of coalesced features restores the
state of any output vertex with the same coordinates as an input vertex.
Vertices whose state is still unknown, because they were created by
clipping or polygon cleaning or came back from a prefilter, are still
looked up in the global list when they are simplified, so the output is
unchanged.
Co-Authored-By: Claude Opus 5.5 <noreply@anthropic.com>
Claude-Session: https://claude.ai/code/session_01P2nBqZisxNQfmEmon3vE9v
Claude