HN Explorer

Ask HN: What's the most elegant piece of code you've seen?

139 points by mc42 ↗ HN
Lots of people have spent years writing programs spanning platforms, servers, services, and languages. However, efficient and elegant code is far and few between.

What code has stood out to you for being elegant and efficient? Why or why not?

90 comments

[ 2.7 ms ] story [ 160 ms ] thread
d13
Commodore 64's Basic random maze generator:

10 PRINT CHR$(205.5+RND(1)); : GOTO 10

https://www.youtube.com/watch?v=m9joBLOZVEo

agildehaus
It prints either \ or /, not sure how amazing that is. It also isn't a maze, considering it's unlikely any of those paths leads to an exit.
jibalt
I think you have quite missed the point.
alexandercrohde
Fair point. Making a a traditional 1-solution maze in 1 line is qualitatively more impressive than making a complex pattern of passages in 1 line.
austinjp
I've got to say, that is truly wonderful.
tebeka
Peter Norvig's Spell Checker http://norvig.com/spell-correct.html

A lot of other code he writes as well.

jessedhillon
Fast inverse square root[0] is something that I encountered in the mid-2000s in the Q3A source code. It took me a really long time to understand it, and I eventually had to show it to some professors before I really understood what was going on and why this worked.

That's really an example of how arbitrary human thought processes are. When you release the constraint that your code has to have some human-comprehensible analog, you might arrive at interesting results.

[0] https://en.wikipedia.org/wiki/Fast_inverse_square_root

pkaye
Most of that is fairly straightforward. It is using newton's method to calculate the inverse square root. But to get that with one or two iterations, you need a good estimate to start with. The square root of the floating point exponent is half the value. Knowing how the floating point number is packed, we know a right shift is equal to divide by two and negate it. What remains is how the shift affects the mantissa and if some correction factor is needed. This could have been gotten by least square optimization to minimize the error.
jessedhillon
> Knowing how the floating point number is packed, we know a right shift is equal to divide by two and negate it.

Shifting an IEEE754 floating point number does not have that effect.[0] The fact that it doesn't do that is the source of the "mystery" of fast inverse square root.

[0] https://gist.github.com/jessedhillon/386fa964e822e529f6c1

wasd
I love the story of the fast inverse square root. A bizzare piece of code from quake 3 shows up on usenet with a magic constant that calculates the inverse square root faster than table lookups and approximately four times faster than regular floating point division. Inverse square roots are used to compute angles of incidence and reflection for lighting and shading in computer graphics. Author unknown but was once thought as of Carmack.

https://en.m.wikipedia.org/wiki/Fast_inverse_square_root

matt_wulfeck
I would say that the actual source code there is extremely ugly. It may be an elegant solution, but there's no way I would want to crawl around in that repo:

    x2 = number * 0.5F;
	y  = number;
	i  = * ( long * ) &y;                               // evil floating point bit level hacking
	i  = 0x5f3759df - ( i >> 1 );               
    // what the fuck? 
	y  = * ( float * ) &i;
projectileboy
I learned a lot reading Paul Graham's source code for Arc. And John Carmack's (and others) code for Quake is also very educational.
jamessantiago
Doom 3 was touted[1] as having some "exceptional beauty." Naming, spacing of properties, consistency, and how multiple parameterized calls were formatted are quite nice. You can see an example on github[2], but for some reason the spacing is a bit off in the web view. I'd recommend cloning a local copy and taking a look.

[1] http://kotaku.com/5975610/the-exceptional-beauty-of-doom-3s-...

[2] https://github.com/id-Software/DOOM-3/blob/master/neo/game/a...

nostrademons
Jeff Dean's original implementation of MapReduce.

It was, IIRC, only 3 C++ classes and just a few hundred lines of code. It outsourced much of the distribution, task running, and disk-access tasks to other Google infrastructure, and only focused on running the computation, collecting results for each key, and distributing to the reducers.

The current (as of ~2012, so not that current anymore) version of MapReduce is much faster and more reliable, but there's a certain elegance to starting a trillion-dollar industry with a few hundred lines of code.

There was another doozy, also by Jeff Dean, in the current (again, as of 2012) MapReduce code. It was an external sorting algorithm, and like most external sorts, it worked by writing a bunch of whole-machine-RAM sized temporary files and then performing an N-way merge. But how did it sort the machine's RAM? Using the STL qsort() function, of course! But how do you sort ~64GB of data efficiently using a standard-library function? He'd written a custom comparator that compared whole records at a time, using IIRC compiler intrinsics that compiled down into SIMD instructions and did some sort of Duff's-Device like unrolling to account for varying key lengths. It was a very clever mix of stock standard library functions with highly-optimized, specialized code.

