OT: Does Linux have any "Perfect Code"

OT: Does Linux have any "Perfect Code"

[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):

>
>
> 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...
>
> Posted by Bryan Cantrill on November 14, 2007 at 07:51 AM PST #

Does Linux have any such examples true software perfection?

Re: OT: Does Linux have any "Perfect Code"

[David Miller]

From: Russell Leighton <russ@elegant-software.com>
Date: Wed, 14 Nov 2007 20:21:04 -0500

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

Re: OT: Does Linux have any "Perfect Code"

[Eric Dumazet]

Russell Leighton a écrit :
> 
> 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):
> 
>>
>>
>> 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...
>>
>> 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

Re: OT: Does Linux have any "Perfect Code"

[David Miller]

From: Eric Dumazet <dada1@cosmosbay.com>
Date: Thu, 15 Nov 2007 07:29:47 +0100

> 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

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.

Re: OT: Does Linux have any "Perfect Code"

[Andi Kleen]

Eric Dumazet <dada1@cosmosbay.com> writes:
>
> 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. 

> 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

Re: OT: Does Linux have any "Perfect Code"

[Philippe Elie]

On Wed, 14 Nov 2007 at 20:21 +0000, Russell Leighton wrote:

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

-- 
Phe

Re: OT: Does Linux have any "Perfect Code"

[Michael Gerdau]

[-- Attachment #1: Type: text/plain, Size: 2192 bytes --]

> 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 :)

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

>  		/*
>  		 * 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
-- 
 Vote against SPAM - see http://www.politik-digital.de/spam/
 Michael Gerdau       email: mgerdau@tiscali.de
 GPG-keys available on request or at public keyserver

[-- Attachment #2: This is a digitally signed message part. --]
[-- Type: application/pgp-signature, Size: 194 bytes --]

Re: OT: Does Linux have any "Perfect Code"

[Daniel Barkalow]

On Thu, 15 Nov 2007, Michael Gerdau wrote:

> > 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();
> 
> <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.
>
> ...
> 
> 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*

Re: OT: Does Linux have any "Perfect Code"

[Geert Uytterhoeven]

On Thu, 15 Nov 2007, Daniel Barkalow wrote:
> On Thu, 15 Nov 2007, Michael Gerdau wrote:
> > > 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();
> > 
> > <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.
> >
> > ...
> > 
> > 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.

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 -- geert@linux-m68k.org

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

Re: OT: Does Linux have any "Perfect Code"

[Chris Friesen]

Michael Gerdau wrote:

> 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