Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.c > #167089 > unrolled thread

How to optimize this search?

Back to article view | Back to comp.lang.c

Contents

  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 2 of 6 — ← Prev page 1 [2] 3 4 5 6  Next page →

#167229

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

I have a few problems with such a function. 

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

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

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

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

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

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

[toc] | [prev] | [next] | [standalone]

#167115

On Monday, August 22, 2022 at 1:17:18 PM UTC-3, Scott Lurndal wrote:
> Thiago Adams <thiago...@gmail.com> writes: 
> >On Monday, August 22, 2022 at 11:17:29 AM UTC-3, Thiago Adams wrote: 
> >> Given a c string I need to return as fast as possible the pair (if exist) of the corresponding keyword_pair. 
> >
> Use a binary search. Max comparisons for your 70+ entries would 
> be 6.

One alternative is create a hash given the first char it return the low/high
index on a sorted array.  Then we do normal binary search only at this reduced range.

enum token_type is_keyword(const char* text)
{
    static struct keyword_pair keywords[] =
    {
 /*0*/   {"NULL", TK_KEYWORD_NULL},
 /*code removed*/
 /*23*/{ "_asm", TK_KEYWORD__ASM},
 /*24*/{ "alignas", TK_KEYWORD__ALIGNAS},
 /*25*/{ "alignof", TK_KEYWORD__ALIGNOF},
 /*26*/{ "auto", TK_KEYWORD_AUTO},
 /*27*/{ "bool", TK_KEYWORD__BOOL},
 /*28*/{ "break", TK_KEYWORD_BREAK},
  /*code removed*/
    };

    /*hash*/
    static struct low_high {
        int low, high;
    } map[] =   {
         ['a'] = {.low = 24, .high = 26},
         ['b'] = {.low = 27, .high = 28},
         /*etc*/
    };
    if (text[0] >= 'N' && text[0] <= 'w')
    {
        return binary_search_str(keywords,
            map[text[0]].low, 
            map[text[0]].high,
            text);
    }
    return TK_NONE;
}

[toc] | [prev] | [next] | [standalone]

#167117

Thiago Adams <thiago.adams@gmail.com> writes:
>On Monday, August 22, 2022 at 1:17:18 PM UTC-3, Scott Lurndal wrote:
>> Thiago Adams <thiago...@gmail.com> writes: 
>> >On Monday, August 22, 2022 at 11:17:29 AM UTC-3, Thiago Adams wrote: 
>> >> Given a c string I need to return as fast as possible the pair (if exist) of the corresponding keyword_pair. 
>> >
>> Use a binary search. Max comparisons for your 70+ entries would 
>> be 6.
>
>One alternative is create a hash given the first char it return the low/high
>index on a sorted array.  Then we do normal binary search only at this reduced range.
>
>enum token_type is_keyword(const char* text)
>{
>    static struct keyword_pair keywords[] =
>    {
> /*0*/   {"NULL", TK_KEYWORD_NULL},
> /*code removed*/
> /*23*/{ "_asm", TK_KEYWORD__ASM},
> /*24*/{ "alignas", TK_KEYWORD__ALIGNAS},
> /*25*/{ "alignof", TK_KEYWORD__ALIGNOF},
> /*26*/{ "auto", TK_KEYWORD_AUTO},
> /*27*/{ "bool", TK_KEYWORD__BOOL},
> /*28*/{ "break", TK_KEYWORD_BREAK},
>  /*code removed*/
>    };
>
>    /*hash*/
>    static struct low_high {
>        int low, high;
>    } map[] =   {
>         ['a'] = {.low = 24, .high = 26},
>         ['b'] = {.low = 27, .high = 28},
>         /*etc*/
>    };
>    if (text[0] >= 'N' && text[0] <= 'w')
>    {
>        return binary_search_str(keywords,
>            map[text[0]].low, 
>            map[text[0]].high,
>            text);
>    }
>    return TK_NONE;
>}

While these experiments are enjoyable, in the real world
keep it simple and use a linear search until the
number of elements exceeds some number of table
comparisons, where that number is derived from the
clock speed.

Given a 3Ghz processor with a IPC
of 1.5, you are looking at 4.5 billion instructions
per second.  If a comparison loop required 10 instructions
per entry (for round numbers, it's likely less) (assuming
an inline string compare function that aborts on first
mismatch character), a 2000 entry table linear lookup miss would
require 20k instruction and you could execute a quarter
million lookups  that miss completely per second.  That's
worst case.

The median hit cost would be perhaps half that assuming a
uniform access distribution.

Sorting the initial list by by expected frequency of use rather
than alphabetically will reduce the average hit cost substantially
for straight linear searches.   Our mainframe compilers back at
Burroughs (where we had a 'search table' instruction in the hardware)
would order the keyword tables by expected frequency of use
(measured from many customer and internal applications).

Personally, unless the table has more than a few hundred entries, I just
use a simple linear table search, and for keyword tables, the
keywords are ordered by expected frequency of use.

[toc] | [prev] | [next] | [standalone]

#167125

