Skip to contentSkip to conversation

OT: Does Linux have any "Perfect Code"

DISCUSSION Russell Leighton 9 participants 10 messages Nov 15, 2007 – Nov 17, 2007

lore
Share & tools
lore
#0 lore raw

Bryan Cantrill of Sun (ala DTrace) has a notion of perfect code:

http://blogs.sun.com/bmc/entry/on_i_dreaming_in_code

He also has some examples (from bottom comment section of above):

Quoted 14 lines

Can you list a small number of examples of "software perfection"?

Posted by Russell Leighton on November 14, 2007 at 04:02 AM PST #

Russell,

My canonical small example of perfection in Solaris would be Jeff Bonwick's mod-by-a-billion code in hrt2ts():

http://cvs.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/uts/common/os/timers.c#875

Solaris of course has lots of bigger, more complicated examples. Now on the one hand, one wants to refrain from pointing to thousands of lines of code and saying that there are no bugs therein, but on the other, there are many subsystems that have been in place and in heavy use for years without defect or modification. At the risk of being egocentric, the cyclic subsystem (which is executed at least 100 times per second on every Solaris system) had its last substantial fix over six years ago, and its last fix of any flavor over three years ago:

Quoted 7 lines

http://cvs.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/uts/common/os/cyclic.c

Modesty (and the lack, of course, of a proof of its correctness) prevents me from calling the cyclic subsystem perfect -- but such as unknown defects remain, there are damn few of them, and we can say that they must be a result of highly usual (or at least, heretofore unseen) circumstances.

A non-Solaris example -- and one that I've been known to use as the canonical example of the persistence of software -- is Super Mario Kart. This is a game that was developed (to its completion) fifteen years ago for the Super Nintendo console. Source code, to the best of my knowledge, is not publicly available and may indeed be lost -- but the binaries persist and (if my coworkers are any indication) remain in active use. Given the longevity of, say, Homer's Odyssey, there is reason to believe that Super Mario Kart will survive in perpetuity -- that thousands of years from now, twenty-somethings somewhere will be using the software exactly as it is used today. Is this perfection? Perhaps not -- but it also might not be discernible from perfection...

Posted by Bryan Cantrill on November 14, 2007 at 07:51 AM PST #

Does Linux have any such examples true software perfection?

#1 lore raw

From: Russell Leighton <[email protected]>
Date: Wed, 14 Nov 2007 20:21:04 -0500

Quoted 4 lines
Quoted 4 lines

At the risk of being egocentric, the cyclic subsystem (which is executed at least 100 times per second on every Solaris system) had its last substantial fix over six years ago, and its last fix of any flavor over three years ago:

Yeah, if you develop at the glacial pace Solaris does, don't add any features to cyclics or work on scalability improvment, sure it can be bug free and untouched for 6 years.

I think all of this talk of perfect code is just trolling by the Solaris folks.

#2 lore raw
In reply to Russell Leighton
Quoted 25 lines · Russell Leighton

Bryan Cantrill of Sun (ala DTrace) has a notion of perfect code:

http://blogs.sun.com/bmc/entry/on_i_dreaming_in_code

He also has some examples (from bottom comment section of above):

Quoted 18 lines

Can you list a small number of examples of "software perfection"?

Posted by Russell Leighton on November 14, 2007 at 04:02 AM PST #

Russell,

My canonical small example of perfection in Solaris would be Jeff Bonwick's mod-by-a-billion code in hrt2ts():

http://cvs.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/uts/common/os/timers.c#875

Solaris of course has lots of bigger, more complicated examples. Now on the one hand, one wants to refrain from pointing to thousands of lines of code and saying that there are no bugs therein, but on the other, there are many subsystems that have been in place and in heavy use for years without defect or modification. At the risk of being egocentric, the cyclic subsystem (which is executed at least 100 times per second on every Solaris system) had its last substantial fix over six years ago, and its last fix of any flavor over three years ago:

http://cvs.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/uts/common/os/cyclic.c

Quoted 8 lines
Quoted 5 lines

Modesty (and the lack, of course, of a proof of its correctness) prevents me from calling the cyclic subsystem perfect -- but such as unknown defects remain, there are damn few of them, and we can say that they must be a result of highly usual (or at least, heretofore unseen) circumstances.

A non-Solaris example -- and one that I've been known to use as the canonical example of the persistence of software -- is Super Mario Kart. This is a game that was developed (to its completion) fifteen years ago for the Super Nintendo console. Source code, to the best of my knowledge, is not publicly available and may indeed be lost -- but the binaries persist and (if my coworkers are any indication) remain in active use. Given the longevity of, say, Homer's Odyssey, there is reason to believe that Super Mario Kart will survive in perpetuity -- that thousands of years from now, twenty-somethings somewhere will be using the software exactly as it is used today. Is this perfection? Perhaps not -- but it also might not be discernible from perfection...

