Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Efficiency is fundamentally at odds with elegance (2013)

yosefk.com

Post reply on HN
Print view View original

21–30 of 46 posts

Re: Efficiency is fundamentally at odds with elegance (2013)

#21

Post by tonyarkles »

phaedrus wrote: post #16
phkahler wrote: post #12

Symbolic representation vs floating point as a trade of elegance? The suggestion of maintaining non-numeric representations falls flat very quickly in a number of cases: 5th root of a polynomial. There is no closed form solution that could be carried through other computations. Integrals. There is no general method for symbolic integration. A physics simulation cannot maintain closed form solutions and it would not b…

I recently started playing an Android game called Euclidea. It teaches the basics of compass and ruler construction (geometry) and asks you to complete various tasks such as bisecting an angle or finding a circle equally spaced between four points, etc. The goal is to do so with a certain minimal number of moves. Having never taken a geometry class, but being an experienced programmer, I was struck by the difference…

It's funny, I've been diving into a lot of math I haven't used in a while lately (via the Coursera "Robotics Specialization"). Since I don't particularly trust myself to do huge amounts of symbolic manipulation/integration/etc on paper, I've picked up Maxima as a CAS to try to keep track of it all. More than once, I've gotten some set of equations into a form that I'm ready to use to do numerical iteration/gradient descent/whatever, and Maxima just kind of... pops out a closed form solution for the problem I'm trying to solve.

My basic approach to straddle the symbolic/numeric divide is to keep things symbolic until the last minute and then substitute in the boundary conditions/constants/whatever at the end and see what pops out. If Maxima pops out a closed form solution, I'll analyze that geometrically to make sure it makes sense and isn't just a quirk of the specific boundary conditions I've chosen, and if it doesn't really have a closed form solution, I'll use the simplified equations and run them through a solver of whatever kind (ODE, gradient descent, etc).

Re: Efficiency is fundamentally at odds with elegance (2013)

#22

Post by [deleted] »

mattnewport wrote: post #20
diegoperini wrote: post #17

Earlier quoted context omitted.

Noob question: What does std::sort do (aside from sorting oc) ? Which feature of it were you highlighting?

