Ichthyostega
a68f145640
The Boost-Libraries changed their internal implementation
of the formula to chain hash values.
Fortunately, we had already extracted the existing implementation
from Boost 1.67 and incorporated it in-tree, in the Lumiera support libary.
After switching to that `lib:#️⃣:combine()` function, all the graph
computations related to the Scheduler-test-load can be shown to be identical.
So at the moment, the impact is still limited, but this incident highlights
the importance of a controlled, stable (and ideally also portable) hash implementation.
1340 lines
67 KiB
C++
1340 lines
67 KiB
C++
/*
|
||
TestChainLoad(Test) - verify diagnostic setup to watch scheduler activities
|
||
|
||
Copyright (C)
|
||
2023, Hermann Vosseler <Ichthyostega@web.de>
|
||
|
||
**Lumiera** is free software; you can redistribute it and/or modify it
|
||
under the terms of the GNU General Public License as published by the
|
||
Free Software Foundation; either version 2 of the License, or (at your
|
||
option) any later version. See the file COPYING for further details.
|
||
|
||
* *****************************************************************/
|
||
|
||
/** @file test-chain-load-test.cpp
|
||
** unit test \ref TestChainLoad_test
|
||
*/
|
||
|
||
|
||
#include "lib/test/run.hpp"
|
||
#include "lib/test/test-helper.hpp"
|
||
#include "lib/format-string.hpp"
|
||
#include "test-chain-load.hpp"
|
||
#include "vault/gear/job.h"
|
||
#include "lib/util.hpp"
|
||
|
||
#include <array>
|
||
|
||
|
||
using util::_Fmt;
|
||
using util::isnil;
|
||
using util::isSameObject;
|
||
using std::array;
|
||
|
||
|
||
namespace vault{
|
||
namespace gear {
|
||
namespace test {
|
||
|
||
namespace { // shorthands and parameters for test...
|
||
|
||
/** shorthand for specific parameters employed by the following tests */
|
||
using ChainLoad16 = TestChainLoad<16>;
|
||
using Node = ChainLoad16::Node;
|
||
auto isStartNode = [](Node& n){ return isStart(n); };
|
||
auto isInnerNode = [](Node& n){ return isInner(n); };
|
||
auto isExitNode = [](Node& n){ return isExit(n); };
|
||
|
||
}//(End)test definitions
|
||
|
||
|
||
|
||
|
||
/*****************************************************************//**
|
||
* @test verify a tool to generate synthetic load for Scheduler tests.
|
||
* @remark statistics output and the generation of Graphviz-DOT diagrams
|
||
* is commented out; these diagnostics are crucial to understand
|
||
* the generated load pattern or to develop new graph shapes.
|
||
* Visualise graph with `dot -Tpng example.dot | display`
|
||
* @see SchedulerService_test
|
||
* @see SchedulerStress_test
|
||
*/
|
||
class TestChainLoad_test : public Test
|
||
{
|
||
|
||
virtual void
|
||
run (Arg)
|
||
{
|
||
seedRand();
|
||
usageExample();
|
||
verify_Node();
|
||
verify_Topology();
|
||
showcase_Expansion();
|
||
showcase_Reduction();
|
||
showcase_SeedChains();
|
||
showcase_PruneChains();
|
||
showcase_StablePattern();
|
||
verify_computation_load();
|
||
verify_reseed_recalculate();
|
||
verify_runtime_reference();
|
||
verify_adjusted_schedule();
|
||
verify_scheduling_setup();
|
||
}
|
||
|
||
|
||
/** @test demonstrate simple usage of the test-load
|
||
* - build a graph with 64 nodes, grouped into small segments
|
||
* - use a scheduler instance to »perform« this graph
|
||
*/
|
||
void
|
||
usageExample()
|
||
{
|
||
auto testLoad =
|
||
TestChainLoad{64}
|
||
.configureShape_short_segments3_interleaved()
|
||
.buildTopology();
|
||
|
||
// while building the graph, node hashes are computed
|
||
CHECK (testLoad.getHash() == 0x554F5086DE5B0861);
|
||
|
||
|
||
BlockFlowAlloc bFlow;
|
||
EngineObserver watch;
|
||
Scheduler scheduler{bFlow, watch};
|
||
|
||
testLoad.setupSchedule(scheduler)
|
||
.launch_and_wait();
|
||
|
||
// invocation through Scheduler has reproduced all node hashes
|
||
CHECK (testLoad.getHash() == 0x554F5086DE5B0861);
|
||
}
|
||
|
||
|
||
|
||
/** @test data structure to represent a computation Node
|
||
*/
|
||
void
|
||
verify_Node()
|
||
{
|
||
Node n0; // Default-created empty Node
|
||
CHECK (n0.hash == 0);
|
||
CHECK (n0.level == 0);
|
||
CHECK (n0.weight == 0);
|
||
CHECK (n0.pred.size() == 0 );
|
||
CHECK (n0.succ.size() == 0 );
|
||
CHECK (n0.pred == Node::Tab{0});
|
||
CHECK (n0.succ == Node::Tab{0});
|
||
|
||
Node n1{23}, n2{55}; // further Nodes with initial seed hash
|
||
CHECK (n1.hash == 23);
|
||
CHECK (n2.hash == 55);
|
||
|
||
CHECK (0 == n0.calculate()); // hash calculation is NOP on unconnected Nodes
|
||
CHECK (0 == n0.hash);
|
||
CHECK (23 == n1.calculate());
|
||
CHECK (23 == n1.hash);
|
||
CHECK (55 == n2.calculate());
|
||
CHECK (55 == n2.hash);
|
||
|
||
n0.addPred(n1); // establish bidirectional link between Nodes
|
||
CHECK (isSameObject (*n0.pred[0], n1));
|
||
CHECK (isSameObject (*n1.succ[0], n0));
|
||
CHECK (not n0.pred[1]);
|
||
CHECK (not n1.succ[1]);
|
||
CHECK (n2.pred == Node::Tab{0});
|
||
CHECK (n2.succ == Node::Tab{0});
|
||
|
||
n2.addSucc(n0); // works likewise in the other direction
|
||
CHECK (isSameObject (*n0.pred[0], n1));
|
||
CHECK (isSameObject (*n0.pred[1], n2)); // next link added into next free slot
|
||
CHECK (isSameObject (*n2.succ[0], n0));
|
||
CHECK (not n0.pred[2]);
|
||
CHECK (not n2.succ[1]);
|
||
|
||
CHECK (n0.hash == 0);
|
||
n0.calculate(); // but now hash calculation combines predecessors
|
||
CHECK (n0.hash == 0x53F8F4753B85558A);
|
||
|
||
Node n00; // another Node...
|
||
n00.addPred(n2) // just adding the predecessors in reversed order
|
||
.addPred(n1);
|
||
|
||
CHECK (n00.hash == 0);
|
||
n00.calculate(); // ==> hash is different, since it depends on order
|
||
CHECK (n00.hash == 0xECA6BE804934CAF2);
|
||
CHECK (n0.hash == 0x53F8F4753B85558A);
|
||
|
||
CHECK (isSameObject (*n1.succ[0], n0));
|
||
CHECK (isSameObject (*n1.succ[1], n00));
|
||
CHECK (isSameObject (*n2.succ[0], n0));
|
||
CHECK (isSameObject (*n2.succ[1], n00));
|
||
CHECK (isSameObject (*n00.pred[0], n2));
|
||
CHECK (isSameObject (*n00.pred[1], n1));
|
||
CHECK (isSameObject (*n0.pred[0], n1));
|
||
CHECK (isSameObject (*n0.pred[1], n2));
|
||
|
||
CHECK (n00.hash == 0xECA6BE804934CAF2);
|
||
n00.calculate(); // calculation is NOT idempotent (inherently statefull)
|
||
CHECK (n00.hash == 0xB682F06D29B165C0);
|
||
|
||
CHECK (isnil (n0.succ)); // number of predecessors or successors properly accounted for
|
||
CHECK (isnil (n00.succ));
|
||
CHECK (n00.succ.empty());
|
||
CHECK (0 == n00.succ.size());
|
||
CHECK (2 == n00.pred.size());
|
||
CHECK (2 == n0.pred.size());
|
||
CHECK (2 == n1.succ.size());
|
||
CHECK (2 == n2.succ.size());
|
||
CHECK (isnil (n1.pred));
|
||
CHECK (isnil (n2.pred));
|
||
}
|
||
|
||
|
||
|
||
/** @test build topology by connecting the nodes
|
||
* - pre-allocate a block with 32 nodes and then
|
||
* build a topology to connect these, using default rules
|
||
* - in the default case, nodes are linearly chained
|
||
* - hash is also computed by chaining with predecessor hash
|
||
* - hash computations can be reproduced
|
||
*/
|
||
void
|
||
verify_Topology()
|
||
{
|
||
auto graph = ChainLoad16{32}
|
||
.buildTopology();
|
||
|
||
CHECK (graph.topLevel() == 31);
|
||
CHECK (graph.getSeed() == 0);
|
||
CHECK (graph.getHash() == 0xB3445F1240A1B05F);
|
||
|
||
auto* node = & *graph.allNodes();
|
||
CHECK (node->hash == graph.getSeed());
|
||
CHECK (node->succ.size() == 1);
|
||
CHECK (isSameObject(*node, *node->succ[0]->pred[0]));
|
||
|
||
size_t steps{0};
|
||
while (not isnil(node->succ))
|
||
{// verify node connectivity
|
||
++steps;
|
||
node = node->succ[0];
|
||
CHECK (steps == node->level);
|
||
CHECK (1 == node->pred.size());
|
||
size_t exHash = node->hash;
|
||
|
||
// recompute the hash -> reproducible
|
||
node->hash = 0;
|
||
node->calculate();
|
||
CHECK (exHash == node->hash);
|
||
|
||
// explicitly compute the hash (formula taken from boost)
|
||
node->hash = 0;
|
||
lib::hash::combine (node->hash, node->pred[0]->hash);
|
||
CHECK (exHash == node->hash);
|
||
}
|
||
// got a complete chain using all allocated nodes
|
||
CHECK (steps == 31);
|
||
CHECK (steps == graph.topLevel());
|
||
CHECK (node->hash == 0x5CDF544B70E59866);
|
||
|
||
// Since this graph has only a single exit-node,
|
||
// the global hash of the graph is derived from this hash
|
||
size_t globalHash{0};
|
||
lib::hash::combine (globalHash, node->hash);
|
||
CHECK (globalHash == graph.getHash());
|
||
CHECK (globalHash == 0xB3445F1240A1B05F);
|
||
}
|
||
|
||
|
||
|
||
|
||
|
||
/** @test demonstrate shaping of generated topology
|
||
* - the expansion rule injects forking nodes
|
||
* - after some expansion, width limitation is enforced
|
||
* - thus join nodes are introduced to keep all chains connected
|
||
* - by default, the hash controls shape, evolving identical in each branch
|
||
* - with additional shuffling, the decisions are more random
|
||
* - statistics can be computed to characterise the graph
|
||
* - the graph can be visualised as _Graphviz diagram_
|
||
*/
|
||
void
|
||
showcase_Expansion()
|
||
{
|
||
ChainLoad16 graph{32};
|
||
|
||
// moderate symmetrical expansion with 40% probability and maximal +2 links
|
||
graph.expansionRule(graph.rule().probability(0.4).maxVal(2))
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0x6EDD7B92F12E9A37);
|
||
|
||
auto stat = graph.computeGraphStatistics();
|
||
CHECK (stat.indicators[STAT_NODE].cnt == 32); // the 32 Nodes...
|
||
CHECK (stat.levels == 11); // ... were organised into 11 levels
|
||
CHECK (stat.indicators[STAT_FORK].cnt == 4); // we got 4 »Fork« events
|
||
CHECK (stat.indicators[STAT_SEED].cnt == 1); // one start node
|
||
CHECK (stat.indicators[STAT_EXIT].cnt == 1); // and one exit node at end
|
||
CHECK (stat.indicators[STAT_NODE].pL == "2.9090909"_expect); // ∅ 3 Nodes / level
|
||
CHECK (stat.indicators[STAT_NODE].cL == "0.640625"_expect); // with Node density concentrated towards end
|
||
|
||
|
||
// with additional re-shuffling, probability acts independent in each branch
|
||
// leading to more chances to draw a »fork«, leading to a faster expanding graph
|
||
graph.expansionRule(graph.rule().probability(0.4).maxVal(2).shuffle(23))
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0x710D010554FEA614);
|
||
|
||
stat = graph.computeGraphStatistics();
|
||
CHECK (stat.levels == 7); // expands faster, with only 7 levels
|
||
CHECK (stat.indicators[STAT_NODE].pL == "4.5714286"_expect); // this time ∅ 4.6 Nodes / level
|
||
CHECK (stat.indicators[STAT_FORK].cnt == 7); // 7 »Fork« events
|
||
CHECK (stat.indicators[STAT_EXIT].cnt == 10); // but 10 »Exit« nodes....
|
||
CHECK (stat.indicators[STAT_JOIN].cnt == 1); // and even one »Join« node....
|
||
CHECK (stat.indicators[STAT_EXIT].cL == 1); // which are totally concentrated towards end
|
||
CHECK (stat.indicators[STAT_JOIN].cL == 1); // when nodes are exhausted
|
||
|
||
|
||
// if the generation is allowed to run for longer,
|
||
// while more constrained in width...
|
||
TestChainLoad<8> gra_2{256};
|
||
gra_2.expansionRule(gra_2.rule().probability(0.4).maxVal(2).shuffle(23))
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (gra_2.getHash() == 0x619491B22C3F8A6F);
|
||
|
||
stat = gra_2.computeGraphStatistics();
|
||
CHECK (stat.levels == 36); // much more levels, as can be expected
|
||
CHECK (stat.indicators[STAT_NODE].pL == "7.1111111"_expect); // ∅ 7 Nodes per level
|
||
CHECK (stat.indicators[STAT_JOIN].pL == "0.77777778"_expect); // but also almost one join per level to deal with the limitation
|
||
CHECK (stat.indicators[STAT_FORK].frac == "0.24609375"_expect); // 25% forks (there is just not enough room for more forks)
|
||
CHECK (stat.indicators[STAT_JOIN].frac == "0.109375"_expect); // and 10% joins
|
||
CHECK (stat.indicators[STAT_EXIT].cnt == 3); // ...leading to 3 »Exit« nodes
|
||
CHECK (stat.indicators[STAT_EXIT].cL == 1); // ....located at the very end
|
||
}
|
||
|
||
|
||
|
||
|
||
|
||
/** @test demonstrate impact of reduction on graph topology
|
||
* - after one fixed initial expansion, reduction causes
|
||
* all chains to be joined eventually
|
||
* - expansion and reduction can counterbalance each other,
|
||
* leading to localised »packages« of branchings and reductions
|
||
*/
|
||
void
|
||
showcase_Reduction()
|
||
{
|
||
ChainLoad16 graph{32};
|
||
|
||
// expand immediately at start and then gradually reduce / join chains
|
||
graph.expansionRule(graph.rule_atStart(8))
|
||
.reductionRule(graph.rule().probability(0.2).maxVal(3).shuffle(555))
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0x3E9BFAE5E686BEB4);
|
||
|
||
auto stat = graph.computeGraphStatistics();
|
||
CHECK (stat.levels == 8); // This connection pattern filled 8 levels
|
||
CHECK (stat.indicators[STAT_JOIN].cnt == 4); // we got 4 »Join« events (reductions=
|
||
CHECK (stat.indicators[STAT_FORK].cnt == 1); // and the single expansion/fork
|
||
CHECK (stat.indicators[STAT_FORK].cL == 0.0); // ...sitting right at the beginning
|
||
CHECK (stat.indicators[STAT_NODE].cL == "0.42857143"_expect); // Nodes are concentrated towards the beginning
|
||
|
||
|
||
// expansion and reduction can counterbalance each other
|
||
graph.expansionRule(graph.rule().probability(0.2).maxVal(3).shuffle(555))
|
||
.reductionRule(graph.rule().probability(0.2).maxVal(3).shuffle(555))
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0xB0335595D34F1D8D);
|
||
|
||
stat = graph.computeGraphStatistics();
|
||
CHECK (stat.levels == 11); // This example runs a bit longer
|
||
CHECK (stat.indicators[STAT_NODE].pL == "2.9090909"_expect); // in the middle threading 3-5 Nodes per Level
|
||
CHECK (stat.indicators[STAT_FORK].cnt == 5); // with 5 expansions
|
||
CHECK (stat.indicators[STAT_JOIN].cnt == 3); // and 3 reductions
|
||
CHECK (stat.indicators[STAT_FORK].cL == 0.5); // forks dominating earlier
|
||
CHECK (stat.indicators[STAT_JOIN].cL == "0.73333333"_expect); // while joins need forks as prerequisite
|
||
|
||
|
||
// expansion bursts can be balanced with a heightened reduction intensity
|
||
graph.expansionRule(graph.rule().probability(0.3).maxVal(4).shuffle(555))
|
||
.reductionRule(graph.rule().probability(0.9).maxVal(2).shuffle(555))
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0x220A2E81F65146FC);
|
||
|
||
stat = graph.computeGraphStatistics();
|
||
CHECK (stat.levels == 12); // This graph has a similar outline
|
||
CHECK (stat.indicators[STAT_NODE].pL == "2.6666667"_expect); // in the middle threading 3-5 Nodes per Level
|
||
CHECK (stat.indicators[STAT_FORK].cnt == 7); // ...yet with quite different internal structure
|
||
CHECK (stat.indicators[STAT_JOIN].cnt == 9); //
|
||
CHECK (stat.indicators[STAT_FORK].cL == "0.41558442"_expect);
|
||
CHECK (stat.indicators[STAT_JOIN].cL == "0.62626263"_expect);
|
||
CHECK (stat.indicators[STAT_FORK].pLW == "0.19583333"_expect); // while the densities of forks and joins almost match,
|
||
CHECK (stat.indicators[STAT_JOIN].pLW == "0.26527778"_expect); // a slightly higher reduction density leads to convergence eventually
|
||
}
|
||
|
||
|
||
|
||
|
||
|
||
/** @test demonstrate shaping of generated topology by seeding new chains
|
||
* - the seed rule allows to start new chains in the middle of the graph
|
||
* - combined with with reduction, the emerging structure resembles
|
||
* the processing pattern encountered with real media calculations
|
||
*/
|
||
void
|
||
showcase_SeedChains()
|
||
{
|
||
ChainLoad16 graph{32};
|
||
|
||
// randomly start new chains, to be carried-on linearly
|
||
graph.seedingRule(graph.rule().probability(0.2).maxVal(3).shuffle())
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0xBC35A96B3CE1F39F);
|
||
|
||
auto stat = graph.computeGraphStatistics();
|
||
CHECK (stat.levels == 7); // 7 Levels...
|
||
CHECK (stat.indicators[STAT_SEED].cnt == 12); // overall 12 »Seed« events generated several ongoing chains
|
||
CHECK (stat.indicators[STAT_FORK].cnt == 0); // yet no branching/expanding
|
||
CHECK (stat.indicators[STAT_LINK].cnt == 14); // thus more and more chains were just carried on
|
||
CHECK (stat.indicators[STAT_LINK].pL == 2); // on average 2-3 per level are continuations
|
||
CHECK (stat.indicators[STAT_NODE].pL == "4.5714286"_expect); // leading to ∅ 4.5 Nodes per level
|
||
CHECK (stat.indicators[STAT_NODE].cL == "0.734375"_expect); // with nodes amassing towards the end
|
||
CHECK (stat.indicators[STAT_LINK].cL == "0.64285714"_expect); // because there are increasingly more links to carry-on
|
||
CHECK (stat.indicators[STAT_JOIN].cL == 1); // while joining only happens at the very end
|
||
|
||
|
||
// combining random seed nodes with reduction leads to a processing pattern
|
||
// with side-chaines successively joined into a single common result
|
||
graph.seedingRule(graph.rule().probability(0.2).maxVal(3).shuffle())
|
||
.reductionRule(graph.rule().probability(0.9).maxVal(2))
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0x3DFA720156540247);
|
||
|
||
stat = graph.computeGraphStatistics();
|
||
CHECK (stat.indicators[STAT_SEED].cnt == 11); // the same number of 11 »Seed« events
|
||
CHECK (stat.indicators[STAT_JOIN].cnt == 6); // but now 6 joining nodes
|
||
CHECK (stat.indicators[STAT_LINK].cnt == 15); // and less carry-on
|
||
CHECK (stat.indicators[STAT_FORK].cnt == 0); // no branching
|
||
CHECK (stat.indicators[STAT_NODE].pL == 3.2); // leading a slightly leaner graph with ∅ 3.2 Nodes per level
|
||
CHECK (stat.indicators[STAT_NODE].cL == "0.5625"_expect); // and also slightly more evenly spaced this time
|
||
CHECK (stat.indicators[STAT_LINK].cL == "0.55555556"_expect); // links are also more encountered in the middle
|
||
CHECK (stat.indicators[STAT_JOIN].cL == "0.72222222"_expect); // and also joins are happening underway
|
||
CHECK (stat.levels == 10); // mostly because a leaner graph takes longer to use 32 Nodes
|
||
}
|
||
|
||
|
||
|
||
|
||
|
||
/** @test demonstrate topology with pruning and multiple segments
|
||
* - the prune rule terminates chains randomly
|
||
* - this can lead to fragmentation into several sub-graphs
|
||
* - these can be completely segregated, or appear interwoven
|
||
* - equilibrium of seeding and pruning can be established
|
||
*/
|
||
void
|
||
showcase_PruneChains()
|
||
{
|
||
ChainLoad16 graph{32};
|
||
|
||
// terminate chains randomly
|
||
graph.pruningRule(graph.rule().probability(0.2))
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0x660BD1CD261A990);
|
||
|
||
auto stat = graph.computeGraphStatistics();
|
||
CHECK (stat.levels == 32); // only a single line of connections...
|
||
CHECK (stat.segments == 8); // albeit severed into 8 segments
|
||
CHECK (stat.indicators[STAT_NODE].pS == 4); // with always 4 Nodes per segment
|
||
CHECK (stat.indicators[STAT_NODE].pL == 1); // and only ever a single node per level
|
||
CHECK (stat.indicators[STAT_SEED].cnt == 8); // consequently we get 8 »Seed« nodes
|
||
CHECK (stat.indicators[STAT_EXIT].cnt == 8); // 8 »Exit« nodes
|
||
CHECK (stat.indicators[STAT_LINK].cnt == 16); // and 16 interconnecting links
|
||
|
||
|
||
// combined with expansion, several tree-shaped segments emerge
|
||
graph.pruningRule(graph.rule().probability(0.2))
|
||
.expansionRule(graph.rule().probability(0.6))
|
||
.setSeed(10101)
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0x1D0A7C39647340AA);
|
||
|
||
stat = graph.computeGraphStatistics();
|
||
CHECK (stat.levels == 14); //
|
||
CHECK (stat.segments == 5); // this time the graph is segregated into 5 parts
|
||
CHECK (stat.indicators[STAT_NODE].pS == "6.4"_expect); // with 4 Nodes per segment
|
||
CHECK (stat.indicators[STAT_FORK].sL == "0"_expect); // where »Fork« is always placed at the beginning of each segment
|
||
CHECK (stat.indicators[STAT_EXIT].sL == "1"_expect); // and several »Exit« at the end
|
||
CHECK (stat.indicators[STAT_EXIT].pS == "3"_expect); // with always 3 exits per segment
|
||
CHECK (stat.indicators[STAT_SEED].cnt == 5); // so overall we get 5 »Seed« nodes
|
||
CHECK (stat.indicators[STAT_FORK].cnt == 5); // 5 »Fork« nodes
|
||
CHECK (stat.indicators[STAT_EXIT].cnt == 15); // 15 »Exit« nodes
|
||
CHECK (stat.indicators[STAT_LINK].cnt == 12); // and 12 interconnecting links
|
||
CHECK (stat.indicators[STAT_NODE].pL == "2.2857143"_expect); // leading to ∅ ~2 Nodes per level
|
||
|
||
|
||
// however, by chance, with more randomised pruning points...
|
||
graph.pruningRule(graph.rule().probability(0.2).shuffle(5))
|
||
.expansionRule(graph.rule().probability(0.6))
|
||
.setSeed(10101)
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0x12BB22F76ECC5C1B);
|
||
|
||
stat = graph.computeGraphStatistics();
|
||
CHECK (stat.segments == 1); // ...the graph can evade severing altogether
|
||
CHECK (stat.indicators[STAT_FORK].cnt == 3); // with overall 3 »Fork«
|
||
CHECK (stat.indicators[STAT_EXIT].cnt == 10); // and 10 »Exit« nodes
|
||
CHECK (stat.indicators[STAT_EXIT].pL == "1.6666667"_expect); // ∅ 1.6 exits per level
|
||
CHECK (stat.indicators[STAT_NODE].pL == "5.3333333"_expect); // ∅ 5.3 nodes per level
|
||
|
||
|
||
graph.expansionRule(graph.rule()); // reset
|
||
|
||
|
||
// combined with a special seeding rule,
|
||
// which injects /another seed/ in the next level after each seed,
|
||
// an equilibrium of chain seeding and termination can be achieved...
|
||
graph.seedingRule(graph.rule_atStart(1))
|
||
.pruningRule(graph.rule().probability(0.2))
|
||
.setSeed(10101)
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0xBFFA04FE8202C708);
|
||
|
||
// NOTE: this example produced 11 disjoint graph parts,
|
||
// which however start and end interleaved
|
||
stat = graph.computeGraphStatistics();
|
||
CHECK (stat.levels == 12); // Generation carries on for 12 levels
|
||
CHECK (stat.segments == 1); // NOTE: the detection of segments FAILS here (due to interleaved starts)
|
||
CHECK (stat.indicators[STAT_SEED].cnt == 12); // 12 »Seed« nodes
|
||
CHECK (stat.indicators[STAT_EXIT].cnt == 11); // 11 »Exit« nodes (including the isolated, last one)
|
||
CHECK (stat.indicators[STAT_LINK].cnt == 10); // 10 interconnecting links
|
||
CHECK (stat.indicators[STAT_JOIN].cnt == 1); // and one additional »Join«
|
||
CHECK (stat.indicators[STAT_JOIN].cL == "1"_expect); // ....appended at graph completion
|
||
CHECK (stat.indicators[STAT_NODE].pL == "2.6666667"_expect); // overall ∅ 2⅔ nodes per level (converging ⟶ 3)
|
||
CHECK (stat.indicators[STAT_NODE].cL == "0.52840909"_expect); // with generally levelled distribution
|
||
CHECK (stat.indicators[STAT_SEED].cL == "0.5"_expect); // also for the seeds
|
||
CHECK (stat.indicators[STAT_EXIT].cL == "0.62809917"_expect); // and the exits
|
||
|
||
|
||
// The next example is »interesting« insofar it shows self-similarity
|
||
// The generation is entirely repetitive and locally predictable,
|
||
// producing an ongoing sequence of small graph segments,
|
||
// partially overlapping with interwoven starts.
|
||
graph.seedingRule(graph.rule().fixedVal(1))
|
||
.pruningRule(graph.rule().probability(0.5))
|
||
.reductionRule(graph.rule().probability(0.8).maxVal(4))
|
||
.setSeed(10101)
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0xFB0A0EA9B7072507);
|
||
|
||
stat = graph.computeGraphStatistics();
|
||
CHECK (stat.levels == 8); // Generation carries on for 13 levels
|
||
CHECK (stat.indicators[STAT_JOIN].pL == 1); // with one »Join« event per level on average
|
||
CHECK (stat.indicators[STAT_SEED].cnt == 22); // seeds are injected with /fixed rate/, meaning that
|
||
CHECK (stat.indicators[STAT_SEED].pL == 2.75); // there is one additional seed for every node in previous level
|
||
}
|
||
|
||
|
||
|
||
|
||
|
||
/** @test examples of realistic stable processing patterns
|
||
* - some cases achieve a real equilibrium
|
||
* - other examples' structure is slowly expanding
|
||
* and become stable under constriction of width
|
||
* - some examples go into a stable repetitive loop
|
||
* - injecting additional randomness generates a
|
||
* chaotic yet stationary flow of similar patterns
|
||
* @note these examples use a larger pre-allocation of nodes
|
||
* to demonstrate the stable state; because, towards end,
|
||
* a tear-down into one single exit node will be enforced.
|
||
* @remark creating any usable example is a matter of experimentation;
|
||
* the usual starting point is to balance expanding and contracting
|
||
* forces; yet generation can either run-away or suffocate, and
|
||
* so the task is to find a combination of seed values and slight
|
||
* parameter variations leading into repeated re-establishment
|
||
* of some node constellation. When this is achieved, additional
|
||
* shuffling can be introduced to uncover further potential.
|
||
*/
|
||
void
|
||
showcase_StablePattern()
|
||
{
|
||
ChainLoad16 graph{256};
|
||
|
||
// This example creates a repetitive, non-expanding stable pattern
|
||
// comprised of four small graph segments, generated interleaved
|
||
// Explanation: rule_atLink() triggers when the preceding node is a »Link«
|
||
graph.seedingRule(graph.rule_atLink(1))
|
||
.pruningRule(graph.rule().probability(0.4))
|
||
.reductionRule(graph.rule().probability(0.6).maxVal(5).minVal(2))
|
||
.setSeed(23)
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0x6B5D7BD3130044E2);
|
||
|
||
auto stat = graph.computeGraphStatistics();
|
||
CHECK (stat.indicators[STAT_NODE].cL == "0.50509511"_expect); // The resulting distribution of nodes is stable and balanced
|
||
CHECK (stat.levels == 93); // ...arranging the 256 nodes into 93 levels
|
||
CHECK (stat.indicators[STAT_NODE].pL == "2.7526882"_expect); // ...with ∅ 2.7 nodes per level
|
||
CHECK (stat.indicators[STAT_SEED].pL == "1.0537634"_expect); // comprised of ∅ 1 seed per level
|
||
CHECK (stat.indicators[STAT_JOIN].pL == "0.48387097"_expect); // ~ ∅ ½ join per level
|
||
CHECK (stat.indicators[STAT_EXIT].pL == "0.34408602"_expect); // ~ ∅ ⅓ exit per level
|
||
CHECK (stat.indicators[STAT_SEED].frac == "0.3828125"_expect); // overall, 38% nodes are seeds
|
||
CHECK (stat.indicators[STAT_EXIT].frac == "0.125"_expect); // and ⅛ are exit nodes
|
||
CHECK (stat.indicators[STAT_SEED].cLW == "0.49273514"_expect); // the density centre of all node kinds
|
||
CHECK (stat.indicators[STAT_LINK].cLW == "0.49588657"_expect); // ...is close to the middle
|
||
CHECK (stat.indicators[STAT_JOIN].cLW == "0.52481335"_expect);
|
||
CHECK (stat.indicators[STAT_EXIT].cLW == "0.55716297"_expect);
|
||
|
||
|
||
|
||
// with only a slight increase in pruning probability
|
||
// the graph goes into a stable repetition loop rather,
|
||
// repeating a single shape with 3 seeds, 3 links and one 3-fold join as exit
|
||
graph.seedingRule(graph.rule_atLink(1))
|
||
.pruningRule(graph.rule().probability(0.5))
|
||
.reductionRule(graph.rule().probability(0.6).maxVal(5).minVal(2))
|
||
.setSeed(23)
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0x20122CF2A1F301D1);
|
||
|
||
stat = graph.computeGraphStatistics();
|
||
CHECK (stat.levels == 77); //
|
||
CHECK (stat.indicators[STAT_NODE].pL == "3.3246753"_expect); // ∅ 3.3 nodes per level
|
||
CHECK (stat.indicators[STAT_SEED].frac == "0.421875"_expect); // 42% seed
|
||
CHECK (stat.indicators[STAT_EXIT].frac == "0.14453125"_expect); // 14% exit
|
||
|
||
|
||
|
||
// The next example uses a different generation approach:
|
||
// Here, seeding happens randomly, while every join immediately
|
||
// forces a prune, so all joins become exit nodes.
|
||
// With a reduction probability slightly over seed, yet limited reduction strength
|
||
// the generation goes into a stable repetition loop, yet with rather small graphs,
|
||
// comprised each of two seeds, two links and a single 2-fold join at exit,
|
||
// with exit and the two seeds of the following graph happening simultaneously.
|
||
graph.seedingRule(graph.rule().probability(0.6).maxVal(1))
|
||
.reductionRule(graph.rule().probability(0.75).maxVal(3))
|
||
.pruningRule(graph.rule_atJoin(1))
|
||
.setSeed(47)
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0xB58904674ED84031);
|
||
|
||
stat = graph.computeGraphStatistics();
|
||
CHECK (stat.levels == 104); //
|
||
CHECK (stat.indicators[STAT_NODE].pL == "2.4615385"_expect); // ∅ 2.5 nodes per level
|
||
CHECK (stat.indicators[STAT_SEED].frac == "0.40234375"_expect); // 40% seed
|
||
CHECK (stat.indicators[STAT_EXIT].frac == "0.19921875"_expect); // 20% exit
|
||
CHECK (stat.indicators[STAT_SEED].pL == "0.99038462"_expect); // resulting in 1 seed per level
|
||
CHECK (stat.indicators[STAT_EXIT].pL == "0.49038462"_expect); // ½ exit per level
|
||
|
||
|
||
// »short_segments_interleaved«
|
||
// Increased seed probability combined with overall seed value 0 ◁──── (crucial, other seeds produce larger graphs)
|
||
// produces what seems to be the best stable repetition loop:
|
||
// same shape as in preceding, yet interwoven by 2 steps
|
||
graph.seedingRule(graph.rule().probability(0.8).maxVal(1))
|
||
.reductionRule(graph.rule().probability(0.75).maxVal(3))
|
||
.pruningRule(graph.rule_atJoin(1))
|
||
.setSeed(0)
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0x11B57D9E98FDF6DF);
|
||
|
||
stat = graph.computeGraphStatistics();
|
||
CHECK (stat.levels == 55); // much denser arrangement due to stronger interleaving
|
||
CHECK (stat.indicators[STAT_NODE].pL == "4.6545455"_expect); // ∅ 4.7 nodes per level — almost twice as much
|
||
CHECK (stat.indicators[STAT_SEED].frac == "0.3984375"_expect); // 40% seed
|
||
CHECK (stat.indicators[STAT_EXIT].frac == "0.1953125"_expect); // 20% exit — same fractions
|
||
CHECK (stat.indicators[STAT_SEED].pL == "1.8545455"_expect); // 1.85 seed per level — higher density
|
||
CHECK (stat.indicators[STAT_EXIT].pL == "0.90909091"_expect); // 0.9 exit per level
|
||
|
||
|
||
// With just the addition of irregularity through shuffling on the reduction,
|
||
// a stable and tightly interwoven pattern of medium sized graphs is generated
|
||
graph.seedingRule(graph.rule().probability(0.8).maxVal(1))
|
||
.reductionRule(graph.rule().probability(0.75).maxVal(3).shuffle())
|
||
.pruningRule(graph.rule_atJoin(1))
|
||
.setSeed(0)
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0x7C0453E7A4F6418D);
|
||
|
||
stat = graph.computeGraphStatistics();
|
||
CHECK (stat.levels == 44); //
|
||
CHECK (stat.indicators[STAT_NODE].pL == "5.8181818"_expect); // ∅ 5.7 nodes per level
|
||
CHECK (stat.indicators[STAT_SEED].pL == "2.4318182"_expect); // ∅ 2.4 seeds
|
||
CHECK (stat.indicators[STAT_LINK].pL == "2.4772727"_expect); // ∅ 2.5 link nodes
|
||
CHECK (stat.indicators[STAT_EXIT].pL == "1"_expect); // ∅ 1 join/exit nodes — indicating stronger spread/reduction
|
||
|
||
|
||
|
||
// This example uses another setup, without special rules;
|
||
// rather, seed, reduction and pruning are tuned to balance each other.
|
||
// The result is a regular interwoven pattern of very small graphs,
|
||
// slowly expanding yet stable under constriction of width.
|
||
// Predominant is a shape with two seeds on two levels, a single link and a 2-fold join;
|
||
// caused by width constriction, this becomes complemented by larger compounds at intervals.
|
||
graph.seedingRule(graph.rule().probability(0.8).maxVal(1))
|
||
.reductionRule(graph.rule().probability(0.75).maxVal(3))
|
||
.pruningRule(graph.rule().probability(0.55))
|
||
.setSeed(55) // ◁───────────────────────────────────────────── use 31 for width limited to 8 nodes
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0x904A906B7859301A);
|
||
|
||
stat = graph.computeGraphStatistics();
|
||
CHECK (stat.levels == 21); // ▶ resulting graph is very dense, hitting the parallelisation limit
|
||
CHECK (stat.indicators[STAT_NODE].pL == "12.190476"_expect); // ∅ more than 12 nodes per level !
|
||
CHECK (stat.indicators[STAT_SEED].pL == "6.8571429"_expect); // comprised of ∅ 6.9 seeds
|
||
CHECK (stat.indicators[STAT_LINK].pL == "2.3809524"_expect); // ∅ 2.4 links
|
||
CHECK (stat.indicators[STAT_JOIN].pL == "2.8095238"_expect); // ∅ 2.8 joins
|
||
CHECK (stat.indicators[STAT_EXIT].pL == "2.5714286"_expect); // ∅ 2.6 exits
|
||
CHECK (stat.indicators[STAT_SEED].frac == "0.5625"_expect ); // 56% seed
|
||
CHECK (stat.indicators[STAT_EXIT].frac == "0.2109375"_expect); // 21% exit
|
||
|
||
|
||
|
||
// A slight parameters variation generates medium sized graphs, which are deep interwoven;
|
||
// the generation is slowly expanding, but becomes stable under width constriction
|
||
graph.seedingRule(graph.rule().probability(0.8).maxVal(1))
|
||
.reductionRule(graph.rule().probability(0.6).maxVal(5).minVal(2))
|
||
.pruningRule(graph.rule().probability(0.4))
|
||
.setSeed(42)
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0x9453C56534FF9CD6);
|
||
|
||
stat = graph.computeGraphStatistics();
|
||
CHECK (stat.levels == 26); //
|
||
CHECK (stat.indicators[STAT_NODE].pL == "9.8461538"_expect); // ∅ 9.8 nodes per level — ⅓ less dense
|
||
CHECK (stat.indicators[STAT_SEED].frac == "0.40234375"_expect); // 40% seed
|
||
CHECK (stat.indicators[STAT_LINK].frac == "0.453125"_expect); // 45% link
|
||
CHECK (stat.indicators[STAT_JOIN].frac == "0.109375"_expect ); // 11% joins
|
||
CHECK (stat.indicators[STAT_EXIT].frac == "0.08984375"_expect); // 8% exits — hinting at very strong reduction
|
||
|
||
|
||
// The same setup with different seeing produces a
|
||
// stable repetitive change of linear chain and small tree with 2 joins
|
||
graph.seedingRule(graph.rule().probability(0.8).maxVal(2))
|
||
.reductionRule(graph.rule().probability(0.6).maxVal(5).minVal(2))
|
||
.pruningRule(graph.rule().probability(0.42))
|
||
.setSeed(23)
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0xA57727C2ED277C87);
|
||
|
||
stat = graph.computeGraphStatistics();
|
||
CHECK (stat.levels == 129); //
|
||
CHECK (stat.indicators[STAT_NODE].pL == "1.9844961"_expect); // ∅ ~2 nodes per level — much lesser density
|
||
CHECK (stat.indicators[STAT_SEED].frac == "0.3359375"_expect); // 33% seed
|
||
CHECK (stat.indicators[STAT_LINK].frac == "0.4140625"_expect); // 42% link
|
||
CHECK (stat.indicators[STAT_JOIN].frac == "0.1640625"_expect); // 16% join
|
||
CHECK (stat.indicators[STAT_EXIT].frac == "0.171875"_expect); // 17% exit — only a 2:1 reduction on average
|
||
|
||
|
||
// With added shuffling in the seed rule, and under width constriction,
|
||
// an irregular sequence of small to large and strongly interwoven graphs emerges.
|
||
graph.seedingRule(graph.rule().probability(0.8).maxVal(2).shuffle())
|
||
.reductionRule(graph.rule().probability(0.6).maxVal(5).minVal(2))
|
||
.pruningRule(graph.rule().probability(0.42))
|
||
.setSeed(23)
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0x4D0575F8BD269FC3);
|
||
|
||
stat = graph.computeGraphStatistics();
|
||
CHECK (stat.levels == 20); // rather dense
|
||
CHECK (stat.indicators[STAT_NODE].pL == "12.8"_expect); // ∅ 12.8 nodes per level
|
||
CHECK (stat.indicators[STAT_SEED].pL == "7.65"_expect); // ∅ 7.7 seeds
|
||
CHECK (stat.indicators[STAT_LINK].pL == "3.15"_expect); // ∅ 3 links
|
||
CHECK (stat.indicators[STAT_JOIN].pL == "1.9"_expect); // ∅ 1.9 joins
|
||
CHECK (stat.indicators[STAT_EXIT].pL == "0.95"_expect); // ∅ ~1 exit per level
|
||
|
||
|
||
|
||
// »chain_loadBursts«
|
||
// The final example attempts to balance expansion and reduction forces.
|
||
// Since reduction needs expanded nodes to work on, expansion always gets
|
||
// a head start and we need to tune reduction to slightly higher strength
|
||
// to ensure the graph width does not explode. The result is one single
|
||
// graph with increasingly complex connections, which can expand into
|
||
// width limitation at places, but also collapse to a single thread.
|
||
// The seed controls how fast the onset of the pattern happens.
|
||
// low values -> long single-chain prelude
|
||
// seed ≔ 55 -> prelude with 2 chains, then join, then onset at level 17
|
||
// high values -> massive onset quickly going into saturation
|
||
graph.expansionRule(graph.rule().probability(0.27).maxVal(4))
|
||
.reductionRule(graph.rule().probability(0.44).maxVal(6).minVal(2))
|
||
.seedingRule(graph.rule())
|
||
.pruningRule(graph.rule())
|
||
.setSeed(62)
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
// .printTopologyStatistics()
|
||
;
|
||
CHECK (graph.getHash() == 0x25114F8770B1B78E);
|
||
|
||
stat = graph.computeGraphStatistics();
|
||
CHECK (stat.levels == 30); // rather high concurrency
|
||
CHECK (stat.indicators[STAT_SEED].cnt == 1); // a single seed
|
||
CHECK (stat.indicators[STAT_EXIT].cnt == 4); // ...and 4 exit when running out of node space
|
||
CHECK (stat.indicators[STAT_NODE].pL == "8.5333333"_expect); // ∅ 8.25 nodes per level
|
||
CHECK (stat.indicators[STAT_FORK].frac == "0.16015625"_expect); // 16% forks
|
||
CHECK (stat.indicators[STAT_LINK].frac == "0.76171875"_expect); // 77% links
|
||
CHECK (stat.indicators[STAT_JOIN].frac == "0.1015625"_expect); // 10% joins
|
||
CHECK (stat.indicators[STAT_KNOT].frac == "0.0390625"_expect); // 3% »Knot« nodes which both join and fork
|
||
CHECK (stat.indicators[STAT_FORK].cLW == "0.43298744"_expect); // density centre of forks lies earlier
|
||
CHECK (stat.indicators[STAT_JOIN].cLW == "0.64466378"_expect); // while density centre of joins leans rather towards end
|
||
}
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
|
||
/** @test verify calibration of a configurable computational load.
|
||
*/
|
||
void
|
||
verify_computation_load()
|
||
{
|
||
ComputationalLoad cpuLoad;
|
||
CHECK (cpuLoad.timeBase == 100us);
|
||
|
||
double micros = cpuLoad.invoke();
|
||
CHECK (micros < 2000);
|
||
CHECK (micros > 2);
|
||
|
||
cpuLoad.calibrate();
|
||
|
||
micros = cpuLoad.invoke();
|
||
CHECK (micros < 133);
|
||
CHECK (micros > 80);
|
||
|
||
micros = cpuLoad.benchmark();
|
||
CHECK (micros < 110);
|
||
CHECK (micros > 90);
|
||
|
||
cpuLoad.useAllocation = true;
|
||
micros = cpuLoad.invoke();
|
||
CHECK (micros < 133);
|
||
CHECK (micros > 80);
|
||
|
||
micros = cpuLoad.benchmark();
|
||
CHECK (micros < 110);
|
||
CHECK (micros > 90);
|
||
|
||
cpuLoad.timeBase = 1ms;
|
||
cpuLoad.sizeBase *= 100;
|
||
cpuLoad.calibrate();
|
||
|
||
cpuLoad.useAllocation = false;
|
||
micros = cpuLoad.invoke();
|
||
CHECK (micros > 900);
|
||
micros = cpuLoad.invoke(5);
|
||
CHECK (micros > 4600);
|
||
micros = cpuLoad.invoke(10);
|
||
CHECK (micros > 9500);
|
||
micros = cpuLoad.invoke(100);
|
||
CHECK (micros > 95000);
|
||
|
||
cpuLoad.useAllocation = true;
|
||
micros = cpuLoad.invoke();
|
||
CHECK (micros > 900);
|
||
micros = cpuLoad.invoke(5);
|
||
CHECK (micros > 4600);
|
||
micros = cpuLoad.invoke(10);
|
||
CHECK (micros > 9500);
|
||
micros = cpuLoad.invoke(100);
|
||
CHECK (micros > 95000);
|
||
}
|
||
|
||
|
||
|
||
/** @test set and propagate seed values and recalculate all node hashes.
|
||
* @remark This test uses parameter rules with some expansion and a
|
||
* pruning rule with 60% probability. This setup is known to
|
||
* create a sequence of tiny isolated trees with 4 nodes each;
|
||
* there are 8 such groups, each with a fork and two exit nodes.
|
||
* The following code traverses all nodes grouped into 4-node
|
||
* clusters to verify the regular pattern and calculated hashes.
|
||
*/
|
||
void
|
||
verify_reseed_recalculate()
|
||
{
|
||
ChainLoad16 graph{32};
|
||
graph.expansionRule(graph.rule().probability(0.8).maxVal(1))
|
||
.pruningRule(graph.rule().probability(0.6))
|
||
.weightRule((graph.rule().probability(0.5)))
|
||
.buildTopology();
|
||
|
||
CHECK (8 == graph.allNodes().filter(isStartNode).count());
|
||
CHECK (16 == graph.allNodes().filter(isExitNode).count());
|
||
|
||
|
||
// verify computation of the globally combined exit hash
|
||
auto exitHashes = graph.allNodes()
|
||
.filter(isExitNode)
|
||
.transform([](Node& n){ return n.hash; })
|
||
.effuse();
|
||
CHECK (16 == exitHashes.size());
|
||
|
||
size_t combinedHash{0};
|
||
for (uint i=0; i <16; ++i)
|
||
lib::hash::combine (combinedHash, exitHashes[i]);
|
||
|
||
CHECK (graph.getHash() == combinedHash);
|
||
CHECK (graph.getHash() == 0x33B00C450215EB00);
|
||
|
||
|
||
// verify connectivity and local exit hashes
|
||
graph.allNodePtr().grouped<4>()
|
||
.foreach([&](auto group)
|
||
{ // verify wiring pattern
|
||
// and the resulting exit hashes
|
||
auto& [a,b,c,d] = *group;
|
||
CHECK (isStart(a));
|
||
CHECK (isInner(b));
|
||
CHECK (not a->weight);
|
||
CHECK (not b->weight);
|
||
CHECK (isExit(c));
|
||
CHECK (isExit(d));
|
||
CHECK (c->hash == 0xAEDC04CFA2E5B999);
|
||
CHECK (d->hash == 0xAEDC04CFA2E5B999);
|
||
CHECK (c->weight == 4);
|
||
CHECK (d->weight == 4);
|
||
});
|
||
|
||
|
||
graph.setSeed(55).clearNodeHashes();
|
||
CHECK (graph.getSeed() == 55);
|
||
CHECK (graph.getHash() == 0);
|
||
graph.allNodePtr().grouped<4>()
|
||
.foreach([&](auto group)
|
||
{ // verify hashes have been reset
|
||
auto& [a,b,c,d] = *group;
|
||
CHECK (a->hash == 55);
|
||
CHECK (b->hash == 0);
|
||
CHECK (b->hash == 0);
|
||
CHECK (b->hash == 0);
|
||
});
|
||
|
||
graph.recalculate();
|
||
CHECK (graph.getHash() == 0x17427F67DBC8BCC0);
|
||
graph.allNodePtr().grouped<4>()
|
||
.foreach([&](auto group)
|
||
{ // verify hashes were recalculated
|
||
// based on the new seed
|
||
auto& [a,b,c,d] = *group;
|
||
CHECK (a->hash == 55);
|
||
CHECK (c->hash == 0x7887993B0ED41395);
|
||
CHECK (d->hash == 0x7887993B0ED41395);
|
||
});
|
||
|
||
// seeding and recalculation are reproducible
|
||
graph.setSeed(0).recalculate();
|
||
CHECK (graph.getHash() == 0x33B00C450215EB00);
|
||
graph.setSeed(55).recalculate();
|
||
CHECK (graph.getHash() == 0x17427F67DBC8BCC0);
|
||
}
|
||
|
||
|
||
|
||
/** @test compute synchronous execution time for reference
|
||
*/
|
||
void
|
||
verify_runtime_reference()
|
||
{
|
||
double t1 =
|
||
TestChainLoad{64}
|
||
.configureShape_short_segments3_interleaved()
|
||
.buildTopology()
|
||
.calcRuntimeReference();
|
||
|
||
double t2 =
|
||
TestChainLoad{64}
|
||
.configureShape_short_segments3_interleaved()
|
||
.buildTopology()
|
||
.calcRuntimeReference(1ms);
|
||
|
||
double t3 =
|
||
TestChainLoad{256}
|
||
.configureShape_short_segments3_interleaved()
|
||
.buildTopology()
|
||
.calcRuntimeReference();
|
||
|
||
auto isWithin10Percent = [](double t, double r)
|
||
{
|
||
auto delta = abs (1.0 - t/r);
|
||
return delta < 0.1;
|
||
};
|
||
|
||
// the test-graph has 64 Nodes,
|
||
// each using the default load of 100µs
|
||
CHECK (isWithin10Percent(t1, 6400)); // thus overall we should be close to 6.4ms
|
||
CHECK (isWithin10Percent(t2, 10*t1)); // and the 10-fold load should yield 10-times
|
||
CHECK (isWithin10Percent(t3, 4*t1)); // using 4 times as much nodes (64->256)
|
||
|
||
// the time measurement uses a performance
|
||
// which clears, re-seeds and calculates the complete graph
|
||
auto graph =
|
||
TestChainLoad{64}
|
||
.configureShape_short_segments3_interleaved()
|
||
.buildTopology();
|
||
|
||
CHECK (graph.getHash() == 0x554F5086DE5B0861);
|
||
|
||
graph.clearNodeHashes();
|
||
CHECK (graph.getHash() == 0);
|
||
|
||
// this is used by the timing benchmark
|
||
graph.performGraphSynchronously();
|
||
CHECK (graph.getHash() == 0x554F5086DE5B0861);
|
||
|
||
graph.clearNodeHashes();
|
||
CHECK (graph.getHash() == 0);
|
||
|
||
graph.calcRuntimeReference();
|
||
CHECK (graph.getHash() == 0x554F5086DE5B0861);
|
||
}
|
||
|
||
|
||
|
||
/** @test verify use of computation weights and topology to establish
|
||
* a predicted load pattern, which can be used to construct a
|
||
* schedule adapted to the expected load.
|
||
* @remark use `printTopologyDOT()` and then `dot -Tpng xx.dot|display`
|
||
* to understand the numbers in context of the topology
|
||
*/
|
||
void
|
||
verify_adjusted_schedule()
|
||
{
|
||
TestChainLoad testLoad{64};
|
||
testLoad.configureShape_chain_loadBursts()
|
||
.buildTopology()
|
||
// .printTopologyDOT()
|
||
;
|
||
|
||
// compute aggregated level data....
|
||
auto level = testLoad.allLevelWeights().effuse();
|
||
CHECK (level.size() == 26);
|
||
|
||
// visualise and verify this data......
|
||
auto node = testLoad.allNodePtr().effuse();
|
||
_Fmt nodeFmt{"i=%-2d lev:%-2d w=%1d"};
|
||
_Fmt levelFmt{" Σ%-2d Σw:%2d"};
|
||
auto nodeStr = [&](uint i)
|
||
{
|
||
size_t l = node[i]->level;
|
||
return string{nodeFmt % i % node[i]->level % node[i]->weight}
|
||
+ (i == level[l].endidx? string{levelFmt % level[l].nodes % level[l].weight}
|
||
: string{" · · "});
|
||
};
|
||
// |idx--level--wght|-levelSum-------
|
||
CHECK (nodeStr( 1) == "i=1 lev:1 w=0 Σ1 Σw: 0"_expect);
|
||
CHECK (nodeStr( 2) == "i=2 lev:2 w=2 Σ1 Σw: 2"_expect);
|
||
CHECK (nodeStr( 3) == "i=3 lev:3 w=0 Σ1 Σw: 0"_expect);
|
||
CHECK (nodeStr( 4) == "i=4 lev:4 w=0 Σ1 Σw: 0"_expect);
|
||
CHECK (nodeStr( 5) == "i=5 lev:5 w=0 Σ1 Σw: 0"_expect);
|
||
CHECK (nodeStr( 6) == "i=6 lev:6 w=1 Σ1 Σw: 1"_expect);
|
||
CHECK (nodeStr( 7) == "i=7 lev:7 w=2 Σ1 Σw: 2"_expect);
|
||
CHECK (nodeStr( 8) == "i=8 lev:8 w=2 Σ1 Σw: 2"_expect);
|
||
CHECK (nodeStr( 9) == "i=9 lev:9 w=1 · · "_expect);
|
||
CHECK (nodeStr(10) == "i=10 lev:9 w=1 Σ2 Σw: 2"_expect);
|
||
CHECK (nodeStr(11) == "i=11 lev:10 w=0 · · "_expect);
|
||
CHECK (nodeStr(12) == "i=12 lev:10 w=0 Σ2 Σw: 0"_expect);
|
||
CHECK (nodeStr(13) == "i=13 lev:11 w=0 · · "_expect);
|
||
CHECK (nodeStr(14) == "i=14 lev:11 w=0 Σ2 Σw: 0"_expect);
|
||
CHECK (nodeStr(15) == "i=15 lev:12 w=1 · · "_expect);
|
||
CHECK (nodeStr(16) == "i=16 lev:12 w=1 Σ2 Σw: 2"_expect);
|
||
CHECK (nodeStr(17) == "i=17 lev:13 w=1 · · "_expect);
|
||
CHECK (nodeStr(18) == "i=18 lev:13 w=1 Σ2 Σw: 2"_expect);
|
||
CHECK (nodeStr(19) == "i=19 lev:14 w=2 · · "_expect);
|
||
CHECK (nodeStr(20) == "i=20 lev:14 w=2 Σ2 Σw: 4"_expect);
|
||
CHECK (nodeStr(21) == "i=21 lev:15 w=0 Σ1 Σw: 0"_expect);
|
||
CHECK (nodeStr(22) == "i=22 lev:16 w=1 Σ1 Σw: 1"_expect);
|
||
CHECK (nodeStr(23) == "i=23 lev:17 w=3 Σ1 Σw: 3"_expect);
|
||
CHECK (nodeStr(24) == "i=24 lev:18 w=0 · · "_expect);
|
||
CHECK (nodeStr(25) == "i=25 lev:18 w=0 · · "_expect);
|
||
CHECK (nodeStr(26) == "i=26 lev:18 w=0 · · "_expect);
|
||
CHECK (nodeStr(27) == "i=27 lev:18 w=0 · · "_expect);
|
||
CHECK (nodeStr(28) == "i=28 lev:18 w=0 Σ5 Σw: 0"_expect);
|
||
CHECK (nodeStr(29) == "i=29 lev:19 w=2 · · "_expect);
|
||
CHECK (nodeStr(30) == "i=30 lev:19 w=2 · · "_expect);
|
||
CHECK (nodeStr(31) == "i=31 lev:19 w=2 · · "_expect);
|
||
CHECK (nodeStr(32) == "i=32 lev:19 w=2 · · "_expect);
|
||
CHECK (nodeStr(33) == "i=33 lev:19 w=2 Σ5 Σw:10"_expect);
|
||
CHECK (nodeStr(34) == "i=34 lev:20 w=3 · · "_expect);
|
||
CHECK (nodeStr(35) == "i=35 lev:20 w=2 Σ2 Σw: 5"_expect);
|
||
CHECK (nodeStr(36) == "i=36 lev:21 w=1 · · "_expect);
|
||
CHECK (nodeStr(37) == "i=37 lev:21 w=1 · · "_expect);
|
||
CHECK (nodeStr(38) == "i=38 lev:21 w=3 Σ3 Σw: 5"_expect);
|
||
CHECK (nodeStr(39) == "i=39 lev:22 w=3 · · "_expect);
|
||
CHECK (nodeStr(40) == "i=40 lev:22 w=3 · · "_expect);
|
||
CHECK (nodeStr(41) == "i=41 lev:22 w=0 · · "_expect);
|
||
CHECK (nodeStr(42) == "i=42 lev:22 w=0 · · "_expect);
|
||
CHECK (nodeStr(43) == "i=43 lev:22 w=0 · · "_expect);
|
||
CHECK (nodeStr(44) == "i=44 lev:22 w=0 Σ6 Σw: 6"_expect);
|
||
CHECK (nodeStr(45) == "i=45 lev:23 w=0 · · "_expect);
|
||
|
||
// compute a weight factor for each level,
|
||
// using the number of nodes, the weight sum and concurrency
|
||
CHECK (level[19].nodes = 5); // ╭────────────────────────╢ concurrency
|
||
CHECK (level[19].weight = 10); // ▽ ╭───────╢ boost by concurrency
|
||
CHECK (computeWeightFactor(level[19], 1) == 10.0);// ▽
|
||
CHECK (computeWeightFactor(level[19], 2) == 10.0 / (5.0/3));
|
||
CHECK (computeWeightFactor(level[19], 3) == 10.0 / (5.0/2));
|
||
CHECK (computeWeightFactor(level[19], 4) == 10.0 / (5.0/2));
|
||
CHECK (computeWeightFactor(level[19], 5) == 10.0 / (5.0/1));
|
||
|
||
// build a schedule sequence based on
|
||
// summing up weight factors, with example concurrency ≔ 4
|
||
uint concurrency = 4;
|
||
auto steps = testLoad.levelScheduleSequence(concurrency).effuse();
|
||
CHECK (steps.size() == 26);
|
||
|
||
// for documentation/verification: show also the boost factor and the resulting weight factor
|
||
auto boost = [&](uint i){ return level[i].nodes / std::ceil (double(level[i].nodes)/concurrency); };
|
||
auto wfact = [&](uint i){ return computeWeightFactor(level[i], concurrency); };
|
||
|
||
_Fmt stepFmt{"lev:%-2d nodes:%-2d Σw:%2d %4.1f Δ%5.3f ▿▿ %6.3f"};
|
||
auto stepStr = [&](uint i){ return string{stepFmt % i % level[i].nodes % level[i].weight % boost(i) % wfact(i) % steps[i]}; };
|
||
|
||
// boost wfactor steps
|
||
CHECK (stepStr( 0) == "lev:0 nodes:1 Σw: 0 1.0 Δ0.000 ▿▿ 0.000"_expect);
|
||
CHECK (stepStr( 1) == "lev:1 nodes:1 Σw: 0 1.0 Δ0.000 ▿▿ 0.000"_expect);
|
||
CHECK (stepStr( 2) == "lev:2 nodes:1 Σw: 2 1.0 Δ2.000 ▿▿ 2.000"_expect);
|
||
CHECK (stepStr( 3) == "lev:3 nodes:1 Σw: 0 1.0 Δ0.000 ▿▿ 2.000"_expect);
|
||
CHECK (stepStr( 4) == "lev:4 nodes:1 Σw: 0 1.0 Δ0.000 ▿▿ 2.000"_expect);
|
||
CHECK (stepStr( 5) == "lev:5 nodes:1 Σw: 0 1.0 Δ0.000 ▿▿ 2.000"_expect);
|
||
CHECK (stepStr( 6) == "lev:6 nodes:1 Σw: 1 1.0 Δ1.000 ▿▿ 3.000"_expect);
|
||
CHECK (stepStr( 7) == "lev:7 nodes:1 Σw: 2 1.0 Δ2.000 ▿▿ 5.000"_expect);
|
||
CHECK (stepStr( 8) == "lev:8 nodes:1 Σw: 2 1.0 Δ2.000 ▿▿ 7.000"_expect);
|
||
CHECK (stepStr( 9) == "lev:9 nodes:2 Σw: 2 2.0 Δ1.000 ▿▿ 8.000"_expect);
|
||
CHECK (stepStr(10) == "lev:10 nodes:2 Σw: 0 2.0 Δ0.000 ▿▿ 8.000"_expect);
|
||
CHECK (stepStr(11) == "lev:11 nodes:2 Σw: 0 2.0 Δ0.000 ▿▿ 8.000"_expect);
|
||
CHECK (stepStr(12) == "lev:12 nodes:2 Σw: 2 2.0 Δ1.000 ▿▿ 9.000"_expect);
|
||
CHECK (stepStr(13) == "lev:13 nodes:2 Σw: 2 2.0 Δ1.000 ▿▿ 10.000"_expect);
|
||
CHECK (stepStr(14) == "lev:14 nodes:2 Σw: 4 2.0 Δ2.000 ▿▿ 12.000"_expect);
|
||
CHECK (stepStr(15) == "lev:15 nodes:1 Σw: 0 1.0 Δ0.000 ▿▿ 12.000"_expect);
|
||
CHECK (stepStr(16) == "lev:16 nodes:1 Σw: 1 1.0 Δ1.000 ▿▿ 13.000"_expect);
|
||
CHECK (stepStr(17) == "lev:17 nodes:1 Σw: 3 1.0 Δ3.000 ▿▿ 16.000"_expect);
|
||
CHECK (stepStr(18) == "lev:18 nodes:5 Σw: 0 2.5 Δ0.000 ▿▿ 16.000"_expect);
|
||
CHECK (stepStr(19) == "lev:19 nodes:5 Σw:10 2.5 Δ4.000 ▿▿ 20.000"_expect);
|
||
CHECK (stepStr(20) == "lev:20 nodes:2 Σw: 5 2.0 Δ2.500 ▿▿ 22.500"_expect);
|
||
CHECK (stepStr(21) == "lev:21 nodes:3 Σw: 5 3.0 Δ1.667 ▿▿ 24.167"_expect);
|
||
CHECK (stepStr(22) == "lev:22 nodes:6 Σw: 6 3.0 Δ2.000 ▿▿ 26.167"_expect);
|
||
CHECK (stepStr(23) == "lev:23 nodes:6 Σw: 6 3.0 Δ2.000 ▿▿ 28.167"_expect);
|
||
CHECK (stepStr(24) == "lev:24 nodes:10 Σw: 9 3.3 Δ2.700 ▿▿ 30.867"_expect);
|
||
CHECK (stepStr(25) == "lev:25 nodes:3 Σw: 4 3.0 Δ1.333 ▿▿ 32.200"_expect);
|
||
}
|
||
|
||
|
||
|
||
|
||
/** @test setup for running a chain-load as scheduled task
|
||
* - running an isolated Node recalculation
|
||
* - dispatch of this recalculation packaged as render job
|
||
* - verify the planning job, which processes nodes in batches;
|
||
* for the test, the callback-λ will not invoke the Scheduler,
|
||
* but rather use the instructions to create clone nodes;
|
||
* if all nodes are processed and all dependency connections
|
||
* properly reported through the callback-λ, then calculating
|
||
* this clone network should reproduce the original hash.
|
||
*/
|
||
void
|
||
verify_scheduling_setup()
|
||
{
|
||
array<Node,4> nodes;
|
||
auto& [s,p1,p2,e] = nodes;
|
||
s.addSucc(p1)
|
||
.addSucc(p2);
|
||
e.addPred(p1)
|
||
.addPred(p2);
|
||
s.level = 0;
|
||
p1.level = p2.level = 1;
|
||
e.level = 2;
|
||
CHECK (e.hash == 0);
|
||
for (Node& n : nodes)
|
||
n.calculate();
|
||
CHECK (e.hash == 0x6A5924BA3389D7C);
|
||
|
||
|
||
// now do the same invoked as »render job«
|
||
for (Node& n : nodes)
|
||
n.hash = 0;
|
||
s.level = 0;
|
||
p1.level = 1;
|
||
p2.level = 1;
|
||
e.level = 2;
|
||
|
||
RandomChainCalcFunctor<16> chainJob{nodes[0]};
|
||
Job job0{chainJob
|
||
,chainJob.encodeNodeID(0)
|
||
,chainJob.encodeLevel(0)};
|
||
Job job1{chainJob
|
||
,chainJob.encodeNodeID(1)
|
||
,chainJob.encodeLevel(1)};
|
||
Job job2{chainJob
|
||
,chainJob.encodeNodeID(2)
|
||
,chainJob.encodeLevel(1)};
|
||
Job job3{chainJob
|
||
,chainJob.encodeNodeID(3)
|
||
,chainJob.encodeLevel(2)};
|
||
|
||
CHECK (e.hash == 0);
|
||
job0.triggerJob();
|
||
// ◁───────────────────────────────────────────── Note: fail to invoke some predecessor....
|
||
job2.triggerJob();
|
||
job3.triggerJob();
|
||
CHECK (e.hash != 0x6A5924BA3389D7C);
|
||
|
||
e.hash = 0;
|
||
job1.triggerJob(); // recalculate missing part of the graph...
|
||
job3.triggerJob();
|
||
CHECK (e.hash == 0x6A5924BA3389D7C);
|
||
|
||
job3.triggerJob(); // Hash calculations are *not* idempotent
|
||
CHECK (e.hash != 0x6A5924BA3389D7C);
|
||
|
||
|
||
// use the »planing job« to organise the calculations:
|
||
// Let the callbacks create a clone — which at the end should generate the same hash
|
||
array<Node,4> clone;
|
||
size_t lastTouched(-1);
|
||
size_t lastNode (-1);
|
||
size_t lastLevel(-1);
|
||
bool shallContinue{false};
|
||
auto getNodeIdx = [&](Node* n) { return n - &nodes[0]; };
|
||
|
||
// callback-λ rigged for test....
|
||
// Instead of invoking the Scheduler, here we replicate the node structure
|
||
auto disposeStep = [&](size_t idx, size_t level)
|
||
{
|
||
Node& n = clone[idx];
|
||
n.clear();
|
||
n.level = level;
|
||
lastTouched = idx;
|
||
};
|
||
auto setDependency = [&](Node* pred, Node* succ)
|
||
{
|
||
size_t predIdx = getNodeIdx(pred);
|
||
size_t succIdx = getNodeIdx(succ);
|
||
// replicate this relation into the clone array
|
||
clone[predIdx].addSucc(clone[succIdx]);
|
||
};
|
||
auto continuation = [&](size_t, size_t nodeDone, size_t levelDone, bool work_left)
|
||
{
|
||
lastNode =nodeDone;
|
||
lastLevel = levelDone;
|
||
shallContinue = work_left;
|
||
};
|
||
// build a JobFunctor for the planning step(s)
|
||
RandomChainPlanFunctor<16> planJob{nodes.front(), nodes.size()
|
||
,disposeStep
|
||
,setDependency
|
||
,continuation};
|
||
Job jobP1{planJob
|
||
,planJob.encodeNodeID(1)
|
||
,Time::ANYTIME};
|
||
Job jobP2{planJob
|
||
,planJob.encodeNodeID(5)
|
||
,Time::ANYTIME};
|
||
|
||
jobP1.triggerJob();
|
||
CHECK (lastLevel = 1);
|
||
CHECK (lastTouched = 2);
|
||
CHECK (lastTouched == lastNode);
|
||
Node* lastN = &clone[lastTouched];
|
||
CHECK (lastN->level == lastLevel);
|
||
CHECK ( isnil (lastN->succ));
|
||
CHECK (not isnil (lastN->pred));
|
||
CHECK (shallContinue);
|
||
|
||
jobP2.triggerJob();
|
||
CHECK (lastLevel = 3);
|
||
CHECK (lastTouched = 3);
|
||
CHECK (lastTouched == lastNode);
|
||
lastN = &clone[lastTouched];
|
||
CHECK (lastN->level == 2);
|
||
CHECK (lastN->level < lastLevel);
|
||
CHECK ( isnil (lastN->succ));
|
||
CHECK (not isnil (lastN->pred));
|
||
CHECK (not shallContinue);
|
||
|
||
// all clone nodes should be wired properly now
|
||
CHECK (lastN->hash == 0);
|
||
for (Node& n : clone)
|
||
n.calculate();
|
||
CHECK (lastN->hash == 0x6A5924BA3389D7C);
|
||
}
|
||
};
|
||
|
||
|
||
/** Register this test class... */
|
||
LAUNCHER (TestChainLoad_test, "unit engine");
|
||
|
||
|
||
|
||
}}} // namespace vault::gear::test
|