DDraceNetwork - developer

haxor boys hi

05:07

tell me what snd_rate in f1 does

05:07

@here

05:08

oh, it has discription

05:10

is there bandwidth limit in tw?

05:10

in cs 1.6 there was rate and other commands

@Fudgy Is your showothers alpha perhaps 0?

Do u know what color code tw use? I mean what is BodyColor = 9417075

@Learath2 ^

Packed HSL with a weird clamping of L

10:19

8F B1 73, thaaats 8F ~ 202/360 blueish

10:21

70% saturation, 28% lighting

10:22

but player colors cant be below 50% lighting, soooo 64% lighting I think

❤️ thanks a lot

11:15

11:15

so bad

heinrich5991

[ddnet/ddnet] Pull request opened: #2212 Use a consistent PRNG on all platforms

I just used glibc's because that is what we use on all the servers. Based on https://www.mscs.dal.ca/~selinger/random/. Behavior change: The PRNG is actually seeded now.

Thx Learath, seems to have fixed it, Im pretty sure I never changed that setting directly tho :/

13:27

Didnt even know it existed

@heinrich5991 hm, why dont we just use one mersenne twister implementation accross all platforms instead of trusting that glibc implementation stays stable?

I reimplemented the glibc implementation, no need for it to stay stable

follow up question, why the glibc implementation if you had implementation freedom? Is the glibc one specifically better for this task somehow?

no

15:00

it helped me not face hard questions like "which should I choose?"

15:00

Use a consistent PRNG on all platforms by heinrich5991 · Pull Reque...

I just used glibc's because that is what we use on all the servers. Based on https://www.mscs.dal.ca/~selinger/random/. Behavior change: The PRNG is actually seeded now.

@Learath2 okay, now how does one choose between xoshiro256++ and xoshiro256**?

who are those and what do they do? D:

15:16

Oh fancy new prngs

apparently you're supposed to choose one of these

15:17

http://vigna.di.unimi.it/ftp/papers/ScrambledLinear.pdf 5.3 choosing a generator

isn't the pcg family supposed to be better?

pcg?

15:19

I have no idea about PRNGs

Me neither, I usually just use a mersenne twister for most everything

PCG-RXS-M-XS (with 32-bit output) passes BigCrush with 36 bits of state (the minimum possible), PCG-XSH-RR (pcg32() above) requires 39, and PCG-XSH-RS (pcg32_fast() above) requires 49 bits of state. For comparison, xorshift*, one of the best of the alternatives, requires 40 bits of state,[5]:19 and Mersenne twister fails despite 19937 bits of state.[9]

I guess pcg is the ducks guts nowadays

15:22

seems it performs a little better then xorshift, is a little more uniform and is less predictable

15:25

and I guess we can bitmask and reject like apple or that other integer multiplicaton voodoo that seemed a tad better optimized

bitmask and reject like apple?

15:26

you mean reject when PRNG output is too high before % ?

You mask some bits, if the number is not within the range you want, you discard and get a new one

15:27

cheaper then modulo and not biased

ah, interesting

15:27

didn't know about that technique

