From: eric@... (Eric Lee Green) Date: 2001-08-05T01:32:06+09:00 Subject: [ruby-talk:19143] Re: Endianness and integer indexing -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 On Sat, 04 Aug 2001 08:01:33 GMT, Harry Ohlsen wrote: >> Oh, okay. I've noticed an interesting thing about [] though -- it is >> almost as slow as doing a " % 2" on the number! > >Fortunately, I'll only ever be playing with relatively small numbers, so >the speed isn't an issue for me. However, it sounds like there's an >opportunity for a cleanup on the [] method for BigNum. > >Strangely, I just tried writing a tiny two line routine to get the parity >and it performs only slightly better than using Ruby's & and is still not >as fast as [], which I find bizarre, since it's a cut-down version of the >code for [] !! > >Oh well. Someone's bound to come back and tell you how to make things >faster. I spent more time thinking on the subject last night, and I think that what I am running into is memory allocation overhead. [] itself runs in constant time regardless of the size of the integer, a 128-bit integer runs [] in the same amount of time as a 2048-bit integer, so it appears that [] itself is not doing something stupidly inefficient. 30,000 >> calls ought to run faster than 6,000 % calls when we're talking about 1024-bit numbers when we are talking about the two obvious implementations for gcd (Stein's binary gcd algo. vs. Euclidean gcd algo.), but the 6,000 % calls actually run close to 4 times faster. Clearly ruby is being swamped by something other than the cost of the operation itself. My suspicion is that it is memory allocation overhead. Hmm... ruby -r profile -e 'require "modexp.rb"' \ -e "a=128.random ; 30000.times { a.clone } " time seconds seconds calls ms/call ms/call name 53.23 2.14 2.14 2 1070.00 2010.00 Fixnum#times 46.77 4.02 1.88 30001 0.06 0.06 Numeric#clone .... Yep, it appears that creating and destroying bigints is a very expensive operation in Ruby. [eric@localhost ruby]$ ruby -r profile -e 'require "modexp.rb"' \ -e "a=128.random ; 30000.times { a % 5 } " % cumulative self self total time seconds seconds calls ms/call ms/call name 69.98 3.17 3.17 2 1585.00 2265.00 Fixnum#times shows that well. '%' on a 1024-bit number should take significant time, but it is clear that it is being swamped (lost in the noise) by the overhead of creating and destroying. The actual % took only 250ms, the rest of that is Ruby overhead for creating and destroying the bignums. [eric@localhost ruby]$ ruby -r profile -e 'require "modexp.rb"'\ -e "a=128.random ; 30000.times { a[0] } " % cumulative self self total time seconds seconds calls ms/call ms/call name 61.37 2.51 2.51 2 1255.00 2040.00 Fixnum#times 37.65 4.05 1.54 30000 0.05 0.05 Bignum#[] shows that [] itself is very fast, requiring only 40ms or so to execute 30,000 times, but again is being swamped by the overhead of creating and destroying objects. But [] is creating an integer, not a Bignum :-(. [eric@localhost ruby]$ ruby -r profile -e 'require "modexp.rb"' \ -e "a=128.random ; 30000.times { 5+1 } " % cumulative self self total time seconds seconds calls ms/call ms/call name 78.83 3.24 3.24 2 1620.00 2050.00 Fixnum#times 20.19 4.07 0.83 30000 0.03 0.03 Fixnum#+ This proves that the problem is the object creator/destructor, not the cost of the mathematical operations. So it appears that for anything that requires doing many operations, such as finding the greatest common denominator using the Stein binary gcd algorithm, I will need to move it into "C" entirely rather than implementing it in Ruby. This is nothing very new. I ran into this when I wrote the twofish-py module for Python. Even allocating my blocks (string objects) 8K at a time and encrypting blocks in 'C', Python's memory allocator limited my performance to a max of 2mb/sec. When I re-wrote the stream encrypter into "C" (using same low-level "C" routines, just finished moving the block slinger into "C"), I managed over 100mb/sec. I had hoped that Ruby's memory allocator was significantly faster, but perhaps I am running into limitations of the GNU 'libc' library, which is not known for its excellent speed. It appears that investigation of the object creator is warranted to see if there is a way to speed up creation of objects :-(. Eric Lee Green Web: http://www.badtux.org GnuPG public key at http://badtux.org/eric/eric.gpg Free Dmitry Sklyarov! [ http://www.eff.org ] -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.0.6 (GNU/Linux) Comment: For info see http://www.gnupg.org iD8DBQE7bB9L3DrrK1kMA04RAn/VAJ4uOJm82vcKOS60wAtULFmkV/AOrwCaAvrQ mICp8QY+YkxlklxvzrkB50c= =NY6T -----END PGP SIGNATURE-----