Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]
Groups > comp.lang.c > #111691 > unrolled thread
| Started by | "Rick C. Hodgin" <rick.c.hodgin@gmail.com> |
|---|---|
| First post | 2017-06-07 06:16 -0700 |
| Last post | 2017-06-07 08:53 -0700 |
| Articles | 20 on this page of 122 — 18 participants |
Back to article view | Back to comp.lang.c
memscan() function or equivalent "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-06-07 06:16 -0700
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-07 15:47 +0200
Re: memscan() function or equivalent "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-06-07 07:15 -0700
Re: memscan() function or equivalent scott@slp53.sl.home (Scott Lurndal) - 2017-06-07 14:34 +0000
Re: memscan() function or equivalent "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-06-07 07:42 -0700
Re: memscan() function or equivalent scott@slp53.sl.home (Scott Lurndal) - 2017-06-07 14:45 +0000
Re: memscan() function or equivalent "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-06-07 08:07 -0700
Re: memscan() function or equivalent jameskuyper@verizon.net - 2017-06-07 09:14 -0700
Re: memscan() function or equivalent "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-06-07 09:33 -0700
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-07 16:48 +0200
Re: memscan() function or equivalent "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-06-07 08:31 -0700
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-07 17:37 +0200
Re: memscan() function or equivalent "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-06-07 08:47 -0700
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-07 18:02 +0200
Re: memscan() function or equivalent "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-06-07 09:09 -0700
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-07 18:34 +0200
Re: memscan() function or equivalent "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-06-07 09:54 -0700
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-07 19:01 +0200
Re: memscan() function or equivalent "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-06-07 10:17 -0700
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-07 19:53 +0200
Re: memscan() function or equivalent asetofsymbols@gmail.com - 2017-06-07 22:15 -0700
Re: memscan() function or equivalent asetofsymbols@gmail.com - 2017-06-07 22:26 -0700
Re: memscan() function or equivalent asetofsymbols@gmail.com - 2017-06-07 22:56 -0700
Re: memscan() function or equivalent asetofsymbols@gmail.com - 2017-06-07 23:03 -0700
Re: memscan() function or equivalent scott@slp53.sl.home (Scott Lurndal) - 2017-06-07 16:10 +0000
Re: memscan() function or equivalent "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-06-07 09:30 -0700
Re: memscan() function or equivalent Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-06-07 16:50 +0100
Re: memscan() function or equivalent "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-06-07 08:58 -0700
Re: memscan() function or equivalent "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-06-07 09:03 -0700
Re: memscan() function or equivalent "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-06-07 09:07 -0700
Re: memscan() function or equivalent bartc <bc@freeuk.com> - 2017-06-07 17:30 +0100
Re: memscan() function or equivalent "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-06-07 09:36 -0700
Re: memscan() function or equivalent bartc <bc@freeuk.com> - 2017-06-07 17:48 +0100
Re: memscan() function or equivalent "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-06-07 09:57 -0700
Re: memscan() function or equivalent Ike Naar <ike@iceland.freeshell.org> - 2017-06-12 05:54 +0000
Re: memscan() function or equivalent Keith Thompson <kst-u@mib.org> - 2017-06-07 09:48 -0700
Re: memscan() function or equivalent Gareth Owen <gwowen@gmail.com> - 2017-06-07 20:55 +0100
Re: memscan() function or equivalent bartc <bc@freeuk.com> - 2017-06-07 22:13 +0100
Re: memscan() function or equivalent Keith Thompson <kst-u@mib.org> - 2017-06-07 16:02 -0700
Re: memscan() function or equivalent bartc <bc@freeuk.com> - 2017-06-08 01:26 +0100
Re: memscan() function or equivalent Ian Collins <ian-news@hotmail.com> - 2017-06-08 13:00 +1200
Re: memscan() function or equivalent bartc <bc@freeuk.com> - 2017-06-08 09:48 +0100
Re: memscan() function or equivalent "Patrick.Schluter" <Patrick.Schluter@free.fr> - 2017-06-10 08:52 +0200
Re: memscan() function or equivalent supercat@casperkitty.com - 2017-06-07 10:00 -0700
Re: memscan() function or equivalent "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-06-07 10:13 -0700
Re: memscan() function or equivalent supercat@casperkitty.com - 2017-06-07 11:19 -0700
Re: memscan() function or equivalent "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-06-07 11:27 -0700
Re: memscan() function or equivalent Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-06-07 21:18 +0100
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-07 18:18 +0200
Re: memscan() function or equivalent "Patrick.Schluter" <Patrick.Schluter@free.fr> - 2017-06-07 21:15 +0200
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-07 21:16 +0200
Re: memscan() function or equivalent "Patrick.Schluter" <Patrick.Schluter@free.fr> - 2017-06-10 09:08 +0200
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-10 09:56 +0200
Re: memscan() function or equivalent "Patrick.Schluter" <Patrick.Schluter@free.fr> - 2017-06-10 17:14 +0200
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-10 17:38 +0200
Re: memscan() function or equivalent David Kleinecke <dkleinecke@gmail.com> - 2017-06-10 11:52 -0700
Re: memscan() function or equivalent bartc <bc@freeuk.com> - 2017-06-10 20:03 +0100
Re: memscan() function or equivalent Keith Thompson <kst-u@mib.org> - 2017-06-10 13:32 -0700
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-10 23:40 +0200
Re: memscan() function or equivalent Anton Shepelev <anton.txt@gmail.com> - 2017-06-11 00:53 +0300
Re: memscan() function or equivalent Anton Shepelev <anton.txt@gmail.com> - 2017-06-11 01:11 +0300
Re: memscan() function or equivalent Ian Collins <ian-news@hotmail.com> - 2017-06-11 10:26 +1200
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-11 00:32 +0200
Re: memscan() function or equivalent "Patrick.Schluter" <Patrick.Schluter@free.fr> - 2017-06-11 10:05 +0200
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-11 10:06 +0200
Re: memscan() function or equivalent Keith Thompson <kst-u@mib.org> - 2017-06-11 13:19 -0700
Re: memscan() function or equivalent Anton Shepelev <anton.txt@gmail.com> - 2017-06-11 02:17 +0300
Re: memscan() function or equivalent supercat@casperkitty.com - 2017-06-10 15:21 -0700
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-11 00:19 +0200
Re: memscan() function or equivalent Anton Shepelev <anton.txt@gmail.com> - 2017-06-11 02:15 +0300
Re: memscan() function or equivalent "Patrick.Schluter" <Patrick.Schluter@free.fr> - 2017-06-11 10:36 +0200
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-11 10:46 +0200
Re: memscan() function or equivalent asetofsymbols@gmail.com - 2017-06-10 22:25 -0700
Re: memscan() function or equivalent "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2017-06-10 15:13 -0700
Re: memscan() function or equivalent bartc <bc@freeuk.com> - 2017-06-10 23:21 +0100
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-11 00:28 +0200
Re: memscan() function or equivalent bartc <bc@freeuk.com> - 2017-06-11 10:56 +0100
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-11 13:27 +0200
Re: memscan() function or equivalent bartc <bc@freeuk.com> - 2017-06-11 13:19 +0100
Re: memscan() function or equivalent Ike Naar <ike@iceland.freeshell.org> - 2017-06-11 18:36 +0000
Re: memscan() function or equivalent bartc <bc@freeuk.com> - 2017-06-11 20:22 +0100
Re: memscan() function or equivalent Ike Naar <ike@iceland.freeshell.org> - 2017-06-12 06:09 +0000
Re: memscan() function or equivalent bartc <bc@freeuk.com> - 2017-06-12 10:38 +0100
Re: memscan() function or equivalent asetofsymbols@gmail.com - 2017-06-12 05:30 -0700
Re: memscan() function or equivalent Ike Naar <ike@iceland.freeshell.org> - 2017-06-12 13:51 +0000
Re: memscan() function or equivalent bartc <bc@freeuk.com> - 2017-06-12 15:04 +0100
Re: memscan() function or equivalent Ike Naar <ike@iceland.freeshell.org> - 2017-06-12 21:26 +0000
Re: memscan() function or equivalent "Patrick.Schluter" <Patrick.Schluter@free.fr> - 2017-06-11 10:04 +0200
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-11 10:13 +0200
Re: memscan() function or equivalent "Patrick.Schluter" <Patrick.Schluter@free.fr> - 2017-06-11 13:38 +0200
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-11 14:18 +0200
Re: memscan() function or equivalent supercat@casperkitty.com - 2017-06-11 09:57 -0700
Re: memscan() function or equivalent Melzzzzz <Melzzzzz@zzzzz.com> - 2017-06-11 17:18 +0000
Re: memscan() function or equivalent "Patrick.Schluter" <Patrick.Schluter@free.fr> - 2017-06-11 09:53 +0200
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-11 10:00 +0200
Re: memscan() function or equivalent "Patrick.Schluter" <Patrick.Schluter@free.fr> - 2017-06-11 13:41 +0200
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-07 21:24 +0200
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-07 21:55 +0200
Re: memscan() function or equivalent Gareth Owen <gwowen@gmail.com> - 2017-06-07 20:54 +0100
Re: memscan() function or equivalent David Brown <david.brown@hesbynett.no> - 2017-06-07 23:00 +0200
Re: memscan() function or equivalent Gareth Owen <gwowen@gmail.com> - 2017-06-08 08:16 +0100
Re: memscan() function or equivalent David Brown <david.brown@hesbynett.no> - 2017-06-08 10:55 +0200
Re: memscan() function or equivalent Gareth Owen <gwowen@gmail.com> - 2017-06-08 11:44 +0100
Re: memscan() function or equivalent David Brown <david.brown@hesbynett.no> - 2017-06-08 13:11 +0200
Re: memscan() function or equivalent Gareth Owen <gwowen@gmail.com> - 2017-06-08 13:45 +0100
Re: memscan() function or equivalent David Brown <david.brown@hesbynett.no> - 2017-06-08 14:51 +0200
Re: memscan() function or equivalent supercat@casperkitty.com - 2017-06-08 08:00 -0700
Re: memscan() function or equivalent Tim Rentsch <txr@alumni.caltech.edu> - 2017-06-09 12:26 -0700
Re: memscan() function or equivalent Gareth Owen <gwowen@gmail.com> - 2017-06-10 07:24 +0100
Re: memscan() function or equivalent Ben Bacarisse <ben.usenet@bsb.me.uk> - 2017-06-10 13:17 +0100
Re: memscan() function or equivalent Gareth Owen <gwowen@gmail.com> - 2017-06-10 17:18 +0100
Re: memscan() function or equivalent Ike Naar <ike@iceland.freeshell.org> - 2017-06-11 18:11 +0000
Re: memscan() function or equivalent Tim Rentsch <txr@alumni.caltech.edu> - 2017-06-11 15:08 -0700
Re: memscan() function or equivalent Gareth Owen <gwowen@gmail.com> - 2017-06-12 18:34 +0100
Re: memscan() function or equivalent Tim Rentsch <txr@alumni.caltech.edu> - 2017-06-14 09:52 -0700
Re: memscan() function or equivalent Gareth Owen <gwowen@gmail.com> - 2017-06-14 19:56 +0100
Re: memscan() function or equivalent Keith Thompson <kst-u@mib.org> - 2017-06-14 12:20 -0700
Re: memscan() function or equivalent Tim Rentsch <txr@alumni.caltech.edu> - 2017-06-17 06:37 -0700
Re: memscan() function or equivalent supercat@casperkitty.com - 2017-06-17 10:02 -0700
Re: memscan() function or equivalent David Brown <david.brown@hesbynett.no> - 2017-06-07 16:51 +0200
Re: memscan() function or equivalent GOTHIER Nathan <nathan.gothier@gmail.com> - 2017-06-07 17:00 +0200
Re: memscan() function or equivalent supercat@casperkitty.com - 2017-06-07 08:53 -0700
Page 6 of 7 — ← Prev page 1 2 3 4 5 [6] 7 Next page →
| From | Gareth Owen <gwowen@gmail.com> |
|---|---|
| Date | 2017-06-08 08:16 +0100 |
| Message-ID | <87zidj9cfv.fsf@gmail.com> |
| In reply to | #111756 |
David Brown <david.brown@hesbynett.no> writes:
> In some cases, a conditional branch would be more efficient, in other
> cases an integer selection instruction or some other way of producing
> a 0 or 1, followed by an unconditional add, would be best. A compiler
> /could/ choose the method it thought was most efficient, but it could
> also reasonably choose the method that matched the source code best,
> on the assumption that the programmer knows best.
I agree with all of this. With optimisation off ("a supercat
compiler") I would expect different code generated - code that logically
mapped to the syntax.
With optimisation maxed out, I would hope the compiler compiled them the
same.
Did a quick test gcc -O0 and -O3 produce the subtly different code for
both of these functions (this is gcc-6.2 on ubuntu), but my assembler-fu
isn't enough to tell which is more efficient.
#include<stdlib.h>
int count(const char * b,char c,size_t n)
{
int ct = 0;
for(size_t idx = 0; idx < n; ++idx) ct += (*b == c);
return ct;
}
int count2(const char * b,char c,size_t n)
{
int ct = 0;
for(size_t idx = 0; idx < n; ++idx) if(*b == c) ++ct;
return ct;
}
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2017-06-08 10:55 +0200 |
| Message-ID | <ohb36i$p0q$1@dont-email.me> |
| In reply to | #111798 |
On 08/06/17 09:16, Gareth Owen wrote:
> David Brown <david.brown@hesbynett.no> writes:
>
>> In some cases, a conditional branch would be more efficient, in other
>> cases an integer selection instruction or some other way of producing
>> a 0 or 1, followed by an unconditional add, would be best. A compiler
>> /could/ choose the method it thought was most efficient, but it could
>> also reasonably choose the method that matched the source code best,
>> on the assumption that the programmer knows best.
>
> I agree with all of this. With optimisation off ("a supercat
> compiler") I would expect different code generated - code that logically
> mapped to the syntax.
>
> With optimisation maxed out, I would hope the compiler compiled them the
> same.
>
> Did a quick test gcc -O0 and -O3 produce the subtly different code for
> both of these functions (this is gcc-6.2 on ubuntu), but my assembler-fu
> isn't enough to tell which is more efficient.
>
> #include<stdlib.h>
> int count(const char * b,char c,size_t n)
> {
> int ct = 0;
> for(size_t idx = 0; idx < n; ++idx) ct += (*b == c);
> return ct;
> }
>
> int count2(const char * b,char c,size_t n)
> {
> int ct = 0;
> for(size_t idx = 0; idx < n; ++idx) if(*b == c) ++ct;
> return ct;
> }
>
You have to have "(*b++ == c)", or the loop will exit rather quickly -
gcc is smart enough to do one check, and return 0 or n.
With that change, I tried a few gcc's on godbolt. For the x86_64, the
compiler generates different code - one with the "sete" instruction to
turn the results of the comparison into a 0 or 1 for adding to ct, and
one with a conditional jump. The first version will be faster if the
results of the comparison are hard to predict, while the second version
will be faster if they are predictable. Accumulating the results
whether they are 0 or 1 introduces dependencies in the instruction
stream, limiting superscaling. Correctly predicted branches are nearly
free, but incorrectly predicted branches are expensive - it is
impossible to say which solution is "best" without knowledge of the data
used in practice.
On the ARM, on the other hand, which has conditional execution flags on
instructions, the two functions produce the same code.
[toc] | [prev] | [next] | [standalone]
| From | Gareth Owen <gwowen@gmail.com> |
|---|---|
| Date | 2017-06-08 11:44 +0100 |
| Message-ID | <87ink6g3n1.fsf@gmail.com> |
| In reply to | #111800 |
David Brown <david.brown@hesbynett.no> writes: > You have to have "(*b++ == c)", or the loop will exit rather quickly - > gcc is smart enough to do one check, and return 0 or n. *Facepalm* Thanks for doing it right! [interesting results and commentary snipped] So *if* its speed critical - you still need to measure, and profile, and possibly feed that profile information back to the optimiser. Except when you don't. :)
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2017-06-08 13:11 +0200 |
| Message-ID | <ohbb74$j9c$1@dont-email.me> |
| In reply to | #111804 |
On 08/06/17 12:44, Gareth Owen wrote: > David Brown <david.brown@hesbynett.no> writes: > >> You have to have "(*b++ == c)", or the loop will exit rather quickly - >> gcc is smart enough to do one check, and return 0 or n. > > *Facepalm* Thanks for doing it right! > > [interesting results and commentary snipped] > > So *if* its speed critical - you still need to measure, and profile, and > possibly feed that profile information back to the optimiser. > Yes, ultimately that is true. And you also need to play with other settings, like enabling vectorisation. For a function like this, you will find that the most efficient way to handle small inputs is very different from the most efficient way to handle large inputs. > Except when you don't. :) > Usually you don't need to. But sometimes it is fun to play with that sort of thing!
[toc] | [prev] | [next] | [standalone]
| From | Gareth Owen <gwowen@gmail.com> |
|---|---|
| Date | 2017-06-08 13:45 +0100 |
| Message-ID | <87zidi6426.fsf@gmail.com> |
| In reply to | #111806 |
David Brown <david.brown@hesbynett.no> writes: >> Except when you don't. :) >> > Usually you don't need to. But sometimes it is fun to play with that > sort of thing! It's more fun when you remember to increment the pointer...
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2017-06-08 14:51 +0200 |
| Message-ID | <ohbh1a$7aq$1@dont-email.me> |
| In reply to | #111808 |
On 08/06/17 14:45, Gareth Owen wrote: > David Brown <david.brown@hesbynett.no> writes: > >>> Except when you don't. :) >>> >> Usually you don't need to. But sometimes it is fun to play with that >> sort of thing! > > It's more fun when you remember to increment the pointer... > Mistakes like that are what let you write /really/ fast code. Look how well your original algorithm scales with the length of the data :-)
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2017-06-08 08:00 -0700 |
| Message-ID | <aff31355-c379-4849-97c1-2f46c60ad697@googlegroups.com> |
| In reply to | #111798 |
On Thursday, June 8, 2017 at 2:16:32 AM UTC-5, gwowen wrote:
> David Brown writes:
>
> > In some cases, a conditional branch would be more efficient, in other
> > cases an integer selection instruction or some other way of producing
> > a 0 or 1, followed by an unconditional add, would be best. A compiler
> > /could/ choose the method it thought was most efficient, but it could
> > also reasonably choose the method that matched the source code best,
> > on the assumption that the programmer knows best.
>
> I agree with all of this. With optimisation off ("a supercat
> compiler") I would expect different code generated - code that logically
> mapped to the syntax.
>
> With optimisation maxed out, I would hope the compiler compiled them the
> same.
In many cases, one interpretation will be better for some inputs and the
other will be better for other inputs. In such cases, I would think
letting the programmer choose the approach would allow better code
generation, in cases where it matters, than always using one or the other.
If the programmer would be satisfied with the performance of either
version, there's no reason the compiler shouldn't be satisfied with the
programmer's choice).
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2017-06-09 12:26 -0700 |
| Message-ID | <kfnmv9h9d47.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #111711 |
Ben Bacarisse <ben.usenet@bsb.me.uk> writes:
> GOTHIER Nathan <nathan.gothier@gmail.com> writes:
> [...condensed for reply...]
>>
>> #include <stddef.h>
>>
>> typedef unsigned char uchar_t;
>>
>> size_t memfrq(const void *s, int c, size_t n)
>> {
>> uchar_t *s0 = (uchar_t *) s;
>> uchar_t c0 = (uchar_t) c;
>> size_t k = 0U;
>> scan:
>> {
>> if (n > 1)
>> {
>> if (*s0 == c0)
>> {
>> k++;
>> }
>>
>> s0++;
>> n--;
>>
>> goto scan;
>> }
>> return k;
>> }
>> }
>
> What is the general view of writing things like
>
> k += *s0 == c0;
>
> ? I find it compact and natural with no extra cost, at least with
> modern compilers.
I prefer this form to the if() approach. Besides being more
compact, it is more direct - computing 'k' is the point of the
loop, and this form brings that computation to the top level (ie,
of the loop body), and eliminates an if().
Many years ago I took a course from Alan Perlis, who was at that
time a fan of APL (and also other things, I don't mean APL only).
Describing APL, a phrase he used that stuck in my mind is "all in
one fell swoop", talking about computation that is done using
array operations rather than looping. At first I didn't see what
he was getting at, but over time I started to see the value of
computing based on data rather than computing based on control
flow. My preference here for 'k += *s0 == c0;' is mainly an
outgrowth of that insight.
[toc] | [prev] | [next] | [standalone]
| From | Gareth Owen <gwowen@gmail.com> |
|---|---|
| Date | 2017-06-10 07:24 +0100 |
| Message-ID | <878tl0fjh1.fsf@gmail.com> |
| In reply to | #111902 |
Tim Rentsch <txr@alumni.caltech.edu> writes:
> Many years ago I took a course from Alan Perlis, who was at that
> time a fan of APL (and also other things, I don't mean APL only).
> Describing APL, a phrase he used that stuck in my mind is "all in
> one fell swoop", talking about computation that is done using
> array operations rather than looping. At first I didn't see what
> he was getting at, but over time I started to see the value of
> computing based on data rather than computing based on control
> flow. My preference here for 'k += *s0 == c0;' is mainly an
> outgrowth of that insight.
I totally understand and respect this opinion -- and I definitely don't
feel desperately strongly -- but offer the following rejoinder, courtesy
of Don Knuth
"Let us change our traditional attitude to the construction of
programs: Instead of imagining that our main task is to instruct a
computer what to do, let us concentrate rather on explaining to
human beings what we want a computer to do"
k += (*s0 == c0) (and as I read it, your rationale for it) falls firmly
in the former category.
[toc] | [prev] | [next] | [standalone]
| From | Ben Bacarisse <ben.usenet@bsb.me.uk> |
|---|---|
| Date | 2017-06-10 13:17 +0100 |
| Message-ID | <87tw3o9gve.fsf@bsb.me.uk> |
| In reply to | #111917 |
Gareth Owen <gwowen@gmail.com> writes: > Tim Rentsch <txr@alumni.caltech.edu> writes: > >> Many years ago I took a course from Alan Perlis, who was at that >> time a fan of APL (and also other things, I don't mean APL only). >> Describing APL, a phrase he used that stuck in my mind is "all in >> one fell swoop", talking about computation that is done using >> array operations rather than looping. At first I didn't see what >> he was getting at, but over time I started to see the value of >> computing based on data rather than computing based on control >> flow. My preference here for 'k += *s0 == c0;' is mainly an >> outgrowth of that insight. > > I totally understand and respect this opinion -- and I definitely don't > feel desperately strongly -- but offer the following rejoinder, courtesy > of Don Knuth > > "Let us change our traditional attitude to the construction of > programs: Instead of imagining that our main task is to instruct a > computer what to do, let us concentrate rather on explaining to > human beings what we want a computer to do" > > k += (*s0 == c0) (and as I read it, your rationale for it) falls firmly > in the former category. Curious. I have exactly the reverse view! The 'if' form is the one that painstakingly explains what the machine should do. To find out what it calculates you have to (mentally) unwind the actions into a computation. The *s0 == c0 is an indicator function (APL uses these a lot) giving zero for the 'no' cases and one for the 'yes' cases. A count of things (any things) in a sequence is the sum of an suitable indicator function mapped onto the elements of the sequence. Ideally, I'd prefer not to have a walking pointer because that, again, is too much "how" and not enough "what" for me. Now obviously which way the balance falls has a lot to do with who you expect to be reading the code, but for many people summing a 0/1 function over a list is almost the definition of counting. For others, the clearest explanation is "is this one of the ones we want? yes? OK add one to the counter" but that's way too much "how" for me. -- Ben.
[toc] | [prev] | [next] | [standalone]
| From | Gareth Owen <gwowen@gmail.com> |
|---|---|
| Date | 2017-06-10 17:18 +0100 |
| Message-ID | <87wp8j6ckj.fsf@gmail.com> |
| In reply to | #111926 |
Ben Bacarisse <ben.usenet@bsb.me.uk> writes: > The *s0 == c0 is an indicator function (APL uses these a lot) giving > zero for the 'no' cases and one for the 'yes' cases. A count of things > (any things) in a sequence is the sum of an suitable indicator function > mapped onto the elements of the sequence. Your idea of "easily comprehended by a human" and mine appear to differ. My explanation involves the notion of "if some predicate, do some action". Yours explantion is based on the notion that "A count of things (any things) in a sequence is the sum of an suitable indicator function mapped onto the elements of the sequence." Now don't get me wrong - I understand that pretty easily. But I have multiple degrees in mathematics, and 20+ years programming experience. If I were to try the two explainations on my wife (degrees in music and history, postgraduate qualification in education), I suspect I know which one she would understand. Then she would tell me I spelt "explainations" incorrectly.
[toc] | [prev] | [next] | [standalone]
| From | Ike Naar <ike@iceland.freeshell.org> |
|---|---|
| Date | 2017-06-11 18:11 +0000 |
| Message-ID | <slrn3vfsojr24l.smk.ike@iceland.freeshell.org> |
| In reply to | #111930 |
On 2017-06-10, Gareth Owen <gwowen@gmail.com> wrote: > Ben Bacarisse <ben.usenet@bsb.me.uk> writes: > >> The *s0 == c0 is an indicator function (APL uses these a lot) giving >> zero for the 'no' cases and one for the 'yes' cases. A count of things >> (any things) in a sequence is the sum of an suitable indicator function >> mapped onto the elements of the sequence. > > Your idea of "easily comprehended by a human" and mine appear to differ. > > My explanation involves the notion of "if some predicate, do some action". > > Yours explantion is based on the notion that "A count of things (any > things) in a sequence is the sum of an suitable indicator function > mapped onto the elements of the sequence." > > Now don't get me wrong - I understand that pretty easily. But I have > multiple degrees in mathematics, and 20+ years programming experience. > > If I were to try the two explainations on my wife (degrees in music and > history, postgraduate qualification in education), I suspect I know > which one she would understand. > > Then she would tell me I spelt "explainations" incorrectly. And "explantion" ;-)
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2017-06-11 15:08 -0700 |
| Message-ID | <kfnfuf69nyc.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #111917 |
Gareth Owen <gwowen@gmail.com> writes:
> Tim Rentsch <txr@alumni.caltech.edu> writes:
>
>> Many years ago I took a course from Alan Perlis, who was at that
>> time a fan of APL (and also other things, I don't mean APL only).
>> Describing APL, a phrase he used that stuck in my mind is "all in
>> one fell swoop", talking about computation that is done using
>> array operations rather than looping. At first I didn't see what
>> he was getting at, but over time I started to see the value of
>> computing based on data rather than computing based on control
>> flow. My preference here for 'k += *s0 == c0;' is mainly an
>> outgrowth of that insight.
>
> I totally understand and respect this opinion -- and I definitely don't
> feel desperately strongly -- but offer the following rejoinder, courtesy
> of Don Knuth
>
> "Let us change our traditional attitude to the construction of
> programs: Instead of imagining that our main task is to instruct a
> computer what to do, let us concentrate rather on explaining to
> human beings what we want a computer to do"
>
> k += (*s0 == c0) (and as I read it, your rationale for it) falls firmly
> in the former category.
I was about to reply to one or two of your other postings in this
thread, but then I saw this and decided to respond here. I will
take up the comment above shortly, first let me go through the
other items.
Re: what code will be produced for the two cases. What I expect
is the compiler will choose what it thinks is the fastest code in
both cases (subject of course to -O setting), unless directed
otherwise by annotations in the source code (eg, #pragma). I
took your two example functions (with the correction to increment
the buffer pointer), and compiled them on two different platforms
at all six optimization levels (-O0, -O1, -Os, -O2, -O3, -O4).
(If it matters one platform was x86, the other x86-64, and the
versions of gcc were different in the two cases.) The results
were as follows (here "cases" refers to the two functions, and
the statements below apply to each platform without regard to
the other):
-O0
Different assembly in the two cases, pretty much a direct
mapping of source to assembly.
-O1, -Os, -O2
Assembly in the two cases was isomorphic (I didn't check
carefully to see if it was identical).
-O3, -O4
Assembly in the two cases was similar but not line-for-line
the same. The produced functions were quite a bit longer
and more complicated than the lower optimization levels,
which I believe represents some amount of loop unrolling.
(FWIW my guess is the loop unrolling complicated the later
code selection, which is what caused the differences.)
Not counting -O0, the method used (conditional branch, or a
branchless generation of 0 or 1) was the same at all levels
of optimization. (It was different between the two platforms,
although I don't know whether that is due to instruction set
or having different versions of gcc.)
Returning to the question of which writing one chooses - despite
the impression you got, it is very much my intention to write for
people in my programs. Related to that, it struck me that you
describe the if() approach as "directly expressing what you want
to do", and yet in my previous posting I described the other
approach as being "more direct". Clearly we are using different
reasoning to reach our respective conclusions. Let me see if I
can explain mine.
In Dijkstra's writings, he mentions this idea of two views of
computing. In the old view, the purpose of programs is to
instruct our machines. In the new view, the purpose of our
machines is to execute our programs. From this influence and
also a few others, relatively early in my programming education I
learned to program primarily for human consumption rather than
focusing on directing the machine.
In your first response on this question, you characterized the
two approaches (the if() method first, the other second) this
way:
> Which of these is clearest:
> "If the characters match, increment the counter".
> "Increment the counter by one if the characters match,
> or zero if they don't"
The first paraphrase seems okay, but the second one isn't at all
how I think of what is being expressed. For the second approach
I would probably say something like this, meant for the loop as
a whole:
"Count one for each buffer position that matches the
argument character."
That English description is (IMO, of course) more directly
expressed by 'k += b[i]==c' (or something similar) than by a
conditional assignment. The if() method seems like a holdover
from early learning of imperative programming, when what we
were doing /was/ learning how to instruct a computer. When I
write programs, I (mostly) don't think of it as instructing a
computer what to do, or describing what I want the computer to
do. That's the old view of computing, which I have made an
effort to abandon (or at least mostly abandon). Rather I write
programs, or at least I try to write programs, so that they
best express how I conceptualize solving the problem.
I acknowledge your comment that most people who are used to
imperative programming will have no trouble with the if() method,
and might be less sure about how to take the other one. Here
though I think it does a disservice to the community to try to
cater to that, as otherwise it becomes a self-reinforcing cycle,
and whole swaths of developers will be stuck in their imperative
ruts forever. I am hoping we can do better, and act accordingly.
Do my earlier comments make more sense now?
[toc] | [prev] | [next] | [standalone]
| From | Gareth Owen <gwowen@gmail.com> |
|---|---|
| Date | 2017-06-12 18:34 +0100 |
| Message-ID | <87efupaz5e.fsf@gmail.com> |
| In reply to | #111983 |
Tim Rentsch <txr@alumni.caltech.edu> writes: > Do my earlier comments make more sense now? Totally - excellently written expression of a totally valid opinion with which I only partly disagree.
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2017-06-14 09:52 -0700 |
| Message-ID | <kfnk24e7bqx.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #112062 |
Gareth Owen <gwowen@gmail.com> writes: > Tim Rentsch <txr@alumni.caltech.edu> writes: > >> Do my earlier comments make more sense now? > > Totally - excellently written expression of a totally valid opinion with > which I only partly disagree. Thank you for the glowing description. If you don't mind a further question, I'm curious to know what you don't agree with and why. Not to debate or argue about it, just to satisfy my curiosity. Please feel free to send that by email if that makes things easier.
[toc] | [prev] | [next] | [standalone]
| From | Gareth Owen <gwowen@gmail.com> |
|---|---|
| Date | 2017-06-14 19:56 +0100 |
| Message-ID | <874lvi4cvs.fsf@gmail.com> |
| In reply to | #112202 |
Tim Rentsch <txr@alumni.caltech.edu> writes: > Gareth Owen <gwowen@gmail.com> writes: > >> Tim Rentsch <txr@alumni.caltech.edu> writes: >> > Thank you for the glowing description. If you don't mind a > further question, I'm curious to know what you don't agree > with and why. Not to debate or argue about it, just to > satisfy my curiosity. Please feel free to send that by > email if that makes things easier. I will briefly, because I think we're really subjective territory, and I'm not sure how well I can explain myself, or even if it'll be very elucidating if I do: > "Count one for each buffer position that matches the > argument character." > > That English description is (IMO, of course) more directly > expressed by 'k += b[i]==c' (or something similar) than by a > conditional assignment Really, this is the bit that I don't agree with - and I think its how our minds have respectively come to read code, that I can't read that line of code in your sense without it feeling unnatural to me. Don't really understand why. I think possibly part of it is that something in my mind is seeing the right-hand-side as "true" rather than 1 - and as soon as I think "Boolean" I'm right into thinking about predicates and conditionals. When you read some prose, say, that you consider well written, your mind parses the meaning and the poetry out without you ever consciously thinking about the words. But if an author uses a clunky conjunction, or just an idiom with which you're insufficiently familiar -- clearly the best analogy here -- (or just outright writes a few sentences in Spanish, thank you, Cormac McCarthy) you're jerked right back into the text to try and figure out what was intended. There's something about the implicit conversion from "true" to "1" that requires a tiny extra element of conscious thought that prevents smooth comprehension. Does that make even the slightest bit of sense? (Told you it'd be unhelpful.)
[toc] | [prev] | [next] | [standalone]
| From | Keith Thompson <kst-u@mib.org> |
|---|---|
| Date | 2017-06-14 12:20 -0700 |
| Message-ID | <lnbmpqcr5z.fsf@kst-u.example.com> |
| In reply to | #112213 |
Gareth Owen <gwowen@gmail.com> writes:
> Tim Rentsch <txr@alumni.caltech.edu> writes:
[...]
>> That English description is (IMO, of course) more directly
>> expressed by 'k += b[i]==c' (or something similar) than by a
>> conditional assignment
[...]
> There's something about the implicit conversion from "true" to
> "1" that requires a tiny extra element of conscious thought that
> prevents smooth comprehension.
I will pedantically point out that the result of `b[i]==c` *is* of type
int. But that doesn't affect your argument.
--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Working, but not speaking, for JetHead Development, Inc.
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"
[toc] | [prev] | [next] | [standalone]
| From | Tim Rentsch <txr@alumni.caltech.edu> |
|---|---|
| Date | 2017-06-17 06:37 -0700 |
| Message-ID | <kfnlgoq68ha.fsf@x-alumni2.alumni.caltech.edu> |
| In reply to | #112213 |
Gareth Owen <gwowen@gmail.com> writes: > Tim Rentsch <txr@alumni.caltech.edu> writes: > >> Gareth Owen <gwowen@gmail.com> writes: >> >>> Tim Rentsch <txr@alumni.caltech.edu> writes: >> >> Thank you for the glowing description. If you don't mind a >> further question, I'm curious to know what you don't agree >> with and why. Not to debate or argue about it, just to >> satisfy my curiosity. Please feel free to send that by >> email if that makes things easier. > > I will briefly, because I think we're really subjective territory, > and I'm not sure how well I can explain myself, or even if it'll > be very elucidating if I do: > >> "Count one for each buffer position that matches the >> argument character." >> >> That English description is (IMO, of course) more directly >> expressed by 'k += b[i]==c' (or something similar) than by a >> conditional assignment > > Really, this is the bit that I don't agree with - and I think its > how our minds have respectively come to read code, that I can't read > that line of code in your sense without it feeling unnatural to me. > > Don't really understand why. I think possibly part of it is that > something in my mind is seeing the right-hand-side as "true" rather > than 1 - and as soon as I think "Boolean" I'm right into thinking > about predicates and conditionals. > > When you read some prose, say, that you consider well written, your > mind parses the meaning and the poetry out without you ever consciously > thinking about the words. But if an author uses a clunky conjunction, > or just an idiom with which you're insufficiently familiar -- clearly > the best analogy here -- (or just outright writes a few sentences in > Spanish, thank you, Cormac McCarthy) you're jerked right back into the > text to try and figure out what was intended. > > There's something about the implicit conversion from "true" to "1" > that requires a tiny extra element of conscious thought that prevents > smooth comprehension. > > Does that make even the slightest bit of sense? > > (Told you it'd be unhelpful.) Yes it does make sense. And actually it helps a lot. You explain which part of what I was saying gives you a mental hiccup, and why. My own reaction is different but I understand how "an unnatural construction" could get in the way of flow, and that is really the key element here. I appreciate very much you taking the time to articulate it. I have been lucky in a way that my early programming experience was in lots of different languages, so I didn't get "set" on one or another viewpoint. (They were mostly imperative languages but that is a whole other discussion.) The idea that comparisons yield a boolean type seems to come from Algol, and perhaps more influentially the successor Pascal. Algol-family languages even have a separate syntax for boolean expressions. The language APL takes a different view - relational expressions yield 0 or 1, and are just ordinary numbers. (And that is more important than it might seem because of some array operations, but I don't want to wander too far afield.) I learned APL about the same time as Algol and Pascal (or perhaps a little earlier, I don't remember exactly). So I got used to both the Algol style of comparisons and the APL style of comparisons. When I got to C, which was roughly, oh, maybe five years later, I took the C model of comparing as corresponding to the APL model of comparing: comparisons yield ordinary integers that are 0 or 1, and their syntactic forms are just part of the syntax for ordinary expressions. I never really thought about it, since by then I was used to both models and could switch between them without difficulty. While writing this I have been trying to think of an analogy where I have a mental speed bump similar to what you describe for yourself. The best (but still not very good) example I came up with is natural language. My native language is English, and I am very much entrenched in English language and idiom (this despite many years of learning not one but two other languages). I conjecture that people used to other languages sometimes phrase things in ways that would sound odd to me even though they are expressed in English. But not to them: their experience with other language(s) and other idioms of construction provides a perspective that lets them navigate the semantic landscape easily where I would find it slow going. In fact now that I think of it I have an example just yesterday. Talking with someone who is not a native speaker of English and who wanted me to leave a note, I heard: "You better have a piece of paper...". I definitely had a mental hiccup on that; I would have said "You better get a piece of paper and ..." or "You better put a piece of paper on it with ..." or something along those lines. "You better have a piece of paper...", even though I could understand it, was just peculiar.
[toc] | [prev] | [next] | [standalone]
| From | supercat@casperkitty.com |
|---|---|
| Date | 2017-06-17 10:02 -0700 |
| Message-ID | <d7260094-1819-4061-8865-049557d465e3@googlegroups.com> |
| In reply to | #112396 |
On Saturday, June 17, 2017 at 8:37:30 AM UTC-5, Tim Rentsch wrote: > Yes it does make sense. And actually it helps a lot. You > explain which part of what I was saying gives you a mental > hiccup, and why. My own reaction is different but I understand > how "an unnatural construction" could get in the way of flow, > and that is really the key element here. I appreciate very much > you taking the time to articulate it. In human languages, there is a concept of "garden path sentences"--sentences which would cause a reader to start parsing them one way and then discover that the initial parse doesn't work and they consequently have to rewind to figure out what's going on. Parentheses can sometimes be useful to warn readers of computer programs that parsing in left-to-right order is apt to lead them astray. Given a construct like: x = b+c == d+e; a computer would not perceive any ambiguity in how that should be processed, but adding parentheses as: x = (b+c == d+e); would avoid creating an initial impression that the thing being stored into x is a "b" that has been manipulated in some way. Instead, the opening parenthesis would invite the reader to scan through to the close parenthesis before trying to examine anything else. Such scanning would reveal the == and thus establish how things should be parsed. Such an approach would also have a nice parallel with the normal contexts in which expressions that represent truth and falsity are used (as controls for "if", "while", etc.)
[toc] | [prev] | [next] | [standalone]
| From | David Brown <david.brown@hesbynett.no> |
|---|---|
| Date | 2017-06-07 16:51 +0200 |
| Message-ID | <oh93mo$q5m$1@dont-email.me> |
| In reply to | #111695 |
On 07/06/17 16:15, Rick C. Hodgin wrote: > On Wednesday, June 7, 2017 at 9:50:27 AM UTC-4, GOTHIER Nathan wrote: >> /* count the occurrence number of c */ >> size_t memfrq(const void *s, int c, size_t n); > > What do these parameters equate to? What are s, c, and n? Can you > include the function body so I can see it at work? > He means the same function as you have given, but a more "inspired" prototype. By that, I expect he means a choice of types and names that are closer to those used by the standard library functions such as memchr: void *memchr(const void *s, int c, size_t n); If you are considering this as a function for an implementation that extends the standard library, then you might like to follow the style of the existing library. If this is to be a user-level function, then you should be aware that "memscan" (and "memfrq") are reserved names. IMHO, if your function is counting "characters" then it is fine to have "char" types - but perhaps not a "mem..." name. Whatever you pick for names and types, I recommend the first parameter be "const" qualified.
[toc] | [prev] | [next] | [standalone]
Page 6 of 7 — ← Prev page 1 2 3 4 5 [6] 7 Next page →
Back to top | Article view | comp.lang.c
csiph-web