O(n^2) is bad - can it be fixed?

[Helen Dawson]

Tim Peters wrote:

> [Tim]
> In the meantime, I did check in a change (for 2.2) that continues to do mild
> over-allocation, but on a sliding scale that doesn't think the world ends at
> 500 elements.  This speeds real-life appends, but mostly because it gets rid
> of the current integer multiplication and division in favor of simple bit
> shifts.

For what it's worth - this might actually be one point in MS's favour. If I
remember correctly the divides in the roundup() routine are all dividing
by integer constants. VC++ deals with those very nicely. In optimized
builds (optimized for speed anyway) it is impossible to get it to emit a
divide instruction - it always replaces it with bit shifts. It does a
particularly efficient job if the number you are dividing is unsigned. It
doesn't matter what number you divide by - it knows how to simulate
dividing by every integer I've ever tested with.

So, you may have improved on a Win32-only problem, and also improved
on a non-Win32-only problem also. The symmetry appeals to me.

Bruce/Helen Dawson