From 84a2c470edcd97fd72188250ab81989b203fc4fe Mon Sep 17 00:00:00 2001 From: Bruno Donassolo Date: Tue, 8 Mar 2022 13:41:05 +0100 Subject: [PATCH] BMF: One pass in sonar issues --- src/kernel/lmm/bmf.cpp | 77 +++++++++++++++-------------- src/kernel/lmm/bmf.hpp | 2 +- src/kernel/lmm/bmf_test.cpp | 99 +++++++++++++------------------------ 3 files changed, 77 insertions(+), 101 deletions(-) diff --git a/src/kernel/lmm/bmf.cpp b/src/kernel/lmm/bmf.cpp index 537e8692e5..777f252976 100644 --- a/src/kernel/lmm/bmf.cpp +++ b/src/kernel/lmm/bmf.cpp @@ -38,7 +38,7 @@ bool AllocationGenerator::next(std::vector& next_alloc) return true; } - int n_resources = A_.rows(); + auto n_resources = A_.rows(); size_t idx = 0; while (idx < alloc_.size()) { alloc_[idx] = (++alloc_[idx]) % n_resources; @@ -114,7 +114,7 @@ double BmfSolver::get_resource_capacity(int resource, const std::vector& bo std::vector BmfSolver::alloc_map_to_vector(const allocation_map_t& alloc) const { std::vector alloc_by_player(A_.cols(), -1); - for (auto it : alloc) { + for (const auto& it : alloc) { for (auto p : it.second) { alloc_by_player[p] = it.first; } @@ -135,7 +135,7 @@ std::vector BmfSolver::get_bounded_players(const allocation_map_t& alloc) c Eigen::VectorXd BmfSolver::equilibrium(const allocation_map_t& alloc) const { - int n_players = A_.cols(); + auto n_players = A_.cols(); Eigen::MatrixXd A_p = Eigen::MatrixXd::Zero(n_players, n_players); // square matrix with number of players Eigen::VectorXd C_p = Eigen::VectorXd::Zero(n_players); @@ -144,36 +144,37 @@ Eigen::VectorXd BmfSolver::equilibrium(const allocation_map_t& alloc) const for (const auto& e : alloc) { // add one row for the resource with A[r,] int cur_resource = e.first; + /* bounded players, nothing to do */ if (cur_resource == NO_RESOURCE) continue; - - if (C_shared_[cur_resource]) { - /* shared resource: fairly share it between players */ - A_p.row(row) = A_.row(cur_resource); - C_p[row] = get_resource_capacity(cur_resource, bounded_players); - row++; - if (e.second.size() > 1) { - // if 2 players have chosen the same resource - // they must have a fair sharing of this resource, adjust A_p and C_p accordingly - auto it = e.second.begin(); - int i = *it; // first player - /* for each other player sharing this resource */ - for (++it; it != e.second.end(); ++it) { - /* player i and k on this resource j: so maxA_ji*rho_i - maxA_jk*rho_k = 0 */ - int k = *it; - C_p[row] = 0; - A_p(row, i) = maxA_(cur_resource, i); - A_p(row, k) = -maxA_(cur_resource, k); - row++; - } - } - } else { - /* not shared resource, each player can receive the full capacity of the resource */ + /* not shared resource, each player can receive the full capacity of the resource */ + if (not C_shared_[cur_resource]) { for (int i : e.second) { C_p[row] = get_resource_capacity(cur_resource, bounded_players); A_p(row, i) = A_(cur_resource, i); row++; } + continue; + } + + /* shared resource: fairly share it between players */ + A_p.row(row) = A_.row(cur_resource); + C_p[row] = get_resource_capacity(cur_resource, bounded_players); + row++; + if (e.second.size() > 1) { + // if 2 players have chosen the same resource + // they must have a fair sharing of this resource, adjust A_p and C_p accordingly + auto it = e.second.begin(); + int i = *it; // first player + /* for each other player sharing this resource */ + for (++it; it != e.second.end(); ++it) { + /* player i and k on this resource j: so maxA_ji*rho_i - maxA_jk*rho_k = 0 */ + int k = *it; + C_p[row] = 0; + A_p(row, i) = maxA_(cur_resource, i); + A_p(row, k) = -maxA_(cur_resource, k); + row++; + } } } /* clear players which are externally bounded */ @@ -258,7 +259,7 @@ void BmfSolver::set_fair_sharing(const allocation_map_t& alloc, const Eigen::Vec double consumption_r = A_.row(r) * rho; double_update(&consumption_r, C_[r], sg_maxmin_precision); if (consumption_r > 0.0) { - int n_players = (A_.row(r).array() > 0).count(); + auto n_players = (A_.row(r).array() > 0).count(); fair_sharing[r] = C_[r] / n_players; } else { fair_sharing[r] = get_resource_capacity(r, bounded_players); @@ -293,7 +294,7 @@ bool BmfSolver::is_bmf(const Eigen::VectorXd& rho) const Eigen::MatrixXi player_max_share = ((usage.array().colwise() - max_share.array()).abs() <= sg_maxmin_precision).cast(); // but only saturated resources must be considered - Eigen::VectorXi saturated = ((remaining.array().abs() <= sg_maxmin_precision)).cast(); + Eigen::VectorXi saturated = (remaining.array().abs() <= sg_maxmin_precision).cast(); XBT_DEBUG("Saturated_j resources:\n%s", debug_eigen(saturated).c_str()); player_max_share.array().colwise() *= saturated.array(); @@ -310,7 +311,7 @@ bool BmfSolver::is_bmf(const Eigen::VectorXd& rho) const XBT_DEBUG("Player_ji usage of saturated resources:\n%s", debug_eigen(player_max_share).c_str()); // for all columns(players) it has to be the max at least in 1 - bmf = bmf && (player_max_share.colwise().sum().all() >= 1); + bmf = bmf && (player_max_share.colwise().sum().array() >= 1).all(); return bmf; } @@ -330,7 +331,8 @@ Eigen::VectorXd BmfSolver::solve() auto fair_sharing = C_; /* BMF allocation for each player (current and last one) stop when are equal */ - allocation_map_t last_alloc, cur_alloc; + allocation_map_t last_alloc; + allocation_map_t cur_alloc; Eigen::VectorXd rho; while (it < max_iteration_ && not get_alloc(fair_sharing, last_alloc, cur_alloc, it == 0)) { @@ -372,7 +374,8 @@ Eigen::VectorXd BmfSolver::solve() /*****************************************************************************/ -void BmfSystem::get_flows_data(int number_cnsts, Eigen::MatrixXd& A, Eigen::MatrixXd& maxA, Eigen::VectorXd& phi) +void BmfSystem::get_flows_data(Eigen::Index number_cnsts, Eigen::MatrixXd& A, Eigen::MatrixXd& maxA, + Eigen::VectorXd& phi) { A.resize(number_cnsts, variable_set.size()); A.setZero(); @@ -387,9 +390,9 @@ void BmfSystem::get_flows_data(int number_cnsts, Eigen::MatrixXd& A, Eigen::Matr bool active = false; bool linked = false; // variable is linked to some constraint (specially for selective_update) for (const Element& elem : var.cnsts_) { - boost::intrusive::list_member_hook<>& cnst_hook = selective_update_active - ? elem.constraint->modified_constraint_set_hook_ - : elem.constraint->active_constraint_set_hook_; + const boost::intrusive::list_member_hook<>& cnst_hook = selective_update_active + ? elem.constraint->modified_constraint_set_hook_ + : elem.constraint->active_constraint_set_hook_; if (not cnst_hook.is_linked()) continue; /* active and linked variable, lets check its consumption */ @@ -461,8 +464,10 @@ template void BmfSystem::bmf_solve(const CnstList& cnst_list) /* initialize players' weight and constraint matrices */ idx2Var_.clear(); cnst2idx_.clear(); - Eigen::MatrixXd A, maxA; - Eigen::VectorXd C, bounds; + Eigen::MatrixXd A; + Eigen::MatrixXd maxA; + Eigen::VectorXd C; + Eigen::VectorXd bounds; std::vector shared; get_constraint_data(cnst_list, C, shared); get_flows_data(C.size(), A, maxA, bounds); diff --git a/src/kernel/lmm/bmf.hpp b/src/kernel/lmm/bmf.hpp index 5320a519a5..d039d247b7 100644 --- a/src/kernel/lmm/bmf.hpp +++ b/src/kernel/lmm/bmf.hpp @@ -247,7 +247,7 @@ private: * @param maxA Max subflow consumption matrix (OUTPUT) * @param phi Bounds for variables */ - void get_flows_data(int number_cnsts, Eigen::MatrixXd& A, Eigen::MatrixXd& maxA, Eigen::VectorXd& phi); + void get_flows_data(Eigen::Index number_cnsts, Eigen::MatrixXd& A, Eigen::MatrixXd& maxA, Eigen::VectorXd& phi); /** * @brief Builds the vector C_ with resource's capacity * diff --git a/src/kernel/lmm/bmf_test.cpp b/src/kernel/lmm/bmf_test.cpp index 2fe15f4c2c..0062972e8b 100644 --- a/src/kernel/lmm/bmf_test.cpp +++ b/src/kernel/lmm/bmf_test.cpp @@ -80,7 +80,7 @@ TEST_CASE("kernel::bmf Basic tests", "[kernel-bmf-basic]") * o rho1 + rho2 = C (because all weights are 1) */ - lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3); + lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1); lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1); lmm::Variable* rho_2 = Sys.variable_new(nullptr, 2); @@ -88,14 +88,14 @@ TEST_CASE("kernel::bmf Basic tests", "[kernel-bmf-basic]") Sys.expand(sys_cnst, rho_2, 1); Sys.solve(); - REQUIRE(double_equals(rho_1->get_value(), 2, sg_maxmin_precision)); - REQUIRE(double_equals(rho_2->get_value(), 1, sg_maxmin_precision)); + REQUIRE(double_equals(rho_1->get_value(), 2.0 / 3.0, sg_maxmin_precision)); + REQUIRE(double_equals(rho_2->get_value(), 1.0 / 3.0, sg_maxmin_precision)); } SECTION("Disable variable doesn't count") { /* - * Two flows sharing a single resource, but only disabled + * Two flows sharing a single resource, but one is disabled * * In details: * o System: a1 * p1 * \rho1 + a2 * p2 * \rho2 < C @@ -106,7 +106,7 @@ TEST_CASE("kernel::bmf Basic tests", "[kernel-bmf-basic]") * o a1*rho1 = C */ - lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 3); + lmm::Constraint* sys_cnst = Sys.constraint_new(nullptr, 1); lmm::Variable* rho_1 = Sys.variable_new(nullptr, 1); lmm::Variable* rho_2 = Sys.variable_new(nullptr, 0); @@ -114,7 +114,7 @@ TEST_CASE("kernel::bmf Basic tests", "[kernel-bmf-basic]") Sys.expand(sys_cnst, rho_2, 10); Sys.solve(); - REQUIRE(double_equals(rho_1->get_value(), 3.0, sg_maxmin_precision)); + REQUIRE(double_equals(rho_1->get_value(), 1.0, sg_maxmin_precision)); REQUIRE(double_equals(rho_2->get_value(), 0.0, sg_maxmin_precision)); } @@ -550,9 +550,8 @@ TEST_CASE("kernel::bmf Loop", "[kernel-bmf-loop]") sys_cnst.push_back(Sys.constraint_new(nullptr, c)); } std::vector vars; - for (size_t i = 0; i < A[0].size(); i++) { - vars.push_back(Sys.variable_new(nullptr, 1, -1, A.size())); - } + std::for_each(A[0].begin(), A[0].end(), + [&vars, &Sys, &A](const auto&) { vars.push_back(Sys.variable_new(nullptr, 1, -1, A.size())); }); for (size_t j = 0; j < A.size(); j++) { for (size_t i = 0; i < A[j].size(); i++) { Sys.expand_add(sys_cnst[j], vars[i], A[j][i]); @@ -560,7 +559,7 @@ TEST_CASE("kernel::bmf Loop", "[kernel-bmf-loop]") } Sys.solve(); - for (auto* rho : vars) { + for (const auto* rho : vars) { REQUIRE(double_positive(rho->get_value(), sg_maxmin_precision)); } } @@ -622,61 +621,55 @@ TEST_CASE("kernel::bmf Stress-tests", "[.kernel-bmf-stress]") { lmm::BmfSystem Sys(false); - SECTION("Random consumptions - independent flows") + auto create_cnsts = [&Sys](int C, int capacity) -> auto { - int C = 5; - int N = 2; - auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0)))); std::vector sys_cnst; for (int i = 0; i < C; i++) { - sys_cnst.push_back(Sys.constraint_new(nullptr, 1)); + sys_cnst.push_back(Sys.constraint_new(nullptr, capacity)); } + return sys_cnst; + }; + + auto test_shared = [&Sys, &create_cnsts](int C, int N, int capacity, const auto& data) { + auto sys_cnst = create_cnsts(C, capacity); for (int j = 0; j < N; j++) { + lmm::Variable* rho = Sys.variable_new(nullptr, 1, -1, C); for (int i = 0; i < C; i++) { - lmm::Variable* rho = Sys.variable_new(nullptr, 1); Sys.expand_add(sys_cnst[i], rho, data[i * j + j]); } } Sys.solve(); - } + }; - SECTION("Random consumptions - flows sharing resources") + SECTION("Random consumptions - independent flows") { - int C = 5; - int N = 10; - auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0)))); - - std::vector sys_cnst; - for (int i = 0; i < C; i++) { - sys_cnst.push_back(Sys.constraint_new(nullptr, 1)); - } + int C = 5; + int N = 2; + auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0)))); + auto sys_cnst = create_cnsts(C, 1); for (int j = 0; j < N; j++) { - lmm::Variable* rho = Sys.variable_new(nullptr, 1, -1, C); for (int i = 0; i < C; i++) { + lmm::Variable* rho = Sys.variable_new(nullptr, 1); Sys.expand_add(sys_cnst[i], rho, data[i * j + j]); } } - Sys.solve(); } + SECTION("Random consumptions - flows sharing resources") + { + int C = 5; + int N = 10; + auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0)))); + test_shared(C, N, 1, data); + } + SECTION("Random integer consumptions - flows sharing resources") { int C = 5; int N = 10; auto data = GENERATE_COPY(chunk(C * N, take(100000, random(1, 10)))); - - std::vector sys_cnst; - for (int i = 0; i < C; i++) { - sys_cnst.push_back(Sys.constraint_new(nullptr, 10)); - } - for (int j = 0; j < N; j++) { - lmm::Variable* rho = Sys.variable_new(nullptr, 1, -1, C); - for (int i = 0; i < C; i++) { - Sys.expand_add(sys_cnst[i], rho, data[i * j + j]); - } - } - Sys.solve(); + test_shared(C, N, 10, data); } SECTION("Random consumptions - high number of constraints") @@ -684,18 +677,7 @@ TEST_CASE("kernel::bmf Stress-tests", "[.kernel-bmf-stress]") int C = 500; int N = 10; auto data = GENERATE_COPY(chunk(C * N, take(100000, random(0., 1.0)))); - - std::vector sys_cnst; - for (int i = 0; i < C; i++) { - sys_cnst.push_back(Sys.constraint_new(nullptr, 1)); - } - for (int j = 0; j < N; j++) { - lmm::Variable* rho = Sys.variable_new(nullptr, 1, -1, C); - for (int i = 0; i < C; i++) { - Sys.expand_add(sys_cnst[i], rho, data[i * j + j]); - } - } - Sys.solve(); + test_shared(C, N, 1, data); } SECTION("Random integer consumptions - high number of constraints") @@ -703,18 +685,7 @@ TEST_CASE("kernel::bmf Stress-tests", "[.kernel-bmf-stress]") int C = 500; int N = 10; auto data = GENERATE_COPY(chunk(C * N, take(100000, random(1, 10)))); - - std::vector sys_cnst; - for (int i = 0; i < C; i++) { - sys_cnst.push_back(Sys.constraint_new(nullptr, 10)); - } - for (int j = 0; j < N; j++) { - lmm::Variable* rho = Sys.variable_new(nullptr, 1, -1, C); - for (int i = 0; i < C; i++) { - Sys.expand_add(sys_cnst[i], rho, data[i * j + j]); - } - } - Sys.solve(); + test_shared(C, N, 10, data); } Sys.variable_free_all(); -- 2.20.1