On Monday, 22 August 2022 at 19:10:21 UTC+1, Scott Lurndal wrote:
> Thiago Adams writes: 
> >On Monday, August 22, 2022 at 1:17:18 PM UTC-3, Scott Lurndal wrote: 
> >> Thiago Adams writes: 
> >> >On Monday, August 22, 2022 at 11:17:29 AM UTC-3, Thiago Adams wrote: 
> >> >> Given a c string I need to return as fast as possible the pair (if exist) of the corresponding keyword_pair. 
> >> > 
> >> Use a binary search. Max comparisons for your 70+ entries would 
> >> be 6. 
> > 
> >One alternative is create a hash given the first char it return the low/high 
> >index on a sorted array. Then we do normal binary search only at this reduced range. 
> > 
> >enum token_type is_keyword(const char* text) 
> >{ 
> > static struct keyword_pair keywords[] = 
> > { 
> > /*0*/ {"NULL", TK_KEYWORD_NULL}, 
> > /*code removed*/ 
> > /*23*/{ "_asm", TK_KEYWORD__ASM}, 
> > /*24*/{ "alignas", TK_KEYWORD__ALIGNAS}, 
> > /*25*/{ "alignof", TK_KEYWORD__ALIGNOF}, 
> > /*26*/{ "auto", TK_KEYWORD_AUTO}, 
> > /*27*/{ "bool", TK_KEYWORD__BOOL}, 
> > /*28*/{ "break", TK_KEYWORD_BREAK}, 
> > /*code removed*/ 
> > }; 
> > 
> > /*hash*/ 
> > static struct low_high { 
> > int low, high; 
> > } map[] = { 
> > ['a'] = {.low = 24, .high = 26}, 
> > ['b'] = {.low = 27, .high = 28}, 
> > /*etc*/ 
> > }; 
> > if (text[0] >= 'N' && text[0] <= 'w') 
> > { 
> > return binary_search_str(keywords, 
> > map[text[0]].low, 
> > map[text[0]].high, 
> > text); 
> > } 
> > return TK_NONE; 
> >}
> While these experiments are enjoyable, in the real world 
> keep it simple and use a linear search until the 
> number of elements exceeds some number of table 
> comparisons, where that number is derived from the 
> clock speed. 

Rather strange advice. Would you also advocate the use of bubble sort in the 'real world'?

The OP is posting /because/ they want something faster than a linear search.

But I tried your idea on one of my compilers: doing a linear search to first see if an identifier was a keyword.

Parsing got about 7 times slower (from 2.1Mlps to 0.3Mlps). Overall compiler throughout reduced by 2-4 times. This is for some 250 keywords in arbitrary order.

Imagine if you could speed up any compiler by 2-4 times just by adding 100 lines of code or even less.

A linear search might suffice for a toy or experimental product working on small inputs.

[toc] | [prev] | [next] | [standalone]

#167126

bart c <bart4858@gmail.com> writes:
> On Monday, 22 August 2022 at 19:10:21 UTC+1, Scott Lurndal wrote:
>> Thiago Adams writes: 
>> >On Monday, August 22, 2022 at 1:17:18 PM UTC-3, Scott Lurndal wrote: 
>> >> Thiago Adams writes: 
>> >> >On Monday, August 22, 2022 at 11:17:29 AM UTC-3, Thiago Adams wrote: 
>> >> >> Given a c string I need to return as fast as possible the pair (if exist) of the corresponding keyword_pair. 
>> >> > 
>> >> Use a binary search. Max comparisons for your 70+ entries would 
>> >> be 6. 
>> > 
>> >One alternative is create a hash given the first char it return the low/high 
>> >index on a sorted array. Then we do normal binary search only at this reduced range. 
>> > 
>> >enum token_type is_keyword(const char* text) 
>> >{ 
>> > static struct keyword_pair keywords[] = 
>> > { 
>> > /*0*/ {"NULL", TK_KEYWORD_NULL}, 
>> > /*code removed*/ 
>> > /*23*/{ "_asm", TK_KEYWORD__ASM}, 
>> > /*24*/{ "alignas", TK_KEYWORD__ALIGNAS}, 
>> > /*25*/{ "alignof", TK_KEYWORD__ALIGNOF}, 
>> > /*26*/{ "auto", TK_KEYWORD_AUTO}, 
>> > /*27*/{ "bool", TK_KEYWORD__BOOL}, 
>> > /*28*/{ "break", TK_KEYWORD_BREAK}, 
>> > /*code removed*/ 
>> > }; 
>> > 
>> > /*hash*/ 
>> > static struct low_high { 
>> > int low, high; 
>> > } map[] = { 
>> > ['a'] = {.low = 24, .high = 26}, 
>> > ['b'] = {.low = 27, .high = 28}, 
>> > /*etc*/ 
>> > }; 
>> > if (text[0] >= 'N' && text[0] <= 'w') 
>> > { 
>> > return binary_search_str(keywords, 
>> > map[text[0]].low, 
>> > map[text[0]].high, 
>> > text); 
>> > } 
>> > return TK_NONE; 
>> >}
>> While these experiments are enjoyable, in the real world 
>> keep it simple and use a linear search until the 
>> number of elements exceeds some number of table 
>> comparisons, where that number is derived from the 
>> clock speed. 
>
> Rather strange advice. Would you also advocate the use of bubble sort in the 'real world'?
>
> The OP is posting /because/ they want something faster than a linear search.
>
> But I tried your idea on one of my compilers: doing a linear search to first see if an identifier was a keyword.
>
> Parsing got about 7 times slower (from 2.1Mlps to 0.3Mlps). Overall compiler throughout reduced by 2-4 times. This is for some 250 keywords in arbitrary order.
>
> Imagine if you could speed up any compiler by 2-4 times just by adding 100 lines of code or even less.
>
> A linear search might suffice for a toy or experimental product working on small inputs.

So with that change, your compiler spent 50-75% of its time running
linear searches on a list of 250 keywords?

That's surprising.  I can't help wondering if there was some additional
inefficiency in the code.  Would you care to share a snippet?

-- 
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]

#167128

On Monday, 22 August 2022 at 23:38:13 UTC+1, Keith Thompson wrote:
> bart c writes: 

> > Rather strange advice. Would you also advocate the use of bubble sort in the 'real world'? 
> > 
> > The OP is posting /because/ they want something faster than a linear search. 
> > 
> > But I tried your idea on one of my compilers: doing a linear search to first see if an identifier was a keyword. 
> > 
> > Parsing got about 7 times slower (from 2.1Mlps to 0.3Mlps). Overall compiler throughout reduced by 2-4 times. This is for some 250 keywords in arbitrary order. 
> > 
> > Imagine if you could speed up any compiler by 2-4 times just by adding 100 lines of code or even less. 
> > 
> > A linear search might suffice for a toy or experimental product working on small inputs.
> So with that change, your compiler spent 50-75% of its time running 
> linear searches on a list of 250 keywords? 
> 
> That's surprising. I can't help wondering if there was some additional 
> inefficiency in the code. Would you care to share a snippet? 

