Possible Bootloader Optimization in inflate (get rid of unnecessary 32k Window)

Possible Bootloader Optimization in inflate (get rid of unnecessary 32k Window)

[Axel Kittenberger]

Hello, Whom do I talk to about acceptance of Patches in the Bootloader?

I have seen, and coded once some time ago for priv. uses, do infalte the 
gziped linux kernel at boottime in "arch/i386/boot/compressed/misc.c" and " 
windowlib/inflate.c" the deflation algorthimn uses a 32k backtrack window. 
Whenever it is full, it copies it .... into the memory. 

While this window makes a lot of sense in an userspace application like 
gunzip, it does not make a lot sense in the bootloader. As userspace 
application the window is flushed to a file when full. The bootloader 
"flushes" it to memory (copies it in memory). That 1 time copy of the whole 
kernel can be optimized away, since we do not keep track of a window since 
the inflater can read what it has written right in the computer memory, while 
it unpacks the kernel.

What would the optimization be worth? 
* A faster uncompressing of the kernel, since a total 1-time memcopy of the 
whole kernel is been optimized away.
* I'm not sure about the size, the memory or disk footprint. If the 32k static 
(!) memory array in compressed/misc.c, I don't know if it safes 32k running 
memory, or 32k on-disk size. Since I don't know the indepth working of these.

Before I code this again (I know that this optimization has worked with a 2.4 
kernel), I want to ask, would such patch be accepted? now or once ever? who 
should I forward this?

Greetings,
Axel

Re: Possible Bootloader Optimization in inflate (get rid of unnecessary 32k Window)

[Marc Singer]

On Thu, Dec 22, 2005 at 01:52:23PM +0100, Axel Kittenberger wrote:
> Hello, Whom do I talk to about acceptance of Patches in the Bootloader?
> 
> I have seen, and coded once some time ago for priv. uses, do infalte the 
> gziped linux kernel at boottime in "arch/i386/boot/compressed/misc.c" and " 
> windowlib/inflate.c" the deflation algorthimn uses a 32k backtrack window. 
> Whenever it is full, it copies it .... into the memory. 
> 
> While this window makes a lot of sense in an userspace application like 
> gunzip, it does not make a lot sense in the bootloader. As userspace 
> application the window is flushed to a file when full. The bootloader 
> "flushes" it to memory (copies it in memory). That 1 time copy of the whole 
> kernel can be optimized away, since we do not keep track of a window since 
> the inflater can read what it has written right in the computer memory, while 
> it unpacks the kernel.
> 
> What would the optimization be worth? 
> * A faster uncompressing of the kernel, since a total 1-time memcopy of the 
> whole kernel is been optimized away.

Have you timed this operation?  I would predict that the time to copy
the kernel is nominal as compared the the time taken to perform the
decompression.

Re: Possible Bootloader Optimization in inflate (get rid of unnecessary 32k Window)

[Axel Kittenberger]

> Have you timed this operation?  I would predict that the time to copy
> the kernel is nominal as compared the the time taken to perform the
> decompression.

In the current version it is defleated AND copied. The optimization would
reduce it by 1 copy.

Greetings, Axel

Re: Possible Bootloader Optimization in inflate (get rid of unnecessary 32k Window)

[Marc Singer]

On Thu, Dec 22, 2005 at 07:12:38PM +0100, Axel Kittenberger wrote:
> > Have you timed this operation?  I would predict that the time to copy
> > the kernel is nominal as compared the the time taken to perform the
> > decompression.
> 
> In the current version it is defleated AND copied. The optimization would
> reduce it by 1 copy.

Right.  And the time to perform that one copy is exactly...?

I doubt that it is a significant percentage of the whole operation.

> 
> Greetings, Axel

Re: Possible Bootloader Optimization in inflate (get rid of unnecessary 32k Window)

[Axel Kittenberger]

> Right.  And the time to perform that one copy is exactly...?
>
> I doubt that it is a significant percentage of the whole operation.

Well Yes I agree, I guess also it isn't. Its roughly the time you need to
copy 1 MB memory around. I just noticed that it is in fact after all still
unneccary and that in fact could be optimized away. As some
window-management could can be optimized away.

I would volunteer to take the time to code it, but only if i have a good
feeling that it would be accepted... if not, well than okay for me also, i
will do other things :o)

Greetings, Axel

Re: Possible Bootloader Optimization in inflate (get rid of unnecessary 32k Window)

[Hans Kristian Rosbach]

On Thu, 2005-12-22 at 20:04 +0100, Axel Kittenberger wrote:
> > Right.  And the time to perform that one copy is exactly...?
> >
> > I doubt that it is a significant percentage of the whole operation.
> 
> Well Yes I agree, I guess also it isn't. Its roughly the time you need to
> copy 1 MB memory around. I just noticed that it is in fact after all still
> unneccary and that in fact could be optimized away. As some
> window-management could can be optimized away.
> 
> I would volunteer to take the time to code it, but only if i have a good
> feeling that it would be accepted... if not, well than okay for me also, i
> will do other things :o)

I would think this would be a welcome optimization for embedded
platforms even if not included in mainline. Embedded platforms
often dont have very fast memory, but nevertheless are
required to boot ASAP.

-HK

Re: Possible Bootloader Optimization in inflate (get rid of unnecessary 32k Window)

[Jan Engelhardt]

