howto count lines - fast

[H. S. Teoh via Digitalmars-d-learn]

On Thu, Jun 01, 2017 at 08:39:07AM +0100, Russel Winder via Digitalmars-d-learn wrote:
> On Wed, 2017-05-31 at 16:37 -0700, H. S. Teoh via Digitalmars-d-learn
> wrote:
> > 
> […]
> > With D, we can have the cake and eat it too.  The understandable /
> > naïve implementation can be available as a fallback (and reference
> > implementation), with OS-specific optimized implementations guarded
> > under version() or static-if blocks so that one could, in theory,
> > provide implementations specific to each supported platform that
> > would give the best performance.
> 
> But isn't that the compiler's job?

Unfortunately, the compiler can only go so far, because it doesn't
understand the larger context of what you're trying to accomplish.
Modern optimizing compilers certainly go a lot further than before, but
still, at some point some amount of human judgment is needed.

Also, compiler implementors do still have to do the "heroics", or
rather, teach the compiler to do the "heroics" when compiling
straightforward code. So while the general programmer probably will have
less need for it, compiler writers still need to know how to do them in
order to write the optimizing compilers in the first place.


> The lesson of functional programming, logic programming, etc. (when
> the acolytes  remember the actual lesson) is that declarative
> expression of goal is more comprehensible to people than detailed
> explanation of how the computer calculates a result. Object-oriented
> computing lost the plot somewhere in the early 2000s.

There is no argument that straightforward code is more comprehensible to
people.  The question here is whether it delivers maximum performance.

We know from Kolgomorov complexity theory that global optimization, in
the general case, is undecidable, so no optimizing compiler is going to
be able to generate optimal code in all cases. There will always be
cases where you have to manually tweak it yourself.  Of course, that
doesn't mean you go around micro-optimizing everything -- the usual
approach is to write it the straightforward way first, then profile it,
identify the hotspots, and find ways to improve performance in the
hotspots. Well, at a higher level, the first order of business is really
to look at it from an algorithmic POV and decide whether or not a
different algorithm ought to be used (and no optimizing compiler can
help you there).  Then if that's still not enough, then you dig into the
details and see if you can squeeze more juice out of your current
algorithms -- if the profiler has indicated that they are the
bottleneck.


> The advance of Scala, Kotlin, Groovy, and now Rust and Go (but only to
> some extent), which D has, is to express algorithms as declarative
> requirements in a dataflow manner.
> 
> One day hardware people will catch up with the hardware innovations of
> the 1970s and 1980s regarding support of dataflow rather than state.

Dataflow can only capture a limited subset of algorithms.  Of course, in
my observation, 90% of code being written today generally belongs in the
category of what I call "linear shuffling of data", i.e., iterate over
some linear set of objects and perform some transformation X on each
object, copying linear memory region X to linear memory region Y,
rearranging some linear set of objects, permuting the order of some
linear set of things, etc..  This category basically subsumes all of GUI
programming and web programming, which in my estimation covers 90% or
maybe even 95% of code out there.  The bulk of game code also falls
under this category -- they are basically a matter of copying X items
from A to B, be they pixels to be copied to the video buffer, traversing
the list of in-game objects to update their current position, direction,
speed, or traversing scanlines of a polygon to map a 3D object to 2D,
etc.. Almost all business logic also falls under this category. All of
these are easily captured by dataflow models.

However, there are algorithms outside of this category, that are not
easily captured by the dataflow model.  Solving certain graph theory
problems, for example, require actual insight into the structure of the
problem than mere "move X items from A to B".  Route planning, which is
an NP-complete problem that, for practical applications, can only be
approximated, and therefore actual thought is required for how you
actually go about solving the problem beyond "data X moves from A to B".
Computing the convex hull of a set of input points, used for solving
optimization problems, if expressed and solved in a naïve way, has
O(n^3) time complexity, and therefore impractical for non-trivial
problem instances.

True, your average general programmer may not even know what a convex
hull problem is, and probably doesn't even need to care -- at worst,
there are already libraries out there that implement the algorithms for
you.  But the point is, *somebody* out there needs to write these
algorithms, and they need to implement these algorithms in an optimal
way so that it will continue to be useful for non-trivial problem sizes.
You cannot just say, "here is the problem specification, now just let
the computer / AI system / whatever figure out for themselves how to
obtain the answer".  *Somebody* has to actually sit down and specify
exactly how to compute the answer, because generic ways of arriving at
the answer are exponential or worse and are therefore useless. And even
a feasible algorithm may require a lot of "heroics" in order to make
medium-sized problems more tractable.  You want your weather forecasting
model to produce an answer by tomorrow before the 10am news, not 3
months later when the answer is no longer relevant.


> > I disagree about the philosophy of "if you need to go faster, use a
> > bigger computer".  There are some inherently complex problems (such
> > as NP-complete, PSPACE-complete, or worse, outright exponential
> > class problems) where the difference between a "heroic
> > implementation" of a computational primitive and a naïve one may
> > mean the difference between obtaining a result in this lifetime vs.
> > practically never. Or, more realistically speaking, the difference
> > between being able to solve moderately-complex problem instances vs.
> > being able to solve only trivial toy instances.  When you're dealing
> > with exponential complexity, every small bit counts, and you can
> > never get a big enough computer.
> 
> There are always places for experimentation, and innovation. Hard
> problems will always be hard, we just need to find the least hard way
> of expressing the solutions.

Some problems are inherently hard, and no amount of searching can reduce
its complexity past a certain limit. These require extreme measures to
be even remotely tractable.


> The crucial thing is that people always work to remove the heroicism
> of the initial solutions, creating new computational models, new
> programming languages, etc. to do it.
[...]

But *somebody* has to implement those computational models and
programming languages.  If nobody knows how to write "heroic" code, then
nobody would know how to write an optimizing compiler that produces such
code either, and these computational models and programming languages
wouldn't exist in the first place.

I know that the average general programmer doesn't (and shouldn't) care.
But *somebody* has to, in order to implement the system in the first
place. *Somebody* had to implement the "heroic" version of memchr so
that others can use it as a primitive. Without that, everyone would have
to roll their own, and it's almost a certainty that the results will be
underwhelming.


T

-- 
Question authority. Don't ask why, just do it.