Opportunities for multithreading

[yakra]

Task	Priority	Comments
Sorting waypoints in Quadtree	Done 250a2fa	Combine sorting colocated point lists. See #89.
Writing near-miss point merged wpt files	Done
Processing traveler list files	Done
Concurrency detection	(bottom) 1.1s	Potential for data races makes this impracticable.
Processing waypoint labels and checking for unconnected chopped routes	Done b07f73b	TravelMapping#397
Concurrency augments	Done
Computing stats	Done	Had less luck first time round: Spent all its time hung up inside one mutex with one map always creating and throwing std::out_of_range. Was written a little too much like the original Python. :)
per-traveler stats log entries	Done
Writing traveler list logs	Done	Maybe fold the writing into the calculation... Only 0.2 s now. Done.
Writing stats csv files	Done 2dd3b28	~ 1/3 all active, 1/3 active+preview, 1/3 individual systems
unique names and vertices	Done 4d988b3	TravelMapping#285
Creating edges	(medium) 3.3s	Do #175 first! Need mutex, to: • check for duplicate edges (reorder code in 1st ctor). • add to adjacency lists Just one should be good, but see below...
Compressing collapsed edges	(low) ~1.3s	Need mutex for adding to and detaching from adjacency lists. • 1 for every vertex = 22,686,480 B • 1 for every quadtree node (faster) = 4,916,336 B • 1 for every quadtree node (slower) = 1,526,120 B • 1 for everything = 40 B. I can get away with this, right?
writing master graphs	Done 96be2a3	Combined into one function & written alongside subgraphs.
subgraphs	Done 4879245
Performing data checks	Done	Folded into Route::read_wpt to take advantage of idle CPU time while waiting for I/O.
Marking datacheck false positives	(high) 9.7s	Iterator validity, etc. Don't think parallel, just think concurrent -- see TravelMapping#379
database file	Done bc96425	Start one thread writing everything except for the graph info; generate graphs; join() the file-writing thread; append graph data to the file.

[yakra]

Multi-threaded subgraph writing is implemented, but there's room to improve parallelism.

There's a lot of "dead space" in the way processing is split up between each graph category. Some cores are idle while we wait for the last graphs in each category to finish, before we prepare for the graphs in the next category.
With only 2 multisystem graph sets, 2 cores are idle the entire 3.8s. And EUR-freeways probably finishes quite a bit before USA-national.

A better way is to first prep all categories' graphs, and load up the entire graph_vector first.
Then we can plow through the entire thing in one go, no gaps, no stalls.
Add graphs to graph_vector from slowest to fastest. Fill the bathtub up with baseballs before filling it up with marbles, n'at.

Task	Time (s)	Sets	Seconds Per set
Writing continent graphs.	17.4	6	2.90
Writing multisystem graphs.	4.2	2	2.10
Writing system data graphs.	4.6	4	1.15
Writing country graphs.	10.8	14	0.77
Writing area data graphs.	8.5	25	0.34
Writing multiregion graphs.	1.1	4	0.27
Writing regional data graphs.	10.9	342	0.03

[yakra]

^ Tackle TravelMapping#223 first.
this may alter where the area graphs sit in the speed hierarchy.

[yakra]

Task	Time (s)	Sets	Seconds Per set
Creating continent graphs.	17.3	6	2.88
Creating multisystem graphs.	4.3	2	2.15
Creating system data graphs.	4.5	4	1.1
Creating country graphs.	10.6	14	0.76
Creating multiregion graphs.	1.1	4	0.3
Creating area data graphs.	1.2	26	0.05
Creating regional data graphs.	11	329	0.03

[yakra]

Lab2 is able to take advantage of its greater number of cores, and outperforms lab1 in most multi-threaded tasks.
yakra@BiggaTomato:~/TravelMapping/devel/cpuscale/20200318$

sum=0
deltas=$( \
 for task in ReadWpt NmpSearch NmpMerged ReadList \
 ConcAug CompStats UserLog Subgraph; do
 vals=$( \
 for BOX in lab1 lab2; do
 ./taskscale.sh $BOX _insert $task | grep 'peak'
 done | sed 's~.*is \(.*\)s at.*~\1~'
 )
 eq=$(echo $vals | tr ' ' '-')
 echo -n "$eq="
 echo "scale=3; $eq" | bc
 done | cut -f2 -d'=' \
)
for d in $deltas; do sum=$sum+$d; done
echo "scale=3; $sum" | bc

All combined, lab2 is faster by 1.89s.
Lab1 wins overall because it's faster in the single-threaded bits.

---

TBD: How much total time is taken up by each machine:

• in all single-threaded tasks total?
• in all multi-threaded tasks total?

---

To find average time for a given single-threaded task on a given machine:
yakra@BiggaTomato:~/TravelMapping/devel/cpuscale/20200318/sulogs/cpp$

count=$(ls siteupdate_insert-lab2* | wc -l)
sum=0
for file in $(ls siteupdate_insert-lab2*); do
 sum=$sum+$( \
 delta=$( \
 tac $file | grep '^\[[0-9]\+\.[0-9]\]' \
 | grep -B 1 unique \
 | sed 's~^\[\([0-9]\+\.[0-9]\).*~\1~'
 )
 echo "scale=1; $(echo $delta | tr ' ' '-')" | bc \
 )
done
echo "scale=8; ($sum) / $count" | bc