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 01:54 +0000
Organization	Aioe.org NNTP Server
Message-ID	<te1c0a$2fa$1@gioia.aioe.org> (permalink)
References	(3 earlier) <fe9c8d16-e900-4be5-a0f3-af33b4f13219n@googlegroups.com> <2EPMK.792333$zgr9.428150@fx13.iad> <2ea7d68c-d15f-4896-97f5-b852174ca081n@googlegroups.com> <te15o8$aka$1@gioia.aioe.org> <9befe5fc-292d-4739-9b29-dccbfeb359b2n@googlegroups.com>

Show all headers | View raw

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

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