>Number:         30203
>Category:       bin
>Synopsis:       restore has apparently n^2 or worse algorithms
>Confidential:   no
>Severity:       serious
>Priority:       medium
>Responsible:    bin-bug-people
>State:          open
>Class:          sw-bug
>Submitter-Id:   net
>Arrival-Date:   Wed May 11 20:52:00 +0000 2005
>Originator:     Havard Eidnes
>Release:        NetBSD 2.0
>Organization:
	UNINETT AS
>Environment:
System: NetBSD smistad.uninett.no 2.0 NetBSD 2.0 (GENERIC) #12: Thu Dec 2 12:00:22 CET 2004 he@splitter-pine.urc.uninett.no:/work/netbsd-2-0/i386/obj/sys/arch/i386/compile/GENERIC i386
Architecture: i386
Machine: i386
>Description:
	When I last updated my system (due to a progressive disk
	failure), I upgraded from 1.6.2_STABLE to 2.0.  At that time
	I restored my backups, starting with a level 0 dump.
	My home file system is of this size:

Filesystem  Size   Used   Avail Capacity  iused    ifree  %iused  Mounted on
/dev/wd0g    61G    24G     34G    41%  2299703 13548743    14%   /home

	Note, it contains approximately 2.3 million files.
	Overwhelmingly these files can be found in my MH folders, a
	few of which are relatively large, a few with more than
	100.000 entries.

	The behaviour I noticed when doing restore of the level 0 dump
	was that after an initial activity of transfer from the remote
	system, the restore process stopped transferring data and
	instead went into CPU-busy mode.  The thing is that it took
	literally *hours* (on a 1GHz P3 system) before ot continued
	with actually reading the rest of the dump and restoring the
	files.

	I conclude that there must be some algorithms in restore which
	do not scale particularly well with some of the properties of
	the contents in my file system.
	
>How-To-Repeat:
	Try to restore a dump with lots of files and/or directories
	with lots of files.

	Watch it take a very long time between start of restore until
	it actually starts restoring files.

>Fix:
	Sorry, none supplied.