Possible Bootloader Optimization in inflate (get rid of unnecessary 32k Window)
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
Quoted 15 lines · 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.
Quoted 3 lines
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.
Quoted 3 lines
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
Quoted 6 lines · Axel Kittenberger
Quoted 3 lines
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.
Quoted 2 lines
Greetings, Axel
Quoted 3 lines
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
Quoted 4 lines · Axel Kittenberger
Quoted 3 lines
Right. And the time to perform that one copy is exactly...?
I doubt that it is a significant percentage of the whole operation.
Quoted 8 lines
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
Quoted 5 lines
Quoted 5 lines
Quoted 4 lines
Right. And the time to perform that one copy is exactly...?
I doubt that it is a significant percentage of the whole operation.
Quoted 7 lines
Quoted 2 lines
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
Quoted 7 lines
Quoted 5 lines
Quoted 3 lines
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
Signature · 6 lines
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
Quoted 1 line
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
Quoted 7 lines
Quoted 2 lines
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
2005/12/22, Axel Kittenberger <[email protected]>:
Quoted 15 lines
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.
Quoted 6 lines
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 incompressed/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).
Quoted 2 lines
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.
Quoted 2 lines
kernel), I want to ask, would such patch be accepted? now or once ever? who should I forward this?
"H. Peter Anvin" <[email protected]>, and akpm, and even Linus. I'd like to see your patch. It would be instructive.
-- Coywolf
Quoted 11 lines · Coywolf Qi Hunt
Quoted 7 lines
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 incompressed/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 theseNeither 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