Re: [Swig-user] Performance bug in pycontainers.swg

[Eric M. <eri...@gm...>]

On 5/19/07, gga <gg...@ad...> wrote:
> Eric Mahurin wrote:
> > I'm guessing that push/insert aren't functioning and
> > the above is just the ruby loop time - which should also show O(n)
> > eventually.
> >
>
> No, the elements are there.   Feel free to download the latest swig SVN
> and try it (I also checked the test in as li_std_speed_runme.rb).
> I guess that's a good measure of how bad the performance on python
> currently is.

The results look more reasonable now.  In your previous results, this
is what insert/push_back looked like:

    8192( 0.594745)( 0.000041)( 0.000072)( 0.000188)
   16384( 2.201943)( 0.000040)( 0.000072)( 0.000381)

Ignoring vector (which it looks like you fixed), the others looked
several orders of magnitude faster than the other benchmarks and
looked to have sub-linear runtime.  I'd expect all of the benchmarks
to have O(n) (except set insert : O(n*log(n)) and there to be a small
constant difference between all of them for the same container size.

> AFAIK, Integers are just much faster and efficient in ruby than in
> python, as they are stored as odd pointers.  IIRC, Python2.3+ uses a
> full class with a local memory pool for them.
> Storage speed/memory of ruby will be more similar to python if you
> actually store a real class (like a string, a float, custom class, etc).

I've always thought this was an ingenous idea of Matz to encode common
objects directly in the pointer taking advantage of the fact that
object pointers are word (32-bit or 64-bit) aligned so that illegal
pointer values can be used for something else.

Your ruby results look great now.  All these benchmarks look linear
except which set insert which looks O(n*log(n)).  You might add the
set insert method that takes a hint iterator to get an expected O(n)
performance.

Since the big-O performance of every STL function/method is well
documented (at least on SGI's site), it might be a good idea to test
the performance in addition to the functionality.

Also, I just ran these benchmarks again with the fix I originally
posted in this thread (make PySequence_Cont::check a nop and always
return true) and all of these benchmarks work fine.  In the test, I
also added a big-O calculations (based on the largest 2 n's) and
disabled garbage collection.  Here are the results (python):

iterate_end
        n   pyvector    pydeque      pyset     pylist
 ...
    65536       0.52       0.55       0.54       0.54
   131072       1.06       1.08       1.08       1.08
   262144       2.10       2.15       2.17       2.18
   524288       4.20       4.30       4.35       4.34
      n**     1.0000     1.0000     1.0033     0.9934
iterate
        n   pyvector    pydeque      pyset     pylist
...
    65536       0.24       0.24       0.25       0.25
   131072       0.47       0.49       0.49       0.51
   262144       0.95       0.97       1.01       0.99
   524288       1.90       1.90       1.93       1.99
      n**     1.0000     0.9699     0.9342     1.0073
insert
        n   pyvector    pydeque      pyset     pylist
...
    65536       0.13       0.12       0.50       0.14
   131072       0.25       0.24       1.02       0.28
   262144       0.49       0.47       2.09       0.56
   524288       0.98       0.94       4.29       1.12
      n**     1.0000     1.0000     1.0375     1.0000
erase
        n   pyvector    pydeque      pyset     pylist
...
    65536       0.96       1.01       1.13       1.03
   131072       1.97       2.02       2.24       1.92
   262144       3.79       4.03       4.49       3.79
   524288       7.62       8.33       9.13       7.76
      n**     1.0076     1.0475     1.0239     1.0339