Yes, the inefficiency is doing a linear search at a place which is a bottleneck! Processing the next alphanumeric token. Surely that's obvious?

It is otherwise a pretty fast compiler. Here however is the normal code (sorry can't guarantee the formatting under Googlegroups):

    lookup(lxsvalue, lxsptr-lxsvalue, hashw(hsum))

This is done after a series of alphanumeric characters has been identified as a token; it does a lookup via a hashtable which contains all keywords, reserved words, and user-identifiers (only one generic version of each unique identifier; multiple instances of those are put into a linked list of duplicate names; that /is/ searched linearly when they need resolving).

This is the code that was added just before that to do this experiment (clearly, not C):

    length:=lxsptr-lxsvalue
    memcpy(&str, lxsvalue, length)
    str[length+1]:=0
    for i to nkeywords do
        if strcmp(str, keywords[i].name)=0 then
            d:=keywords[i]
            nextlx.symptr:=d
            nextlx.symbol:=d.symbol
            nextlx.subcode:=d.subcode
            return
        fi
    od

    lookup(lxsvalue, lxsptr-lxsvalue, hashw(hsum))
    return

keywords[] is a compact linear table populated from the hashtable after the keywords have been added, but before any user identifiers.

[toc] | [prev] | [next] | [standalone]

#167132

bart c <bart4858@gmail.com> writes:

> On Monday, 22 August 2022 at 23:38:13 UTC+1, Keith Thompson wrote:
>> bart c writes: 
>
>> > Rather strange advice. Would you also advocate the use of bubble sort in the 'real world'? 
>> > 
>> > The OP is posting /because/ they want something faster than a linear search. 
>> > 
>> > But I tried your idea on one of my compilers: doing a linear search to first see if an identifier was a keyword. 
>> > 
>> > Parsing got about 7 times slower (from 2.1Mlps to 0.3Mlps). Overall compiler throughout reduced by 2-4 times. This is for some 250 keywords in arbitrary order. 
>> > 
>> > Imagine if you could speed up any compiler by 2-4 times just by adding 100 lines of code or even less. 
>> > 
>> > A linear search might suffice for a toy or experimental product working on small inputs.
>> So with that change, your compiler spent 50-75% of its time running 
>> linear searches on a list of 250 keywords? 
>> 
>> That's surprising. I can't help wondering if there was some additional 
>> inefficiency in the code. Would you care to share a snippet? 
>
> Yes, the inefficiency is doing a linear search at a place which is a
> bottleneck! Processing the next alphanumeric token. Surely that's
> obvious?
>
> It is otherwise a pretty fast compiler. Here however is the normal
> code (sorry can't guarantee the formatting under Googlegroups):
>
>     lookup(lxsvalue, lxsptr-lxsvalue, hashw(hsum))
>
> This is done after a series of alphanumeric characters has been
> identified as a token; it does a lookup via a hashtable which contains
> all keywords, reserved words, and user-identifiers (only one generic
> version of each unique identifier; multiple instances of those are put
> into a linked list of duplicate names; that /is/ searched linearly
> when they need resolving).
>
> This is the code that was added just before that to do this
> experiment (clearly, not C):
>
>     length:=lxsptr-lxsvalue
>     memcpy(&str, lxsvalue, length)
>     str[length+1]:=0

So you need to copy the string?

>     for i to nkeywords do
>         if strcmp(str, keywords[i].name)=0 then

In C, one would try to avoid a copy and use strncmp here.

>             d:=keywords[i]
>             nextlx.symptr:=d
>             nextlx.symbol:=d.symbol
>             nextlx.subcode:=d.subcode
>             return
>         fi
>     od
>
>     lookup(lxsvalue, lxsptr-lxsvalue, hashw(hsum))
>     return

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#167133

On Tuesday, 23 August 2022 at 01:18:34 UTC+1, Ben Bacarisse wrote:
> bart c writes: 
> 
> > On Monday, 22 August 2022 at 23:38:13 UTC+1, Keith Thompson wrote: 
> >> bart c writes: 
> > 
> >> > Rather strange advice. Would you also advocate the use of bubble sort in the 'real world'? 
> >> > 
> >> > The OP is posting /because/ they want something faster than a linear search. 
> >> > 
> >> > But I tried your idea on one of my compilers: doing a linear search to first see if an identifier was a keyword. 
> >> > 
> >> > Parsing got about 7 times slower (from 2.1Mlps to 0.3Mlps). Overall compiler throughout reduced by 2-4 times. This is for some 250 keywords in arbitrary order. 
> >> > 
> >> > Imagine if you could speed up any compiler by 2-4 times just by adding 100 lines of code or even less. 
> >> > 
> >> > A linear search might suffice for a toy or experimental product working on small inputs. 
> >> So with that change, your compiler spent 50-75% of its time running 
> >> linear searches on a list of 250 keywords? 
> >> 
> >> That's surprising. I can't help wondering if there was some additional 
> >> inefficiency in the code. Would you care to share a snippet? 
> > 
> > Yes, the inefficiency is doing a linear search at a place which is a 
> > bottleneck! Processing the next alphanumeric token. Surely that's 
> > obvious? 
> > 
> > It is otherwise a pretty fast compiler. Here however is the normal 
> > code (sorry can't guarantee the formatting under Googlegroups): 
> > 
> > lookup(lxsvalue, lxsptr-lxsvalue, hashw(hsum)) 
> > 
> > This is done after a series of alphanumeric characters has been 
> > identified as a token; it does a lookup via a hashtable which contains 
> > all keywords, reserved words, and user-identifiers (only one generic 
> > version of each unique identifier; multiple instances of those are put 
> > into a linked list of duplicate names; that /is/ searched linearly 
> > when they need resolving). 
> > 
> > This is the code that was added just before that to do this 
> > experiment (clearly, not C): 
> > 
> > length:=lxsptr-lxsvalue 
> > memcpy(&str, lxsvalue, length) 
> > str[length+1]:=0

> So you need to copy the string?

Well, it's not zero-terminated in memory (still pointing into the source at this point).

> > for i to nkeywords do 
> > if strcmp(str, keywords[i].name)=0 then

> In C, one would try to avoid a copy and use strncmp here.

OK, if I do that (it doesn't work unless I check the lengths match first), then strncmp or memcmp both make it significantly faster, although still quite a bit slower than normal (surprisingly as I've never previously notices much difference).

(1.5 seconds to parse 740Kloc, compared with 2.25 using strcmp, but normal speed is 0.3 seconds.)

[toc] | [prev] | [next] | [standalone]

#167131

bart c <bart4858@gmail.com> wrote:
> On Monday, 22 August 2022 at 19:10:21 UTC+1, Scott Lurndal wrote:
> > Thiago Adams writes: 
> > >On Monday, August 22, 2022 at 1:17:18 PM UTC-3, Scott Lurndal wrote: 
> > >> Thiago Adams writes: 
> > >> >On Monday, August 22, 2022 at 11:17:29 AM UTC-3, Thiago Adams wrote: 
> > >> >> Given a c string I need to return as fast as possible the pair (if exist) of the corresponding keyword_pair. 
> > >> > 
> > >> Use a binary search. Max comparisons for your 70+ entries would 
> > >> be 6. 
> > > 
> > >One alternative is create a hash given the first char it return the low/high 
> > >index on a sorted array. Then we do normal binary search only at this reduced range. 
> > > 
> > >enum token_type is_keyword(const char* text) 
> > >{ 
> > > static struct keyword_pair keywords[] = 
> > > { 
> > > /*0*/ {"NULL", TK_KEYWORD_NULL}, 
> > > /*code removed*/ 
> > > /*23*/{ "_asm", TK_KEYWORD__ASM}, 
> > > /*24*/{ "alignas", TK_KEYWORD__ALIGNAS}, 
> > > /*25*/{ "alignof", TK_KEYWORD__ALIGNOF}, 
> > > /*26*/{ "auto", TK_KEYWORD_AUTO}, 
> > > /*27*/{ "bool", TK_KEYWORD__BOOL}, 
> > > /*28*/{ "break", TK_KEYWORD_BREAK}, 
> > > /*code removed*/ 
> > > }; 
> > > 
> > > /*hash*/ 
> > > static struct low_high { 
> > > int low, high; 
> > > } map[] = { 
> > > ['a'] = {.low = 24, .high = 26}, 
> > > ['b'] = {.low = 27, .high = 28}, 
> > > /*etc*/ 
> > > }; 
> > > if (text[0] >= 'N' && text[0] <= 'w') 
> > > { 
> > > return binary_search_str(keywords, 
> > > map[text[0]].low, 
> > > map[text[0]].high, 
> > > text); 
> > > } 
> > > return TK_NONE; 
> > >}
> > While these experiments are enjoyable, in the real world 
> > keep it simple and use a linear search until the 
> > number of elements exceeds some number of table 
> > comparisons, where that number is derived from the 
> > clock speed. 
> 
> Rather strange advice. Would you also advocate the use of bubble sort in the 'real world'?
> 
> The OP is posting /because/ they want something faster than a linear search.
> 
> But I tried your idea on one of my compilers: doing a linear search to first see if an identifier was a keyword.
> 
> Parsing got about 7 times slower (from 2.1Mlps to 0.3Mlps). Overall compiler throughout reduced by 2-4 times. This is for some 250 keywords in arbitrary order.
>

With reasonale assumption of one operator per line, linear search is
doing _more_ searches than in Scott worst case estimate (but one
would expect better from such short list).

Your compiler is highly tuned for compilation speed.  If you did
the same to gcc you probably would be unable to measure speed
difference.  OTOH if Thiago wants high compilation speed, then
following your advice is reasonable.

> Imagine if you could speed up any compiler by 2-4 times just by adding 100 lines of code or even less.
> 
> A linear search might suffice for a toy or experimental product working on small inputs.

Actually there are real compilers using linear search.  Some are considerd
to be very fast: they are much faster then gcc... 

Concerning code size: in non-toy compiler I want dynamically growing
symbol table, so that compiler uses tiny amount of memory on small
programs but can handle very big ones.  Fast resizable hash table is
likely to be much bigger than 100 lines (but less than 500 lines
is reasonable).

-- 
                              Waldek Hebisch

[toc] | [prev] | [next] | [standalone]

#167134

On Tuesday, 23 August 2022 at 01:08:00 UTC+1, anti... wrote:
> bart c wrote: 
> > On Monday, 22 August 2022 at 19:10:21 UTC+1, Scott Lurndal wrote: 
> > > Thiago Adams writes: 
> > > >On Monday, August 22, 2022 at 1:17:18 PM UTC-3, Scott Lurndal wrote: 
> > > >> Thiago Adams writes: 
> > > >> >On Monday, August 22, 2022 at 11:17:29 AM UTC-3, Thiago Adams wrote: 
> > > >> >> Given a c string I need to return as fast as possible the pair (if exist) of the corresponding keyword_pair. 
> > > >> > 
> > > >> Use a binary search. Max comparisons for your 70+ entries would 
> > > >> be 6. 
> > > > 
> > > >One alternative is create a hash given the first char it return the low/high 
> > > >index on a sorted array. Then we do normal binary search only at this reduced range. 
> > > > 
> > > >enum token_type is_keyword(const char* text) 
> > > >{ 
> > > > static struct keyword_pair keywords[] = 
> > > > { 
> > > > /*0*/ {"NULL", TK_KEYWORD_NULL}, 
> > > > /*code removed*/ 
> > > > /*23*/{ "_asm", TK_KEYWORD__ASM}, 
> > > > /*24*/{ "alignas", TK_KEYWORD__ALIGNAS}, 
> > > > /*25*/{ "alignof", TK_KEYWORD__ALIGNOF}, 
> > > > /*26*/{ "auto", TK_KEYWORD_AUTO}, 
> > > > /*27*/{ "bool", TK_KEYWORD__BOOL}, 
> > > > /*28*/{ "break", TK_KEYWORD_BREAK}, 
> > > > /*code removed*/ 
> > > > }; 
> > > > 
> > > > /*hash*/ 
> > > > static struct low_high { 
> > > > int low, high; 
> > > > } map[] = { 
> > > > ['a'] = {.low = 24, .high = 26}, 
> > > > ['b'] = {.low = 27, .high = 28}, 
> > > > /*etc*/ 
> > > > }; 
> > > > if (text[0] >= 'N' && text[0] <= 'w') 
> > > > { 
> > > > return binary_search_str(keywords, 
> > > > map[text[0]].low, 
> > > > map[text[0]].high, 
> > > > text); 
> > > > } 
> > > > return TK_NONE; 
> > > >} 
> > > While these experiments are enjoyable, in the real world 
> > > keep it simple and use a linear search until the 
> > > number of elements exceeds some number of table 
> > > comparisons, where that number is derived from the 
> > > clock speed. 
> > 
> > Rather strange advice. Would you also advocate the use of bubble sort in the 'real world'? 
> > 
> > The OP is posting /because/ they want something faster than a linear search. 
> > 
> > But I tried your idea on one of my compilers: doing a linear search to first see if an identifier was a keyword. 
> > 
> > Parsing got about 7 times slower (from 2.1Mlps to 0.3Mlps). Overall compiler throughout reduced by 2-4 times. This is for some 250 keywords in arbitrary order. 
> >
> With reasonale assumption of one operator per line, linear search is 
> doing _more_ searches than in Scott worst case estimate (but one 
> would expect better from such short list). 
> 
> Your compiler is highly tuned for compilation speed. If you did 
> the same to gcc you probably would be unable to measure speed 
> difference. OTOH if Thiago wants high compilation speed, then 
> following your advice is reasonable.
> > Imagine if you could speed up any compiler by 2-4 times just by adding 100 lines of code or even less. 
> > 
> > A linear search might suffice for a toy or experimental product working on small inputs.
> Actually there are real compilers using linear search. Some are considerd 
> to be very fast: they are much faster then gcc... 

I use linear search in quite a few places as well. Mainly for linked lists and where typical lengths are not long. Not however for symbol table lookups, but the hashtable for that is the most sophisticated data structure I use.

As for gcc, I used to have a version of my compiler running as interpreted bytecode; it was still twice as fast as even gcc-O0.

> Concerning code size: in non-toy compiler I want dynamically growing 
> symbol table, so that compiler uses tiny amount of memory on small 
> programs but can handle very big ones. Fast resizable hash table is 
> likely to be much bigger than 100 lines (but less than 500 lines 
> is reasonable). 

I can't find a compiler version with a resized hash table, but I'm sure I must have done it (or maybe it's part of the Dict implementation of an interpreter).

I don't think it will take an extra 400 lines; you just need to keep track of capacity, and move to a bigger table as needed. Then the contents need to be rehashed into the bigger table. Say an extra 100 lines. Or a cheap solution is to have the table size as a compiler option.

[toc] | [prev] | [next] | [standalone]

#167135

bart c <bart4858@gmail.com> wrote:
> On Tuesday, 23 August 2022 at 01:08:00 UTC+1, anti... wrote:
> > bart c wrote: 
> > > On Monday, 22 August 2022 at 19:10:21 UTC+1, Scott Lurndal wrote: 
> > > > Thiago Adams writes: 
> > > > >On Monday, August 22, 2022 at 1:17:18 PM UTC-3, Scott Lurndal wrote: 
> > > > >> Thiago Adams writes: 
> > > > >> >On Monday, August 22, 2022 at 11:17:29 AM UTC-3, Thiago Adams wrote: 
> > > > >> >> Given a c string I need to return as fast as possible the pair (if exist) of the corresponding keyword_pair. 
> > > > >> > 
> > > > >> Use a binary search. Max comparisons for your 70+ entries would 
> > > > >> be 6. 
> > > > > 
> > > > >One alternative is create a hash given the first char it return the low/high 
> > > > >index on a sorted array. Then we do normal binary search only at this reduced range. 
> > > > > 
> > > > >enum token_type is_keyword(const char* text) 
> > > > >{ 
> > > > > static struct keyword_pair keywords[] = 
> > > > > { 
> > > > > /*0*/ {"NULL", TK_KEYWORD_NULL}, 
> > > > > /*code removed*/ 
> > > > > /*23*/{ "_asm", TK_KEYWORD__ASM}, 
> > > > > /*24*/{ "alignas", TK_KEYWORD__ALIGNAS}, 
> > > > > /*25*/{ "alignof", TK_KEYWORD__ALIGNOF}, 
> > > > > /*26*/{ "auto", TK_KEYWORD_AUTO}, 
> > > > > /*27*/{ "bool", TK_KEYWORD__BOOL}, 
> > > > > /*28*/{ "break", TK_KEYWORD_BREAK}, 
> > > > > /*code removed*/ 
> > > > > }; 
> > > > > 
> > > > > /*hash*/ 
> > > > > static struct low_high { 
> > > > > int low, high; 
> > > > > } map[] = { 
> > > > > ['a'] = {.low = 24, .high = 26}, 
> > > > > ['b'] = {.low = 27, .high = 28}, 
> > > > > /*etc*/ 
> > > > > }; 
> > > > > if (text[0] >= 'N' && text[0] <= 'w') 
> > > > > { 
> > > > > return binary_search_str(keywords, 
> > > > > map[text[0]].low, 
> > > > > map[text[0]].high, 
> > > > > text); 
> > > > > } 
> > > > > return TK_NONE; 
> > > > >} 
> > > > While these experiments are enjoyable, in the real world 
> > > > keep it simple and use a linear search until the 
> > > > number of elements exceeds some number of table 
> > > > comparisons, where that number is derived from the 
> > > > clock speed. 
> > > 
> > > Rather strange advice. Would you also advocate the use of bubble sort in the 'real world'? 
> > > 
> > > The OP is posting /because/ they want something faster than a linear search. 
> > > 
> > > But I tried your idea on one of my compilers: doing a linear search to first see if an identifier was a keyword. 
> > > 
> > > Parsing got about 7 times slower (from 2.1Mlps to 0.3Mlps). Overall compiler throughout reduced by 2-4 times. This is for some 250 keywords in arbitrary order. 
> > >
> > With reasonale assumption of one operator per line, linear search is 
> > doing _more_ searches than in Scott worst case estimate (but one 
> > would expect better from such short list). 
> > 
> > Your compiler is highly tuned for compilation speed. If you did 
> > the same to gcc you probably would be unable to measure speed 
> > difference. OTOH if Thiago wants high compilation speed, then 
> > following your advice is reasonable.
> > > Imagine if you could speed up any compiler by 2-4 times just by adding 100 lines of code or even less. 
> > > 
> > > A linear search might suffice for a toy or experimental product working on small inputs.
> > Actually there are real compilers using linear search. Some are considerd 
> > to be very fast: they are much faster then gcc... 
> 
> I use linear search in quite a few places as well. Mainly for linked lists and where typical lengths are not long. Not however for symbol table lookups, but the hashtable for that is the most sophisticated data structure I use.
> 
> As for gcc, I used to have a version of my compiler running as interpreted bytecode; it was still twice as fast as even gcc-O0.
> 
> > Concerning code size: in non-toy compiler I want dynamically growing 
> > symbol table, so that compiler uses tiny amount of memory on small 
> > programs but can handle very big ones. Fast resizable hash table is 
> > likely to be much bigger than 100 lines (but less than 500 lines 
> > is reasonable). 
> 
> I can't find a compiler version with a resized hash table, but I'm sure I must have done it (or maybe it's part of the Dict implementation of an interpreter).
> 
> I don't think it will take an extra 400 lines; you just need to keep track of capacity, and move to a bigger table as needed. Then the contents need to be rehashed into the bigger table. Say an extra 100 lines. Or a cheap solution is to have the table size as a compiler option.

Well, 500 was upper estimate.  My resizable hashtab is 305 wc lines,
164 is hashtab proper, rest is header files (with declaration of
data structures) and few utilities.  One could probably make it
smaller, but I doubt that one could shrink it to 100 lines without
making it unreadable.  And it has no frills, so compiler author
may wish to add to it...

BTW: GNU folks in their utility library have file "hashtab.c",
998 wc lines...

-- 
                              Waldek Hebisch

[toc] | [prev] | [next] | [standalone]

#167136

On 23/08/2022 00:22, bart c wrote:
> On Monday, 22 August 2022 at 19:10:21 UTC+1, Scott Lurndal wrote:

>> While these experiments are enjoyable, in the real world keep it
>> simple and use a linear search until the number of elements exceeds
>> some number of table comparisons, where that number is derived from
>> the clock speed.
> 
> Rather strange advice. Would you also advocate the use of bubble sort
> in the 'real world'?

That's a non-sequitor.  There are quite clearly situations where a 
linear search is better than a binary search or hash-map, much less so 
for a bubble sort compared to other sorts.

> 
> The OP is posting /because/ they want something faster than a linear
> search.
> 

He is trying to find the fastest way to do the mapping - if that's a 
linear search, then he'll be happy with a linear search.

In the good old days, it was relatively easy to guess the speed of code. 
  And you could use simple algorithmic complexity arguments to see that 
a binary search would be faster than a linear search for more than about 
3 or 4 items.  But now the key factors for speed here will be branch 
prediction, jump target caches, and the like.  Binary searches are 
terrible for branch prediction, while linear searches are much faster. 
The cross-over point when a binary search beats a linear search is far 
higher than it used to be, and will vary wildly by processor - if the 
processor can speculatively execute both sides of a branch far enough 
for the cost of mispredicting to be low, binary search may be fine even 
for small sizes.  If not, then binary searches should be avoided 
whenever speed is of the essence.

My guess for the best average result would be to put the keywords in a 
sorted list.  Have a table of 32 entries for the first letter as 
pointers to a starting point in the keyword table - so a single-letter 
dummy hash on the first letter, followed by a linear search.

But real-life measurements may show something else entirely.

> But I tried your idea on one of my compilers: doing a linear search
> to first see if an identifier was a keyword.
> 

If that is for your language, then I believe you have a lot more 
keywords, which will make a difference.

> Parsing got about 7 times slower (from 2.1Mlps to 0.3Mlps). Overall
> compiler throughout reduced by 2-4 times. This is for some 250
> keywords in arbitrary order.
> 
> Imagine if you could speed up any compiler by 2-4 times just by
> adding 100 lines of code or even less.
> 
> A linear search might suffice for a toy or experimental product
> working on small inputs.
> 

[toc] | [prev] | [next] | [standalone]

#167139

On Tuesday, 23 August 2022 at 07:50:20 UTC+1, David Brown wrote:
> On 23/08/2022 00:22, bart c wrote: 
> > On Monday, 22 August 2022 at 19:10:21 UTC+1, Scott Lurndal wrote: 
> 
> >> While these experiments are enjoyable, in the real world keep it 
> >> simple and use a linear search until the number of elements exceeds 
> >> some number of table comparisons, where that number is derived from 
> >> the clock speed. 
> > 
> > Rather strange advice. Would you also advocate the use of bubble sort 
> > in the 'real world'?
> That's a non-sequitor. There are quite clearly situations where a 
> linear search is better than a binary search or hash-map, much less so 
> for a bubble sort compared to other sorts.
> > 
> > The OP is posting /because/ they want something faster than a linear 
> > search. 
> >
> He is trying to find the fastest way to do the mapping - if that's a 
> linear search, then he'll be happy with a linear search. 

I assume he's already tried a linear traversal.

> In the good old days, it was relatively easy to guess the speed of code. 
> And you could use simple algorithmic complexity arguments to see that 
> a binary search would be faster than a linear search for more than about 
> 3 or 4 items. But now the key factors for speed here will be branch 
> prediction, jump target caches, and the like. Binary searches are 
> terrible for branch prediction, while linear searches are much faster. 
> The cross-over point when a binary search beats a linear search is far 
> higher than it used to be, and will vary wildly by processor - if the 
> processor can speculatively execute both sides of a branch far enough 
> for the cost of mispredicting to be low, binary search may be fine even 
> for small sizes. If not, then binary searches should be avoided 
> whenever speed is of the essence. 
> 
> My guess for the best average result would be to put the keywords in a 
> sorted list. Have a table of 32 entries for the first letter as 
> pointers to a starting point in the keyword table - so a single-letter 
> dummy hash on the first letter, followed by a linear search. 

(I think he said he did and that and got a worthwhile speed up. So already better than linear.)


> But real-life measurements may show something else entirely.
> > But I tried your idea on one of my compilers: doing a linear search 
> > to first see if an identifier was a keyword. 
> >
> If that is for your language, then I believe you have a lot more 
> keywords, which will make a difference.

Scott mentioned 'a few hundred' entries before trying a difference approach.

But I have tried this on my C compiler. There, there were 77 keywords. Overall throughput was reduced by about 20% (timings were erratic but it was something like that). But that also had a more complicated, multi-layer lexer.

(This is using Ben's suggestion to compare as blocks of bytes not strings. A side-effect of that is that comparisons are only done when string lengths match, so the compare function is not called for every keyword. This requires that the linear table stores the length of each keyword.)

I also extracted the OP's list of 75 C reserved words into my scripting language. I put them into a simple linear list of strings, and into a hash table (a built-in type).

I then did 5 million lookups of 3 different words (from the beginning, middle and end) using code like this (.... acts as tab):

fun findlinear(w)=
....return w in keywords
end

fun findhash(w)=
....return hashtable{w,-1}
end

The hash method consistently took about 0.22 seconds. The linear search was 0.2, 1.9 and 3.8 seconds. Both searches are implemented in native code (inside the interpreter).

(BTW the hash-table implementation in my C compiler comprises about 120 lines of code, of which 55 is to do with resizing (I found that compiler in the end). So only a few dozen lines is needed.)

[toc] | [prev] | [next] | [standalone]

#167146

On 23/08/2022 13:18, bart c wrote:
> On Tuesday, 23 August 2022 at 07:50:20 UTC+1, David Brown wrote:
>> On 23/08/2022 00:22, bart c wrote:
>>> On Monday, 22 August 2022 at 19:10:21 UTC+1, Scott Lurndal
>>> wrote:
>> 
>>>> While these experiments are enjoyable, in the real world keep
>>>> it simple and use a linear search until the number of elements
>>>> exceeds some number of table comparisons, where that number is
>>>> derived from the clock speed.
>>> 
>>> Rather strange advice. Would you also advocate the use of bubble
>>> sort in the 'real world'?
>> That's a non-sequitor. There are quite clearly situations where a 
>> linear search is better than a binary search or hash-map, much less
>> so for a bubble sort compared to other sorts.
>>> 
>>> The OP is posting /because/ they want something faster than a
>>> linear search.
>>> 
>> He is trying to find the fastest way to do the mapping - if that's
>> a linear search, then he'll be happy with a linear search.
> 
> I assume he's already tried a linear traversal.
> 

I'm trying not to assume things.  I am also not assuming that there /is/ 
an approach that is faster than linear searching, or faster than 
whatever he has tried so far.

>> In the good old days, it was relatively easy to guess the speed of
>> code. And you could use simple algorithmic complexity arguments to
>> see that a binary search would be faster than a linear search for
>> more than about 3 or 4 items. But now the key factors for speed
>> here will be branch prediction, jump target caches, and the like.
>> Binary searches are terrible for branch prediction, while linear
>> searches are much faster. The cross-over point when a binary search
>> beats a linear search is far higher than it used to be, and will
>> vary wildly by processor - if the processor can speculatively
>> execute both sides of a branch far enough for the cost of
>> mispredicting to be low, binary search may be fine even for small
>> sizes. If not, then binary searches should be avoided whenever
>> speed is of the essence.
>> 
>> My guess for the best average result would be to put the keywords
>> in a sorted list. Have a table of 32 entries for the first letter
>> as pointers to a starting point in the keyword table - so a
>> single-letter dummy hash on the first letter, followed by a linear
>> search.
> 
> (I think he said he did and that and got a worthwhile speed up. So
> already better than linear.)
> 

OK.  I have probably skipped over some of the posts in this thread, and 
missed that.

> 
>> But real-life measurements may show something else entirely.
>>> But I tried your idea on one of my compilers: doing a linear
>>> search to first see if an identifier was a keyword.
>>> 
>> If that is for your language, then I believe you have a lot more 
>> keywords, which will make a difference.
> 
> Scott mentioned 'a few hundred' entries before trying a difference
> approach.
> 
> But I have tried this on my C compiler. There, there were 77
> keywords. Overall throughput was reduced by about 20% (timings were
> erratic but it was something like that). But that also had a more
> complicated, multi-layer lexer.
> 
> (This is using Ben's suggestion to compare as blocks of bytes not
> strings. A side-effect of that is that comparisons are only done when
> string lengths match, so the compare function is not called for every
> keyword. This requires that the linear table stores the length of
> each keyword.)

That sounds like a bad idea to me.  Comparing blocks of bytes with a 
fixed size is the ideal - and that fixed size should ideally be 8.  As 
long as you are careful with your types, your alignments, and your use 
of a good optimising C compiler, your comparisons are now just a single 
64-bit integer comparison.  (Clearly both the string for the lookup and 
the strings in the table need consistent padding.)  Some keywords are 
longer than 8 characters and need extra checking once the first lookup 
is done (all are, I think, distinguishable by their first 8 characters 
except _Decimal128, _Decimal32 and _Decimal64).

A smart enough C compiler might automatically vectorise this for SIMD 
instructions, if told it is targeting a suitable processor.

> 
> I also extracted the OP's list of 75 C reserved words into my
> scripting language. I put them into a simple linear list of strings,
> and into a hash table (a built-in type).
> 
> I then did 5 million lookups of 3 different words (from the
> beginning, middle and end) using code like this (.... acts as tab):
> 
> fun findlinear(w)= ....return w in keywords end
> 
> fun findhash(w)= ....return hashtable{w,-1} end
> 
> The hash method consistently took about 0.22 seconds. The linear
> search was 0.2, 1.9 and 3.8 seconds. Both searches are implemented in
> native code (inside the interpreter).
> 
> (BTW the hash-table implementation in my C compiler comprises about
> 120 lines of code, of which 55 is to do with resizing (I found that
> compiler in the end). So only a few dozen lines is needed.)

Be aware that it is difficult to test this kind of thing well.  Testing 
repeatedly with only a few words can give hugely different effects from 
branch target buffers and branch prediction than you'd get from a random 
mix of all the keywords.

Real-life source code, is different again - the mix of keywords is far 
from random.  It might even be worth doing a linear search for the most 
common keywords such as "if" and "int", then moving to a hash table for 
rare ones such as "thread_local" and "goto".  Or to keep it simpler, 
have a linear search but with the table ordered by the frequency of the 
keywords in real code - who cares if keywords like "_Imaginary" or 
"_BitInt" are found more slowly?

[toc] | [prev] | [next] | [standalone]

#167120

Scott Lurndal <scott@slp53.sl.home> wrote:
> Thiago Adams <thiago.adams@gmail.com> writes:
> >On Monday, August 22, 2022 at 11:17:29 AM UTC-3, Thiago Adams wrote:
> >> Given a c string I need to return as fast as possible the pair (if exist) of the corresponding keyword_pair. 
> >
> 
> Use a binary search.  Max comparisons for your 70+ entries would
> be 6.

Around 2004-2005 Frank Heckenbach did some optimization of
search for record fields in Gnu Pascal.  His measurements
indicated that below 50 fields linear search was faster,
above binary search won.  Basically, in linear search
there is 1 mispredicted branch and a lot of predictable ones.
In binary search about half of branches is likely to
be misprediced.  Assuming that mispredicted branch costs
about 10 predicted ones leads to similar level for
"breakeven".   Of course machines changed and branch
predictors are better now, but it is not clear to me
if improvements to branch predictors help in case
of binary search.

Of course there is a little catch: in Gnu Pascal search
was done after symbol table lookup so all comparisons
were pointer comparisons.  Apparently Thiago works
with strings which if done naively needs several character
comparisons (with their own chances for mispredicted
branches).  But if length is limited one can pack the
whole string or first part in machine word and do
comparison as single instruction.  Only in case of
match with long entry one needs extra check to
verify rest of match.

-- 
                              Waldek Hebisch

[toc] | [prev] | [next] | [standalone]

#167092

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.

Since the set is know at compile time, a "perfect hash" would be a good
candidate.  (Searching for "perfect hash" should work.)

But why as fast as possible?  Tools like the one you appear to be
building often have significant IO costs, so a keyword look-up is
unlikely to be very significant.

> struct keyword_pair{
>     const char* lexeme;
>     int token;
> };
>
> struct keyword_pair[] = {
> { "NULL", 0},
> { "_Alignas", 1},
> { "_Atomic", 2},
> { "_BitInt", 3},

etc...

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#167099

On Monday, August 22, 2022 at 12:34:15 PM 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.
> Since the set is know at compile time, a "perfect hash" would be a good 
> candidate. (Searching for "perfect hash" should work.) 

Yes but let's say we have a perfect hash. Then I find 
the index of keyword.. and then I guess a strcmp is also 
required to check against conflicts. Because the input
can be any string.
So there is at least two operations hash and strcmp.

[toc] | [prev] | [next] | [standalone]

#167106

Thiago Adams <thiago.adams@gmail.com> writes:

> On Monday, August 22, 2022 at 12:34:15 PM 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.
>> Since the set is know at compile time, a "perfect hash" would be a good 
>> candidate. (Searching for "perfect hash" should work.) 
>
> Yes but let's say we have a perfect hash. Then I find 
> the index of keyword.. and then I guess a strcmp is also 
> required to check against conflicts. Because the input
> can be any string.
> So there is at least two operations hash and strcmp.

Well, the function written by gperf has a slight optimisation, but, yes,
there are two operations.  Are you sure you are not prematurely
optimising this?

-- 
Ben.

[toc] | [prev] | [next] | [standalone]

#167093

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.

-- 
:-<> 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]

#167095

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]

Page 2 of 6 — ← Prev page 1 [2] 3 4 5 6  Next page →

Back to top | Article view | comp.lang.c

csiph-web