TMBitset<HGVertex*>

[yakra]

Carving this out into its own issue from the OP of #245.
Nota Bene: Code examples below use old nomenclature.
TMBitset::insert is deprecated in favor of TMBitset::add_index and TMBitset::add_value, so get hip.

---

TMBitset<HGVertex*> simplifies code. How about performance? Don't have to zero out individual bits at least.

• Create a clear() funtion, based on final selected alternative for |= operator
  Or not -- current thinking is, the TMBitsets will be destroyed by exiting scope.
• if (vertex_set.insert(vertex)) mvvec.push_back(vertex); here and here.
• Or, what if mvvec is nixed altogether? Is the slower iteration thru mvset (or whatever I end up calling it) outweighed by not doing all the vector's (re)allocations? Way more vertices = higher impact than nixing traveler_lists.
• Beware this line. (Full custom graphs only. Maybe cook up some more test cases?) Which is faster?

  if (!vertex_set(vw.first) && vw.second->system_match(g.systems))
  {	mvvec.push_back(vw.first);
  	vertex_set.insert(vw.first);
  }

  if (vw.second->system_match(g.systems) && vertex_set.insert(vw.first))
  	mvvec.push_back(vw.first);

• OTOH, better yet? This is a set! Think back to the earlier idea of unions & intersections. Avoid mucking about with iterating, checking, and adding.
  • For multiregion (et al) & multisystem graphs, |= everything together.
    • Get the first one via a copy ctor (thus taking care of single-region or single-system sets)
    • Iterate thru any remaining and |= them in.
  • For full custom graphs, use a new &= operator.
  • When a PlaceRadius is present? This may take a little more thought.
  • Potential stumbling block: regions contain std::pair<HGVertex*,Waypoint*>s.
    Remember how & why; look for ways around this.
    

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

    Line 10 in 387c99b

    if (!subgraph_contains(vw.first, threadnum) && vw.second->system_match(g->systems))

    
    Just this. Dates to subgraph bit field (cc9da66).
    With system membership done by TMBitset, no need to call system_match anymore.
    Can be safely removed.
  • There's unused space in HighwaySystem. Use a bool to track which systems are included in subgraphs, and only allocate for those. This can be done now to save space in the existing vector<HGVertex*>s.
    RAM use figures below don't reflect this; they were calculated before I thought of it.
  • How much RAM for a TMBitset for each region & system?
    54.22 M rg + 55.02 M sys = 109.24 M, as of 2decc64
    • How much is saved by not allocating for devel systems or regions where active_preview_mileage == 0?
      We're down to 37.36 M rg + 53.41 M sys = 90.76 M
    • Consider a TMBitset::shrink_to_fit() function (exact mechanics TBD).
      • What's the span, high-low+1, for each region/system? How much RAM can be saved?
        We're down to 45.43 M total, for a/p systems only.
        Actually a little more when accounting for potential extra units allocated due to alignment requirements, but this should top out at 8.5 K. Negligible. :)
        Compare this to 42.79 M for all vectors' capacity (including the paired Waypoint*s for regions) -- not bad!
        • What if vertices are created in a different order, e.g. sys->rte->pts?
          56.06 M. Weigh this against potential speed benefits noted in VISIBLE_HIDDEN_COLOC and graph_points #242's OP.
        • What if vertices are created in rg->rte->pts order?
      • Beware, lots of pitfalls
        • unit alignment, for memcmp and especially |=
        • []: Deprecate for squished applications (will vertex/edge applications just use addresses, and the () operator?) or store a new variable for orig start?
          Or maybe store a squished bool in the low bit of data, and throw? Would require replacing each use of data element with a function. PitA, probably not worth it.
        • !=: What about a larger set containing elements outside a smaller one?
          Could return 1 if start or len are unequal. OTOH, the big set could be unsquished, with everything before/after the small set's range =0.
          Could just have the definition if == mean, "if the start & len and contents are equal". ;)
          It's only used for comparing clinched_by when compressing edges -- even no-build would work as long as I don't resize clinched_by (how much would that save?) but probably a bad idea; defies developer expectations.
        • |=: Cope with different data ranges; start or len could differ. Find min start, max end & thus len, reallocate, memcpy existing data then free it, |= in the other stuff.
        • Don't forget to clear/set the end() bit as needed.
  • We won't know how many vertices there will be when regions & systems are created, so TMBitset will need:
    • a default ctor
    • an alloc function, a la TMArray
    • Member variables no longer const. Oh well.
  • There's no TMBitset::size() function, precisely because there's no efficient way to keep track of it while |=ing sets together. No big deal, as we need to iterate anyway to get the collapsed & traveled vertex counts. Just make a simple count a part of the process too.

