From owner-freebsd-hackers@FreeBSD.ORG Wed Jun 13 19:30:45 2007 Return-Path: X-Original-To: hackers@freebsd.org Delivered-To: freebsd-hackers@FreeBSD.ORG Received: from mx1.freebsd.org (mx1.freebsd.org [69.147.83.52]) by hub.freebsd.org (Postfix) with ESMTP id 52E0216A480 for ; Wed, 13 Jun 2007 19:30:45 +0000 (UTC) (envelope-from kientzle@freebsd.org) Received: from kientzle.com (h-66-166-149-50.snvacaid.covad.net [66.166.149.50]) by mx1.freebsd.org (Postfix) with ESMTP id EE1EA13C48C for ; Wed, 13 Jun 2007 19:30:44 +0000 (UTC) (envelope-from kientzle@freebsd.org) Received: from [10.0.0.222] (p54.kientzle.com [66.166.149.54]) by kientzle.com (8.12.9/8.12.9) with ESMTP id l5DJ0vH7071350; Wed, 13 Jun 2007 12:00:57 -0700 (PDT) (envelope-from kientzle@freebsd.org) Message-ID: <46703EE9.1030804@freebsd.org> Date: Wed, 13 Jun 2007 12:00:57 -0700 From: Tim Kientzle User-Agent: Mozilla/5.0 (X11; U; FreeBSD i386; en-US; rv:1.7.12) Gecko/20060422 X-Accept-Language: en-us, en MIME-Version: 1.0 To: youshi10@u.washington.edu References: In-Reply-To: Content-Type: text/plain; charset=us-ascii; format=flowed Content-Transfer-Encoding: 7bit Cc: hackers@freebsd.org Subject: Re: Using shell commands versus C equivalents X-BeenThere: freebsd-hackers@freebsd.org X-Mailman-Version: 2.1.5 Precedence: list List-Id: Technical Discussions relating to FreeBSD List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , X-List-Received-Date: Wed, 13 Jun 2007 19:30:45 -0000 >>> Next step, eliminating the linked list structure in favor or red-black >>> trees, maybe. >> >> Due to the way pkg_install works, this most likely is just adding >> complexity for no gain, it might actually slow it down. > > Hmmm... the only thing is that it does the linked list traversal a > number of times per dependency. I'll take a look in gdb at the size of > each dependency and then confer with Kirill (my mentor) about that a bit > more. If you tend to look for the same few items over and over, just move items to the front of the list as soon as you find them. Alternatively, if you know you won't look for this item ever again, move it to the end of the list or remove it from the list entirely. Simple tricks like this can greatly speed things up with almost no effort. Better yet, do easy things like this first; if they help, then look at more complex approaches. As Joerg said, though, you're not likely to gain much from this. pkg_install is almost entirely disk bound. I spent a lot of time recently in libarchive/bsdtar optimizing the disk handling; I can share lots of ideas for improving performance of disk-bound operations like this. Tim Kientzle