|
Wildmeshing Toolkit
|
Classes | |
| struct | OpTable |
| The registered operations by rank. edit_operation_maps is a std::map, so iterating it yields the names in lexicographic order and an operation's index is its name's rank: comparing ranks is comparing names, which is what keeps the queue order unchanged. More... | |
| struct | PassStats |
| What the last pass cost in contention, as opposed to in work. More... | |
| class | QueuedCount |
| struct | WaitSink |
Where a screened round collects the next round's candidates: the operations its successes renewed and the ones must_wait set aside, by rank (see OpTable), each with its queue key, which stays counted (keys is empty when the pass sets no queue_key). More... | |
Public Types | |
| using | Tuple = typename AppMesh::Tuple |
Public Member Functions | |
| bool | is_queued (uint64_t key) const |
| size_t | waits () const |
| size_t | wait_defects () const |
| ExecutePass (const ExecutionPolicy &policy_=ExecutionPolicy::kSeq) | |
| Construct a new Execute Pass object. It contains the name-to-operation map and the functions that define the rules for operations. | |
| ExecutePass (ExecutePass &)=delete | |
| bool | operator() (AppMesh &m, const std::vector< std::pair< Op, Tuple > > &operation_tuples) |
| Executes the operations for an application when the lambda function is invoked. The rules that are customizly defined for applications are applied. | |
| bool | operator() (AppMesh &m, std::vector< std::pair< Op, Tuple > > &&operation_tuples) |
| As above, but takes the operation list over and frees it as soon as the queues are seeded. | |
| bool | operator() (AppMesh &m, OpList< Tuple > &&operation_tuples) |
| As above for an OpList, which is released entry by entry while the queues are seeded, so the list and the queue never both hold every candidate. | |
| int | get_cnt_success () const |
| int | get_cnt_fail () const |
| const PassStats & | stats () const |
Public Attributes | |
| std::map< Op, std::function< std::optional< std::vector< Tuple > >(AppMesh &, const Tuple &)> > | edit_operation_maps |
| A dictionary that registers names with operations. | |
| std::function< double(const AppMesh &, Op op, const Tuple &)> | priority |
| Priority function (default to edge length) | |
| std::function< bool(double)> | should_renew = [](double) { return true; } |
| check on wheather new operations should be added to the priority queue | |
| std::function< std::vector< std::pair< Op, Tuple > >(const AppMesh &, Op, const std::vector< Tuple > &)> | renew_neighbor_tuples |
| renew neighboring Tuples after each operation depends on the operation | |
| std::function< bool(AppMesh &, const Tuple &, int task_id)> | lock_vertices |
| lock the vertices concerned depends on the operation | |
| std::function< bool(const AppMesh &)> | stopping_criterion |
| Stopping Criterion based on the whole mesh For efficiency, not every time is checked. In serial, this may go over all the elements. For parallel, this involves synchronization. So there is a checking frequency. | |
| size_t | stopping_criterion_checking_frequency = std::numeric_limits<size_t>::max() |
Cumulative successful operations before stopping_criterion is first consulted. | |
| std::function< bool(const AppMesh &, const std::tuple< double, Op, Tuple > &t)> | is_weight_up_to_date |
| Should Process drops some Tuple from being processed. For example, if the energy is out-dated. This is in addition to calling tuple valid. | |
| std::function< void(const AppMesh &, Op, const Tuple &t)> | on_fail |
| used to collect operations that are not finished and used for later re-execution | |
| std::function< uint64_t(const AppMesh &, const Op &, const Tuple &)> | queue_key |
| Optional order between queued operations, used by the split passes. | |
| std::function< bool(const AppMesh &, const Op &, const Tuple &)> | must_wait |
| ExecutionPolicy | policy |
| int | num_threads = 1 |
| size_t | max_retry_limit = 10 |
| Attempts an operation gets at claiming its ring before it is handed to the serial queue drained after the barrier. | |
| size_t | deferral_window = 128 |
| Operations to run before handing deferred operations back to the queue, or 0 to wait until the queue empties. | |
| bool | screen_before_commit = true |
| Screen every operation with a dry run before committing any. | |
Private Types | |
| using | Push = std::function< void(const Op &, const Tuple &, uint64_t)> |
| Queues one candidate; what a seeder calls for each entry of its list. | |
| using | OpFn = std::function< std::optional< std::vector< Tuple > >(AppMesh &, const Tuple &)> |
Private Member Functions | |
| void | operation_cleanup (AppMesh &m) |
| size_t | get_partition_id (const AppMesh &m, const Tuple &e) |
| bool | run_screened (AppMesh &m, const std::function< void(const Push &)> &seed) |
| Screened rounds; see screen_before_commit. | |
| void | check_queued_drained () |
| void | take_unique_renewed (const AppMesh &m, const OpTable &ops, WaitSink &s) |
Leaves in s the valid, still-wanted operations, each (operation, simplex) once, with their queue keys; the ones left out are no longer queued. | |
| bool | execute (AppMesh &m, const std::function< void(const Push &)> &seed, WaitSink *sink=nullptr) |
| void | log_contention (size_t executed_ops=std::numeric_limits< size_t >::max()) const |
Private Attributes | |
| std::atomic_int | cnt_success = 0 |
| std::atomic_int | cnt_fail = 0 |
| PassStats | m_stats |
| QueuedCount | m_queued |
| std::atomic< size_t > | m_waits = 0 |
| std::atomic< size_t > | m_wait_defects = 0 |
| size_t | m_untracked_done = 0 |
|
private |
Queues one candidate; what a seeder calls for each entry of its list.
The third argument is the candidate's queue key when the caller has already counted it (a screened round's commit, see WaitSink); every other seeder passes 0, and the key is computed and counted as the candidate is queued.
|
inline |
Construct a new Execute Pass object. It contains the name-to-operation map and the functions that define the rules for operations.
|
inlineprivate |
Every operation counted as queued during a call was tried or dropped by its end; anything left, or a finished operation that was never counted, means is_queued() may have answered wrongly during the call.
|
inlineprivate |
sink non-null: a screened round's commit. It logs nothing (the screened call does); the queue_key counts span the whole screened call, so they are neither reset nor counted here – the seeder hands over each candidate's counted key – and a waiting operation goes to the sink.
|
inlineprivate |
Debug-level because it is per pass and there are many passes per iteration. Enable with the logger at debug to see whether contention is worth acting on. executed: the operations the contention is spread over; by default every attempt of the last call. A screened call passes the attempts that got past its screen.
|
inline |
Executes the operations for an application when the lambda function is invoked. The rules that are customizly defined for applications are applied.
| m | |
| operation_tuples | a vector of pairs of operation's name and the Tuple to be operated on |
|
inline |
As above, but takes the operation list over and frees it as soon as the queues are seeded.
The queues hold their own copy of every operation, so the list is dead weight from then on – and it is at its longest on the first pass after construction, which is also when the mesh is at its largest. Releasing it there is what keeps a pass from holding every candidate twice at the run's peak.
|
inlineprivate |
Leaves in s the valid, still-wanted operations, each (operation, simplex) once, with their queue keys; the ones left out are no longer queued.
Each entry's validity, priority and dedup key are computed in parallel – priority() is the expensive part. The key is the operation's rank and its simplex: the vertex ids, ordered for edges since a collapse is directed, sorted for faces; the tet id for tets. An operation named after none of these is never merged with another. The list is compacted in place.
|
inline |
Over every call on this executor: operations set aside by must_wait, and must_wait refusals in a serial run (defects, see above).
| size_t wmtk::ExecutePass< AppMesh >::deferral_window = 128 |
Operations to run before handing deferred operations back to the queue, or 0 to wait until the queue empties.
Bounding this is what makes the second-chance list pay. A per-thread queue holds thousands of operations, so draining only at queue-empty means a deferred operation waits that long, by which time the mesh around it has moved, is_weight_up_to_date rejects it, and the work has to be rediscovered. That inflates the attempt count by roughly a fifth and eats most of the per-operation saving.
Measured at 16 threads, three reps, optimization wall time against the pre-deferral baseline, with attempts in brackets:
103197 (base 23.0M) 101881 (base 48.8M) window 0 -2.2% [28.5M] -20.4% [45.7M] window 32 -16.3% [23.7M] -21.6% [43.7M] window 128 -17.9% [23.1M] -26.4% [41.9M] window 512 -17.0% [23.7M] -25.5% [42.7M]
128 is at or near best on both and keeps the attempt count closest to the baseline's. The result is not sharp between 32 and 512; it is sharp against 0.
| std::function<bool(const AppMesh&, const std::tuple<double, Op, Tuple>& t)> wmtk::ExecutePass< AppMesh >::is_weight_up_to_date |
Should Process drops some Tuple from being processed. For example, if the energy is out-dated. This is in addition to calling tuple valid.
| std::function<bool(AppMesh&, const Tuple&, int task_id)> wmtk::ExecutePass< AppMesh >::lock_vertices |
lock the vertices concerned depends on the operation
|
private |
A screened call's finished operations that were not counted as queued (see check_queued_drained()); written by the calling thread only.
| size_t wmtk::ExecutePass< AppMesh >::max_retry_limit = 10 |
Attempts an operation gets at claiming its ring before it is handed to the serial queue drained after the barrier.
10 was swept and left alone. Measured on 128k-tet Thingi10K 103197 at 16 threads, three reps each, in µs per attempted operation:
immediate requeue (before the second-chance deferral below existed): 1: +17.0% 2: +7.2% 3: +6.2% 5: +4.6% 10: best 20: +6.2% with the deferral: 2: 2.170 3: 1.969 10: 1.974 (baseline at 10 was 2.527)
So under the old immediate-requeue behaviour the value mattered a lot – a low limit sent everything it stopped retrying to the serial queue, and that tail (23% of scheduler time at 10, 39% at 1) cost more than the spinning it avoided. With the deferral the retries are nearly free, the overflow pressure disappears, and 3 and 10 become indistinguishable. Left at 10 because nothing argues for moving it.
Below about 3 it still hurts: at 2 the overflow rate climbs enough to be visible again.
| std::function<void(const AppMesh&, Op, const Tuple& t)> wmtk::ExecutePass< AppMesh >::on_fail |
used to collect operations that are not finished and used for later re-execution
| std::function<double(const AppMesh&, Op op, const Tuple&)> wmtk::ExecutePass< AppMesh >::priority |
Priority function (default to edge length)
| std::function<uint64_t(const AppMesh&, const Op&, const Tuple&)> wmtk::ExecutePass< AppMesh >::queue_key |
Optional order between queued operations, used by the split passes.
queue_key names what an operation is about – for a split, its edge (edge_queue_key) – or returns 0 for "not tracked". A tracked operation is counted from the moment it is queued until it is tried, or dropped as invalid or out of date. Being set aside after a lost lock race does not end it. is_queued() reads that count, for any thread.
must_wait is asked after is_weight_up_to_date, with the operation's ring locked. True sets the operation aside exactly like a lost lock race: it is retried later in the pass and, after max_retry_limit attempts, handed to the serial queue drained after the barrier. A serial run – kSeq, or that serial queue – pops in priority order, so whatever an operation could wait on has been tried before it. There a must_wait that still says true is a defect: the operation fails (on_fail) and is counted in wait_defects() rather than being set aside forever.
In a screened pass (screen_before_commit) an operation that waits is not retried within the round: it stays counted and is a candidate of the next round, screened again. A round in which nothing got as far as an attempt while operations waited cannot make progress – what they wait on is still queued and the mesh has not changed – so there, too, every waiting operation is a defect: it fails and is counted in wait_defects(). A must_wait that orders the operations strictly never gets there, since the first operation in its order never waits.
Both empty, the default: nothing is counted and nothing waits.
| std::function<std::vector<std::pair<Op, Tuple> >(const AppMesh&, Op, const std::vector<Tuple>&)> wmtk::ExecutePass< AppMesh >::renew_neighbor_tuples |
renew neighboring Tuples after each operation depends on the operation
| bool wmtk::ExecutePass< AppMesh >::screen_before_commit = true |
Screen every operation with a dry run before committing any.
When set, a parallel pass runs in rounds. Each round first dry-runs every candidate in parallel against the unchanging mesh, with no locks (see operation_dry_run()): everything an operation checks before its first change – the before-hook, valence, the choice of swap configuration – runs, and the operations refused there are reported through on_fail like any failure. Only the survivors go through the queues and ring locks, where they are attempted for real with every check repeated. The operations their successes renew are not queued straight away; they are the next round's candidates, screened the same way.
The point is that the expensive part of a parallel pass was claiming a two-ring of locks for every attempt, and ~98% of attempts on the challenging tetwild models are refused before their first change: those now cost a lock-free read, and the ring locks are taken by the ~2% that get as far as changing the mesh.
On by default for every parallel pass: every operation of the TetMesh and TriMesh registries honours operation_dry_run(), including the splits and vertex smoothing, where it screens out almost nothing but keeps all passes on one pipeline. One driver turns it off: the 2D collapse pass, where it costs more than it saves (TriOptimizerMeshCollapse.cpp). Not used by serial passes, which keep their single queue (and their output), nor by a pass with a live stopping criterion (qslim, shortest edge collapse): those collapse in global priority order up to an exact count, which rounds would reorder.
Memory: a round holds its candidates as (operation rank, tuple), compacts the survivors in place, and collects the next round's in deques, so a screened pass holds about what the queues of an unscreened one would.
| std::function<bool(const AppMesh&)> wmtk::ExecutePass< AppMesh >::stopping_criterion |
Stopping Criterion based on the whole mesh For efficiency, not every time is checked. In serial, this may go over all the elements. For parallel, this involves synchronization. So there is a checking frequency.
| size_t wmtk::ExecutePass< AppMesh >::stopping_criterion_checking_frequency = std::numeric_limits<size_t>::max() |
Cumulative successful operations before stopping_criterion is first consulted.
Despite the name this is a threshold, not a period: the count it is tested against is never reset, so once the pass has had this many successes the criterion is consulted after every subsequent operation. Both current users rely on exactly that – they set the criterion to return true and the threshold to the number of collapses needed to reach a target vertex count, making this a decimation counter that stops the pass on its first check. It is not a "check every N operations" knob, and writing a genuinely periodic criterion against it would evaluate that criterion on every operation forever after.
Left at the default, the criterion is never consulted at all, which is the case for every tetwild/triwild/simwild pass.
(There used to be a cnt_update member here that was incremented per success and reset inside the check, as if the threshold were a period. Nothing ever read it – the reset was on a branch the always-true criteria above never reach – so it was one more contended atomic on the hot path buying nothing, and it is gone.)
1.9.8