concurrency detection memory leak

[yakra]

Valgrind reports:

• definitely lost: 24 B (clang) / 16 B (g++) in 1 block, allocated here.
  An orphaned concurrency list is not attached to any HighwaySegment. It's created, partially populated, and then its pointer is overwritten during concurrency detection.
• indirectly lost: 144 B in 6 blocks (i.e., 6 std::_List_nodes)
  • 24 B in 1 block, allocated here, the 1st route when the concurrency is first detected.
  • 24 B in 1 block, allocated here, the 2nd route when the concurrency is first detected.
  • 96 B in 4 blocks, allocated here, when the concurrency is augmented with more routes afterward.
• My first guess was our old pal outside the Fort Pitt Tunnel, with 6 concurrent routes (I-376, US19, US22, US30, SB US19Trk, NB US19Trk).
• But nope! The missing object was first assigned to POL E67 29(S8) 27(A1). Same deal here with a wrong-way self-multiplex -- the ramps for the desired E67/S8 movements aren't built yet, so traffic continues straight on through, U-turns at the next interchange, and doubles back, leaving via the other road. There are 7 concurrent segments here, processed in system>route order:
  1. POL E67 29(S8) 27(A1) The first list constructed gets built out to 6 of 7 routes, then its pointer is overwritten.
  2. POL E67 27(A1) 26(A1)
  3. POL E75 26(A1) 27(A1)
  4. POL A1 26 27
  5. POL S8 26(A1) 27(A1)
  6. POL S8 27(A1) 29
  7. POL DK74 A1_S A1_N
• Why does POL have a memory leak but not PA? Could be any of a number of different factors at play here. This will take a long walk thru the code like in Concurrent segment detection #135...

[yakra]

colocation lists

N	S
pol.a001@26	pol.a001@27
pol.dk074@A1_N	pol.dk074@A1_S
pol.e67@26(A1)	pol.e67@27(A1)
pol.e67@29(S8)	pol.e75@27(A1)
pol.e75@26(A1)	pol.s008@27(A1)
pol.s008@26(A1)
pol.s008@29

[yakra]