>> > Right.  And the time to perform that one copy is exactly...?
>> >
>> > I doubt that it is a significant percentage of the whole operation.
>> 
>> Well Yes I agree, I guess also it isn't. Its roughly the time you need to
>> copy 1 MB memory around.
>
>I would think this would be a welcome optimization for embedded
>platforms even if not included in mainline. Embedded platforms
>often dont have very fast memory, but nevertheless are
>required to boot ASAP.

Do old i386s count? I've got one that ran 2.6.11 perfectly (even w/o 
-tiny), but kernel decompression is what took most time. (At 3.00 bogomips, 
the world looks quite different!)


Jan Engelhardt
-- 

Re: Possible Bootloader Optimization in inflate (get rid of unnecessary 32k Window)

[Folkert van Heusden]

> > > Have you timed this operation?  I would predict that the time to copy
> > > the kernel is nominal as compared the the time taken to perform the
> > > decompression.
> > In the current version it is defleated AND copied. The optimization would
> > reduce it by 1 copy.
> Right.  And the time to perform that one copy is exactly...?
> I doubt that it is a significant percentage of the whole operation.

On the other hand it makes the kernel a few bytes smaller :-)


Folkert van Heusden

-- 
Try MultiTail! Multiple windows with logfiles, filtered with regular
expressions, colored output, etc. etc. www.vanheusden.com/multitail/
----------------------------------------------------------------------
Get your PGP/GPG key signed at www.biglumber.com!
----------------------------------------------------------------------
Phone: +31-6-41278122, PGP-key: 1F28D8AE, www.vanheusden.com

Re: Possible Bootloader Optimization in inflate (get rid of unnecessary 32k Window)

[Axel Kittenberger]

> On the other hand it makes the kernel a few bytes smaller :-)

Well on rather slow machines it is a bit faster indeed, I did code it 3
years ago for an embedded system (embedded PowerPC). 'til now I just never
found the time to offer a patch back to "vanilla" linux. I recently just
thought I could ask maybe if it is after all desired even so....

Greetings, Axel

Re: Possible Bootloader Optimization in inflate (get rid of unnecessary 32k Window)

[Jan Engelhardt]

>> On the other hand it makes the kernel a few bytes smaller :-)
>
>Well on rather slow machines it is a bit faster indeed, I did code it 3
>years ago for an embedded system (embedded PowerPC). 'til now I just never
>found the time to offer a patch back to "vanilla" linux. I recently just
>thought I could ask maybe if it is after all desired even so....

Well if it's about size, why is not something better than gzip used yet?
Like bzip2, 7z or whatever comes to mind? Is it because of the amount of 
memory required for decompression?


Jan

Re: Possible Bootloader Optimization in inflate (get rid of unnecessary 32k Window)

[Coywolf Qi Hunt]

2005/12/22, Axel Kittenberger <axel.kernel@kittenberger.net>:
> Hello, Whom do I talk to about acceptance of Patches in the Bootloader?
>
> I have seen, and coded once some time ago for priv. uses, do infalte the
> gziped linux kernel at boottime in "arch/i386/boot/compressed/misc.c" and "
> windowlib/inflate.c" the deflation algorthimn uses a 32k backtrack window.
> Whenever it is full, it copies it .... into the memory.
>
> While this window makes a lot of sense in an userspace application like
> gunzip, it does not make a lot sense in the bootloader. As userspace
> application the window is flushed to a file when full. The bootloader
> "flushes" it to memory (copies it in memory). That 1 time copy of the whole
> kernel can be optimized away, since we do not keep track of a window since
> the inflater can read what it has written right in the computer memory, while
> it unpacks the kernel.
>
> What would the optimization be worth?
> * A faster uncompressing of the kernel, since a total 1-time memcopy of the
> whole kernel is been optimized away.
> * I'm not sure about the size, the memory or disk footprint. If the 32k static
> (!) memory array in compressed/misc.c, I don't know if it safes 32k running
> memory, or 32k on-disk size. Since I don't know the indepth working of these.

Neither for saving running memory (discarded), nor on-disk size
(window[WSIZE] resides in BSS).

>
> Before I code this again (I know that this optimization has worked with a 2.4

I think 2.6 didn't change much in this field.

> kernel), I want to ask, would such patch be accepted? now or once ever? who
> should I forward this?

"H. Peter Anvin" <hpa@zytor.com>, and akpm, and even Linus. I'd like
to see your patch. It would be instructive.


-- Coywolf

Re: Possible Bootloader Optimization in inflate (get rid of unnecessary 32k Window)

[H. Peter Anvin]

Coywolf Qi Hunt wrote:
>>
>>What would the optimization be worth?
>>* A faster uncompressing of the kernel, since a total 1-time memcopy of the
>>whole kernel is been optimized away.
>>* I'm not sure about the size, the memory or disk footprint. If the 32k static
>>(!) memory array in compressed/misc.c, I don't know if it safes 32k running
>>memory, or 32k on-disk size. Since I don't know the indepth working of these 
> 
> Neither for saving running memory (discarded), nor on-disk size
> (window[WSIZE] resides in BSS).
> 

I've actually implemented this for another application (where BSS was at 
a premium.)  It even has some nice benefits for code size if you do it 
right.

It indeed would avoid a cache-to-memory copy, but that's not really a 
huge deal, which is why noone has worried too much about it.

	-hpa