[MERGE] TreeTransform avoids many renames when constructing trees

[John Arbash Meinel]

-----BEGIN PGP SIGNED MESSAGE-----
Hash: SHA1

Aaron Bentley wrote:

...

>>> AIUI, it is faster to iterate through a list than a generator.
>> Well, you are creating a list to pass it to sorted, which generates another
>> list. I do believe that
>>   foo = sorted([list expression])
>> is better than
>>   foo = [list expression]
>>   foo.sort()
> 
> I can't parse that.  You either mean "list comprehension" or "generator
> expression", but they are significantly different in this context.
> 
> Anyhow, submitted.
> 
> Aaron

the function "sorted()" takes an iterable and returns a sorted list. You can
pass in a generator or a list or a set or whatever.

What I found was that for long (100k entry) lists that:

foo = sorted([x for x in something])

is slightly (<10%) faster than:

foo = sorted(x for x in something)

My only guess is that it can pre-allocate somehow. The tradeoff, however, is
that you have another copy of the data in memory. (in the temporary list).

The code in question was doing:
entries = [(self._limbo_name(t), t, k) for t, k in
           self._new_contents.iteritems()]
for path, trans_id, kind in sorted(entries, reverse=True):

which is using list comprehension to build up a list which it then passes to
sorted. And I was arguing that:

entries = sorted((self._limbo_name(t), t, k)
                 for t,k in self._new_contents.iteritems(),
                 reverse=True)
for path, trans_id, kind in entries:


can do the same thing at effectively the same speed but without creating an
intermediate list.

I also just found that doing:

x = [n for n in y]
x.sort()

isn't strictly slower than
x = sorted([n for n in y])

or

x = sorted(n for n in y)

It probably depends on how close to sorted the lists are.

John
=:->
-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.4.7 (Darwin)
Comment: Using GnuPG with Mozilla - http://enigmail.mozdev.org

iD8DBQFGZYyEJdeBCYSNAAMRAlI1AKCJMo6GwMDcaH+bTdHN7KP9CXo2dQCePRXy
8U88pDC7+lf0p0vk1ut7tgw=
=ZANF
-----END PGP SIGNATURE-----