Groups > comp.lang.c > #111983

Re: memscan() function or equivalent

From	Tim Rentsch <txr@alumni.caltech.edu>
Newsgroups	comp.lang.c
Subject	Re: memscan() function or equivalent
Date	2017-06-11 15:08 -0700
Organization	A noiseless patient Spider
Message-ID	<kfnfuf69nyc.fsf@x-alumni2.alumni.caltech.edu> (permalink)
References	(2 earlier) <12fb0e96-0ac3-442d-8d04-baaef4234a85@googlegroups.com> <20170607164800.a6fba9d07170ec5d056d25a0@gmail.com> <878tl3g5jw.fsf@bsb.me.uk> <kfnmv9h9d47.fsf@x-alumni2.alumni.caltech.edu> <878tl0fjh1.fsf@gmail.com>

Show all headers | View raw

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?

Thread

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

csiph-web