Difference between revisions of "Random number generation"

From reSIProcate
Jump to: navigation, search
(new page, early draft)
 
(another draft)
Line 1: Line 1:
This section describes some options and performance measurements of the rutil/Random class.
+
Configuration and performance of the rutil/Random class.
  
The Random class has compile time options to control how it generates random numbers. It is control via pre-process symbols, defined either by changing Random.hxx or in the build environment.
+
[This describes changes not yet committed to SVN. -- kennard]
  
 +
== Configuration ==
  
The choices are:
+
The Random class has compile time options to control how it generates random numbers. It is configured via pre-processor symbols, defined either by changing Random.hxx or in the build environment.
 +
 
 +
The configuration choices primarily affect how multi-threaded applications behave. The behavior is important because the Random class is used to generate SIP CallIds, branch identifiers, and (from/to) tags.
 +
 
 +
The options are described below. See Random.hxx for most up-to-date descriptions.
  
 
[WIN32-default]
 
[WIN32-default]
Line 10: Line 15:
  
 
RESIP_RANDOM_WIN32_RTL
 
RESIP_RANDOM_WIN32_RTL
The Random class uses Window's RtlGenRandom (aka SystemFunction036) on XP and higher system, and fallsback to rand() on older Windows platforms.
+
The Random class uses Window's RtlGenRandom (aka SystemFunction036) on XP and higher system, and falls back to rand() on older Windows platforms.
  
 
[POSIX-default]
 
[POSIX-default]
The Random class uses libc's random().
+
The Random class uses libc's random(). The random state is shared across all threads and all libraries of the application. While Linux's libc implementation has an internal mutex for thread protection, POSIX doesn't require this and other platforms may have corruption. Also, any part of the application may "corrupt" the state by calling srandom with "stupid" values.
  
 
RESIP_RANDOM_THREAD_MUTEX
 
RESIP_RANDOM_THREAD_MUTEX
The Random class itself keeps a Mutex, and will lock the mutex prior to calling random_r().  
+
The Random class itself keeps a Mutex, and will lock the mutex prior to calling random_r(). Of course, this requires that the platform support random_r(). This provides assured thread-safety. Also, the random state is private to resiprocate, and other parts of the application cannot corrupt it.
  
 
RESIP_RANDOM_THREAD_LOCAL
 
RESIP_RANDOM_THREAD_LOCAL
The Random class allocate state for each thread and tracks that using ThreadLocalStorage.
+
The Random class allocate state for each thread and tracks that using ThreadLocalStorage. As above, this requires that the platform support random_r(). This avoids serialization among threads (no mutex), and also prevents corruption by non-resiprocate parts of the application.
  
  
 
== Linux Performance results ==
 
== Linux Performance results ==
 +
 +
See rutil/test/{testRandomThread.cxx,sweepRandom.sh} for details.
 +
 +
The test program starts T threads, and runs C cycles in each thread, where each cycle generates one million random integers (each integer is 32 bits). It then reports the total time from start of all the threads to completion of the last one. With respect to the number of threads, there are some special cases. Values of T (number of threads):
 +
* -1. The test is run in the main process, without creating any child threads.
 +
*  0. The test is run in the main process, but there is also a dummy thread hanging around doing nothing. Turns out this makes a difference, because libc's mutex protection of random() optimizes for the single-thread case.
 +
* 1. The test is run in a child process, and the main process does nothing.
 +
* N. Each child process generates C cycles of random numbers, and main process does nothing.
 +
 +
[[File:RandomPerfResult-1.jpg]]

Revision as of 00:01, 8 February 2011

Configuration and performance of the rutil/Random class.

[This describes changes not yet committed to SVN. -- kennard]

Configuration

The Random class has compile time options to control how it generates random numbers. It is configured via pre-processor symbols, defined either by changing Random.hxx or in the build environment.

The configuration choices primarily affect how multi-threaded applications behave. The behavior is important because the Random class is used to generate SIP CallIds, branch identifiers, and (from/to) tags.

The options are described below. See Random.hxx for most up-to-date descriptions.

[WIN32-default] The Random class uses rand().

RESIP_RANDOM_WIN32_RTL The Random class uses Window's RtlGenRandom (aka SystemFunction036) on XP and higher system, and falls back to rand() on older Windows platforms.

[POSIX-default] The Random class uses libc's random(). The random state is shared across all threads and all libraries of the application. While Linux's libc implementation has an internal mutex for thread protection, POSIX doesn't require this and other platforms may have corruption. Also, any part of the application may "corrupt" the state by calling srandom with "stupid" values.

RESIP_RANDOM_THREAD_MUTEX The Random class itself keeps a Mutex, and will lock the mutex prior to calling random_r(). Of course, this requires that the platform support random_r(). This provides assured thread-safety. Also, the random state is private to resiprocate, and other parts of the application cannot corrupt it.

RESIP_RANDOM_THREAD_LOCAL The Random class allocate state for each thread and tracks that using ThreadLocalStorage. As above, this requires that the platform support random_r(). This avoids serialization among threads (no mutex), and also prevents corruption by non-resiprocate parts of the application.


Linux Performance results

See rutil/test/{testRandomThread.cxx,sweepRandom.sh} for details.

The test program starts T threads, and runs C cycles in each thread, where each cycle generates one million random integers (each integer is 32 bits). It then reports the total time from start of all the threads to completion of the last one. With respect to the number of threads, there are some special cases. Values of T (number of threads):

  • -1. The test is run in the main process, without creating any child threads.
  • 0. The test is run in the main process, but there is also a dummy thread hanging around doing nothing. Turns out this makes a difference, because libc's mutex protection of random() optimizes for the single-thread case.
  • 1. The test is run in a child process, and the main process does nothing.
  • N. Each child process generates C cycles of random numbers, and main process does nothing.

File:RandomPerfResult-1.jpg