From owner-freebsd-hackers  Mon Oct 16 15:29:30 1995
Return-Path: owner-hackers
Received: (from root@localhost)
          by freefall.freebsd.org (8.6.12/8.6.6) id PAA25623
          for hackers-outgoing; Mon, 16 Oct 1995 15:29:30 -0700
Received: from Root.COM (implode.Root.COM [198.145.90.17])
          by freefall.freebsd.org (8.6.12/8.6.6) with ESMTP id PAA25616
          for <hackers@freebsd.org>; Mon, 16 Oct 1995 15:29:27 -0700
Received: from corbin.Root.COM (corbin [198.145.90.50]) by Root.COM (8.6.12/8.6.5) with ESMTP id PAA23695; Mon, 16 Oct 1995 15:29:25 -0700
Received: from localhost (localhost [127.0.0.1]) by corbin.Root.COM (8.6.12/8.6.5) with SMTP id PAA15796; Mon, 16 Oct 1995 15:23:43 -0700
Message-Id: <199510162223.PAA15796@corbin.Root.COM>
To: "Justin T. Gibbs" <gibbs@freefall.freebsd.org>
cc: Olof Johansson <offe@dawnrazor.campus.luth.se>, hackers@freebsd.org
Subject: Re: wtmp efficiency 
In-reply-to: Your message of "Mon, 16 Oct 95 15:13:23 PDT."
             <199510162213.PAA19607@aslan.cdrom.com> 
From: David Greenman <davidg@Root.COM>
Reply-To: davidg@Root.COM
Date: Mon, 16 Oct 1995 15:23:40 -0700
Sender: owner-hackers@freebsd.org
Precedence: bulk

>>I've found (and fixed) the problem.
>>
>>It's the fact that ftp and uucp connections get 'ftp' or 'uucp' + pid as 
>>tty_line in wtmp. The pid isn't removed when looking up the tty, so the list 
>>gets bigger and bigger.
>>For 'ftp-only' wtmp files the time for parsing the file is proportional to 
>>n^2, where n is the number of entries in the file...
>>(I have an exam on data structures and algorithms next week *grin*).
>
>Well you've put a finger on the problem, but your patch breaks last for
>"last ftp" or "last uucp".
>
>A better solution is to only add entries to the tty list that match our
>interest, and to remove entries from the tty list once we find the matching
>login time.  Since the tty records are small, bcopying the next record
>over the matched record and freeing the next record should make the removal
>easy.  Care to do the honors?

   Actually, I'm writing this change right now, and will post the changes when
I'm finished... There are some other optimizations I'm making at the same time.

-DG