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

Groups > comp.lang.c > #167132

Re: How to optimize this search?

From Ben Bacarisse <ben.usenet@bsb.me.uk>
Newsgroups comp.lang.c
Subject Re: How to optimize this search?
Date 2022-08-23 01:18 +0100
Organization A noiseless patient Spider
Message-ID <87fshnvmlv.fsf@bsb.me.uk> (permalink)
References (3 earlier) <fe9c8d16-e900-4be5-a0f3-af33b4f13219n@googlegroups.com> <2EPMK.792333$zgr9.428150@fx13.iad> <2ea7d68c-d15f-4896-97f5-b852174ca081n@googlegroups.com> <875yijzyyh.fsf@nosuchdomain.example.com> <893f061a-1684-4e2c-80ac-caeba29a4445n@googlegroups.com>

Show all headers | View raw

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.

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