[yakra]

ideas for TMBitset::shrink_to_fit():

void operator |= (const TMBitset<item,unit>& other)
{	if (start > other.start)
	{	item old_s = start;
		start = other.start;
		realloc(other, old_s);
	}
	else if (len != other.len)
		realloc(other, start);
	TMBImpl::bitwise_oreq(*this, other);
}

void realloc(const TMBitset<item,unit>& other, item old_s)
{	item a_end = old_s + len;
	item b_end = other.start + other.len;
	len = (a_end > b_end ? a_end : b_end) - (old_s < other.start ? old_s : b_start);

	size_t old_u = units;
	units = ceil(double(len+1)/ubits);

	unit* const old_d = data;
	data = (unit*)calloc(units, sizeof(unit));
	std::memcpy(data+old_s/ubits, old_d, old_u*ubits);
	free(old_d);
	//TODO: end() bit
}

[yakra]

RAM footprint:

HighwayGraph ctor, after creating vertices & before creating edges

	size_t vtmb_bytes_full = ceil(double(vertices.size()+1)/64)*8;
	size_t rtotal_all_full=0, rtotal_all_part=0, rtotal_a_p_full=0, rtotal_a_p_part=0;
	size_t stotal_all_full=0, stotal_all_part=0, stotal_a_p_full=0, stotal_a_p_part=0;
	size_t lo_size=0, hi_size=0, lo_cap=0, hi_cap=0;
	HGVertex *lo_v, *hi_v;

	std::cout << "(total)\tAllFull\t\tAPFull\t\tAllPart\t\tAPPart" << std::endl;
	std::cout << "(total)\t--------------------------------------------------------" << std::endl;

	// regions
	std::cout << "Region\tAllFull\tAPFull\tAllPart\tAPPart" << std::endl;
	for (Region& r : Region::allregions)
	{	std::cout << r.code << '\t' << std::flush;
		lo_v = r.vertices.empty() ? nullptr : r.vertices.front().first;
		hi_v = r.vertices.empty() ? nullptr : r.vertices.back().first;

		size_t vtmb_bytes_part = ceil(double(hi_v-lo_v+2)/64)*8;
		rtotal_all_full += vtmb_bytes_full;
		rtotal_all_part += vtmb_bytes_part;
		if (r.active_preview_mileage)
		{	rtotal_a_p_full += vtmb_bytes_full;
			rtotal_a_p_part += vtmb_bytes_part;
		}

		std::cout << vtmb_bytes_full << '\t'
			  << (r.active_preview_mileage ? vtmb_bytes_full : 0) /*APFull*/ << '\t'
			  << vtmb_bytes_part << '\t'
			  << (r.active_preview_mileage ? vtmb_bytes_part : 0) /*APPart*/ << std::endl;
		lo_cap += r.vertices.capacity()*8;
		hi_cap += r.vertices.capacity()*16;
		lo_size += r.vertices.size()*8;
		hi_size += r.vertices.size()*16;
	}
	std::cout << "rTOTAL\t"
		  << rtotal_all_full << '\t'
		  << rtotal_a_p_full << '\t'
		  << rtotal_all_part << '\t'
		  << rtotal_a_p_part << std::endl;
	printf("~total\t%.2f\t\t%.2f\t\t%.2f\t\t%.2f\n",
		double(rtotal_all_full)/1048576,
		double(rtotal_a_p_full)/1048576,
		double(rtotal_all_part)/1048576,
		double(rtotal_a_p_part)/1048576); fflush(stdout);

	// systems
	std::cout << "\nSystem\tAllFull\tAPFull\tAllPart\tAPPart" << std::endl;
	for (HighwaySystem& h : HighwaySystem::syslist)
	{	std::cout << h.systemname << '\t' << std::flush;
		lo_v = h.vertices.empty() ? nullptr : h.vertices.front();
		hi_v = h.vertices.empty() ? nullptr : h.vertices.back();

		size_t vtmb_bytes_part = ceil(double(hi_v-lo_v+2)/64)*8;
		stotal_all_full += vtmb_bytes_full;
		stotal_all_part += vtmb_bytes_part;
		if (!h.devel())
		{	stotal_a_p_full += vtmb_bytes_full;
			stotal_a_p_part += vtmb_bytes_part;
		}

		std::cout << vtmb_bytes_full << '\t'
			  << (h.devel() ? 0 : vtmb_bytes_full) /*APFull*/ << '\t'
			  << vtmb_bytes_part << '\t'
			  << (h.devel() ? 0 : vtmb_bytes_part) /*APPart*/ << std::endl;
		lo_cap += h.vertices.capacity()*8;
		hi_cap += h.vertices.capacity()*8;
		lo_size += h.vertices.size()*8;
		hi_size += h.vertices.size()*8;
	}
	std::cout << "sTOTAL\t"
		  << stotal_all_full << '\t'
		  << stotal_a_p_full << '\t'
		  << stotal_all_part << '\t'
		  << stotal_a_p_part << std::endl;
	printf("~total\t%.2f\t\t%.2f\t\t%.2f\t\t%.2f\n",
		double(stotal_all_full)/1048576,
		double(stotal_a_p_full)/1048576,
		double(stotal_all_part)/1048576,
		double(stotal_a_p_part)/1048576); fflush(stdout);

	// grand totals
	std::cout << "tTOTAL\t"
		  << rtotal_all_full+stotal_all_full << '\t'
		  << rtotal_a_p_full+stotal_a_p_full << '\t'
		  << rtotal_all_part+stotal_all_part << '\t'
		  << rtotal_a_p_part+stotal_a_p_part << std::endl;
	printf("~total\t%.2f\t\t%.2f\t\t%.2f\t\t%.2f\n",
		double(stotal_all_full+rtotal_all_full)/1048576,
		double(stotal_a_p_full+rtotal_a_p_full)/1048576,
		double(stotal_all_part+rtotal_all_part)/1048576,
		double(stotal_a_p_part+rtotal_a_p_part)/1048576); fflush(stdout);
	std::cout << "Cap\t"  << hi_cap  << '\t' << lo_cap  << '\t' << std::endl;
	printf("Cap\t%.2f\t\t%.2f\n" , double(hi_cap) /1048576, double(lo_cap) /1048576);
	std::cout << "Size\t" << hi_size << '\t' << lo_size << '\t' << std::endl;
	printf("Size\t%.2f\t\t%.2f\n", double(hi_size)/1048576, double(lo_size)/1048576);

