From: Martin Quinson Date: Tue, 19 Nov 2019 00:13:06 +0000 (+0100) Subject: Merge branch 'xbt_random' into 'master' X-Git-Tag: v3.25~386 X-Git-Url: http://info.iut-bm.univ-fcomte.fr/pub/gitweb/simgrid.git/commitdiff_plain/5089a0a98b27f5eeee62321dff4f025f1648f025?hp=c34ec0a9a237bf4befb762e35ab117731a8c3851 Merge branch 'xbt_random' into 'master' A module for RNG calls See merge request simgrid/simgrid!20 --- diff --git a/MANIFEST.in b/MANIFEST.in index bdcab2b3f8..af8fabfca3 100644 --- a/MANIFEST.in +++ b/MANIFEST.in @@ -2009,6 +2009,7 @@ include include/xbt/mallocator.h include include/xbt/misc.h include include/xbt/module.h include include/xbt/parmap.h +include include/xbt/random.hpp include include/xbt/range.hpp include include/xbt/replay.hpp include include/xbt/signal.hpp @@ -2590,6 +2591,8 @@ include src/xbt/mmalloc/mrealloc.c include src/xbt/mmalloc/swag.c include src/xbt/mmalloc/swag.h include src/xbt/parmap.cpp +include src/xbt/random.cpp +include src/xbt/random_test.cpp include src/xbt/snprintf.c include src/xbt/string.cpp include src/xbt/unit-tests_main.cpp diff --git a/examples/s4u/app-bittorrent/s4u-bittorrent.cpp b/examples/s4u/app-bittorrent/s4u-bittorrent.cpp index 899802c6be..47ecad6941 100644 --- a/examples/s4u/app-bittorrent/s4u-bittorrent.cpp +++ b/examples/s4u/app-bittorrent/s4u-bittorrent.cpp @@ -8,8 +8,6 @@ #include "s4u-peer.hpp" #include "s4u-tracker.hpp" -std::default_random_engine generator; - int main(int argc, char* argv[]) { simgrid::s4u::Engine e(&argc, argv); diff --git a/examples/s4u/app-bittorrent/s4u-bittorrent.hpp b/examples/s4u/app-bittorrent/s4u-bittorrent.hpp index 06fabfa086..126017acd3 100644 --- a/examples/s4u/app-bittorrent/s4u-bittorrent.hpp +++ b/examples/s4u/app-bittorrent/s4u-bittorrent.hpp @@ -7,8 +7,8 @@ #ifndef BITTORRENT_BITTORRENT_HPP_ #define BITTORRENT_BITTORRENT_HPP_ -#include #include +#include constexpr char TRACKER_MAILBOX[] = "tracker_mailbox"; /** Max number of peers sent by the tracker to clients */ @@ -77,6 +77,4 @@ public: : type(type), peer_id(peer_id), return_mailbox(return_mailbox), piece(piece){}; }; -extern std::default_random_engine generator; - #endif /* BITTORRENT_BITTORRENT_HPP_ */ diff --git a/examples/s4u/app-bittorrent/s4u-peer.cpp b/examples/s4u/app-bittorrent/s4u-peer.cpp index d3415ad8b6..a5e59bbc0e 100644 --- a/examples/s4u/app-bittorrent/s4u-peer.cpp +++ b/examples/s4u/app-bittorrent/s4u-peer.cpp @@ -446,8 +446,7 @@ int Peer::selectPieceToDownload(Connection* remote_peer) xbt_assert(nb_interesting_pieces != 0); // get a random interesting piece - std::uniform_int_distribution dist(0, nb_interesting_pieces - 1); - int random_piece_index = dist(generator); + int random_piece_index = simgrid::xbt::random::uniform_int(0, nb_interesting_pieces - 1); int current_index = 0; for (unsigned int i = 0; i < FILE_PIECES; i++) { if (hasNotPiece(i) && remote_peer->hasPiece(i)) { @@ -470,8 +469,7 @@ int Peer::selectPieceToDownload(Connection* remote_peer) nb_interesting_pieces++; xbt_assert(nb_interesting_pieces != 0); // get a random interesting piece - std::uniform_int_distribution dist(0, nb_interesting_pieces - 1); - int random_piece_index = dist(generator); + int random_piece_index = simgrid::xbt::random::uniform_int(0, nb_interesting_pieces - 1); int current_index = 0; for (unsigned int i = 0; i < FILE_PIECES; i++) { if (hasNotPiece(i) && remote_peer->hasPiece(i) && isNotDownloadingPiece(i)) { @@ -504,8 +502,7 @@ int Peer::selectPieceToDownload(Connection* remote_peer) // get a random rarest piece int random_rarest_index = 0; if (nb_min_pieces > 0) { - std::uniform_int_distribution dist(0, nb_min_pieces - 1); - random_rarest_index = dist(generator); + random_rarest_index = simgrid::xbt::random::uniform_int(0, nb_min_pieces - 1); } for (unsigned int i = 0; i < FILE_PIECES; i++) if (pieces_count[i] == min && hasNotPiece(i) && remote_peer->hasPiece(i) && isNotDownloadingPiece(i)) { @@ -555,8 +552,7 @@ void Peer::updateChokedPeers() do { // We choose a random peer to unchoke. std::unordered_map::iterator chosen_peer_it = connected_peers.begin(); - std::uniform_int_distribution dist(0, connected_peers.size() - 1); - std::advance(chosen_peer_it, dist(generator)); + std::advance(chosen_peer_it, simgrid::xbt::random::uniform_int(0, connected_peers.size() - 1)); chosen_peer = &chosen_peer_it->second; if (not chosen_peer->interested || not chosen_peer->choked_upload) chosen_peer = nullptr; diff --git a/examples/s4u/app-bittorrent/s4u-tracker.cpp b/examples/s4u/app-bittorrent/s4u-tracker.cpp index 390020a0b7..c4bfc168ce 100644 --- a/examples/s4u/app-bittorrent/s4u-tracker.cpp +++ b/examples/s4u/app-bittorrent/s4u-tracker.cpp @@ -52,8 +52,7 @@ void Tracker::operator()() while (tried < max_tries) { do { next_peer = known_peers.begin(); - std::uniform_int_distribution dist(0, nb_known_peers - 1); - std::advance(next_peer, dist(generator)); + std::advance(next_peer, simgrid::xbt::random::uniform_int(0, nb_known_peers - 1)); } while (ta->getPeers().find(*next_peer) != ta->getPeers().end()); ta->addPeer(*next_peer); tried++; diff --git a/examples/s4u/dht-chord/s4u-dht-chord-node.cpp b/examples/s4u/dht-chord/s4u-dht-chord-node.cpp index 1fa0c39b06..f76484cc29 100644 --- a/examples/s4u/dht-chord/s4u-dht-chord-node.cpp +++ b/examples/s4u/dht-chord/s4u-dht-chord-node.cpp @@ -134,7 +134,7 @@ void Node::notifyAndQuit() void Node::randomLookup() { int res = id_; - int random_index = generator() % nb_bits; + int random_index = simgrid::xbt::random::uniform_int(0, nb_bits - 1); int random_id = fingers_[random_index]; XBT_DEBUG("Making a lookup request for id %d", random_id); if (random_id != id_) diff --git a/examples/s4u/dht-chord/s4u-dht-chord.cpp b/examples/s4u/dht-chord/s4u-dht-chord.cpp index b8d20a71df..372c509bf6 100644 --- a/examples/s4u/dht-chord/s4u-dht-chord.cpp +++ b/examples/s4u/dht-chord/s4u-dht-chord.cpp @@ -11,8 +11,6 @@ int nb_bits = 24; int nb_keys = 0; int timeout = 50; -std::mt19937 generator; - int main(int argc, char* argv[]) { simgrid::s4u::Engine e(&argc, argv); diff --git a/examples/s4u/dht-chord/s4u-dht-chord.hpp b/examples/s4u/dht-chord/s4u-dht-chord.hpp index 81821cf8a3..eea1f2f41a 100644 --- a/examples/s4u/dht-chord/s4u-dht-chord.hpp +++ b/examples/s4u/dht-chord/s4u-dht-chord.hpp @@ -6,8 +6,8 @@ #ifndef S4U_CHORD_HPP #define S4U_CHORD_HPP #include "simgrid/s4u.hpp" -#include #include +#include #include constexpr double MAX_SIMULATION_TIME = 1000; @@ -21,8 +21,6 @@ extern int nb_bits; extern int nb_keys; extern int timeout; -extern std::mt19937 generator; - /* Types of tasks exchanged between nodes. */ enum e_message_type_t { FIND_SUCCESSOR, diff --git a/include/xbt/random.hpp b/include/xbt/random.hpp new file mode 100644 index 0000000000..3ca1db16e5 --- /dev/null +++ b/include/xbt/random.hpp @@ -0,0 +1,23 @@ +/* Copyright (c) 2019. The SimGrid Team. All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#ifndef SIMGRID_XBT_RANDOM_HPP +#define SIMGRID_XBT_RANDOM_HPP + +#include + +namespace simgrid { +namespace xbt { +namespace random { +int uniform_int(int, int); +double uniform_real(double, double); +double exponential(double); +double normal(double, double); +void set_mersenne_seed(int); +} // namespace random +} // namespace xbt +} // namespace simgrid + +#endif diff --git a/src/xbt/random.cpp b/src/xbt/random.cpp new file mode 100644 index 0000000000..63d5353ca1 --- /dev/null +++ b/src/xbt/random.cpp @@ -0,0 +1,69 @@ +/* Copyright (c) 2019. The SimGrid Team. All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#include "xbt/random.hpp" +#include "xbt/asserts.h" +#include +#include + +namespace simgrid { +namespace xbt { +namespace random { +std::mt19937 mt19937_gen; + +int uniform_int(int min, int max) +{ + unsigned long gmin = mt19937_gen.min(); + unsigned long gmax = mt19937_gen.max(); + unsigned long grange = gmax - gmin + 1; + unsigned long range = max - min + 1; + xbt_assert( + min < max || min == max, + "The maximum value for the uniform integer distribution must be greater than or equal to the minimum value"); + xbt_assert(range < grange || range == grange, "The current implementation of the uniform integer distribution does " + "not allow range to be higher than mt19937's range"); + unsigned long mult = grange / range; + unsigned long maxallowed = gmin + (mult + 1) * range - 1; + while (true) { + unsigned long value = mt19937_gen(); + if (value > maxallowed) { + } else { + return value % range + min; + } + } +} + +double uniform_real(double min, double max) +{ + // This reuses Boost's uniform real distribution ideas + unsigned long numerator = mt19937_gen() - mt19937_gen.min(); + unsigned long divisor = mt19937_gen.max() - mt19937_gen.min(); + return min + (max - min) * numerator / divisor; +} + +double exponential(double lambda) +{ + return -1 / lambda * log(uniform_real(0, 1)); +} + +double normal(double mean, double sd) +{ + double u1 = 0; + while (u1 < std::numeric_limits::min()) { + u1 = uniform_real(0, 1); + } + double u2 = uniform_real(0, 1); + double z0 = sqrt(-2.0 * log(u1)) * cos(2 * M_PI * u2); + return z0 * sd + mean; +} + +void set_mersenne_seed(int seed) +{ + mt19937_gen.seed(seed); +} + +} // namespace random +} // namespace xbt +} // namespace simgrid diff --git a/src/xbt/random_test.cpp b/src/xbt/random_test.cpp new file mode 100644 index 0000000000..c93049b8b0 --- /dev/null +++ b/src/xbt/random_test.cpp @@ -0,0 +1,21 @@ +/* Copyright (c) 2019. The SimGrid Team. All rights reserved. */ + +/* This program is free software; you can redistribute it and/or modify it + * under the terms of the license (GNU LGPL) which comes with this package. */ + +#include "src/include/catch.hpp" +#include "xbt/log.h" +#include "xbt/random.hpp" + +TEST_CASE("xbt::random: Random Number Generation") +{ + SECTION("Random") + { + simgrid::xbt::random::set_mersenne_seed(12345); + + REQUIRE(simgrid::xbt::random::exponential(25) == 0.00291934351538427348); + REQUIRE(simgrid::xbt::random::uniform_int(1, 6) == 4); + REQUIRE(simgrid::xbt::random::uniform_real(0, 1) == 0.31637556043369124970); + REQUIRE(simgrid::xbt::random::normal(0, 2) == 1.62746784745133976635); + } +} diff --git a/tools/cmake/DefinePackages.cmake b/tools/cmake/DefinePackages.cmake index a5980b5d7a..b35053688e 100644 --- a/tools/cmake/DefinePackages.cmake +++ b/tools/cmake/DefinePackages.cmake @@ -283,6 +283,7 @@ set(XBT_SRC src/xbt/memory_map.hpp src/xbt/OsSemaphore.hpp src/xbt/parmap.cpp + src/xbt/random.cpp src/xbt/snprintf.c src/xbt/string.cpp src/xbt/xbt_log_appender_file.cpp @@ -774,6 +775,7 @@ set(headers_to_install include/xbt/module.h include/xbt/parmap.h include/xbt/range.hpp + include/xbt/random.hpp include/xbt/replay.hpp include/xbt/signal.hpp include/xbt/str.h diff --git a/tools/cmake/Tests.cmake b/tools/cmake/Tests.cmake index e40775287e..b430dea117 100644 --- a/tools/cmake/Tests.cmake +++ b/tools/cmake/Tests.cmake @@ -105,6 +105,7 @@ set(UNIT_TESTS src/xbt/unit-tests_main.cpp src/xbt/config_test.cpp src/xbt/dict_test.cpp src/xbt/dynar_test.cpp + src/xbt/random_test.cpp src/xbt/xbt_str_test.cpp src/kernel/lmm/maxmin_test.cpp) if (SIMGRID_HAVE_MC)