Inside Bitcoin

501 *  * Register pressure: 4
502 *  * State size: 128 bits
503 *
504 * This random generator is a drop-in replacement for the generators supplied by ``<random>``. It is not
505 * cryptographically secure. It's intended purpose is to be very fast so that benchmarks that make use
506 * of randomness are not distorted too much by the random generator.
507 *
508 * Rng also provides a few non-standard helpers, optimized for speed.
509 */
510class Rng final {
511public:
512    /**
513     * @brief This RNG provides 64bit randomness.
514     */
515    using result_type = uint64_t;
516
517    static constexpr uint64_t(min)();
518    static constexpr uint64_t(max)();
519
520    /**
521     * As a safety precaution, we don't allow copying. Copying a PRNG would mean you would have two random generators that produce the
522     * same sequence, which is generally not what one wants. Instead create a new rng with the default constructor Rng(), which is
523     * automatically seeded from `std::random_device`. If you really need a copy, use `copy()`.
524     */
525    Rng(Rng const&) = delete;
526
527    /**
528     * Same as Rng(Rng const&), we don't allow assignment. If you need a new Rng create one with the default constructor Rng().
529     */
530    Rng& operator=(Rng const&) = delete;
531
532    // moving is ok
533    Rng(Rng&&) noexcept = default;
534    Rng& operator=(Rng&&) noexcept = default;
535    ~Rng() noexcept = default;
536
537    /**
538     * @brief Creates a new Random generator with random seed.
539     *
540     * Instead of a default seed (as the random generators from the STD), this properly seeds the random generator from
541     * `std::random_device`. It guarantees correct seeding. Note that seeding can be relatively slow, depending on the source of
542     * randomness used. So it is best to create a Rng once and use it for all your randomness purposes.
543     */
544    Rng();
545
546    /*!
547      Creates a new Rng that is seeded with a specific seed. Each Rng created from the same seed will produce the same randomness
548      sequence. This can be useful for deterministic behavior.
549
550      @verbatim embed:rst
551      .. note::
552
553         The random algorithm might change between nanobench releases. Whenever a faster and/or better random
554         generator becomes available, I will switch the implementation.
555      @endverbatim
556
557      As per the Romu paper, this seeds the Rng with splitMix64 algorithm and performs 10 initial rounds for further mixing up of the
558      internal state.
559
560      @param seed  The 64bit seed. All values are allowed, even 0.
561     */
562    explicit Rng(uint64_t seed) noexcept;
563    Rng(uint64_t x, uint64_t y) noexcept;
564    explicit Rng(std::vector<uint64_t> const& data);
565
566    /**
567     * Creates a copy of the Rng, thus the copy provides exactly the same random sequence as the original.
568     */
569    ANKERL_NANOBENCH(NODISCARD) Rng copy() const noexcept;
570
571    /**
572     * @brief Produces a 64bit random value. This should be very fast, thus it is marked as inline. In my benchmark, this is ~46 times
573     * faster than `std::default_random_engine` for producing 64bit random values. It seems that the fastest std contender is
574     * `std::mt19937_64`. Still, this RNG is 2-3 times as fast.
575     *
576     * @return uint64_t The next 64 bit random value.
577     */
578    inline uint64_t operator()() noexcept;
579
580    // This is slightly biased. See
581
582    /**
583     * Generates a random number between 0 and range (excluding range).
584     *
585     * The algorithm only produces 32bit numbers, and is slightly biased. The effect is quite small unless your range is close to the
586     * maximum value of an integer. It is possible to correct the bias with rejection sampling (see
587     * [here](https://lemire.me/blog/2016/06/30/fast-random-shuffling/), but this is most likely irrelevant in practices for the
588     * purposes of this Rng.
589     *
590     * See Daniel Lemire's blog post [A fast alternative to the modulo
591     * reduction](https://lemire.me/blog/2016/06/27/a-fast-alternative-to-the-modulo-reduction/)
592     *
593     * @param range Upper exclusive range. E.g a value of 3 will generate random numbers 0, 1, 2.
594     * @return uint32_t Generated random values in range [0, range(.
595     */
596    inline uint32_t bounded(uint32_t range) noexcept;
597
598    // random double in range [0, 1(
599    // see http://prng.di.unimi.it/
600
601    /**
602     * Provides a random uniform double value between 0 and 1. This uses the method described in [Generating uniform doubles in the
603     * unit interval](http://prng.di.unimi.it/), and is extremely fast.
604     *
605     * @return double Uniformly distributed double value in range [0,1(, excluding 1.
606     */
607    inline double uniform01() noexcept;
608
609    /**
610     * Shuffles all entries in the given container. Although this has a slight bias due to the implementation of bounded(), this is
611     * preferable to `std::shuffle` because it is over 5 times faster. See Daniel Lemire's blog post [Fast random
612     * shuffling](https://lemire.me/blog/2016/06/30/fast-random-shuffling/).
613     *
614     * @param container The whole container will be shuffled.
615     */
616    template <typename Container>
617    void shuffle(Container& container) noexcept;
618
619    /**
620     * Extracts the full state of the generator, e.g. for serialization. For this RNG this is just 2 values, but to stay API compatible
621     * with future implementations that potentially use more state, we use a vector.
622     *
623     * @return Vector containing the full state:
624     */
625    ANKERL_NANOBENCH(NODISCARD) std::vector<uint64_t> state() const;
626
627private:
628    static constexpr uint64_t rotl(uint64_t x, unsigned k) noexcept;
629
630    uint64_t mX;
631    uint64_t mY;
632};
633
634/**
635 * @brief Main entry point to nanobench's benchmarking facility.
636 *
637 * It holds configuration and results from one or more benchmark runs. Usually it is used in a single line, where the object is
638 * constructed, configured, and then a benchmark is run. E.g. like this:
639 *
640 *     ankerl::nanobench::Bench().unit("byte").batch(1000).run("random fluctuations", [&] {
641 *         // here be the benchmark code
642 *     });
643 *
644 * In that example Bench() constructs the benchmark, it is then configured with unit() and batch(), and after configuration a
645 * benchmark is executed with run(). Once run() has finished, it prints the result to `std::cout`. It would also store the results
646 * in the Bench instance, but in this case the object is immediately destroyed so it's not available any more.
647 */
648ANKERL_NANOBENCH(IGNORE_PADDED_PUSH)
649class Bench {
650public:
651    /**
652     * @brief Creates a new benchmark for configuration and running of benchmarks.
653     */
654    Bench();
655
656    Bench(Bench&& other) noexcept;
657    Bench& operator=(Bench&& other) noexcept(ANKERL_NANOBENCH(NOEXCEPT_STRING_MOVE));
658    Bench(Bench const& other);
659    Bench& operator=(Bench const& other);
660    ~Bench() noexcept;
661
662    /*!
663      @brief Repeatedly calls `op()` based on the configuration, and performs measurements.
664
665      This call is marked with `noinline` to prevent the compiler to optimize beyond different benchmarks. This can have quite a big
666      effect on benchmark accuracy.
667
668      @verbatim embed:rst
669      .. note::
670
671        Each call to your lambda must have a side effect that the compiler can't possibly optimize it away. E.g. add a result to an
672        externally defined number (like `x` in the above example), and finally call `doNotOptimizeAway` on the variables the compiler
673        must not remove. You can also use :cpp:func:`ankerl::nanobench::doNotOptimizeAway` directly in the lambda, but be aware that
674        this has a small overhead.
675
676      @endverbatim
677
678      @tparam Op The code to benchmark.
679     */
680    template <typename Op>
681    ANKERL_NANOBENCH(NOINLINE)
682    Bench& run(char const* benchmarkName, Op&& op);
683
684    template <typename Op>
685    ANKERL_NANOBENCH(NOINLINE)
686    Bench& run(std::string const& benchmarkName, Op&& op);
687
688    /**
689     * @brief Same as run(char const* benchmarkName, Op op), but instead uses the previously set name.
690     * @tparam Op The code to benchmark.
691     */
692    template <typename Op>
693    ANKERL_NANOBENCH(NOINLINE)
694    Bench& run(Op&& op);
695
696    /**
697     * @brief Title of the benchmark, will be shown in the table header. Changing the title will start a new markdown table.
698     *
699     * @param benchmarkTitle The title of the benchmark.
700     */
701    Bench& title(char const* benchmarkTitle);
702    Bench& title(std::string const& benchmarkTitle);
703
704    /**
705     * @brief Gets the title of the benchmark
706     */
707    ANKERL_NANOBENCH(NODISCARD) std::string const& title() const noexcept;
708
709    /// Name of the benchmark, will be shown in the table row.
710    Bench& name(char const* benchmarkName);
711    Bench& name(std::string const& benchmarkName);
712    ANKERL_NANOBENCH(NODISCARD) std::string const& name() const noexcept;
713
714    /**
715     * @brief Set context information.
716     *
717     * The information can be accessed using custom render templates via `{{context(variableName)}}`.
718     * Trying to render a variable that hasn't been set before raises an exception.
719     * Not included in (default) markdown table.
720     *
721     * @see clearContext, render
722     *
723     * @param variableName The name of the context variable.
724     * @param variableValue The value of the context variable.
725     */
726    Bench& context(char const* variableName, char const* variableValue);
727    Bench& context(std::string const& variableName, std::string const& variableValue);
728
729    /**
730     * @brief Reset context information.
731     *
732     * This may improve efficiency when using many context entries,
733     * or improve robustness by removing spurious context entries.
734     *
735     * @see context
736     */
737    Bench& clearContext();
738
739    /**
740     * @brief Sets the batch size.
741     *
742     * E.g. number of processed byte, or some other metric for the size of the processed data in each iteration. If you benchmark
743     * hashing of a 1000 byte long string and want byte/sec as a result, you can specify 1000 as the batch size.
744     *
745     * @tparam T Any input type is internally cast to `double`.
746     * @param b batch size
747     */
748    template <typename T>
749    Bench& batch(T b) noexcept;
750    ANKERL_NANOBENCH(NODISCARD) double batch() const noexcept;