View Single Post
Old 03 August 2015, 14:47   #218
Registered User

Megol's Avatar
Join Date: May 2014
Location: inside the emulator
Posts: 304
Originally Posted by Mrs Beanbag View Post
i had to go for a long walk before writing this reply.

it is as if everything i have said about algorithmic time complexity has just gone down a black hole. i said that a lot of problems in modern code are caused by programmers not understanding it, well it seems that old-timer asm coders don't understand it either. They know a hash map is "fast" but that's about it.

Maybe hand-coded asm (by an expert) is 4 times faster (i remember reading the figure 3 times faster on average, elsewhere) but let's just say 10 times for simplicity. In any case, it is a more-or-less constant factor for any given compiler.
Such huge differences is either the result of the compiler not being mapped well to the processor or using a feature that can't be directly exposed in the high level language model.
The solution to those problem is in most cases inline assembly code or using intrinsics.

In the general case what causes compilers to be slower is rigid calling conventions.

The point is, you could write the most efficient bubble sort ever in hand-coded asm, but even a crudely implemented quick sort written in AMOS Basic would still outperform it given a sufficiently large input. The choice of algorithm makes far more difference than the choice of language for all but fairly trivial operations. Asm might be ten times faster than any given language, but an O(n log n) algorithm might be hundreds, thousands, even millions of times faster than a naive O(n^2) algorithm, for the size of data sets you are dealing with.
Obviously true for anybody with some programming education. Unless one have a problem with (almost) sorted data

Well then you would say, if you wrote the quick sort in asm it would be ever faster still. And you'd be right. But the user really doesn't care if he gets his result in a tenth of a second or a hundredth of a second, but he sure as hell doesn't want to have to wait ten minutes.

Of course we care about speed, but performance isn't the only consideration. There are other priorities too, such as development time, portability, maintainability, and of course being able to hire people who can actually do it.
And the programmer that have more time on his/her hands can spend it by testing other algorithms potentially leading of huge speedups.

Strictly speaking assembly can be faster than higher level languages (but not generally) but for most problems runtime generated machine code is the fastest. But that's even messier.
Megol is offline  
Page generated in 0.04212 seconds with 10 queries