On Wednesday, August 24, 2022 at 8:43:35 PM UTC-3, Thiago Adams wrote:
> On Wednesday, August 24, 2022 at 7:04:36 PM UTC-3, Anton Shepelev wrote:

> This generator outputs the code
>
output is:

This code looks a bad linear search..but -o2 gcc transform this
in a jump give the initial letter. The same code can be written using switch..

int is_keyword(const char* s)
{ if(*s == 'N') {
s++;
/*NULL*/
if( *s++ == 'U' && *s++ == 'L' && *s++ == 'L' && *s =='\0') return 0; else return -1;;
}
if(*s == '_') {
s++;
if(*s == 'A') {
s++;
if(*s == 'l') {
s++;
if(*s == 'i') {
s++;
if(*s == 'g') {
s++;
if(*s == 'n') {
s++;
if(*s == 'a') {
s++;
/*_Alignas*/
if( *s++ == 's' && *s =='\0') return 1; else return -1;;
}
if(*s == 'o') {
s++;
/*_Alignof*/
if( *s++ == 'f' && *s =='\0') return 2; else return -1;;
}
return -1;
};
return -1;
};
return -1;
};
return -1;
};
if(*s == 't') {
s++;
/*_Atomic*/
if( *s++ == 'o' && *s++ == 'm' && *s++ == 'i' && *s++ == 'c' && *s =='\0') return 3; else return -1;;
}
return -1;
};
if(*s == 'B') {
s++;
if(*s == 'i') {
s++;
/*_BitInt*/
if( *s++ == 't' && *s++ == 'I' && *s++ == 'n' && *s++ == 't' && *s =='\0') return 4; else return -1;;
}
if(*s == 'o') {
s++;
/*_Bool*/
if( *s++ == 'o' && *s++ == 'l' && *s =='\0') return 5; else return -1;;
}
return -1;
};
if(*s == 'C') {
s++;
/*_Complex*/
if( *s++ == 'o' && *s++ == 'm' && *s++ == 'p' && *s++ == 'l' && *s++ == 'e' && *s++ == 'x' && *s =='\0') return 6; else return -1;;
}
if(*s == 'D') {
s++;
if(*s == 'e') {
s++;
if(*s == 'c') {
s++;
if(*s == 'i') {
s++;
if(*s == 'm') {
s++;
if(*s == 'a') {
s++;
if(*s == 'l') {
s++;
if(*s == '1') {
s++;
/*_Decimal128*/
if( *s++ == '2' && *s++ == '8' && *s =='\0') return 7; else return -1;;
}
if(*s == '3') {
s++;
/*_Decimal32*/
if( *s++ == '2' && *s =='\0') return 8; else return -1;;
}
if(*s == '6') {
s++;
/*_Decimal64*/
if( *s++ == '4' && *s =='\0') return 9; else return -1;;
}
return -1;
};
return -1;
};
return -1;
};
return -1;
};
return -1;
};
return -1;
};
return -1;
};
if(*s == 'G') {
s++;
/*_Generic*/
if( *s++ == 'e' && *s++ == 'n' && *s++ == 'e' && *s++ == 'r' && *s++ == 'i' && *s++ == 'c' && *s =='\0') return 10; else return -1;;
}
if(*s == 'H') {
s++;
/*_Hashof*/
if( *s++ == 'a' && *s++ == 's' && *s++ == 'h' && *s++ == 'o' && *s++ == 'f' && *s =='\0') return 11; else return -1;;
}
if(*s == 'I') {
s++;
/*_Imaginary*/
if( *s++ == 'm' && *s++ == 'a' && *s++ == 'g' && *s++ == 'i' && *s++ == 'n' && *s++ == 'a' && *s++ == 'r' && *s++ == 'y' && *s =='\0') return 12; else return -1;;
}
if(*s == 'N') {
s++;
/*_Noreturn*/
if( *s++ == 'o' && *s++ == 'r' && *s++ == 'e' && *s++ == 't' && *s++ == 'u' && *s++ == 'r' && *s++ == 'n' && *s =='\0') return 13; else return -1;;
}
if(*s == 'S') {
s++;
/*_Static_assert*/
if( *s++ == 't' && *s++ == 'a' && *s++ == 't' && *s++ == 'i' && *s++ == 'c' && *s++ == '_' && *s++ == 'a' && *s++ == 's' && *s++ == 's' && *s++ == 'e' && *s++ == 'r' && *s++ == 't' && *s =='\0') return 14; else return -1;;
}
if(*s == 'T') {
s++;
/*_Thread_local*/
if( *s++ == 'h' && *s++ == 'r' && *s++ == 'e' && *s++ == 'a' && *s++ == 'd' && *s++ == '_' && *s++ == 'l' && *s++ == 'o' && *s++ == 'c' && *s++ == 'a' && *s++ == 'l' && *s =='\0') return 15; else return -1;;
}
if(*s == '_') {
s++;
if(*s == 'a') {
s++;
if(*s == 'l') {
s++;
/*__alignof*/
if( *s++ == 'i' && *s++ == 'g' && *s++ == 'n' && *s++ == 'o' && *s++ == 'f' && *s =='\0') return 16; else return -1;;
}
if(*s == 's') {
s++;
/*__asm*/
if( *s++ == 'm' && *s =='\0') return 17; else return -1;;
}
return -1;
};
if(*s == 'f') {
s++;
/*__forceinline*/
if( *s++ == 'o' && *s++ == 'r' && *s++ == 'c' && *s++ == 'e' && *s++ == 'i' && *s++ == 'n' && *s++ == 'l' && *s++ == 'i' && *s++ == 'n' && *s++ == 'e' && *s =='\0') return 18; else return -1;;
}
if(*s == 'i') {
s++;
if(*s == 'n') {
s++;
if(*s == 'l') {
s++;
/*__inline*/
if( *s++ == 'i' && *s++ == 'n' && *s++ == 'e' && *s =='\0') return 19; else return -1;;
}
if(*s == 't') {
s++;
if(*s == '1') {
s++;
/*__int16*/
if( *s++ == '6' && *s =='\0') return 20; else return -1;;
}
if(*s == '3') {
s++;
/*__int32*/
if( *s++ == '2' && *s =='\0') return 21; else return -1;;
}
if(*s == '6') {
s++;
/*__int64*/
if( *s++ == '4' && *s =='\0') return 22; else return -1;;
}
if(*s == '8') {
s++;
/*__int8*/
if( *s =='\0') return 23; else return -1;;
}
return -1;
};
return -1;
};
return -1;
};
return -1;
};
if(*s == 'a') {
s++;
/*_asm*/
if( *s++ == 's' && *s++ == 'm' && *s =='\0') return 24; else return -1;;
}
return -1;
};
if(*s == 'a') {
s++;
if(*s == 'l') {
s++;
if(*s == 'i') {
s++;
if(*s == 'g') {
s++;
if(*s == 'n') {
s++;
if(*s == 'a') {
s++;
/*alignas*/
if( *s++ == 's' && *s =='\0') return 25; else return -1;;
}
if(*s == 'o') {
s++;
/*alignof*/
if( *s++ == 'f' && *s =='\0') return 26; else return -1;;
}
return -1;
};
return -1;
};
return -1;
};
return -1;
};
if(*s == 'u') {
s++;
/*auto*/
if( *s++ == 't' && *s++ == 'o' && *s =='\0') return 27; else return -1;;
}
return -1;
};
if(*s == 'b') {
s++;
if(*s == 'o') {
s++;
/*bool*/
if( *s++ == 'o' && *s++ == 'l' && *s =='\0') return 28; else return -1;;
}
if(*s == 'r') {
s++;
/*break*/
if( *s++ == 'e' && *s++ == 'a' && *s++ == 'k' && *s =='\0') return 29; else return -1;;
}
return -1;
};
if(*s == 'c') {
s++;
if(*s == 'a') {
s++;
if(*s == 's') {
s++;
/*case*/
if( *s++ == 'e' && *s =='\0') return 30; else return -1;;
}
if(*s == 't') {
s++;
/*catch*/
if( *s++ == 'c' && *s++ == 'h' && *s =='\0') return 31; else return -1;;
}
return -1;
};
if(*s == 'h') {
s++;
/*char*/
if( *s++ == 'a' && *s++ == 'r' && *s =='\0') return 32; else return -1;;
}
if(*s == 'o') {
s++;
if(*s == 'n') {
s++;
if(*s == 's') {
s++;
if(*s == 't') {
s++;
if(*s == '\0') {
s++;
/*const*/
return 33;
};
if(*s == 'e') {
s++;
/*constexpr*/
if( *s++ == 'x' && *s++ == 'p' && *s++ == 'r' && *s =='\0') return 34; else return -1;;
}
return -1;
};
return -1;
};
if(*s == 't') {
s++;
/*continue*/
if( *s++ == 'i' && *s++ == 'n' && *s++ == 'u' && *s++ == 'e' && *s =='\0') return 35; else return -1;;
}
return -1;
};
return -1;
};
return -1;
};
if(*s == 'd') {
s++;
if(*s == 'e') {
s++;
if(*s == 'f') {
s++;
if(*s == 'a') {
s++;
/*default*/
if( *s++ == 'u' && *s++ == 'l' && *s++ == 't' && *s =='\0') return 36; else return -1;;
}
if(*s == 'e') {
s++;
/*defer*/
if( *s++ == 'r' && *s =='\0') return 37; else return -1;;
}
return -1;
};
return -1;
};
if(*s == 'o') {
s++;
if(*s == '\0') {
s++;
/*do*/
return 38;
};
if(*s == 'u') {
s++;
/*double*/
if( *s++ == 'b' && *s++ == 'l' && *s++ == 'e' && *s =='\0') return 39; else return -1;;
}
return -1;
};
return -1;
};
if(*s == 'e') {
s++;
if(*s == 'l') {
s++;
/*else*/
if( *s++ == 's' && *s++ == 'e' && *s =='\0') return 40; else return -1;;
}
if(*s == 'n') {
s++;
/*enum*/
if( *s++ == 'u' && *s++ == 'm' && *s =='\0') return 41; else return -1;;
}
if(*s == 'x') {
s++;
/*extern*/
if( *s++ == 't' && *s++ == 'e' && *s++ == 'r' && *s++ == 'n' && *s =='\0') return 42; else return -1;;
}
return -1;
};
if(*s == 'f') {
s++;
if(*s == 'a') {
s++;
/*false*/
if( *s++ == 'l' && *s++ == 's' && *s++ == 'e' && *s =='\0') return 43; else return -1;;
}
if(*s == 'l') {
s++;
/*float*/
if( *s++ == 'o' && *s++ == 'a' && *s++ == 't' && *s =='\0') return 44; else return -1;;
}
if(*s == 'o') {
s++;
/*for*/
if( *s++ == 'r' && *s =='\0') return 45; else return -1;;
}
return -1;
};
if(*s == 'g') {
s++;
/*goto*/
if( *s++ == 'o' && *s++ == 't' && *s++ == 'o' && *s =='\0') return 46; else return -1;;
}
if(*s == 'i') {
s++;
if(*s == 'f') {
s++;
/*if*/
if( *s =='\0') return 47; else return -1;;
}
if(*s == 'n') {
s++;
if(*s == 'l') {
s++;
/*inline*/
if( *s++ == 'i' && *s++ == 'n' && *s++ == 'e' && *s =='\0') return 48; else return -1;;
}
if(*s == 't') {
s++;
/*int*/
if( *s =='\0') return 49; else return -1;;
}
return -1;
};
return -1;
};
if(*s == 'l') {
s++;
/*long*/
if( *s++ == 'o' && *s++ == 'n' && *s++ == 'g' && *s =='\0') return 50; else return -1;;
}
if(*s == 'n') {
s++;
/*nullptr*/
if( *s++ == 'u' && *s++ == 'l' && *s++ == 'l' && *s++ == 'p' && *s++ == 't' && *s++ == 'r' && *s =='\0') return 51; else return -1;;
}
if(*s == 'r') {
s++;
if(*s == 'e') {
s++;
if(*s == 'g') {
s++;
/*register*/
if( *s++ == 'i' && *s++ == 's' && *s++ == 't' && *s++ == 'e' && *s++ == 'r' && *s =='\0') return 52; else return -1;;
}
if(*s == 'p') {
s++;
/*repeat*/
if( *s++ == 'e' && *s++ == 'a' && *s++ == 't' && *s =='\0') return 53; else return -1;;
}
if(*s == 's') {
s++;
/*restrict*/
if( *s++ == 't' && *s++ == 'r' && *s++ == 'i' && *s++ == 'c' && *s++ == 't' && *s =='\0') return 54; else return -1;;
}
if(*s == 't') {
s++;
/*return*/
if( *s++ == 'u' && *s++ == 'r' && *s++ == 'n' && *s =='\0') return 55; else return -1;;
}
return -1;
};
return -1;
};
if(*s == 's') {
s++;
if(*s == 'h') {
s++;
/*short*/
if( *s++ == 'o' && *s++ == 'r' && *s++ == 't' && *s =='\0') return 56; else return -1;;
}
if(*s == 'i') {
s++;
if(*s == 'g') {
s++;
/*signed*/
if( *s++ == 'n' && *s++ == 'e' && *s++ == 'd' && *s =='\0') return 57; else return -1;;
}
if(*s == 'z') {
s++;
/*sizeof*/
if( *s++ == 'e' && *s++ == 'o' && *s++ == 'f' && *s =='\0') return 58; else return -1;;
}
return -1;
};
if(*s == 't') {
s++;
if(*s == 'a') {
s++;
if(*s == 't') {
s++;
if(*s == 'i') {
s++;
if(*s == 'c') {
s++;
if(*s == '\0') {
s++;
/*static*/
return 59;
};
if(*s == '_') {
s++;
/*static_assert*/
if( *s++ == 'a' && *s++ == 's' && *s++ == 's' && *s++ == 'e' && *s++ == 'r' && *s++ == 't' && *s =='\0') return 60; else return -1;;
}
return -1;
};
return -1;
};
return -1;
};
return -1;
};
if(*s == 'r') {
s++;
/*struct*/
if( *s++ == 'u' && *s++ == 'c' && *s++ == 't' && *s =='\0') return 61; else return -1;;
}
return -1;
};
if(*s == 'w') {
s++;
/*switch*/
if( *s++ == 'i' && *s++ == 't' && *s++ == 'c' && *s++ == 'h' && *s =='\0') return 62; else return -1;;
}
return -1;
};
if(*s == 't') {
s++;
if(*s == 'h') {
s++;
if(*s == 'r') {
s++;
if(*s == 'e') {
s++;
/*thread_local*/
if( *s++ == 'a' && *s++ == 'd' && *s++ == '_' && *s++ == 'l' && *s++ == 'o' && *s++ == 'c' && *s++ == 'a' && *s++ == 'l' && *s =='\0') return 63; else return -1;;
}
if(*s == 'o') {
s++;
/*throw*/
if( *s++ == 'w' && *s =='\0') return 64; else return -1;;
}
return -1;
};
return -1;
};
if(*s == 'r') {
s++;
if(*s == 'u') {
s++;
/*true*/
if( *s++ == 'e' && *s =='\0') return 65; else return -1;;
}
if(*s == 'y') {
s++;
/*try*/
if( *s =='\0') return 66; else return -1;;
}
return -1;
};
if(*s == 'y') {
s++;
if(*s == 'p') {
s++;
if(*s == 'e') {
s++;
if(*s == 'd') {
s++;
/*typedef*/
if( *s++ == 'e' && *s++ == 'f' && *s =='\0') return 67; else return -1;;
}
if(*s == 'i') {
s++;
/*typeid*/
if( *s++ == 'd' && *s =='\0') return 68; else return -1;;
}
if(*s == 'o') {
s++;
if(*s == 'f') {
s++;
if(*s == '\0') {
s++;
/*typeof*/
return 69;
};
if(*s == '_') {
s++;
/*typeof_unqual*/
if( *s++ == 'u' && *s++ == 'n' && *s++ == 'q' && *s++ == 'u' && *s++ == 'a' && *s++ == 'l' && *s =='\0') return 70; else return -1;;
}
return -1;
};
return -1;
};
return -1;
};
return -1;
};
return -1;
};
return -1;
};
if(*s == 'u') {
s++;
if(*s == 'n') {
s++;
if(*s == 'i') {
s++;
/*union*/
if( *s++ == 'o' && *s++ == 'n' && *s =='\0') return 71; else return -1;;
}
if(*s == 's') {
s++;
/*unsigned*/
if( *s++ == 'i' && *s++ == 'g' && *s++ == 'n' && *s++ == 'e' && *s++ == 'd' && *s =='\0') return 72; else return -1;;
}
return -1;
};
return -1;
};
if(*s == 'v') {
s++;
if(*s == 'o') {
s++;
if(*s == 'i') {
s++;
/*void*/
if( *s++ == 'd' && *s =='\0') return 73; else return -1;;
}
if(*s == 'l') {
s++;
/*volatile*/
if( *s++ == 'a' && *s++ == 't' && *s++ == 'i' && *s++ == 'l' && *s++ == 'e' && *s =='\0') return 74; else return -1;;
}
return -1;
};
return -1;
};
if(*s == 'w') {
s++;
/*while*/
if( *s++ == 'h' && *s++ == 'i' && *s++ == 'l' && *s++ == 'e' && *s =='\0') return 75; else return -1;;
}
return -1;
}

