From owner-cvs-all  Wed Jun 28 21:48:40 2000
Delivered-To: cvs-all@freebsd.org
Received: from freefall.freebsd.org (freefall.FreeBSD.ORG [204.216.27.21])
	by hub.freebsd.org (Postfix) with ESMTP
	id C28F337C39C; Wed, 28 Jun 2000 21:48:34 -0700 (PDT)
	(envelope-from dcs@FreeBSD.org)
Received: (from dcs@localhost)
	by freefall.freebsd.org (8.9.3/8.9.2) id VAA72899;
	Wed, 28 Jun 2000 21:48:34 -0700 (PDT)
	(envelope-from dcs@FreeBSD.org)
Message-Id: <200006290448.VAA72899@freefall.freebsd.org>
From: "Daniel C. Sobral" <dcs@FreeBSD.org>
Date: Wed, 28 Jun 2000 21:48:34 -0700 (PDT)
To: cvs-committers@FreeBSD.org, cvs-all@FreeBSD.org
Subject: cvs commit: src/lib/libc/regex engine.c regcomp.c regex2.h
X-FreeBSD-CVS-Branch: HEAD
Sender: owner-cvs-all@FreeBSD.ORG
Precedence: bulk
X-Loop: FreeBSD.ORG

dcs         2000/06/28 21:48:34 PDT

  Modified files:
    lib/libc/regex       engine.c regcomp.c regex2.h 
  Log:
  Add Boyler-Moore algorithm to pre-matching test.
  
  The BM algorithm works by scanning the pattern from right to left,
  and jumping as many characters as viable based on the text's mismatched
  character and the pattern's already matched suffix.
  
  This typically enable us to test only a fraction of the text's characters,
  but has a worse performance than the straight-forward method for small
  patterns. Because of this, the BM algorithm will only be used if the
  pattern size is at least 4 characters.
  
  Notice that this pre-matching is done on the largest substring of the
  regular expression that _must_ be present on the text for a succesful
  match to be possible at all.
  
  For instance, "(xyzzy|grues)" will yield a null "must" substring, and,
  therefore, not benefit from the BM algorithm at all. Because of the
  lack of intelligence of the algorithm that finds the "must" string,
  things like "charjump|matchjump" will also yield a null string. To
  optimize that, "(char|match)jump" should be used.
  
  The setup time (at regcomp()) for the BM algorithm will most likely
  outweight any benefits for one-time matches. Given the slow regex(3)
  we have, this is unlikely to be even perceptible, though.
  
  The size of a regex_t structure is increased by 2*sizeof(char*) +
  256*sizeof(int) + strlen(must)*sizeof(int). This is all inside the
  regex_t's "guts", which is allocated dynamically by regcomp(). If
  allocation of either of the two tables fail, the other one is freed.
  In this case, the straight-forward algorithm is used for pre-matching.
  
  Tests exercising the code path affected have shown a speed increase of
  50% for "must" strings of length four or five.
  
  API and ABI remain unchanged by this commit.
  
  The patch submitted on the PR was not used, as it was non-functional.
  
  PR: 14342
  
  Revision  Changes    Path
  1.6       +54 -6     src/lib/libc/regex/engine.c
  1.14      +144 -0    src/lib/libc/regex/regcomp.c
  1.4       +4 -0      src/lib/libc/regex/regex2.h



To Unsubscribe: send mail to majordomo@FreeBSD.org
with "unsubscribe cvs-all" in the body of the message