Path: csiph.com!3.us.feeder.erje.net!feeder.erje.net!news.snarked.org!news.linkpendium.com!news.linkpendium.com!news.iecc.com!.POSTED.news.iecc.com!nerds-end From: Martin Ward Newsgroups: comp.compilers Subject: Re: Add nested-function support in a language the based on a stack-machine Date: Fri, 23 Mar 2018 10:44:20 +0000 Organization: Compilers Central Lines: 49 Sender: news@iecc.com Approved: comp.compilers@iecc.com Message-ID: <18-03-090@comp.compilers> References: <6effed5e-6c90-f5f4-0c80-a03c61fd2127@gkc.org.uk> <18-03-042@comp.compilers> <18-03-047@comp.compilers> <18-03-075@comp.compilers> <18-03-077@comp.compilers> Mime-Version: 1.0 Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Injection-Info: gal.iecc.com; posting-host="news.iecc.com:2001:470:1f07:1126:0:676f:7373:6970"; logging-data="29344"; mail-complaints-to="abuse@iecc.com" Keywords: history, performance, comment Posted-Date: 23 Mar 2018 08:40:37 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:2022 On 19/03/18 19:50, Gene Wirchenko wrote: >> Faster machines and larger memories mean that it becomes more >> important to use the best algorithms. > > How does that follow? It follows because data expands to fill the memory available. > One could argue exactly the opposite as there are resources to > waste. > > [Depends on the algorithms. If they're linear, things are fine, not > so fine if they're O(N^2) or O(2^N) -John] My first computer had 8K of RAM and a 1MHz clock speed. If I wanted to sort 1,000 values I could use bubble sort, O(N^2), or quicksort, O(N log N). So, bubble sort would need of the order of 1,000,000 instructions and take about 1 second: this might well be acceptable for an operation you only need to do a few times an hour. Quicksort would need of the order of 10,000 instructions and take 0.01 seconds. My current laptop (not the latest model) has 8Gb of RAM: literally, over a million times as much RAM, and a 1.7 GHz clock. Even accounting for more powerful instructions, the clock is only of the order 10,000 times faster, while the memory is 1,000,000 times larger. Now 1,000,000,000 values will fit in RAM. Sorting these with bubble sort will need of the order 10^18 instructions which takes 100,000,000 seconds (over 1,000 years) while quicksort needs 300,000,000,000 instructions and takes only a few seconds. For a linear algorithm, say a linear search, my first computer takes 0.001 seconds to process the data, while my new laptop takes 0.1 seconds. So if I need to execute this linear algorithm more than 10 times a second, my old computer will be fine but my new laptop would struggle. I would need to look hard for a sub-linear algorithm. Conclusion: even for linear algorithms things may not be fine and more powerful sub-linear algorithms may be needed. -- Martin Dr Martin Ward | Email: martin@gkc.org.uk | http://www.gkc.org.uk G.K.Chesterton site: http://www.gkc.org.uk/gkc | Erdos number: 4 [Give or take the detail that bubble sort is never the right algorithm since insertion sort is shorter and faster, I agree. -John]