Skip to content

optimizing vertex creation order #275

Description

@yakra

Carving this out of #242 into its own issue.

With Waypoints stored contiguously, graph point setup iterating via system->route (benchmarked slower when WaypointQuadtree::graph_points was written although the method changed quite a bit ) rather than via quadtree may become faster.
Low impact, though. Low priority.
Potentially higher impact: Vertices created in this order may yield a more favorable compressed edge order, leading to better memory locality when writing files.

  • unordered_set may jumble up the order and negate the benefit.
  • forward_list should do better though, retaining the order of the edges creation.
  • No-build should perform in between -- I expect allocation should go low->high, though it won't be perfect.
    None of the jumbling of unordered_set, but addresses of deleted temporary edges may be re-used for new edges.
  • In any case, hi_priority & lo_priority vertex separation will jumble up compressed edge order a bit, but whatchagonnado.

3*2 ways to do it:

  • Iterate by:
  • No-build vs. eliminating extraneous visibility checks & branching thusly:
    elsefor (Waypoint *w : points)
    {	// singleton waypointsif (!w->colocated)
    {	if (!w->route->system->active_or_preview()) continue;
    w->ap_coloc.push_back(w);
    goto lo_priority;
    }
    // skip if not at front of colocation listif (w != w->colocated->front()) continue;
    // skip if this point is occupied by only waypoints in devel systemsif ([=](){for (Waypoint* p : *w->colocated) if (p->route->system->active_or_preview()) return0; return1;}()) continue;
    // store a colocated list with any devel system entries removedfor (Waypoint *p : *(w->colocated))
    if (p->route->system->active_or_preview())
    w->ap_coloc.push_back(p);
    // determine vertex name simplification priorityif (	w->ap_coloc.size() != 2
    || w->ap_coloc.front()->route->abbrev.size()
    || w->ap_coloc.back()->route->abbrev.size()
    )	lo_priority:
    lo_priority_points.push_back(w);
    else	hi_priority_points.push_back(w);
    }

What to observe:

  • Speed
    • Setup / graph_points
    • Writing files
  • RAM (with TMBitset::shrink_to_fit())
    • regions, systems, combined
    • vertices, edges, combined
    • more/less compact if ap_coloc.size() != 2 -> hi_priority?

Metadata

Metadata

Assignees

No one assigned

    Projects

    No projects

    Milestone

    No milestone

    Relationships

    None yet

    Development

    No branches or pull requests

    Issue actions