Compared to C style qsort what std::sort gives you are type safety, convenience (types that already define a suitable operator< will use it automatically without you having to explicitly create a comparison function), correctness/convenience (you don't have to manually specify the number of elements to sort, it's deduced from the range) and efficiency (the comparison can be inlined by the compiler much more easily th…

[deleted]

Re: Efficiency is fundamentally at odds with elegance (2013)

#23

Post by jstimpfle »

mattnewport wrote: post #20
diegoperini wrote: post #17

Earlier quoted context omitted.

Noob question: What does std::sort do (aside from sorting oc) ? Which feature of it were you highlighting?

Compared to C style qsort what std::sort gives you are type safety, convenience (types that already define a suitable operator< will use it automatically without you having to explicitly create a comparison function), correctness/convenience (you don't have to manually specify the number of elements to sort, it's deduced from the range) and efficiency (the comparison can be inlined by the compiler much more easily th…

TBH the efficiency thing is irrelevant. I once compared std::sort and qsort on large integer arrays (which is where you can expect the greatest speedup) and the speedup was less than 2x on my machine. Furthermore the cases where sorting could ever become a noticeable bottleneck are pretty rare.

Meanwhile each std::sort instantiation costs a few hundred bytes of machine code and increases the project's compilation times.

When performance ever matters, you tune your sort algorithm and implementation to the data - you use a bucket sort for example. Much larger speedups than 2x to be had this way. std::sort cannot do that.

I like the type safety of std::sort vs qsort, though, even though I don't find pursuing "type safety" a good idea in general.

Re: Efficiency is fundamentally at odds with elegance (2013)

#24

Post by mattnewport »

jstimpfle wrote: post #23
mattnewport wrote: post #20

Earlier quoted context omitted.

Compared to C style qsort what std::sort gives you are type safety, convenience (types that already define a suitable operator< will use it automatically without you having to explicitly create a comparison function), correctness/convenience (you don't have to manually specify the number of elements to sort, it's deduced from the range) and efficiency (the comparison can be inlined by the compiler much more easily th…

TBH the efficiency thing is irrelevant. I once compared std::sort and qsort on large integer arrays (which is where you can expect the greatest speedup) and the speedup was less than 2x on my machine. Furthermore the cases where sorting could ever become a noticeable bottleneck are pretty rare. Meanwhile each std::sort instantiation costs a few hundred bytes of machine code and increases the project's compilation tim…

I don't consider a 2x speedup "irrelevant". It's also not the case that large integer arrays are where I would expect the greatest speedup. The greatest speedup would be on arrays that fit in L1 cache where function call overhead is going to be the most significant factor rather than cache misses.

Compile times and code bloat with templates are genuine issues but they are being improved both with improved compilers and linkers and with C++ standard changes (modules should be a big help for compile times).

Type safety is in my opinion a good example of elegance and efficiency being generally aligned. Typically improving type safety makes code more elegant, catches bugs and give opportunities for better efficiency in my experience.

Re: Efficiency is fundamentally at odds with elegance (2013)

#25

Post by jstimpfle »

mattnewport wrote: post #24
jstimpfle wrote: post #23

Earlier quoted context omitted.

TBH the efficiency thing is irrelevant. I once compared std::sort and qsort on large integer arrays (which is where you can expect the greatest speedup) and the speedup was less than 2x on my machine. Furthermore the cases where sorting could ever become a noticeable bottleneck are pretty rare. Meanwhile each std::sort instantiation costs a few hundred bytes of machine code and increases the project's compilation tim…

I don't consider a 2x speedup "irrelevant". It's also not the case that large integer arrays are where I would expect the greatest speedup. The greatest speedup would be on arrays that fit in L1 cache where function call overhead is going to be the most significant factor rather than cache misses. Compile times and code bloat with templates are genuine issues but they are being improved both with improved compilers a…

Again, it was an artificial benchmark. I sorted millions of integers. 2x is not measured in a real-life program. It's the absolute upper limit what you can ever expect. Most programs don't spend a noticeable amount time in sorting at all. Program performance usually is dominated by other things, like I/O. Now what is 50% of "not a noticeable amount of time"? Right, it's irrelevant.

But 2x is a hard number, so people tend to think it's important and forget about all the disadvantages which are hard to measure but have far more ramifications.

And for the rare cases where a sort really matters, you should use an implementation that is tuned to the data. That will bring you larger speed-ups. I could have said "10x" to sound impressive, and it wouldn't be wrong in most cases, but it's simply not possible to make a blanket statement. It depends. It could be more than 10x.

Even better, you can often construct the data so it falls out sorted. Speed-up: INFx. Machine code and compile time: Zero.

It's the same story for types in general. They lead to wrong and bloated design and boilerplate code when you overdo it. Which prevents the important optimizations that could simplify program structure enormously, and kill many more bugs this way.

> The greatest speedup would be on arrays that fit in L1 cache where function call overhead is going to be the most significant factor rather than cache misses.

The smaller you make the data, the less time it takes to sort it with whatever implementation, the less important the implementation is.

Furthermore, shouldn't we expect most sorting applications to be pretty cache-friendly? E.g. Quicksort scans the array sequentially, log n times.

Re: Efficiency is fundamentally at odds with elegance (2013)

#26

Post by socketnaut »

This just seems like survivorship bias. An algorithm / tool / technology tends not to remain in use if something that is both more elegant and more efficient is available. Therefore, if you survey the well known options you'll see a negative relationship between elegance and efficiency. It doesn't imply a general relationship nor does it preclude the discovery of an approach that is both more elegant and more efficient than anything available today.

Re: Efficiency is fundamentally at odds with elegance (2013)

#27

Post by mattnewport »

jstimpfle wrote: post #25
mattnewport wrote: post #24

Earlier quoted context omitted.

I don't consider a 2x speedup "irrelevant". It's also not the case that large integer arrays are where I would expect the greatest speedup. The greatest speedup would be on arrays that fit in L1 cache where function call overhead is going to be the most significant factor rather than cache misses. Compile times and code bloat with templates are genuine issues but they are being improved both with improved compilers a…

Again, it was an artificial benchmark. I sorted millions of integers. 2x is not measured in a real-life program. It's the absolute upper limit what you can ever expect. Most programs don't spend a noticeable amount time in sorting at all. Program performance usually is dominated by other things, like I/O. Now what is 50% of "not a noticeable amount of time"? Right, it's irrelevant. But 2x is a hard number, so people…

> It's the same story for types in general. They lead to wrong and bloated design and boilerplate code when you overdo it.

I wouldn't recommend overdoing anything, by definition. My experience however is that when done correctly type safety usually makes code both more elegant and more efficient. Like anything in programming it is often done poorly however and people sometimes seem to confuse types with OOP concepts in C++. A lot of people seem to worry about certain programming practices because they fear other people abusing them. Those discussions are of little interest to me. I'm interested in how I can best write good code, not worrying about what other people are doing.

Re: Efficiency is fundamentally at odds with elegance (2013)

#28

Post by ben509 »

mattnewport wrote: post #19

It's not my experience that efficiency is "fundamentally" at odds with elegance. Elegance can be a hard concept to pin down and has a somewhat subjective component but I often find situations where code can be made both more efficient and more elegant. There are certainly cases where I can't see a way to make the code more efficient without sacrificing elegance however. They don't seem to be fundamentally at odds but…

The underlying need is to traverse and update data structures, so language designers went with universally mutable objects with arbitrary references. That makes the representation of an individual object quite simple, and it does centralize the complexity of memory management in garbage collection, so it's a good engineering decision. But real GC requires extensive tuning (different "generations", stop-the-world pauses, etc) and that's simply not an elegant solution.

My approach was to revisit that underlying need, and I settled on a data model that simply prohibits cyclic data structures, so memory management doesn't have to be more complex than reference counting. Now, I'm still going to have to implement zippers and paths and such to handle traversal, but I think that will still be far cleaner. I have some notes here if you're curious: https://tenet-lang.org/types.html

Re: Efficiency is fundamentally at odds with elegance (2013)

#29

Post by blablabla123 »

I find this discussion tiring, also I have actually seen people vividly defending both positions: that the most efficient code is also very elegant and the opposite, as here.

It depends so much on the situation, skill/experience of the person/team building the stuff and what focus one has.

Sometimes an elegant solution opens completely new perspectives on performance optimizations.

Re: Efficiency is fundamentally at odds with elegance (2013)

#30

Post by edjroot »

I recently watched a documentary where Dijkstra says the opposite:

https://youtu.be/RCCigccBzIU?t=1125

"One of the things I discovered as early as the 1960s is that mathematical elegance is not a question of aesthetics, of taste or fashion, but something you can translate into a technical notion.

"The Concise Oxford Dictionary gives as one of the meanings of 'elegant' 'ingeniously simple and effective'.

"In practice a program is manageable if you make a truly elegant program, firstly because it is shorter than most alternatives and consists of discrete parts, each of which you can replace by an alternative implementation without influencing the rest of the program, but also, curiously, the most elegant programs are often the most efficient."

Post reply on HN