=  David Harvey: would like to experiment further with speeding up object construction =

== Email announcing the project from David Harvey ==
 
hi people,
 
Just want to float an idea for discussion and possibly a coding  
sprint at SD3.
 
Some background: Today I did some work on speeding up getting  
coefficients out of NTL objects, specifically polynomials in Z[x].  
It's much improved now; when you request a coefficient of an NTL ZZX  
object, it copies the bytes directly into a new Integer object,  
instead of what it used to do (which went via a C string in decimal,  
and a python string, and a python long, etc etc).
 
But still what is taking a lot of time is constructing the Integer  
object. In fact, it's quite embarrasing: it takes us about half as  
long to construct 100,000 Integer objects as NTL takes to *multiply*  
two polynomials with 100,000 small coefficients:
{{{
sage: time for i in range(100000): pass
CPU times: user 0.05 s, sys: 0.00 s, total: 0.05 s
 
sage: time for i in range(100000): x = None
CPU times: user 0.09 s, sys: 0.00 s, total: 0.09 s
 
sage: time for i in range(100000): x = int()
CPU times: user 0.16 s, sys: 0.00 s, total: 0.17 s
 
sage: time for i in range(100000): x = Integer()
CPU times: user 0.36 s, sys: 0.00 s, total: 0.36 s
 
sage: f = PolynomialRing(ZZ, "x")([ZZ.random_element() for _ in range 
(100000)])
sage: time g = f*f
CPU times: user 0.76 s, sys: 0.02 s, total: 0.79 s
}}}
This is despite all the work we put into this at SD2.
 
It would be good to be able to optimise object construction in  
general. Unfortunately I think the general case is a very difficult  
problem. Anyone who worked on this at SD2 will agree, I'm sure 
 
On the other hand, I would wager that construction of Integer objects  
is by far the most important. So perhaps we should give up some  
beauty and unity of code to just get Integers working damn fast. So  
here's what I propose: at SD3, let's try writing an experimental pure  
C function for constructing Integers that gets inserted into whatever  
tp_xyz slot is appropriate. I don't care if it has to deal directly  
with mangled pyrex names or whatever. From memory, all it needs to do  
is:
(1) reference counting on the integer ring (ha ha we could even skip  
this if we could guarantee that no-one else ever resets the parent,  
and that there is always at least one reference to the integer ring  
lying around somewhere)
(2) malloc some space for the actual python object
(3) fill in some fields, like the TypeObject*
(4) mpz_init
 
Let's skip all the function calls, all the crap that pyrex puts in,  
etc etc. Basically the only stuff left that will really suck up time  
is the two malloc calls. We could even try writing a buffering system  
for mallocing space for a whole bunch of Integers at once, if that  
proves to be taking up time.
 
Similarly we would need a destructor.
 
I'm sure it's not quite as simple as what I've put in the above list,  
but let's just see what we can do. I would like it to be as close as  
possible to the int() construction time. We still are a factor of > 2  
away.
 
David


== Email back from William ==
{{{
> (1) reference counting on the integer ring (ha ha we could even skip
> this if we could guarantee that no-one else ever resets the parent,
> and that there is always at least one reference to the integer ring
> lying around somewhere)

There is my integer with the integer ring -- it should be immutable and
create at module load time and there should only ever be exactly one
copy of it.  I think we should definitely be allowed to forgot about
reference counting for it. 

> (2) malloc some space for the actual python object
> (3) fill in some fields, like the TypeObject*
> (4) mpz_init

You should put 
  (0) or (5) object pool
as an important step -- this "object pool" idea is one of the tricks
that Python uses for its ints.  For example, in your benchmark:

  time for i in range(10^5): x = int()

Python is looking up and returning exactly the same int (the 0) every time:
  sage: int() is int()
  True
  sage: a = 999038r; b=999038r
  sage: a is b
  True

In contrast, when you do Integer(), so is creating a new integer object
every time, and probably (?) also freeing one:
  sage: Integer() is Integer()
  False
  sage: a = 999038; b=999038
  sage: a is b
  False


> Let's skip all the function calls, all the crap that pyrex puts in,
> etc etc. Basically the only stuff left that will really suck up time
> is the two malloc calls. We could even try writing a buffering system
> for mallocing space for a whole bunch of Integers at once, if that
> proves to be taking up time.
>
> Similarly we would need a destructor.

Or return objects to the pool -- this can also speed up desctructing,
since you just don't do it!

> I'm sure it's not quite as simple as what I've put in the above list,
> but let's just see what we can do. I would like it to be as close as
> possible to the int() construction time. We still are a factor of > 2
> away.

This project is very very well worth pursing. 

  -- William
}}}

== Some Ideas from Robert Bradshaw ==
{{{
Some thoughts: I think a pool is a very important idea to consider. I
can think of two instances where 1000's of integer objects would be
created: first, in some large object such as a matrix or polynomial
(in which case there should be a specialized type) and second in some
huge loop (in which case a pool would help immensely).

Also, it'd be interesting to look at the distribution, but I wouldn't
be surprised if the majority of integers (ephemerally) created were
relatively small--say < 100s. Zero and one especially are used all
over. Similar to the pool idea, it might be worth allocating the
first 100 integers and whenever you want to create a "small" integer,
it would simply return one of these. (I think small one-limb mpz_t's
can be detected very easily with mpz_size and a bit mask.) Of course,
using python ints might be in order for many of these cases too.

A related idea came up in the discussion we had here on linear
algebra. Right now if one wants to optimize linear algebra over a new
ring one must re-implement matrix multiplication, addition, etc. The
generic algorithms request an entries (as a Python object), perform
the arithmetic, then store the resulting python object. This can be
hugely inefficient. Rather, what if the matrix had void* methods
_get_unsafe_raw(i,j) and _set_unsafe_raw(i,j), and the corresponding
ring had _add_raw(), _mul_raw(), etc. Also, the ring could have
_get_raw() and _create_from_raw(). For the integer ring, these would
return mpz_t* and, for instance, _mul_raw() could even be a macro to
mpz_mul. The generic base case would just pass around python objects.
The "reference counting" for these raw results would have to be done
manually. I would suggest giving them the same semantics as gmp. This
way one could implement generic polynomial/matrix/etc algorithms that
would be able to operate efficiently on any ring with the above
methods. For some cases (such as the integers) one would want actual
specialized matrices, etc. but it would greatly reduce the work to
get significant speedup for objects containing many elements of a
given generic ring. Also, it would make implementations for specific
ring elements easier to swap in and out (without having to change all
the types that access the element internals).
}}}