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

Groups > comp.lang.c > #167126

Re: How to optimize this search?

From Keith Thompson <Keith.S.Thompson+u@gmail.com>
Newsgroups comp.lang.c
Subject Re: How to optimize this search?
Date 2022-08-22 15:37 -0700
Organization None to speak of
Message-ID <875yijzyyh.fsf@nosuchdomain.example.com> (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> 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 */

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