Path: csiph.com!xmission!news.alt.net!feeder.usenetexpress.com!tr3.iad1.usenetexpress.com!border1.nntp.dca1.giganews.com!nntp.giganews.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Elijah Stone Newsgroups: comp.compilers Subject: Re: Algorithm Optimization Date: Mon, 14 Sep 2020 20:47:11 -0700 Organization: A noiseless patient Spider Lines: 31 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <20-09-033@comp.compilers> References: <20-09-032@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="32206"; mail-complaints-to="abuse@iecc.com" Keywords: optimize Posted-Date: 14 Sep 2020 23:53:06 EDT X-submission-address: compilers@iecc.com X-moderator-address: compilers-request@iecc.com X-FAQ-and-archives: http://compilers.iecc.com In-Reply-To: <20-09-032@comp.compilers> Xref: csiph.com comp.compilers:2604 On Sun, 13 Sep 2020, Rick C. Hodgin wrote: > I've been pursuing the idea of what I call algorithm optimization. > It's the idea that algorithms coded by individuals may not be optimal, > and may require refactoring / re-engineering to be made optimal based on > what's trying to be achieved. I agree with John: generally, it should be the programmer's job to choose the right algorithm. Otherwise, the compiler just becomes an algorithm library, and--well, if you're going to build an algorithm library, why not just expose it directly to your language's users? The main problem is that algorithms are /heavily/ dependant on data structures. So if you want to change an algorithm significantly, you'll need to change its data structures, and usually the compiler can't tell if external code is going to look at those data structures. In the case of your example, though it's hard to tell, I expect that the optimal structure would be a freelist, but because 'first' is a global variable, modifications to it have to be the same with and without optimizations. (You might be able to get around this by making 'first' a static variable local to iAlloc_new_sdata; but this approach doesn't scale, and it's already putting pressure on the programmer's algorithms, which is what you were trying to avoid.) A secondary problem is compile time: recognizing algorithms is likely to be very expensive, which is not a great user experience. (Though llvm/gcc do recognize some things, like algorithm for triangle numbers.) -- time flies like an arrow; fruit flies like a banana