The attached patch bltmodule2.c.diff is a different implementation of 
the fast summation code for your consideration.

It uses three separate sums to add ints, floats and other objects.  All 
ints are accumulated into a C long, reset even after overflow.  All 
floats are added into a C double without mixing ints.  Other objects are 
handled as before.

This version has been tested with Python 2.5.2 as well and passed the 
existing regressions.

/Jean Brouwers

What is the benefit of this new implementation? If it is faster, can you
give us any performance numbers? (for example using timeit)

I did not compare performance (yet).  If there is a particular test 
case, I am happy to measure that.  Also, I made sure that the results 
and errors (!) for non-numeric items are the same as for the original, 
Slow Summation case.

The version I submitted is perhaps only slightly faster for most int and 
float cases, since it never creates and adds the 0 int default for the 
optional 'start' argument.

For other int and float cases it will certainly be faster.  Here are a 
few (extreme) examples.

1) Assume a long list consisting of one float followed by all ints.  The 
existing code will switch to the float loop at the very first float 
encountered and then use C double add (plus the FPE protection overhead) 
to add all subsequent ints.  My version will use C long adds for all 
ints, C double add for the float plus one C double add to combine the 
long and double results.

2) Consider a list of just 2 items, one float and one int (and no 
'start' argument).  The current code will first create a result object 
for the 'start' default 0.  Then, it enters the int loop (since result 
is an int, 0) and gets the first item, the float.  Since the item is not 
an int, it is added to the current result using PyNumber_Add.  Next, it 
falls into the float loop, since the result is now a float, presumably.  
Next, it gets the int item and adds that int as C double to the C double 
in f_result.  The end result C double f_result is returned as float.  
Quite costly for just one float and one int and maybe worse than than 
Slow Summation.

3) My version does not create a 0 int for the missing 'start'.  That is 
only created when absolutely needed at some later time.  In addition, 
all int items are added in C long i_sum and all floats are added in C 
double f_sum, regardless of the order they occur in the sequence.  At 
the end of the iteration loop, the C long i_sum is added to C double 
f_sum once and a single float object is created and returned.  That is 
very efficient and without any unnecessary overhead.

In other words, for sequences with mixed int and float objects the 
difference can be significant, depending on where the very first float 
item is located in the sequence and how may int follow.

However, for sequences with items of the same type, all int or all 
float, there will be little or no difference.  

/Jean Brouwers

PS) There are two additional things to consider for the float case:

- Ooverflow (ERANGE) and value (EDOM) errors in C double adds

- Using a compensating summation for floats, like Kahan's method.

Here is one, simple comparison between 3 different builtin_sum's, all 
measured on the same machine, MacOS X 10.4.11 (Intel Duo):

1) Python 2.5.1 ActiveState with standard Slow Summation:

% python2.5.1 -mtimeit --setup="x=[1.0e12, 7]*1000000" "sum(x)"
10 loops, best of 3: 177 msec per loop


2) Python 2.6a2 (built from source) with the existing Fast Summation:

% python2.6a2 -mtimeit --setup="x=[1.0e12, 7]*1000000" "sum(x)"
10 loops, best of 3: 52.5 msec per loop


3) Python 2.5.2 (built from source) with the submitted Fast Summation:

% python2.5.2 -mtimeit --setup="x=[1.0e12, 7]*1000000" "sum(x)"
10 loops, best of 3: 48.2 msec per loop

Will take a look at this one but am inclined to reject it.  The timing 
benefits are marginal at best and only help in the atypical case of 
mixed floats and ints. The patch changes the type and ordering of 
intermediate sums, resulting in different answers than the standard sum
().

In contrast, the existing fast sum() was carefully designed to mimick 
the operations of the original sum(), so it always produces the same 
results.

The one example given may not be convincing, other ones may be.

What is it in the submitted version which is not designed carefully or 
which may not produce the same results?

The approach of using separate accumulations is intrinsically flawed if 
you want the same result as a regular sum().  Here's a small dataset 
that shows why you can't accumulate separate sums by type:

>>> d = [1000000000000000, -
1000000000000000.0, .0000000000000001, .0000000000000001]
>>> sum(d)
2e-16
>>> d[0] + sum(d[1:])
0.0

Closing this one.  The approach is doomed and the possible benefits 
over the current approach are microscopic at best and only apply to 
unusual corner cases. 

I also prefer the current approach because it is easily extended to 
LongLongs and it is easy to show that the code is correct (at least 
with respect to producing the same result as a regular sum()).