Project

General

Profile

Feature #1107

Investigate into faster modes of random number aquisation

Added by Oliver Maurhart over 1 year ago. Updated over 1 year ago.

Status:
New
Priority:
Low
Assignee:
-
Target version:
Start date:
10.08.2016
Due date:
% Done:

0%


Description

I'm currently investigating a huge performance drop. Don't know what's happening yet, but I encountered some quirks.

While running cascade (test/bin/modules/test-mod-cascade) I found out, that the current random number delivery (qkd::random::random_c_api::get()) is responsible for 33,64 % (!!) of the run time. This method is solely called by qkd_cascade::qkd_cascade_data::generate_random_permutation().

Huh?!?? o.O

Within qkd::random::random_c_api::get() about 84,34% is "wasted" on the rand() call into the libc.

-> todo: think about new ways to speed up random number get.

(did this with valgrind --tool=callgrind on the test scripts)

rand_vs_rdrand.cpp Magnifier (1.51 KB) Oliver Maurhart, 11.08.2016 10:28

rand_vs_rdrand.cpp Magnifier (1.51 KB) Oliver Maurhart, 07.09.2016 10:25

History

#1 Updated by Oliver Maurhart over 1 year ago

As this the test-mod-cascade on a single Intel(R) Xeon(R) CPU E5-2680 v3 @ 2.50GHz needs 215,83 sec (!!). This is cascade with 100 keys each 4kbit of size and a QBER of 3%.

Puhh...

An alternative could be using RDRAND instruction set: https://en.wikipedia.org/wiki/RdRand which is supported by OpenSSL: https://software.intel.com/en-us/articles/how-to-use-the-rdrand-engine-in-openssl-for-random-number-generation.

But I do not have any tests yet done.

#2 Updated by Oliver Maurhart over 1 year ago

Run some tests: get 1.000.000 random bytes.

Compile the attached file with

$ g++ -std=c++11 rand_vs_rdrand.cpp -l ssl -l crypto

It yields:
c_rand lastet: 11479202 ns
rdrand lastet: 6370216 ns

So, RDRAND seems to be about twice as fast as rand() of the C API.

I wonder, if there's a speedup if we create one big block of random numbers instead of requesting a new one each time.

#3 Updated by Oliver Maurhart over 1 year ago

  • Priority changed from Normal to Low

Changed prio to "low" since this is not a blocker or some urgent task.

#5 Updated by Oliver Maurhart over 1 year ago

Or again an OpenSSL free usage of RDRAND with inline assembly: https://software.intel.com/en-us/articles/intel-digital-random-number-generator-drng-software-implementation-guide (at section 4.2.2).

#6 Updated by Oliver Maurhart over 1 year ago

Did:

#include <iostream>
#include <chrono>

#include <openssl/engine.h>

#define RANDOM_NUMBERS 1000000

void c_rand() {

    auto start = std::chrono::high_resolution_clock::now();

    for (unsigned long i = 0; i < RANDOM_NUMBERS; ++i) {
        rand();
    }

    auto end = std::chrono::high_resolution_clock::now();
    auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start);
    std::cout << "c_rand lastet: " << duration.count() << " ns" << std::endl;
}

void rdrand() {

    ENGINE * engine;
    ENGINE_load_rdrand();

    engine = ENGINE_by_id("rdrand");
    if (!engine) {
        std::cerr << "failed to load rdrand engine" << std::endl;
        exit(1);
    }
    if (!ENGINE_init(engine)) {
        std::cerr << "failed to init rdrand engine" << std::endl;
        exit(1);
    }
    if (!ENGINE_set_default(engine, ENGINE_METHOD_RAND)) {
        std::cerr << "failed to set rdrand engine as default" << std::endl;
        exit(1);
    }

    unsigned char buffer[RANDOM_NUMBERS];

    auto start = std::chrono::high_resolution_clock::now();

    RAND_bytes(buffer, RANDOM_NUMBERS);

    auto end = std::chrono::high_resolution_clock::now();

    ENGINE_finish(engine);
    ENGINE_free(engine);
    ENGINE_cleanup();

    auto duration = std::chrono::duration_cast<std::chrono::nanoseconds>(end - start);
    std::cout << "rdrand lastet: " << duration.count() << " ns" << std::endl;
}

int main(int argc, char ** argv) {

    c_rand();
    rdrand();

    return 0;
}

which yielded:

$ ./a.out
c_rand lastet: 35569745 ns
rdrand lastet: 17422215 ns

So a speedup of about 2 when using RDRAND.

Also available in: Atom PDF