On Wednesday, August 24, 2022 at 8:54:56 PM UTC-3, Thiago Adams wrote:
> On Wednesday, August 24, 2022 at 8:43:35 PM UTC-3, Thiago Adams wrote:
> > On Wednesday, August 24, 2022 at 7:04:36 PM UTC-3, Anton Shepelev wrote:
>
> > This generator outputs the code
> >
> output is:
>
> This code looks a bad linear search..but -o2 gcc transform this
> in a jump give the initial letter. The same code can be written using switch..

The bad news it that without a "label pointer" we cannot write similar code by hand.
We need a table jump.
We have function pointers but I thing it will pay the price of function call.(haven't checked)

Ben Bacarisse to Anton Shepelev:

> > My program for performance testing accepts a set of
> > measured implementations, including a reference null
> > implementaion, as function pointers, runs them
> > repeatedly with each dataset until total running time
> > exceeds a certain limit (e.g. 10 seconds), divides the
> > result by the number of iterations, and subracts the
> > null time. It has the advantage of testing all the
> > algorithms against all the datasets in a single run and
> > of outputting their performace in a table. It uses
> > standard C fucntions to measure time. How do you measure
> > time?
>
> For the numbers I posted, the time built-in bash command.
> You code looks fast, but it seems to have a bug.

Probably due to the confusion between ' ' as string
terminator and zero the empty value. I hoped I could get
away with it by way of a hack but failed. I was in a hurry,
will fix it.

> What times do you get for the other search strategies?

That is the program I used for testing sort and hash
algorithms but I did not apply it to the task at hand.
Thanks for poining out the bug and corresponding input in
the other post.

--
() ascii ribbon campaign - against html e-mail
/\ http://preview.tinyurl.com/qcy6mjc [archived]

I wrote to

> > You code looks fast, but it seems to have a bug.
>
> Probably due to the confusion between ' ' as string
> terminator and zero the empty value.

I meant `\0`. Which will make more sense for this
conversation: to fix the bug or to rewrite the function so
that it accepts a raw non-terminated string and a
length -- an interface better suitable for a tokeniser?

--
() ascii ribbon campaign - against html e-mail
/\ http://preview.tinyurl.com/qcy6mjc [archived]

Ben Bacarisse:

> This program reports zero (the token value assigned to
> NULL) for a number of strings that are not keywords.

Yes, it misfires for any words that is a prefix of a
keyword. Below is a fixed version:

#include <stdio.h>
#include <stdlib.h>

/* TODO: allocate tree[] elements from kw_reg() as needed */
#define MAX_RECS 4096
#define EMPTY -1
int tree[MAX_RECS][256]; /* tree of character-tables for NFA-like recognition */
int tree_h; /* index of highest used element in tree[] */

/* register a keyword: */
static void kw_reg( char* word, int id )
{ int* ctab;
int next;
char c;

ctab = tree[0];

while( 1 )
{ c = *word;
/* token scanned => store its id and exit: */
if( c == '\0' )
{ ctab[c] = id; break; }
next = ctab[c];
/* known prefix passed => store current character: */
if( next == EMPTY )
{ ctab[c] = ++tree_h;
ctab = tree[tree_h];
}
/* still within known prefix => continue to next level: */
else
{ ctab = tree[next]; }
word += 1;
}
}

static int kw_check( char* word )
{ char c;
int* ctab;
int next;
int res;

res = -1;
ctab = tree[0];
while( 1 )
{ c = *word;
next = ctab[c];
/* end of token => recognised a keyword: */
if( c == '\0' )
{ res = next; break; }
if( next == EMPTY ) break; /* unknown prefix => not a keyword */
ctab = tree[next]; /* continue to next level */
word += 1;
}
return res;
}

static void kw_init()
{ int r, c;
tree_h = 0;
for( r = 0; r < MAX_RECS; r += 1 )
for( c = 0; c < 256 ; c += 1 )
tree[r][c] = EMPTY;

kw_reg("NULL" , 0);
kw_reg("_Alignas" , 1);
kw_reg("_Atomic" , 2);
kw_reg("_BitInt" , 3);
kw_reg("_Bool" , 4);
kw_reg("_Complex" , 5);
kw_reg("_Decimal128" , 6);
kw_reg("_Decimal32" , 7);
kw_reg("_Decimal64" , 8);
kw_reg("_Generic" , 9);
kw_reg("_Hashof" , 10);
kw_reg("_Imaginary" , 11);
kw_reg("_Noreturn" , 12);
kw_reg("_Static_assert", 13);
kw_reg("_Thread_local" , 14);
kw_reg("__alignof" , 15);
kw_reg("__asm" , 16);
kw_reg("__forceinline" , 17);
kw_reg("__inline" , 18);
kw_reg("__int16" , 19);
kw_reg("__int32" , 20);
kw_reg("__int64" , 21);
kw_reg("__int8" , 22);
kw_reg("_asm" , 23);
kw_reg("alignas" , 24);
kw_reg("alignof" , 25);
kw_reg("auto" , 26);
kw_reg("bool" , 27);
kw_reg("break" , 28);
kw_reg("case" , 29);
kw_reg("catch" , 30);
kw_reg("char" , 31);
kw_reg("const" , 32);
kw_reg("constexpr" , 33);
kw_reg("continue" , 34);
kw_reg("default" , 35);
kw_reg("defer" , 36);
kw_reg("do" , 37);
kw_reg("double" , 38);
kw_reg("else" , 39);
kw_reg("enum" , 40);
kw_reg("extern" , 41);
kw_reg("false" , 42);
kw_reg("float" , 43);
kw_reg("for" , 44);
kw_reg("goto" , 45);
kw_reg("if" , 46);
kw_reg("inline" , 47);
kw_reg("int" , 48);
kw_reg("long" , 49);
kw_reg("nullptr" , 50);
kw_reg("register" , 51);
kw_reg("repeat" , 52);
kw_reg("restrict" , 53);
kw_reg("return" , 54);
kw_reg("short" , 55);
kw_reg("signed" , 56);
kw_reg("sizeof" , 57);
kw_reg("static" , 58);
kw_reg("static_assert" , 59);
kw_reg("struct" , 60);
kw_reg("switch" , 61);
kw_reg("thread_local" , 62);
kw_reg("throw" , 63);
kw_reg("true" , 64);
kw_reg("try" , 65);
kw_reg("typedef" , 66);
kw_reg("typeid" , 67);
kw_reg("typeof" , 68);
kw_reg("typeof_unqual" , 69);
kw_reg("union" , 70);
kw_reg("unsigned" , 71);
kw_reg("void" , 72);
kw_reg("volatile" , 73);
kw_reg("while" , 74);
}

static void test( char* token )
{ printf("%14s: %2i\n", token, kw_check( token ) ); }

int main( int argc, char** argv )
{ kw_init();
test( "NULL" );
test( "constexpr" );
test( "while" );
test( "_Thread_local" );
test( "rest" );
test( "random" );
}

Thiago Adams:

> This generator outputs the code
> [...]
> This code looks a bad linear search..but -o2 gcc transform
> this in a jump give the initial letter.

That is what I dislike about too clever and too high-level
optimisers: they change the essence of the algorithm so much
that the code is not executed as it is written. The compiler
does the work of the programmer. Now, depending on the
compiler, the same C code, may perform in O(n) or O(1),
which is crazy!

> The same code can be written using switch..
>
> int is_keyword(const char* s)
> {
> if(*s == 'N') {
> s++;
> /*NULL*/
> if( *s++ == 'U' && *s++ == 'L' && *s++ == 'L' && *s ==' ') return 0; else return -1;;
> }
> if(*s == '_') {
> s++;
> if(*s == 'A') {
> s++;
> if(*s == 'l') {

Thank you for the explanation, Thiago.

> The bad news it that without a "label pointer" we cannot
> write similar code by hand. We need a table jump. We
> have function pointers but I thing it will pay the price
> of function call.(haven't checked)

I have tried.

--
() ascii ribbon campaign -- against html e-mail
/\ http://preview.tinyurl.com/qcy6mjc [archived]

Anton Shepelev <anton.txt@gmail.com> writes:

> Ben Bacarisse:
>
>> This program reports zero (the token value assigned to
>> NULL) for a number of strings that are not keywords.
>
> Yes, it misfires for any words that is a prefix of a
> keyword. Below is a fixed version:

<snip>

That seems to be a little faster than the perfect hash version (on the
sqlite source).

--
Ben.

Ben Bacarisse to Anton Shepelev:

> > Below is a fixed version:
> > [...]
>
> That seems to be a little faster than the perfect hash
> version (on the sqlite source).

I think my solution is algorithmically equivalent to
Thiago's generated optimiser-based one, about which you
write:

> It runs a little slower than the perfect hash: about
> 0.08s. Both are close to the IO-only times so the lookup
> itself it may be significantly slower, but much more
> detailed timings would be needed to find out.

I believe we should rewrite the function to accept a
character pointer and a length, and then run some decicated,
synthetic, isolated tests, say with just two inputs:

1. a keyword,
2. a non-keyword.

I can contribute a test program (even I fail to dig out my
old one), if I am not the only interested party.

--
() ascii ribbon campaign - against html e-mail
/\ http://preview.tinyurl.com/qcy6mjc [archived]

On Friday, 26 August 2022 at 10:03:09 UTC+1, Anton Shepelev wrote:
> Ben Bacarisse to Anton Shepelev:
> > > Below is a fixed version:
> > > [...]
> >
> > That seems to be a little faster than the perfect hash
> > version (on the sqlite source).
> I think my solution is algorithmically equivalent to
> Thiago's generated optimiser-based one, about which you
> write:
>
> > It runs a little slower than the perfect hash: about
> > 0.08s. Both are close to the IO-only times so the lookup
> > itself it may be significantly slower, but much more
> > detailed timings would be needed to find out.
>
> I believe we should rewrite the function to accept a
> character pointer and a length, and then run some decicated,
> synthetic, isolated tests, say with just two inputs:
>
> 1. a keyword,
> 2. a non-keyword.
>
> I can contribute a test program (even I fail to dig out my
> old one), if I am not the only interested party.

I have a few problems with such a function.

My tests showed that the runtime of the function is usually dwarfed by the set-up time needed to obtain the input. So the emphasis is in the wrong place. (I also feel that those two parts are not distinct, and could either be combined, or made to work together.)

But also, by requiring a length, you've changed the game. With a length, you've now already narrowed down the possibilities for the keywords. For example, there is only one matching keyword when the length is 11, 12 or 14 characters,

Otherwise there is at most 13 keywords matching a particular length.

Without a length, the options are either to have it zero-terminated (which is how it works now), or to leave it open, which is more interesting: the pointer points into the middle of some text, and the end of the potential keyword is either:

- Non-alphabetic (including end-of-text marker)
- An alphabetic that rules out any keyword

This is interesting because then the function can be called as soon as the first character has been detected; no set-up is needed. It can improve overall performance.

On Wednesday, August 24, 2022 at 8:54:56 PM UTC-3, Thiago Adams wrote:
> On Wednesday, August 24, 2022 at 8:43:35 PM UTC-3, Thiago Adams wrote:
> > On Wednesday, August 24, 2022 at 7:04:36 PM UTC-3, Anton Shepelev wrote:
>
> > This generator outputs the code
> >
> output is:
>
> This code looks a bad linear search..but -o2 gcc transform this
> in a jump give the initial letter. The same code can be written using switch..
>
> int is_keyword(const char* s)
> {
> if(*s == 'N') {
> s++;
> /*NULL*/
> if( *s++ == 'U' && *s++ == 'L' && *s++ == 'L' && *s =='\0') return 0; else return -1;;
> }

I changed the generator to instead of using *s++ I put the [constant_index].

Like this:
if(s[0] == 'N') {
/*NULL*/
if( s[1] == 'U' && s[2] == 'L' && s[3] == 'L' && s[4] =='\0') return 0; else return -1;;
}

The compiler ouput is different.

--## GENERATOR ## --

#include <stdio.h>
#include <string.h>

void GenerateCore(const char* keywords[],
int first,
int last,
int level,
int* count) {
int ident = (level + 1) * 2;
for (int i = first; i <= last; i++) {
int begin = i;
int end = begin;
for (int k = i + 1; k <= last; k++) {
if (keywords[k][level] == keywords[begin][level]) {
i++;
end++;
}
else
break;
}
int index = level;
// we have the range
if (begin == end) {
// just one
if (keywords[i][level] != '\0') {
printf("%*cif(s[%d] == '%c') {\n", ident * 2, ' ', level, keywords[i][level]);

//printf("%*cs[%d];\n", ident * 3, ' ', index);
index++;

printf("%*c/*%s*/\n", ident * 3, ' ', keywords[i]);
printf("%*cif(", ident * 3, ' ');
int len = (int)strlen(keywords[i]);

int j = level + 1;
for (; j < len; j++) {
if (j != level + 1)
printf(" &&");

printf(" s[%d] == '%c'", index, keywords[i][j]);
index++;
}
if (j != level + 1) {
printf(" &&");
}
printf(" s[%d] =='\\0') return %i; else return -1;", index, i);

printf("\n");
printf("%*c}\n", ident * 2, ' ');
}
else {
printf("%*cif(*s == '\\0') {\n", ident * 2, ' ');
printf("%*cs[%d];\n", ident * 3, ' ', index); index++;
printf("%*c/*%s*/\n", ident * 3, ' ', keywords[i]);
printf("%*creturn % i;\n", ident * 3, ' ', i);
printf("%*c};\n", ident * 2, ' ');
}

(*count)++;
}
else {
printf("%*cif(s[%d] == '%c') {\n", ident * 2, ' ', level, keywords[i][level]);
//printf("%*cs[%d]; \n", ident * 3, ' ', index); index++;
index++;
GenerateCore(keywords, begin, end, level + 1, count);
printf("%*creturn -1;\n", ident * 3, ' ');
printf("%*c};\n", ident * 2, ' ');
}
}
}

void Generate(const char* keywords[], int size) {
/*sort keywords*/
int i, j;
for (i = 0; i < size - 1; i++) {
for (j = 0; j < size - i - 1; j++) {
if (strcmp(keywords[j], keywords[j + 1]) > 0) {
char* temp = keywords[j + 1];
keywords[j + 1] = keywords[j];
keywords[j] = temp;
}
}
}

printf("int is_keyword(const char* s)\n");
printf("{\n");
int count = 0;
GenerateCore(keywords, 0, size - 1, 0, &count);
printf("%*creturn -1;\n", 2, ' ');
printf("}\n");
}

int main() {
const char* keywords[] = { "NULL",
"_Alignas",
"_Alignof",
"__alignof",
"_Atomic",
"_BitInt",
"_Bool",
"_Complex",
"_Decimal128",
"_Decimal32",
"_Decimal64",
"_Generic",
"_Hashof",
"_Imaginary",
"_Noreturn",
"_Static_assert",
"_Thread_local",
"__asm",
"__forceinline",
"__inline",
"__int16",
"__int32",
"__int64",
"__int8",
"_asm",
"alignas",
"alignof",
"auto",
"bool",
"break",
"case",
"catch",
"char",
"const",
"constexpr",
"continue",
"default",
"defer",
"do",
"double",
"else",
"enum",
"extern",
"false",
"float",
"for",
"goto",
"if",
"inline",
"int",
"long",
"nullptr",
"register",
"repeat",
"restrict",
"return",
"short",
"signed",
"sizeof",
"static",
"static_assert",
"struct",
"switch",
"thread_local",
"throw",
"true",
"try",
"typedef",
"typeid",
"typeof",
"typeof_unqual",
"union",
"unsigned",
"void",
"volatile",
"while" };

Generate(keywords, sizeof(keywords) / sizeof(keywords[0]));
}

## GENERATOR OUTPUT ##

int is_keyword(const char* s)
{ if(s[0] == 'N') {
/*NULL*/
if( s[1] == 'U' && s[2] == 'L' && s[3] == 'L' && s[4] =='\0') return 0; else return -1;
}
if(s[0] == '_') {
if(s[1] == 'A') {
if(s[2] == 'l') {
if(s[3] == 'i') {
if(s[4] == 'g') {
if(s[5] == 'n') {
if(s[6] == 'a') {
/*_Alignas*/
if( s[7] == 's' && s[8] =='\0') return 1; else return -1;
}
if(s[6] == 'o') {
/*_Alignof*/
if( s[7] == 'f' && s[8] =='\0') return 2; else return -1;
}
return -1;
};
return -1;
};
return -1;
};
return -1;
};
if(s[2] == 't') {
/*_Atomic*/
if( s[3] == 'o' && s[4] == 'm' && s[5] == 'i' && s[6] == 'c' && s[7] =='\0') return 3; else return -1;
}
return -1;
};
if(s[1] == 'B') {
if(s[2] == 'i') {
/*_BitInt*/
if( s[3] == 't' && s[4] == 'I' && s[5] == 'n' && s[6] == 't' && s[7] =='\0') return 4; else return -1;
}
if(s[2] == 'o') {
/*_Bool*/
if( s[3] == 'o' && s[4] == 'l' && s[5] =='\0') return 5; else return -1;
}
return -1;
};
if(s[1] == 'C') {
/*_Complex*/
if( s[2] == 'o' && s[3] == 'm' && s[4] == 'p' && s[5] == 'l' && s[6] == 'e' && s[7] == 'x' && s[8] =='\0') return 6; else return -1;
}
if(s[1] == 'D') {
if(s[2] == 'e') {
if(s[3] == 'c') {
if(s[4] == 'i') {
if(s[5] == 'm') {
if(s[6] == 'a') {
if(s[7] == 'l') {
if(s[8] == '1') {
/*_Decimal128*/
if( s[9] == '2' && s[10] == '8' && s[11] =='\0') return 7; else return -1;
}
if(s[8] == '3') {
/*_Decimal32*/
if( s[9] == '2' && s[10] =='\0') return 8; else return -1;
}
if(s[8] == '6') {
/*_Decimal64*/
if( s[9] == '4' && s[10] =='\0') return 9; else return -1;
}
return -1;
};
return -1;
};
return -1;
};
return -1;
};
return -1;
};
return -1;
};
return -1;
};
if(s[1] == 'G') {
/*_Generic*/
if( s[2] == 'e' && s[3] == 'n' && s[4] == 'e' && s[5] == 'r' && s[6] == 'i' && s[7] == 'c' && s[8] =='\0') return 10; else return -1;
}
if(s[1] == 'H') {
/*_Hashof*/
if( s[2] == 'a' && s[3] == 's' && s[4] == 'h' && s[5] == 'o' && s[6] == 'f' && s[7] =='\0') return 11; else return -1;
}
if(s[1] == 'I') {
/*_Imaginary*/
if( s[2] == 'm' && s[3] == 'a' && s[4] == 'g' && s[5] == 'i' && s[6] == 'n' && s[7] == 'a' && s[8] == 'r' && s[9] == 'y' && s[10] =='\0') return 12; else return -1;
}
if(s[1] == 'N') {
/*_Noreturn*/
if( s[2] == 'o' && s[3] == 'r' && s[4] == 'e' && s[5] == 't' && s[6] == 'u' && s[7] == 'r' && s[8] == 'n' && s[9] =='\0') return 13; else return -1;
}
if(s[1] == 'S') {
/*_Static_assert*/
if( s[2] == 't' && s[3] == 'a' && s[4] == 't' && s[5] == 'i' && s[6] == 'c' && s[7] == '_' && s[8] == 'a' && s[9] == 's' && s[10] == 's' && s[11] == 'e' && s[12] == 'r' && s[13] == 't' && s[14] =='\0') return 14; else return -1;
}
if(s[1] == 'T') {
/*_Thread_local*/
if( s[2] == 'h' && s[3] == 'r' && s[4] == 'e' && s[5] == 'a' && s[6] == 'd' && s[7] == '_' && s[8] == 'l' && s[9] == 'o' && s[10] == 'c' && s[11] == 'a' && s[12] == 'l' && s[13] =='\0') return 15; else return -1;
}
if(s[1] == '_') {
if(s[2] == 'a') {
if(s[3] == 'l') {
/*__alignof*/
if( s[4] == 'i' && s[5] == 'g' && s[6] == 'n' && s[7] == 'o' && s[8] == 'f' && s[9] =='\0') return 16; else return -1;
}
if(s[3] == 's') {
/*__asm*/
if( s[4] == 'm' && s[5] =='\0') return 17; else return -1;
}
return -1;
};
if(s[2] == 'f') {
/*__forceinline*/
if( s[3] == 'o' && s[4] == 'r' && s[5] == 'c' && s[6] == 'e' && s[7] == 'i' && s[8] == 'n' && s[9] == 'l' && s[10] == 'i' && s[11] == 'n' && s[12] == 'e' && s[13] =='\0') return 18; else return -1;
}
if(s[2] == 'i') {
if(s[3] == 'n') {
if(s[4] == 'l') {
/*__inline*/
if( s[5] == 'i' && s[6] == 'n' && s[7] == 'e' && s[8] =='\0') return 19; else return -1;
}
if(s[4] == 't') {
if(s[5] == '1') {
/*__int16*/
if( s[6] == '6' && s[7] =='\0') return 20; else return -1;
}
if(s[5] == '3') {
/*__int32*/
if( s[6] == '2' && s[7] =='\0') return 21; else return -1;
}
if(s[5] == '6') {
/*__int64*/
if( s[6] == '4' && s[7] =='\0') return 22; else return -1;
}
if(s[5] == '8') {
/*__int8*/
if( s[6] =='\0') return 23; else return -1;
}
return -1;
};
return -1;
};
return -1;
};
return -1;
};
if(s[1] == 'a') {
/*_asm*/
if( s[2] == 's' && s[3] == 'm' && s[4] =='\0') return 24; else return -1;
}
return -1;
};
if(s[0] == 'a') {
if(s[1] == 'l') {
if(s[2] == 'i') {
if(s[3] == 'g') {
if(s[4] == 'n') {
if(s[5] == 'a') {
/*alignas*/
if( s[6] == 's' && s[7] =='\0') return 25; else return -1;
}
if(s[5] == 'o') {
/*alignof*/
if( s[6] == 'f' && s[7] =='\0') return 26; else return -1;
}
return -1;
};
return -1;
};
return -1;
};
return -1;
};
if(s[1] == 'u') {
/*auto*/
if( s[2] == 't' && s[3] == 'o' && s[4] =='\0') return 27; else return -1;
}
return -1;
};
if(s[0] == 'b') {
if(s[1] == 'o') {
/*bool*/
if( s[2] == 'o' && s[3] == 'l' && s[4] =='\0') return 28; else return -1;
}
if(s[1] == 'r') {
/*break*/
if( s[2] == 'e' && s[3] == 'a' && s[4] == 'k' && s[5] =='\0') return 29; else return -1;
}
return -1;
};
if(s[0] == 'c') {
if(s[1] == 'a') {
if(s[2] == 's') {
/*case*/
if( s[3] == 'e' && s[4] =='\0') return 30; else return -1;
}
if(s[2] == 't') {
/*catch*/
if( s[3] == 'c' && s[4] == 'h' && s[5] =='\0') return 31; else return -1;
}
return -1;
};
if(s[1] == 'h') {
/*char*/
if( s[2] == 'a' && s[3] == 'r' && s[4] =='\0') return 32; else return -1;
}
if(s[1] == 'o') {
if(s[2] == 'n') {
if(s[3] == 's') {
if(s[4] == 't') {
if(*s == '\0') {
s[5];
/*const*/
return 33;
};
if(s[5] == 'e') {
/*constexpr*/
if( s[6] == 'x' && s[7] == 'p' && s[8] == 'r' && s[9] =='\0') return 34; else return -1;
}
return -1;
};
return -1;
};
if(s[3] == 't') {
/*continue*/
if( s[4] == 'i' && s[5] == 'n' && s[6] == 'u' && s[7] == 'e' && s[8] =='\0') return 35; else return -1;
}
return -1;
};
return -1;
};
return -1;
};
if(s[0] == 'd') {
if(s[1] == 'e') {
if(s[2] == 'f') {
if(s[3] == 'a') {
/*default*/
if( s[4] == 'u' && s[5] == 'l' && s[6] == 't' && s[7] =='\0') return 36; else return -1;
}
if(s[3] == 'e') {
/*defer*/
if( s[4] == 'r' && s[5] =='\0') return 37; else return -1;
}
return -1;
};
return -1;
};
if(s[1] == 'o') {
if(*s == '\0') {
s[2];
/*do*/
return 38;
};
if(s[2] == 'u') {
/*double*/
if( s[3] == 'b' && s[4] == 'l' && s[5] == 'e' && s[6] =='\0') return 39; else return -1;
}
return -1;
};
return -1;
};
if(s[0] == 'e') {
if(s[1] == 'l') {
/*else*/
if( s[2] == 's' && s[3] == 'e' && s[4] =='\0') return 40; else return -1;
}
if(s[1] == 'n') {
/*enum*/
if( s[2] == 'u' && s[3] == 'm' && s[4] =='\0') return 41; else return -1;
}
if(s[1] == 'x') {
/*extern*/
if( s[2] == 't' && s[3] == 'e' && s[4] == 'r' && s[5] == 'n' && s[6] =='\0') return 42; else return -1;
}
return -1;
};
if(s[0] == 'f') {
if(s[1] == 'a') {
/*false*/
if( s[2] == 'l' && s[3] == 's' && s[4] == 'e' && s[5] =='\0') return 43; else return -1;
}
if(s[1] == 'l') {
/*float*/
if( s[2] == 'o' && s[3] == 'a' && s[4] == 't' && s[5] =='\0') return 44; else return -1;
}
if(s[1] == 'o') {
/*for*/
if( s[2] == 'r' && s[3] =='\0') return 45; else return -1;
}
return -1;
};
if(s[0] == 'g') {
/*goto*/
if( s[1] == 'o' && s[2] == 't' && s[3] == 'o' && s[4] =='\0') return 46; else return -1;
}
if(s[0] == 'i') {
if(s[1] == 'f') {
/*if*/
if( s[2] =='\0') return 47; else return -1;
}
if(s[1] == 'n') {
if(s[2] == 'l') {
/*inline*/
if( s[3] == 'i' && s[4] == 'n' && s[5] == 'e' && s[6] =='\0') return 48; else return -1;
}
if(s[2] == 't') {
/*int*/
if( s[3] =='\0') return 49; else return -1;
}
return -1;
};
return -1;
};
if(s[0] == 'l') {
/*long*/
if( s[1] == 'o' && s[2] == 'n' && s[3] == 'g' && s[4] =='\0') return 50; else return -1;
}
if(s[0] == 'n') {
/*nullptr*/
if( s[1] == 'u' && s[2] == 'l' && s[3] == 'l' && s[4] == 'p' && s[5] == 't' && s[6] == 'r' && s[7] =='\0') return 51; else return -1;
}
if(s[0] == 'r') {
if(s[1] == 'e') {
if(s[2] == 'g') {
/*register*/
if( s[3] == 'i' && s[4] == 's' && s[5] == 't' && s[6] == 'e' && s[7] == 'r' && s[8] =='\0') return 52; else return -1;
}
if(s[2] == 'p') {
/*repeat*/
if( s[3] == 'e' && s[4] == 'a' && s[5] == 't' && s[6] =='\0') return 53; else return -1;
}
if(s[2] == 's') {
/*restrict*/
if( s[3] == 't' && s[4] == 'r' && s[5] == 'i' && s[6] == 'c' && s[7] == 't' && s[8] =='\0') return 54; else return -1;
}
if(s[2] == 't') {
/*return*/
if( s[3] == 'u' && s[4] == 'r' && s[5] == 'n' && s[6] =='\0') return 55; else return -1;
}
return -1;
};
return -1;
};
if(s[0] == 's') {
if(s[1] == 'h') {
/*short*/
if( s[2] == 'o' && s[3] == 'r' && s[4] == 't' && s[5] =='\0') return 56; else return -1;
}
if(s[1] == 'i') {
if(s[2] == 'g') {
/*signed*/
if( s[3] == 'n' && s[4] == 'e' && s[5] == 'd' && s[6] =='\0') return 57; else return -1;
}
if(s[2] == 'z') {
/*sizeof*/
if( s[3] == 'e' && s[4] == 'o' && s[5] == 'f' && s[6] =='\0') return 58; else return -1;
}
return -1;
};
if(s[1] == 't') {
if(s[2] == 'a') {
if(s[3] == 't') {
if(s[4] == 'i') {
if(s[5] == 'c') {
if(*s == '\0') {
s[6];
/*static*/
return 59;
};
if(s[6] == '_') {
/*static_assert*/
if( s[7] == 'a' && s[8] == 's' && s[9] == 's' && s[10] == 'e' && s[11] == 'r' && s[12] == 't' && s[13] =='\0') return 60; else return -1;
}
return -1;
};
return -1;
};
return -1;
};
return -1;
};
if(s[2] == 'r') {
/*struct*/
if( s[3] == 'u' && s[4] == 'c' && s[5] == 't' && s[6] =='\0') return 61; else return -1;
}
return -1;
};
if(s[1] == 'w') {
/*switch*/
if( s[2] == 'i' && s[3] == 't' && s[4] == 'c' && s[5] == 'h' && s[6] =='\0') return 62; else return -1;
}
return -1;
};
if(s[0] == 't') {
if(s[1] == 'h') {
if(s[2] == 'r') {
if(s[3] == 'e') {
/*thread_local*/
if( s[4] == 'a' && s[5] == 'd' && s[6] == '_' && s[7] == 'l' && s[8] == 'o' && s[9] == 'c' && s[10] == 'a' && s[11] == 'l' && s[12] =='\0') return 63; else return -1;
}
if(s[3] == 'o') {
/*throw*/
if( s[4] == 'w' && s[5] =='\0') return 64; else return -1;
}
return -1;
};
return -1;
};
if(s[1] == 'r') {
if(s[2] == 'u') {
/*true*/
if( s[3] == 'e' && s[4] =='\0') return 65; else return -1;
}
if(s[2] == 'y') {
/*try*/
if( s[3] =='\0') return 66; else return -1;
}
return -1;
};
if(s[1] == 'y') {
if(s[2] == 'p') {
if(s[3] == 'e') {
if(s[4] == 'd') {
/*typedef*/
if( s[5] == 'e' && s[6] == 'f' && s[7] =='\0') return 67; else return -1;
}
if(s[4] == 'i') {
/*typeid*/
if( s[5] == 'd' && s[6] =='\0') return 68; else return -1;
}
if(s[4] == 'o') {
if(s[5] == 'f') {
if(*s == '\0') {
s[6];
/*typeof*/
return 69;
};
if(s[6] == '_') {
/*typeof_unqual*/
if( s[7] == 'u' && s[8] == 'n' && s[9] == 'q' && s[10] == 'u' && s[11] == 'a' && s[12] == 'l' && s[13] =='\0') return 70; else return -1;
}
return -1;
};
return -1;
};
return -1;
};
return -1;
};
return -1;
};
return -1;
};
if(s[0] == 'u') {
if(s[1] == 'n') {
if(s[2] == 'i') {
/*union*/
if( s[3] == 'o' && s[4] == 'n' && s[5] =='\0') return 71; else return -1;
}
if(s[2] == 's') {
/*unsigned*/
if( s[3] == 'i' && s[4] == 'g' && s[5] == 'n' && s[6] == 'e' && s[7] == 'd' && s[8] =='\0') return 72; else return -1;
}
return -1;
};
return -1;
};
if(s[0] == 'v') {
if(s[1] == 'o') {
if(s[2] == 'i') {
/*void*/
if( s[3] == 'd' && s[4] =='\0') return 73; else return -1;
}
if(s[2] == 'l') {
/*volatile*/
if( s[3] == 'a' && s[4] == 't' && s[5] == 'i' && s[6] == 'l' && s[7] == 'e' && s[8] =='\0') return 74; else return -1;
}
return -1;
};
return -1;
};
if(s[0] == 'w') {
/*while*/
if( s[1] == 'h' && s[2] == 'i' && s[3] == 'l' && s[4] == 'e' && s[5] =='\0') return 75; else return -1;
}
return -1;
}

On Friday, August 26, 2022 at 9:40:12 AM UTC-3, Thiago Adams wrote:
> On Wednesday, August 24, 2022 at 8:54:56 PM UTC-3, Thiago Adams wrote:
> > On Wednesday, August 24, 2022 at 8:43:35 PM UTC-3, Thiago Adams wrote:
> > > On Wednesday, August 24, 2022 at 7:04:36 PM UTC-3, Anton Shepelev wrote:
> >
> > > This generator outputs the code
> > >
> > output is:
> >
> > This code looks a bad linear search..but -o2 gcc transform this
> > in a jump give the initial letter. The same code can be written using switch..
> >
> > int is_keyword(const char* s)
> > {
> > if(*s == 'N') {
> > s++;
> > /*NULL*/
> > if( *s++ == 'U' && *s++ == 'L' && *s++ == 'L' && *s =='\0') return 0; else return -1;;
> > }
>
> I changed the generator to instead of using *s++ I put the [constant_index].
>
> Like this:
> if(s[0] == 'N') {
> /*NULL*/
> if( s[1] == 'U' && s[2] == 'L' && s[3] == 'L' && s[4] =='\0') return 0; else return -1;;
> }
>
> The compiler ouput is different.
>
> --## GENERATOR ## --
>
> #include <stdio.h>
> #include <string.h>
>
> void GenerateCore(const char* keywords[],
> int first,
> int last,
> int level,
> int* count) {
> int ident = (level + 1) * 2;
> for (int i = first; i <= last; i++) {
> int begin = i;
> int end = begin;
> for (int k = i + 1; k <= last; k++) {
> if (keywords[k][level] == keywords[begin][level]) {
> i++;
> end++;
> }
> else
> break;
> }
> int index = level;
> // we have the range
> if (begin == end) {
> // just one
> if (keywords[i][level] != '\0') {
> printf("%*cif(s[%d] == '%c') {\n", ident * 2, ' ', level, keywords[i][level]);
>
> //printf("%*cs[%d];\n", ident * 3, ' ', index);
> index++;
>
> printf("%*c/*%s*/\n", ident * 3, ' ', keywords[i]);
> printf("%*cif(", ident * 3, ' ');
> int len = (int)strlen(keywords[i]);
>
> int j = level + 1;
> for (; j < len; j++) {
> if (j != level + 1)
> printf(" &&");
>
> printf(" s[%d] == '%c'", index, keywords[i][j]);
> index++;
> }
> if (j != level + 1) {
> printf(" &&");
> }
> printf(" s[%d] =='\\0') return %i; else return -1;", index, i);
>
> printf("\n");
> printf("%*c}\n", ident * 2, ' ');
> }
> else {
> printf("%*cif(*s == '\\0') {\n", ident * 2, ' ');
> printf("%*cs[%d];\n", ident * 3, ' ', index); index++;
> printf("%*c/*%s*/\n", ident * 3, ' ', keywords[i]);
> printf("%*creturn % i;\n", ident * 3, ' ', i);
> printf("%*c};\n", ident * 2, ' ');
> }
>
> (*count)++;
> }
> else {
> printf("%*cif(s[%d] == '%c') {\n", ident * 2, ' ', level, keywords[i][level]);
> //printf("%*cs[%d]; \n", ident * 3, ' ', index); index++;
> index++;
> GenerateCore(keywords, begin, end, level + 1, count);
> printf("%*creturn -1;\n", ident * 3, ' ');
> printf("%*c};\n", ident * 2, ' ');
> }
> }
> }
>
> void Generate(const char* keywords[], int size) {
> /*sort keywords*/
> int i, j;
> for (i = 0; i < size - 1; i++) {
> for (j = 0; j < size - i - 1; j++) {
> if (strcmp(keywords[j], keywords[j + 1]) > 0) {
> char* temp = keywords[j + 1];
> keywords[j + 1] = keywords[j];
> keywords[j] = temp;
> }
> }
> }
>
> printf("int is_keyword(const char* s)\n");
> printf("{\n");
> int count = 0;
> GenerateCore(keywords, 0, size - 1, 0, &count);
> printf("%*creturn -1;\n", 2, ' ');
> printf("}\n");
> }
>
> int main() {
> const char* keywords[] = { "NULL",
> "_Alignas",
> "_Alignof",
> "__alignof",
> "_Atomic",
> "_BitInt",
> "_Bool",
> "_Complex",
> "_Decimal128",
> "_Decimal32",
> "_Decimal64",
> "_Generic",
> "_Hashof",
> "_Imaginary",
> "_Noreturn",
> "_Static_assert",
> "_Thread_local",
> "__asm",
> "__forceinline",
> "__inline",
> "__int16",
> "__int32",
> "__int64",
> "__int8",
> "_asm",
> "alignas",
> "alignof",
> "auto",
> "bool",
> "break",
> "case",
> "catch",
> "char",
> "const",
> "constexpr",
> "continue",
> "default",
> "defer",
> "do",
> "double",
> "else",
> "enum",
> "extern",
> "false",
> "float",
> "for",
> "goto",
> "if",
> "inline",
> "int",
> "long",
> "nullptr",
> "register",
> "repeat",
> "restrict",
> "return",
> "short",
> "signed",
> "sizeof",
> "static",
> "static_assert",
> "struct",
> "switch",
> "thread_local",
> "throw",
> "true",
> "try",
> "typedef",
> "typeid",
> "typeof",
> "typeof_unqual",
> "union",
> "unsigned",
> "void",
> "volatile",
> "while" };
>
>
>
> Generate(keywords, sizeof(keywords) / sizeof(keywords[0]));
> }
>
> ## GENERATOR OUTPUT ##
Sorry..the previous generator has a bug..

NEW CODE

#include <stdio.h>
#include <string.h>

void GenerateCore(const char* keywords[],
int first,
int last,
int level,
int* count) {
int ident = (level + 1) * 2;
for (int i = first; i <= last; i++) {
int begin = i;
int end = begin;
for (int k = i + 1; k <= last; k++) {
if (keywords[k][level] == keywords[begin][level]) {
i++;
end++;
}
else
break;
}
int index = level;
// we have the range
if (begin == end) {
// just one
if (keywords[i][level] != '\0') {
printf("%*cif(s[%d] == '%c') {\n", ident * 2, ' ', level, keywords[i][level]);

//printf("%*cs[%d];\n", ident * 3, ' ', index);
index++;

printf("%*c/*%s*/\n", ident * 3, ' ', keywords[i]);
printf("%*cif(", ident * 3, ' ');
int len = (int)strlen(keywords[i]);

int j = level + 1;
for (; j < len; j++) {
if (j != level + 1)
printf(" &&");

printf(" s[%d] == '%c'", index, keywords[i][j]);
index++;
}
if (j != level + 1) {
printf(" &&");
}
printf(" s[%d] =='\\0') return %i; else return -1;", index, i);

printf("\n");
printf("%*c}\n", ident * 2, ' ');
}
else {
printf("%*cif(s[%d] == '\\0') {\n", ident * 2, ' ', index);

printf("%*c/*%s*/\n", ident * 3, ' ', keywords[i]);
printf("%*creturn % i;\n", ident * 3, ' ', i);
printf("%*c};\n", ident * 2, ' ');
}

Thiago Adams <thiago.adams@gmail.com> writes:
>On Wednesday, August 24, 2022 at 8:54:56 PM UTC-3, Thiago Adams wrote:
>> On Wednesday, August 24, 2022 at 8:43:35 PM UTC-3, Thiago Adams wrote:
>> > On Wednesday, August 24, 2022 at 7:04:36 PM UTC-3, Anton Shepelev wrote:
>>
>> > This generator outputs the code
>> >
>> output is:
>>
>> This code looks a bad linear search..but -o2 gcc transform this
>> in a jump give the initial letter. The same code can be written using switch..
>>

<snip>

A perfect example of trading space for speed. Your is_keyword function
is over 8Kb of x86_64 code (unoptimized), over 5Kb with O2/O3. That
might have some negative effect on the L1 icache, actually reducing
overall performance due to icache misses in other parts of the application.

A symbol table lookup function using a simple double-linked list hash
bucket scheme is less than 512 bytes of object code. This algorithm
however, has potential locality issues, impacting both dcache
and tlb miss rate depending on how the symbol table linked
list entries are allocated (using a pool allocator will reduce
locality issues when compared with willy-nilly use of new,
either directly or under the covers with soi disant smart pointers).

c_symbol *
c_symbol_table::lookup(const char *name, uint64 line)
{ c_dlist_iterator di(&st_buckets[hash(name)]);
while (di.next()) {
c_symbol *sp = (c_symbol *)di.curr();

if (strcmp(name, sp->get_name()) == 0) {
if (line > 0) {
sp->add_ref(line);
}
return sp;
}
}

return NULL;
}

Before microoptimizing a lookup function, I would profile the application which
calls the function to see if it is a hotspot.

Before complaining about the home-made iterator, note that this
code dates to circa 1990 with cfront 2.1.