Generate 75,000,000 + Random Numbers Fast

[Ethan_145]

I'm making a game in Python, where two armies battle each other. The soldiers both spray arrows at each other. But for each soldier, there is a 1 in 15,000 chance every frame them firing. One thing I noticed was the FPS dropped from 60 to less than 3. Both armies combined have about 5,000 soldiers, so that means about 75,000,000 random numbers are generated every frame. Is there a way I can generate huge amounts of random numbers efficiently? I was using the randrange function, which is pretty slow. I plan to expand the armies, but it seems hopeless.

[JamesCherrill]

With 5000 soldiers that should be 5000 random numbers. The 1/15000 chance requires just one random number.

[pritaeas]

What he said, and if you do need a lot of random numbers, generate a huge fifo queue beforehand and while you're using them just take the next one and add a new one.

[Reverend Jim]

That sounds like the perfect scenario to create a thread that generates the random numbers. That would allow the generation to be done concurrently with your game. The thread could maintain a queue of n random numbers, automatically generating new numbers to maintain the pool as you make pull requests. If you don't know how to do this I could help you out. Coincidentally I am currently making my way through "Quan Nguyen - Mastering Concurrency in Python".

[Ethan_145]

How would I do that?

[Reverend Jim]

I'm just coding it up. I'll post it with comments shortly.

[Reverend Jim]

"""
Name:

    Thread.py

Description:

    Simple (I hope) example of how to run a piece of code in a separate thread.
    This code is the result of a question from a user who needed to generate
    many random numbers, but found it was slowing his application down.

    Random_Pool subclasses threading.Thread. To create a self-filling pool of
    random numbers you create a Random_Pool object, giving it the maximum pool
    size, and the minimum and maximum integer values you want to generate. You
    can also give it a name.

    To start auto-generating random numbers you use the start method. You do
    not call run directly.

    To get a random number call get_num()

    The test for whether the pool is less than full runs on a 0.01 second
    sleep loop.

    When you are done with the pool you have to tell the run method to complete.
    You do this by calling the set_done() method. Following that you must join
    the pool thread to the main thread by calling join().

    Comment out the print statements for production code.

Audit:

    2022-07-08  rj  original code
"""

import threading
import random
import time


class Random_Pool(threading.Thread):
    def __init__(self, name='pool', max_size=100, min_num=0, max_num=1000):
        threading.Thread.__init__(self)
        self.name = name

        self.pool  = []         # a list containing the generated random numbers
        self.size  = max_size   # maximum number of random numbers at any given time
        self.min   = min_num    # minimum random integer to generate
        self.max   = max_num    # maximum random integer to generate
        self.done  = False      # when True the run method will complete

    def run(self):
        """
        This method should never be called directly. This method tests to see
        if the pool needs topping up. There is a 0.01 second delay between
        each test. This can be adjusted to tweak performance.
        """
        print('Starting thread %s.' % self.name)
        while not self.done:
            while len(self.pool) < self.size:
                self.pool.append(random.randrange(self.min, self.max + 1))
                print(f'generated item {len(self.pool)}')
            time.sleep(.01)
        print('Finished thread %s.' % self.name)

    def get_num(self):
        """
        Return the next available random number from the pool. If the
        pool is empty, wait until a number is available.
        """
        while len(self.pool) == 0:
            time.sleep(.01)
        return self.pool.pop()

    def get_size(self):
        """
        Return the current number of random numbers in the pool.
        """
        return len(self.pool)

    def set_done(self):
        """
        Set a flag that will cause the run method to complete.
        """
        self.done = True

# Create a thread to generate a pool of random numbers between 0 and 1000
pool = Random_Pool(max_size=100, min_num=0, max_num=1000)
pool.start()

# Any code put here will run concurrently with Random_Pool

# Clean up the pool. Tell the run method it can complete, then join the
# thread to the main thread.
pool.set_done()
pool.join()

The generation of the pool begins when you run pool.start(). You can set the value (in seconds) of the delay in case you have performance issues. If you run this code in idle and comment out the last two lines you can interact with the pool to see how it behaves. The last two lines will cause the thread to exit.

pool.get_num() returns the next available random number. If the pool is empty it waits for a number to be generated.

I'll check back in a while in case you have questions.

[JamesCherrill]

Time for a reality check.
Generating a pseudo random number is one multiplication, one addition, one modulo.
It’s a fast as a function can be.
You can’t make it faster by adding the overhead of storing and retrieving values. The use of sleep to synchronise around an empty pool will utterly destroy the performance when large quantities of values are needed quickly; that needs proper synchronisation which will bring its own overheads. Yes, you can potentially gain 2x performance by using two cores concurrently, but I’m pretty sure the overheads will be greater than 2x.

Pritaeas’ original suggestion was to pre-compute a pool of numbers. The o.p. Wants 75,000,000 numbers every 16 mSec. So a pre-computed pool of (say) a billion numbers (4 GB minimum) will last less than 1/4 second. After that all you have is overhead slowing things down.

The real question is why does o.p. Think he needs 75,000,000 random numbers? That’s almost certainly based on some kind of misconception, and that’s what we should be addressing.