for (HighwaySystem* h : HighwaySystem::syslist)					// h = eure
{cout << '.' << flush;								// 
 for (Route* r : h->route_list)							// r = pol.e67
 for (HighwaySegment* s : r->segment_list)					// s = [POL E67 29(S8) 27(A1)]
 if (s->waypoint1->colocated && s->waypoint2->colocated)			// both colocated; proceed
 for ( Waypoint* w1 : *(s->waypoint1->colocated) )				// w1 = pol.a001@26
 if (w1->route != r)							// diff route; proceed
 for ( Waypoint* w2 : *(s->waypoint2->colocated) )				// w2 = pol.a001@27
 if (w1->route == w2->route)						// same route; proceed
 {HighwaySegment* other = w1->route->find_segment_by_waypoints(w1,w2);	// other = [POL A1 26 27]
 if (other)								// proceed
 if (!s->concurrent)							// First pass; s->concurrent still 0; proceed
 {s->concurrent = new list<HighwaySegment*>;				// new list
 other->concurrent = s->concurrent;					// 2 pointers to the same list
 s->concurrent->push_back(s);						// E67 S & A1 get E67 S
 s->concurrent->push_back(other);					// E67 S & A1 get A1
 //concurrencyfile << "New concurrency [" etc.				// 
 }									// 
 else //...
 }

E67 S	E67 N	E75	A1	S8 S	S8 N	DK74
E67 S	0	0	E67 S	0	0	0
A1			A1

[yakra]

 				// w1 = pol.a001@26
 for ( Waypoint* w2 : *(s->waypoint2->colocated) )				// w2 = pol.dk074@A1_S, etc.
 if (w1->route == w2->route)						// False for all remaining

E67 S	E67 N	E75	A1	S8 S	S8 N	DK74
E67 S	0	0	E67 S	0	0	0
A1			A1

[yakra]

 					// s = [POL E67 29(S8) 27(A1)]
 if (s->waypoint1->colocated && s->waypoint2->colocated)			// both colocated; proceed
 for ( Waypoint* w1 : *(s->waypoint1->colocated) )				// w1 = pol.dk074@A1_N
 if (w1->route != r)							// diff route; proceed
 for ( Waypoint* w2 : *(s->waypoint2->colocated) )				// w2 = pol.dk074@A1_S
 if (w1->route == w2->route)						// same route; proceed
 {HighwaySegment* other = w1->route->find_segment_by_waypoints(w1,w2);	// other = [POL DK74 A1_S A1_N]
 if (other)								// proceed
 if (!s->concurrent)							// assigned a value in prev pass; skip
	 //...									//
 else if (!contains(*s->concurrent, other))				// not in list; proceed
 {other->concurrent = s->concurrent;					// add list to DK74
 s->concurrent->push_back(other);					// add DK74 to list
 //concurrencyfile << "Extended concurrency " etc.			// 
 }
 }

E67 S	E67 N	E75	A1	S8 S	S8 N	DK74
E67 S	0	0	E67 S	0	0	E67 S
A1			A1			A1
DK74			DK74			DK74

[yakra]

 										// s = [POL E67 29(S8) 27(A1)]
 for ( Waypoint* w1 : *(s->waypoint1->colocated) )				// w1 = pol.e67@26(A1), pol.e67@29(S8)
 if (w1->route != r)							// same route; skip

E67 S	E67 N	E75	A1	S8 S	S8 N	DK74
E67 S	0	0	E67 S	0	0	E67 S
A1			A1			A1
DK74			DK74			DK74

OK, I think I see where this is going...
We probably want to proceed if (w1 != s->waypoint1),
and detect POL E67 27(A1) 26(A1) when testing POL E67 29(S8) 27(A1).
I'll continue down this rabbit hole in the morning & make sure I'm on the right track.

[yakra]

We continue on with POL E67 29(S8) 27(A1)...
w1 = pol.e75@26(A1); w2 = pol.e75@27(A1); add list to E75; add E75 to list.
w1 = pol.s008@26(A1); w2 = pol.s008@27(A1); add list to S8 S; add S8 S to list.
w1 = pol.s008@29; w2 = pol.s008@27(A1); add list to S8 N; add S8 N to list.

E67 S	E67 N	E75	A1	S8 S	S8 N	DK74
E67 S	0	E67 S	E67 S	E67 S	E67 S	E67 S
A1		A1	A1	A1	A1	A1
DK74		DK74	DK74	DK74	DK74	DK74
E75		E75	E75	E75	E75	E75
S8 S		S8 S	S8 S	S8 S	S8 S	S8 S
S8 N		S8 N	S8 N	S8 N	S8 N	S8 N

We're done checking POL E67 29(S8) 27(A1).
Time to check POL E67 27(A1) 26(A1)...

---

Why is PA different?

The first route processed is I-376, not the self-concurrent one. All other routes pass the if (w1->route != r) test. Once we're done processing I-376, the list is fully built out, with all segments pointing to it. When we move on past I-376 to process the rest of the routes, there's nothing left to do.

[yakra]

 for (HighwaySegment* s : r->segment_list)					// s = [POL E67 27(A1) 26(A1)]
 if (s->waypoint1->colocated && s->waypoint2->colocated)			// both colocated; proceed
 for ( Waypoint* w1 : *(s->waypoint1->colocated) )				// w1 = pol.a001@27
 if (w1->route != r)							// diff route; proceed
 for ( Waypoint* w2 : *(s->waypoint2->colocated) )				// w2 = pol.a001@26
 if (w1->route == w2->route)						// same route; proceed
 {HighwaySegment* other = w1->route->find_segment_by_waypoints(w1,w2);	// other = [POL A1 26 27]
 if (other)								// proceed
 if (!s->concurrent)							// s->concurrent still 0; proceed
 {s->concurrent = new list<HighwaySegment*>;				// a 2nd list is created
 other->concurrent = s->concurrent;					// [POL A1 26 27]'s list overwritten
 s->concurrent->push_back(s);						// E67 N & A1 get E67 N
 s->concurrent->push_back(other);					// E67 N & A1 get A1
 //concurrencyfile << "New concurrency [" etc.				// 
 }									// 
 else //...								// 
 }

E67 S	E67 N	E75	A1	S8 S	S8 N	DK74
E67 S	E67 N	E67 S	E67 N	E67 S	E67 S	E67 S
A1	A1	A1	A1	A1	A1	A1
DK74		DK74		DK74	DK74	DK74
E75		E75		E75	E75	E75
S8 S		S8 S		S8 S	S8 S	S8 S
S8 N		S8 N		S8 N	S8 N	S8 N

[yakra]

										// s = [POL E67 27(A1) 26(A1)]
 for ( Waypoint* w1 : *(s->waypoint1->colocated) )				// w1 = pol.dk074@A1_S
 if (w1->route != r)							// diff route; proceed
 for ( Waypoint* w2 : *(s->waypoint2->colocated) )				// w2 = pol.dk074@A1_N
 if (w1->route == w2->route)						// same route; proceed
 {HighwaySegment* other = w1->route->find_segment_by_waypoints(w1,w2);	// other = [POL DK74 A1_S A1_N]
 if (other)								// proceed
 if (!s->concurrent)							// list exists since we found A1; skip
 //...									// 
 else if (!contains(*s->concurrent, other))				// not in list; proceed
 {other->concurrent = s->concurrent;					// [POL DK74 A1_S A1_N]'s list overwritten
 s->concurrent->push_back(other);					// add DK74 to list
 //concurrencyfile << "Extended concurrency " etc.			// 
 }
 }

E67 S	E67 N	E75	A1	S8 S	S8 N	DK74
E67 S	E67 N	E67 S	E67 N	E67 S	E67 S	E67 N
A1	A1	A1	A1	A1	A1	A1
DK74	DK74	DK74	DK74	DK74	DK74	DK74
E75		E75		E75	E75
S8 S		S8 S		S8 S	S8 S
S8 N		S8 N		S8 N	S8 N

[yakra]

										// s = [POL E67 27(A1) 26(A1)]
 for ( Waypoint* w1 : *(s->waypoint1->colocated) )				// w1 = pol.e67@27(A1)
 if (w1->route != r)							// same route; skip

We continue on with [POL E67 27(A1) 26(A1)] as above and as above...
w1 = pol.e75@27(A1); w2 = pol.e75@26(A1); add list to overwrite list in E75; add E75 to list.
w1 = pol.s008@27(A1); w2 = pol.s008@26(A1); add list to overwrite list in S8 S; add S8 S to list.
w1 = pol.s008@27(A1); w2 = pol.s008@29; add list to overwrite list in S8 N; add S8 N to list.

E67 S	E67 N	E75	A1	S8 S	S8 N	DK74
E67 S	E67 N	E67 N	E67 N	E67 N	E67 N	E67 N
A1	A1	A1	A1	A1	A1	A1
DK74	DK74	DK74	DK74	DK74	DK74	DK74
E75	E75	E75	E75	E75	E75	E75
S8 S	S8 S	S8 S	S8 S	S8 S	S8 S	S8 S
S8 N	S8 N	S8 N	S8 N	S8 N	S8 N	S8 N

At this point the 7 concurrent segments share 2 concurrency lists, each listing 6 segments:

• The new one (in italics), containing everything but E67 S, attached to everything but E67 S.
• The old one (not italics), containing everything but E67 N, attached to only E67 S.

We're done checking POL E67.
Time to check POL E75...

[yakra]

The A1 & DK74 segments are already contained in POL E75 26(A1) 27(A1)'s concurrency list; nothing happens there. Moving on...

 for (Route* r : h->route_list)							// r = pol.e75
 for (HighwaySegment* s : r->segment_list)					// s = [POL E75 26(A1) 27(A1)]
 if (s->waypoint1->colocated && s->waypoint2->colocated)			// both colocated; proceed
 for ( Waypoint* w1 : *(s->waypoint1->colocated) )				// w1 = pol.e67@26(A1)
 if (w1->route != r)							// diff route; proceed
 for ( Waypoint* w2 : *(s->waypoint2->colocated) )				// w2 = pol.e67@27(A1)
 if (w1->route == w2->route)						// same route; proceed
 {HighwaySegment* other = w1->route->find_segment_by_waypoints(w1,w2);	// other = [POL E67 27(A1) 26(A1)]
 if (other)								// proceed
 if (!s->concurrent)							// list exists; skip
 //...									// 
 else if (!contains(*s->concurrent, other))				// not in the new list yet; proceed
 {other->concurrent = s->concurrent;					// [POL E67 27(A1) 26(A1)]'s list overwritten
 s->concurrent->push_back(other);					// add E67 S to list
 //concurrencyfile << "Extended concurrency " etc.			// 
 }
 }

And there's the memory leak. The last pointer to the original concurrency list is overwritten, making it inaccessible.
Python doesn't care about this, because garbage collection.
In C++, this should clearly be fixed.

E67 S	E67 N	E75	A1	S8 S	S8 N	DK74
E67 N	E67 N	E67 N	E67 N	E67 N	E67 N	E67 N
A1	A1	A1	A1	A1	A1	A1
DK74	DK74	DK74	DK74	DK74	DK74	DK74
E75	E75	E75	E75	E75	E75	E75
S8 S	S8 S	S8 S	S8 S	S8 S	S8 S	S8 S
S8 N	S8 N	S8 N	S8 N	S8 N	S8 N	S8 N
E67 S	E67 S	E67 S	E67 S	E67 S	E67 S	E67 S

All 7 segments point to the new list, which has all 7 segments on it.
The 2nd segment of E67 is counterintuitively at the end of the list, but it makes sense -- with E67 first in line for processing, it doesn't get picked up as concurrent with itself. The 2nd E67 segment isn't added to the list until we process another route it can be concurrent with.
This is borne out in the HighwayGraph structure: load up the graph in the HDX and you'll see E67,A1,DK74,E75,S8,S8,E67 as the edge name.

---

The proposal this time is a bit different from that in #137; code should be leaner & cleaner, smaller diff overall, and should probably run a tiny bit faster.
The results are the same, though -- self-concurrencies will be detected even for cases like UT190 where there's no other designation in the mix. As it should be, IMO; this keeps it consistent with how concurrencies are done in all other scenarios.
Might be time to dust off https://forum.travelmapping.net/index.php?topic=2805
Making this change would beg for conforming changes in Python.

[yakra]

Graph Generation

DataProcessing/siteupdate/cplusplus/classes/GraphGeneration/HGEdge.cpp

Lines 23 to 34 in 4d988b3

	// checks for the very unusual cases where an edge ends up
	// in the system as itself and its "reverse"
	for (HGEdge *e : vertex1->incident_s_edges)
	if (e->vertex1 == vertex2 && e->vertex2 == vertex1)
	{ delete this;
	return;
	}
	for (HGEdge *e : vertex2->incident_s_edges)
	if (e->vertex1 == vertex2 && e->vertex2 == vertex1)
	{ delete this;
	return;
	}

DataProcessing/siteupdate/python-teresco/siteupdate.py

Lines 1812 to 1819 in 3baef90

	# checks for the very unusual cases where an edge ends up
	# in the system as itself and its "reverse"
	for e in self.vertex1.incident_s_edges:
	if e.vertex1 == self.vertex2 and e.vertex2 == self.vertex1:
	return
	for e in self.vertex2.incident_s_edges:
	if e.vertex1 == self.vertex2 and e.vertex2 == self.vertex1:
	return

The graph generation process has changed since this check was first implemented. It's not as necessary as it once was.
It was originally needed for US19TrkPit & pals, and probably written in response to exactly that if the timing of the original commit and Jim's post here are any indication.
Before #136, segments with n>2 concurrent routes would have n-1 concurrency lists between them. In cases with self-concurrent routes, some of these lists would be incomplete. I explored the mechanics behind this in #135. The final concurrency lists for US19TrkPit & pals are in the 2nd table in this post.
Back then, the HighwayGraph constructor would visit each segment in turn, check whether it's marked as visited, and if not, mark it for graph edge construction then mark all concurrent segments visited.
I-376 got visited first, with its incomplete concurrency list, and the southern segment of US19TrkPit was not marked visited.
Later on, US19TrkPit itself was visited, and marked for graph construction. Hence the need for the graph constructor to check for "reversed" edges.
Now, since #135, all segments share the same concurrency list, fully populated. An edge is constructed for I-376, and we don't go on & attempt to construct another one for PA US19TrkPit I-376(69B)_S I-376(69A).

This check is still necessary for cases like UT190 when a route is concurrent with itself but no other routes.
Neither UT UT190 UT190_A UT190_B nor UT UT190 UT190_C UT190_D get marked concurrent at all.
After making the fix for this issue, this code can go away.

[yakra]

People who've marked both segments will see:

• a decrease in region/system mileage
• while mileage on the route stays the same

Based8.log:
3,4c3,4
< Overall in active systems: 61034.46 of 1145620.61 mi (5.33%)
< Overall in active+preview systems: 62409.09 of 1548324.46 mi (4.03%)
---
> Overall in active systems: 61034.13 of 1145620.28 mi (5.33%)
> Overall in active+preview systems: 62408.76 of 1548324.13 mi (4.03%)
45c45
< UT: 1080.46 of 6025.71 mi (17.93%), 1080.46 of 6025.71 mi (17.93%)
---
> UT: 1080.12 of 6025.38 mi (17.93%), 1080.12 of 6025.38 mi (17.93%)
3735c3735
< System usaut (active) overall: 303.15 of 3704.01 mi (8.18%)
---
> System usaut (active) overall: 302.82 of 3703.68 mi (8.18%)

People who've marked only 1 segment will see:

• an increase in on-route mileage
• while region/system = same mileage traveled / smaller total

bobcobb.log:
18,19c18,19
< Overall in active systems: 68285.42 of 1145620.61 mi (5.96%)
< Overall in active+preview systems: 70729.67 of 1548324.46 mi (4.57%)
---
> Overall in active systems: 68285.42 of 1145620.28 mi (5.96%)
> Overall in active+preview systems: 70729.67 of 1548324.13 mi (4.57%)
66c66
< UT: 2084.86 of 6025.71 mi (34.60%), 2084.86 of 6025.71 mi (34.60%)
---
> UT: 2084.86 of 6025.38 mi (34.60%), 2084.86 of 6025.38 mi (34.60%)
3536c3536
< System usaut (active) overall: 378.56 of 3704.01 mi (10.22%)
---
> System usaut (active) overall: 378.56 of 3703.68 mi (10.22%)
3598c3598
< UT190: 16.44 of 19.80 mi (83.03%)
---
> UT190: 16.77 of 19.80 mi (84.72%)