Closed yakra closed 1 month ago
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
}
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
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;
}
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
TMBitset<HGEdge*>
support, whole file// Find sets of vertices & edges from the graph, optionally
// restricted by region or system or placeradius area.
auto pr = [&]()
{ TMBitset<HGVertex*, uint64_t> pr_mv(vertices.data, vertices.size);
TMBitset<HGEdge*, uint64_t> pr_me(edges.data, edges.size);
g->placeradius->matching_ve(qt, pr_mv, pr_me);
mv &= pr_mv;
me &= pr_me;
};
if (g->regions)
{ auto &r = *g->regions;
mv = r[0].vertices;
me = r[0].edges;
for (size_t i = 1; i < r.size(); ++i)
{ mv |= r[i].vertices;
me |= r[i].edges;
}
if (g->systems)
{ auto &h = *g->systems;
auto sys_mv(h[0].vertices);
auto sys_me(h[0].edges);
for (size_t i = 1; i < h.size(); ++i)
{ sys_mv |= h[i].vertices;
sys_me |= h[i].edges;
}
mv &= sys_mv;
me &= sys_me;
}
if (g->placeradius) pr();
}
else if (g->systems)
{ auto &h = *g->systems;
mv = h[0].vertices;
me = h[0].edges;
for (size_t i = 1; i < h.size(); ++i)
{ mv |= h[i].vertices;
me |= h[i].edges;
}
if (g->placeradius) pr();
}
else // We know there's a PlaceRadius, as no GraphListEntry is created for invalid fullcustom.csv data
g->placeradius->matching_ve(qt, mv, me);
// count vertices
for (HGVertex *v : mv)
{ switch (v->visibility) // fall-thru is a Good Thing!
{ case 2: cv_count++;
case 1: tv_count++;
default: sv_count++;
}
}
// count edges & create traveler set
for (HGEdge* e : me)
{ if (e->format & HGEdge::simple)
se_count++;
if (e->format & HGEdge::collapsed)
ce_count++;
if (e->format & HGEdge::traveled)
{ te_count++;
traveler_set |= e->segment->clinched_by;
}
}
Replacing this with a call to __builtin_clzl
:
auto msb = [](uint64_t v)
{ constexpr uint64_t b[] = {0x2, 0xC, 0xF0, 0xFF00, 0xFFFF0000, 0xFFFFFFFF00000000};
constexpr uint8_t s[] = {1, 2, 4, 8, 16, 32};
uint8_t r = 0;
for (char i = 5; i >= 0; i--)
if (v & b[i])
{ v >>= s[i];
r |= s[i];
}
return r;
};
a266f4c
- be15cd0
)//void operator |= (const TMBitset<item,unit>& b)
void debug_union(const TMBitset<item,unit>& b, const item x)
//void operator &= (const TMBitset<item,unit>& b)
void debug_intersection(const TMBitset<item,unit>& b, const item x)
both functions, after offset variable declaration
std::cout << "start:\t" << start-x << '\t' << b.start-x << std::endl;
std::cout << " end:\t" << a_end-x << '\t' << b_end-x << std::endl;
std::cout << " len:\t" << len << '\t' << b.len << std::endl;
std::cout << "units:\t" << units << '\t' << b.units << std::endl;
both functions, after the big if/else where the offsets are assigned
std::cout << "copy_offset: " << copy_offset /*<< " / " << copy_offset*ubits*/ << std::endl;
// same deal for oreq_offset and band_offset
union
if (a_end < b_end) // clear lower end() bit
{ std::cout << "Clearing lower end() bit in A unit " << old_u-1 << std::endl << std::endl;
old_d[old_u-1] ^= (unit)1 << old_l%ubits;
}
else { std::cout << "Clearing lower end() bit in B unit " << b.units-1 << std::endl << std::endl;
data[b.units+copy_offset-1] ^= (unit)1 << b.len%ubits;
}
intersection
if (a_end > b_end) // clear higher end() bit
{ std::cout << "Clearing higher end() bit in A unit " << old_l/ubits << std::endl << std::endl;
old_d[old_l/ubits] ^= (unit)1 << old_l%ubits;
}
else if (b.units == units) // if it's in the new dataset's range
{ std::cout << "Clearing higher end() bit in B unit " << b.units-1 << std::endl << std::endl;
data[b.units-1] ^= (unit)1 << b.len%ubits;
}
if (g->cat != g[-1].cat)
std::cout << '\n' << et->et() << "Writing " << g->category() << " graphs." << std::endl;
std::cout << std::endl << "Tag:" << g->tag() << std::flush;
#include "get_subgraph_data.cpp"
// assign traveler numbers
std::cout << "Assigning traveler numbers..." << std::flush;
unsigned int travnum = 0;
for (TravelerList *t : traveler_set)
{ t->traveler_num[threadnum] = travnum++;
traveler_lists.push_back(t);
}
std::cout << "Done." << std::endl;
plus commenting out the readouts between the 2 #ifdef
s, then
std::cout << "Writing vertices..." << std::flush;
std::cout << "Done." << std::endl;
around the for
loop.
HD@1f85330
/ UD@ad75df7
// Find sets of vertices & edges from the graph, optionally
// restricted by region or system or placeradius area.
auto pr = [&]()
{ TMBitset<HGVertex*, uint64_t> pr_mv(vertices.data(), vertices.size());
TMBitset<HGEdge*, uint64_t> pr_me(edges.data, edges.size);
g->placeradius->matching_ve(qt, pr_mv, pr_me);
//mv &= pr_mv;
//me &= pr_me;
mv.debug_intersection(pr_mv, vertices.data());
me.debug_intersection(pr_me, edges.data);
};
if (g->regions)
{ auto &r = *g->regions;
mv = r[0]->vertices;
me = r[0]->edges;
for (size_t i = 1; i < r.size(); ++i)
if (r[i]->active_preview_mileage)
{ //mv |= r[i]->vertices;
//me |= r[i]->edges;
std::cout << "\n\t(base)\t" << r[i]->code << "\n------------------------" << std::endl;
//for (size_t v : {/*24775,*/ 412115, 413657, 519635})
//if (contains(mv, vertices.data()+v))
//std::cout << "Found " << *vertices[v].unique_name << std::endl;
mv.debug_union(r[i]->vertices, vertices.data());
me.debug_union(r[i]->edges, edges.data);
//for (size_t v : {/*24775,*/ 412115, 413657, 519635})
//if (contains(mv, vertices.data()+v))
//std::cout << "Found " << *vertices[v].unique_name << std::endl;
}
std::cout << "\nRegion sets complete." << std::endl;
if (g->systems)
{ auto &h = *g->systems;
auto sys_mv(h[0]->vertices);
auto sys_me(h[0]->edges);
for (size_t i = 1; i < h.size(); ++i)
{ //sys_mv |= h[i]->vertices;
//sys_me |= h[i]->edges;
std::cout << "\n\t(base)\t" << h[i]->systemname
<< "\n------------------------" << std::endl;
sys_mv.debug_union(h[i]->vertices, vertices.data());
sys_me.debug_union(h[i]->edges, edges.data);
}
std::cout << "System sets complete." << std::endl;
//mv &= sys_mv;
//me &= sys_me;
std::cout << "\n\tRegion\tSystem\n------------------------" << std::endl;
mv.debug_intersection(sys_mv, vertices.data());
std::cout << "begin: " << *mv.begin()-vertices.data() << std::endl << std::endl;
me.debug_intersection(sys_me, edges.data);
std::cout << "\nSet intersections complete." << std::endl;
}
std::cout << "PlaceRadius? " << std::flush;
if (g->placeradius)
{ pr();
std::cout << "Done." << std::endl;
}
else std::cout << "Nope." << std::endl;
}
else if (g->systems)
{ auto &h = *g->systems;
mv = h[0]->vertices;
me = h[0]->edges;
for (size_t i = 1; i < h.size(); ++i)
{ //mv |= h[i]->vertices;
//me |= h[i]->edges;
mv.debug_union(h[i]->vertices, vertices.data());
me.debug_union(h[i]->edges, edges.data);
}
if (g->placeradius) pr();
}
...
std::cout << "Count vertices... " << std::flush;
// and
std::cout << "Count edges & create traveler set... " << std::flush;
// before the respective FOR loops, with
std::cout << "Done." << std::endl;
// after each.
commit | branch | comments |
---|---|---|
7b2c8be | gtmb_rebase4 | equivalent to 3282921 |
5e92ac6 | (stash) | debug: collapses & predictions child of 706ce72 in gtmb_rebase4 |
5d41dc8 | origin/gtmb_rebase4 | branch from 061aa42 |
f19530b | gtmb_v | child commits of gtmb_rebase3 equivalent to 5d41dc8 in tmb_rebase4 |
b44c3cb | rset | branch from gtmb_rebase3 failed region set experiment: add each edge once not twice - &rg comprison, but single-threaded |
4830d40 | hset | branch from gtmb_rebase3 failed system set experiment: add each edge once not twice, but single-threaded. Check if is_subgraph_system ; don't check &h or break. |
584844d | eset | branch from gtmb_rebase3 the above two combined |
b0b92b9 | gtmb_rebase3 | 1 child commit of origin/gtmb_rebase3 |
49a4d2d | origin/gtmb_rebase3 | branch from d02b171 in gtmb_rebase2 |
d66b6c3 | gtmb_rebase2 | equivalent to 49a4d2d in tmb_rebase3 branch from fd96ac6 |
b646a51 | gtmb_rebase | equivalent to e99f486 in tmb_rebase2 branch from fd96ac6 |
050d9c5 | g_tmb | equivalent to c1eb36d in tmb_rebase branch from fd96ac6 |
06371c9 | sort2 | branch from 2142ceb in g_tmb 2-pass: Don't sort dead edges, but do a preliminary pass to delete them. |
08c6cce | sort1 | branch from 2142ceb in g_tmb 1-pass: Take the hit of sorting dead edges; do everything else as-is. |
35ba2aa | egaplogs | branch from 9d1b8a0 in g_tmb revived as f914fbb in gtmb_rebase2 |
8061ea2 | g_tmbdebug | branch from 51d5e88 in g_tmb don't \|= empty sets (later made unnecessary by \|= improvements)__builtin_ctz -> __builtin_ctzl |
ff8bfa3 | g_ugc | Merge branch 'g_u' into g_ugc (g_gc) g (GLE region/system lists -> vectors) adopted; only care about u (unique_name -> char*), and c (concurrency lists -> vectors) |
8eec663 | g_gc | Merge branch 'g_c' into g_gc (g_g) |
3909a22 | g_ug | Merge branch 'g_g' into g_ug (g_u) |
8f84425 | g_g | cherrypicked into g_tmb |
2f6327a | g_y265Phase1 | ancestor of g_tmb |
8ed42a2 | g_y265Phase0 | child of 209170f in g_tmb (disallow devel systems) build vectors for a/p regions & subgraph systems only just a test to compare RAM footprint to no-build |
209170f | g_DevSys | ancestor of g_tmb |
c2004eb | g_EdgeComp | branch from 0ff0af1 remove extraneous collapse conditions -> 3a337c1 in g_tmb nix extraneous pointer chasing -> 8c013a0 in g_tmb (iterate vertices during compression) |
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 ofTMBitset::add_index
andTMBitset::add_value
, so get hip.TMBitset<HGVertex*>
simplifies code. How about performance? Don't have to zero out individual bits at least.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.~mvvec
is nixed altogether? Is the slower iteration thrumvset
(or whatever I end up calling it) outweighed by not doing all the vector's (re)allocations? Way more vertices = higher impact than nixingtraveler_lists
.|=
everything together.|=
them in.&=
operator.std::pair<HGVertex*,Waypoint*>
s. Remember how & why; look for ways around this. https://github.com/yakra/DataProcessing/blob/387c99b0c260938c870457bb9793d4f78b09987f/siteupdate/cplusplus/classes/GraphGeneration/get_subgraph_data.cpp#L10 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.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 existingvector<HGVertex*>
s. RAM use figures below don't reflect this; they were calculated before I thought of it.2decc64
active_preview_mileage
== 0? We're down to 37.36 M rg + 53.41 M sys = 90.76 MTMBitset::shrink_to_fit()
function (exact mechanics TBD).unit
s 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 pairedWaypoint*
s for regions) -- not bad!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 asquished
bool in the low bit ofdata
, and throw? Would require replacing each use ofdata
element with a function. PitA, probably not worth it.!=
: What about a larger set containing elements outside a smaller one? Could return 1 ifstart
orlen
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 comparingclinched_by
when compressing edges -- even no-build would work as long as I don't resizeclinched_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 thenfree
it,|=
in the other stuff.end()
bit as needed.alloc
function, a la TMArrayTMBitset::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.