tar is slow with --listed-incremental

[Jean-Louis Martineau]

Hi,

tar is very slow when use with the --listed-incremental.

As an example, backing up a directory took 70 minutes. the same directory
with --newer took only 20 minutes.

The pass where it collect the names are not optimized, it use two
lists (namelist and directory_list) and scan them too often.
This is O(n x n).

I optimized them and it now took only 25 minutes.

Patch 1 (namelist):
  The function add_hierarchy_to_namelist() call itselt recursivily with:
       addname (name_buffer, change_dir);
       add_hierarchy_to_namelist (name_buffer, change_dir, device);

  addname add at the end of the list, so it will scan all the list
  at the begining of add_hierarchy_to_namelist to find it.

  The patch check the last item of the list before searching the whole list.


Patch 2 (directory_list):
  This patch use an AVL instead of a list. I can't include the patch
  because the AVL code is not GPL. My experiment show that this patch
  is important.

  Do you know where I can find GPL code for a balanced tree? 

Jean-Louis
member of the AMANDA team.
-- 
Jean-Louis Martineau             email: address@hidden 
Departement IRO, Universite de Montreal
C.P. 6128, Succ. CENTRE-VILLE    Tel: (514) 343-6111 ext. 3529
Montreal, Canada, H3C 3J7        Fax: (514) 343-5834

tar-1.13.17-names.c.namelast
Description: Text document