HIDDEN_TERMINUS: unhide

[yakra]

When encountering a HIDDEN_TERMINUS, strip the leading + and make the point visible.

Python: I should be OK to continue doing this datacheck along with the others after graph gen.

[yakra]

related: #91

[yakra]

On second thought... Datacheck errors can get lost in the noise and go unaddressed for a long time. If these points remain hidden, someone might notice a hidden endpoint in the HB, and report the error in the forum.

[yakra]

On the 3rd hand, unhiding these could prevent ERROR: segment name mismatch in HGEdge collapse constructor. Setting the bool to 0 (#582) and keeping the leading + could allow both this & keeping a hidden endpoint in the HB as noted above.

[yakra]

As it stands now, flipping the Waypoint::is_hidden bool immediately when HIDDEN_TERMINUS is detected would mess up VISIBLE_HIDDEN_COLOC detection later on.

VISIBLE_HIDDEN_COLOC detection could be moved into route_integrity (probably a good idea anyway because multithreading).

Heartburn - duplicated code...

• HIDDEN_TERMINUS checks will still need to exist in Route::read_wpt, in order to make VISIBLE_DISTANCE work.
• Duplicated w->colocated && w == w->colocated->front() check and iterating through colocations lists, with WaypointQuadtree::graph_points. Sure, this is already duplicated within graph_points now, but that can be rewritten to remove this redundancy and retain all present functionality.

Nonetheless, this is probably still more efficient than waiting until the compression stage and searching for termini there, which would involve analyzing way more points and iterating through their colocation lists until a terminus is found.

---

On the 4th hand, becoming even more reliant on the is_hidden bool (vs. a function) could get in the way of getting sizeof(Waypoint) down to 96 and being able to fit 2 Waypoints in 3 cache lines, provided I find some way of getting rid of Waypoint::point_num too (edit: which is easy). On the 5th hand, how much time would that save? Most routines iterating & accessing Waypoints are already plenty fast.

Which is better? In any case, all this stuff is pretty low priority for now.

[yakra]

On the 6th hand, some theoretical changes to the HGEdge class would mean storing Waypoint::vertex not as a full pointer, but as a 32-bit index into an array. This means only Waypoint::is_hidden nudges us above an 8-byte alignment boundary. This begs for its removal if keeping a compact sizeof(Waypoint) is a priority. On the 7th hand, losing Waypoint::point_num & effectively replacing it with the 32-bit vertex array index means we're down 8 bytes (for the old HGVertex*) and still have room for the bool.

[yakra]

Yecch. OK, this issue kinda got to be about 2 things...

1. Whether to keep is_hidden at all, when optimizing for object size. (Those mumblings were probably better suited for #582, but anyway.) My current thinking is, Waypoint will eventually have some unused space due to alignment requirements, so we may as well keep it around.
2. Whether and how to unhide hidden termini in the graph data. Definitely should do so, to prevent segment name mismatch errors. Some info and a couple early & outdated ideas are here, though I'd like to keep that issue about what the title says. So I'll yammer on about how to unhide them here.

The segment name mismatch error can only occur at colocated points, never singleton. This is because it requires 2 things:

• a vertex with 2 incident edges, and
• a HIDDEN_TERMINUS error at some underlying waypoint.

For a terminus to have 2 incident edges, either

• multiple routes end at the same point, or
• one route ends while another continues.

Both of which require colocated points. A singleton terminus means no other route to end at, means only 1 incident edge.

[yakra]

How to do it

The goal is to set HGVertex::visibility = 2 and avoid collapsing its incident edges. Most of the time, that's already been done (via a colocated visible point, or <> 2 edges). Short-circuit evaluation makes the hidden terminus check rarely necessary.

There are several alternatives to consider.

• Use a function or lambda, as described in #589. Check whether a hidden point is at the beginning or end of its route's points array.
• Or, since we'll have empty space in Waypoint to play around with, use a new bool Waypoint::hidden_terminus. This can be flagged on those rare occasions HIDDEN_TERMINUS is actually detected. Pro: Cut down on pointer-chasing, dereferencing, comparisons & branching. Con: Gotta initialize all 1.3M* waypoints to 0.

These 2 approaches can each be done in 2 places:

• Edge compression, as suggested in #589. Con: Check whether 221649* waypoints are colocated, then re-iterate through colocation lists we've already iterated through. We'd need to keep a Waypoint* around, forcing a no-build on some pointer-chasing optimizations. Pro: Only done for vertices with 2 edges. After confirming colocation, we only check for hidden termini 38009* times.
• Vertex construction Con: Done for vertices with <> 2 edges. The hidden terminus check kicks in 85828* times. Pro: Simpler, cleaner code; no need for a new function or lambda. We're already iterating thru a colocated list; just add 1 or 2 more conditions to the if.

Or, the other alternative considered upthread & in #589,

• Just zero out is_hidden after it's used in route_integrity. Pro: No extra steps during graph generation; everything proceeds normally. Con: Extra steps during RteInt to check 98834* endpoints, duplicating read_wpt (start points can be safey removed). After RteInt, this breaks is_hidden's traditional purpose of finding out whether a waypoint is, on its own, hidden. If we want to add more functionality using this in the future, that could complicate things. May run counter to another developer's expectations.

*Numbers represent HighwayData @ 2decc64. Not the most recent commit, but it's what I've been runnign tests on.

Of these alternatives, probably pick the most micro-optimizey one. :)

Before benchmarking:

• [x] yakra#265 phase 1
  • Should speed up vertex construction, making it easier to spot performance differences.
  • We'll be able to break or return from the loop in vertex construction, even though it'll rarely happen in practice.

[yakra]

A few more thoughts on bool Waypoint::hidden_terminus...

Propagating this bool's value to the front of the colocation list means...

• Not having to iterate if doing this during edge compression.
• We could get our pointer-chasing optimizations back if we copy the bool to some empty space in HGVertex, but by that point we may as well just be doing this...
• In vertex construction, we'd avoid extra conditions during iteration.

This gets tricky when we remember that when the datacheck is performed, the quadtree is not yet fully populated.

• If we were to update the bool as colocation lists are created and updated, we'd need to know the first point's hidden_terminus value before creating the colocation list. This means still needing to init all 1.3M points, so no gains here.
• Instead, we could just init the first point's value to 0 upon creating the coloc list (just 347011 initializations), then update the front point's value directly during route_integrity.
• But if we get as far as doing that, we may as well skip the bool altogether and go with the updating is_hidden option.

Hm. The Waypoint::hidden_terminus path is looking less & less attractive. Maybe the best option will be to go with whatever has the least overhead, and when we get to graph generation, allow short circuit evaluation to work its magic?