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 3 of 6 — ← Prev page 1 2 [3] 4 5 6 Next page →
| From | Siri Cruise <chine.bleu@yahoo.com> |
|---|---|
| Date | 2022-08-22 09:29 -0700 |
| Message-ID | <chine.bleu-976816.09293522082022@news.eternal-september.org> |
| In reply to | #167095 |
In article <87edx8wa03.fsf@bsb.me.uk>,
Ben Bacarisse <ben.usenet@bsb.me.uk> wrote:
> > You can build a Finite State Automaton.
>
> If you mean a deterministic FSA, that's tedious and error-prone if done
> by hand. But if TA is happy with a slightly slower nondeterministic FSA
> it can be done reasonably simply by maintaining an set of candidate
> matches. Often, a one-word bit-map will do.
In this particular example it's a deterministic FSA that could be
implemented as (this can be done easily with real macro
processors)
> 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},
switch (input) {
case 'N': goto stateN;
case '_': goto state_;
default: goto fail;
}
state_: switch (input) {
case 'A': goto state_A;
case 'B': goto state_B;
...
}
state_A: switch (input) ...
If the language has computed gotos, like GNU label arrays, you
can implement with something like (though cache misses would lose
any supposed efficiency).
static void *start[256] = {'N': &&stateN, '_', &&state_,
...};
static void *state_[256] = {'A': &&state_A, 'B', &&stateB_,
...};
goto start[input];
state_: goto state_[input];
state_A: ...
state_B: ...
...
--
:-<> Siri Seal of Disavowal #000-001. Disavowed. Denied. Deleted. @
'I desire mercy, not sacrifice.' /|\
Discordia: not just a religion but also a parody. This post / \
I am an Andrea Chen sockpuppet. insults Islam. Mohammed
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-08-22 17:36 +0100 |
| Message-ID | <87r118utej.fsf@bsb.me.uk> |
| In reply to | #167105 |
Siri Cruise <chine.bleu@yahoo.com> writes: > In article <87edx8wa03.fsf@bsb.me.uk>, > Ben Bacarisse <ben.usenet@bsb.me.uk> wrote: > >> > You can build a Finite State Automaton. >> >> If you mean a deterministic FSA, that's tedious and error-prone if done >> by hand. But if TA is happy with a slightly slower nondeterministic FSA >> it can be done reasonably simply by maintaining an set of candidate >> matches. Often, a one-word bit-map will do. > > In this particular example it's a deterministic FSA that could be > implemented as (this can be done easily with real macro > processors) You mean like TRAC or M4? I'd like to see how this is done as I've always found hand-written FSAs to be error-prone. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-08-22 16:53 +0100 |
| Message-ID | <878rngw9zg.fsf@bsb.me.uk> |
| In reply to | #167093 |
Siri Cruise <chine.bleu@yahoo.com> writes: > In article > <d8294420-7b45-4344-b9eb-0ad867850ec6n@googlegroups.com>, > Thiago Adams <thiago.adams@gmail.com> wrote: > >> Given a c string I need to return as fast as possible the pair (if exist) of >> the corresponding keyword_pair. > > You can build a Finite State Automaton. If you mean a deterministic FSA, that's tedious and error-prone if done by hand. But if TA is happy with a slightly slower nondeterministic FSA it can be done reasonably simply by maintaining an set of candidate matches. Often, a one-word bit-map will do. But if you want a deterministic FSA, there are tools like flex that will do it right. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-22 09:11 -0700 |
| Message-ID | <9ddfe85a-a07f-4d99-aab1-946f678a1f07n@googlegroups.com> |
| In reply to | #167093 |
On Monday, August 22, 2022 at 12:44:22 PM UTC-3, Siri Cruise wrote: > In article > <d8294420-7b45-4344...@googlegroups.com>, > Thiago Adams <thiago...@gmail.com> wrote: > > > Given a c string I need to return as fast as possible the pair (if exist) of > > the corresponding keyword_pair. > You can build a Finite State Automaton. Yes.. I am thinking exactly like that. But at some point we need to map like char -> state then it is the same switch problem. How to given char how to find the state in a fast way?
[toc] | [prev] | [next] | [standalone]
| From | antispam@math.uni.wroc.pl |
|---|---|
| Date | 2022-08-22 19:30 +0000 |
| Message-ID | <te0lgm$7fh$1@gioia.aioe.org> |
| In reply to | #167098 |
Thiago Adams <thiago.adams@gmail.com> wrote:
> On Monday, August 22, 2022 at 12:44:22 PM UTC-3, Siri Cruise wrote:
> > In article
> > <d8294420-7b45-4344...@googlegroups.com>,
> > Thiago Adams <thiago...@gmail.com> wrote:
> >
> > > Given a c string I need to return as fast as possible the pair (if exist) of
> > > the corresponding keyword_pair.
> > You can build a Finite State Automaton.
>
> Yes.. I am thinking exactly like that. But at some point
> we need to map like char -> state then it is the same
> switch problem. How to given char how to find the state in a fast way?
You need map (state, char) -> state, that is pair state, char to new
state. Easily done with two dimensional array:
int s = 1; /* could use symbolic name here */
unsigned char cp;
while (s && (c = *cp++)) {
s = transition[s][c];
}
After loop test if c = 0, if yes all input string was used, if no
it was rejected before end. If c = 0 thes is s is accepting (single
table lookup), if yes it gives result, if no mens not found.
In your case you will have few hundred cases, so table will be
largish. Traditionally table is compressed by so called comb
vector method. Namely, most entris are "empty", that is they
do not correspond to valid transitions (encoded by 0 above).
In comb vector method we put transitions in one dimensional
array, with some offset for each state. Offsets are chosen
so that _valid_ transitions are in different places. This
can be done in greedy way: use offset zero for first state.
For state n start from zero offset and shift it to find
place with no overlap with previous vectors. Repeat as long
as needed.
Comb vector methods needs two additional arrays: one for
offsets (indexed by states) and another one to check if
transition correspond to current state.
With compressed tables automaton needs more instructions
per transition. OTOH smaller tables means less cache
misses, so may win despite executiong more instructions.
--
Waldek Hebisch
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-22 14:19 -0700 |
| Message-ID | <1ad0af3a-453f-4802-a64e-7dc2480b3018n@googlegroups.com> |
| In reply to | #167121 |
On Monday, August 22, 2022 at 4:30:45 PM UTC-3, anti...@math.uni.wroc.pl wrote:
> Thiago Adams <thiago...@gmail.com> wrote:
> > On Monday, August 22, 2022 at 12:44:22 PM UTC-3, Siri Cruise wrote:
> > > In article
> > > <d8294420-7b45-4344...@googlegroups.com>,
> > > Thiago Adams <thiago...@gmail.com> wrote:
> > >
> > > > Given a c string I need to return as fast as possible the pair (if exist) of
> > > > the corresponding keyword_pair.
> > > You can build a Finite State Automaton.
> >
> > Yes.. I am thinking exactly like that. But at some point
> > we need to map like char -> state then it is the same
> > switch problem. How to given char how to find the state in a fast way?
> You need map (state, char) -> state, that is pair state, char to new
> state. Easily done with two dimensional array:
>
> int s = 1; /* could use symbolic name here */
> unsigned char cp;
> while (s && (c = *cp++)) {
> s = transition[s][c];
> }
In 2013 I implemented chapter 3 of dragon book (https://github.com/thradams/tklgen/tree/master/tklgen)
..but instead of doing in C I did in C++ and instead of creating tables I output switch and ifs..
it is not easy to hack the code now. :(
The ouput was switch + if because it was easy to read and debug.
But it not ease as strcmp for instance. Maybe there is some site to generate these tables..
then I can decide if the performance improvements compensate..
[toc] | [prev] | [next] | [standalone]
| From | Öö Tiib <ootiib@hot.ee> |
|---|---|
| Date | 2022-08-22 14:36 -0700 |
| Message-ID | <56df86c2-aa62-4524-a00b-b8cee6275432n@googlegroups.com> |
| In reply to | #167123 |
On Tuesday, 23 August 2022 at 00:19:41 UTC+3, Thiago Adams wrote:
> On Monday, August 22, 2022 at 4:30:45 PM UTC-3, anti...@math.uni.wroc.pl wrote:
> > Thiago Adams <thiago...@gmail.com> wrote:
> > > On Monday, August 22, 2022 at 12:44:22 PM UTC-3, Siri Cruise wrote:
> > > > In article
> > > > <d8294420-7b45-4344...@googlegroups.com>,
> > > > Thiago Adams <thiago...@gmail.com> wrote:
> > > >
> > > > > Given a c string I need to return as fast as possible the pair (if exist) of
> > > > > the corresponding keyword_pair.
> > > > You can build a Finite State Automaton.
> > >
> > > Yes.. I am thinking exactly like that. But at some point
> > > we need to map like char -> state then it is the same
> > > switch problem. How to given char how to find the state in a fast way?
> > You need map (state, char) -> state, that is pair state, char to new
> > state. Easily done with two dimensional array:
> >
> > int s = 1; /* could use symbolic name here */
> > unsigned char cp;
> > while (s && (c = *cp++)) {
> > s = transition[s][c];
> > }
> In 2013 I implemented chapter 3 of dragon book (https://github.com/thradams/tklgen/tree/master/tklgen)
> ..but instead of doing in C I did in C++ and instead of creating tables I output switch and ifs..
> it is not easy to hack the code now. :(
> The ouput was switch + if because it was easy to read and debug.
> But it not ease as strcmp for instance. Maybe there is some site to generate these tables..
> then I can decide if the performance improvements compensate..
Why not to use GNU gperf for generating code for that problem?
<https://www.gnu.org/software/gperf/>
Or at least a code to benchmark your whatever other solution?
[toc] | [prev] | [next] | [standalone]
| From | antispam@math.uni.wroc.pl |
|---|---|
| Date | 2022-08-22 22:49 +0000 |
| Message-ID | <te116n$uop$1@gioia.aioe.org> |
| In reply to | #167123 |
Thiago Adams <thiago.adams@gmail.com> wrote:
> On Monday, August 22, 2022 at 4:30:45 PM UTC-3, anti...@math.uni.wroc.pl wrote:
> > Thiago Adams <thiago...@gmail.com> wrote:
> > > On Monday, August 22, 2022 at 12:44:22 PM UTC-3, Siri Cruise wrote:
> > > > In article
> > > > <d8294420-7b45-4344...@googlegroups.com>,
> > > > Thiago Adams <thiago...@gmail.com> wrote:
> > > >
> > > > > Given a c string I need to return as fast as possible the pair (if exist) of
> > > > > the corresponding keyword_pair.
> > > > You can build a Finite State Automaton.
> > >
> > > Yes.. I am thinking exactly like that. But at some point
> > > we need to map like char -> state then it is the same
> > > switch problem. How to given char how to find the state in a fast way?
> > You need map (state, char) -> state, that is pair state, char to new
> > state. Easily done with two dimensional array:
> >
> > int s = 1; /* could use symbolic name here */
> > unsigned char cp;
> > while (s && (c = *cp++)) {
> > s = transition[s][c];
> > }
>
> In 2013 I implemented chapter 3 of dragon book (https://github.com/thradams/tklgen/tree/master/tklgen)
> ..but instead of doing in C I did in C++ and instead of creating tables I output switch and ifs..
> it is not easy to hack the code now. :(
> The ouput was switch + if because it was easy to read and debug.
> But it not ease as strcmp for instance. Maybe there is some site to generate these tables..
Well, flex will generate tables for you (actually, the whols scanner,
but if you understand principle you can use flex tables with your
scanner code). However, if your "language" is set of constant
strings, then generating tables is very easy: each prefix of your
strings gives you state (if two strings give the same prefix you
gent only one state). To generate transition tables for each
string assign final state. After that drop final letter one
by one. Generate state for obtained prefix and transition
from this state to state corresonding to longer string. For
example, if you have strings "abc" and "ac", you first create
(final) state for "abc", dropping last letter we get "ab" so
we add state for it and transition "ab", 'c' -> "abc", then
we drop "b" getting "a", add transition to "ab", then we
drop "a" getting empty string, so we add state for empty
string and transition to "a". We handle "ab" in similar way.
However, we need to notice that we already created state
for "a", so we just add new transition. After that we
are done with "ab" because prefix of "a" was handled earlier.
In practice it may be convenient to crate state for empty
string at start, it is initial state and creating it first
we can ensure that it gets fixerd number (say 1). "Generate
state" part is really simple: first we check if string
already appeared as prefix (say using linear search
over already generated prefixes), if yes we use its
state (number), if no we use value from a counter and
increase it.
Comb vector technique requires a bit more work. However,
note that many stats will have only one valid transition,
so clearly will compress quite well (we can put single
trasition in any free spot).
> then I can decide if the performance improvements compensate..
Well, I am saying that generating finite automanton is not
hard. I am not saying that it will give best performance.
Maybe, maybe not. If you have something compiler-like
in mind, then following bartc advice may be best way.
--
Waldek Hebisch
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-23 05:13 -0700 |
| Message-ID | <42a12eea-f20a-49eb-9b5e-7230b374195dn@googlegroups.com> |
| In reply to | #167127 |
On Monday, August 22, 2022 at 7:50:16 PM UTC-3, anti...@math.uni.wroc.pl wrote:
> Thiago Adams <thiago...@gmail.com> wrote:
> > On Monday, August 22, 2022 at 4:30:45 PM UTC-3, anti...@math.uni.wroc.pl wrote:
> > > Thiago Adams <thiago...@gmail.com> wrote:
> > > > On Monday, August 22, 2022 at 12:44:22 PM UTC-3, Siri Cruise wrote:
> > > > > In article
> > > > > <d8294420-7b45-4344...@googlegroups.com>,
> > > > > Thiago Adams <thiago...@gmail.com> wrote:
> > > > >
> > > > > > Given a c string I need to return as fast as possible the pair (if exist) of
> > > > > > the corresponding keyword_pair.
> > > > > You can build a Finite State Automaton.
> > > >
> > > > Yes.. I am thinking exactly like that. But at some point
> > > > we need to map like char -> state then it is the same
> > > > switch problem. How to given char how to find the state in a fast way?
> > > You need map (state, char) -> state, that is pair state, char to new
> > > state. Easily done with two dimensional array:
> > >
> > > int s = 1; /* could use symbolic name here */
> > > unsigned char cp;
> > > while (s && (c = *cp++)) {
> > > s = transition[s][c];
> > > }
I translate a state machine to code without tables / switch cases.
(Doing this I am not depending on compiler magic optimisations for switch)
The translation is done is each state has a label. State is changed moving the "cursor"
and goto to the next state.
For instance for the keywords "auto break bool"
bool is_keyword(const char* text)
{
int i = 0;
/*L_0:*/
if (text[i] == 'a') {
i++;
goto L_1;
}
else if (text[i] == 'b') {
i++;
goto L_2;
}
return false;
L_1:
if (text[i] == 'u') {
i++;
goto L_3;
}
return false;
L_2:
if (text[i] == 'o') {
i++;
goto L_4;
}
else if (text[i] == 'r') {
i++;
goto L_5;
}
return false;
L_3:
if (text[i] == 't') {
i++;
goto L_6;
}
return false;
L_4:
if (text[i] == 'o') {
i++;
goto L_7;
}
return false;
L_5:
if (text[i] == 'e') {
i++;
goto L_8;
}
return false;
L_6:
if (text[i] == 'o') {
i++;
if (text[i] == '\0')
return true;///* end state for TKAUTO*/
}
return false;
L_7:
if (text[i] == 'l') {
i++;
if (text[i] == '\0')
return true;/* end state for TKBOOL*/
}
return false;
L_8:
if (text[i] == 'a') {
i++;
goto L_11;
}
return false;
L_11:
if (text[i] == 'k') {
i++;
if (text[i] == '\0')
return true; /* end state for TKBREAK*/
}
return false;
}
The code has a "linear search" a sequence of ifs that is (for the first state) the number
of possible letters to start. So more frequent ones must go first.
Doing this "mechanical code" I changed it to be more "human" code.
The result is:
bool is_keyword(const char* s)
{
if (*s == 'a')
{
s++;
/*a uto*/
return *s++ == 'u' && *s++ == 't' && *s++ == 'o' && *s++ == '\0';
}
else if (*s == 'b')
{
s++;
if (*s == 'o') {
s++;
/*b o ol*/
return *s++ == 'o' && *s++ == 'l' && *s++ == '\0';
}
else if (*s == 'r')
{
s++;
/*b r eak*/
return *s++ == 'e' && *s++ == 'a' && *s++ == 'k' && *s++ == '\0';
}
}
return false;
}
I think this code has the best performance for many cases!
I will try to create a generator that does this. (I did in the past using switches.. now I want just ifs)
The state machine gotos is good for other types of tokens (regex that have loops) but for
keywords it is basically going forward.
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-23 15:55 -0700 |
| Message-ID | <a615df1d-8969-4055-a721-eba26bf05299n@googlegroups.com> |
| In reply to | #167142 |
On Tuesday, August 23, 2022 at 9:13:59 AM UTC-3, Thiago Adams wrote:
> On Monday, August 22, 2022 at 7:50:16 PM UTC-3, anti...@math.uni.wroc.pl wrote:
> > Thiago Adams <thiago...@gmail.com> wrote:
> > > On Monday, August 22, 2022 at 4:30:45 PM UTC-3, anti...@math.uni.wroc.pl wrote:
> > > > Thiago Adams <thiago...@gmail.com> wrote:
> > > > > On Monday, August 22, 2022 at 12:44:22 PM UTC-3, Siri Cruise wrote:
> > > > > > In article
> > > > > > <d8294420-7b45-4344...@googlegroups.com>,
> > > > > > Thiago Adams <thiago...@gmail.com> wrote:
> > > > > >
> > > > > > > Given a c string I need to return as fast as possible the pair (if exist) of
> > > > > > > the corresponding keyword_pair.
> > > > > > You can build a Finite State Automaton.
> > > > >
> > > > > Yes.. I am thinking exactly like that. But at some point
> > > > > we need to map like char -> state then it is the same
> > > > > switch problem. How to given char how to find the state in a fast way?
> > > > You need map (state, char) -> state, that is pair state, char to new
> > > > state. Easily done with two dimensional array:
> > > >
> > > > int s = 1; /* could use symbolic name here */
> > > > unsigned char cp;
> > > > while (s && (c = *cp++)) {
> > > > s = transition[s][c];
> > > > }
> I translate a state machine to code without tables / switch cases.
> (Doing this I am not depending on compiler magic optimisations for switch)
>
> The translation is done is each state has a label. State is changed moving the "cursor"
> and goto to the next state.
>
> For instance for the keywords "auto break bool"
>
> bool is_keyword(const char* text)
> {
> int i = 0;
> /*L_0:*/
> if (text[i] == 'a') {
> i++;
> goto L_1;
> }
> else if (text[i] == 'b') {
> i++;
> goto L_2;
> }
>
> return false;
>
> L_1:
> if (text[i] == 'u') {
> i++;
> goto L_3;
> }
> return false;
>
> L_2:
> if (text[i] == 'o') {
> i++;
> goto L_4;
> }
> else if (text[i] == 'r') {
> i++;
> goto L_5;
> }
>
> return false;
> L_3:
> if (text[i] == 't') {
> i++;
> goto L_6;
> }
> return false;
>
> L_4:
> if (text[i] == 'o') {
> i++;
> goto L_7;
> }
> return false;
>
> L_5:
> if (text[i] == 'e') {
> i++;
> goto L_8;
> }
> return false;
>
> L_6:
> if (text[i] == 'o') {
> i++;
> if (text[i] == '\0')
> return true;///* end state for TKAUTO*/
> }
> return false;
>
> L_7:
> if (text[i] == 'l') {
> i++;
> if (text[i] == '\0')
> return true;/* end state for TKBOOL*/
> }
> return false;
>
> L_8:
> if (text[i] == 'a') {
> i++;
> goto L_11;
> }
> return false;
>
> L_11:
> if (text[i] == 'k') {
> i++;
> if (text[i] == '\0')
> return true; /* end state for TKBREAK*/
> }
>
> return false;
> }
>
> The code has a "linear search" a sequence of ifs that is (for the first state) the number
> of possible letters to start. So more frequent ones must go first.
>
> Doing this "mechanical code" I changed it to be more "human" code.
> The result is:
>
> bool is_keyword(const char* s)
> {
> if (*s == 'a')
> {
> s++;
> /*a uto*/
> return *s++ == 'u' && *s++ == 't' && *s++ == 'o' && *s++ == '\0';
> }
> else if (*s == 'b')
> {
> s++;
> if (*s == 'o') {
>
> s++;
> /*b o ol*/
> return *s++ == 'o' && *s++ == 'l' && *s++ == '\0';
> }
> else if (*s == 'r')
> {
> s++;
> /*b r eak*/
> return *s++ == 'e' && *s++ == 'a' && *s++ == 'k' && *s++ == '\0';
> }
> }
> return false;
> }
>
> I think this code has the best performance for many cases!
>
> I will try to create a generator that does this. (I did in the past using switches.. now I want just ifs)
> The state machine gotos is good for other types of tokens (regex that have loops) but for
> keywords it is basically going forward.
Jus to document I also tried something like:
if (ch < 'c')
{
if (ch == 'a') ...
if (ch == 'b') ...
}
else
{
if (ch == 'c') ...
if (ch == 'd') ...
...
}
That is similar of binary search .
We can add more and more ifs like this.
[toc] | [prev] | [next] | [standalone]
| From | bart c <bart4858@gmail.com> |
|---|---|
| Date | 2022-08-23 16:36 -0700 |
| Message-ID | <0f9e248d-8a25-4139-a563-c78644eb2402n@googlegroups.com> |
| In reply to | #167167 |
On Tuesday, 23 August 2022 at 23:55:43 UTC+1, Thiago Adams wrote:
> Jus to document I also tried something like:
>
> if (ch < 'c')
> {
> if (ch == 'a') ...
> if (ch == 'b') ...
> }
> else
> {
> if (ch == 'c') ...
> if (ch == 'd') ...
> ...
> }
>
> That is similar of binary search .
> We can add more and more ifs like this.
This is starting to look a little desperate. Such code looks unmaintainable to me (but I assume you will use some tool to generate it).
What is your actual aim here? Granted a simple linear search is not going to be that performant. But pretty much anything else is going to be faster. So how much faster does it have to be; have you done any measurements? Is checking for keywords mixed in with any other input such as punctuation or numeric literals or strings or comments; what's the bigger picture?
(And what is the purpose in just getting a Yes or No answer to whether the current token is a reserved word - what is done with that information? It seems wasteful determining which token you have, then discarding that information.)
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-23 17:42 -0700 |
| Message-ID | <8f086112-8c01-4644-89e7-a96e969a6f62n@googlegroups.com> |
| In reply to | #167169 |
On Tuesday, August 23, 2022 at 8:36:26 PM UTC-3, bart c wrote:
> On Tuesday, 23 August 2022 at 23:55:43 UTC+1, Thiago Adams wrote:
>
> > Jus to document I also tried something like:
> >
> > if (ch < 'c')
> > {
> > if (ch == 'a') ...
> > if (ch == 'b') ...
> > }
> > else
> > {
> > if (ch == 'c') ...
> > if (ch == 'd') ...
> > ...
> > }
> >
> > That is similar of binary search .
> > We can add more and more ifs like this.
> This is starting to look a little desperate. Such code looks unmaintainable to me (but I assume you will use some tool to generate it).
>
> What is your actual aim here? Granted a simple linear search is not going to be that performant. But pretty much anything else is going to be faster. So how much faster does it have to be; have you done any measurements? Is checking for keywords mixed in with any other input such as punctuation or numeric literals or strings or comments; what's the bigger picture?
One of my objectives is to understand what compilers can do on switch cases
and to write equivalent code.
This binary search didn't change the performance. My tests are a bunch of files
that takes 9.4s-10s. And I guess all changes I did are changing less than 0.5s so
it hard to see.
This topic is more about exploration and to understand the options.
Also from a compiler point of view. How switch works. Is it a lot of linear ifs?
> (And what is the purpose in just getting a Yes or No answer to whether the current token is a reserved word - what is done with that information? It seems wasteful determining which token you have, then discarding that information.)
The answer I use is returning the token.. but the algorithm didn't change i guess.
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <Keith.S.Thompson+u@gmail.com> |
|---|---|
| Date | 2022-08-23 18:36 -0700 |
| Message-ID | <87czcqxw04.fsf@nosuchdomain.example.com> |
| In reply to | #167174 |
Thiago Adams <thiago.adams@gmail.com> writes:
[...]
> This topic is more about exploration and to understand the options.
> Also from a compiler point of view. How switch works. Is it a lot of linear ifs?
The C standard specifies the behavior of a switch statement, not the
code that implements it.
Typically a compiler will generate a jump table if the case values
aren't too spread out, or perhaps a combination of jump tables and
conditional jumps if they are. If you're curious, write a few switch
statements and see what the generated code looks like. Try various
optimization levels, and try various compilers if you have access to
them.
(Many years ago, I crashed a UCSD Pascal compiler by writing a case
statement with cases 1, 10, 100, 1000, and 10000 -- back when 10000 was
a big number. I wouldn't expect a modern compiler to have this problem
even for arbitrarily large case values.)
--
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-24 03:34 -0700 |
| Message-ID | <30ebcf8d-dd4a-4dde-a8b9-dbd072453359n@googlegroups.com> |
| In reply to | #167174 |
On Wednesday, 24 August 2022 at 01:43:08 UTC+1, Thiago Adams wrote:
> On Tuesday, August 23, 2022 at 8:36:26 PM UTC-3, bart c wrote:
> > On Tuesday, 23 August 2022 at 23:55:43 UTC+1, Thiago Adams wrote:
> >
> > > Jus to document I also tried something like:
> > >
> > > if (ch < 'c')
> > > {
> > > if (ch == 'a') ...
> > > if (ch == 'b') ...
> > > }
> > > else
> > > {
> > > if (ch == 'c') ...
> > > if (ch == 'd') ...
> > > ...
> > > }
> > >
> > > That is similar of binary search .
> > > We can add more and more ifs like this.
> > This is starting to look a little desperate. Such code looks unmaintainable to me (but I assume you will use some tool to generate it).
> >
> > What is your actual aim here? Granted a simple linear search is not going to be that performant. But pretty much anything else is going to be faster. So how much faster does it have to be; have you done any measurements? Is checking for keywords mixed in with any other input such as punctuation or numeric literals or strings or comments; what's the bigger picture?
> One of my objectives is to understand what compilers can do on switch cases
> and to write equivalent code.
>
> This binary search didn't change the performance. My tests are a bunch of files
> that takes 9.4s-10s. And I guess all changes I did are changing less than 0.5s so
> it hard to see.
But how much of that is due to the lookup anyway? A quick and dirty method I used to discover how much a function contributes compared to total runtime (in the absence of proper profiling tools), is to just call it twice, when there are no harmful side-effects.
It might be that your 10 seconds becomes 11 seconds, so that the relevant function takes only 1 seconds. Then an improvement of 0.5 seconds means it's twice the speed.
It also means you look need to look elsewhere to find out why its slow, if 90% of runtime is not due to the lookup function.
(For tokenising source code (not C preprocessing), a modern machine should manage at least 5M lines per second, and parsing, at least 2M lines per second. So if your test files are much less than 20M lines of code, then it could be a bit faster. If more, then there's nothing wrong with that speed.)
>
> This topic is more about exploration and to understand the options.
> Also from a compiler point of view. How switch works. Is it a lot of linear ifs?
How you never used https://godbolt.org? Put any C code in there, and look at the assembly produced. You can play around with compiler versions and options.
My own approach is this:
* Number of cases in switch is 6-8 or less: use a chain of if-else
* Number of cases have values with a span less than 500 or 1000: use a jump-table
* Otherwise use an if-else chain (C compiler); or report an error (non-C compiler, but that has another statement type which is used instead, which always does sequential tests, and also works with non-ints and non-constants).
If you want something faster than switch, even using a jump-table, then look at computed goto. (Needs gcc extensions in C.) That uses a table of label pointers, and is popular for bytecode-dispatching in interpreters.
[toc] | [prev] | [next] | [standalone]
| From | Thiago Adams <thiago.adams@gmail.com> |
|---|---|
| Date | 2022-08-24 04:40 -0700 |
| Message-ID | <38b94c2c-8524-4e81-bd3b-61bf81269f03n@googlegroups.com> |
| In reply to | #167180 |
On Wednesday, August 24, 2022 at 7:34:18 AM UTC-3, bart c wrote:
> On Wednesday, 24 August 2022 at 01:43:08 UTC+1, Thiago Adams wrote:
> > On Tuesday, August 23, 2022 at 8:36:26 PM UTC-3, bart c wrote:
> > > On Tuesday, 23 August 2022 at 23:55:43 UTC+1, Thiago Adams wrote:
> > >
> > > > Jus to document I also tried something like:
> > > >
> > > > if (ch < 'c')
> > > > {
> > > > if (ch == 'a') ...
> > > > if (ch == 'b') ...
> > > > }
> > > > else
> > > > {
> > > > if (ch == 'c') ...
> > > > if (ch == 'd') ...
> > > > ...
> > > > }
> > > >
> > > > That is similar of binary search .
> > > > We can add more and more ifs like this.
> > > This is starting to look a little desperate. Such code looks unmaintainable to me (but I assume you will use some tool to generate it).
> > >
> > > What is your actual aim here? Granted a simple linear search is not going to be that performant. But pretty much anything else is going to be faster. So how much faster does it have to be; have you done any measurements? Is checking for keywords mixed in with any other input such as punctuation or numeric literals or strings or comments; what's the bigger picture?
> > One of my objectives is to understand what compilers can do on switch cases
> > and to write equivalent code.
> >
> > This binary search didn't change the performance. My tests are a bunch of files
> > that takes 9.4s-10s. And I guess all changes I did are changing less than 0.5s so
> > it hard to see.
> But how much of that is due to the lookup anyway? A quick and dirty method I used to discover how much a function contributes compared to total runtime (in the absence of proper profiling tools), is to just call it twice, when there are no harmful side-effects.
>
> It might be that your 10 seconds becomes 11 seconds, so that the relevant function takes only 1 seconds. Then an improvement of 0.5 seconds means it's twice the speed.
It is an interesting method.
Calling it twice I got 9.73s compared with 9.28s (~.4s) . The results changes a lot +- 0.5s.
A better function will improve just about 0.1s-0.2s I guess. So, again, this is more about exploring
the problem and it will not improve the performance significantly.
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2022-08-24 09:30 +0200 |
| Message-ID | <te4k2b$38uui$1@dont-email.me> |
| In reply to | #167167 |
On 24/08/2022 00:55, Thiago Adams wrote:
>
> Jus to document I also tried something like:
>
> if (ch < 'c')
> {
> if (ch == 'a') ...
> if (ch == 'b') ...
> }
> else
> {
> if (ch == 'c') ...
> if (ch == 'd') ...
> ...
> }
>
> That is similar of binary search .
> We can add more and more ifs like this.
>
gcc (and clang, I think) will sometimes generate that kind of structure
for switch statements, if the cases are too sparse for a jump table to
be appropriate.
[toc] | [prev] | [next] | [standalone]
| From | William Ahern <william@25thandClement.com> |
|---|---|
| Date | 2022-08-24 12:36 -0700 |
| Message-ID | <n6biti-t7t1.ln1@wilbur.25thandClement.com> |
| In reply to | #167177 |
David Brown <david.brown@hesbynett.no> wrote:
> On 24/08/2022 00:55, Thiago Adams wrote:
>
>>
>> Jus to document I also tried something like:
>>
>> if (ch < 'c')
>> {
>> if (ch == 'a') ...
>> if (ch == 'b') ...
>> }
>> else
>> {
>> if (ch == 'c') ...
>> if (ch == 'd') ...
>> ...
>> }
>>
>> That is similar of binary search .
>> We can add more and more ifs like this.
>>
>
> gcc (and clang, I think) will sometimes generate that kind of structure
> for switch statements, if the cases are too sparse for a jump table to
> be appropriate.
Things may have changed in the past few years, but for a long time gcc and
clang generated jump tables far less often than commonly assumed. Jump
tables may be a classic compiler optimization technique, but on modern CPUs
(with sophisticated branch prediction, etc) it's difficult to guess when a
jump table would be faster than a few conditionals, and gcc and clang seemed
to perhaps overly pessimize them, which is why it was and remains common to
explicitly rely on computed gotos, including computed gotos indexed through
an array, the method recommended in the GCC manual to avoid linking overhead
but which is usually slower than taking and dereferencing the raw label
addresses.
It's not just about sparseness and algorithmic ease of deriving a branch
location, but about how *often* specific cases are taken at runtime. If
certain cases are especially hot, a jump table might not only unnecessarily
incur extra loads, but impede the branch predictor and other machinery. In
microbenchmarks this might not be apparent, but in larger applications where
buffers and pipelines are under pressure, it often does matter.
OTOH, if you know there's a more even distribution of cases taken, such as
with a bytecode interpreter loop, then the tradeoff of a jump table load or
indirect branch on a raw computed goto makes sense--it just wouldn't be
readily apparent to the compiler sans profile-directed feedback.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2022-08-22 17:51 +0200 |
| Message-ID | <te08ma$2mrgb$1@dont-email.me> |
| In reply to | #167089 |
Use a proper language:
#include <iostream>
#include <unordered_map>
using namespace std;
int main( int argc, char **argv )
{
if( argc < 2 )
return EXIT_FAILURE;
static unordered_map<char const *, int> keywordMap =
{
{ "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 },
};
auto mapped = keywordMap.find( argv[1] );
if( mapped == keywordMap.end() )
return EXIT_FAILURE;
cout << mapped->second << endl;
}
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2022-08-22 16:55 +0100 |
| Message-ID | <8735dow9ve.fsf@bsb.me.uk> |
| In reply to | #167094 |
Bonita Montero <Bonita.Montero@gmail.com> writes: > Use a proper language: > #include <iostream> Please use the correct group. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Bonita Montero <Bonita.Montero@gmail.com> |
|---|---|
| Date | 2022-08-22 18:14 +0200 |
| Message-ID | <te0a1f$2mvv9$1@dont-email.me> |
| In reply to | #167094 |
I've benched a linear search against a map-access:
#include <iostream>
#include <unordered_map>
#include <random>
#include <concepts>
#include <chrono>
using namespace std;
using namespace chrono;
atomic_int sum( 0 );
int main( int argc, char **argv )
{
using init_pair_t = pair<char const *, int>;
static init_pair_t init[] =
{
{ "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 }
};
constexpr size_t
N = size( init ),
#if defined(NDEBUG)
ROUNDS = 1'000'000;
#else
ROUNDS = 100;
#endif
static unordered_map<char const *, int> keywordMap( init, init + N );
auto bench = [&]<typename FindFn>( FindFn findFn ) -> double
requires requires( FindFn findFn, char const *what ) { { findFn( what
) } -> same_as<int>; }
{
auto start = high_resolution_clock::now();
mt19937_64 mt;
uniform_int_distribution<size_t> uid( 0, N - 1 );
int sum = 0;
for( size_t r = ROUNDS; r--; )
sum += findFn( init[uid( mt )].first );
::sum.store( sum, memory_order_relaxed );
return (double)(int64_t)duration_cast<nanoseconds>(
high_resolution_clock::now() - start ).count() / ROUNDS;
};
double
nsIterate = bench( [&]( char const *what ) -> int
{
for( size_t i = 0; i != N; ++i )
if( strcmp( init[i].first, what ) == 0 )
return init[i].second;
return -1;
} ),
nsMap = bench( [&]( char const *what ) -> int { return
keywordMap.find( what )->second; } );
cout << nsIterate / nsMap << endl;
}
For me the difference is about factor 5.6.
So there's a small number of attempts necessary until you're beyond
a linear search.
[toc] | [prev] | [next] | [standalone]
Page 3 of 6 — ← Prev page 1 2 [3] 4 5 6 Next page →
Back to top | Article view | comp.lang.c
csiph-web