> On Wed, 6 Dec 2000, Patrik Stridvall wrote:
> > I think we have different definitions of heuristics.
>
> Definitely.
>
> > But that is not an heuristic. If it it referenced or recusive it is
> > always correct to not inline it. There is no incorrect cases and
> > therefore it is not an heuristic it is an algoritm and i'm not
> > possitive that it is even a non-optimal algoritm.
>
> Making a distinction between heuristics and algorithms does not really
> make sense here. Heuristics are not (black) magic, when they are part
> of a program, they are algorithms as well.
>
> > Then we have a little missundering with the word heurstics.
> > There are four kinds of algoritms.
> >
> > 1. Optimal algoritms
> > 2. Non-optimal algoritms
> > 3 Algoritms buggy by design
> > 4. Algoritms buggy by misstake
> >
> > As far as I'm concern 3 is heuristics,
> > but you seem to wish to include 2 as well.
>
> I have been dealing with heuristics of various kinds, but "buggy by
> design" fits none of those.
Well, winapi_check is buggy by design since it tries to be clever
and make assumptions on how the input looks like and will in strange
case miss things or crash since it can't handle them. This is not by
misstake, it is by design, since handling all cases is too difficult.
However it is still useful despite this.
> Many problems simply do not lend themselves to a general and optimal
> strategy, that's where heuristics come into play. (Even Quicksort is
> usually implemented with heuristics to choose the "mean" value, and
> you won't call Quicksort buggy by design, will you?)
>
> And yes, I do have scientific papers in referreed conferences that
> deal with heuristics! :-)
>
> On Wed, 6 Dec 2000, Ove Kaaven wrote:
> > (heuristics should be limited to what can be optimized, which is
> > perfectly okay, since that can never generate incorrect code).
>
> Yup: An optimizer employing heuristics does not generate
> incorrect code
> due to this (unless it has a bug). It may, however, generate
> suboptimal
> code in some cases -- that's where the heuristics may fail.
Alright "buggy by design" is a little oversimplification,
even though it makes a good quoute, that I don't remember
where I found, see wine/tools/winapi_check/winapi_check.
What I mean is that a "heuristic" do not cover all strange
cases like normal "algoritms" does and tries to be clever
and make assumptions on how the input usually looks like.
Just like your example concerning QuickSort above.
This might lead to very strange results if there is strange
input. At best it will result in a sub-optimal result (and/or
performance), at worst things will totally break down.
In the QuickSort case above it fortunately only leads to
sub-optimal performance.
I personally usually refer to "algoritms" that might totally
break down as heuristics and call the other kind non-optimal
algoritms.
That said I have seen people calling certain kind of non-optimal
algoritms heuristics so I'm not unused to that classification.
In short I refer to algoritms that tries to be _too_ "clever" as
heuristics while some uses it for normal "clever" algoritms
as well.
That said I remember reading somewhere that there are _some_
optimizations that GNU C employs at higher (like -O6)
optimization level that tries to be _too_ clever and thereby
causing it to generate wrong code for some strange cases.
That was what I was refering to when I said heuristics are bad.
Perhaps the person said the GNU C sometimes was too clever was
wrong I don't know.
Anyway this small remark cause Ove sidestep the real issue
and personally attack me instead of addressing it.
While Ove obviously seem to know how GNU C works he seems
quite unable to debate whether the semantics of
__attribute__((unused)) is sane or not and seems,
judging from his remark about "absolute truth",
belive that the GNU C designer and/or implementors are
infailable and any attempt to question them is in his
own word either prejudical or FUD.
I fully understand that the way it currently works
_might_ be by design eventhough I still call it a
bug since it AFAICS doesn't really make sense, as I tried
to explain, but Ove seems to not want to discuss the
that issue for some reason.
He still haven't provided any example where my suggested
semantic will break down and since few distributions AFAIK
compile with -O6 it will not really effect many people
and the few people that really really want those extra
bytes can always, as I tried to explain, fix their code,
which can arguably be consider "broken" since they rely
on something undocumented.
If anybody is worried about compilation speed the condition
that it can be removed if the compiler is _really_ sure it
isn't used can be removed it makes very little difference
IRL. Perhaps that even would be a saner semantics.
It certainly would be simpler.
But since Ove seems quite unable to contemplate the idea that
the GNU C designers and/or implementors was wrong (or rather
short sighted) it isn't very much to discuss is it?
