patchmake - Patches: patch #2903, great speed up for...

 
 

You are not allowed to post comments on this tracker with your current authentication level.

patch #2903: great speed up for "substitution references"

Submitter:  None
Submitted:  Mon 05 Apr 2004 03:33:08 PM UTC
   
 
Category:  None Priority:  5 - Normal
Status:  Invalid Privacy:  Public
Assigned to:  None Originator Email:  -email is unavailable-
Open/Closed:  Closed Fixed Release:  None

Jump to the original submission

Tue 21 Sep 2004 06:03:43 AM UTC, comment #8: 

I reworked the code to use strstr() everywhere that sindex() was used before, and removed the sindex() function completely.  This patch is thus obsolete.

Paul D. Smith <psmith>
Group administrator
Thu 29 Apr 2004 09:00:10 AM UTC, comment #7: 

Sorry, so what about this patch below?..
It seems to be exactly the same from side of semantics, but it works with the test Makefile (see original post) more then 100 times quicker!

Valery (khamenya@mail.ru)

Anonymous
Wed 14 Apr 2004 04:21:54 PM UTC, comment #6: 

Hm, all indents are removed, but it is OK for emacs users :)

BTW, instead of:


 If blen (or slen) is 0 then the whole string BIG (SMALL is considered)


i wanted to type:


 If blen (or slen) is 0 then the whole string BIG (or SMALL) is considered */

so now we have typo score 1:1
:)

Anonymous
Wed 14 Apr 2004 04:18:03 PM UTC, comment #5: 

below goes the version of sindex that seems to correspond to original version of sindex, but with much better speed. I've updated the comment as well, because it was not reflecting the case of null values for blen and slen.

here we go:

/* Search string BIG (length BLEN) for an occurrence of
   string SMALL (length SLEN).  Return a pointer to the
   beginning of the first occurrence, or return nil if none found. 
   If blen (or slen) is 0 then the whole string BIG (SMALL is considered) */

char *
sindex (big, blen, small, slen)
     const char *big;
     unsigned int blen;
     const char *small;
     unsigned int slen;
{
  char* saved_big = 0;
  char* saved_small = 0;
  const char* haystack;
  const char* needle;

  if(blen) {
    saved_big = savestring (big, blen);
    haystack = saved_big;
  }
  else
    haystack = big;

  if(slen) {
    saved_small = savestring (small, slen);
    needle = saved_small;
  }
  else
    needle = small;

  char* pos = strstr(haystack, needle);
 
  if( saved_small )
    free(saved_small);

  if( saved_big )
     free(saved_big);

  if(pos==NULL)
    return NULL;

  int   offset = pos - haystack;
 
  return (char*)(big+offset); /* casting because "big" had a const qualifier */
}

Anonymous
Mon 12 Apr 2004 04:50:17 PM UTC, comment #4: 

Right, sorry, I meant strstr().  Regardless of this typo, my point stands: you cannot replace sindex() with strstr() because they are not functionally equivalent.  sindex() gives a maximum length of the string to be checked, while strstr() does not (it always matches against the entire string).  This means you will get incorrect results in some situations.

There's no question that sindex() uses an extremely simple-minded algorithm, probably because 95% of the time the strings to be replaced are modestly sized (<1K, often <256 bytes).  It would probably be a good idea to use something more intelligent (any algorithms book will give some good methods).  But, we cannot just switch sindex() for strstr(): that is introducing bugs into the program.

Paul D. Smith <psmith>
Group administrator
Mon 05 Apr 2004 06:55:48 PM UTC, comment #3: 

there are not that much occurances of sindex:
---------------------
commands.c:339:          if (sindex (p, len, "$(MAKE)", 7) != 0
commands.c:340:              || sindex (p, len, "${MAKE}", 7) != 0)
function.c:110:   p = sindex (t, 0, subst, slen);
function.c:834:  if (sindex (argv[1], 0, argv[0], i) != 0)
make.h:421:extern char sindex PARAMS ((const char , unsigned int, \
misc.c:432:sindex (big, blen, small, slen)
---------------------


Anonymous
Mon 05 Apr 2004 06:35:41 PM UTC, comment #2: 

not strchr, but strstr...

Anonymous
Mon 05 Apr 2004 04:53:56 PM UTC, comment #1: 

It is not correct to replace sindex() with strchr().  The sindex() function works on substrings as well as full strings, and this capability is used extensively in GNU make.

Paul D. Smith <psmith>
Group administrator
Mon 05 Apr 2004 03:33:08 PM UTC, original submission:  

This short test shows inadequate slow performance of string replacement:
------------------ END BEGIN
FOO:=$(shell echo creating the set of strings... >/dev/stderr)
NAMES:=$(shell for((i=0;i<30000;i++)); do \
echo alaskjdfkljasldfja      askdljfaksljdflaskdjf qqqqqqqqqqqqqqqqqqqqqqqqqqq aaaaaaaaaaaaaaaaa .bbbbbbb; done)
FOO:=$(shell echo set is created, now replacing... >/dev/stderr)
REP:=$(NAMES:.bbbbbbb=.ccc)
FOO:=$(shell echo done>/dev/stderr)
all:
------------------ TEST END

Profiling shows that "sindex" function is responsible for that. Indeed, this function is quite straight-forward and "strstr" works much quicker.

So, the patch is attached.

Prehistory: I have checked the reply to the issue I have sent:
http://savannah.gnu.org/patch/index.php?func=detailitem&item_id=2777

I was surprized. Indeed, the patch is really applied to last versions of make, but my Makefile is hanging about 3 minutes in filename replacement! Then I have debugged `make' myself ;)

Perhaps there is no misunderstanding now.

Anonymous

 

(Note: upload size limit is set to 16384 kB, after insertion of the required escape characters.)

Attached Files
file #7236:  patch.txt added by None (672B - text/plain)

 

Depends on the following items: None found

Items that depend on this one: None found

 

CC list is empty

 

There are 0 votes so far. Votes easily highlight which items people would like to see resolved in priority, independently of the priority of the item set by tracker managers.

 

Follow 3 latest changes.

Date Changed by Updated Field Previous Value => Replaced by
2004-09-21 psmith StatusNone Invalid
    Open/ClosedOpen Closed
2004-04-05 None Attached File- Added patch.txt, #3058

Back to the top

Powered by Savane 3.13-02a9.
Corresponding source code