(unless your rng is very expensive I'd guess)

15:27

like if you are getting the bits from some quantum noise

Oh also, not sure how architecture affects us, should we maybe be using a 32bit prng?

32bit is dead™

well we still compile for it

15:32

(not like we are generating billions of values here, shouldn't dwell on the choice too long)

xorshiro**++ etc only uses additions/shifts/xors

15:32

so no problem on 32bit

pcg also works fine on 32bit as far as I can see

I couldn't find docs on which of the pcg generators to use

15:37

https://rust-random.github.io/rand/rand_pcg/index.html

rand_pcg - Rust

API documentation for the Rust rand_pcg crate.

15:39

https://github.com/KilianB/pcg-java

KilianB/pcg-java

PCG — Java Implementation. High quality fast random number generator - KilianB/pcg-java

not many choices from what I see

I can't find either algorithm for go

go?

golang

15:41

ah here, both pcg and xoshiro https://godoc.org/github.com/db47h/rand64

Package rand64

Package rand64 is a dummy package that just serves as a container for pseudo-random number generators each in its own sub-package.

But what are we doing with these?

15:42

Not like we have any code in Go or Java

just interested in what support those PRNGs have

ah

but it seems they have similar

Well modern languages seem to interface very well with C anyway

15:43

I wouldn't mind writing a wrapper

but having a library is better than having to write your own

this is true

https://bashtage.github.io/randomgen/ python also both

15:44

pcg is available via https, xoshiro is not

pcg seems so simple

15:45

So simple I'm wondering if someone is missing something

xoshiro seems just a simple(?) http://prng.di.unimi.it/xoshiro256plusplus.c

15:49

hm. state function of pcg seems to be literally linear

Not that I understand the underlying theory of either

I guess since we only use ints and we assume ints are 32bits a 32bit generator is enough for us

16:12

so pcg32 or xoshiro128(** or ++)

16:12

only god knows the difference between ** and ++ because that paper is tough to read

browsers use xorshiro128+ for Math.random apparently

I wonder if it's mathematicians writing these papers or computer scientists

16:15

Can't trust that Math.random is implemented in any specific way afaik not specified in the standard

yes

16:16

just saying that people use it

16:16

pcg says xorshiro is bad and xorshiro says pcg is bad

I think the + variant is only good for floats btw, you are looking for either ++ or ** when generating integers

yes

16:18

okay, so let's take speed as measure?

16:18

completely irrelevant for our use case

16:18

but just so we have some stupid criterion

16:18

(haven't looked at the relative speed)

Uf, I hate this kind of rivalry, I wish someone had an objective review of both papers

16:22

Atleast the xoshiro guy seems to have given actual failings of pcg in examples, and browsers seem to use it so the browser people probably reviewed the family of algorithms a bit

16:25

(also I have an inherent distrust of sites that look clean when it comes to taking algorithms)

pcg has a https site at lesast

oh also xoshiro seems to be from unimi, our sister uni, so forza italia o/

https://github.com/numpy/numpy/issues/13635#issuecomment-506019597 numpy has pcg

Decide on new PRNG BitGenerator default · Issue #13635 · numpy/numpy

#13163 will be bringing in the long-awaited replacement of numpy's PRNG infrastructure. In the interest of keeping that PR manageable, we will merge it to master before all of the decisions...

16:28

food

Okay, I think I'll vote for pcg, the critique from the guy who wrote xoshiro looks pretty petty and full of semi-hidden ad hominems and the author of pcg seems to have responded to them fairly adequately

Funny, I didn't think this kind of petty squabbling happened in academic settings

@Learath2 I don't want to include <system.h> just to get a 64 bit integer

17:54

@heinrich5991 should we maybe split out system.h?

18:18

We could have something like base/types.h?

maybe that would work

18:20

defining our own int64 is still useless, but it would also benefit stuff including system.h for types

18:26

@Learath2 can you find test vectors for PCG?

test vectors?

yes. seed → random number pairs

18:38

so I can figure out if I implemented it correctly

Which variant did you end up using?

wikipedia tells me "most users should use xyz"

18:39

so I used xyz

PCG-XSH-RR??

18:40

.s/??/?/

yes. is that bad?

nope, but I cant look for testcases without knowing which variant you implemented

18:45

The rust library seems to have a set of tests

18:45

https://github.com/rust-random/rand/blob/master/rand_pcg/tests/lcg64xsh32.rs

rust-random/rand

A Rust library for random number generation. Contribute to rust-random/rand development by creating an account on GitHub.

18:46

refers to some "official test suite." I'm currently looking for

https://www.pcg-random.org/using-pcg-c.html

Using the Full C Implementation

18:47

googling the numbers helped

https://github.com/imneme/pcg-c/blob/master/test-high/expected/check-pcg32.out

imneme/pcg-c

PCG — C Implementation. Contribute to imneme/pcg-c development by creating an account on GitHub.

ty

42u and 54u are initstate and initseq respectively

implemented it incorrectly

How can I check that a playername joined a game? I know how to check clientid but not the playername

from what perspective are you coding?

18:56

client? server? econ?

server

0.6/0.7?

0.7 ddnet7

Eeeeeh, not that simple

18:57

You need to wait until the player sends it's info

look for CNetMsg_Cl_StartInfo

@heinrich5991 anything trivial?

@Learath2 I can't find the error

19:02

now comparing to the rust implementation instead of wikipedia

The C implementation isn't too convoluted

19:05

pcg_setseq_64_srandom_r,pcg_setseq_64_xsh_rr_32_random_r are the functions you are looking for

where do I find them? https://github.com/imneme/pcg-c/tree/master/src

imneme/pcg-c

PCG — C Implementation. Contribute to imneme/pcg-c development by creating an account on GitHub.

You basically multiply by a constant, increment by inc and use xsh-rr to output

19:07

https://github.com/imneme/pcg-c/blob/master/include/pcg_variants.h

imneme/pcg-c

PCG — C Implementation. Contribute to imneme/pcg-c development by creating an account on GitHub.

ah, I'm holding the init values wrong

19:09

a wikipedia has init wrong

19:10

ah*

Apparently you can use a 32bit multiplier to get better 32bit performance (assuming the compiler is smart enough), but I doubt we need to bother with that

argh not finding the mistake

19:19

and wikipedia's init does look right after all

19:21

the code in the pcg repo also looks wrong

19:21

https://github.com/imneme/pcg-c/blob/83252d9c23df9c82ecb42210afed61a7b42402d7/include/pcg_variants.h#L134

imneme/pcg-c

PCG — C Implementation. Contribute to imneme/pcg-c development by creating an account on GitHub.

19:22

ah no, not wrong, just different from wikipedia

Wrong output function

19:22

pcg_output_xsh_rr_64_32 is the one you are looking for

ah, that matches wikipedia at least

pcg_setseq_64_srandom_r is the init function

okay, wanna take a look? I can't find the error

sure

https://gist.github.com/heinrich5991/bc6b02b2cd9b68018809f66d912ffc88

prng.cpp

GitHub Gist: instantly share code, notes, and snippets.

could it be some weird integer promotion issue?

I put the remaining constant into a static

19:28

now all the integers are uint64

19:28

no promotion issues should remain™

19:29

but tests still fail

Your CPrng::RandomBits() doesn't look like pcg_setseq_64_step_r tbh

19:29

Ah you scramble it, not just step the underlying LCG

19:32

hmm, not sure if that changes anything really, (except it performs worse probably)

19:39

@heinrich5991 how can I run this?

https://codahale.github.io/pcg/src/pcg/pcg.rs.html#44-65

pcg.rs.html -- source

Source to the Rust file src/pcg.rs.

19:39

this looks like literally the same

I would check what happens after each randombits

pushed WIP into the PR @Learath2

@Learath2 I'm giving up on this

20:03

feel free to take a stab at it

no please don't leave it to me, I'll find your bug

20:06

pinky promise

20:09

How do I run a specific test?

20:15

Ah your test is wrong

20:15

That was so much work getting debugging here

my test is wrong? how?

Well the authors tests are shit is the better way to put it

20:17

She rolls 6 random 32bit integers, rewinds the rng, does 6 more, then does 65 rolls for the coins, 33 rolls for the dice, some for the deck shuffling

20:17

but never rewinds or reseeds the rng

20:17

So on round 2 the rng isn't at 7 but at a lot

DUH

20:17

why can't they just provide nice clean test vectors

People who come up with these usually aren't the people who also implement them in a practical setting

20:18

How many values you want? I can generate them while I have the code here

6 is fine I guess

20:19

I'll just take the first 6

20:20

nice

20:20

and now our uint64 definitions are biting me

20:21

apparently there's no way we can print a 64bit number in teeworlds

20:21

I'll print it with two 32 bit integers

I went for %llc and called it a day

20:21

llx*

20:22

I tried PRIx64 from inttypes however clang on macOS doesn't seem to provide that despite providing a 64 bit integer type

20:22

very confusing

Zwelf

[ddnet/ddnet] Pull request opened: #2213 Rename variables for consistency

The following member variables:

m_name to m_aName
m_String to m_aString
m_CpCurrent to m_aCpCurrent
m_Switchers to m_paSwitchers
SavedTees to m_paSavedTees

The first one is kind of obvious. The others followed while looking at the code. I am not sure if the m_pa prefix is the correct one, it's a pointer to a dynamically allocated array.

@heinrich5991 I wonder if compilers optimize MaskFor(unsigned int n) well

no, does not optimize well

20:31

better suggestion?

20:32

(I looked at the assembly)

well it should be a simple BSR and an XOR

btw, try and spot the funny bug in RandomIntBelow

we can google around for implementations that optimize better in gcc and clang atleast

__builtin_clz seems to be the answer

20:35

I think I prefer not using a builtin here

hm, it's doubtful that it'd ever be a performance issue, (given we don't even need much performance at all) but knowing something can be done with 2-3 instructions is being done with a dozen kinda hurts

20:39

Anyway, it's very trivial instructions, even on toasters the ors and shifts are dirt cheap

20:39

I wonder why gcc and clang don't recognize this pattern and optimize to a BSR though

20:42

(and apparently the author of the bit-twiddling hacks stuff checked and on an older cpu these ors and shifts are indeed almost as cheap as a single BSR

20:42

)

OH btw there is a teeeeny tiny issue

which is?

oh well we do assume ints are 32bit

20:51

nvm, not an issue

20:56

You can optimize the init to only advance the lcg btw, as we are discarding those 2 random numbers. But again performance isn't really much of a concern at all for us

ah yea, wanted to do that anyway

(The shifts needed to output that are again like 1-2 cycles on even a 6502 so not too important, especially as its a constant initialization time cost)

def-

[ddnet-web:master] 1 new commit

8a19535 Add donation - def-

Some inline hints could also help the compiler

I have a question though, do we really care if our rng output is biased?

no

The more I generate the more the bias should be obvious, no?

21:53

I mean even the simple modulo looks flawless to me with 1e8 values generated

21:57

Ah our bucket sizes are far too small to see this kind of bias

21:58

note to self, don't generate 1e10 random values

22:00

(at 64bits per value that's 80gb of data)