X-Recipient: archive-cygwin AT delorie DOT com
DomainKey-Signature: a=rsa-sha1; c=nofws; d=sourceware.org; h=list-id
	:list-unsubscribe:list-subscribe:list-archive:list-post
	:list-help:sender:content-type:mime-version:subject:from
	:in-reply-to:date:content-transfer-encoding:message-id
	:references:to; q=dns; s=default; b=tpwIY0GAJO7iKQTxanOtSu782jEI
	iHhm1cMcw52+gP1XYmRzRc1iTXBYRQrySkJScE0OEBWcfkJTl0mcylLI0SiBP2Qg
	YsKTMaIq8hwW8NT4J5o4TsdfGZVkOkWMUZXQMGlLwPLlNFGiwnXW18d8tk2FCJqa
	oI6I5T0RS80zskM=
DKIM-Signature: v=1; a=rsa-sha1; c=relaxed; d=sourceware.org; h=list-id
	:list-unsubscribe:list-subscribe:list-archive:list-post
	:list-help:sender:content-type:mime-version:subject:from
	:in-reply-to:date:content-transfer-encoding:message-id
	:references:to; s=default; bh=n6P7BhsEaGV8bv0prXdjFbETnoA=; b=D0
	j+5J+EqiKnuXDooA7h8E++TY9T/VlpPFl1QsaAM0RkJRX8L/D+KRV63CA/hkXLLv
	fovpHz6qu3SK+Ri7aB+rr/JYr1RNQHUOXerGo056JzHRhL5yV6Vf542JvzrQa+7a
	vlsiDImNsp003LNghtKCKX1jQrxrlbAj7RVsBqAGM=
Mailing-List: contact cygwin-help AT cygwin DOT com; run by ezmlm
List-Id: <cygwin.cygwin.com>
List-Subscribe: <mailto:cygwin-subscribe AT cygwin DOT com>
List-Archive: <http://sourceware.org/ml/cygwin/>
List-Post: <mailto:cygwin AT cygwin DOT com>
List-Help: <mailto:cygwin-help AT cygwin DOT com>, <http://sourceware.org/ml/#faqs>
Sender: cygwin-owner AT cygwin DOT com
Mail-Followup-To: cygwin AT cygwin DOT com
Delivered-To: mailing list cygwin AT cygwin DOT com
Authentication-Results: sourceware.org; auth=none
X-Virus-Found: No
X-Spam-SWARE-Status: No, score=-1.7 required=5.0 tests=AWL,BAYES_00 autolearn=ham version=3.3.2
X-HELO: tangentsoft.com
Content-Type: text/plain; charset=windows-1252
Mime-Version: 1.0 (Mac OS X Mail 7.1 \(1827\))
Subject: Re: get rid of getpwent? (Was: cygwin-1.7.28 getpwent header declaration changes ?)
From: Warren Young <warren AT etr-usa DOT com>
In-Reply-To: <C1264DEE-1D5E-4F08-8DB5-D62A0EA4DCC0@etr-usa.com>
Date: Sat, 8 Feb 2014 08:39:23 -0700
Message-Id: <707CF923-5BCD-477F-A376-6E099E67697F@etr-usa.com>
References: <52F339CA DOT 5070305 AT gmail DOT com> <20140206090117 DOT GD2821 AT calimero DOT vinschen DOT de> <52F361C5 DOT 3000807 AT gmail DOT com> <20140206141321 DOT GI2821 AT calimero DOT vinschen DOT de> <52F40208 DOT 5030901 AT etr-usa DOT com> <20140207094917 DOT GN2821 AT calimero DOT vinschen DOT de> <52F53D7C DOT 5050201 AT etr-usa DOT com> <52F553AA DOT 9090500 AT cygwin DOT com> <52F561EE DOT 8090806 AT tiscali DOT co DOT uk> <52F56E92 DOT 3070309 AT cygwin DOT com> <675717060 DOT 20140208044040 AT mtu-net DOT ru> <C1264DEE-1D5E-4F08-8DB5-D62A0EA4DCC0 AT etr-usa DOT com>
To: cygwin AT cygwin DOT com
X-IsSubscribed: yes
Content-Transfer-Encoding: 8bit
X-MIME-Autoconverted: from quoted-printable to 8bit by delorie.com id s18Fdn13021009

On Feb 8, 2014, at 8:19 AM, Warren Young <warren AT etr-usa DOT com> wrote:

> On Feb 7, 2014, at 5:40 PM, Andrey Repin <anrdaemon AT yandex DOT ru> wrote:
> 
>> In either case, repeatedly requesting the same record in a short amount of
>> time will only test the system level cache.
> 
> If that were true, moving the requested record around in /etc/passwd wouldn’t cause a 6x spread in test results. That’s O(N) type behavior, whereas a cache approaches O(1).

A clarification:

I agree that /etc/passwd is being cached for the entire test.  My 12-line file is a bit over 1K, so it fits easily into a 4K RAM page.  Also, I repeated my tests several times, so even the initial disk read is cached.

The fact that we see a 6x speed difference depending on where in the file — or RAM page, if you prefer — the target record is tells us that lookups are dominated by parsing time.

Parsing overhead shouldn’t exist for SAM or AD. They’re “pre-parsed.”

The equivalent overhead in SAM/AD terms is tree and index traversal, which should happen a lot faster than O(N).
--
Problem reports:       http://cygwin.com/problems.html
FAQ:                   http://cygwin.com/faq/
Documentation:         http://cygwin.com/docs.html
Unsubscribe info:      http://cygwin.com/ml/#unsubscribe-simple