[PATCH] Use a hash rather than a linked-list for cycle check in cp

[Bo Borgerson]

This addresses a FIXME in src/copy.c:

----
-/* FIXME: rewrite this to use a hash table so we avoid the quadratic
-   performance hit that's probably noticeable only on trees deeper
-   than a few hundred levels.  See use of active_dir_map in remove.c  */
----

The performance benefit is there, but on my machine with a PATH_MAX of
4096 it's hard to see, because the userland work `cp' does is dwarfed
by the work the kernel does on its behalf:

----
$ time src/cp.master -r a b

real    0m54.032s
user    0m3.236s    <-- coreutils HEAD
sys     0m47.335s

$ time src/cp -r a c

real    0m53.475s
user    0m0.624s    <-- with patch
sys     0m48.639s
----

Thanks,

Bo

cp-hashcycle.diff
Description: Text Data