Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.misc > #4835

Re: My experience with using cp to copy a lot of files (432 million

Show all headers | View raw

This is an interesting post for programmers, but not for the quoted text.  
 From the FA:

>After some days of copying the first real surprise came: I noticed that the  
>copying had stopped, and cp did not make any system calls at all according  
>to strace. Reading the source code revealed that cp keeps track of which  
>files have been copied in a hash table that now and then has to be resized  
>to avoid too many collisions. When the RAM has been used up, this becomes a  
>slow operation. Trusting that resizing the hash table would eventually  
>finish, the cp command was allowed to continue, and after a while it started  
>copying again. It stopped again and resized the hash table a couple of  
>times, each taking more and more time.
Everyone 'knows' that hash tables are the fastest way to implement maps. The  
issue is that they are randomly accessed, so when they grow larger than the  
available memory, they tend to cause thrashing.

That's the cost of making a hash of locality of reference [1].

Tree structures can be slower for smaller sizes, but lookups are more likely  
to use the same area of the tree, so the 'working set' stays in memory.

Another issue is that with a hash you need to read the whole string to  
generate the hash. For a tree, if the string is not in the map, then you only  
need to read as much of the string as exists in the tree.

I experimented with both a hash and a ternary tree in a dictionary utility I  
wrote, and for large enough data sizes the ternary tree was faster.

With modern ram sizes it's only with very large maps that you need to think  
about this.



[1] https://en.wikipedia.org/wiki/Locality_of_reference
-- 
tdk

Take back your Internet! http://squte.com/Webertarian-Manifesto
View this thread at http://squte.com/usenet/my-experience-using-cp-copy-lot-files-432-million?src=u#comment-38915

Back to comp.misc | Previous | Next — Previous in thread | Find similar | Unroll thread

Thread

My experience with using cp to copy a lot of files (432 millions, 39 TB) Rich <rich@example.invalid> - 2014-09-12 01:58 +0000
  Re: My experience with using cp to copy a lot of files (432 million "tdk" <forum.tdk@squte.com> - 2014-09-12 03:59 -0500

csiph-web