From patchwork Tue Apr 19 18:19:40 2011 Content-Type: text/plain; charset="utf-8" MIME-Version: 1.0 Content-Transfer-Encoding: 7bit X-Patchwork-Submitter: Linus Torvalds X-Patchwork-Id: 718671 Received: from vger.kernel.org (vger.kernel.org [209.132.180.67]) by demeter1.kernel.org (8.14.4/8.14.3) with ESMTP id p3JIJlGN022700 for ; Tue, 19 Apr 2011 18:19:47 GMT Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1752907Ab1DSSTq (ORCPT ); Tue, 19 Apr 2011 14:19:46 -0400 Received: from mail-pz0-f46.google.com ([209.85.210.46]:59364 "EHLO mail-pz0-f46.google.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1752608Ab1DSSTq (ORCPT ); Tue, 19 Apr 2011 14:19:46 -0400 Received: by pzk9 with SMTP id 9so2773638pzk.19 for ; Tue, 19 Apr 2011 11:19:46 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=gamma; h=domainkey-signature:sender:date:from:x-x-sender:to:subject :in-reply-to:message-id:references:user-agent:mime-version :content-type; bh=fvgenpDKJoeZfWhurRbBOqU2RRoqIPCGmV46szBYbXU=; b=Eshsjs4a3RaY7jVrrGpSnm2eW3V8oTwiR/drunHVaozyInK2sU+84ts6SEhzcPhWdg BSebMIOb1APgHrD7QwDLDtw6f/VWZKUcNYkl0dGDb8bNWMkIoh6gc98d7lsUZ+vyFS7S ZvRtNlW1HsmqmQoJJxz0k9TrKlVk3RaQdFXrU= DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma; h=sender:date:from:x-x-sender:to:subject:in-reply-to:message-id :references:user-agent:mime-version:content-type; b=SRnh7u6+FqLdVqJGkrw8qgd9ip52JGv98Vnba9JPBpf6bbekPZlT35q0EYTjPsBLYR SqoevwHWg/dSG6wJ3uq1xHINkyJpYklob1EoamBgUVCKjxWrHgODY/sY+0VIiCwahzWl +gzJjHv0OkCEVmnoEKtY5ortpbioRGGDuYTl0= Received: by 10.68.10.103 with SMTP id h7mr9229083pbb.203.1303237186031; Tue, 19 Apr 2011 11:19:46 -0700 (PDT) Received: from [192.168.1.87] (c-24-22-0-219.hsd1.or.comcast.net [24.22.0.219]) by mx.google.com with ESMTPS id k1sm88487pbh.34.2011.04.19.11.19.44 (version=TLSv1/SSLv3 cipher=OTHER); Tue, 19 Apr 2011 11:19:45 -0700 (PDT) Date: Tue, 19 Apr 2011 11:19:40 -0700 (PDT) From: Linus Torvalds X-X-Sender: torvalds@i5.linux-foundation.org To: Christopher Li , linux-sparse@vger.kernel.org Subject: PATCH 2/2] Teach 'already_tokenized()' to use the stream name hash table In-Reply-To: Message-ID: References: User-Agent: Alpine 2.02 (LFD 1266 2009-07-14) MIME-Version: 1.0 Sender: linux-sparse-owner@vger.kernel.org Precedence: bulk List-ID: X-Mailing-List: linux-sparse@vger.kernel.org X-Greylist: IP, sender and recipient auto-whitelisted, not delayed by milter-greylist-4.2.6 (demeter1.kernel.org [140.211.167.41]); Tue, 19 Apr 2011 18:19:47 +0000 (UTC) This replaces the "loop over all streams" with a simple hash lookup. It makes the cost of checking for already tokenized streams basically go away (it could be up to 5% of CPU time, almost entirely due to the "strcmp()" of the name). Signed-off-by: Linus Torvalds --- That "up to 5%" is probably debatable, and will depend on just how many includes you have etc etc. And on the CPU and library issues. But 3-4% is definitely the case for my kernel C=2 build on my current machine. So it's real, and worth it. pre-process.c | 8 +++++--- 1 files changed, 5 insertions(+), 3 deletions(-) diff --git a/pre-process.c b/pre-process.c index 603cc00c999f..6d12f173146d 100644 --- a/pre-process.c +++ b/pre-process.c @@ -655,10 +655,12 @@ static const char *token_name_sequence(struct token *token, int endop, struct to static int already_tokenized(const char *path) { - int i; - struct stream *s = input_streams; + int stream, next; + + for (stream = *hash_stream(path); stream >= 0 ; stream = next) { + struct stream *s = input_streams + stream; - for (i = input_stream_nr; --i >= 0; s++) { + next = s->next_stream; if (s->constant != CONSTANT_FILE_YES) continue; if (strcmp(path, s->name))