Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #167146
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Newsgroups | comp.lang.c |
| Subject | Re: How to optimize this search? |
| Date | 2022-08-23 15:50 +0200 |
| Organization | A noiseless patient Spider |
| Message-ID | <te2lvr$30ht8$1@dont-email.me> (permalink) |
| References | (3 earlier) <fe9c8d16-e900-4be5-a0f3-af33b4f13219n@googlegroups.com> <2EPMK.792333$zgr9.428150@fx13.iad> <2ea7d68c-d15f-4896-97f5-b852174ca081n@googlegroups.com> <te1tat$2u80f$1@dont-email.me> <74f2284e-0016-4a0d-8fea-40f05b0381a7n@googlegroups.com> |
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?
Back to comp.lang.c | Previous | Next — Previous in thread | Next in thread | Find similar | Unroll 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