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 5 of 6 — ← Prev page 1 2 3 4 [5] 6 Next page →
| From | Keith Thompson <Keith.S.Thompson+u@gmail.com> |
|---|---|
| Date | 2022-08-23 16:50 -0700 |
| Message-ID | <87lerey0xx.fsf@nosuchdomain.example.com> |
| In reply to | #167168 |
bart c <bart4858@gmail.com> writes:
> 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.
I suggest that 14,000 spurious occurrences of "define" may have skewed
your results.
[...]
>> 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?
Of course it doesn't. But I don't know why you'd *want* all three kinds
of "define" 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 17:26 -0700 |
| Message-ID | <7f0ce303-cb16-4fd7-8afe-417a277fea0bn@googlegroups.com> |
| In reply to | #167170 |
On Wednesday, 24 August 2022 at 00:50:33 UTC+1, Keith Thompson wrote: > bart c <bart...@gmail.com> writes: > > 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. > I suggest that 14,000 spurious occurrences of "define" may have skewed > your results. Here are the two main files: https://raw.githubusercontent.com/sal55/langs/master/sqlite3.c https://github.com/sal55/langs/blob/master/windows.h I believe the first has some 4000 defines, and (my) windows.h has about 10000. (There will be a few in my standard headers.) I haven't counted them myself, but the 14,000 figure seems plausible. > [...] > >> 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? > Of course it doesn't. But I don't know why you'd *want* all three kinds > of "define" in the same table. I'm not the kind to go for umpteen different symbol tables in a compiler, perhaps one for every scope level, and having to do more than one looking for any one instance of a name. There is one global hash table which contains generic versions of all alphanumeric names (keyword or user identifiers or, for C, PP tokens) that occur throughout a program. The ST lookup that occurs early on is dumb; it knows little about the language, and either returns a generic ST entry for each unique name, or it creates one. Levels of scope, namespaces, multiple instances of the same name occurring in different contexts, etc are superimposed later.
[toc] | [prev] | [next] | [standalone]
| From | antispam@math.uni.wroc.pl |
|---|---|
| Date | 2022-08-23 23:54 +0000 |
| Message-ID | <te3pcd$q5o$1@gioia.aioe.org> |
| In reply to | #167163 |
Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
> 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.
Bart wrote that "define" came from "windows.h", so his input is
before preprocessing.
> 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.
Why not? Of course logically lookups for preprocessor keywords
are different from normal lookups, but there is no law that
prevent storing two logical hash tables in single physical
hash table. In particular, info about preprocessor keywords
is likely to be quite small, so there is good chance that
you can put it in place that would be otherwise wasted by
padding.
If you want fast compiler it makes sense to do symbol
table lookup once, that is combine prepocessor with compiler.
In preprocessing stage you need to look up each identifier to
check if it is a macro, when it is not a macro you may deliver
its compilation meaninig. Details needed for correct handling
of C are likely to be tricky and I do not know if Bart did
this correctly. But this is clearly doable and likely to give
large speed advantage.
Note that after macros and normal C symbols are in single
table what remains is handful of preprocessor keywords.
Since they are so frequent and exclusive of normal identifiers
special purpose table may give some speed boost. OTOH
in combined table preprocessor keywords will be entered
first, so with high probablity single lookup will work.
In other words, single combined table is likely to behave
as perfect hash for the purpose of lookup for proprocessor
keywords. It looks tricky to come with faster alternative...
--
Waldek Hebisch
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <Keith.S.Thompson+u@gmail.com> |
|---|---|
| Date | 2022-08-23 17:16 -0700 |
| Message-ID | <87h722xzqp.fsf@nosuchdomain.example.com> |
| In reply to | #167171 |
antispam@math.uni.wroc.pl writes:
> Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
>> 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.
>
> Bart wrote that "define" came from "windows.h", so his input is
> before preprocessing.
Well, it seems to be in the middle of preprocessing. Before
preprocessing, you'd just have `#include "windows.h"` and none of its
contents. After preprocessing, all the `#define` directives should be
gone and all macros expanded. (#include, #define, and macro expansion
are all done on translation phase 4.)
Of course Bart can do whatever he likes as long as the final result is
as if all 8 phases are invoked *or* he doesn't care about full
conformance.
>> 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.
>
> Why not? Of course logically lookups for preprocessor keywords
> are different from normal lookups, but there is no law that
> prevent storing two logical hash tables in single physical
> hash table. In particular, info about preprocessor keywords
> is likely to be quite small, so there is good chance that
> you can put it in place that would be otherwise wasted by
> padding.
>
> If you want fast compiler it makes sense to do symbol
> table lookup once, that is combine prepocessor with compiler.
> In preprocessing stage you need to look up each identifier to
> check if it is a macro, when it is not a macro you may deliver
> its compilation meaninig. Details needed for correct handling
> of C are likely to be tricky and I do not know if Bart did
> this correctly. But this is clearly doable and likely to give
> large speed advantage.
>
> Note that after macros and normal C symbols are in single
> table what remains is handful of preprocessor keywords.
> Since they are so frequent and exclusive of normal identifiers
> special purpose table may give some speed boost. OTOH
> in combined table preprocessor keywords will be entered
> first, so with high probablity single lookup will work.
> In other words, single combined table is likely to behave
> as perfect hash for the purpose of lookup for proprocessor
> keywords. It looks tricky to come with faster alternative...
I'm not convinced, but if it works that's fine.
--
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 | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2022-08-24 09:43 +0200 |
| Message-ID | <te4kqu$390s4$1@dont-email.me> |
| In reply to | #167171 |
On 24/08/2022 01:54, antispam@math.uni.wroc.pl wrote: > Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote: >> 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. > > Bart wrote that "define" came from "windows.h", so his input is > before preprocessing. > >> 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. > > Why not? Of course logically lookups for preprocessor keywords > are different from normal lookups, but there is no law that > prevent storing two logical hash tables in single physical > hash table. In particular, info about preprocessor keywords > is likely to be quite small, so there is good chance that > you can put it in place that would be otherwise wasted by > padding. > > If you want fast compiler it makes sense to do symbol > table lookup once, that is combine prepocessor with compiler. > In preprocessing stage you need to look up each identifier to > check if it is a macro, when it is not a macro you may deliver > its compilation meaninig. Details needed for correct handling > of C are likely to be tricky and I do not know if Bart did > this correctly. But this is clearly doable and likely to give > large speed advantage. > > Note that after macros and normal C symbols are in single > table what remains is handful of preprocessor keywords. > Since they are so frequent and exclusive of normal identifiers > special purpose table may give some speed boost. OTOH > in combined table preprocessor keywords will be entered > first, so with high probablity single lookup will work. > In other words, single combined table is likely to behave > as perfect hash for the purpose of lookup for proprocessor > keywords. It looks tricky to come with faster alternative... > You /could/ put your pre-processor symbols (preprocessor keywords and macro identifiers) in the same table as your "main-phase" symbols (language keywords and identifiers). But you'd need to distinguish the symbol types in the tables - and you need to look up tokens again after preprocessing anyway. So I can't see how you could gain anything from combining them. Consider this translation unit : #define foo in #define bar t #define foobar in ## t foobar foo, bar, define; This has the same result as "int foo, bar, define;". But there is no string "int" in the input text, and the strings in the input change meaning radically from before and after pre-processing. (I apologise for being a bit lose on terminology here, especially processing phases - I hope I am being clear enough despite that.)
[toc] | [prev] | [next] | [standalone]
| From | bart c <bart4858@gmail.com> |
|---|---|
| Date | 2022-08-24 04:03 -0700 |
| Message-ID | <cb1bf2f1-0b9d-407c-b239-14eb3bbe8a98n@googlegroups.com> |
| In reply to | #167178 |
On Wednesday, 24 August 2022 at 08:43:41 UTC+1, David Brown wrote:
> On 24/08/2022 01:54, anti...@ wrote:
> > If you want fast compiler it makes sense to do symbol
> > table lookup once, that is combine prepocessor with compiler.
> > In preprocessing stage you need to look up each identifier to
> > check if it is a macro, when it is not a macro you may deliver
> > its compilation meaninig. Details needed for correct handling
> > of C are likely to be tricky and I do not know if Bart did
> > this correctly. But this is clearly doable and likely to give
> > large speed advantage.
> >
> > Note that after macros and normal C symbols are in single
> > table what remains is handful of preprocessor keywords.
> > Since they are so frequent and exclusive of normal identifiers
> > special purpose table may give some speed boost. OTOH
> > in combined table preprocessor keywords will be entered
> > first, so with high probablity single lookup will work.
> > In other words, single combined table is likely to behave
> > as perfect hash for the purpose of lookup for proprocessor
> > keywords. It looks tricky to come with faster alternative...
> >
> You /could/ put your pre-processor symbols (preprocessor keywords and
> macro identifiers) in the same table as your "main-phase" symbols
> (language keywords and identifiers). But you'd need to distinguish the
> symbol types in the tables - and you need to look up tokens again after
> preprocessing anyway. So I can't see how you could gain anything from
> combining them.
>
> Consider this translation unit :
>
>
> #define foo in
> #define bar t
> #define foobar in ## t
>
> foobar foo, bar, define;
>
>
> This has the same result as "int foo, bar, define;". But there is no
> string "int" in the input text, and the strings in the input change
> meaning radically from before and after pre-processing.
Your example includes these low-level tokens: 'define foo in bar t foobar'. The token-pasting synthesises a new token 'int' which also needs looking up, although that particular token is an existing keywords so already exists.
If I put your example into my compiler, it produces this main structured symbol table (keeping my fingers crossed that googlegroups shows it as fixed pitch, unlike what I'm looking at right now).
Global Symbol Table
:t---------------------------moduleid....[- M1 ]===($prog) none
----:in----------------------staticid....[Exp ]====(t) int static
----:t-----------------------staticid....[Exp ]====(t) int static
----:define------------------staticid....[Exp ]====(t) int static
This is actually superimposed (via various links between entries) onto one global
flat symbol table, like the following. This normally displays only user-defined names,
but I've got it to show built-in type names and CPP directives as well.
Indented entries are duplicate instances of any name, added via a linked list to the
generic version:
Global Flat Symbol Table:
689 0320D8C0 : int ktypespecsym nullid
979 032169C0 : foobar namesym macroid
3596 03268640 : t namesym nullid
---- 03B3E720 t namesym staticid 03268640(From t)
---- 03B3E440 t namesym moduleid 03B3E720(From $prog)
3908 03272240 : long ktypespecsym nullid
6089 032B64C0 : MESSAGE ksourcedirsym nullid
8420 032FF240 : pragma ksourcedirsym nullid
11293 03358EC0 : bar namesym macroid
13706 033A4540 : pause ksourcedirsym nullid
16809 03511540 : message ksourcedirsym nullid
17215 0351E040 : double ktypespecsym nullid
27532 036606C0 : line ksourcedirsym nullid
31476 036DBAC0 : signed ktypespecsym nullid
34091 037426C0 : unsigned ktypespecsym nullid
34684 03754F40 : elif ksourcedirsym nullid
35604 03771B40 : float ktypespecsym nullid
38404 037C9340 : short ktypespecsym nullid
38856 037D7540 : error ksourcedirsym nullid
39813 037F53C0 : define ksourcedirsym nullid
---- 03B3E7A0 define namesym staticid 037F53C0(From t)
41844 03834B40 : warning ksourcedirsym nullid
42984 03858540 : ifdef ksourcedirsym nullid
43135 0385D0C0 : _Complex ktypespecsym nullid
43832 03872D40 : endif ksourcedirsym nullid
45610 038AA640 : foo namesym macroid
48332 038FF740 : ifndef ksourcedirsym nullid
50296 03950DC0 : include ksourcedirsym nullid
51684 0397C3C0 : undef ksourcedirsym nullid
52235 0398D740 : in namesym nullid
---- 03B3E690 in namesym staticid 0398D740(From t)
53041 039A6A40 : showmacro ksourcedirsym nullid
56050 03A04AC0 : $prog namesym nullid
---- 03B3E380 $prog namesym programid 03A04AC0(From -)
56330 03A0D6C0 : char ktypespecsym nullid
56414 03A100C0 : debugon ksourcedirsym nullid
59220 03A67BC0 : debugoff ksourcedirsym nullid
62951 03ADC540 : _Bool ktypespecsym nullid
64700 03B12FC0 : void ktypespecsym nullid
It shows that there are two versions of 'define', but only one version of 'int'.
('t' is also the name of this module, t.c).
Built-in keywords exist at the 'root' entry of each unique symbol name.
User-defined names (like 3 different definitions of 'abc' across a module), start with a generic 'abc' plus 3 specific ones linked to that. Sometimes the generic name is also an allowed keyword like 'define'.
User-define macro names however are stored as the root symbol.
If someone does '#define int abc', then it hides the type 'int' with the macro 'int'.
[toc] | [prev] | [next] | [standalone]
| From | antispam@math.uni.wroc.pl |
|---|---|
| Date | 2022-08-24 14:15 +0000 |
| Message-ID | <te5bpc$187$1@gioia.aioe.org> |
| In reply to | #167178 |
David Brown <david.brown@hesbynett.no> wrote:
> On 24/08/2022 01:54, antispam@math.uni.wroc.pl wrote:
> > Keith Thompson <Keith.S.Thompson+u@gmail.com> wrote:
> >> 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.
> >
> > Bart wrote that "define" came from "windows.h", so his input is
> > before preprocessing.
> >
> >> 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.
> >
> > Why not? Of course logically lookups for preprocessor keywords
> > are different from normal lookups, but there is no law that
> > prevent storing two logical hash tables in single physical
> > hash table. In particular, info about preprocessor keywords
> > is likely to be quite small, so there is good chance that
> > you can put it in place that would be otherwise wasted by
> > padding.
> >
> > If you want fast compiler it makes sense to do symbol
> > table lookup once, that is combine prepocessor with compiler.
> > In preprocessing stage you need to look up each identifier to
> > check if it is a macro, when it is not a macro you may deliver
> > its compilation meaninig. Details needed for correct handling
> > of C are likely to be tricky and I do not know if Bart did
> > this correctly. But this is clearly doable and likely to give
> > large speed advantage.
> >
> > Note that after macros and normal C symbols are in single
> > table what remains is handful of preprocessor keywords.
> > Since they are so frequent and exclusive of normal identifiers
> > special purpose table may give some speed boost. OTOH
> > in combined table preprocessor keywords will be entered
> > first, so with high probablity single lookup will work.
> > In other words, single combined table is likely to behave
> > as perfect hash for the purpose of lookup for proprocessor
> > keywords. It looks tricky to come with faster alternative...
> >
>
> You /could/ put your pre-processor symbols (preprocessor keywords and
> macro identifiers) in the same table as your "main-phase" symbols
> (language keywords and identifiers). But you'd need to distinguish the
> symbol types in the tables - and you need to look up tokens again after
> preprocessing anyway. So I can't see how you could gain anything from
> combining them.
>
> Consider this translation unit :
>
>
> #define foo in
> #define bar t
> #define foobar in ## t
>
> foobar foo, bar, define;
>
>
> This has the same result as "int foo, bar, define;". But there is no
> string "int" in the input text, and the strings in the input change
> meaning radically from before and after pre-processing.
This is not tricky at all. When scanner sees 'foobar' it will do
symbol table lookup. Symbol table contains info that it is a macro
so scanner looks at replacement list. Replacement list contains
symbol table entries for in and t (so no need for lookup). It
also contains marker for pasting. So scanner takes names, creates
pasted name (that is 'int') and performs lookup on this name
getting symbol table entry for 'int' with its predefiend meaning.
Next scanner looks at 'foo' gets it symbol table entry which
again is a macro, from replacement list gets symbol table entry
for 'in' which is not a macro so it get used. Similarly
for 'bar'. Concerning 'define', in first 3 lines scanner
sees '#' so only takes 'preprocessor keyword' part from
symbol table. Final 'define' is not after appropriate '#'
so scanner only looks at macro and C identifier meanings.
Note that pasted tookens are looked up once per expansion,
this is needed for correctness (one could try to optimize,
but it is not clear if gains would justify added complexity).
There are some inconvenient aspects. Normally macro shadow
other meanings, but there are ways to access both (like
'(f)' to get meaning of 'f' as a function), so in general
symbol table must store both macro meaning and other
meaning (if both are present). Structs and unions
require care to get fields when appropriate and outside
meaning otherwise.
--
Waldek Hebisch
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-08-24 13:28 +0100 |
| Message-ID | <87edx5u8p9.fsf@bsb.me.uk> |
| 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},
> { "_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},
> };
I wanted to time some algorithms so in case we want some repeatable and
comparable timings, here is the driver program I am using:
#include <stdio.h>
#include <ctype.h>
int lookup(const char *tok, unsigned len);
int main(void)
{
int r = 0, c;
while ((c = getchar()) != EOF)
if (isalpha(c) || c == '_') {
unsigned l = 0;
char token[20];
do token[l++] = c;
while (l < sizeof token - 1 &&
(isalnum(c = getchar()) || c == '_'));
token[l] = 0;
r += lookup(token, l);
}
printf("%d\n", r);
}
The lookup function returns the token value or -1 for non-keywords.
To get an IO and driver overhead, I compiles and linked with
int lookup(const char *tok, unsigned l)
{
return 1;
}
Running on sqlite3's amalgamated source (sqlite-amalgamation-3390200)
this "null" version reports 992905 in about 0.072s. (The result,
992905, is of course wrong in this case.)
A version using the perfect hash generated by gperf returns 3231512 in
about 0.075s and is hard to distinguish from the IO-only run time.
A linear search returns 3231512 in 0.24s, and a binary search using C's
often overlooked bsearch function returns the same result in 0.1s.
All programs compiled and linked with gcc -O3. The lookup function was
always in a separate translation unit and is not being inlined.
--
Ben.
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-24 06:25 -0700 |
| Message-ID | <7caa0f30-bc19-4c93-80b9-93aa8611fb67n@googlegroups.com> |
| In reply to | #167183 |
On Wednesday, August 24, 2022 at 9:28:50 AM UTC-3, Ben Bacarisse 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},
> > { "_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},
> > };
> I wanted to time some algorithms so in case we want some repeatable and
> comparable timings, here is the driver program I am using:
>
> #include <stdio.h>
> #include <ctype.h>
>
> int lookup(const char *tok, unsigned len);
>
> int main(void)
> {
> int r = 0, c;
> while ((c = getchar()) != EOF)
> if (isalpha(c) || c == '_') {
> unsigned l = 0;
> char token[20];
> do token[l++] = c;
> while (l < sizeof token - 1 &&
> (isalnum(c = getchar()) || c == '_'));
> token[l] = 0;
> r += lookup(token, l);
> }
> printf("%d\n", r);
> }
>
> The lookup function returns the token value or -1 for non-keywords.
>
> To get an IO and driver overhead, I compiles and linked with
>
> int lookup(const char *tok, unsigned l)
> {
> return 1;
> }
>
> Running on sqlite3's amalgamated source (sqlite-amalgamation-3390200)
> this "null" version reports 992905 in about 0.072s. (The result,
> 992905, is of course wrong in this case.)
>
> A version using the perfect hash generated by gperf returns 3231512 in
> about 0.075s and is hard to distinguish from the IO-only run time.
>
> A linear search returns 3231512 in 0.24s, and a binary search using C's
> often overlooked bsearch function returns the same result in 0.1s.
>
> All programs compiled and linked with gcc -O3. The lookup function was
> always in a separate translation unit and is not being inlined.
>
> --
Can you plug this one and compare? I am not using the length.
https://godbolt.org/z/1Yh96ch5e
this one is like:
if (*s == 'N') { ... }
if (*s == 'a') { ... }
if (*s == 'b') { ... }
if (*s == 'c') { ... }
if (*s == 'd') { ... }
if (*s == 'e') { ... }
if (*s == 'f') { ... }
if (*s == 'g') { ... }
if (*s == 'i') { ... }
if (*s == 'l') { ... }
if (*s == 'n') { ... }
if (*s == 'r') { ... }
if (*s == 's') { ... }
if (*s == 't') { ... }
if (*s == 'u') { ... }
if (*s == 'v') { ... }
if (*s == 'w') { ... }
if (*s == '_') { ... }
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-24 06:50 -0700 |
| Message-ID | <332314f7-ff40-4ee3-a24f-08cd9a17f18bn@googlegroups.com> |
| In reply to | #167184 |
On Wednesday, August 24, 2022 at 10:26:07 AM UTC-3, Thiago Adams wrote:
> On Wednesday, August 24, 2022 at 9:28:50 AM UTC-3, Ben Bacarisse wrote:
...
> Can you plug this one and compare? I am not using the length.
> https://godbolt.org/z/1Yh96ch5e
> this one is like:
>
> if (*s == 'N') { ... }
> if (*s == 'a') { ... }
> if (*s == 'b') { ... }
> if (*s == 'c') { ... }
> if (*s == 'd') { ... }
> if (*s == 'e') { ... }
> if (*s == 'f') { ... }
> if (*s == 'g') { ... }
...
Looking at the code, -O2, gcc it creates a jump table.
lookup:
movzx edx, BYTE PTR [rdi]
cmp dl, 78
je .L450
sub edx, 95
cmp dl, 24
ja .L81
movzx edx, dl
jmp [QWORD PTR .L5[0+rdx*8]] <<<<<<<<<<
.L5:
.quad .L21
.quad .L81
...
So doesn't matter the order of "ifs" or changing "ifs" by "switch case" the
result is the same. A
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-08-24 15:19 +0100 |
| Message-ID | <8735dlu3kn.fsf@bsb.me.uk> |
| In reply to | #167184 |
Thiago Adams <thiago.adams@gmail.com> writes: > On Wednesday, August 24, 2022 at 9:28:50 AM UTC-3, Ben Bacarisse wrote: >> Running on sqlite3's amalgamated source (sqlite-amalgamation-3390200) >> this "null" version reports 992905 in about 0.072s. (The result, >> 992905, is of course wrong in this case.) >> >> A version using the perfect hash generated by gperf returns 3231512 in >> about 0.075s and is hard to distinguish from the IO-only run time. >> >> A linear search returns 3231512 in 0.24s, and a binary search using C's >> often overlooked bsearch function returns the same result in 0.1s. >> >> All programs compiled and linked with gcc -O3. The lookup function was >> always in a separate translation unit and is not being inlined. > > Can you plug this one and compare? I am not using the length. > https://godbolt.org/z/1Yh96ch5e Hmm... it produces a different count. Are the numbers supposed to those you originally posted? I may be using an old table. 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 hope the code was automatically generated. It's looks fragile and very hard to verify! -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-24 09:46 -0700 |
| Message-ID | <f115f125-e8f4-4e62-920d-f4fe25c99f0fn@googlegroups.com> |
| In reply to | #167188 |
On Wednesday, August 24, 2022 at 11:19:34 AM UTC-3, Ben Bacarisse wrote: > Thiago Adams <thiago...@gmail.com> writes: > > > On Wednesday, August 24, 2022 at 9:28:50 AM UTC-3, Ben Bacarisse wrote: > > >> Running on sqlite3's amalgamated source (sqlite-amalgamation-3390200) > >> this "null" version reports 992905 in about 0.072s. (The result, > >> 992905, is of course wrong in this case.) > >> > >> A version using the perfect hash generated by gperf returns 3231512 in > >> about 0.075s and is hard to distinguish from the IO-only run time. > >> > >> A linear search returns 3231512 in 0.24s, and a binary search using C's > >> often overlooked bsearch function returns the same result in 0.1s. > >> > >> All programs compiled and linked with gcc -O3. The lookup function was > >> always in a separate translation unit and is not being inlined. > > > > Can you plug this one and compare? I am not using the length. > > https://godbolt.org/z/1Yh96ch5e > Hmm... it produces a different count. Are the numbers supposed to those > you originally posted? I may be using an old table. The original was not sorted by "strcmp" and the code I posted is. sorted by strcmp is this (token is the index, NULL is 0) "NULL", "_Alignas", "_Alignof", "_Atomic", "_BitInt", "_Bool", "_Complex", "_Decimal128", "_Decimal32", "_Decimal64", "_Generic", "_Hashof", "_Imaginary", "_Noreturn", "_Static_assert", "_Thread_local", "__alignof", "__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",
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-08-24 20:40 +0100 |
| Message-ID | <87a67tsa5a.fsf@bsb.me.uk> |
| In reply to | #167190 |
Thiago Adams <thiago.adams@gmail.com> writes: > On Wednesday, August 24, 2022 at 11:19:34 AM UTC-3, Ben Bacarisse wrote: >> Thiago Adams <thiago...@gmail.com> writes: >> >> > On Wednesday, August 24, 2022 at 9:28:50 AM UTC-3, Ben Bacarisse wrote: >> >> >> Running on sqlite3's amalgamated source (sqlite-amalgamation-3390200) >> >> this "null" version reports 992905 in about 0.072s. (The result, >> >> 992905, is of course wrong in this case.) >> >> >> >> A version using the perfect hash generated by gperf returns 3231512 in >> >> about 0.075s and is hard to distinguish from the IO-only run time. >> >> >> >> A linear search returns 3231512 in 0.24s, and a binary search using C's >> >> often overlooked bsearch function returns the same result in 0.1s. >> >> >> >> All programs compiled and linked with gcc -O3. The lookup function was >> >> always in a separate translation unit and is not being inlined. >> > >> > Can you plug this one and compare? I am not using the length. >> > https://godbolt.org/z/1Yh96ch5e >> Hmm... it produces a different count. Are the numbers supposed to those >> you originally posted? I may be using an old table. > > The original was not sorted by "strcmp" and the code I posted is. Not only have you changed the order (and hence the numbering) you've added a keyword. That just messes everything up. I'll just assume your code give the right answer, because it will be a pain to check it. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-24 10:08 -0700 |
| Message-ID | <86f414b4-231e-40d3-a1bf-558b08507376n@googlegroups.com> |
| In reply to | #167188 |
On Wednesday, August 24, 2022 at 11:19:34 AM UTC-3, Ben Bacarisse wrote:
> Thiago Adams <thiago...@gmail.com> writes:
...
> I hope the code was automatically generated. It's looks fragile and
> very hard to verify!
Generator:
#include <stdio.h>
#include <string.h>
#include <assert.h>
#include <stdbool.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;
}
//we have the range
if (begin == end) {
//just one
if (keywords[i][level] != '\0') {
printf("%*cif(*s == '%c') {\n", ident * 2, ' ', keywords[i][level]);
printf("%*cs++;\n", ident * 3, ' ');
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++ == '%c'", keywords[i][j]);
}
if (j != level + 1) {
printf(" &&");
}
printf(" *s =='\\0') return %i; else return -1;", i);
printf(";\n");
printf("%*c}\n", ident * 2, ' ');
}
else {
printf("%*cif(*s == '\\0') {\n", ident * 2, ' ');
printf("%*cs++;\n", ident * 3, ' ');
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 == '%c') {\n", ident * 2, ' ', keywords[i][level]);
printf("%*cs++; \n", ident * 3, ' ');
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;
//swap(&arr[j], &arr[j + 1]);
}
}
}
printf("int find(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]));
}
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-08-24 20:42 +0100 |
| Message-ID | <8735dlsa1d.fsf@bsb.me.uk> |
| In reply to | #167191 |
Thiago Adams <thiago.adams@gmail.com> writes: > On Wednesday, August 24, 2022 at 11:19:34 AM UTC-3, Ben Bacarisse wrote: >> Thiago Adams <thiago...@gmail.com> writes: > ... >> I hope the code was automatically generated. It's looks fragile and >> very hard to verify! > > Generator: That's good. But the generator is not easy to check! I'd go with a relatively widely-used tool. Especially as it give faster code. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | bart c <bart4858@gmail.com> |
|---|---|
| Date | 2022-08-24 07:31 -0700 |
| Message-ID | <71e49cf0-53da-4c73-8ae4-a6f6d1117f23n@googlegroups.com> |
| In reply to | #167184 |
On Wednesday, 24 August 2022 at 14:26:07 UTC+1, Thiago Adams wrote:
> On Wednesday, August 24, 2022 at 9:28:50 AM UTC-3, Ben Bacarisse wrote:
> > I wanted to time some algorithms so in case we want some repeatable and
> > comparable timings, here is the driver program I am using:
> >
> > #include <stdio.h>
> > #include <ctype.h>
> >
> > int lookup(const char *tok, unsigned len);
> >
> > int main(void)
> > {
> > int r = 0, c;
> > while ((c = getchar()) != EOF)
> > if (isalpha(c) || c == '_') {
> > unsigned l = 0;
> > char token[20];
> > do token[l++] = c;
> > while (l < sizeof token - 1 &&
> > (isalnum(c = getchar()) || c == '_'));
> > token[l] = 0;
> > r += lookup(token, l);
> > }
> > printf("%d\n", r);
> > }
> >
> > The lookup function returns the token value or -1 for non-keywords.
> >
> > To get an IO and driver overhead, I compiles and linked with
> >
> > int lookup(const char *tok, unsigned l)
> > {
> > return 1;
> > }
> >
> > Running on sqlite3's amalgamated source (sqlite-amalgamation-3390200)
> > this "null" version reports 992905 in about 0.072s. (The result,
> > 992905, is of course wrong in this case.)
> >
> > A version using the perfect hash generated by gperf returns 3231512 in
> > about 0.075s and is hard to distinguish from the IO-only run time.
> >
> > A linear search returns 3231512 in 0.24s, and a binary search using C's
> > often overlooked bsearch function returns the same result in 0.1s.
> >
> > All programs compiled and linked with gcc -O3. The lookup function was
> > always in a separate translation unit and is not being inlined.
> >
> > --
> Can you plug this one and compare? I am not using the length.
> https://godbolt.org/z/1Yh96ch5e
> this one is like:
I tried your code in Ben's program and it's pretty fast.
However, I don't believe it's a good fit within that test program, as that does quite a lot of work in finding the boundaries of each token, using system calls, and extracting the token into a zero-terminated string.
Your lookup method doesn't need all that, it can start work immediately the first alphabetic is detected. But it needs to consume characters from the input ready for the next token. (Personally I would grab the entire input file into an in-memory string, or use another method to map the file so that it can be accessed like a string.)
So it could end up performing better with a customised test program.
A hash-table approach has the same problems in needing to identify the whole token first, /and/ work out its hash value. However it has the potential to be more useful within the bigger program, whatever that happens to do.
[toc] | [prev] | [next] | [standalone]
| From | Anton Shepelev <anton.txt@gmail.com> |
|---|---|
| Date | 2022-08-25 01:04 +0300 |
| Message-ID | <20220825010423.97f368943e1fd1e556e0321f@gmail.com> |
| In reply to | #167184 |
Thiago Adams: > Can you plug this one and compare? I am not using the length. > https://godbolt.org/z/1Yh96ch5e The site won't open on my PC with Windows XP. This is Usenet. Let us post code in our articles so that it is archived and accessible for everyone with access to Usenet. With respect to Usenet, the Web is a transcendental entity and web references are out-of-bandwith. -- () 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-24 16:43 -0700 |
| Message-ID | <08a98867-c006-480c-9b15-0b0019c064fen@googlegroups.com> |
| In reply to | #167199 |
On Wednesday, August 24, 2022 at 7:04:36 PM UTC-3, Anton Shepelev wrote:
> Thiago Adams:
> > Can you plug this one and compare? I am not using the length.
> > https://godbolt.org/z/1Yh96ch5e
> The site won't open on my PC with Windows XP. This is
> Usenet. Let us post code in our articles so that it is
> archived and accessible for everyone with access to Usenet.
> With respect to Usenet, the Web is a transcendental entity
> and web references are out-of-bandwith.
This generator outputs the 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;
}
//we have the range
if (begin == end)
{
//just one
if (keywords[i][level] != '\0')
{
printf("%*cif(*s == '%c') {\n", ident * 2, ' ', keywords[i][level]);
printf("%*cs++;\n", ident * 3, ' ');
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++ == '%c'", keywords[i][j]);
}
if (j != level + 1)
{
printf(" &&");
}
printf(" *s =='\\0') return %i; else return -1;", i);
printf(";\n");
printf("%*c}\n", ident * 2, ' ');
}
else
{
printf("%*cif(*s == '\\0') {\n", ident * 2, ' ');
printf("%*cs++;\n", ident * 3, ' ');
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 == '%c') {\n", ident * 2, ' ', keywords[i][level]);
printf("%*cs++; \n", ident * 3, ' ');
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]));
}
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-24 16:54 -0700 |
| Message-ID | <e72e2f97-da10-417e-8252-9015b6f70f5fn@googlegroups.com> |
| In reply to | #167203 |
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;
}
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-24 17:08 -0700 |
| Message-ID | <a6176a75-ca68-48c5-85fc-0c1417027f1cn@googlegroups.com> |
| In reply to | #167204 |
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)
[toc] | [prev] | [next] | [standalone]
Page 5 of 6 — ← Prev page 1 2 3 4 [5] 6 Next page →
Back to top | Article view | comp.lang.c
csiph-web