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

31–40 of 46 posts

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

#31

Post by phkahler »

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…

Since you're into geometric constructions... I've been learning CAD with SolveSpace, which is GPL and has a constraint solver. This is very interesting code to dig into. When you apply constraints to a drawing (midpoint, point on line, parallel, perpendicular, etc..) It creates an internal algebraic expression for that constraint. You end up with a system of equations (internally only) that are constantly enforced as you manipulate a sketch. It's a hybrid approach where the constraints are represented as equations but the solutions are all computed numerically. I think you'd appreciate it.

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

#32

Post by naasking »

ben509 wrote: post #28
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 paus…

> 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.

Not sure I'd call reference counting elegant or efficient either. It has a lot of problems, like spurious updates which kill performance.

If you've already ruled out cycles, then you've ruled out a large class of expressions in your programming language. Perhaps you should revisit region-based memory management to see if it's sufficient, as that will give you optimal space and time use.

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

#33

Post by glaurung_ »

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…

Your comment reminds me of frustrations I ran into when going the opposite direction in college. I majored in mathematics (focusing on pure math) where the goal is typically to produce a solution which is as elegant and readable as possible. In the couple of programming classes I took for my minor, I tended to follow this same approach. If I could write a sexy three line recursive statement that solved the problem in O(n^2) rather than some convoluted nest of loops and tests that did it in O(nlogn) I wanted to go with the first one! It was really hard to make the mental shift from trying to produce something elegant and concise to something fast and memory efficient.

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

#35

Post by sebringj »

Here's an example that made sense to me

elegant (readable / compact)

function isPalindrome(str) { return str == str.split('').reverse().join(''); }

efficient (~50x faster than above)

function isPalindrome(str) { var len = Math.floor(str.length / 2); for (var i = 0; i I would probably say elegance and efficiency are not aligned rather than at odds IMO because they may overlap or may not, they don't have the same goals.

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

#36

Post by kazinator »

sebringj wrote: post #35

Here's an example that made sense to me elegant (readable / compact) function isPalindrome(str) { return str == str.split('').reverse().join(''); } efficient (~50x faster than above) function isPalindrome(str) { var len = Math.floor(str.length / 2); for (var i = 0; i I would probably say elegance and efficiency are not aligned rather than at odds IMO because they may overlap or may not, they don't have the same goals…

Does just str.reverse() not work, by the way.

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

#37

Post by sebringj »

kazinator wrote: post #36
sebringj wrote: post #35

Here's an example that made sense to me elegant (readable / compact) function isPalindrome(str) { return str == str.split('').reverse().join(''); } efficient (~50x faster than above) function isPalindrome(str) { var len = Math.floor(str.length / 2); for (var i = 0; i I would probably say elegance and efficiency are not aligned rather than at odds IMO because they may overlap or may not, they don't have the same goals…

Does just str.reverse() not work, by the way.

I didn't see that on MDN but would be cool. I get 'abc'.reverse() exception that it is not a function.

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

#38

Post by myWindoonn »

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…

There is an elegant universal notation for integers, called "variable-width integers" or "varints" or "bigints" or similar. It is reviled amongst many, and doesn't see much use.

There is an elegant universal notation for rationals, called "quote notation" or "finite continued fractions" or "p-adic rationals". It is largely unknown and sees next-to-no use.

There is an elegant universal notation for computable reals, called "computability". We use this all the time, but almost never for computing reals.

Floating-point numbers are fussy and require careful management in order to avoid buggy algorithms. In contrast, there exists an algorithm (although it's an open problem to express it in a quick way!) for taking the fifth root of any generalized continued fraction or any Turing-computable real, in a way that allows the result to be used in further computation. Somebody should tackle the Gaussian distributions next!

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

#39

Post by yters »

Symbolic manipulation is undecidable, hence programmers prefer numeric approaches. But, symbolic approaches are clearly superior if the programmer does them a priori. I can convert a completely intractable bruteforce combinatorics problem into a very tractable algorithm with some human symbolic preprocessing (i.e. math).

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

#40

Post by Jtsummers »

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…

> Most programs don't spend a noticeable amount time in sorting at all.

I think a more important point is that most programs that depend on sorting data will use a data structure which can sort itself rather than trying to sort lists/arrays of such large numbers (especially when exceeding a certain threshold of data records). Consider if you're getting millions of records and need them in some order (potentially different from how they arrive), it makes more sense (especially with the IO delays) to spend the extra time on inserting into a sorted structure while waiting for the next piece of data to arrive. Interleaving the two activities, rather than waiting for all IO to finish and then sorting a massive list (forcing them to be serialized). The concurrent version can benefit from the inherent parallel nature of dealing with IO-bound and CPU-bound activities.

Post reply on HN