[rproffitt]

Flip the equation. 2,500 soldiers have a 1 in 15K chance to fire per frame. or 2500 in 15000. To get to 15000 in 15000, that's 6 frames for a random arrow. Or 1/10th of a second per arrow.
I only need one random number every 1/10th of a second to select which soldier fired.

[Reverend Jim]

My fault on that. For some reason I was thinking 75 thousand, not million. The concurrency aspect intrigued me.

[JamesCherrill]

I'm no Pythonista, but if I understand it correctly there's a Queue class that is designed to be thread safe for concurrent producers and consumers. That would make the code very simple (eg, producer simply sits in a loop and blocks when queue is full, consumer simply blocks until a value is available).

[Reverend Jim]

I haven't gotten to that chapter yet ;-)

[Ethan_145]

I have several different types of soldiers, like archers and light infantry. Could I make it so that archers shoot more often than regular light infantry or heavy infantry? BTW I had a typo in a reply. I don't know how to fix that. I just recently tried out the Pool. Unfortunately, the FPS was even lower, at about 5.

My code structure is like this. I have a file that holds the Pool class and functions, and another that defines but does not create the soldiers and arrows. Finally, I have another file that runs and displays everything. Currently, I initialize the pool at the beginning of the file where I define the soldiers. On each of their update loops, I pick a number from the pool using get_num() and see if it is one. If it is, then the soldier fires an arrow. If not, the soldier does nothing. Note that this is a ginormous pool, with 100,000 items and a max value of 100,000. I think I may be using get_num incorrectly.

if len(self.window.projectile_list) < 20: # Checks if there is fewer than twenty arrows
    if pool.get_num() == 1:
        self.on_attack() # Fire arrow

        break # Return from loop to keep from firing repeatedly

[Dani]

I think the goal should be to create the illusion to the gamer that so much is going on simultaneously when, in fact, a lot of things are over-simplified, not truly random, etc. behind the scenes.

[JamesCherrill]

Unfortunately, the FPS was even lower, at about 5.

That’s inevitable. The overheads of maintaining the pool greatly exceed the cost of creating each random number. That approach is not going to work for you.

archers shoot more often…

For each type of soldier define a mean time to fire (some number of seconds). Then in your main update do something like (pseudo-code)

for each soldier in the game
   if random.random() < 1/(soldier.timeToFire*frameRate)
      soldier.fireWeapon

That’s just one call to random per soldier, so fast you won’t be able to measure it.

[Ethan_145]

This approach does work better than the Pool, but the FPS is at about 15. I was wishing for the FPS to be about fifty. My code is like this. It is called every frame for every soldier. I'm going to make it that firing called for the list of soldiers, not individually. That would mean only 60 RNs per frame.

for enemy in self.enemies:
    if enemy.health > 0: # Enemy still alive
        rate = 4000
        if self.archer: rate = 3000

        if len(self.window.projectile_list) < 20: # Fewer than twenty arrows
            if random() < 1 / rate:     #
                if random() < 1 / rate: # Reduce amount of random numbers
                    self.on_attack() # Fire

                break # Stop from spamming arrows 

[Reverend Jim]

50 FPS seems like overkill.

[toneewa]

My advice is learn about threads to do it in real-time. Otherwise, load/generate everything that is needed, before you start battles. Then, see what direction you need to go. Benchmarking your design is just part of the process.

[JamesCherrill]

I don't understand the need for both line 7 and line 8 but anyway...
In that code the random number generation is not significant to the execution speed; it's utterly trivial.
Whatever is slowing down your code, it's not random()

FYI my Mac mini will generate just under 50 million random numbers per second using a single thread, an average of 21 nanoSeconds per call.

[Ethan_145]

I found a way to call it for the list of soldiers, where it would generate a random number, and if it equaled something, it would pick a random soldier to fire an arrow. I used the Pool to generate the random number, and some Cython to speed some things up. The FPS is now at about sixty or fifty, so it looks good performance-wise.

[toneewa]

Recommended hardware, system requirements to run the game, should be gathered with benchmarks. This could be a built-in debug mode.

2.88 million random numbers / second. 60 fps / # of soilders. 2.88mil/60/5k = 9.6 random numbers per frame per soilder
8 million random numbers / second. 60 fps / # of soilders. 8mil/60/5k = 26.6 random numbers per frame per soilder
28 milllion random numbers / second. 60 fps / # of soilders. 28mil/60/5k = 93.3 random numbers per frame per soilder
50 million random numbers / second. 60 fps / # of soilders. 50mil/60/5k = 166.6 random numbers per frame per soilder
75 million random numbers / second. 60 fps / # of soilders. 75mil/60/5k = 250 random numbers per frame per soilder

import random
import time  

start = time.process_time()
for zero in range(75000000):
    random.random()
end = time.process_time()
print((end - start),"sec")
rn = 75000000
rate = rn/(end - start)
frame_rate = rate / 60 / 5000
print((rate), "random numbers / sec")
print(frame_rate, "rn/f/s")