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

Groups > comp.lang.c > #167131

Re: How to optimize this search?

From antispam@math.uni.wroc.pl
Newsgroups comp.lang.c
Subject Re: How to optimize this search?
Date 2022-08-23 00:07 +0000
Organization Aioe.org NNTP Server
Message-ID <te15o8$aka$1@gioia.aioe.org> (permalink)
References (1 earlier) <b8624e58-8af6-4c48-8b27-694174e4243cn@googlegroups.com> <5_NMK.799766$ntj.539650@fx15.iad> <fe9c8d16-e900-4be5-a0f3-af33b4f13219n@googlegroups.com> <2EPMK.792333$zgr9.428150@fx13.iad> <2ea7d68c-d15f-4896-97f5-b852174ca081n@googlegroups.com>

Show all headers | View raw

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

Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll thread

Thread

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

csiph-web