list_entry_name & route_names_and_systems

[yakra]

HGEdge::route_names_and_systems has a lot of redundancy, duplicating list_entry_name strings across many segments.

• Option 1:
  Save list_entry_names with Routes; just store pointers here.
  • Save a boatload of RAM.
  • Save time in initial edge construction.
  • Save time in deep list copies in collapse constructor.
  • Leverage stored strings to save time in other areas, e.g. canonical_waypoint_name.
• Option 2
  Investigate deleting route_names_and_systems completely.
  • Save even more RAM.
  • Save even more time in both edge constructors.
  • Effects on speed?
    • HighwayGraph::matching_vertices_and_edges
    • HGEdge::write_label

[yakra]

All that clunky system_match stuff in HighwayGraph::matching_vertices_and_edges can be replaced with a new system_match function.
Refer to HGEdge::route_names_and_systems near-term / interim. Or not.
Refer to HighwaySegment:colocated long-term. Whatever's clever.

[yakra]

RAM

C++:

• Takes up 94,492,212 B as currently implemented, as a list
  (clang/BSD. Other builds (e.g. clang/Ubuntu) can take up more space.)
• Would be 77,170,740 B if implemented as a vector
• Would be 64,859,975 B if vectors/strings magically had no excess capacity

Python:

• Takes up 144,911,426 B.
• Sure, in theory string interning saves us some space. We're storing route name strings once per route; each segment only contains a reference. However...
• That's more than made up for by increased overhead in Python's type system every step of the way -- list containers, list elements, tuples, string containers...

Speed

C++:

• HighwayGraph::matching_vertices_and_edges ever so slightly faster thru the noise.
• HGEdge::write_label slightly slower using a fairly straightforward adaptation of existing code.
  • Any of several tweaks may help improve speed. But until then...
• This is offset (+a tiny bit more) by speed increases when creating & compressing edges. Time savings appear most visible on...
  • Ubuntu
  • lower memory bandwidth machines

Python (lab1):

• HighwayGraph.matching_vertices_and_edges increases subgraph time by ~1.5%, 65.2 s -> 66.17 s.
• HGEdge.write_label increases subgraph time by ~6.8%, ~4.44 s.
• Only ~0.81s saved during edge construction/compression.
• A clear speed disadvantage.

To build or not to build?

• C++: Faster. Saves RAM. Win/win. Build.
• Python: Meh. What do we value more?
  • Build: Saving 138 MB RAM while taking 4.63 s longer
  • Build: Saving more RAM & code brevity when EduTools#156 gets underway
  • No-build: Saving 4.63 s while using 138 MB more RAM
  • No-build: Not cluttering up the commit history with changes that don't produce a clear benefit

[yakra]

Dropping this here so I can go ahead and delete the rns_size branch on BiggaTomato (012533125da1046f3962410023bc864e62ad493c):

HGEdge.h
std::vector<std::pair<std::string, HighwaySystem*>> route_names_and_systems; //instead of std::list

graph_generation.cpp
added before cout << et.et() << "Clearing HighwayGraph contents from memory." << endl;

unordered_set<string> PyStr;
unordered_set<HGEdge*> edges;
for (HGVertex* v : graph_data.vertices)
{	for (HGEdge* e : v->incident_s_edges) edges.insert(e);
	for (HGEdge* e : v->incident_c_edges) edges.insert(e);
	for (HGEdge* e : v->incident_t_edges) edges.insert(e);
}
size_t VecSize = 0;
size_t VecCap = 0;
size_t ListSize = 0;
size_t ListCap = 0;
size_t Python = 0;
for (HGEdge* e : edges)
{	// container itself
	VecSize += 24;
	VecCap += 24;
	ListSize += 24;
	ListCap += 24;
	Python += 64;
	// elements
	for (std::pair<std::string, HighwaySystem*>& ns : e->route_names_and_systems)
	{	// pair<string, HighwaySystem*>
		VecSize += 32;
		VecCap += 32;
		ListSize += 32 + 16;
		ListCap += 32 + 16;
		Python += 64 + 8;
		// string
		VecSize += 1 + ns.first.size();
		VecCap += 1 + ns.first.capacity();
		ListSize += 1 + ns.first.size();
		ListCap += 1 + ns.first.capacity();
		PyStr.insert(ns.first);
	}
	VecCap += 32*(e->route_names_and_systems.capacity() - e->route_names_and_systems.size());
}
for (const string& s : PyStr) Python += s.size() + 49;
cout << "route_names_and_systems:" << endl;
cout << "VecSize " << VecSize << endl;
cout << "VecCap " << VecCap << endl;
cout << "ListSize " << ListSize << endl;
cout << "ListCap " << ListCap << endl;
cout << "Python " << Python << endl;

IIRC this overwrote an earlier version that estimated the size of stuff implemented as a std::list, but that should be easy enough to recreate should I ever want to.