For vertices created via sys->rte->pts, comment out, copy-paste*, add 2 outer for loops, and iterate with a pointer instead of by range.
*Update link with shorter version after datacheck removal is pushed

[yakra]

copy & assign

	// copy ctor (Will a call to copy assignment compile the same?)
	TMBitset(const TMBitset<item,unit>& other):
	  units(other.units),
	  len  (other.len),
	  start(other.start),
	  data ( (unit*const)malloc(units*sizeof(unit)) )
	{	memcpy(data, other.data, units*sizeof(unit));
	}

	// copy assignment
	// Does not free resources. Only to be used on uninitiaized objects.
	void operator = (const TMBitset<item,unit>& other)
	{	units = other.units;
		len   = other.len;
		start = other.start;
		data  = (unit*const)malloc(units*sizeof(unit));
		memcpy(data, other.data, units*sizeof(unit));
	}

	// move assignment
	// Does not free resources. Only to be used on uninitiaized objects.
	void operator = (TMBitset<item,unit>&& other)
	{	units = other.units;
		len   = other.len;
		start = other.start;
		data  = other.data;
		other.data() = 0;
	}

[yakra]

get_subgraph_data.cpp

Prerequisite: convert regions & systems from lists to vectors (2nd-last bullet point here).

// Find a set of vertices from the graph, optionally
// restricted by region or system or placeradius area.
if (g->regions)
{	auto& r = *g->regions;
	mv = r[0].vertices;
	for (size_t i = 1; i < r.size(); ++i) mv |= r[i].vertices;

	if (g->systems)
	{	auto& h = *g->systems;
		TMBitset sys_mv(h[0].vertices);
		for (size_t i = 1; i < h.size(); ++i) sys_mv |= h[i].vertices;
		mv &= sys_mv;
	}
	if (g->placeradius)
		mv &= g->placeradius->vertices(qt, this);
}
else if (g->systems)
{	auto& h = *g->systems;
	mv = h[0].vertices;
	for (size_t i = 1; i < h.size(); ++i) mv |= h[i].vertices;

	if (g->placeradius)
		mv &= g->placeradius->vertices(qt, this);
} else	// We know there's a PlaceRadius, as no GraphListEntry is created for invalid fullcustom.csv data
		mv =  g->placeradius->vertices(qt, this);

// initialize written booleans