StephanTLavavej
Minor correction: qsort() is CRT, std::sort() is STL.
nostrademons
My memory's actually hazy over whether it was qsort or sort; my intuition is that it would've been qsort because QuickSort is what you'd use when you need an in-place sort with little additional RAM required, but it's been so long that I honestly don't remember.
JoachimSchipper
Not a C++ programmer, but isn't std::stable_sort usually mergesort, while std::sort is usually an introspective quicksort?
jibalt
Yes.
nostrademons
Ah, good. I'd initially written std::sort in the comment and then went back and edited it because I was like "Isn't std::sort usually mergesort? That wouldn't work here because it takes extra space." It's been a while since I've written C++.
chengiz
You are assuming qsort is Quicksort and std::sort is not. Both typically use quicksort; but neither is required to.
StephanTLavavej
In C++11, std::sort() is forbidden from being just a quicksort, as it's required to have worst-case O(N log N) complexity.
ganduG
Do you have a link to the code?
andor
He's talking about proprietary Google code.
nostrademons
Dead proprietary Google code, too - it's long since replaced, I was looking back in the version control history out of curiosity.
dividuum
Since it's old and no longer relevant to the Google, it would be really interesting to have that code in some kind of code museum, as I feel it gave an interesting insight on how Google did big data (the real one, not the marketing one) back then. Not sure it that's feasible, but I guess it doesn't hurt to ask.
nostrademons
I wish, but it's unfortunately not my call to make. A few other companies have done this, eg. Microsoft open-sourcing Altair Basic about 30 years after it came out or id open-sourcing DOOM. Maybe if I ever go back to work for them, I can propose it. For now, consider getting a job at Google if you want to peek into the VCS history.
vram22
I'd read somewhere [1] that the built-in Python sort function has a lot of good / clever optimizations too, though maybe not of the same kinds that you describe, i.e. may not be at machine language level. Tim Peters did a lot of that, per what I read, though others may have too.

[1] Think I read it in the Python Cookbook, 2nd Edition, which is a very good book, BTW.

nostrademons
Different kinds of optimizations. Timsort tries to collect runs and falls back on insertion sort for them; it exploits the fact that much real-world data is already partially sorted to reduce the number of comparisons made. This optimization exploits the fact that MapReduce keys are always strings in contiguous areas of memory, and are often fairly large, to compare them really quickly.
nine_k
Lisp interpreter loop.
Chris_Newton
On a larger scale than most suggestions so far, I’ve always been impressed with SQLite. The developers have managed to create a useful-in-the-real-world tool, small and efficient enough for even quite demanding applications like embedded systems work.

The original source code was solid and well documented in the parts I’ve seen, but the remarkable thing to me is the way they distribute it: it comes as a single ANSI C file and a single matching header, which they refer to as the “amalgamation”. It therefore works just about anywhere, has no packaging or dependency hell issues, can be be incorporated into any build process in moments, and can be statically linked and fully optimised.

weeksie
Love that source code. I dug around in it quite a bit when I was teaching myself about B-tree implementations about ten years ago.
jcoffland
Perl 6......JK of course.
mojojojojo
Perl is amazing.
jcoffland
Have you ever read the code? I actually think preprocessor macros can be quite useful but Perl dials it up to 11.
Radim
For me, the memorable pieces of code are those that made me "want to become a programmer", to choose the path I chose, way back in the day.

Unsurprisingly, these were games:

1) A C64 "SnakeByte-like" game, whose exact name I forgot. It was written entirely in BASIC 2.0 (so you could list and read the source code), and with me having no C64 manual, and no English, it was a true revelation. So much fun and beauty emerging from such a concise, approachable program!

2) An ancient five-in-a-row implementation, I think in BASIC again or maybe Pascal. I remember the shock after seeing how simple the code was, compared to its (surprisingly good) playing strength and speed. My github user name, "piskvorky", is an echo of this old experience :-)

The underlying appeal seems to be a combination of simple, elegant rules giving rise to complex and fun behaviour. That, to me, is elegance.

[deleted]
(comment deleted)
sssilver
Naive factorial implementation in Haskell

factorial 0 = 1

factorial n = n * factorial (n - 1)

agumonkey
fib, with its tail biting zip felt even better.

one of my favorite intermediate recursive function is powerset

lokedhs
The Solaris kernel source. I got a deep appreciation for the elegance of it when I was working for Sun a long time ago. I can enjoy analysing that code base, which is opposite to the feeling I get when looking at the Linux code.

It's not overly clever, but it's incredibly clear and easy to understand.

jibalt
Much of that code was inherited from Bell Labs UNIX, much of which came from Ritchie and Thompson.
lokedhs
While I don't know exactly what parts were inherited, I have looked at parts of the code that definitely was not inherited from Bell Labs (for features that are comparatively new) and they are also very nice to read.

Perhaps they just followed in the footsteps of the masters, but whatever the reason, the code is, in opinion, incredibly nice to work with.

gaze
Jeff Bonwick is one of the best systems programmers ever
bitwize
Duff's Device.

Much of the NetBSD code base.

Pick a hack by Oleg Kiselyov.

The Commodore KERNAL.

jacquesm
Hands down Peter Norvig's hashlife and sudoku solver.
SixSigma
The Plan9 Source code

https://github.com/0intro/plan9

> A Professor of Computer Science gave a paper on how he uses Linux to teach his undergraduates about operating systems. Someone in the audience asked 'why use Linux rather than Plan 9?' and the professor answered: Plan 9 looks like it was written by experts; Linux looks like something my students could aspire to write.

But see also the HN thread :

Code which every programmer must read before dying

https://news.ycombinator.com/item?id=2466129

kpil
Although not 'real' code, almost anything from The Wizard Book is either nice, elegant or sometimes a minor epiphany for a C-damaged mind...

Probably not that efficient in terms of raw CPU grunt though...

eps
I worked for a networking software developer at some point in the past and they were considering licensing a VPN stack from the SSH company [1]. That thing was in C and the sample code included was stunningly beautiful as was the documentation - well modularized, consistent, good naming notation, but above all it was concise. I think I still have a CD with the SDK demo, I can pull up some code from there if anyone's interested.

[1] https://en.wikipedia.org/wiki/SSH_Communications_Security

visof
quicksort [] = []

quicksort (p:xs) = (quicksort lesser) ++ [p] ++ (quicksort greater)

    where

        lesser = filter (< p) xs

        greater = filter (>= p) xs
alisey
Keep in mind that this algorithm is not in-place, so it wouldn't be fair to say that it's more 'elegant' than imperative quicksort implementations.