Re: Algorithm Optimization

Path	csiph.com!newsfeed.xs4all.nl!newsfeed7.news.xs4all.nl!tr3.eu1.usenetexpress.com!feeder.usenetexpress.com!tr1.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end
From	"Johann 'Myrkraverk' Oskarsson" <johann@myrkraverk.com>
Newsgroups	comp.compilers
Subject	Re: Algorithm Optimization
Date	Wed, 21 Apr 2021 16:29:30 +0000
Organization	Compilers Central
Lines	26
Sender	news@iecc.com
Approved	comp.compilers@iecc.com
Message-ID	<21-04-011@comp.compilers> (permalink)
References	<20-09-032@comp.compilers> <20-09-035@comp.compilers> <20-09-036@comp.compilers>
Mime-Version	1.0
Content-Type	text/plain; charset="UTF-8"
Injection-Info	gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="8258"; mail-complaints-to="abuse@iecc.com"
Keywords	optimize
Posted-Date	21 Apr 2021 12:40:15 EDT
X-submission-address	compilers@iecc.com
X-moderator-address	compilers-request@iecc.com
X-FAQ-and-archives	http://compilers.iecc.com
Xref	csiph.com comp.compilers:2650

Show key headers only | View raw

On 16/09/2020 5:25 am, gah4 wrote:

> I think I remember this being discussed many years ago.

> One thought was that someone codes bubblesort, and the compiler
> generates quicksort. Small complication that bubblesort is stable, and
> quicksort isn't. (Add an array with the original position to break
> ties.)

Here are even more dragons.

What if you're sorting exactly three elements?  In that situation, I'll
be very surprised if bubblesort doesn't outperform all other algorithms.

How does the /compiler/ decide that an algorithm is better, based
on data it never sees?  Even if we account for profile guided optimi-
zations, we shouldn't allow the compiler to adjust for /what if this is
run with more data in production?/ kind of questions.

If you want to go down this rabbit hole, I'd much prefer warnings than
outright algorithm changes.

--
Johann

 I'm not from the internet, I just work there.

Back to comp.compilers | Previous | Next — Previous in thread | Next in thread | Find similar

Thread

Algorithm Optimization "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-13 13:00 -0400
  Re: Algorithm Optimization Elijah Stone <elronnd@elronnd.net> - 2020-09-14 20:47 -0700
    Re: Algorithm Optimization "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-15 00:42 -0400
  Re: Algorithm Optimization "Derek M. Jones" <derek@_NOSPAM_knosof.co.uk> - 2020-09-15 14:29 +0100
    Re: Algorithm Optimization gah4 <gah4@u.washington.edu> - 2020-09-15 22:25 -0700
      Re: Algorithm Optimization "Derek M. Jones" <derek@_NOSPAM_knosof.co.uk> - 2020-09-16 20:11 +0100
      Re: Algorithm Optimization Richard Harnden <richard.nospam@gmail.com> - 2020-09-16 22:45 +0100
      Re: Algorithm Optimization Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2020-09-17 06:35 +0200
        Re: Algorithm Optimization "A. K." <minforth@arcor.de> - 2020-09-21 02:12 -0700
      Re: Algorithm Optimization "Johann 'Myrkraverk' Oskarsson" <johann@myrkraverk.com> - 2021-04-21 16:29 +0000
  Re: Algorithm Optimization "mwmarkland@gmail.com" <mwmarkland@gmail.com> - 2020-09-16 07:57 -0700
    Re: Algorithm Optimization "Rick C. Hodgin" <rick.c.hodgin@gmail.com> - 2020-09-16 11:44 -0400
    Re: Algorithm Optimization gah4 <gah4@u.washington.edu> - 2020-09-16 13:59 -0700
      Re: Algorithm Optimization Thomas Koenig <tkoenig@netcologne.de> - 2020-09-17 06:39 +0000
  Re: Algorithm Optimization Hans-Peter Diettrich <DrDiettrich1@netscape.net> - 2020-12-13 23:13 +0100
    Re: Algorithm Optimization gah4 <gah4@u.washington.edu> - 2020-12-20 22:45 -0800

csiph-web