Posted by Bryan Cantrill on November 14, 2007 at 07:51 AM PST #

Does Linux have any such examples true software perfection?

I dont know, (what a strange idea is it anyway ?) but reading two Solaris functions just gave me the example of non true software perfection.

http://cvs.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/uts/common/os/timers.c#1106

I would say this code was OK 10 years ago.

Now that a processor (say an Opteron in 64 bits mode, used on SUN hardware), can perform a multiply in few cycles, ts2hrt() could use a normal multiply and an addition.

Processors are improving, compilers are improving, memory sizes are increasing, source code (and algorithms) should be changed accordingly.

(gcc for example already knows the reciprocal division trick and so can compile this :

hrt2ts_div(hrtime_t hrt, timestruc_t *tsp)

{
    tsp->tv_nsec = do_div(hrt, NANOSEC);
    tsp->tv_sec = hrt;
}

to :

movq %rdi, %rdx
movabsq $19342813113834067, %rax
shrq $9, %rdx
mulq %rdx
shrq $11, %rdx
imulq $1000000000, %rdx, %rax
movq %rdx, (%rsi)
subq %rax, %rdi
movl %edi, 8(%rsi)

while

hrtime_t
ts2hrt(const timestruc_t *tsp)
{
return tsp->tv_sec * NANOSEC + tsp->tv_nsec;
}

can be inlined as it is trivial (and much faster than Solaris version)

        movq    (%rdi), %rdx
        mov     8(%rdi), %eax
        imulq   $1000000000, %rdx, %rdx
        addq    %rdx, %rax
#3 lore raw

From: Eric Dumazet <[email protected]>
Date: Thu, 15 Nov 2007 07:29:47 +0100

Quoted 6 lines

hrtime_t
ts2hrt(const timestruc_t *tsp)
{
return tsp->tv_sec * NANOSEC + tsp->tv_nsec;
}

Quoted 6 lines

can be inlined as it is trivial (and much faster than Solaris version)

         movq    (%rdi), %rdx
         mov     8(%rdi), %eax
         imulq   $1000000000, %rdx, %rdx
         addq    %rdx, %rax

This is exactly the kind of thing that is not happening to the Solaris code base. These gradual improvements that are being done constantly to every nook and cranny of the Linux kernel.

Code sits untouched for 6+ years in the Solaris tree not because it's perfect and bug free, but rather because Sun simply does not have the environment and resources with which to make the kinds of ongoing improvements Linux can.

The things Sun is trying to say is so great about the Solaris code base is actually, as shown by Eric, it's greatest weakness. Development is glacial and a lot of stuff simply does not get looked at.

Someone who really wants to get some kind of idea on what scale Linux development is compared to Solaris should sit down with a current Linux git tree and a current OpenSolaris mercurial checkout and do some comparisons.

Here is one you could ferret out that I am pretty sure of. I bet that in the 2.6.24 merge window (1.5 weeks of merging patches) we had more individual contributors to the Linux kernel than OpenSolaris has had in it's entire existence.

#4 lore raw
In reply to Eric Dumazet
Quoted 4 lines · Eric Dumazet

http://cvs.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/uts/common/os/timers.c#1106

I would say this code was OK 10 years ago.

I would have expected 1997 compilers to already do these standard muliplication optimizations.

Quoted 3 lines

Now that a processor (say an Opteron in 64 bits mode, used on SUN hardware), can perform a multiply in few cycles, ts2hrt() could use a normal multiply and an addition.

To be fair Linux runs on a lot of CPUs which are not quite as fast at multiplying as an Opteron, especially not for 64bit multiplies. So some optimizations might be still a good idea. For divisions at least Linux also actively does this.

On the other hand compilers also get worse. Modern gccs now turn

while (nsec >= NANOSEC) {
      nsec -= NANOSEC;
      sec++;
}

into a division which is actually much slower. Or insert unnecessary cache misses randomly. See the recent gcc thread safety discussion where it turned out that the thread breaking optimization is actually more a general pessimization.

-Andi

#5 lore raw
In reply to Russell Leighton
Quoted 51 lines · Russell Leighton

Bryan Cantrill of Sun (ala DTrace) has a notion of perfect code:

http://blogs.sun.com/bmc/entry/on_i_dreaming_in_code

He also has some examples (from bottom comment section of above):

Quoted 44 lines

Can you list a small number of examples of "software perfection"?

Posted by Russell Leighton on November 14, 2007 at 04:02 AM PST #

Russell,

My canonical small example of perfection in Solaris would be Jeff Bonwick's mod-by-a-billion code in hrt2ts():

http://cvs.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/uts/
common/os/timers.c#875

Solaris of course has lots of bigger, more complicated examples. Now on the one hand, one wants to refrain from pointing to thousands of lines of code and saying that there are no bugs therein, but on the other, there are many subsystems that have been in place and in heavy use for years without defect or modification. At the risk of being egocentric, the cyclic subsystem (which is executed at least 100 times per second on every Solaris system) had its last substantial fix over six years ago, and its last fix of any flavor over three years ago:

http://cvs.opensolaris.org/source/xref/onnv/onnv-gate/usr/src/uts/
common/os/cyclic.c

Modesty (and the lack, of course, of a proof of its correctness) prevents me from calling the cyclic subsystem perfect -- but such as unknown defects remain, there are damn few of them, and we can say that they must be a result of highly usual (or at least, heretofore unseen) circumstances.

A non-Solaris example -- and one that I've been known to use as the canonical example of the persistence of software -- is Super Mario Kart. This is a game that was developed (to its completion) fifteen years ago for the Super Nintendo console. Source code, to the best of my knowledge, is not publicly available and may indeed be lost -- but the binaries persist and (if my coworkers are any indication) remain in active use. Given the longevity of, say, Homer's Odyssey, there is reason to believe that Super Mario Kart will survive in perpetuity -- that thousands of years from now, twenty-somethings somewhere will be using the software exactly as it is used today. Is this perfection? Perhaps not -- but it also might not be discernible from perfection...

Quoted 3 lines
Quoted 1 line

Posted by Bryan Cantrill on November 14, 2007 at 07:51 AM PST #

Does Linux have any such examples true software perfection?

This code is far to be perfect, some part is outdated, bcopy() use instead of memcpy() for example. More annoying are the comment, the file is 3306 lines while there is only 1640 line of code, nothing bad per se but looking some comments:

/*
* Before we begin this operation, disable kernel preemption. */
kpreempt_disable();

uhh...

or

 	if (cyclic->cy_pend != 0) {
		/*

* The pend is non-zero; ...

I will never guessed that, w/o the comment :)

/*
* We have both a left and a right child. We need to compare
* the expiration times of the children to determine which
* expires earlier.
*/
if (cyclics[right].cy_expire < cyclics[left].cy_expire) {

writing array[index] in C is already a promise than index is in [0-array size)

Signature · 1 line
Phe
#6 lore raw
Quoted 13 lines

This code is far to be perfect, some part is outdated, bcopy() use instead of memcpy() for example. More annoying are the comment, the file is 3306 lines while there is only 1640 line of code, nothing bad per se but looking some comments:

(quoted diff) +0 -0
 		/*
 		 * Before we begin this operation, disable kernel preemption.
 		 */
 		kpreempt_disable();

uhh...

Quoted 7 lines

or

 	if (cyclic->cy_pend != 0) {
		/*

* The pend is non-zero; ...

I will never guessed that, w/o the comment :)

<disclaimer>
I'm not a kernel developer.
</disclaimer>

That having said:
I really do like such obvious (as in: for those knowing the stuff anyway) comments when looking at code and probably concepts I'm not familiar with.

IMO there is no need to belittle this type of comment. IMO any casual reader not familiar with the whole set of functions possibly involved will be thankful for this type of comment - I certainly am.

Quoted 9 lines
(quoted diff) +0 -0
 		/*
 		 * We have both a left and a right child.  We need to compare
 		 * the expiration times of the children to determine which
 		 * expires earlier.
 		 */
 		if (cyclics[right].cy_expire < cyclics[left].cy_expire) {

writing array[index] in C is already a promise than index is in [0-array size)

Yes. And ?

FWIW whenever I tried to look at kernel code I'm usually facing the decision to
- either give up trying to understand what is intended or
- do a thorough search to learn everything required

I usually give up due to time constraints.

I mean, isn't the whole purpose of comments to help those not familiar with the code to understand it's purpose and possibly the intention of the author (just in case the author had coded a bug) ?

From my PoV this establishes a steep learning curve for "outsiders" to start working on the kernel.
[just in case: don't give me anything along the line "this is an inherent test as to the fitness of the potential hacker" ;]

Just my thoughts,
Michael

Signature · 3 lines
 Vote against SPAM - see http://www.politik-digital.de/spam/
 Michael Gerdau       email: [email protected]
 GPG-keys available on request or at public keyserver
#7 lore raw
Quoted 18 lines · Michael Gerdau

Review

Quoted 9 lines

This code is far to be perfect, some part is outdated, bcopy() use instead of memcpy() for example. More annoying are the comment, the file is 3306 lines while there is only 1640 line of code, nothing bad per se but looking some comments:

(quoted diff) +0 -0
 		/*
 		 * Before we begin this operation, disable kernel preemption.
 		 */
 		kpreempt_disable();

<disclaimer>
I'm not a kernel developer.
</disclaimer>

That having said:
I really do like such obvious (as in: for those knowing the stuff anyway) comments when looking at code and probably concepts I'm not familiar with.

Quoted 5 lines

...

I mean, isn't the whole purpose of comments to help those not familiar with the code to understand it's purpose and possibly the intention of the author (just in case the author had coded a bug) ?

That's the problem with really obvious comments. In the example above, that function had better disable kernel preemption with a name like that, and, assuming it's before the code begins the operation in sequence, we know when we're doing it. But the comment fails to explain why we need to disable kernel preemption before beginning the operation, just that we are doing so. Having the comment merely distracts the reader from the fact that the purpose of the code and the intention of the author are completely undocumented. And there's a realy chance that this comment or ones like it cause this statement and the place in the code where things would go wrong if preemption weren't disabled to not fit on the reader's screen together, so it is not only unclear what the author's intention was, but it is harder to figure out from looking at the code than it would be without comments, because fewer clues are actually visible at the same time, since each of them takes up extra screen space.

The code itself should be written to tell the reader everything there is to know about what it does, and the comments in code should only tell the reader why it does that.

-Daniel
*This .sig left intentionally blank*

#8 lore raw
Quoted 40 lines · Daniel Barkalow
Quoted 18 lines · Michael Gerdau

Review

Quoted 9 lines

This code is far to be perfect, some part is outdated, bcopy() use instead of memcpy() for example. More annoying are the comment, the file is 3306 lines while there is only 1640 line of code, nothing bad per se but looking some comments:

(quoted diff) +0 -0
 		/*
 		 * Before we begin this operation, disable kernel preemption.
 		 */
 		kpreempt_disable();

<disclaimer>
I'm not a kernel developer.
</disclaimer>

That having said:
I really do like such obvious (as in: for those knowing the stuff anyway) comments when looking at code and probably concepts I'm not familiar with.

Quoted 5 lines

...

I mean, isn't the whole purpose of comments to help those not familiar with the code to understand it's purpose and possibly the intention of the author (just in case the author had coded a bug) ?

That's the problem with really obvious comments. In the example above, that function had better disable kernel preemption with a name like that, and, assuming it's before the code begins the operation in sequence, we know when we're doing it. But the comment fails to explain why we need to disable kernel preemption before beginning the operation, just that we are doing so. Having the comment merely distracts the reader from the fact that the purpose of the code and the intention of the author are completely undocumented. And there's a realy chance that this comment or ones like it cause this statement and the place in the code where things would go wrong if preemption weren't disabled to not fit on the reader's screen together, so it is not only unclear what the author's intention was, but it is harder to figure out from looking at the code than it would be without comments, because fewer clues are actually visible at the same time, since each of them takes up extra screen space.

Quoted 3 lines

The code itself should be written to tell the reader everything there is to know about what it does, and the comments in code should only tell the reader why it does that.

Agreed!

At work we used to have a contractor who documented _every_ single statement with a literal C/C++-to-English translation. Nobody liked it, except him. It was completely unreadable.
Of course a few of these comments went out-of-sync with the actual code...

Gr{oetje,eeting}s,

Geert

--
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- [email protected]

In personal conversations with technical people, I call myself a hacker. But when I'm talking to journalists I just say "programmer" or something like that.
-- Linus Torvalds

#9 lore raw
In reply to Michael Gerdau
Quoted 7 lines · Michael Gerdau

That having said:
I really do like such obvious (as in: for those knowing the stuff anyway) comments when looking at code and probably concepts I'm not familiar with.

IMO there is no need to belittle this type of comment. IMO any casual reader not familiar with the whole set of functions possibly involved will be thankful for this type of comment - I certainly am.

Obvious comments explaining _what_ the code is doing are annoying. They're fluff. You can see what the code is doing.

The critical comments are the ones that explain _why_ and _how_. The comments should give the higher level view as to the rationale for that code.

Of course if you've got some highly-optimized bit of black magic there had better be some good comments explaining what's going on...but there should also be some comments explaining why we need the magic in the first place.

Chris