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 4 of 6 — ← Prev page 1 2 3 [4] 5 6 Next page →
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-22 09:15 -0700 |
| Message-ID | <febd215c-8541-4e3e-a101-be98bde7308an@googlegroups.com> |
| In reply to | #167094 |
On Monday, August 22, 2022 at 12:51:52 PM UTC-3, Bonita Montero wrote: > Use a proper language: > > #include <iostream> > #include <unordered_map> With unordered_map you are not taking advantage that strings are know at compile times. So I am sure a better performance/memory can be achieved.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2022-08-22 18:28 +0200 |
| Message-ID | <te0aqp$2n27h$1@dont-email.me> |
| In reply to | #167101 |
Am 22.08.2022 um 18:15 schrieb Thiago Adams: > On Monday, August 22, 2022 at 12:51:52 PM UTC-3, Bonita Montero wrote: >> Use a proper language: >> >> #include <iostream> >> #include <unordered_map> > > With unordered_map you are not taking advantage that > strings are know at compile times. I don't see where's the problem here. If I initialize the map static as I did the map is initialized thread-safe with double-checked locking when the function is called first. DCL is that fast that further checks if the map is already initialized carry nearly no weight. > So I am sure a better performance/memory can be achieved.
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-22 09:34 -0700 |
| Message-ID | <59e36b02-2c8a-4948-bfd8-34346e03b286n@googlegroups.com> |
| In reply to | #167104 |
On Monday, August 22, 2022 at 1:28:23 PM UTC-3, Bonita Montero wrote: > Am 22.08.2022 um 18:15 schrieb Thiago Adams: > > On Monday, August 22, 2022 at 12:51:52 PM UTC-3, Bonita Montero wrote: > >> Use a proper language: > >> > >> #include <iostream> > >> #include <unordered_map> > > > > With unordered_map you are not taking advantage that > > strings are know at compile times. > I don't see where's the problem here. If I initialize the map static > as I did the map is initialized thread-safe with double-checked locking > when the function is called first. DCL is that fast that further checks > if the map is already initialized carry nearly no weight. > > So I am sure a better performance/memory can be achieved. You need a compile time state machine analizer.. I am sure unordered_map will not do that. but compiler will do on switches.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2022-08-22 18:35 +0200 |
| Message-ID | <te0b8p$2n27h$2@dont-email.me> |
| In reply to | #167107 |
Am 22.08.2022 um 18:34 schrieb Thiago Adams: > On Monday, August 22, 2022 at 1:28:23 PM UTC-3, Bonita Montero wrote: >> Am 22.08.2022 um 18:15 schrieb Thiago Adams: >>> On Monday, August 22, 2022 at 12:51:52 PM UTC-3, Bonita Montero wrote: >>>> Use a proper language: >>>> >>>> #include <iostream> >>>> #include <unordered_map> >>> >>> With unordered_map you are not taking advantage that >>> strings are know at compile times. >> I don't see where's the problem here. If I initialize the map static >> as I did the map is initialized thread-safe with double-checked locking >> when the function is called first. DCL is that fast that further checks >> if the map is already initialized carry nearly no weight. >>> So I am sure a better performance/memory can be achieved. > > You need a compile time state machine analizer.. > I am sure unordered_map will not do that. > but compiler will do on switches. Whatever you want to try to do. With that number of keywords you'll be slower than with a hash map.
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-22 09:45 -0700 |
| Message-ID | <85faf079-8adf-4528-9010-54ac3d483664n@googlegroups.com> |
| In reply to | #167108 |
On Monday, August 22, 2022 at 1:35:50 PM UTC-3, Bonita Montero wrote: > Am 22.08.2022 um 18:34 schrieb Thiago Adams: > > On Monday, August 22, 2022 at 1:28:23 PM UTC-3, Bonita Montero wrote: > >> Am 22.08.2022 um 18:15 schrieb Thiago Adams: > >>> On Monday, August 22, 2022 at 12:51:52 PM UTC-3, Bonita Montero wrote: > >>>> Use a proper language: > >>>> > >>>> #include <iostream> > >>>> #include <unordered_map> > >>> > >>> With unordered_map you are not taking advantage that > >>> strings are know at compile times. > >> I don't see where's the problem here. If I initialize the map static > >> as I did the map is initialized thread-safe with double-checked locking > >> when the function is called first. DCL is that fast that further checks > >> if the map is already initialized carry nearly no weight. > >>> So I am sure a better performance/memory can be achieved. > > > > You need a compile time state machine analizer.. > > I am sure unordered_map will not do that. > > but compiler will do on switches. > Whatever you want to try to do. With that number > of keywords you'll be slower than with a hash map. If you want to try a benchmark with C and C++ here is the C code you need to be faster. :) https://godbolt.org/z/3v1xMPscG
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2022-08-22 18:51 +0200 |
| Message-ID | <te0c68$2n70a$1@dont-email.me> |
| In reply to | #167111 |
Am 22.08.2022 um 18:45 schrieb Thiago Adams: > On Monday, August 22, 2022 at 1:35:50 PM UTC-3, Bonita Montero wrote: >> Am 22.08.2022 um 18:34 schrieb Thiago Adams: >>> On Monday, August 22, 2022 at 1:28:23 PM UTC-3, Bonita Montero wrote: >>>> Am 22.08.2022 um 18:15 schrieb Thiago Adams: >>>>> On Monday, August 22, 2022 at 12:51:52 PM UTC-3, Bonita Montero wrote: >>>>>> Use a proper language: >>>>>> >>>>>> #include <iostream> >>>>>> #include <unordered_map> >>>>> >>>>> With unordered_map you are not taking advantage that >>>>> strings are know at compile times. >>>> I don't see where's the problem here. If I initialize the map static >>>> as I did the map is initialized thread-safe with double-checked locking >>>> when the function is called first. DCL is that fast that further checks >>>> if the map is already initialized carry nearly no weight. >>>>> So I am sure a better performance/memory can be achieved. >>> >>> You need a compile time state machine analizer.. >>> I am sure unordered_map will not do that. >>> but compiler will do on switches. >> Whatever you want to try to do. With that number >> of keywords you'll be slower than with a hash map. > > If you want to try a benchmark with C and C++ > here is the C code you need to be faster. :) > > https://godbolt.org/z/3v1xMPscG I don't need to benchmark that ugly code. A hash map is faster for sure. I extended by benchmark and I compared a linear search with N elements with a hash map, and the hash map is faster from 2 to N. Your code is simply ugly and error-prone.
[toc] | [prev] | [next] | [standalone]
| From | Anton Shepelev <anton.txt@g{oogle}mail.com> |
|---|---|
| Date | 2022-08-23 17:53 +0300 |
| Message-ID | <20220823175333.faf15d03b47ee964cd0e1ce1@g{oogle}mail.com> |
| In reply to | #167111 |
Thiago Adams: > here is the C code you need to be faster. :) Not "faster than."? You don't like to end sentences with prepostions? -- () ascii ribbon campaign - against html e-mail /\ http://preview.tinyurl.com/qcy6mjc [archived]
[toc] | [prev] | [next] | [standalone]
| From | bart c <bart4858@gmail.com> |
|---|---|
| Date | 2022-08-22 10:20 -0700 |
| Message-ID | <db9c05cf-f055-48aa-8074-d9f58d8a0693n@googlegroups.com> |
| In reply to | #167089 |
On Monday, 22 August 2022 at 15:17:29 UTC+1, Thiago Adams wrote:
> 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},
...
> { "volatile", 73},
> { "while", 74},
> };
I suspect other things are going on. Presumably you are looking up an identifier encountered in source code to see if it's a keyword, but if not, another lookup is needed to see if it matches a user-identifier in a symbol table.
My approach usually involves a hash table (the symbol table), containing both keywords and user identifiers. Each entry contains information on whether it is a keyword name (and its token value), or user identifier.
To start, your list is used to populate the empty hash table.
You don't need a perfect hash for this. Typically, most of the time you only end up doing one strcmp to confirm the right selection. If significantly more than one on average, then you have too many clashes: the table is getting full, or you have a poor hash function.
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-22 10:53 -0700 |
| Message-ID | <55c55211-6e7e-4aa7-a9e6-3e7b11bab898n@googlegroups.com> |
| In reply to | #167114 |
On Monday, August 22, 2022 at 2:20:09 PM UTC-3, bart c wrote:
> On Monday, 22 August 2022 at 15:17:29 UTC+1, Thiago Adams wrote:
> > 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},
> ...
> > { "volatile", 73},
> > { "while", 74},
> > };
> I suspect other things are going on. Presumably you are looking up an identifier encountered in source code to see if it's a keyword, but if not, another lookup is needed to see if it matches a user-identifier in a symbol table.
>
> My approach usually involves a hash table (the symbol table), containing both keywords and user identifiers. Each entry contains information on whether it is a keyword name (and its token value), or user identifier.
Interesting, but not sure if this make code more complicated not having
a "keyword" token for sure without check a symbol table.
[toc] | [prev] | [next] | [standalone]
| From | antispam@math.uni.wroc.pl |
|---|---|
| Date | 2022-08-22 23:31 +0000 |
| Message-ID | <te13ks$1mtg$1@gioia.aioe.org> |
| In reply to | #167116 |
Thiago Adams <thiago.adams@gmail.com> wrote:
> On Monday, August 22, 2022 at 2:20:09 PM UTC-3, bart c wrote:
> > On Monday, 22 August 2022 at 15:17:29 UTC+1, Thiago Adams wrote:
> > > 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},
> > ...
> > > { "volatile", 73},
> > > { "while", 74},
> > > };
> > I suspect other things are going on. Presumably you are looking up an identifier encountered in source code to see if it's a keyword, but if not, another lookup is needed to see if it matches a user-identifier in a symbol table.
> >
> > My approach usually involves a hash table (the symbol table), containing both keywords and user identifiers. Each entry contains information on whether it is a keyword name (and its token value), or user identifier.
>
> Interesting, but not sure if this make code more complicated not having
> a "keyword" token for sure without check a symbol table.
In compiler you almost surely need symbol table. And most natural
place to do symbol table lookup is in lexical analyser. In fact,
if you want simple code it makes sense to put almost everthing in
symbol table. For example when you see "+" symbol table tells you
that this special syntactic property, namely precedence (priority).
Logically you could even put numbers in symbol table, but I see
no gain from doing this. But for other things you scanner will
be simpler: once you know which characters form your token it
is single table lookup to get all semantic info.
BTW: All compiler text that I have seen introduce IMO
unnecessary distinctions from very beginning. Namely,
for parsing what matters are syntactic properties,
kewords without syntactic role are no different than
variables or functions. After parsing distinction between
variables, functions operators and keywords depend
on purpose. Naive compiler may simply "generate
semantics". Of couse, declarations are somewhat
special because they mainly change compiler state. But
other things also may change compiler state and
declarations may generate code. Particularly unhelpful
is distinction between operators and functions.
In most aspect they are the same and real difference
is in what is expanded inline and what is handled by
function calls. Anyway sorry for rant, but take
int account that handling things that look different
by single machanism usually leads to simpler compiler.
--
Waldek Hebisch
[toc] | [prev] | [next] | [standalone]
| From | bart c <bart4858@gmail.com> |
|---|---|
| Date | 2022-08-22 17:04 -0700 |
| Message-ID | <cf695e1c-5e69-498f-a047-7dfb64fae2f2n@googlegroups.com> |
| In reply to | #167129 |
On Tuesday, 23 August 2022 at 00:31:54 UTC+1, anti... wrote:
> Thiago Adams wrote:
> > On Monday, August 22, 2022 at 2:20:09 PM UTC-3, bart c wrote:
> > > On Monday, 22 August 2022 at 15:17:29 UTC+1, Thiago Adams wrote:
> > > > 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},
> > > ...
> > > > { "volatile", 73},
> > > > { "while", 74},
> > > > };
> > > I suspect other things are going on. Presumably you are looking up an identifier encountered in source code to see if it's a keyword, but if not, another lookup is needed to see if it matches a user-identifier in a symbol table.
> > >
> > > My approach usually involves a hash table (the symbol table), containing both keywords and user identifiers. Each entry contains information on whether it is a keyword name (and its token value), or user identifier.
> >
> > Interesting, but not sure if this make code more complicated not having
> > a "keyword" token for sure without check a symbol table.
> In compiler you almost surely need symbol table. And most natural
> place to do symbol table lookup is in lexical analyser. In fact,
> if you want simple code it makes sense to put almost everthing in
> symbol table. For example when you see "+" symbol table tells you
> that this special syntactic property, namely precedence (priority).
I wouldn't go as far as putting punctuation into a symbol table. Once you've identified the boundaries of the token, you're pretty much already there in identifying what it is. (Perhaps with user-defined symbols like '+++' it might start to be more worthwhile, as the compiler won't already know what they are.)
> Logically you could even put numbers in symbol table, but I see
> no gain from doing this.
That's what I thought too. But this may have merit, if you want to collate all instances of the same literal, especially with string literals and to a lesser extent with float literals (which usually can't be immediate values, but if 34.8 occurs 50 times, you don't want 50 copies of it).
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <tr.17687@z991.linuxsc.com> |
|---|---|
| Date | 2022-08-23 09:50 -0700 |
| Message-ID | <868rneuco0.fsf@linuxsc.com> |
| In reply to | #167089 |
Thiago Adams <thiago.adams@gmail.com> writes:
> 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},
> [...]
> { "volatile", 73},
> { "while", 74},
> };
There is no way to give a good answer to this question without more
information, as for example how often does a query result in a miss
rather than a hit, and what is the expected distribution of queries
that result in a hit. And there are other factors that could play a
major role in making good choices for this.
Also, it seems likely that a better way to approach this problem is
to change the callers (or at least some of them) so that they
provide more information than just a pointer to a string. For
example, if this is to be part of a scanner, then it should be
possible without too much difficult to compute a hash as the
identifier is scanned, and also a length. Both of those could
help speed up the keyword lookup code.
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-23 10:07 -0700 |
| Message-ID | <93c78669-e681-48bf-b421-ff199e5fcf7an@googlegroups.com> |
| In reply to | #167154 |
On Tuesday, August 23, 2022 at 1:50:53 PM UTC-3, Tim Rentsch wrote:
> Thiago Adams <thiago...@gmail.com> writes:
>
> > 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},
> > [...]
> > { "volatile", 73},
> > { "while", 74},
> > };
> There is no way to give a good answer to this question without more
> information, as for example how often does a query result in a miss
> rather than a hit, and what is the expected distribution of queries
> that result in a hit. And there are other factors that could play a
> major role in making good choices for this.
>
> Also, it seems likely that a better way to approach this problem is
> to change the callers (or at least some of them) so that they
> provide more information than just a pointer to a string. For
> example, if this is to be part of a scanner, then it should be
> possible without too much difficult to compute a hash as the
> identifier is scanned, and also a length. Both of those could
> help speed up the keyword lookup code.
Imagine the input is a C identifier.
Things like "void" "int" "struct" "enum" are common keywords , very frequent.
Things like "i" "j" "k" are common not keywords.
[toc] | [prev] | [next] | [standalone]
| From | bart c <bart4858@gmail.com> |
|---|---|
| Date | 2022-08-23 11:28 -0700 |
| Message-ID | <d4424f70-b00d-4102-89b3-6e151cc54aa3n@googlegroups.com> |
| In reply to | #167156 |
On Tuesday, 23 August 2022 at 18:08:07 UTC+1, Thiago Adams wrote:
> On Tuesday, August 23, 2022 at 1:50:53 PM UTC-3, Tim Rentsch wrote:
> > Thiago Adams writes:
> >
> > > 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},
> > > [...]
> > > { "volatile", 73},
> > > { "while", 74},
> > > };
> > There is no way to give a good answer to this question without more
> > information, as for example how often does a query result in a miss
> > rather than a hit, and what is the expected distribution of queries
> > that result in a hit. And there are other factors that could play a
> > major role in making good choices for this.
> >
> > Also, it seems likely that a better way to approach this problem is
> > to change the callers (or at least some of them) so that they
> > provide more information than just a pointer to a string. For
> > example, if this is to be part of a scanner, then it should be
> > possible without too much difficult to compute a hash as the
> > identifier is scanned, and also a length. Both of those could
> > help speed up the keyword lookup code.
> Imagine the input is a C identifier.
> Things like "void" "int" "struct" "enum" are common keywords , very frequent.
> Things like "i" "j" "k" are common not keywords.
If input is C source code, then some brief tests suggest that 30-40% of identifiers are keywords, the rest are used-defined.
For the test input sqlite3.c + shell.c + shell.h, 30% were keywords. And the most common were (counts shown):
46066 define
10005 if
09531 int
03522 endif
03468 return
03053 char
02924 void
02802 else
02366 const
01491 static
01461 struct
01369 typedef
....
What the percentage means is, if you have an alphanumeric token but don't know if it's a keyword or not, then if you first check for a keyword, that effort will be wasted 2/3 of the time; you need to do a keyword check AND a normal lookup.
On the other hand, 1/3 of the time, you will save having to do a conventional lookup.
If a keyword check (that is, determine which keyword, if any, not just yes or no as one of your posts did) is much faster than a normal lookup, this might have a small net benefit.
Although I can't myself see the extra complication as being worthwhile, this might make your tokenising logic simpler. Since it's not going to make it much slower either, provided you don't just do a linear search.
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <Keith.S.Thompson+u@gmail.com> |
|---|---|
| Date | 2022-08-23 12:17 -0700 |
| Message-ID | <87wnayydld.fsf@nosuchdomain.example.com> |
| In reply to | #167158 |
bart c <bart4858@gmail.com> writes:
[...]
> If input is C source code, then some brief tests suggest that 30-40% of identifiers are keywords, the rest are used-defined.
>
> For the test input sqlite3.c + shell.c + shell.h, 30% were keywords. And the most common were (counts shown):
>
> 46066 define
> 10005 if
> 09531 int
> 03522 endif
> 03468 return
> 03053 char
> 02924 void
> 02802 else
> 02366 const
> 01491 static
> 01461 struct
> 01369 typedef
> ....
"define" and "endif" would be recognized by the preprocessor, which
doesn't know about "int", "return", et al. After preprocessing,
"define" and "endif" don't have to be recognized.
It would be difficult to have a correct C implementation in which
"define" and "int" both need to be recognized by the same code.
And that's a *lot* of "define"s. It sounds like the code you're
looking at is not typical. Your numbers don't match what I see
in the latest sqlite3 sources.
--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-23 13:16 -0700 |
| Message-ID | <fab399cf-9141-4f71-9a07-2743ede6f16fn@googlegroups.com> |
| In reply to | #167159 |
On Tuesday, August 23, 2022 at 4:17:18 PM UTC-3, Keith Thompson wrote: > bart c <bart...@gmail.com> writes: > [...] > > If input is C source code, then some brief tests suggest that 30-40% of identifiers are keywords, the rest are used-defined. > > > > For the test input sqlite3.c + shell.c + shell.h, 30% were keywords. And the most common were (counts shown): > > > > 46066 define > > 10005 if > > 09531 int > > 03522 endif > > 03468 return > > 03053 char > > 02924 void > > 02802 else > > 02366 const > > 01491 static > > 01461 struct > > 01369 typedef > > .... > "define" and "endif" would be recognized by the preprocessor, which > doesn't know about "int", "return", et al. After preprocessing, > "define" and "endif" don't have to be recognized. > > It would be difficult to have a correct C implementation in which > "define" and "int" both need to be recognized by the same code. > > And that's a *lot* of "define"s. It sounds like the code you're > looking at is not typical. Your numbers don't match what I see > in the latest sqlite3 sources. Having the keywords out from preprocessor has the advantage of not checking keywords on the inactive preprocessor blocks. My transpiler promotes the "surviving" identifiers to keywords after preprocessing on the first usage. pp-numbers are similar.. that are checked after preprocessing except the ones that are in #if expression , :) that need to be evaluated at preprocessor phase. We also can see that bad ppnumber survives if not used in # if expressions. the other tokens like punctuators strings..are the same (for me) for preprocessor or not. define endif etc are used as identifers and checked with strcmp.
[toc] | [prev] | [next] | [standalone]
| From | bart c <bart4858@gmail.com> |
|---|---|
| Date | 2022-08-23 13:18 -0700 |
| Message-ID | <376a7c64-113a-46d3-bc81-664a6b7dd32cn@googlegroups.com> |
| In reply to | #167159 |
On Tuesday, 23 August 2022 at 20:17:18 UTC+1, Keith Thompson wrote: > bart c <bart...@gmail.com> writes: > [...] > > If input is C source code, then some brief tests suggest that 30-40% of identifiers are keywords, the rest are used-defined. > > > > For the test input sqlite3.c + shell.c + shell.h, 30% were keywords. And the most common were (counts shown): > > > > 46066 define > > 10005 if > > 09531 int > > 03522 endif > > 03468 return > > 03053 char > > 02924 void > > 02802 else > > 02366 const > > 01491 static > > 01461 struct > > 01369 typedef > > .... > "define" and "endif" would be recognized by the preprocessor, which > doesn't know about "int", "return", et al. After preprocessing, > "define" and "endif" don't have to be recognized. I have a 3-level lex function (lex() calls mlex() which calls lexreadtoken()); the middle one takes of of macro expansion; cpp directives are recognised in there somewhere so don't make it through to the top function. I don't have a completely separate preprocess stage; that's done as it goes. For the purpose of my test, keywords are detected a bit earlier than normal (the compiler still seems able to do its job). > And that's a *lot* of "define"s. It sounds like the code you're > looking at is not typical. Your numbers don't match what I see > in the latest sqlite3 sources. Yeah, that looked dodgy. I don't know what's going on there. If I compile only sqlite3.c, then I get more reasonable looking figures: 14010 define 08728 if 08543 int 03115 endif 03111 return 02658 void 02291 else Note that 10,000 of those defines are inside my windows.h. Also note that the same 'if' keyword is used for "'#if". This is specific to normal C however. We don't know exactly what the OP is doing, or what his inputs will be, whether they are already preprocessed or not.
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-23 13:23 -0700 |
| Message-ID | <e671aa49-46cb-44b7-95d3-5ba5d84f2be6n@googlegroups.com> |
| In reply to | #167161 |
On Tuesday, August 23, 2022 at 5:18:26 PM UTC-3, bart c wrote: > On Tuesday, 23 August 2022 at 20:17:18 UTC+1, Keith Thompson wrote: > > bart c <bart...@gmail.com> writes: > > [...] > > > If input is C source code, then some brief tests suggest that 30-40% of identifiers are keywords, the rest are used-defined. > > > > > > For the test input sqlite3.c + shell.c + shell.h, 30% were keywords. And the most common were (counts shown): > > > > > > 46066 define > > > 10005 if > > > 09531 int > > > 03522 endif > > > 03468 return > > > 03053 char > > > 02924 void > > > 02802 else > > > 02366 const > > > 01491 static > > > 01461 struct > > > 01369 typedef > > > .... > > "define" and "endif" would be recognized by the preprocessor, which > > doesn't know about "int", "return", et al. After preprocessing, > > "define" and "endif" don't have to be recognized. > I have a 3-level lex function (lex() calls mlex() which calls lexreadtoken()); the middle one takes of of macro expansion; cpp directives are recognised in there somewhere so don't make it through to the top function. > > I don't have a completely separate preprocess stage; that's done as it goes. > > For the purpose of my test, keywords are detected a bit earlier than normal (the compiler still seems able to do its job). > > And that's a *lot* of "define"s. It sounds like the code you're > > looking at is not typical. Your numbers don't match what I see > > in the latest sqlite3 sources. > Yeah, that looked dodgy. I don't know what's going on there. If I compile only sqlite3.c, then I get more reasonable looking figures: > > 14010 define > 08728 if > 08543 int > 03115 endif > 03111 return > 02658 void > 02291 else > > Note that 10,000 of those defines are inside my windows.h. Also note that the same 'if' keyword is used for "'#if". > > This is specific to normal C however. We don't know exactly what the OP is doing, or what his inputs will be, whether they are already preprocessed or not. After preprocessor , at first usage, the tokens of type "identifier" are checked and promoted to keywords (if there are keywords ).
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <Keith.S.Thompson+u@gmail.com> |
|---|---|
| Date | 2022-08-23 13:40 -0700 |
| Message-ID | <87sflmy9qx.fsf@nosuchdomain.example.com> |
| In reply to | #167161 |
bart c <bart4858@gmail.com> writes:
> On Tuesday, 23 August 2022 at 20:17:18 UTC+1, Keith Thompson wrote:
[...]
>> And that's a *lot* of "define"s. It sounds like the code you're
>> looking at is not typical. Your numbers don't match what I see
>> in the latest sqlite3 sources.
>
> Yeah, that looked dodgy. I don't know what's going on there. If I
> compile only sqlite3.c, then I get more reasonable looking figures:
>
> 14010 define
> 08728 if
> 08543 int
> 03115 endif
> 03111 return
> 02658 void
> 02291 else
>
> Note that 10,000 of those defines are inside my windows.h. Also note
>that the same 'if' keyword is used for "'#if".
>
> This is specific to normal C however. We don't know exactly what the
> OP is doing, or what his inputs will be, whether they are already
> preprocessed or not.
Ah, so that's 14010 occurrences of "define" after preprocessing.
Except that after preprocessing there shouldn't be *any* occurrences of
"define" that result from macro definitions ("define" could be used as
an ordinary identifier). And if you're distinguishing between keywords
like "int" and identifiers like "foo" before translation phase 7, there
are likely to be some programs that you'll handle incorrectly. You
certainly don't have to implement the 8 translation phases as distinct
passes, but if you want a conforming implementation you must do
something that acts that way.
This:
#if int
#error "Error 1"
#endif
#if foo
#error "Error 2"
#endif
shouldn't produce any error messages.
The point is that if you're processing C source code and recognizing
whether tokens that look like identifiers are keywords or not, it
doesn't make sense to have "define" and "int" in the same table.
--
Keith Thompson (The_Other_Keith) Keith.S.Thompson+u@gmail.com
Working, but not speaking, for Philips
void Void(void) { Void(); } /* The recursive call of the void */
[toc] | [prev] | [next] | [standalone]
| From | bart c <bart4858@gmail.com> |
|---|---|
| Date | 2022-08-23 16:26 -0700 |
| Message-ID | <03619802-f8c4-41d6-9575-d96f02a37ae5n@googlegroups.com> |
| In reply to | #167163 |
On Tuesday, 23 August 2022 at 21:40:25 UTC+1, Keith Thompson wrote: > bart c <bart...@gmail.com> writes: > > On Tuesday, 23 August 2022 at 20:17:18 UTC+1, Keith Thompson wrote: > [...] > >> And that's a *lot* of "define"s. It sounds like the code you're > >> looking at is not typical. Your numbers don't match what I see > >> in the latest sqlite3 sources. > > > > Yeah, that looked dodgy. I don't know what's going on there. If I > > compile only sqlite3.c, then I get more reasonable looking figures: > > > > 14010 define > > 08728 if > > 08543 int > > 03115 endif > > 03111 return > > 02658 void > > 02291 else > > > > Note that 10,000 of those defines are inside my windows.h. Also note > >that the same 'if' keyword is used for "'#if". > > > > This is specific to normal C however. We don't know exactly what the > > OP is doing, or what his inputs will be, whether they are already > > preprocessed or not. > Ah, so that's 14010 occurrences of "define" after preprocessing. This is getting dragged down by mention of preprocessing. In order to test the effects of a linear search, I added that at the lowest level of the tokeniser, which normally only does an incomplete lookup - determine the location in a symbol table, and only commit to an actual reserved word later on. This can mean that all instances of "define" are counted as reserved words, which would include 4 from this code: #define A 1 #define B(x) define##x int define; when it should really be only two. And under normal circumstances, all 4 (2 reserved word 'define's, one PP token 'define', and one user identifier 'define') share the same symbol table entry, via some magic. So the counts may be a little skewed, but remember the purpose was a quick and dirty test to see how much a linear search can affect performances. (Funnily enough, the code still above compiles correctly. I tested it on two other non-C compilers before, and those had ordinary lexers; it was much easier to see where the put that extra code!) > The point is that if you're processing C source code and recognizing > whether tokens that look like identifiers are keywords or not, it > doesn't make sense to have "define" and "int" in the same table. Well, they *are* in the same table, and all three kinds of "define" share the same slot too. Or does C stipulate how people should organise their symbol tables?
[toc] | [prev] | [next] | [standalone]
Page 4 of 6 — ← Prev page 1 2 3 [4] 5 6 Next page →
Back to top | Article view | comp.lang.c
csiph-web