[Python-Dev] decorate-sort-undecorate

[Guido van Rossum]

> [Fred]
> >> We could allocate a second array of PyObject* to mirror the list
> >> contents; that would have only the keys.  When two values are
> >> switched in the sort, the values in both the key list and the value
> >> list can be switched.  When done, we only need to decref the
> >> computed keys and free the array of keys.
> 
> [Guido]
> > I can't tell if that'll work, but if it does, it would be a great
> > solution.

[Tim]
> I mentioned that before -- doubling the amount of data movement would hurt,
> at best by blowing cache all to hell.
> 
> There's a related approach, though:  build a distinct vector of custom
> objects, each containing:
> 
> 1. A pointer to the key.
> 2. The original index, as a C integer.
> 
> This is similar to, but smaller than, something mentioned before.

But wouldn't the memory allocated for all those tiny custom objects
also be spread all over the place and hence blow away the cache?

I guess another approach would be to in-line those objects so that we
sort an array of structs like this:

  struct {
    PyObject *key;
    long index;
  }

rather than an array of PyObject*.  But this would probably require
all of the sort code to be cloned.

> The comparison function for this kind of object redirects to comparing only
> the keys -- the integers are ignored during the sort.  Sort this list with
> the sorting code exactly as it exists now.
> 
> At the end of sorting, the integer members can be used to permute the
> original list into order.  This can be done in-place efficiently (not
> entirely obvious; Knuth gives at least one algorithm for it).

--Guido van Rossum (home page: http://www.python.org/~guido/)