*Abstract is slower than concrete.* You are asking the CPU to repeatedly
discover at run-time what you were unwilling or unable to specify at
compile time. Maybe you're being lazy or maybe there is a good reason, but
the key notion is crucial: the actual instructions that the computer
performs are type-specific so any coding that is type-unspecific forces an
analysis and branch table somewhere (preprocessor expansion, compiler
concretization, run-time dispatch among equals, or in hardware.)
*Differences are often insignificant.* Common CPUs are fast compared to
common data sizes (so the difference is not important to the user) and most
real programs do more in their inner-loops than the exchanges in these sort
functions (so the amortized extra time may barely be measurable).
*Point of view is important*. Programmers coming from the dynamic typing
world expect abstraction and find system design without it difficult.
They've always been paying the overhead, even for "i = i + 1." From this
perspective, it is not that interfaces are slow, but that not using
interfaces is unusually fast. (The same argument applies to writing
critical sections in assembler vs a higher-level language, making use of
special SIMD or AES-assist instructions vs assembler, GPU/MIC coprocessors
vs the main CPU, or BitCoin and security ASICs.)
*Usage trumps mechanism.* Examine the sort package's source code
(go/src/pkg/sort/sort.go) and look at Ints() in line 270. What happens is
that the API that knows you want to sort an int slice in non-decreasing
order uses the abstract sorting engine by specifying the use of default
int-specific Len(), Less(), and Swap() functions. That's easy, but it
forces the default sorting engine to be abstract "all the way down."
Instead, it could have said, "Oh, I have special code for this" and simply
been the int-specific version of sorting in to non-decreasing order with
custom code for this case (and similarly for other built-in types). If it
were coded this way, then the abstract-to-concrete mechanism would happen
once per sort call and be immeasurable in terms of performance penalty.
That's an example of style of usage being more important than cost of usage.
*Solutions are well known.* The situation of wanting to perform a fixed
algorithm on various types of data is common. The desire to do this in a
"factored" way, where the logic is written once with data types as
parameters is as old as algorithms. I can easily imagine a student asking
Euclid, "but, master, what if we need the GCD of a 64-bit number? You only
showed us what to do for 16-bit numbers. Is the algorithm for the larger
type related in any way to the smaller?" Both Euclid and I agree that the
algorithms are the same and the difference in types is trivial. I use m4 or
mcpp (http://mcpp.sourceforge.net/) to make such trivialities, well,
trivial. I do this because Go does not have a native macro, parameterized,
or other abstract-to-specific type management facility. Maybe this could be
a good research project for Go 1.3 interval -- not to adopt an answer but
to explore alternatives with vigor in search of consensus.
On Thu, Dec 5, 2013 at 12:58 AM, Kevin Gillette
On Wednesday, December 4, 2013 10:29:48 PM UTC-7, Joshua Marsh wrote:
I agree performance isn't everything. I love Interfaces. They make
testing substantially easier for me. The idea of duck-typing in my mind is
so much cleaner as well than other similar language features. In my
experience though, you start to find critical sections of code where a
performance improvement can save lots of money.
I've found that constant-time-reduction optimizations (which this is) have
only fixed hardware cost savings, but that deprioritizing work spent
towards such optimizations has closer to linear savings in time and money.
In other words, at typical (or even sub-typical) programmer wages, it
generally makes more financial sense to buy 2x faster hardware than it does
to pay the programmer to make the program run only 2x faster. If it were a
quadratic time savings (which this isn't) or even a linear savings (which
this also isn't), then it would start to make financial sense to have
programmers begin to rewrite code.
I'm not sure I agree that the example is some obscure corner case. Sure
not everyone is using sort, but the notion of a CPU bound critical section
of code seems fairly common from my experience. It never occurred to me
that stripping out interfaces would cause an improvement (which in the
example isn't a mild improvement, it's drastic).
The downside of this is that to avoid use of interfaces in sort, you have
to fork, and then maintain, one or more type-specific versions of sort. For
many times of input, there are far better sort algorithms than quicksort,
thus forking the stdlib sort to have a slightly faster integer quicksort
seems pointless when there are, e.g. bucket sorts you could be using.
As far as the benchmarks go, 1 << 10 seems a bit small, and may or may not
be biased toward testing the overhead (or lack thereof) involved with
algorithm heuristics than it is toward actually testing the sort behavior.
Last time I looked, the stdlib sort is a hybrid sort that is predominantly
quicksort based -- but any hybrid sort has some overhead, either during an
initial probe, or in periodic checks, to determine which sorting behavior
to employ. I'd consider 16 << 20 or more to produce timings that are more
likely to be representative of the core algorithms involved, though of
course, the timings may come out to be much the same.
Additionally, you're creating a lot of unnecessary garbage in your b.N
loops, since the data is being consistently reinitialized each iteration
irrespective of the contents of the data slice -- that allocation can be
moved to the function scope. Though it's not being timed, in the spirit of
discussing performance critical code, you could turn your initialization
loops (based on len(data)) into range loops to potentially avoid boundary
checks on each iteration -- and it will look cleaner too.
You received this message because you are subscribed to the Google Groups
To unsubscribe from this group and stop receiving emails from it, send an
email to firstname.lastname@example.org.
For more options, visit https://groups.google.com/groups/opt_out.
Michael T. Jones | Chief Technology Advocate | email@example.com
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to firstname.lastname@example.org.
For more options, visit https://groups.google.com/groups/opt_out.