Messages in this thread |  | | Date | Mon, 16 Sep 1996 09:01:11 +0300 (EET DST) | From | Linus Torvalds <> | Subject | Re: Perl make depend made faster |
| |
On Sun, 15 Sep 1996, Luca Lizzeri wrote: > > I think I will just stare at mkdep.c for a couple of days and ponder on > the ways of the wizards, hoping that I will learn as much more of C as I > did of Perl while writing depend.pl.
Umm.. "mkdep.c" isn't exactly a thing of beauty. What it _is_ is my way of writing state machines, and an efficient one. I don't think you should actually show it to impressionable people, or people with heart disease.
I have fixed up "mkdep.c" to be more portable (it worked fine on Linux systems, but if you're cross-compiling from other systems you might have had problems with "mmap()" and "munmap()" wanting to always have a page-aligned argument to them).
I also made it do the memory accesses a "long" at a time, which helps a lot on architectures that don't have fast byte accesses. That should actually speed it up on x86 too, especially the newer ones (or the really old ones without any cache at all).
The new version is really sick, but I had fun writing it. You should compile it with "-S -O2 -fomit-frame-pointer" to see all the subtleties by looking at the generated assembly code.
Ok, now it's a competition: is anobody able to shave another second off this one? On my alpha it runs in eight seconds on the whole source tree once things are cached (22 secs on a P166).
Subtleties you should keep in mind when looking at it: (a) use "mmap()" to avoid a copy from kernel space (b) map in the whole file to avoid having to worry about boundary conditions (c) do ugly things when loading a "long" at a time, it doesn't work if the source file has NUL-characters in it (d) partition the functions so that gcc can allocate registers sanely (e) not so subtle: "goto" is your friend if you're doing state machines
Linus
----- #include <stdio.h> #include <stdlib.h>
#include <string.h> #include <sys/types.h> #include <sys/stat.h> #include <unistd.h> #include <sys/fcntl.h> #include <sys/mman.h>
char *filename, *command, __depname[256] = "\n\t@touch "; int needsconfig, hasconfig, hasdep;
#define depname (__depname+9)
struct path_struct { int len; char buffer[256-sizeof(int)]; } path_array[2] = { { 23, "/usr/src/linux/include/" }, { 0, "" } };
static void handle_include(int type, char *name, int len) { int plen; struct path_struct *path = path_array+type;
if (len == 14 && !memcmp(name, "linux/config.h", len)) hasconfig = 1;
plen = path->len; memcpy(path->buffer+plen, name, len); len += plen; path->buffer[len] = '\0'; if (access(path->buffer, F_OK)) return;
if (!hasdep) { hasdep = 1; printf("%s:", depname); } printf(" \\\n %s", path->buffer); }
static void handle_config(void) { hasconfig = 1; if (!hasdep) fprintf(stderr, "%s needs config but has not included config file\n", filename); }
#if defined(__alpha__) || defined(__i386__) #define LE_MACHINE #endif
#ifdef LE_MACHINE #define first_byte(x) current = (unsigned char) x; x >>= 8; #else #define first_byte(x) current = x >> 8*(sizeof(unsigned long)-1); x <<= 8; #endif
#define GETNEXT { \ if (!__buf) { \ __buf = *(unsigned long *) next; \ if (!__buf) \ break; \ } first_byte(__buf); next++; } #define CASE(c,label) if (current == c) goto label #define NOTCASE(c,label) if (current != c) goto label
static void state_machine(char *next) { for(;;) { unsigned long __buf = 0; unsigned char current;
normal: GETNEXT __normal: CASE('/',slash); CASE('"',string); CASE('\'',char_const); CASE('#',preproc); goto normal;
slash: GETNEXT CASE('*',comment); goto __normal;
string: GETNEXT CASE('"',normal); NOTCASE('\\',string); GETNEXT goto string;
char_const: GETNEXT CASE('\'',normal); NOTCASE('\\',char_const); GETNEXT goto char_const;
comment: GETNEXT __comment: NOTCASE('*',comment); GETNEXT CASE('/',normal); goto __comment;
preproc: GETNEXT CASE('\n',normal); CASE(' ',preproc); CASE('\t',preproc); CASE('i',i_preproc); GETNEXT
skippreproc: CASE('\n',normal); GETNEXT goto skippreproc;
i_preproc: GETNEXT CASE('f',if_line); NOTCASE('n',skippreproc); GETNEXT NOTCASE('c',skippreproc); GETNEXT NOTCASE('l',skippreproc); GETNEXT NOTCASE('u',skippreproc); GETNEXT NOTCASE('d',skippreproc); GETNEXT NOTCASE('e',skippreproc);
/* "# include" found */ include_line: GETNEXT CASE('\n',normal); CASE('<', std_include_file); NOTCASE('"', include_line);
/* "local" include file */ { char *incname = next; local_include_name: GETNEXT CASE('\n',normal); NOTCASE('"', local_include_name); handle_include(1, incname, next-incname-1); goto skippreproc; }
/* <std> include file */ std_include_file: { char *incname = next; std_include_name: GETNEXT CASE('\n',normal); NOTCASE('>', std_include_name); handle_include(0, incname, next-incname-1); goto skippreproc; }
if_line: if (hasconfig) goto skippreproc; if_start: if (!memcmp("CONFIG_", next, 7)) { handle_config(); goto skippreproc; } GETNEXT CASE('\n', normal); CASE('_', if_middle); if (current >= 'a' && current <= 'z') goto if_middle; if (current < 'A' || current > 'Z') goto if_start; if_middle: GETNEXT CASE('\n', normal); CASE('_', if_middle); if (current >= 'a' && current <= 'z') goto if_middle; if (current < 'A' || current > 'Z') goto if_start; goto if_middle; } }
static void do_depend(void) { char *map; int mapsize; int pagesizem1 = getpagesize()-1; int fd = open(filename, O_RDONLY); struct stat st;
if (fd < 0) return; fstat(fd, &st); mapsize = st.st_size + 2*sizeof(unsigned long); mapsize = (mapsize+pagesizem1) & ~pagesizem1; map = mmap(NULL, mapsize, PROT_READ, MAP_PRIVATE, fd, 0); if (-1 == (long)map) { close(fd); return; } state_machine(map); munmap(map, mapsize); if (hasdep) puts(command); }
int main(int argc, char **argv) { int len; char * hpath;
hpath = getenv("HPATH"); if (!hpath) hpath = "/usr/src/linux/include"; len = strlen(hpath); memcpy(path_array[0].buffer, hpath, len); if (len && hpath[len-1] != '/') { path_array[0].buffer[len] = '/'; len++; } path_array[0].buffer[len] = '\0'; path_array[0].len = len;
while (--argc > 0) { int len; char *name = *++argv;
filename = name; len = strlen(name); memcpy(depname, name, len+1); command = __depname; if (len > 2 && name[len-2] == '.') { switch (name[len-1]) { case 'c': case 'S': depname[len-1] = 'o'; command = ""; } } needsconfig = hasconfig = hasdep = 0; do_depend(); } return 0; }
|  |