Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #167089 > unrolled thread
| Started by | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| First post | 2022-08-22 07:17 -0700 |
| Last post | 2022-08-25 11:33 +0300 |
| Articles | 20 on this page of 110 — 14 participants |
Back to article view | Back to comp.lang.c
How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-22 07:17 -0700
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-22 07:34 -0700
Re: How to optimize this search? scott@slp53.sl.home (Scott Lurndal) - 2022-08-22 16:17 +0000
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-22 09:24 -0700
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-22 09:38 -0700
Re: How to optimize this search? scott@slp53.sl.home (Scott Lurndal) - 2022-08-22 17:03 +0000
Re: How to optimize this search? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2022-08-23 14:58 +0300
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-23 05:02 -0700
Re: How to optimize this search? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2022-08-23 17:50 +0300
Re: How to optimize this search? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-08-23 16:58 +0100
Re: How to optimize this search? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2022-08-23 19:21 +0300
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-23 09:46 -0700
Re: How to optimize this search? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2022-08-23 20:06 +0300
Re: How to optimize this search? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-08-23 23:39 +0100
Re: How to optimize this search? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2022-08-24 11:20 +0300
Re: How to optimize this search? Anton Shepelev <anton.txt@gmail.com> - 2022-08-25 00:52 +0300
Re: How to optimize this search? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-08-24 23:23 +0100
Re: How to optimize this search? Anton Shepelev <anton.txt@gmail.com> - 2022-08-26 01:38 +0300
Re: How to optimize this search? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-08-26 00:55 +0100
Re: How to optimize this search? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2022-08-26 12:02 +0300
Re: How to optimize this search? bart c <bart4858@gmail.com> - 2022-08-26 04:10 -0700
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-22 10:47 -0700
Re: How to optimize this search? scott@slp53.sl.home (Scott Lurndal) - 2022-08-22 18:10 +0000
Re: How to optimize this search? bart c <bart4858@gmail.com> - 2022-08-22 15:22 -0700
Re: How to optimize this search? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-08-22 15:37 -0700
Re: How to optimize this search? bart c <bart4858@gmail.com> - 2022-08-22 16:28 -0700
Re: How to optimize this search? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-08-23 01:18 +0100
Re: How to optimize this search? bart c <bart4858@gmail.com> - 2022-08-22 18:01 -0700
Re: How to optimize this search? antispam@math.uni.wroc.pl - 2022-08-23 00:07 +0000
Re: How to optimize this search? bart c <bart4858@gmail.com> - 2022-08-22 18:12 -0700
Re: How to optimize this search? antispam@math.uni.wroc.pl - 2022-08-23 01:54 +0000
Re: How to optimize this search? David Brown <david.brown@hesbynett.no> - 2022-08-23 08:50 +0200
Re: How to optimize this search? bart c <bart4858@gmail.com> - 2022-08-23 04:18 -0700
Re: How to optimize this search? David Brown <david.brown@hesbynett.no> - 2022-08-23 15:50 +0200
Re: How to optimize this search? antispam@math.uni.wroc.pl - 2022-08-22 18:51 +0000
Re: How to optimize this search? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-08-22 16:34 +0100
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-22 09:14 -0700
Re: How to optimize this search? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-08-22 17:33 +0100
Re: How to optimize this search? Siri Cruise <chine.bleu@yahoo.com> - 2022-08-22 08:44 -0700
Re: How to optimize this search? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-08-22 16:53 +0100
Re: How to optimize this search? Siri Cruise <chine.bleu@yahoo.com> - 2022-08-22 09:29 -0700
Re: How to optimize this search? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-08-22 17:36 +0100
Re: How to optimize this search? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-08-22 16:53 +0100
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-22 09:11 -0700
Re: How to optimize this search? antispam@math.uni.wroc.pl - 2022-08-22 19:30 +0000
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-22 14:19 -0700
Re: How to optimize this search? Öö Tiib <ootiib@hot.ee> - 2022-08-22 14:36 -0700
Re: How to optimize this search? antispam@math.uni.wroc.pl - 2022-08-22 22:49 +0000
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-23 05:13 -0700
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-23 15:55 -0700
Re: How to optimize this search? bart c <bart4858@gmail.com> - 2022-08-23 16:36 -0700
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-23 17:42 -0700
Re: How to optimize this search? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-08-23 18:36 -0700
Re: How to optimize this search? bart c <bart4858@gmail.com> - 2022-08-24 03:34 -0700
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-24 04:40 -0700
Re: How to optimize this search? David Brown <david.brown@hesbynett.no> - 2022-08-24 09:30 +0200
Re: How to optimize this search? William Ahern <william@25thandClement.com> - 2022-08-24 12:36 -0700
Re: How to optimize this search? Bonita Montero <Bonita.Montero@gmail.com> - 2022-08-22 17:51 +0200
Re: How to optimize this search? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-08-22 16:55 +0100
Re: How to optimize this search? Bonita Montero <Bonita.Montero@gmail.com> - 2022-08-22 18:14 +0200
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-22 09:15 -0700
Re: How to optimize this search? Bonita Montero <Bonita.Montero@gmail.com> - 2022-08-22 18:28 +0200
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-22 09:34 -0700
Re: How to optimize this search? Bonita Montero <Bonita.Montero@gmail.com> - 2022-08-22 18:35 +0200
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-22 09:45 -0700
Re: How to optimize this search? Bonita Montero <Bonita.Montero@gmail.com> - 2022-08-22 18:51 +0200
Re: How to optimize this search? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2022-08-23 17:53 +0300
Re: How to optimize this search? bart c <bart4858@gmail.com> - 2022-08-22 10:20 -0700
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-22 10:53 -0700
Re: How to optimize this search? antispam@math.uni.wroc.pl - 2022-08-22 23:31 +0000
Re: How to optimize this search? bart c <bart4858@gmail.com> - 2022-08-22 17:04 -0700
Re: How to optimize this search? Tim Rentsch <tr.17687@z991.linuxsc.com> - 2022-08-23 09:50 -0700
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-23 10:07 -0700
Re: How to optimize this search? bart c <bart4858@gmail.com> - 2022-08-23 11:28 -0700
Re: How to optimize this search? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-08-23 12:17 -0700
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-23 13:16 -0700
Re: How to optimize this search? bart c <bart4858@gmail.com> - 2022-08-23 13:18 -0700
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-23 13:23 -0700
Re: How to optimize this search? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-08-23 13:40 -0700
Re: How to optimize this search? bart c <bart4858@gmail.com> - 2022-08-23 16:26 -0700
Re: How to optimize this search? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-08-23 16:50 -0700
Re: How to optimize this search? bart c <bart4858@gmail.com> - 2022-08-23 17:26 -0700
Re: How to optimize this search? antispam@math.uni.wroc.pl - 2022-08-23 23:54 +0000
Re: How to optimize this search? Keith Thompson <Keith.S.Thompson+u@gmail.com> - 2022-08-23 17:16 -0700
Re: How to optimize this search? David Brown <david.brown@hesbynett.no> - 2022-08-24 09:43 +0200
Re: How to optimize this search? bart c <bart4858@gmail.com> - 2022-08-24 04:03 -0700
Re: How to optimize this search? antispam@math.uni.wroc.pl - 2022-08-24 14:15 +0000
Re: How to optimize this search? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-08-24 13:28 +0100
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-24 06:25 -0700
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-24 06:50 -0700
Re: How to optimize this search? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-08-24 15:19 +0100
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-24 09:46 -0700
Re: How to optimize this search? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-08-24 20:40 +0100
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-24 10:08 -0700
Re: How to optimize this search? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-08-24 20:42 +0100
Re: How to optimize this search? bart c <bart4858@gmail.com> - 2022-08-24 07:31 -0700
Re: How to optimize this search? Anton Shepelev <anton.txt@gmail.com> - 2022-08-25 01:04 +0300
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-24 16:43 -0700
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-24 16:54 -0700
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-24 17:08 -0700
Re: How to optimize this search? Anton Shepelev <anton.txt@gmail.com> - 2022-08-26 01:47 +0300
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-26 05:40 -0700
Re: How to optimize this search? Thiago Adams <thiago.adams@gmail.com> - 2022-08-26 06:29 -0700
Re: How to optimize this search? scott@slp53.sl.home (Scott Lurndal) - 2022-08-26 14:05 +0000
Re: How to optimize this search? bart c <bart4858@gmail.com> - 2022-08-24 06:45 -0700
Re: How to optimize this search? bart c <bart4858@gmail.com> - 2022-08-24 13:01 -0700
Re: How to optimize this search? Anton Shepelev <anton.txt@gmail.com> - 2022-08-25 01:17 +0300
Re: How to optimize this search? Ben Bacarisse <ben.usenet@bsb.me.uk> - 2022-08-24 23:38 +0100
Re: How to optimize this search? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2022-08-25 11:29 +0300
Re: How to optimize this search? Anton Shepelev <anton.txt@g{oogle}mail.com> - 2022-08-25 11:33 +0300
Page 1 of 6 [1] 2 3 4 5 6 Next page →
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-22 07:17 -0700 |
| Subject | How to optimize this search? |
| Message-ID | <d8294420-7b45-4344-b9eb-0ad867850ec6n@googlegroups.com> |
Given a c string I need to return as fast as possible the pair (if exist) of the corresponding keyword_pair.
struct keyword_pair{
const char* lexeme;
int token;
};
struct keyword_pair[] = {
{ "NULL", 0},
{ "_Alignas", 1},
{ "_Atomic", 2},
{ "_BitInt", 3},
{ "_Bool", 4},
{ "_Complex", 5},
{ "_Decimal128", 6},
{ "_Decimal32", 7},
{ "_Decimal64", 8},
{ "_Generic", 9},
{ "_Hashof", 10},
{ "_Imaginary", 11},
{ "_Noreturn", 12},
{ "_Static_assert", 13},
{ "_Thread_local", 14},
{ "__alignof", 15},
{ "__asm", 16},
{ "__forceinline", 17},
{ "__inline", 18},
{ "__int16", 19},
{ "__int32", 20},
{ "__int64", 21},
{ "__int8", 22},
{ "_asm", 23},
{ "alignas", 24},
{ "alignof", 25},
{ "auto", 26},
{ "bool", 27},
{ "break", 28},
{ "case", 29},
{ "catch", 30},
{ "char", 31},
{ "const", 32},
{ "constexpr", 33},
{ "continue", 34},
{ "default", 35},
{ "defer", 36},
{ "do", 37},
{ "double", 38},
{ "else", 39},
{ "enum", 40},
{ "extern", 41},
{ "false", 42},
{ "float", 43},
{ "for", 44},
{ "goto", 45},
{ "if", 46},
{ "inline", 47},
{ "int", 48},
{ "long", 49},
{ "nullptr", 50},
{ "register", 51},
{ "repeat", 52},
{ "restrict", 53},
{ "return", 54},
{ "short", 55},
{ "signed", 56},
{ "sizeof", 57},
{ "static", 58},
{ "static_assert", 59},
{ "struct", 60},
{ "switch", 61},
{ "thread_local", 62},
{ "throw", 63},
{ "true", 64},
{ "try", 65},
{ "typedef", 66},
{ "typeid", 67},
{ "typeof", 68},
{ "typeof_unqual", 69},
{ "union", 70},
{ "unsigned", 71},
{ "void", 72},
{ "volatile", 73},
{ "while", 74},
};
[toc] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-22 07:34 -0700 |
| Message-ID | <b8624e58-8af6-4c48-8b27-694174e4243cn@googlegroups.com> |
| In reply to | #167089 |
On Monday, August 22, 2022 at 11:17:29 AM UTC-3, Thiago Adams wrote:
> Given a c string I need to return as fast as possible the pair (if exist) of the corresponding keyword_pair.
How compiler generates code for switch?
But does assembler has a "dynamic" jump?
I want to "jump" to code that search for words starting with 'a' for instance
and jump to the code that search for words starting with 'b'.
switch(str[0])
{
case 'a':
switch(str[1])
{
case 'l': /*alignof*/
break;
case 'u': /*auto*/
break;
case 'l': /*alignas, alignof*/
break;
}
break;
...
}
[toc] | [prev] | [next] | [standalone]
| From | scott@slp53.sl.home (Scott Lurndal) |
|---|---|
| Date | 2022-08-22 16:17 +0000 |
| Message-ID | <5_NMK.799766$ntj.539650@fx15.iad> |
| In reply to | #167090 |
Thiago Adams <thiago.adams@gmail.com> writes: >On Monday, August 22, 2022 at 11:17:29 AM UTC-3, Thiago Adams wrote: >> Given a c string I need to return as fast as possible the pair (if exist) of the corresponding keyword_pair. > Use a binary search. Max comparisons for your 70+ entries would be 6.
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-22 09:24 -0700 |
| Message-ID | <ac7f8956-aadb-4179-9327-ab8a25547de9n@googlegroups.com> |
| In reply to | #167102 |
On Monday, August 22, 2022 at 1:17:18 PM UTC-3, Scott Lurndal wrote:
> Thiago Adams <thiago...@gmail.com> writes:
> >On Monday, August 22, 2022 at 11:17:29 AM UTC-3, Thiago Adams wrote:
> >> Given a c string I need to return as fast as possible the pair (if exist) of the corresponding keyword_pair.
> >
> Use a binary search. Max comparisons for your 70+ entries would
> be 6.
I tried!
Using a switch for the first character and then using if with strcmp was
faster than binary search.
switch(str[0])
{
case 'a':
if (strcmp(str, "auto") == 0) return 1;
break;
...
etc...
}
The compiler is creating the code for me and I want to understand
better how it is doing then maybe I can improve further..
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-22 09:38 -0700 |
| Message-ID | <60da3e78-a685-446e-b75a-a35bf249d2cen@googlegroups.com> |
| In reply to | #167103 |
On Monday, August 22, 2022 at 1:24:12 PM UTC-3, Thiago Adams wrote:
> On Monday, August 22, 2022 at 1:17:18 PM UTC-3, Scott Lurndal wrote:
> > Thiago Adams <thiago...@gmail.com> writes:
> > >On Monday, August 22, 2022 at 11:17:29 AM UTC-3, Thiago Adams wrote:
> > >> Given a c string I need to return as fast as possible the pair (if exist) of the corresponding keyword_pair.
> > >
> > Use a binary search. Max comparisons for your 70+ entries would
> > be 6.
> I tried!
>
> Using a switch for the first character and then using if with strcmp was
> faster than binary search.
> switch(str[0])
> {
> case 'a':
> if (strcmp(str, "auto") == 0) return 1;
> break;
> ...
> etc...
> }
>
> The compiler is creating the code for me and I want to understand
> better how it is doing then maybe I can improve further..
int find(const char* s)
{
switch(s[0])
{
case 'a':
return 1;
case 'b':
return 2;
case 'c':
return 3;
}
return -1;
}
int main(int argv, char* args[]){
return find(args[1]);
}
without optimisations if looks like if else if else...
https://godbolt.org/z/Gn7K7vThM
but with -o3..it is completely different.
https://godbolt.org/z/6b65zYoEq
[toc] | [prev] | [next] | [standalone]
| From | scott@slp53.sl.home (Scott Lurndal) |
|---|---|
| Date | 2022-08-22 17:03 +0000 |
| Message-ID | <VFOMK.157471$Me2.32072@fx47.iad> |
| In reply to | #167103 |
Thiago Adams <thiago.adams@gmail.com> writes:
>On Monday, August 22, 2022 at 1:17:18 PM UTC-3, Scott Lurndal wrote:
>> Thiago Adams <thiago...@gmail.com> writes:
>> >On Monday, August 22, 2022 at 11:17:29 AM UTC-3, Thiago Adams wrote:
>> >> Given a c string I need to return as fast as possible the pair (if exist) of the corresponding keyword_pair.
>> >
>> Use a binary search. Max comparisons for your 70+ entries would
>> be 6.
>I tried!
>
>Using a switch for the first character and then using if with strcmp was
>faster than binary search.
>
>switch(str[0])
>{
>case 'a':
> if (strcmp(str, "auto") == 0) return 1;
> break;
>...
>etc...
>}
>
>The compiler is creating the code for me and I want to understand
>better how it is doing then maybe I can improve further..
code space vs. performance.
[toc] | [prev] | [next] | [standalone]
| From | Anton Shepelev <anton.txt@g{oogle}mail.com> |
|---|---|
| Date | 2022-08-23 14:58 +0300 |
| Message-ID | <20220823145856.464a208687d544911b246825@g{oogle}mail.com> |
| In reply to | #167103 |
Scott Lurndal to Thiago Adams: > > Use a binary search. Max comparisons for your 70+ > > entries would be 6. > > I tried! If speed is that important, which does not seem so to me in your case, generate a perfect hash. -- () ascii ribbon campaign - against html e-mail /\ http://preview.tinyurl.com/qcy6mjc [archived]
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-23 05:02 -0700 |
| Message-ID | <607d6a50-9932-4b63-9108-0894646ad04bn@googlegroups.com> |
| In reply to | #167140 |
On Tuesday, August 23, 2022 at 8:59:11 AM UTC-3, Anton Shepelev wrote: > Scott Lurndal to Thiago Adams: > > > Use a binary search. Max comparisons for your 70+ > > > entries would be 6. > > > > I tried! > > If speed is that important, which does not seem so to me in > your case, generate a perfect hash. The perfect hash will ensure each keyword has a unique hash right? So we need hash the input then we have the index in a table. Then because the input can have by coincidence the same hash we need strcmp. The total time is time to compute hash + (index table is fast) + strcmp. I believe we can have better performance than this for some cases.
[toc] | [prev] | [next] | [standalone]
| From | Anton Shepelev <anton.txt@g{oogle}mail.com> |
|---|---|
| Date | 2022-08-23 17:50 +0300 |
| Message-ID | <20220823175014.5b34c47ce60ab0dd18768269@g{oogle}mail.com> |
| In reply to | #167141 |
Thiago Adams to Anton Shepelev: > > If speed is that important, which does not seem so to me > > in your case, generate a perfect hash. > > The perfect hash will ensure each keyword has a unique > hash right? Yes. > So we need hash the input then we have the index in a > table. Then because the input can have by coincidence the > same hash we need strcmp. I am confused. A perfect hash is designed to avoid collisions. Why shluld we need strcmp? > The total time is time to compute > hash + (index table is fast) + strcmp. > I believe we can have better performance than this for > some cases. But the hasing ought to be done at compile time or at program startup. -- () ascii ribbon campaign - against html e-mail /\ http://preview.tinyurl.com/qcy6mjc [archived]
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-08-23 16:58 +0100 |
| Message-ID | <87a67vuf2n.fsf@bsb.me.uk> |
| In reply to | #167147 |
Anton Shepelev <anton.txt@g{oogle}mail.com> writes:
> Thiago Adams to Anton Shepelev:
>
>> > If speed is that important, which does not seem so to me
>> > in your case, generate a perfect hash.
>>
>> The perfect hash will ensure each keyword has a unique
>> hash right?
>
> Yes.
>
>> So we need hash the input then we have the index in a
>> table. Then because the input can have by coincidence the
>> same hash we need strcmp.
>
> I am confused. A perfect hash is designed to avoid
> collisions. Why shluld we need strcmp?
There are no collision among the keywords, but some strings that are not
keywords might hash the same value as one.
I suppose there might be a way to generate a truly perfect hash that
generates an index outside the table for every possible string not in
it, but I've not seen such a thing.
>> The total time is time to compute
>> hash + (index table is fast) + strcmp.
>> I believe we can have better performance than this for
>> some cases.
You mean with an FSA? It would be interesting to compare times. Also
implementation times. I was cooking dinner when I suggested a perfect
hash, but I had a program running withing 45 minutes of posting. That
included finding gpref, installing it reading enough documentation to
get to going.
> But the hasing ought to be done at compile time or at
> program startup.
Not sure what you mean. You can't hash the input until there is input,
but gperf does, of course, make a static, compile time, hash table.
--
Ben.
[toc] | [prev] | [next] | [standalone]
| From | Anton Shepelev <anton.txt@g{oogle}mail.com> |
|---|---|
| Date | 2022-08-23 19:21 +0300 |
| Message-ID | <20220823192116.ccb5f45f05abfc38e14ad9af@g{oogle}mail.com> |
| In reply to | #167149 |
Ben Bacarisse to Anton Shepelev: > > I am confused. A perfect hash is designed to avoid > > collisions. Why shluld we need strcmp? > > There are no collision among the keywords, but some > strings that are not keywords might hash the same value as > one. Thiago wrote nothing about any other strings than the static set of keywords known in advance. > > But the hasing ought to be done at compile time or at > > program startup. > > Not sure what you mean. You can't hash the input until > there is input, but gperf does, of course, make a static, > compile time, hash table. Mutual. As understood Thiago's post, he wants to search a static set of keywords, not arbitrary unpredictable input. If need be, he chould use a separate and more traditional hash table for non-keywords, but that seems beyond the original question... Do you mean the hashing of string literals? -- () ascii ribbon campaign - against html e-mail /\ http://preview.tinyurl.com/qcy6mjc [archived]
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-23 09:46 -0700 |
| Message-ID | <493e6a13-22be-4d0b-a968-8301b386fc82n@googlegroups.com> |
| In reply to | #167150 |
On Tuesday, August 23, 2022 at 1:21:30 PM UTC-3, Anton Shepelev wrote: > Ben Bacarisse to Anton Shepelev: > > > I am confused. A perfect hash is designed to avoid > > > collisions. Why shluld we need strcmp? > > > > There are no collision among the keywords, but some > > strings that are not keywords might hash the same value as > > one. Yes the input is any identifier.
[toc] | [prev] | [next] | [standalone]
| From | Anton Shepelev <anton.txt@g{oogle}mail.com> |
|---|---|
| Date | 2022-08-23 20:06 +0300 |
| Message-ID | <20220823200606.db811f5f9ce0a3dd7d129ba6@g{oogle}mail.com> |
| In reply to | #167153 |
Thiago Adams: > Yes the input is any identifier. I see. What about an NFA-based tokeniser that would narrow down the set of possible keywords while reading the source character by character, as described here wrt RegExes: https://swtch.com/~rsc/regexp/regexp1.html Since each step handles a single character, the search can be efficiently indexed using arrays. It seems to me the most efficient (because earliest) use of incoming information. -- () ascii ribbon campaign - against html e-mail /\ http://preview.tinyurl.com/qcy6mjc [archived]
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-08-23 23:39 +0100 |
| Message-ID | <874jy2vb3m.fsf@bsb.me.uk> |
| In reply to | #167150 |
Anton Shepelev <anton.txt@g{oogle}mail.com> writes:
> Ben Bacarisse to Anton Shepelev:
>
>> > I am confused. A perfect hash is designed to avoid
>> > collisions. Why shluld we need strcmp?
>>
>> There are no collision among the keywords, but some
>> strings that are not keywords might hash the same value as
>> one.
>
> Thiago wrote nothing about any other strings than the static
> set of keywords known in advance.
It would be very odd to only lookup strings that you know are in a
table. And very, very odd given the context -- language keywords. TA
will want to know if a token is or is not a keyword.
--
Ben.
[toc] | [prev] | [next] | [standalone]
| From | Anton Shepelev <anton.txt@g{oogle}mail.com> |
|---|---|
| Date | 2022-08-24 11:20 +0300 |
| Message-ID | <20220824112016.061ec6fc03ae86688a8534b6@g{oogle}mail.com> |
| In reply to | #167165 |
Ben Bacarisse to Anton Shepelev: > > Thiago wrote nothing about any other strings than the > > static set of keywords known in advance. > > It would be very odd to only lookup strings that you know > are in a table. And very, very odd given the > context -- language keywords. TA will want to know if a > token is or is not a keyword. Yes, it makes no sense for a lexical analyser, but may be useful for some queer task. I will try to gnaw out some time his evening to post my solution. -- () ascii ribbon campaign - against html e-mail /\ http://preview.tinyurl.com/qcy6mjc [archived]
[toc] | [prev] | [next] | [standalone]
| From | Anton Shepelev <anton.txt@gmail.com> |
|---|---|
| Date | 2022-08-25 00:52 +0300 |
| Message-ID | <20220825005213.77a5a9e36a0e8fe01a1c42f3@gmail.com> |
| In reply to | #167179 |
I wrote:
> I will try to gnaw out some time his evening to post my
> solution.
OK, my solution is below. Thiago's in-place initialisation
did not work in my TCC, so I wrote an initialisation
function, kw_init().
#include <stdio.h>
#include <stdlib.h>
/* TODO: allocate tree[] elements from kw_reg() as needed */
int tree[4096][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 == 0 )
{ 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 == 0 ) break; /* unknown prefix => not a keyword */
ctab = tree[next]; /* continue to next level */
word += 1;
}
return res;
}
static void kw_init()
{ tree_h = 0;
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( "random" );
}
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-08-24 23:23 +0100 |
| Message-ID | <87pmgpqo1d.fsf@bsb.me.uk> |
| In reply to | #167198 |
Anton Shepelev <anton.txt@gmail.com> writes:
> I wrote:
>
>> I will try to gnaw out some time his evening to post my
>> solution.
>
> OK, my solution is below. Thiago's in-place initialisation
> did not work in my TCC, so I wrote an initialisation
> function, kw_init().
This program reports zero (the token value assigned to NULL) for a
number of strings that are not keywords.
<cut code>
> int main( int argc, char** argv )
> { kw_init();
> test( "NULL" );
> test( "constexpr" );
> test( "while" );
> test( "_Thread_local" );
> test( "random" );
> }
Try, for example, test("rest").
--
Ben.
[toc] | [prev] | [next] | [standalone]
| From | Anton Shepelev <anton.txt@gmail.com> |
|---|---|
| Date | 2022-08-26 01:38 +0300 |
| Message-ID | <20220826013841.422b5a9f2e46dd8fa88e0b42@gmail.com> |
| In reply to | #167201 |
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" );
}
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-08-26 00:55 +0100 |
| Message-ID | <87a67ranej.fsf@bsb.me.uk> |
| In reply to | #167224 |
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.
[toc] | [prev] | [next] | [standalone]
| From | Anton Shepelev <anton.txt@g{oogle}mail.com> |
|---|---|
| Date | 2022-08-26 12:02 +0300 |
| Message-ID | <20220826120252.b8a994a2f425c1924488d6cc@g{oogle}mail.com> |
| In reply to | #167226 |
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]
[toc] | [prev] | [next] | [standalone]
Page 1 of 6 [1] 2 3 4 5 6 Next page →
Back to top | Article view | comp.lang.c
csiph-web