Angband.oook.cz
Angband.oook.cz
AboutVariantsLadderForumCompetitionComicScreenshotsFunniesLinks

Go Back   Angband Forums > Angband > Development

Reply
 
Thread Tools Display Modes
Old August 16, 2016, 23:33   #21
AnonymousHero
Veteran
 
AnonymousHero's Avatar
 
Join Date: Jun 2007
Posts: 1,365
AnonymousHero is on a distinguished road
Quote:
Originally Posted by rhutson View Post
As for the 28 bit limitation, that can now be safely and trivially bumped up to a more classic 31 bit limitation. If it is really an issue, email me, and I'll email you back some diffs. But any major rewrite of known working code in such a vital section of the game for no obvious reason would be an ill-advised waste of time.
Funnily enough, my interest in this was only tangential and coincidental to replacing the (really, really old) RNG in the ToME 2.x codebase. I've replaced it with a PCG family RNG which gives me a standard C++ interface which means i also get randnor() without any 'weird' tables, etc. It's all good from my perspective .

I mostly wanted the replacement for the same somewhat perverse reasons as yourself, but I also want to reduce the amount of "in-house" code and since PCG is a header-only implementation, it's completely trivial to include it.

(I haven't yet pushed this to the public GH repo. I should probably start gathering commits to push...)
AnonymousHero is offline   Reply With Quote
Old August 16, 2016, 23:45   #22
rhutson
Rookie
 
Join Date: Jul 2013
Location: In the Misty Mountains
Posts: 23
rhutson is on a distinguished road
Good news everyone!

I morphed z-rand.c into a Rand_div() speed test and study program. My memory of prior testing and claim that any attempt at optimizing my algorithm any further could not even be measured in a full microseconds have been validated! And I expanded the range and domain of Rand_div into 31 bit territory as well.

My speed test and the loop test reults on a 2.6 GHz Intel Core i5 compiled with clang -O2 on OS X 10.11.6 :

Code:
Newton- 1:39PM-s009 ~/src/angband/src% time ./a.out 2
1000000000 calls, 1000000000 loop entries, test and branch success rate of  0.00000000%
./a.out 2  14.03s user 0.02s system 99% cpu 14.082 total
Newton- 1:40PM-s009 ~/src/angband/src% printf '< %.2f microseconds per call\n' $((14.03 / 1000000000 * 1000000))
< 0.01 microseconds per call
Newton- 1:40PM-s009 ~/src/angband/src% time ./a.out 100                                                         
1000000000 calls, 1000000024 loop entries, test and branch success rate of  0.00000240%
./a.out 100  14.00s user 0.02s system 99% cpu 14.046 total
Newton- 1:40PM-s009 ~/src/angband/src% time ./a.out 100000000
1000000000 calls, 1022613980 loop entries, test and branch success rate of  2.26139800%
./a.out 100000000  14.50s user 0.02s system 99% cpu 14.550 total
Newton- 1:42PM-s009 ~/src/angband/src% printf '< %.2f microseconds per call\n' $((14.5 / 1000000000 * 1000000))
< 0.01 microseconds per call
Newton- 1:42PM-s009 ~/src/angband/src% time ./a.out 100000001                                                  
1000000000 calls, 1022608062 loop entries, test and branch success rate of  2.26080620%
./a.out 100000001  14.50s user 0.02s system 99% cpu 14.554 total
Newton- 1:48PM-s009 ~/src/angband/src% time ./a.out 200000001
1000000000 calls, 1073732253 loop entries, test and branch success rate of  7.37322530%
./a.out 200000001  15.69s user 0.03s system 99% cpu 15.747 total
Newton- 1:49PM-s009 ~/src/angband/src% printf '< %.2f microseconds per call\n' $((15.69 / 1000000000 * 1000000))
< 0.02 microseconds per call
Newton- 1:49PM-s009 ~/src/angband/src% time ./a.out 2000000000                                                  
1000000000 calls, 1073726417 loop entries, test and branch success rate of  7.37264170%
./a.out 2000000000  15.52s user 0.02s system 99% cpu 15.570 total
My program called Rand_div() via the randint0 macro 1 billion times requesting a random number from 0 to n-1 where n is specified via command line. As you can see, the bias issue begins at not being an issue. As n becomes a relatively very large 2 billion, the loop can cycle at least once around 7.4% of the time. For the purposes of the Angband that I played, the unbiased algorithm added no measurable overhead during gameplay. (I can share my test program, but I am probably the only one interested in it.)

As for the idea of expanding the RNG from 28 bits to 31 bits, that's not my call. I've compiled and am "playing" 4.0.4. (It looks nice!) I'm on the town level, and I should perhaps stay in town for now.

The edit:

Actually, thinking about this further, there may be a bug in what my test program is reporting as "test and branch success rate", as that should be a little under 7%, not a little over 7%. Also, there are definitely some efficiency advantages to expanding the range of Rand_div() using that algorithm. I'm not sure if the matter is worth bothering with though. I'll ponder the matter later after I deal with the lawn mower belt.

Last edited by rhutson; August 17, 2016 at 00:31. Reason: test program bug?
rhutson is offline   Reply With Quote
Old August 17, 2016, 02:51   #23
AnonymousHero
Veteran
 
AnonymousHero's Avatar
 
Join Date: Jun 2007
Posts: 1,365
AnonymousHero is on a distinguished road
What about "perf" instead of "time"? (Regardless of whether that's better, "time" is definitely not a good way to benchmark anything if you're looking a variation at the sub-second level.)

"perf" will at least show you 'cycle counts'.
AnonymousHero is offline   Reply With Quote
Old August 17, 2016, 05:42   #24
rhutson
Rookie
 
Join Date: Jul 2013
Location: In the Misty Mountains
Posts: 23
rhutson is on a distinguished road
Quote:
Originally Posted by AnonymousHero View Post
I mostly wanted the replacement for the same somewhat perverse reasons as yoursel
I have developed a "problem" with joking on technical forums. This can cause confusion and create credibility issues. I will try to restrain myself as you and others are interested in learning.

The reason that I became foucsed on the RNG was because changes that Ben made to the game slowed it down considerably. I profiled the game and noticed that the plurality (IIRC) of CPU time in the game was being spent in the RNG. Ben did "something" to reduce RNG calls while I focused on improving the efficiency of the RNG. Wanting the best for Angband, I added the algorithm to eliminate the inherent bias of the random() % N method (which was "satisfying").

BTW: My last Angband session was over 21 hours nonstop.

Last edited by rhutson; August 17, 2016 at 05:49.
rhutson is offline   Reply With Quote
Old August 17, 2016, 07:09   #25
rhutson
Rookie
 
Join Date: Jul 2013
Location: In the Misty Mountains
Posts: 23
rhutson is on a distinguished road
Quote:
Originally Posted by AnonymousHero View Post
What about "perf" instead of "time"? (Regardless of whether that's better, "time" is definitely not a good way to benchmark anything if you're looking a variation at the sub-second level.
Newton- 9:50PM-s001 ~/src/angband/src% perf
zsh: command not found: perf



I did find the Wikipedia page for 'perf', but something like that is not needed for what I was/am doing. I did note, e.g., '< 0.02 microseconds per call' as zsh's builtin 'time' reported the CPU usage for the entire program. After that, the math was simple enough. (getrusage() still exists, but it was not needed.)

Oh, there was not a bug in my test program. I encountered a printf terminology issue while multitasking, and after my unedited post, I noticed that what I thought should be 6.7% was 7.4%. Needing to commute, I edited and declared a possible bug in my hastily composed test program.

With the 31 bit version of the RNG, there is a worst case 6.7% chance of the branch being taken. But if the branch is taken, there is another 6.7% chance of the branch being taken again ... (Unnecessary careful study of earlier posts indicate that I was quite aware of relooping. // again, multitasking)

The 28 bit vs 31 bit RNG efficiency study is interesting, but would be more so in later days.
rhutson is offline   Reply With Quote
Old August 17, 2016, 10:17   #26
AnonymousHero
Veteran
 
AnonymousHero's Avatar
 
Join Date: Jun 2007
Posts: 1,365
AnonymousHero is on a distinguished road
Quote:
Originally Posted by rhutson View Post
Newton- 9:50PM-s001 ~/src/angband/src% perf
zsh: command not found: perf



I did find the Wikipedia page for 'perf', but something like that is not needed for what I was/am doing.
My point was merely that 'perf' can tell you exact (well, as exact as possible) numbers for many things you might be interested in. (Like branch prediction and such.)
AnonymousHero is offline   Reply With Quote
Old August 18, 2016, 00:30   #27
rhutson
Rookie
 
Join Date: Jul 2013
Location: In the Misty Mountains
Posts: 23
rhutson is on a distinguished road
Quote:
Originally Posted by AnonymousHero View Post
My point was merely that 'perf' can tell you exact (well, as exact as possible) numbers for many things you might be interested in. (Like branch prediction and such.)
I understood your point, but I don't think that you understand what I am doing. 'perf' looks like a tool that I would be using if I was still playing and contributing to Angband while running Linux or even if there was a OS X version. 'perf' does appears to be a good tool for studying the performance of the game itself.

Here is stripped down code of the program which I am speed testing with zsh's time (/usr/bin/time yields essentially identical results) :

Code:
static int loops, calls;

// stripped z-rand31.c begins

        } else {
                ++calls;
                /* Use a complex RNG */
                while (1) {
                    ++loops;
// stripped z-rand31.c continues and ends

// omitted test program stuff

int main(int argc, char *argv[])
{
// omitted test program stuff which includes converting argv[1] to the integer n

    for (i = 0; i < BIG; ++i)        // I use a do-while loop, but this is more conventional.
    {
        if (randint0(n) >= n)
            die("Uh oh");
    }

    printf("%d calls, %d loop entries, (loops - calls) / calls * 100: %.8lf\n", calls, loops, (double)(loops - calls) / calls * 100);
}
The 'time' utility is the right tool for speed testing what I am doing. 'time' is reporting the CPU time of code besides the RNG, but that extra code uses trival CPU time, and it uses a constant amount of time. The constant extra trivial CPU time is what makes the 'time' utility the right tool for optimizing my spare time , and, again, is also why I qualified the results with '<'.

I am now reminded of an amusing true story related as dialogue which I hope that you and some others appreciate:

"And so, the algorithm runs in `O(n log(n)^2) + 483' time."

"Professor, why did you include 483 in your analysis? I thought that we were supposed to removed constants from an analysis."

"Oh, you're right." // "+ 483" erased from chalkboard.

Addressing any concerns about the accuracy of a modern 'time', I do notice that Apple's unmaintained(?) man pages for /usr/bin/time do add a warning about the 'time' utilty:

Quote:
BUGS
The granularity of seconds on microprocessors is crude and can result in times being reported for CPU usage which are too large by a second.

BSD June 6, 1993 BSD
That probably was true with BSD in 1993, and I do recall 'time' not having much granularity on 4.2 BSD. However, I've never seen such a bug of that magnitude under Linux or OS X (which I primarily switched to in 2008). I am getting results that are consistent enough for my purposes using getrusage() via zsh or /usr/bin/time:

Quote:
Newton- 2:47PM-s001 ~/src/angband/src% time a.out 400
500000000 calls, 500000011 loop entries, (loops - calls) / calls * 100: 0.00000220
a.out 400 6.85s user 0.01s system 99% cpu 6.886 total
Newton- 2:47PM-s001 ~/src/angband/src% time a.out 400
500000000 calls, 500000014 loop entries, (loops - calls) / calls * 100: 0.00000280
a.out 400 6.86s user 0.01s system 99% cpu 6.890 total
Newton- 2:48PM-s001 ~/src/angband/src% time a.out 400
500000000 calls, 500000009 loop entries, (loops - calls) / calls * 100: 0.00000180
a.out 400 6.86s user 0.01s system 99% cpu 6.890 total
Newton- 2:48PM-s001 ~/src/angband/src% time a.out 400
500000000 calls, 500000014 loop entries, (loops - calls) / calls * 100: 0.00000280
a.out 400 6.94s user 0.02s system 99% cpu 6.983 total
Newton- 3:21PM-s001 ~/src/angband/src% time a.out 400
500000000 calls, 500000009 loop entries, (loops - calls) / calls * 100: 0.00000180
a.out 400 6.86s user 0.01s system 99% cpu 6.891 total
Newton- 3:21PM-s001 ~/src/angband/src% time a.out 400
500000000 calls, 500000009 loop entries, (loops - calls) / calls * 100: 0.00000180
a.out 400 6.86s user 0.02s system 99% cpu 6.901 total
Newton- 3:21PM-s001 ~/src/angband/src% time a.out 400
500000000 calls, 500000014 loop entries, (loops - calls) / calls * 100: 0.00000280
a.out 400 6.85s user 0.02s system 99% cpu 6.892 total
I do need to come up with a better name for the "(loops - calls) / calls * 100" metric, but at least it is now not "wrong", but just lacking in meaning. (It's just a test program that I'm working on in my spare time.)

But remember, the main idea of the test program was to verify and assure that my unbiased algorithm was not looping a lot. 20 years ago or whenever, I used the "static int calls, loops;" method while testing the algorithm. I added a game command to occasionally print their values while playing the game. I don't recall the specifics, only that I did not observe any alarming looping. The shell speed measurements and numerical demonstration that randint0() has indeed been working correctly all of these years were add-ons.

P.S. Obviously, I enjoy discussing this subject with you. And I do need to check the looping performace of the 28-bit RNG.

PS2 The reason for the quick P.S. was that I needed to "disconnect", and I think that my post should have begun thusly:

"Thank you for sharing that info about 'perf'. However, I abandoned my 16 year Linux project in 2008 for personal reasons. Any advice or help offered by you or anyone else is always welcomed!"

Last edited by rhutson; August 18, 2016 at 05:00.
rhutson is offline   Reply With Quote
Reply

Tags
rng


Currently Active Users Viewing This Thread: 1 (0 members and 1 guests)
 
Thread Tools
Display Modes

Posting Rules
You may not post new threads
You may not post replies
You may not post attachments
You may not edit your posts

BB code is On
Smilies are On
[IMG] code is On
HTML code is Off

Forum Jump

Similar Threads
Thread Thread Starter Forum Replies Last Post
Random map generator. LostTemplar Development 0 May 16, 2013 21:05
Limited Iron Man Mode EpicMan Vanilla 3 December 4, 2010 05:10
Random number generation? Chud Vanilla 21 November 8, 2010 18:00
Mechanic idea for a variant...monster generator Jude Variants 44 November 19, 2008 20:44
Angband Variant without random levels? TJA Variants 32 August 18, 2007 16:47


All times are GMT +1. The time now is 20:22.


Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2018, vBulletin Solutions Inc.