Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
2011/12/7 Graeme Geldenhuys graemeg.li...@gmail.com: Hi, I did a simple GetTickCount() timing around this loop. Delphi executes the loop in 20 ticks. FPC 2.6.0-rc2 takes 10585 ticks The outer loop runs 200400 iterations. The types for BitValue, ByteValue and RandSeed is of type Byte. 01 for Index := 1 to Length(Source) do 02 begin 03 OrdValue := Ord(Source[Index]); 04 for BitCount := 0 to 7 do 05 begin 06 BitValue := Byte(OrdValue and (1 shl BitCount) = 1 shl BitCount); 07 RandSeed := ByteValue; 08 ByteValue := (((Random(255) + 1) div 2) * 2) + BitValue; 09 Result[(Index - 1) * 8 + BitCount + 1] := AnsiChar(ByteValue); 10 end; 11 end; I have one question about this code, why is RandSeed set inside the loop and not outside the loop or even at the program start? If you change the randseed, then the random number generator has to be initialized and that is more costly for a stateful RNG as the mersenne twister. Vincent ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
Am 09.12.2011 09:02, schrieb Vincent Snijders: 2011/12/7 Graeme Geldenhuys graemeg.li...@gmail.com: Hi, I did a simple GetTickCount() timing around this loop. Delphi executes the loop in 20 ticks. FPC 2.6.0-rc2 takes 10585 ticks The outer loop runs 200400 iterations. The types for BitValue, ByteValue and RandSeed is of type Byte. 01 for Index := 1 to Length(Source) do 02 begin 03OrdValue := Ord(Source[Index]); 04for BitCount := 0 to 7 do 05begin 06 BitValue := Byte(OrdValue and (1 shl BitCount) = 1 shl BitCount); 07 RandSeed := ByteValue; 08 ByteValue := (((Random(255) + 1) div 2) * 2) + BitValue; 09 Result[(Index - 1) * 8 + BitCount + 1] := AnsiChar(ByteValue); 10end; 11 end; I have one question about this code, why is RandSeed set inside the loop and not outside the loop or even at the program start? If you change the randseed, then the random number generator has to be initialized and that is more costly for a stateful RNG as the mersenne twister. Oops, mails crossed. The assignment to randseed is indeed the problem. Why is it done? Bad random generator of delphi :)? ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 9 December 2011 10:02, Vincent Snijders wrote: I have one question about this code, why is RandSeed set inside the loop and not outside the loop or even at the program start? For the full code as used by tiOPF, see the following URL. http://tiopf.svn.sourceforge.net/viewvc/tiopf/tiOPF2/Trunk/Options/tiEncryptSimple.pas?revision=2143view=markup I didn't write this encryption code, I merely debugged why the unit tests for this unit took so long to complete, compared to under Delphi. Looking at the code again, I have no idea how it will affect the encryption algorithm if I move the assignment to RandSeed outside the loop (just after the first assignment to ByteValue). As a test, made your suggested change and ran the unit tests. The unit tests still pass, and the performance under FPC has drastically improved. FPC (64-bit) is now roughly 4 times slower that Delphi. Much better indeed, and an acceptable result. I'll see if I can get hold of the original author of this code and what they think about the suggested change - and if it will affect the encryption algorithm at all. Thanks Vincent for mentioning this. I totally overlooked that. -- Regards, - Graeme - ___ fpGUI - a cross-platform Free Pascal GUI toolkit http://fpgui.sourceforge.net ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On Fri, Dec 9, 2011 at 9:39 AM, Graeme Geldenhuys graemeg.li...@gmail.com wrote: I didn't write this encryption code, I merely debugged why the unit tests for this unit took so long to complete, compared to under Delphi. It is specifically written in the Delphi documentation that Random should not be utilized for encryption... -- Felipe Monteiro de Carvalho ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
- Felipe Monteiro de Carvalho felipemonteiro.carva...@gmail.com schreef: On Fri, Dec 9, 2011 at 9:39 AM, Graeme Geldenhuys graemeg.li...@gmail.com wrote: I didn't write this encryption code, I merely debugged why the unit tests for this unit took so long to complete, compared to under Delphi. It is specifically written in the Delphi documentation that Random should not be utilized for encryption... true, (but) looking at the code again, it seems that you always have a predictable sequence when using the same algorithm. Not sure if that is a good thing or a bad one in cryptology :-). After all, when you do not randomize() first, randseed has a default startupvalue (and otherwise it is typically seeded with a timestamp of somesorts). I don't remember where I read it (ages ago), and the comment in Delphi seems to negate that this is the used algorithm, but this 'predictable sequence from the same seed'-property is especially true when using a LCG pseudo-random-number-generator. Just to be sure, the wikipedia article DOES mention that Delphi (and every other HL language that matters :-)) supplies a Random functionality that is based on a LCG. http://en.wikipedia.org/wiki/Linear_congruential_generator And in the java realm there are numerous other algorithms available, but the default implementation with the language libraries is a LCG, as does the C(++). Reading the article again, I find a few paragraphs corresponding to the Delphi help. Excerpt from the 'advantages and disadvantages' part of the page: -- LCGs should not be used for applications where high-quality randomness is critical. For example, it is not suitable for a Monte Carlo simulation because of the serial correlation (among other things). They should also not be used for cryptographic applications; see cryptographically secure pseudo-random number generator for more suitable generators. If a linear congruential generator is seeded with a character and then iterated once, the result is a simple classical cipher called an affine cipher; this cipher is easily broken by standard frequency analysis. -- kind regards, Dimitri Smits ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 09 Dec 2011, at 09:39, Graeme Geldenhuys wrote: Looking at the code again, I have no idea how it will affect the encryption algorithm if I move the assignment to RandSeed outside the loop It will improve the randomness of the generated numbers. Changing the random seed all the time removes any properties the random generator normally has. In other words, the original code is wrong. Jonas ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
- Graeme Geldenhuys graemeg.li...@gmail.com schreef: On 9 December 2011 10:42, Felipe Monteiro de Carvalho wrote: It is specifically written in the Delphi documentation that Random should not be utilized for encryption... Delphi documentation mentions a lot of things you mustn't do... Does that stop anybody. ;-) only those that take their jobs seriously and read help/manuals iso assuming? :-) Like I said, I didn't write that code, and I don't specialise in encryption algorithms. But Florian might be right, the RandSeed assignment might have been added due to the bad random generator of Delphi - hopefully the original author of the code can shed some light. I actually doubt that that codesnippet does any real encryption. From what I understand from it (with the provided code and assuming types), the source-message is bitstreamed. In the resulting message, the LSB of every octet/byte/8-bitvalue is the one you need to focus on, the rest is random data. Also, as a result, the result-message is 8 times as large. And that LSB is also easily decrypted = parse the LSB from every byte in your data and reconstruct using OR the (index mod 8)-th bit on the (index div 8) octet. hardly encrypted ;-) kind regards, Dimitri Smits ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On Fri, 09 Dec 2011 07:27:46 +0100 Jürgen Hestermann juergen.hesterm...@gmx.de wrote: Reimar Grabowski schrieb: The parameter should default to FALSE to not break existing code relying on FPCs random function And what about existing code coming from Delphi/Turbo Pascal? This was a strong argument in the past for doing even crap coding. Not by me, but the FPC developers. I am not interested in Delphi/TP compatability and never was, so I don't care if Delphi/TP code works or not, but I care if code written exclusively in and for FPC continues to work as it did. I think that Delphi is a burden for FPC and Lazarus, but the developers have other opinions, so be it. I don't need a change at all. It may be irritating for a Delphi developer that his code runs slower, but profiling is no secret art and changing a random implementations to a less 'good' but faster one is a matter of minutes. Like people already said, lots of talk about a 'problem' that 10 years noone has seen as one. Another 2 cents R. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
In our previous episode, Reimar Grabowski said: Like people already said, lots of talk about a 'problem' that 10 years noone has seen as one. (it's afaik not the first. Has been noticed once or twice before. But those people used it in unittests, and simply changed without much ado when the problem was identified. Contrary to the fact that before the twister change, people complaining about random being not as random as Delphi several times per year) ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 9 December 2011 15:51, Reimar Grabowski wrote: knowledge to back up your statements. Next time please take the time to identify the problem correctly before jumping to conclusions. No offense ment. No offense take. Two unknown (to most) facts came out of this discussion. 1) the FPC Random() function IS slower than Delphi's. 2) FPC implements a different random generator than Delphi. Is this good or bad? Considering the must be Delphi compatible term thrown around so often. Even with the original (slightly non-optimal usage of Random) code, Delphi ran it fine and fast, FPC didn't. So from a porting point of view (Delphi to FPC), there was a problem which others might get caught in as well. Either way, thanks to Vincent's sharp eye, which everybody but Vincent overlooked, the speed problem in the tiOPF code can be greatly reduced to acceptable levels with FPC - even though FPC has a different random generator. Thanks to all that participated and helped solve my problem. It was an interesting discussion as always. -- Regards, - Graeme - ___ fpGUI - a cross-platform Free Pascal GUI toolkit http://fpgui.sourceforge.net ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 9 December 2011 12:42, Jonas Maebe wrote: It will improve the randomness of the generated numbers. Thanks Jonas. -- Regards, - Graeme - ___ fpGUI - a cross-platform Free Pascal GUI toolkit http://fpgui.sourceforge.net ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 9 December 2011 12:50, Dimitri Smits wrote: I actually doubt that that codesnippet does any real encryption. It isn't. The sample code / test program I posted is just a snippet of the actual unit. No point in posting the whole unit here, just to point out that a single section of code in one method is the location of the slow-running code under FPC. I only supplied the slow-running code to demonstrate the problem. -- Regards, - Graeme - ___ fpGUI - a cross-platform Free Pascal GUI toolkit http://fpgui.sourceforge.net ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
Well, lets go to theory : One way to build a cypher is to XOR the stream that must be encrypted against a fixed value. But, this is easy to break using statistical methods. So the next logical way to do this is to XOR the stream against another stream of numbers, kind of one time password. But, the stream of numbers must be shared by both ends. How ? Simple, generate the stream on-the-fly using a PRNG. Now you only need to share the seed of the PRNG and the encrypted stream. But for this to work the same PRNG must be used on both ends, and the PRNG must be strong enough with a period much longer than the size of the data being encrypted. Whats wrong with calling RANDOMIZE during the loop ? The problem is that you keep seeding the PRNG with the Now() (current time stamp), defeating the whole idea. Now, instead of XORing your plain text against a pseudo-random sequence, you are XORing your plain text against the current time/date, something quite easily predictable. Even in your case, seeding a Mersenne Twister in every loop interaction will put that algorithm exactly in its worst case : the startup sequence. The mersenne Twister is slow to start generating good random numbers. So your program is bug to the guts in this case. To solve this all you have to do is to guarantee that both communication ends use the same random number generation algorithm and seed. This will work. (IE.: the fix will break compatibility with old binaries). And dont seed against the last result, thats not a good idea (This will keep the MT restarting). A good alternative to a simple encryption algorithm is to use cryptographic hash functions like SHA. hash your key using SHA. Split your file in blocks the same size of the SHA key. XOR the first block against the first key, output the bytes. Hash the SHA key itself, generating a second key, XOR the second block against that second key. repeat until end of data. PAD the last block to match the Hash size. 2011/12/9 Graeme Geldenhuys graemeg.li...@gmail.com: On 9 December 2011 12:50, Dimitri Smits wrote: I actually doubt that that codesnippet does any real encryption. It isn't. The sample code / test program I posted is just a snippet of the actual unit. No point in posting the whole unit here, just to point out that a single section of code in one method is the location of the slow-running code under FPC. I only supplied the slow-running code to demonstrate the problem. -- Regards, - Graeme - ___ fpGUI - a cross-platform Free Pascal GUI toolkit http://fpgui.sourceforge.net ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
even if FPC implemented a ultra high tech PRNG it would be compatible
with DELPHI :
1 - Delphi asserts that you should not use the Random function to
encryption porpuses.
2 - Delphi asserts no speed guarantees.
3 - Delphi asserts no randomness quality guarantees.
IE : to be compatible you only need the function to have the same
calling parameters and result type.
Formally, in that case, even this would be compatible :
Function Random(): Real;
Begin
Result := 4; { i throwed a dice to reach that result ! }
End;
2011/12/9 Graeme Geldenhuys graemeg.li...@gmail.com:
On 9 December 2011 12:42, Jonas Maebe wrote:
It will improve the randomness of the generated numbers.
Thanks Jonas.
--
Regards,
- Graeme -
___
fpGUI - a cross-platform Free Pascal GUI toolkit
http://fpgui.sourceforge.net
___
fpc-pascal maillist - fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
___
fpc-pascal maillist - fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On Thu, 08 Dec 2011 10:52:01 +0100, Graeme Geldenhuys graemeg.li...@gmail.com wrote: On 8 December 2011 11:33, Henry Vermaak wrote: I agree, quality first. I would normally agree with that. But such huge magnitudes slower (20ms vs 10585ms) on a new Quad-Core type system? That just seems a bit excessive, and considering most use cases are not even for statistical type applications. Well, considering that the MT is a very bad choice as PRNG for a stream- cipher (even if it's never used in production code, it still gives me the creeps), I'd say, your use case isn't the typical one, either. ;) In my case I needed a thread-safe version, so may I request that System.Random() shall be protected against concurrent access - making it even slower? I mean, using your own random generator for whatever reason (statistical properties, cryptographically strong, lightning fast) isn't exactly rocket science. ;) http://stop-me.svn.sourceforge.net/viewvc/stop-me/trunk/src/lfsr.pas?revision=53view=markup Especially because you could speed-up your code alone by using the 64 random bits you are actually getting from the Random() call instead of generating a stream of 512 bits for each single character. ;) So, to come to a conclusion, I do not see any reason why the current implementation of System.Random() shall be changed. Vinzent. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 9 December 2011 19:55, Jorge Aldo G. de F. Junior wrote: Well, lets go to theory : In case you didn't notice the unit name this code comes from tiEncryptSimple.pas The name should be a good enough hint that it wasn't meant for real-world apps. ;-) For real-world apps, tiOPF has other encryption units based on DES and Blowfish. But thanks for the theory. I'll keep it for a rainy day. -- Regards, - Graeme - ___ fpGUI - a cross-platform Free Pascal GUI toolkit http://fpgui.sourceforge.net ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 9 December 2011 20:54, wrote: In europe electricity is sometimes 220 volts. Twice as fast as 110 volts in Canada, but I'm not sure about africa ;-) :-) South Africa uses 220 volts too. -- Regards, - Graeme - ___ fpGUI - a cross-platform Free Pascal GUI toolkit http://fpgui.sourceforge.net ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 8 December 2011 09:50, Florian Klaempfl wrote: Actually those who depend on speed should have spoken up ten years ago when the MT was implemented. I for one did not even know about the existence of Free Pascal 10 year ago. I don't believe I am alone either. On a side note: As for Jonas doing the implementation. I think we should give the correct person credit here. The current repository only goes back as far as 2005-05-16 (fpc release 2.0.0). But I believe Jonas simply added the existing Object Pascal implementation or MT to FPC some 10 years ago, but the real implementor was: Translated to OP and Delphi interface added by Roman Krejci (6.12.1999) --- system.inc (line 478) Just so that we are statistically correct with the credits too. ;-) -- Regards, - Graeme - ___ fpGUI - a cross-platform Free Pascal GUI toolkit http://fpgui.sourceforge.net ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
In our previous episode, Graeme Geldenhuys said: And what about people using FPC only and depending on our Random being statistically strong, they are less important then theorical Delphi migrants? [like what was told to me numerous times before] They (FPC users) should speak up now, or forever hold your peace. And those that have spoken so far, all seem to be fine with a less statistically strong default Random(), and have the statistically strong one available in the Maths unit. I don't enjoy validating working programs because of this. It's a strange case where people are advocating the introduction of a slower manager to improve the speed of random :-) IMHO people wanting a guaranteed fast random, should create a package with a guaranteed fast random, and use that, and not confuse it with compatibility issues. It is only a matter of time before an user wants to create a program that includes a package that wants fast random with a package that wants a reliable reproducable one. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
Am 08.12.2011 09:03, schrieb Graeme Geldenhuys: On 8 December 2011 09:50, Florian Klaempfl wrote: Actually those who depend on speed should have spoken up ten years ago when the MT was implemented. I for one did not even know about the existence of Free Pascal 10 year ago. I don't believe I am alone either. Indeed, but people depending for years of FPC's random function and dicussed it years ago might not followed up this mailing list anymore but just use it so they cannot speak up today either. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 8 December 2011 10:04, Marco van de Voort wrote: It's a strange case where people are advocating the introduction of a slower manager to improve the speed of random :-) It's called an acceptable compromise, by those that use it most. Just like FPC doesn't do micro code optimizations on each and every platform. The FPC performance [see Martin Schriebers annual posts about FPC speed vs Delphi 7] hit is a compromise for easier maintainability of source code. A simple trade-off. The Maths unit is known for more advanced math and statistical features. A strong random number generator seem a good fit for that unit. -- Regards, - Graeme - ___ fpGUI - a cross-platform Free Pascal GUI toolkit http://fpgui.sourceforge.net ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 8 December 2011 10:08, Florian Klaempfl wrote: dicussed it years ago might not followed up this mailing list anymore but just use it so they cannot speak up today either. That's their loss. -- Regards, - Graeme - ___ fpGUI - a cross-platform Free Pascal GUI toolkit http://fpgui.sourceforge.net ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
2011/12/8 Graeme Geldenhuys graemeg.li...@gmail.com: On 8 December 2011 09:25, Felipe Monteiro de Carvalho wrote: And what if it changes in the future to being slow and statistically strong, we change again too? The random number generator can be implemented in such a way that the backend generator is user selectable. And what about people using FPC only and depending on our Random being statistically strong, they are less important then theorical Delphi migrants? [like what was told to me numerous times before] They (FPC users) should speak up now, or forever hold your peace. When I used fpc in past to write statistical simulation I also investigated the random number generator and was pleased to see that it used the Mersenne Twister. I hope a upcoming change won't break my programs or make there outcome suspect because of the poor quality of the random number generator. Writing a fast number generator is almost a one liner: http://en.wikipedia.org/wiki/Linear_congruential_generator Vincent (not holding his peace) ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 08/12/11 09:13, Vincent Snijders wrote: 2011/12/8 Graeme Geldenhuysgraemeg.li...@gmail.com: On 8 December 2011 09:25, Felipe Monteiro de Carvalho wrote: And what if it changes in the future to being slow and statistically strong, we change again too? The random number generator can be implemented in such a way that the backend generator is user selectable. And what about people using FPC only and depending on our Random being statistically strong, they are less important then theorical Delphi migrants? [like what was told to me numerous times before] They (FPC users) should speak up now, or forever hold your peace. When I used fpc in past to write statistical simulation I also investigated the random number generator and was pleased to see that it used the Mersenne Twister. I hope a upcoming change won't break my programs or make there outcome suspect because of the poor quality of the random number generator. I agree, quality first. Especially when faster lower quality alternatives are so easy to implement. Henry ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 8 December 2011 11:33, Henry Vermaak wrote: I agree, quality first. I would normally agree with that. But such huge magnitudes slower (20ms vs 10585ms) on a new Quad-Core type system? That just seems a bit excessive, and considering most use cases are not even for statistical type applications. -- Regards, - Graeme - ___ fpGUI - a cross-platform Free Pascal GUI toolkit http://fpgui.sourceforge.net ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
Hi, On 8/12/2011 9:48 πμ, Graeme Geldenhuys wrote: [like what was told to me numerous times before] They (FPC users) should speak up now, or forever hold your peace. And those that have spoken so far, all seem to be fine with a less statistically strong default Random(), and have the statistically strong one available in the Maths unit. IMO, there is two separate subjects in this discussion. The first obviously is the implementation and the Delphi compatibility of the Random function but for me the hidden and most valuable subject is the fpc's lack of documentation. If the algorithm used to implement the Random function was documented then it wouldn't be any reason for this discussion . The user will be warned, informed and acted accordingly to suit his needs. And plz don't use the UTS ( Use The Source) on me. There is situations that you don't have the time and the state of mind to read and study all the fpc sources. In the end IMO don't change the Random implementation just documented it. regards, -- Dimitrios Chr. Ioannidis ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On Thu, December 8, 2011 08:48, Graeme Geldenhuys wrote: On 8 December 2011 09:25, Felipe Monteiro de Carvalho wrote: . . And what about people using FPC only and depending on our Random being statistically strong, they are less important then theorical Delphi migrants? [like what was told to me numerous times before] They (FPC users) should speak up now, or forever hold your peace. And those that have spoken so far, all seem to be fine with a less statistically strong default Random(), and have the statistically strong one available in the Maths unit. It's always that people who want changes are louder than those who are happy with the current state. Changing something (to worse, at least for some users) shouldn't be done just because people not happy with the current state are louder than those who are happy now, should it? Anyway: some people expressed their wish to keep the current solution as the default option exactly like you suggested, and you still argue with them that their view is not valid - strange... Tomas ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
2011/12/8 Tomas Hajny : Anyway: some people expressed their wish to keep the current solution as the default option exactly like you suggested, Did I suggest this? and you still argue with them that their view is not valid - strange... Clearly somewhere our lines have crossed. Strange indeed... -- Regards, - Graeme - ___ fpGUI - a cross-platform Free Pascal GUI toolkit http://fpgui.sourceforge.net ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On Thu, December 8, 2011 16:08, Graeme Geldenhuys wrote: 2011/12/8 Tomas Hajny : Anyway: some people expressed their wish to keep the current solution as the default option exactly like you suggested, Did I suggest this? . . Sorry, I wasn't clear - you suggested that people interested in keeping the current solution raised their voice (which at least Felipe and Karl-Michael did). Tomas ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 12/8/2011 02:48, Graeme Geldenhuys wrote: On 8 December 2011 09:25, Felipe Monteiro de Carvalho wrote: And what about people using FPC only and depending on our Random being statistically strong, they are less important then theorical Delphi migrants? [like what was told to me numerous times before] They (FPC users) should speak up now, or forever hold your peace. And those that have spoken so far, all seem to be fine with a less statistically strong default Random(), and have the statistically strong one available in the Maths unit. i wouldn't say specifically place it in the maths unit but what's wrong with having both available via a fastrandom boolean parameter that is passed? if the parameter is not passed, it is defaulted to TRUE... if one wants the MT random, then they send FALSE in this parameter... seems simple enough... i think ;) ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 8 December 2011 19:51, waldo kitty wrote: fastrandom boolean parameter that is passed? if the parameter is not passed, it is defaulted to TRUE... if one wants the MT random, then they send FALSE in this parameter... seems simple enough... i think ;) That sounds perfect to me, but now will the FPC team accept such a patch (with their double standards and all)? I don't mind implementing such a change, but let me know first if I will be wasting my time or not on a patch that will probably never be accepted. -- Regards, - Graeme - ___ fpGUI - a cross-platform Free Pascal GUI toolkit http://fpgui.sourceforge.net ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
My Delphi's random is only 7 times faster then fpc's random (Celeron 700). Bart On 12/8/11, Marco van de Voort mar...@stack.nl wrote: In our previous episode, Tomas Hajny said: the default option exactly like you suggested, Did I suggest this? Sorry, I wasn't clear - you suggested that people interested in keeping the current solution raised their voice (which at least Felipe and Karl-Michael did). And me. I don't see anything in a manager-record solution for this. I'd be happy to have a random package in packages/ with a bunch of random mgrs, but I don't see the urgent need to make this default if a better solution is already there. It is like the fast trunc/round discussions over again. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
Reimar Grabowski schrieb: The parameter should default to FALSE to not break existing code relying on FPCs random function And what about existing code coming from Delphi/Turbo Pascal? This was a strong argument in the past for doing even crap coding. As the fast random function then has to be called with random(x, true) I think this would be the best solution: Add an additional parameter to random() so that existing code would stop on compiling and the user has to look up the help to see what this additional parameter means. Then everybody is forced to choose the version that fits for his needs. But having the same function doing something different (or at a magnitude different speed) is the wrong way IMO. Just imagine that divisions suddenly need 500 times the time because the last digit was inaccurate or so. In many cases the error is not relevant in your programs but the speed penalty surely would. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
Am 09.12.2011 07:27, schrieb Jürgen Hestermann: Reimar Grabowski schrieb: The parameter should default to FALSE to not break existing code relying on FPCs random function And what about existing code coming from Delphi/Turbo Pascal? This was a strong argument in the past for doing even crap coding. As said before, this came only up because for every difference somebody popped up and cried. When random was implemented using MT, we didn't learn this lesson. Just imagine that divisions suddenly need 500 times the time because the last digit was inaccurate or so. According to measurements of me and other peoples, random is only 7-10 times slower (depending on the CPU). ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 9 December 2011 09:47, Florian Klaempfl wrote: According to measurements of me and other peoples, random is only 7-10 times slower (depending on the CPU). What do you feed your computer, because mine differs vastly from yours. Not to mention that our clients still run P4 workstations under Win2000 or XP. So lets hope no production code uses Random() a lot. -- Regards, - Graeme - ___ fpGUI - a cross-platform Free Pascal GUI toolkit http://fpgui.sourceforge.net ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
[fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
Hi,
I'm busy working on some of the remaining unit tests for the tiOPF
project that doesn't run 100% to my satisfaction yet under FPC
(compared to Delphi 7). One of the tests is for a Simple Encryption
algorithm implemented in tiOPF, that runs extremely slow under FPC
2.4.x (and 2.6.0-rc), and near instant under Delphi 7. I'm trying to
figure out why.
Below is a snippet of code I tracked down which contains the slowdown.
The problem under FPC lies with line 08, and more specifically the
call to Random(255). Simply replacing the Random(255) call with a
variable speeds up the loop by some 529 times!
I did a simple GetTickCount() timing around this loop. Delphi executes
the loop in 20 ticks. FPC 2.6.0-rc2 takes 10585 ticks The outer
loop runs 200400 iterations. The types for BitValue, ByteValue and
RandSeed is of type Byte.
01 for Index := 1 to Length(Source) do
02 begin
03OrdValue := Ord(Source[Index]);
04for BitCount := 0 to 7 do
05begin
06 BitValue := Byte(OrdValue and (1 shl BitCount) = 1 shl BitCount);
07 RandSeed := ByteValue;
08 ByteValue := (((Random(255) + 1) div 2) * 2) + BitValue;
09 Result[(Index - 1) * 8 + BitCount + 1] := AnsiChar(ByteValue);
10end;
11 end;
I'm using 64bit Ubuntu Linux 10.04.3 with 64-bit FPC 2.6.0-rc2.
Anybody have any ideas why the code under FPC runs so slowly? Is it
maybe some type conversion problem in FPC? I noticed that Random()
returns a Int64 on my Linux system. I'm not sure what it returns under
Delphi 7 (the docs don't say, and I can see the implementation of it).
If you wanted to test this, I attached a fully working program code
(snippets from the original tiOPF code) to demonstrate the problem.
--
Regards,
- Graeme -
___
fpGUI - a cross-platform Free Pascal GUI toolkit
http://fpgui.sourceforge.net
program speedtest;
{$IFDEF FPC}
{$mode delphi}{$H+}
{$ELSE}
{$APPTYPE Console}
{$ENDIF}
uses
Classes, SysUtils;
function GetTickCount: Cardinal;
begin
Result := Cardinal(Trunc(Now * 24 * 60 * 60 * 1000));
end;
function GetTestString: string;
var
i : integer;
lsLine : string;
begin
SetLength(lsLine, 1000);
for i := 1 to 1000 do
lsLine[ i ]:= Chr(ord('A')+random(ord('z')-ord('A')));
for i := 1 to 200 do
result := result + lsLine + #13 + #10;
result := result + 'x'; // make it an odd number
end;
function EncryptString(const psData : AnsiString): AnsiString;
var
OrdValue: Byte;
Index: Integer;
BitCount: Integer;
BitValue: Byte;
ByteValue: Byte;
Source: ansiString;
c: Cardinal;
begin
writeln('Length(psData) = ', Length(psData));
ByteValue := Random(255) + 1;
writeln('ByteValue: ', ByteValue);
Source := psData;
writeln('Length(Source) = ', Length(Source));
SetLength(Result, Length(Source) * 8);
writeln('First Loop');
c := GetTickCount;
for Index := 1 to Length(Source) do
begin
OrdValue := Ord(Source[Index]);
for BitCount := 0 to 7 do
begin
BitValue := Byte(OrdValue and (1 shl BitCount) = 1 shl BitCount);
RandSeed := ByteValue;
ByteValue := (((Random(255) + 1) div 2) * 2) + BitValue;
{ Replace the above line with the following to see the speed difference }
// ByteValue := (((ByteValue + 1) div 2) * 2) + BitValue;
Result[(Index - 1) * 8 + BitCount + 1] := AnsiChar(ByteValue);
end;
end;
writeln('elapsed time: ', GetTickCount - c);
end;
var
s: string;
begin
Randomize;
s := GetTestString;
s := EncryptString(s);
end.
___
fpc-pascal maillist - fpc-pascal@lists.freepascal.org
http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On Wed, 7 Dec 2011, Graeme Geldenhuys wrote: Hi, I'm busy working on some of the remaining unit tests for the tiOPF project that doesn't run 100% to my satisfaction yet under FPC (compared to Delphi 7). One of the tests is for a Simple Encryption algorithm implemented in tiOPF, that runs extremely slow under FPC 2.4.x (and 2.6.0-rc), and near instant under Delphi 7. I'm trying to figure out why. Below is a snippet of code I tracked down which contains the slowdown. The problem under FPC lies with line 08, and more specifically the call to Random(255). Simply replacing the Random(255) call with a variable speeds up the loop by some 529 times! I did a simple GetTickCount() timing around this loop. Delphi executes the loop in 20 ticks. FPC 2.6.0-rc2 takes 10585 ticks The outer loop runs 200400 iterations. The types for BitValue, ByteValue and RandSeed is of type Byte. 01 for Index := 1 to Length(Source) do 02 begin 03OrdValue := Ord(Source[Index]); 04for BitCount := 0 to 7 do 05begin 06 BitValue := Byte(OrdValue and (1 shl BitCount) = 1 shl BitCount); 07 RandSeed := ByteValue; 08 ByteValue := (((Random(255) + 1) div 2) * 2) + BitValue; 09 Result[(Index - 1) * 8 + BitCount + 1] := AnsiChar(ByteValue); 10end; 11 end; I'm using 64bit Ubuntu Linux 10.04.3 with 64-bit FPC 2.6.0-rc2. Anybody have any ideas why the code under FPC runs so slowly? Is it maybe some type conversion problem in FPC? I noticed that Random() returns a Int64 on my Linux system. I'm not sure what it returns under Delphi 7 (the docs don't say, and I can see the implementation of it). I think the random() algorithm is simply much more complicated in FPC. It tries very hard to get an evenly distributed random number, more so than Delphi, probably. Jonas Maebe implemented it, I think, he can probably shed some more light on this. Michael. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 07 Dec 2011, at 13:51, michael.vancann...@wisa.be wrote: I think the random() algorithm is simply much more complicated in FPC. That's correct. We use the mersenne twister, Delphi probably a linear congruential generator. The mersenne twister has a much larger period. Jonas ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 7 December 2011 14:54, Jonas Maebe wrote: That's correct. We use the mersenne twister, Delphi probably a linear congruential generator. The mersenne twister has a much larger period. OK thanks for the info. This is a serious performance hit, but I understand that the FPC implementation is different. Does FPC have a faster (comparable to Delphi) version of Random() too? @Michael, Should the FPC docs maybe mention the fact that the FPC version is considerably slower that Delphi (with an explanation why of course) - purely for the purpose of informing those porting code from Delphi to FPC. The original code in tiOPF is so slow, I almost thought the program froze - thus making that code really unusable in an application. Luckily that code will normally not be used in a real app though. Delphi developers wanting to move to FPC should really be warned about this, and use Random() sparingly. -- Regards, - Graeme - ___ fpGUI - a cross-platform Free Pascal GUI toolkit http://fpgui.sourceforge.net ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
Why not use the previous fpc version - I guess similar to that in delphi- I can remember an email when Jonas changed it quite a few years ago - Jonas must have older version - but can't really remember the fpc version - v1.0? My guess it could be found in either svn or more likely the older cvs fpc archive. John On 7 December 2011 13:10, Graeme Geldenhuys graemeg.li...@gmail.com wrote: On 7 December 2011 14:54, Jonas Maebe wrote: That's correct. We use the mersenne twister, Delphi probably a linear congruential generator. The mersenne twister has a much larger period. OK thanks for the info. This is a serious performance hit, but I understand that the FPC implementation is different. Does FPC have a faster (comparable to Delphi) version of Random() too? @Michael, Should the FPC docs maybe mention the fact that the FPC version is considerably slower that Delphi (with an explanation why of course) - purely for the purpose of informing those porting code from Delphi to FPC. The original code in tiOPF is so slow, I almost thought the program froze - thus making that code really unusable in an application. Luckily that code will normally not be used in a real app though. Delphi developers wanting to move to FPC should really be warned about this, and use Random() sparingly. -- Regards, - Graeme - ___ fpGUI - a cross-platform Free Pascal GUI toolkit http://fpgui.sourceforge.net ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
2011/12/7 Peter pe...@pblackman.plus.com: Graeme, I would recommend using Marsaglia's XORShift. Blisteringly fast, high quality statistically, and very easy to implement. http://en.wikipedia.org/wiki/Xorshift For those who want to test it here is an Object Pascal implementation. -- Inoussa O. hrandom.pas Description: Binary data ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
How does it compare re 'randomness' cf current fpc version? The wikipedia reference doesn't make this clear. Or the original fpc/delphi versions? Jonas? John On 7 December 2011 14:08, Inoussa OUEDRAOGO inouss...@gmail.com wrote: 2011/12/7 Peter pe...@pblackman.plus.com: Graeme, I would recommend using Marsaglia's XORShift. Blisteringly fast, high quality statistically, and very easy to implement. http://en.wikipedia.org/wiki/Xorshift For those who want to test it here is an Object Pascal implementation. -- Inoussa O. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 7 December 2011 15:54, Peter peter@. wrote: I would recommend using Marsaglia's XORShift. Blisteringly fast, high quality statistically, and very easy to implement. Thanks for the info. Like I said, the original code in tiOPF is just an extra [sample / simple] encryption implementation. There already exists more secure encryption implementations in tiOPF, based on DES Blowfish. The latter two will be used in real-world applications, and the simple encryption not. Either way, I'll add this to my todo list, to improve the simple encryption - but it's a low priority item at the moment. -- Regards, - Graeme - ___ fpGUI - a cross-platform Free Pascal GUI toolkit http://fpgui.sourceforge.net ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 7 December 2011 14:54, Jonas Maebe jonas.maebe@ wrote: That's correct. We use the mersenne twister, Delphi probably a linear congruential generator. The mersenne twister has a much larger period. I was reading a bit more about this. The Mersenne Twister (MT) generator has a massive period of 2^19937−1, compared to the XorShift generator, which in turn has a period of 2^128-1. Most text I read mentions that MT is great for statistical purposes, and performs well in its class. So wouldn't it maybe make more sense to let the standard (read more common) Random() call use a higher performance random number generator, with a much lower period. Then add the MT generator as a call to the Maths unit - where more statistical functions are located? Most applications are not statistical apps, they just want a random number here or there, so such high period low performance generator is normally not required. Having it in the Maths unit still makes in available when needed though - for those specialised apps. Just a thought... -- Regards, - Graeme - ___ fpGUI - a cross-platform Free Pascal GUI toolkit http://fpgui.sourceforge.net ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
Am 07.12.2011 16:03, schrieb Graeme Geldenhuys: On 7 December 2011 14:54, Jonas Maebe jonas.maebe@ wrote: That's correct. We use the mersenne twister, Delphi probably a linear congruential generator. The mersenne twister has a much larger period. I was reading a bit more about this. The Mersenne Twister (MT) generator has a massive period of 2^19937−1, compared to the XorShift generator, which in turn has a period of 2^128-1. Most text I read mentions that MT is great for statistical purposes, and performs well in its class. So wouldn't it maybe make more sense to let the standard (read more common) Random() call use a higher performance random number generator, with a much lower period. Well, once we thought we try to do things better than Delphi ;) Some people, I think John Lee, asked for a better random in FPC years ago so Jonas implemented a MT. Then add the MT generator as a call to the Maths unit - where more statistical functions are located? Most applications are not statistical apps, they just want a random number here or there, so such high period low performance generator is normally not required. Having it in the Maths unit still makes in available when needed though - for those specialised apps. Just a thought... FPC uses MT at least for 10 years and nobody complained about performance yet. So I suspect the cases might be very rare when random performance matters and having good random numbers is always a good thing ... I prefer not to change it but it's fine for me for delphi compatibility's sake ;) ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
Maybe implementing something other : The main advantages of the MWC method are that it invokes simple computer integer arithmetic and leads to very fast generation of sequences of random numbers with immense periods, ranging from around 260 to 2200. http://en.wikipedia.org/wiki/Multiply-with-carry 2011/12/7 Florian Klaempfl flor...@freepascal.org: Am 07.12.2011 16:03, schrieb Graeme Geldenhuys: On 7 December 2011 14:54, Jonas Maebe jonas.maebe@ wrote: That's correct. We use the mersenne twister, Delphi probably a linear congruential generator. The mersenne twister has a much larger period. I was reading a bit more about this. The Mersenne Twister (MT) generator has a massive period of 2^19937-1, compared to the XorShift generator, which in turn has a period of 2^128-1. Most text I read mentions that MT is great for statistical purposes, and performs well in its class. So wouldn't it maybe make more sense to let the standard (read more common) Random() call use a higher performance random number generator, with a much lower period. Well, once we thought we try to do things better than Delphi ;) Some people, I think John Lee, asked for a better random in FPC years ago so Jonas implemented a MT. Then add the MT generator as a call to the Maths unit - where more statistical functions are located? Most applications are not statistical apps, they just want a random number here or there, so such high period low performance generator is normally not required. Having it in the Maths unit still makes in available when needed though - for those specialised apps. Just a thought... FPC uses MT at least for 10 years and nobody complained about performance yet. So I suspect the cases might be very rare when random performance matters and having good random numbers is always a good thing ... I prefer not to change it but it's fine for me for delphi compatibility's sake ;) ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
FPC uses MT at least for 10 years and nobody complained about performance yet. So I suspect the cases might be very rare when random performance matters and having good random numbers is always a good thing ... I prefer not to change it but it's fine for me for delphi compatibility's sake ;) Or maybe it's because no one had anything to compare it to. I have a program that sends encrypted data every night to our data base. The encryption part (which I wrote with random numbers) is VERY slow. I never gave it much thought since it is running at a time where not much else is happening. But I will look into it now. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
I have noticed the following code in Tstrings, in the quicksort; Pivot := L + Random(R - L); // they say random is best On 07/12/11 13:10, Graeme Geldenhuys wrote: On 7 December 2011 14:54, Jonas Maebe wrote: That's correct. We use the mersenne twister, Delphi probably a linear congruential generator. The mersenne twister has a much larger period. OK thanks for the info. This is a serious performance hit, but I understand that the FPC implementation is different. Does FPC have a faster (comparable to Delphi) version of Random() too? @Michael, Should the FPC docs maybe mention the fact that the FPC version is considerably slower that Delphi (with an explanation why of course) - purely for the purpose of informing those porting code from Delphi to FPC. The original code in tiOPF is so slow, I almost thought the program froze - thus making that code really unusable in an application. Luckily that code will normally not be used in a real app though. Delphi developers wanting to move to FPC should really be warned about this, and use Random() sparingly. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
Florian Klaempfl schrieb: Well, once we thought we try to do things better than Delphi ;) Some people, I think John Lee, asked for a better random in FPC years ago so Jonas implemented a MT. I think there are two very different approaches. I wrote a small tool for testing network performance that simply generates a file with random numbers. I used random() for the data because I wanted to avoid any possible compression. There is no need to have a *real* random number in this case. I always wondered, why this program reported slightly faster network transfer in Delphi than in Lazarus/FPC but now I now why. Here it is a bad thing that the calculation of the random numbers impacts the speed calculation. IMO the generation of numbers should be much faster than 100 MB/s but it already delays the whole process. A completely different thing is statistics. Then you realy need a good random() function. In this case the quality of the numbers is much more important than speed. But now we have a fast random() function in Delphi and a statistical good one in FPC but none of them has both. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
- Jürgen Hestermann juergen.hesterm...@gmx.de schreef: But now we have a fast random() function in Delphi and a statistical good one in FPC but none of them has both. just my 2cts, but... The Delphi 7 help states about function System.Random [ ( Range: Integer) ]; the following -- In Delphi code, Random returns a random number within the range 0 = X Range. If Range is not specified, the result is a real-type random number within the range 0 = X 1. To initialize the random number generator, add a single call Randomize or assign a value to the RandSeed variable before making any calls to Random. Note: Because the implementation of the Random function may change between compiler versions, we do not recommend using Random for encryption or other purposes that require reproducible sequences of pseudo-random numbers. -- I would argue that: - using Random for encryption always was a bad idea - you have largely incompatible implementations and expectations when you want to make code fpc+delphi7 compilable As for other Random functions, Delphi7 also has Math.RandG (gaussian distribution around a mean) and Math.RandomRange. I would suggest the Math.RandomMT and a simpler, faster random method + good documenting. The above Delphi-help snippet also discourages explicitly the use for encryption and other purposes. A See also could be used to get some statistically better distributed random numbers. OR, what was suggested with the pluggable Random number generatorcall like the memorymanagers. like I said, just my 2cts... kind regards, Dimitri Smits ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 7 December 2011 19:31, Jürgen Hestermann juergen.hestermann@... wrote: compression. There is no need to have a *real* random number in this case. I always wondered, why this program reported slightly faster network transfer in Delphi than in Lazarus/FPC but now I now why. Here it is a bad thing that I just found another slow-down case in my code too. I have a data generator that uses Random() for various things. I generate a few million records of data to stress test our application. I always thought the slowness was due to the data being stored on a RDBMS, but some testing revealed that a large portion of the time taken to complete the task is actually the numerous calls to Random(), not solely the data storage as I always suspected. Apparently XorShift can generate 125 million random numbers per second [see url and page 5] - that's if I understood the technical paper correctly, and not sure what machine they used for the test. --- http://www.jstatsoft.org/v08/i14/paper A completely different thing is statistics. Then you realy need a good random() function. In this case the quality of the numbers is much more important than speed. Exactly. There are multiple cases for using random numbers. The average Joe does care too much about the quality of the numbers. Allowing FPC to have multiple random number generators - via two or more different functions, or a plugable generator - does seem like a good solution. I would suggest the default Random() call uses a higher speed performance generator though, and not the MT one. -- Regards, - Graeme - ___ fpGUI - a cross-platform Free Pascal GUI toolkit http://fpgui.sourceforge.net ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
Graeme Geldenhuys schrieb: I would suggest the default Random() call uses a higher speed performance generator though, and not the MT one. Fully agree. Especially, because ex Delphi (and ex Turbo Pascal) users would expect it like that. And most of them (coming from Delphi/TP) believe that the randomness is not very reliable. They mainly don't even know (like me) that the FPC random() is much more sophisticated. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On Thu, Dec 8, 2011 at 7:27 AM, Jürgen Hestermann juergen.hesterm...@gmx.de wrote: Fully agree. Especially, because ex Delphi (and ex Turbo Pascal) users would expect it like that. And most of them (coming from Delphi/TP) believe that the randomness is not very reliable. They mainly don't even know (like me) that the FPC random() is much more sophisticated. Based on what they expect that? For sure not based on reading the Delphi documentation about Random: http://docs.embarcadero.com/products/rad_studio/delphiAndcpp2009/HelpUpdate2/EN/html/delphivclwin32/System_Random.html There is no mention of it being fast and also not about it being weak statistically, so those are undocumented behavior. But it is written: Note: Because the implementation of the Random function may change between compiler versions, we do not recommend using Random for encryption or other purposes that require reproducible sequences of pseudo-random numbers. So are we supporting usage of Random in Delphi which depends on implementation details even while the documentation never said they were guaranteed but instead explicitly says it can change? And what if it changes in the future to being slow and statistically strong, we change again too? And what about people using FPC only and depending on our Random being statistically strong, they are less important then theorical Delphi migrants? -- Felipe Monteiro de Carvalho ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
Am 08.12.2011 08:25, schrieb Felipe Monteiro de Carvalho: On Thu, Dec 8, 2011 at 7:27 AM, Jürgen Hestermann juergen.hesterm...@gmx.de wrote: Fully agree. Especially, because ex Delphi (and ex Turbo Pascal) users would expect it like that. And most of them (coming from Delphi/TP) believe that the randomness is not very reliable. They mainly don't even know (like me) that the FPC random() is much more sophisticated. Based on what they expect that? In this border case they expect delphi compatibility because it effects their code and not others. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
On 8 December 2011 09:25, Felipe Monteiro de Carvalho wrote: And what if it changes in the future to being slow and statistically strong, we change again too? The random number generator can be implemented in such a way that the backend generator is user selectable. And what about people using FPC only and depending on our Random being statistically strong, they are less important then theorical Delphi migrants? [like what was told to me numerous times before] They (FPC users) should speak up now, or forever hold your peace. And those that have spoken so far, all seem to be fine with a less statistically strong default Random(), and have the statistically strong one available in the Maths unit. -- Regards, - Graeme - ___ fpGUI - a cross-platform Free Pascal GUI toolkit http://fpgui.sourceforge.net ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
Re: [fpc-pascal] Why is Random(255) some 529x slower compared to Delphi 7?
Am 08.12.2011 08:48, schrieb Graeme Geldenhuys: [like what was told to me numerous times before] They (FPC users) should speak up now, Actually those who depend on speed should have spoken up ten years ago when the MT was implemented. ___ fpc-pascal maillist - fpc-pascal@lists.freepascal.org http://lists.freepascal.org/mailman/listinfo/fpc-pascal
