[Python-Dev] decorate-sort-undecorate

[Tim Peters]

[Phillip J. Eby]
> What expense?  The extra memory overhead for the index?  I suppose
> so.

Yes, that is an expense.  Partly because of the extra memory space in
len(list) temp tuples, but mostly because space allocated for integer
objects is immortal.  That is,

    range(10000000)

grabs space for 1000000 distinct integer objects that's never reused for any
other kind of object, and so does stuffing a million distinct int objects
into a temp DSU list.  Note that this is very different from doing

    for i in xrange(1000000):

which allocates space for only three integer objects (100000, the current
value of i, and preceding value of i), and keeps reusing it.

A cleverer implementation might be able to avoid permanently ratcheting the
space devoted to int objects.

> But if you *don't* want that behavior, you can still DSU manually, no?

I hope so <wink>.