Re: Re: Swap Compression

Re: Re: Swap Compression

[rmoser]

Yeah, I had to mail it 3 times.  Lst time I figured it out.

As for the performance hit, the original idea of that very tiny format was
to pack 6502 programs into 4k of code.  The expansion phase is very
tight and very efficient, and on a ... anything... it will provide no problem.
The swap-on-ram as long as it's not like 200 MB uncompressed SOR and
1 MB RAM will I think work great in the decompression phase.

Compression will take a little overhead.  I think if you use a boyer-moore
fast string search algo for binary strings (yes you can do this), you can
quickly compress the data.  It may be like.. just a guess... 10-30 times
more overhead than the decompression phase.  So use it on at least a
10-30 mhz processor.  If I ever write the code, it won't be kernel; just the
compression/decompression program (userspace).  Take the code and
stuff it into the kernel if I do.  I'll at the point of the algo coming in to
existence make another estimate.

The real power in this is Swap on RAM, but setting that as having precidence
over swap on disk (normal swaps) would decrease disk swap usage by
supplying more RAM in RAM.  And of course swapping RAM to RAM is
a lot faster.  I'm looking at this for PDA's but yes I will be running this on
my desktop the day we see it.

Well, I could work on the compression code, mebbe I can put the tarball up
here.  If I do I'd expect someone to add the code to swap to work with it--in
kernel 2.4 at the very least (port it to dev kernel later!).  As a separate module.
We don't want code that could be mean in the real swap driver. :)

--Bluefox Icy

---- ORIGINAL MESSAGE ----

List:     linux-kernel
Subject:  Re: Swap Compression
From:     =?iso-8859-1?Q?J=F6rn?= Engel <joern () wohnheim ! fh-wedel ! de>
Date:     2003-04-25 21:14:05
[Download message RAW]

On Fri, 25 April 2003 16:48:15 -0400, rmoser wrote:
> 
> Sorry if this is HTML mailed.  I don't know how to control those settings

It is not, but if you could limit lines to <80 characters, that would
be nice.

> COMPRESSED SWAP
> 
> This is mainly for things like linux on iPaq (handhelds.org) and
> people who like to play (me :), but how about compressed swap and
> RAM as swap?  To be plausable, we need a very fast compression
> algorithm.  I'd say use the following back pointer algorithm (this
> is headerless and I coded a decompressor in 6502 assembly in about
> 315 bytes) and 100k block sizes (compress streams of data until they
> are 100k in size, then stop.  Include the cap at the end in the
> 100k).
> 
> [...]
> 
> CONCLUSION
> 
> I think compressed swap and swap-on-ram with compression would be a
> great idea, especially for embedded systems.  High-performance
> systems that can handle the compression/decompression without
> blinking would especially benefit, as the swap-on-ram feature would
> give an almost seamless RAM increase.  Low-performance systems would
> take a performance hit, but embedded devices would still benefit
> from the swap-on-ram with compression RAM boost, considering they
> can probably handle the algorithm.  I am looking forward to seeing
> this implimented in 2.4 and 2.5/2.6 if it is adopted.

Nice idea. This might even benefit normal pc style boxes, if the
performance loss through compression is overcompensated by io gains
(less data transferred).

The tiny problem I see is that most people here have tons of whacky
ideas themselves but lack the time to actually implement them. If you
really want to get it done, do it yourself. It doesn't have to be
perfect, if it works in principle and appears to be promising, you
will likely receive enough help to finish it. But you have to get
there first.

At least, that is how it usually works. Feel free to prove me wrong.

Jörn

-- 
When in doubt, use brute force.
-- Ken Thompson
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/

Re: Re: Swap Compression

[Jörn Engel]

On Fri, 25 April 2003 18:48:41 -0400, rmoser wrote:
> 
> Yeah, I had to mail it 3 times.  Lst time I figured it out.

<more formal junk>
- Your mailer doesn't generate In-Reply-To: or References: Headers.
This breaks threading.
- It is usually more readable if you reply below the quoted text you
refer to.
- Most people prefer, if you reply to all. Not everyone here is
actually subscribed to the list.
- Feel free to ignore any of this, as long as the mail contains
interesting information. :)
</more formal junk>

> As for the performance hit, the original idea of that very tiny format was
> to pack 6502 programs into 4k of code.  The expansion phase is very
> tight and very efficient, and on a ... anything... it will provide no problem.
> The swap-on-ram as long as it's not like 200 MB uncompressed SOR and
> 1 MB RAM will I think work great in the decompression phase.
> 
> Compression will take a little overhead.  I think if you use a boyer-moore
> fast string search algo for binary strings (yes you can do this), you can
> quickly compress the data.  It may be like.. just a guess... 10-30 times
> more overhead than the decompression phase.  So use it on at least a
> 10-30 mhz processor.  If I ever write the code, it won't be kernel; just the
> compression/decompression program (userspace).  Take the code and
> stuff it into the kernel if I do.  I'll at the point of the algo coming in to
> existence make another estimate.

A userspace program would be just fine. Send it to me and I'll convert
it to the kernel, putting it somewhere under lib/.
Do you have any problems with a GPL license to your code (necessary
for kernel port)?

> The real power in this is Swap on RAM, but setting that as having precidence
> over swap on disk (normal swaps) would decrease disk swap usage by
> supplying more RAM in RAM.  And of course swapping RAM to RAM is
> a lot faster.  I'm looking at this for PDA's but yes I will be running this on
> my desktop the day we see it.

Swapping RAM to RAM sounds interesting, but also quite complicated. As
a first step, I would try to compress the swap data before going to
disk, that should be relatively simple to do.

("I would" means, I will if I find the time for it.)

> Well, I could work on the compression code, mebbe I can put the tarball up
> here.  If I do I'd expect someone to add the code to swap to work with it--in
> kernel 2.4 at the very least (port it to dev kernel later!).  As a separate module.
> We don't want code that could be mean in the real swap driver. :)

Right. But for 2.4, there is no swap driver, that you can simply
enable or disable. I hacked up a patch, but so far, disabling swap
eats ~100k of memory every second, so that clearly needs more work.

Jörn

-- 
Do not stop an army on its way home.
-- Sun Tzu

Some code for Swap Compression

[rmoser]

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

Alright, I'm done with everything except fdecomp_push() and
fcomp_push().  For the decompression function fdecomp_push(),
it fully supports the fcomp-standard streams (the ones I outlined
originally), so the fcomp-extended stuff has to be supported
(simple enough modification.  I'm lazy).  A very large portion (most
of it) of fcomp_push() needs to be coded; the entire compression
phase is uncoded.  The logic is in that function, in comments.
Someone has to read it, look at the format, and write it.  After
those two things, this can finally be shoved into a userspace
program and rewritten for the kernel, and also can be preoptimized
(i.e. don't resize the stream so many times in decompression when
it's just copying data).

tar.bz2 attatched.  Please please PLEASE make a userspace
program for this as well so that we can get a general idea about
compression ratio.  No better way than using it on files.

--Bluefox Icy

[-- Attachment #2: fcomp.tar.bz2 --]
[-- Type: application/octet-stream, Size: 9424 bytes --]

begin 755 fcomp.tar.bz2
M0EIH.3%!62936=QEER@`':G_A/ZX(B!________>^O____\`!``(8"&/)I(U
M]OF+KHL>]ZO<WM5$]5I*#HT1Q+L[N[J]SWMVZZ>O>JTK/=V[3D;M2"ZO:.SC
MW=RUUI&V7KUQY9V;<SE-G;&[%VS6H/(U+*V.A+(7PDB!"9-,FC00F(T-",D>
MIZ,@3]03$-/4,U-,FC-0T-!D"`(FA!I/29,J>I[4AZFAIA!H```,(``#'#$:
M::#0!H````:#(--`T`&C0!B&@$FDDB--!-!3TTC---3]1J#TC)F2>HTT--`&
M@````(DIHF4R>DD>U1IYJIZ;*>F4T]$GJ-D,1/4'J:'J?JGDFRAY1Y1ZCU/2
M9!$D(1H!1@F@C:FB>30IZGZ*>H\GJ9)H::#0`T:``'K#\[/M]/U]'2N]2H*G
M:M`+KEW>O<@ZU%'6$I-UM(VW`8NF*Z8`2`P@L2"@R"Q=I2(6(@,((DLG3"*F
M]UZZWJ\Y[?6'KG_O16CMV;\ONA%V^Z["^\@8U/JE`:#GV:XQ]VIXKI^U5$?6
MQ@,@@##N.,=[W8K5$U-.]LFSR*ZXLEA3*BK=#/-\H3]Z,MR%*#&%SHHG$@G]
ML!,CK@J!Y+Y4'F;?)0;(!(T,8./](P[8D<VI=A?#RE3X75#QWQ@^_UY^(KKQ
MKX?5`(6[!\_7S;R[#C7I@/OW'X+Q]Q6)CIRW-L:/"=Q]'(0V1+:S]'5-K2;U
M\7%*BG!LBDH*"(DC&RJ$&]'0.CHF5$H&YAD('VS1:*B.8[H4200$HBLJJN`.
MODR)7:OROB=`QP@].1A^1G`M9&7(&@D:S\3#%QR!42NL@0&($;H%P9S<O8/F
M:D9DX9M4Q%&K3PJZMM\NQ2L+8^3R=WQ=/-XO>A`Z<KAF(*)LW1-J"^83U5P,
M"9T5M<GI/F??&]>+LG0XNUIR<(2'[,-6(:L`"9#3BJ2DV+.3=3:`S$W3C2G_
MNB\-/$*@<G,LX6;^`<P"QVP,>VA[>KT2?$+[DB"H8F.N@`;PBB+BA$!$VTFU
M]+Y!Z@W-]\+FYN*EEHL7#(TXDW2\G:WX,`]UD"L,:(JPBHL5"1P+1$$#FDC.
M*C)$(0B!=H"L$0D(&P&A=Z>OQ3@-]I^(:!/9$)#F0TA551Z!^'OH;/<[NTN@
M&I`]-FAIB&0W+V4?AVJ>+!5XATJK)#3&("P)"H;T@C,9(H!P#,;\3FSZ$O$9
MN$.%/I8@0461`H21^WV7(B1(#?E#*R43[PTFTUGXWOSI#Q\I9*SP]'*^#^\7
MH]D,.D85EWI5WYSQGQA<985N$.<]T-H]K?E/*D9((@H=OL,,D*VQ!G#:DF&B
MEI0T2TR&4&T!9EL@F%HF,F+A9%N4'*5#&9;"LQ@8RL3Y\[TZ^WS'EG'U`Q8\
M;3>#Z'WWE>(;)N(221'YB*>C$]-SK>LB=I@ZCG6A2ZVUL96!10*X/-J*<.X3
M<D:#JC595"9FV>+_H\O'H#I-+)T0PWD%TS.NU'MZ._'23JHQ7-G`M1EOI<\Q
MWA`&L&@5M!9,>%@K&3E\IVVJ8M]9U85E47L8"29(02B@EL*"AN.`1$3Y_OA;
M\Q`'AK3IE,CQ_;<.K3['3-L/Z\F\[!][&-;R+NW`GM^&TE#0?-/6L.">(Y_%
M3%Z=NIW(LAH\N7J;M$ALXE$(!:'&'-LT=!RKBCE#%F017PTJ'RD2A5[;+Q>T
M:T8(Q)V'HIC`@0/A)ZE]%A+B$8D9#>A1GL[.O:;NG:>#SFD1@..4[R@@652:
M657?H+@0POI1H+(@[Y7ME+]VI[W9+`8.`4P*\E@^L+7KFWIA0@$@;`R!KHVW
M[<.GD^#"4-;[A.?`[G4+K=N@E5LLNK?9=THL[:FJT5-/SJB4\_-[;,-`I;?J
M'7!5ZJ0@T>H#U2-5XF9.]%X-L!E?C+FL(DIYYH%][A^(_9,,9@JQ[1)7"U2^
M7BML-BGPS`Q`882QCQ=L5!07(S86:;,3"/)F95"`!,O/OX:U)P!A"7D587,(
M3JF"SRBJU#;&N<?":6"+=F%&ENMN8Q:6LOX5TNHQ!AQ8J&!=M&MKD(PW4T#8
M!$ZM`0NN9%WG*QN*EQ&S&2'>>8XY*@^RI484C)L2'IX0)%)&4"J(*P:`U4&F
M>KV-W&4E0HDF'CD`N7.$/\:/1^BM3T2Z./0H*:?7ML5ZCMK%:JGJSJTAK^@M
M>"Y^Y7OGZL.`"Q.^S'_7`TZMJ'0_G(>AZ#--@SNT8E;K3H'W$MN6<PSR]ZGN
MAP=#'&X/-,N1D'"SE8Y^5VCXX(;#7A:KO86//R]VJVYNQ:/;[VT+^6Z^BVS6
M6[2-`'*+N&Q"#4$A)$))(!\=])Y?!LSL':&[)KCUQW_;X$YYZ-6MXJP@*7=4
MH9>B2)RQ-DX=["86C&T6IU.*=X*K["U=M:C$W9B'OS\>\CL*$5!8%!XBAW#<
MARE2OITE9X(%&):#!W(3T$30.V%_P$5ER\9`U.JP;(T6@18,B+B4D2F=N[I%
M'<L;C5I7P6@;EJR"!9U0:4,N?$XA#%*.5#(\NBNG3%5\\;K6ON>HROS>WMP,
MCM'EC;KU8:'8H>*"YLT`;B@1!L/*JI8K6-2[R%>QV\GLM*]W&'4**?M*R"S;
M$0[)A2!W"QHS!6,/)RX[AI%)TU?:%5>2"SFQ/KYOPBVO8/`*'!&9IV-[=FSQ
M%^O>MX2?6,/L.`**$XG17$U8H$S2XU<"6^M$J7BY:X,C-P44,TU/-!#!.`IA
MX16XI@V(D;M,010%4(0>A2)@X(-!NS3"7FNR76)F%-)OI!H8.L;0T$=+0X"%
M^>*,`O4IERHU]R,`SHX87E=87>[]GHC+WMV*F6I-N8ESFNYE@`_@1@"\&\QB
MG.ZN.5:>E`PT!71->*^A%W\&Y8JQEB0C=Q\P,3CDB(/&4#O*R.BC$RNF&*(0
MKR+/$'JFTS)>R*9-!6"B(%(0REN\3YJZ<2IP*^"E0+W>VTFM:[S!R644)S!L
MVS:#.X84BM-%A;N:30R5!7"')2\&YPEN@QL:Q-<L:R"0DK/&V@-W/!%ASKZA
MO#&#=+#=C;IW@3VI7%^7=.0X%#-.";-7`QT-FO"ZE,BIT#';+AJT8:[WET97
MS;4[0!![0J2KN7$N-2M>UN2CK8SM5A4VL`='!T!6:0]PEEZ!>>ST;.-.#^<G
ME9]Y56:#\;@/<-9:0/.?#JR0.2^6!,^0$Q_8W5DDN=_WD%!D=.1VVWIES!O]
M].H,N9&%9]HWU,>$SC@@6!M'JB2'IL/@Y-[W&[=N6(PB'M855#124)^GTWY;
MY*MLR#E&\70Q;.XZDQ!/ST[+92BB@[MG[/2>X?MH[[3W8^P]Q<AD5^4O"QI#
M)2_DJ8%8Y[0R[;:F+\'^>SYQ8.?)SWEW9/2%_I&5+^!?9:#"\F%1/!S2.LKA
MX,6CG*1&B>BA(L8(%$96/?;3&GS/K,S%"?:AZ#@O"A*`A99TE"Q`FN!A`U$#
M1E\'R,W\;8\AUS(,R!@%SKQ\HXR81W.V+/'(E?0K"P.9/+@&X,ZN+1R_#4M,
ML_DJ"SX)?`O!K7BHXD-]]KUHMVP#BUMH#``9"`OM>V#7?Q`D5E=0]!"M=5DY
MU9I)OD5>S>W%KM0?E=3=ENP'J'P<SS:YB$BLJDD*M(%0&V%2#;!MA&T#KZ>F
M^*$ZI^'S02.B_VJ6>&?%I[`X*Y43DAT:JY[X=KX=](N]3YFNWXYY9->QJBW3
MC2[B4K;!-.Z(4<`P@9J*F8&@ES&P0,>-443(&V:UI75MP3:VI@JREGL2B%CU
MR#;*IE/FK+["LP);8V.#NF,9H6O]^"X?>QU'6#PDD]\B8`$RZH[#E6/5M7V3
MLKSQ((J]C\2#DD(0D@JQ9%4%@LG[Q/,#(&)!&0GG82L`OGEAB!C)%BD,85`#
M%?D;P+0EZ=NPA3WH_II%J(.;2/9$:$NQ_J*O2/,WI[Y,)2ENWL6?8\X+C4$X
M(N^A#,#CJ4?_(8QK5@`C.N2(>=A[@GH$AM.?"KC*FDP(Z#CMG"Q3#)CGH0I?
M;HL8`(Z`DB*PE!<P"$Y86U#E)E`DZ+I3HSQG6P:#;%@MS&HI;&S`Z0T,LPSS
M`TPUD%RDM@#!_5P>HI>VLT@5]7;=W\8O8'.\JNR/J[3NM[I;'9$]P<,J^3U,
M.'DO<Z/AS`WE#[")[EUB3T'7N-C$97NGH.-!U_F\)R2-=TPT^2[RMY2R!50D
M0,H6M'JU0_@)EP#$Q/C*\=M+5=L,=IIG48GF(06-Q"V#]D^$5%GEN"0V:<H?
MD$R&L<BJ=M@S.G5>8UW[#7`K.6P[0P,QU%0;A@WJ*-V1E962*CS:@M!!_/L%
M'W%+4+BA0F_YD_<-Y-F#(MQ!,"&#"UJ%Q:5^8.6[\-GA>UK=IF@9<;GO+K\*
M*O?\8[ISOD.O_P_N,/#SN&E.M'OL`\4`<A\7GWK?=VEUJP4LP@;?T%,`_1O&
MR$&1GWCJ/$="ZYP9&:(ND?;YPO$P8'+)@TC^DA"!W7]8ZVI,!Y0S<.Q,<"]?
M6,+0IJ63:P9>I;L#B-AP")U50"`:[$%H<3@$*]O#$#=5N3(8@6>IJ/YGTTWX
M#'X8GK!]P&G\K?_1N09D);.=+>9F*2U[#8NC<,+@D%27`M`Y\^@6\/.7WL'G
MAOL.G$H8_`ZH-/NCFMEN0O>AR$*)RP.!W$)`3IA;USO8B]PZ)&JB%0:E-4.6
M$"FHMACVD[1M8?LN<GYSY8(#*6&C!9["#GT,'5VAH\OGFQZ,/;$TX_H>42.)
M83KC2A%P>@QH][N4F*LX+H#>E@>GK5E>1Z/`-H.Q=X*0?L1Z`(HIP!8-(']6
MX%"R)\="P6`B`Q5!9+;"6IM9H#\%A&8*`_I]_UOG$/FWU45T9[\!8UT/AT88
MJ.!Q_0XX@1S&'RK`X;/[_PR>HEU!@XC!BT%DM^IZLL)H.`0?QP.&AOGS1S!@
M6@%#P5M$VQ+`\XHY2P/3(SN;"C3L7JU!,C:6!7K+&<`6<`+`L3`0*TC&*V*L
M$8J"*YB&8=9BL"^4E#M#ZQR]V"^6BA0A)"$LT.1SQ*#DBE+IEMG.FZ3.X6;Z
MFNJ:Y0R#LA(</95<CF=PC_'VT@$4BDDBZIT(A"!_N08PY1T(`;<4TP<D-'J!
M[`LECXB@+X]P\IQEVV\>&70KHHIAP'CNFVASMY5=VWM9K=`W`,RS>%T;KMA0
MVV/BF!?&#2D7P@16(N(_W<IY_46!+C8"H>BVH>^=F"((%;@;NT^`DX/)Z=`0
M10-QCP@7.DEVL#:L]+-C8B<!A(,@'%"9&#&FPND=::"-HVC8(50U:(&US3$.
M$+!(HBH,5!@BC$555550(B*L1(*#%56,5C$!EC&9%>&6:C#Q@@*L6",-M([,
MAQ(BQR,N^;N?WMVPG$I8N[A<8S?2@.N-P$6;G3@;#9B`42&))K)9H]3"79=)
MO2%G025>J`C8H;*_T/!`]\5]#!RLM?*Y7<8ZF+G@Q%"%)#VH+V0:2/W(N"A^
M@>;M#J;Z!&=?IX2,81O`J,A)*`\&2]^![(H-K="J1>.RT'Y\E1R<2'AZY3U>
M"2C/V9A69#BU8HI)Z_9@+`D2ZL$(A)&23`2RW5.+F8.G%R<AON2V0F(NZ'MB
M%TQNM:`;M:';$)"_/#%]R%,W8XP"VINHT-8L*.JT3"Z,/),H2,(;[L+974.5
M!&$(V0!6FP-T<2*D9668@[(%,*2;2?5`UK[C1#`%T.3*8#F[.?/",NF7FLVV
MY^G[7-SQVY^.E456R8*T-['.#G+,N6Y]#/GERR"MD<Y&9MWXUEMERPZAD'#\
M"!1Q@%H@+T/'L7Y+IV^MH@?FKX-6O$(NO[V;R^T8,N29@9[8+4`VY1Y%-],@
MA.,FJ;*%*('%:2+TJ@9"KB:#XF4N7]EB"HYD&"<\Q-!H]V_=;O?0`7<>=OB1
MZ_!M6&E?\TK'=RS@&^2&81!-`U(#>Q6WRRLHIV;\4XEC'D-]NT;DFQW.&SR,
MU)KT(;W'3R>OV>OZ_=0Z.88A-*Y(VZ,K!'PLW[:R8F^%KU;%_4PND@9QA][%
MEGKT(X#R=&D;L""#0G#HVV>,BD#L&O$88BPLS=FY`""&$3Q<-<,ENM1%-L89
MG-Y""+`">C58`+2)E^`@_'T4>X(H<8?2C]%SG[N\ZVI9**H#?`A2D'[GJZS0
M@LFF!7*[(8!L,R8TA(E7L4D+-EZ0!=$R@/ZX.V$B3CJFD:$I@$8/>DGC[GEY
M,?OP`'%RJFD:5/=V7\0>6`G,Y(G1\=E+V=B=$@'UB'[@8:[^T#XO-8>5EOM)
MD(+TL)R0$,1@J#JI;80MQA9V@!(I(C*N<[D]50NF#FPY%C,M$*H(O>PMH`:1
M,X-"%_L]![-XS`SR62Q8Y;(D2(K&\]FS@&QMP&:V-_?8",D3J&4*C\&'<RNJ
M1#3)KZ]"]V@9INRNY*Y36J:W-P=K2C`UNT7ABY$\,$&X[5DYDD+FD5[;!!D`
M">>P9F;6`R(OUT%)8B9S!U?=,G["&#$'<H"D408HK#?!!>Z]ZX!@8,Z\Z[+)
M*!U4,B$1,8I)060U#DW%AQ^=\AVOFQW^9-7KV.3B_`G;`J5!.ZU,;4%$5,(2
M4/,^YD9+:CZ0R>)KL9@C05&O2?:2&Y6I8V'..^"$A-[=[N3AVGTRG>E);??F
MZ;ZJ$XUBVJN]4\M$$C7$@U*LYO0D?IKE#(+])W%-9(((]^TI,45QB-@D!(K"
M`>8"`LA(I=A(]![O5141BB=1&^E7G)U!OV&`5`*"%62(,0$42()$%CU4LZ^K
MHA%(LD\T8Q4&)H-F>D)3X#M9-")8@-0"1"_+4Y>\F<.:]K=2LW+1CLR;PL1`
MCPM(!@NQ(PB<1!8PC^W6A<IK\4AWXY$O)+)3P58<OJ]6$T.^@R^';<RW1N^;
M,'Q.NQ?8YX0VW+,0-3<8YYC`KKE)+4%53(R+F?%]QYE"$"MVW'SO3NE@-;:D
MZFCIWZ"#*!?<5G3A'2H@6Y&XD@(**+-8.!!%_.;FEN*N3(D,R2'`9DU&60=N
MT*IWZ4>]@6$RE"J64DI.V'Z,F"/,2%X,)[Z`+IE*<>6)0.<U+(<-Y_%<^7B=
M[W`:<5.I6'#O0@N+.G'#6,;DX40282-@8#EC<<_1"Z$0BD@\01>((-^!08L$
MH@!8BU=$_4Z:?UI(^:@N(NXE-+S31ONU+F,\P45GVE$R]OE)4QB3;3^1L!@(
M61<R)VL05Y;`H1KI'/>:);$8;<46L_00&N!4-/*;D,NQH:?.S("S&FERLK39
M+G'"S:.T%6(K(W:9FKE->GM*:B=\&[M34;G8%Z&.\[BP!8(.<2:C9@1C38/5
M=,FHRYJ19+D"6TT8,H2P#LU*,.`P?)$-DSFAT6DGH&(=%4]@B`L2PN$0"#'0
M560ASNRX-PUB2D,S[83/8G,UR0WO`8#NE,[V"?BF1`R'1W`-R2I.*5]ZH!&I
M@HBBL("L>"F"B)0=,4^-XS%5+JUL#=CZQ#)(WL!#!P,XS@IX-6HH+1M&,J-0
M'![C1@6)?D9',JA$.HI4JR?4620B'#V)N-,U1Z,#O(1,]/J3+Z$?SQ"$8Q4D
M`U`X>(CP!YI3Q#]N#+%"J%$D`ZTXQDD8./3N+L._H_FHL`&1M5"P@EHV3"[)
MUWSYF<(MK8Q5@DF.V(,(<R>\@5*(%5*#X^6<@]--W-SSN.-$J/6=FS"/!@>6
M'#Z7RCONXF[]H0Y:3IP27G6.W&V0?(:4);H<;Q+C'NY9%$"<?POR+X+9P.('
M6RA>G`U^:+V!Y4IJ`>%J/3%+!*$#20`4`1A`YCSL\)'VH(GE:G+&SP$*+8L*
M^K@W$L#UH=IA(_)"IW8TEHPH*9(.%2!YYLB]+OM.(W_($#8,4@'9\P&.24J4
M7J))T\V",3!$8,$.["V,@)%&):!5545(+WF5(R)+F#4)&1H`8HX'Q5?S\ENM
MHQ&*DS)[8F'*:KQR<*S/-HF5PU9FVF+-JMG.'H/.M/7[Z-Q.8"/(*A#H^#Z1
M;(;W=2]/77%G>,DA88,'UGG:XP28R5"&B<@^S+'3AQ`KV1D<[,:&/4($A.#2
M#3L.$.(,=1V<MU]C[AV([DU[-\3(Q!#"FG5\:9N1DYAY";Y4O+QFR-U//V#A
MW,N0<V(09<84P/)3Q?B&NCC6&3=K6!BU'>UEF8Q>Q676\&VQOJ.96UIQL8[8
M#D.;4($<ZO$+!Y+)QAE&10%20R,5FSH51<4/IMY!@<%C6E$./&U+_4,M"-\E
MD:051!4K<R5868K0**1:0E-*S#)W=9YY#8E%CZM#>/24QIF4Q;(WPDX`6I.D
M:[PJ2;HFW+#PB&2E@J(=V@]KLR9VG9%L6(<QHN65N5#XGD]>-V=<R2&YGR3/
M2^_+8;R:$).4MZNUAF0,3F#N4=9,V,NLETN\KVNXQ#(6$!D41@F`TI!^1:0W
MA0#ZJOG3<G(R3H)[!X\`2,)1.EL,LG8&!1&"#V(0VB=>\J)OY`YYD])AKR>1
M>9<^=_;'.99=R):H>-R*M*@1CLP4SH]/&WA;W'!GYZT-0F`4877`NT!`Z`4`
MN4,FS6`T@@K<S)"%"!2!ZJFMY`JEKY-,!+:95*`[($AJ,!:FN):QF33&3KP+
M#+[LY4J^5TU0W@&2`:6A`!>]18J@>JA*3HKT@+"+-C"+G4XZS-IOM.%7DR7D
M&S>3B'-JY!8(LPY&V,:Z7!QBH;)NLHC63)$V\*'9/#=N0%FS9E:DJ7H*=$@4
M&44D%>1:#$5R,MX&#9$Q\%X`;!E8MB[9WVET,!I=T+.J/?-R2PJ98ZL)9'3D
MQ1T:CD#(W61JJ:0H)NC<0.J"G7`",%9%`^YB!FYT-<(4!E$+NVJBQ-4UW(S=
M+V8=)@H^&^5GCNJ^Q%@P0))$PFPJ4AR*#G(19%!<%]==8.,5CA1EM=45UT>1
MF(;WG<^+Q*9N?-*0_$Y$5.O`3'258L0==C1P\HGYNPA=GLU/X&]F.^&6)J3I
M-A:G8(5KS#21WT5L/G<EN#+?PO*(?_!BY`.G$M86UK2U`<AZYW,W=R%@;G7@
MNF6T1L2>!4USEF$\&'8:-1$@B@L8"&<T^$I#BFY.M-PPF,4J`2`0,P@&OUT%
M+Y\?J$,L"V%]=D$Y>2)XMZ5S"'*6[V#790T94\+/=I;2^"TLV"K54?)+6=LM
M&&_I^6GDQOXVE"&G#0>"`[^P5<P?4_*]R6B%B%$HE%%2JH^IAHT_'88FAV)&
68!L&L"9#0Z*&$R3^+N2*<*$AN,LN4`
`
end

Re: Re: Swap Compression

[rmoser]

So what's the best way to do this?  I was originally thinking like this:

Grab some swap data
Stuff it into fcomp_push()
When you have 100k of data, seal it up
Write that 100k block

But does swap compress in 64k blocks?  80x86 has 64k segments.
The calculation for compression performance loss, 256/size_of_input,
gives a loss of 0.003906 (0.3906%) for a dataset 65536 bytes long.
So would it be better to just compress segments, whatever size they
may be, and index those?  This would, of course, be much more efficient
in terms of finding the data to uncompress.  (And system dependant)

The algo is flexible; it doesn't care about the size of the input.  If you
pass full segments at once, you could gain a little more speed.  Best
part, if you rewrite my decompression code to do the forward calculations
for straight data copy (I'll likely do this before the night is up myself),
you will evade a lot of realloc()'s in the data copy between pointers.  This
could also optimize out the decriments of the distance-to-next-pointer
counter, and total this all together gives a lot of speed increase over my
original code.  Since this is a logic change, the compiler can't do this
optimization for you.

Another thing, I did state the additional overhead (which now is going to be
64K + code + 256 byte analysis section + 64k uncompressed data)
before, but you can pull in less than the full block, decompress it, put it
where it goes, and pull in more.  So on REALLY small systems, you
can still do pagefile buffering and not blow out RAM with the extra 128k
you may need.  (heck, all the work could be done in one 64k segment if
you're that determined.  Then you could compress the swap on little 6 MB
boxen).

--Bluefox Icy

Re: Re: Swap Compression

[Jörn Engel]

On Sat, 26 April 2003 22:24:04 -0400, rmoser wrote:
> 
> So what's the best way to do this?  I was originally thinking like this:
> 
> Grab some swap data
> Stuff it into fcomp_push()
> When you have 100k of data, seal it up
> Write that 100k block

I would like something like this:

/*	fox_compress
 *	@input: Pointer to uncompressed data
 *	@output: Pointer to buffer
 *	@inlen: Size of uncompressed data
 *	@outlen: Size of the buffer
 *
 *	Return:
 *	0 on successful compression
 *	-Esomething on error
 *
 *	Side effects:
 *	Output buffer is filled with random data after an error
 *	condition or the compressed input data on success.
 *	outlen remains unchanged on error and holds the compressed
 *	data size on success
 *
 *	If the output buffer is too small, this is an error.
 */
int fox_compress(unsigned char *input, unsigned char *output,
		uint32_t inlen, uint32_t *outlen);

/*	fox_decompress
 *	see above, basically
 */
int fox_decompress(unsigned char *input, unsigned char *output,
		uint32_t inlen, uint32_t *outlen);

Then the mm code can pick any useful size for compression.

Jörn

-- 
My second remark is that our intellectual powers are rather geared to
master static relations and that our powers to visualize processes
evolving in time are relatively poorly developed.
-- Edsger W. Dijkstra

Re: Re: Swap Compression

[rmoser]

*********** REPLY SEPARATOR  ***********

On 4/27/2003 at 11:04 AM Jörn Engel wrote:

>On Sat, 26 April 2003 22:24:04 -0400, rmoser wrote:
>> 
>> So what's the best way to do this?  I was originally thinking like this:
>> 
>> Grab some swap data
>> Stuff it into fcomp_push()
>> When you have 100k of data, seal it up
>> Write that 100k block
>
>I would like something like this:
>
>/*	fox_compress
> *	@input: Pointer to uncompressed data
> *	@output: Pointer to buffer
> *	@inlen: Size of uncompressed data
> *	@outlen: Size of the buffer
> *
> *	Return:
> *	0 on successful compression
> *	-Esomething on error
> *
> *	Side effects:
> *	Output buffer is filled with random data after an error
> *	condition or the compressed input data on success.
> *	outlen remains unchanged on error and holds the compressed
> *	data size on success
> *
> *	If the output buffer is too small, this is an error.
> */
>int fox_compress(unsigned char *input, unsigned char *output,
>		uint32_t inlen, uint32_t *outlen);
>
>/*	fox_decompress
> *	see above, basically
> */
>int fox_decompress(unsigned char *input, unsigned char *output,
>		uint32_t inlen, uint32_t *outlen);
>

Ey? uint32_t*?  I assume that's a mistake....  Anyhow, this wasn't what
I was asking.  What I was asking was about how to determine how much
data to send to compress it.  Read the message again, the whole thing
this time.

>Then the mm code can pick any useful size for compression.
>
>Jörn

Eh?  I rather the code alloc space itself and do all its own handling.  That
way you don't have to second-guess the buffer size for decompressed
data if you don't do all-at-once decompression (i.e. decompressing x86
segments, all-at-once would be to decompress the whole compressed
block of N size to 64k, where partial would be to pull in N/n at a time and
decompress in n sets of N/n, which would give varying sized output).

Another thing is that the code isn't made to strictly stick to compressing
or decompressing a whole input all at once; you may break down the
input into smaller pieces.  Therefore it does need to think about how much
it's gonna actually tell you to pull off when you inquire about the size to
remove from the stream (for compression at least), because you might
break it if you pull too much data off midway through compression.  The
advantage of this method is in when you're A) Compressing files, and
B) trying to do this kind of thing on EXTREMELY low RAM systems,
where you can't afford to pass whole buffers back and forth.  (Think 4 meg)

You do actually understand the code, right?  I have this weird habit of
making code and doing such obfuscating comments that people go
"WTF is this?" when they see it.  Then again, you're probably about
12 classes past me in C programming, so maybe it's just my logic that's
flawed. :)

--Bluefox Icy
(John Moser in case something winds up with my name on it)

>
>-- 
>My second remark is that our intellectual powers are rather geared to
>master static relations and that our powers to visualize processes
>evolving in time are relatively poorly developed.
>-- Edsger W. Dijkstra
>-
>To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
>the body of a message to majordomo@vger.kernel.org
>More majordomo info at  http://vger.kernel.org/majordomo-info.html
>Please read the FAQ at  http://www.tux.org/lkml/

Re: Re: Swap Compression

[Jörn Engel]

On Sun, 27 April 2003 13:24:37 -0400, rmoser wrote:
> >int fox_compress(unsigned char *input, unsigned char *output,
> >		uint32_t inlen, uint32_t *outlen);
> >
> >int fox_decompress(unsigned char *input, unsigned char *output,
> >		uint32_t inlen, uint32_t *outlen);
> 
> Ey? uint32_t*?  I assume that's a mistake....

Nope. outlen is changed, you need a pointer here.

> Anyhow, this wasn't what
> I was asking.  What I was asking was about how to determine how much
> data to send to compress it.  Read the message again, the whole thing
> this time.

I did. But modularity is the key here. The whole idea may be great or
plain bullshit, depending on the benchmarks. Which one it is depends
on the compression algorithm used, among other things. Maybe your
compression algo is better for some machines, zlib for others, etc.

Why should someone decide on an algorithm before measuring?

> >Then the mm code can pick any useful size for compression.
> 
> Eh?  I rather the code alloc space itself and do all its own handling.  That
> way you don't have to second-guess the buffer size for decompressed
> data if you don't do all-at-once decompression (i.e. decompressing x86
> segments, all-at-once would be to decompress the whole compressed
> block of N size to 64k, where partial would be to pull in N/n at a time and
> decompress in n sets of N/n, which would give varying sized output).

Segments are old, stupid and x86 only. What you want is a number of
pages, maybe just one at a time. Always compress chunks of the same
size and you don't have to guess the decompressed size.

> Another thing is that the code isn't made to strictly stick to compressing
> or decompressing a whole input all at once; you may break down the
> input into smaller pieces.  Therefore it does need to think about how much
> it's gonna actually tell you to pull off when you inquire about the size to
> remove from the stream (for compression at least), because you might
> break it if you pull too much data off midway through compression.  The
> advantage of this method is in when you're A) Compressing files, and
> B) trying to do this kind of thing on EXTREMELY low RAM systems,
> where you can't afford to pass whole buffers back and forth.  (Think 4 meg)

a) Even with 4M, two pages of 4k each don't hurt that much. If they
do, the whole compression trick doesn't pay off at all.
b) Compression ratios usually suck with small buffers.

> You do actually understand the code, right?  I have this weird habit of
> making code and doing such obfuscating comments that people go
> "WTF is this?" when they see it.  Then again, you're probably about
> 12 classes past me in C programming, so maybe it's just my logic that's
> flawed. :)

I didn't look that far yet. What you could do, is read through
/usr/src/linux/Documentation/CodingStyle. It is just so much nicer
(and faster) to read and sticking to it usually produces better code.

Jörn

-- 
Beware of bugs in the above code; I have only proved it correct, but
not tried it.
-- Donald Knuth

Re: Re: Swap Compression

[William Lee Irwin III]

On Sun, Apr 27, 2003 at 07:51:47PM +0200, J?rn Engel wrote:
> Segments are old, stupid and x86 only. What you want is a number of
> pages, maybe just one at a time. Always compress chunks of the same
> size and you don't have to guess the decompressed size.

Well, not really, but x86's notion of segments differs substantially
from that held by other cpus.


-- wli

Re: Re: Swap Compression

[rmoser]

*********** REPLY SEPARATOR  ***********

On 4/27/2003 at 7:51 PM Jörn Engel wrote:

>On Sun, 27 April 2003 13:24:37 -0400, rmoser wrote:
>> >int fox_compress(unsigned char *input, unsigned char *output,
>> >		uint32_t inlen, uint32_t *outlen);
>> >
>> >int fox_decompress(unsigned char *input, unsigned char *output,
>> >		uint32_t inlen, uint32_t *outlen);
>> 
>> Ey? uint32_t*?  I assume that's a mistake....
>
>Nope. outlen is changed, you need a pointer here.
>

ahh okay, gotcha

>> Anyhow, this wasn't what
>> I was asking.  What I was asking was about how to determine how much
>> data to send to compress it.  Read the message again, the whole thing
>> this time.
>
>I did. But modularity is the key here. The whole idea may be great or
>plain bullshit, depending on the benchmarks. Which one it is depends
>on the compression algorithm used, among other things. Maybe your
>compression algo is better for some machines, zlib for others, etc.
>

Yeah I know.  I really need to get a working user-space version of this
thing so I can bench it against source tarballs and extractions from
/dev/random a bunch of times.


>Why should someone decide on an algorithm before measuring?
>

Erm.  You can use any one of the other algos you want, there's a lot
out there.  Go ahead and try zlib/gzip/bzip2/7zip/compress if you
want.  I just figured, the simplest algo would hopefully be the fastest.
But really we need some finished code to make this work :-)

The real reason I'm working on this is because I favor speed completely
over size in this application.  It's all modular; make the interface for the
kernel module flexible enough to push in gzip/bzip2 modules or whatever
else you want:

<M> Swap partition support
____<M> Compressed Swap
________<M> fcomp
____________<M> fcomp-extended support
________<M> zlib
________<M> gzip
________<M> bzip2
________<M> compress
____<M> Swap on RAM

As far as I know, zlib, gzip, and compress use Huffman trees.  I am pretty
sure about zlib, not sure about the others.  gzip I believe uses 16 bit
backpointers as well, which means you need a 64k processing window
for [de]compression, not to mention that it takes more work.  bzip2 we
all know is CPU-intensive, or at least it was last time I checked.

>> >Then the mm code can pick any useful size for compression.
>> 
>> Eh?  I rather the code alloc space itself and do all its own handling. 
>That
>> way you don't have to second-guess the buffer size for decompressed
>> data if you don't do all-at-once decompression (i.e. decompressing x86
>> segments, all-at-once would be to decompress the whole compressed
>> block of N size to 64k, where partial would be to pull in N/n at a time
>and
>> decompress in n sets of N/n, which would give varying sized output).
>
>Segments are old, stupid and x86 only. What you want is a number of
>pages, maybe just one at a time. Always compress chunks of the same
>size and you don't have to guess the decompressed size.
>

Yeah true.  But for guessing the decompressed size I meant like when
you don't want to load the WHOLE block into RAM at once.  Ahh, so you
swap in pages?  Well whatever unit you swap in, that's how you should
compress things.  Look I'm confusing myself here, just ignore anything
that sounds retarded--I'm just a kid after all :-p

>> Another thing is that the code isn't made to strictly stick to
>compressing
>> or decompressing a whole input all at once; you may break down the
>> input into smaller pieces.  Therefore it does need to think about how
>much
>> it's gonna actually tell you to pull off when you inquire about the size
>to
>> remove from the stream (for compression at least), because you might
>> break it if you pull too much data off midway through compression.  The
>> advantage of this method is in when you're A) Compressing files, and
>> B) trying to do this kind of thing on EXTREMELY low RAM systems,
>> where you can't afford to pass whole buffers back and forth.  (Think 4
>meg)
>
>a) Even with 4M, two pages of 4k each don't hurt that much. If they
>do, the whole compression trick doesn't pay off at all.
>b) Compression ratios usually suck with small buffers.
>
a)
True, two chunks of 4k don't hurt.  But how big are swap pages?  Assuming
the page can't be compressed at all, it's [page size / 256] * 3 + [page size]
for the maximum compressed data size.  (4144 bytes for 4k of absolutely
non-redundant data within 256 bytes).

b)
Yeah they do.  But to find the compression performance (ratio) loss, you
do [max pointer distance]/[block size], meaning like for this one
256/[page size].  If you do a 4k page size, you lose 6.25% of the compression
performance (so if we average 2:1, we'll average 1.875:1).  What IS the page
size the kernel uses?

>> You do actually understand the code, right?  I have this weird habit of
>> making code and doing such obfuscating comments that people go
>> "WTF is this?" when they see it.  Then again, you're probably about
>> 12 classes past me in C programming, so maybe it's just my logic that's
>> flawed. :)
>
>I didn't look that far yet. What you could do, is read through
>/usr/src/linux/Documentation/CodingStyle. It is just so much nicer
>(and faster) to read and sticking to it usually produces better code.
>

Eh, I should just crack open the kernel source and immitate it.  But I have
that file on my hard disk, so mebbe I should look.  Mebbe I should take a
whack at getting the compression algo to work too, instead of pushing it
on someone else.


>Jörn
>
>-- 
>Beware of bugs in the above code; I have only proved it correct, but
>not tried it.
>-- Donald Knuth

Re: Re: Swap Compression

[Jörn Engel]

On Sun, 27 April 2003 14:31:25 -0400, rmoser wrote:
> 
> Yeah I know.  I really need to get a working user-space version of this
> thing so I can bench it against source tarballs and extractions from
> /dev/random a bunch of times.

Your compression won't be too good on /dev/random. ;)
But /dev/kmem might be useful test data.

> >Why should someone decide on an algorithm before measuring?
> 
> Erm.  You can use any one of the other algos you want, there's a lot
> out there.  Go ahead and try zlib/gzip/bzip2/7zip/compress if you
> want.  I just figured, the simplest algo would hopefully be the fastest.

Hopefully, yes. Also, the one that doesn't trash the L[12] caches too
much will be "fast" in that it doesn't slow down the rest of the
system. This aspect really favors current uncompressing code, as it is
very easy on the CPU.

> But really we need some finished code to make this work :-)

Yes!

> The real reason I'm working on this is because I favor speed completely
> over size in this application.  It's all modular; make the interface for the
> kernel module flexible enough to push in gzip/bzip2 modules or whatever
> else you want:
> 
> <M> Swap partition support
> ____<M> Compressed Swap
> ________<M> fcomp
> ____________<M> fcomp-extended support
> ________<M> zlib
> ________<M> gzip
> ________<M> bzip2
> ________<M> compress
> ____<M> Swap on RAM

Exactly. It might also be possible to choose the algorithm at bootup
or during runtime.

> As far as I know, zlib, gzip, and compress use Huffman trees.  I am pretty
> sure about zlib, not sure about the others.  gzip I believe uses 16 bit
> backpointers as well, which means you need a 64k processing window
> for [de]compression, not to mention that it takes more work.  bzip2 we
> all know is CPU-intensive, or at least it was last time I checked.

Yes, zlib eats up several 100k of memory. You really notice this when
you add it to a bootloader that was (once) supposed to be small. :)

> Yeah true.  But for guessing the decompressed size I meant like when
> you don't want to load the WHOLE block into RAM at once.  Ahh, so you
> swap in pages?  Well whatever unit you swap in, that's how you should
> compress things.  Look I'm confusing myself here, just ignore anything
> that sounds retarded--I'm just a kid after all :-p

Will do. :)
It should be fine to load a page (maybe several pages) at once. There
is read-ahead code all over the kernel and this is nothing else. Plus
it simplifies things.

> >a) Even with 4M, two pages of 4k each don't hurt that much. If they
> >do, the whole compression trick doesn't pay off at all.
> >b) Compression ratios usually suck with small buffers.
> >
> a)
> True, two chunks of 4k don't hurt.  But how big are swap pages?  Assuming
> the page can't be compressed at all, it's [page size / 256] * 3 + [page size]
> for the maximum compressed data size.  (4144 bytes for 4k of absolutely
> non-redundant data within 256 bytes).

4k + sizeof(header). If the compression doesn't manage to shrink the
code, it should return an error. The calling code will then put an
uncompressed flag in the header and we're done.
The header may be as small as one byte.

> b)
> Yeah they do.  But to find the compression performance (ratio) loss, you
> do [max pointer distance]/[block size], meaning like for this one
> 256/[page size].  If you do a 4k page size, you lose 6.25% of the compression
> performance (so if we average 2:1, we'll average 1.875:1).  What IS the page
> size the kernel uses?

4k on most architectures, 8k on alpha.

> >I didn't look that far yet. What you could do, is read through
> >/usr/src/linux/Documentation/CodingStyle. It is just so much nicer
> >(and faster) to read and sticking to it usually produces better code.
> >
> 
> Eh, I should just crack open the kernel source and immitate it.  But I have
> that file on my hard disk, so mebbe I should look.  Mebbe I should take a
> whack at getting the compression algo to work too, instead of pushing it
> on someone else.

:)

Imitating the kernel source may or may not be a good idea, btw. It is
very diverse in style and quality. Some drivers are absolutely
horrible, but they are just drivers, so noone without that hardware
cares.

Another thing: Did you look at the links John Bradford gave yet? It
doesn't hurt to try something alone first, but once you have a good
idea about what the problem is and how you would solve it, look for
existing code.

Most times, someone else already had the same idea and the same
general solution. Good, less work. Sometimes you were stupid and the
existing solution is much better. Good to know. And on very rare
occasions, your solution is better, at least in some details.

Well, in this case, the sourceforge project appears to be silent since
half a year or so, whatever that means.

Jörn

-- 
Data dominates. If you've chosen the right data structures and organized
things well, the algorithms will almost always be self-evident. Data
structures, not algorithms, are central to programming.
-- Rob Pike

Re: Re: Swap Compression

[Livio Baldini Soares]

  Hello,

  Unfortunately, I've missed the  beginning of this discussion, but it
seems you're trying  to do almost exactly what  the "Compressed Cache"
project set out to do:

http://linuxcompressed.sourceforge.net/

  _Please_ take a  look at it. Rodrigo de Castro  (the author) spent a
_lot_ of time working out the issues and corner details which a system
like this entail. I've been also  involved in the project, even if not
actively  coding, but  giving suggestions  and helping  out  when time
permitted.   This   project  has  been   the  core  of   his  Master's
dissertation, which  he has just finished writting  recently, and will
soon defend.

  It would be foolish (IMHO) to start from scratch. Take a look at the
web site. There is a nice sketch of the degin he has chosen here:

http://linuxcompressed.sourceforge.net/design/

  Scott Kaplan, a researcher  interested in compression of memory, has
also helped a bit. This article is something definitely worth reading,
and was one of Rodrigo's "starting point":

http://www.cs.amherst.edu/~sfkaplan/papers/compressed-caching.ps.gz

  (There are other relevant sources available on the web page).

  Rodrigo has also written a  paper about his compressed caching which
has much  more up-to-date information  than the web page.   His newest
benchmarks  of  the  newest  compressed  cache  version  shows  better
improvements then the numbers on the web page too. I'll ask him to put
it somewhere public, if he's willing.

Jörn Engel writes:
> On Sun, 27 April 2003 14:31:25 -0400, rmoser wrote:

[...]

> Another thing: Did you look at the links John Bradford gave yet? It
> doesn't hurt to try something alone first, but once you have a good
> idea about what the problem is and how you would solve it, look for
> existing code.

  I think the compressed cache project is the one John mentioned.

> Most times, someone else already had the same idea and the same
> general solution. Good, less work. Sometimes you were stupid and the
> existing solution is much better. Good to know. And on very rare
> occasions, your solution is better, at least in some details.
> 
> Well, in this case, the sourceforge project appears to be silent since
> half a year or so, whatever that means.

  It means Rodrigo has been  busy writting his dissertation, and, most
recently, looking  for a job :-)  I've talked to him  recently, and he
intends to continue on with the project, as he might have some time to
devote to it.

  On a side  note, though, one thing that has  still not been explored
is compressed  _swap_. Since the project's focus  has been performance
gains, and it  was not clear from the  beginning that compressing swap
actually  results  in  performance   gains,  it  still  has  not  been
implemented. That said, this *is* on the project's to-study list. 


  Hope this helps,

--  
  Livio B. Soares

Re: Re: Swap Compression

[rmoser]

*********** REPLY SEPARATOR  ***********

On 4/27/2003 at 9:04 PM Jörn Engel wrote:

>On Sun, 27 April 2003 14:31:25 -0400, rmoser wrote:
>> 
>> Yeah I know.  I really need to get a working user-space version of this
>> thing so I can bench it against source tarballs and extractions from
>> /dev/random a bunch of times.
>
>Your compression won't be too good on /dev/random. ;)
>But /dev/kmem might be useful test data.
>

Ahh okay.

>> >Why should someone decide on an algorithm before measuring?
>> 
>> Erm.  You can use any one of the other algos you want, there's a lot
>> out there.  Go ahead and try zlib/gzip/bzip2/7zip/compress if you
>> want.  I just figured, the simplest algo would hopefully be the fastest.
>
>Hopefully, yes. Also, the one that doesn't trash the L[12] caches too
>much will be "fast" in that it doesn't slow down the rest of the
>system. This aspect really favors current uncompressing code, as it is
>very easy on the CPU.
>

Mine doesn't do anything :)  It's the lazy-boy of compression!  I don't know
enough to trash anything

>> But really we need some finished code to make this work :-)
>
>Yes!
>
>> The real reason I'm working on this is because I favor speed completely
>> over size in this application.  It's all modular; make the interface for
>the
>> kernel module flexible enough to push in gzip/bzip2 modules or whatever
>> else you want:
>> 
>> <M> Swap partition support
>> ____<M> Compressed Swap
>> ________<M> fcomp
>> ____________<M> fcomp-extended support
>> ________<M> zlib
>> ________<M> gzip
>> ________<M> bzip2
>> ________<M> compress
>> ____<M> Swap on RAM
>
>Exactly. It might also be possible to choose the algorithm at bootup
>or during runtime.
>

(note:  Using swaponram as an example instead of a regular swap to
show how to avoid making the user actually give a swap device name
for that particular feature; this works the same if you replace
 " -o swaponram=24MB" with a device like /dev/hda4)

Okay, again, swapon -o foo[=bar] should pass whatever foo and bar are
to the kernel, and let the kernel evaluate it.  This way you never update
swapon again ;-) Except of the usual (bugs, security fixes, etc)

swapon -o compressed=fcomp-extended -o algoflags=fcomp-mdist=1024 \
  -o swaponram=24MB

That should be completely evaluated by the kernel to mean (as long as
fcomp-extended support is enabled and loaded) to swapon compressed
with fcomp-extended with a max backpointer distance of 1024 bytes (which
is 16 bit pointers; always use the minimum), and do a swaponram of 24MB.
The kernel will look at it, as long as all modules needed are loaded it goes
"Okay", tells swapon what the name (swaponram0 ?) of the swaponram
is, and then that gets handled in userspace as a normal

swapon swaponram0

would (assuming that device exists; think shmfs), meaning

swapoff swaponram0

would turn that swaponram off.

>> As far as I know, zlib, gzip, and compress use Huffman trees.  I am
>pretty
>> sure about zlib, not sure about the others.  gzip I believe uses 16 bit
>> backpointers as well, which means you need a 64k processing window
>> for [de]compression, not to mention that it takes more work.  bzip2 we
>> all know is CPU-intensive, or at least it was last time I checked.
>
>Yes, zlib eats up several 100k of memory. You really notice this when
>you add it to a bootloader that was (once) supposed to be small. :)
>

Bick.


>> Yeah true.  But for guessing the decompressed size I meant like when
>> you don't want to load the WHOLE block into RAM at once.  Ahh, so you
>> swap in pages?  Well whatever unit you swap in, that's how you should
>> compress things.  Look I'm confusing myself here, just ignore anything
>> that sounds retarded--I'm just a kid after all :-p
>
>Will do. :)
>It should be fine to load a page (maybe several pages) at once. There
>is read-ahead code all over the kernel and this is nothing else. Plus
>it simplifies things.
>

Heh, cool.  Compressing groups of pages I think is a bad idea; you have
to waste time RECOMPRESSING when you pull a page off the disk (or
flag it free)

>> >a) Even with 4M, two pages of 4k each don't hurt that much. If they
>> >do, the whole compression trick doesn't pay off at all.
>> >b) Compression ratios usually suck with small buffers.
>> >
>> a)
>> True, two chunks of 4k don't hurt.  But how big are swap pages?  Assuming
>> the page can't be compressed at all, it's [page size / 256] * 3 + [page
>size]
>> for the maximum compressed data size.  (4144 bytes for 4k of absolutely
>> non-redundant data within 256 bytes).
>
>4k + sizeof(header). If the compression doesn't manage to shrink the
>code, it should return an error. The calling code will then put an
>uncompressed flag in the header and we're done.
>The header may be as small as one byte.
>


>> b)
>> Yeah they do.  But to find the compression performance (ratio) loss, you
>> do [max pointer distance]/[block size], meaning like for this one
>> 256/[page size].  If you do a 4k page size, you lose 6.25% of the
>compression
>> performance (so if we average 2:1, we'll average 1.875:1).  What IS the
>page
>> size the kernel uses?
>
>4k on most architectures, 8k on alpha.
>

Let's make this a swapon option at some point, i.e.

swapon -o page_size=16K /dev/hda5


>> >I didn't look that far yet. What you could do, is read through
>> >/usr/src/linux/Documentation/CodingStyle. It is just so much nicer
>> >(and faster) to read and sticking to it usually produces better code.
>> >
>> 
>> Eh, I should just crack open the kernel source and immitate it.  But I
>have
>> that file on my hard disk, so mebbe I should look.  Mebbe I should take a
>> whack at getting the compression algo to work too, instead of pushing it
>> on someone else.
>
>:)
>
>Imitating the kernel source may or may not be a good idea, btw. It is
>very diverse in style and quality. Some drivers are absolutely
>horrible, but they are just drivers, so noone without that hardware
>cares.
>

LOL!  True.

>Another thing: Did you look at the links John Bradford gave yet? It
>doesn't hurt to try something alone first, but once you have a good
>idea about what the problem is and how you would solve it, look for
>existing code.
>

Saw it.

>Most times, someone else already had the same idea and the same
>general solution. Good, less work. Sometimes you were stupid and the
>existing solution is much better. Good to know. And on very rare
>occasions, your solution is better, at least in some details.
>

It happens.

>Well, in this case, the sourceforge project appears to be silent since
>half a year or so, whatever that means.
>

It's dead I'd guess, unless someone can prove me wrong.

>Jörn
>
>-- 
>Data dominates. If you've chosen the right data structures and organized
>things well, the algorithms will almost always be self-evident. Data
>structures, not algorithms, are central to programming.
>-- Rob Pike
>-
>To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
>the body of a message to majordomo@vger.kernel.org
>More majordomo info at  http://vger.kernel.org/majordomo-info.html
>Please read the FAQ at  http://www.tux.org/lkml/

--Bluefox Icy

Re: Re: Swap Compression

[rmoser]

First I'd like to note that I'd not seen anything on this topic up until I
actually had said something in #C++.  I got the linuxcompressed
sourceforge site but already had my algorithm and I don't intend to
defame anyone, nor have I attempted to steal anyone's ideas.
I'm not rivaling anyone either.

... But I am starting from scratch.

*********** REPLY SEPARATOR  ***********

On 4/27/2003 at 4:57 PM Livio Baldini Soares wrote:

>Hello,
>
>  Unfortunately, I've missed the  beginning of this discussion, but it
>seems you're trying  to do almost exactly what  the "Compressed Cache"
>project set out to do:
>

Archives.. archives....

http://marc.theaimsgroup.com/?l=linux-kernel&m=105130405702475&w=2

>http://linuxcompressed.sourceforge.net/
>

Saw that.  I'm going for plain swap-on-ram tying right in to the normal
swap code.  This means that all of these extensions (compression) will
go right to the swap-on-ram driver too.  Of course, the kernel should be
smart enough to make a swap-on-ram the first choice by default, meaning
that it goes to SoR before going to disk swaps.

It's a lot less thought-out I'll grant you that, but I'm not the type to start
with someone else's code (I can never understand it).  Besides that, I'm
just working on the compression algo.

Both ways can go into the kernel, you know.  But I've got time to do this
and I'm gonna funnel whatever I can into it.

>  _Please_ take a  look at it. Rodrigo de Castro  (the author) spent a
>_lot_ of time working out the issues and corner details which a system
>like this entail. I've been also  involved in the project, even if not
>actively  coding, but  giving suggestions  and helping  out  when time
>permitted.   This   project  has  been   the  core  of   his  Master's
>dissertation, which  he has just finished writting  recently, and will
>soon defend.
>

>  It would be foolish (IMHO) to start from scratch. Take a look at the
>web site. There is a nice sketch of the degin he has chosen here:
>
>http://linuxcompressed.sourceforge.net/design/
>

Cool I know, but:

<QUOTE>
Bottom line in swap issue: (increasing) space isn't a issue,
 only performance

Discussing these issues we've come to the conclusion that
we should not aim for making swap bigger (keeping compressed
pages in it), that doesn't seem to be an issue for anyone...
Specially because disks nowadays are so low-cost compared
to RAM and CPU. We should design our cache to be tuned for
speed. 
</QUOTE>

I'm working on this for handheld devices mainly, but my aim IS size.
Speed is important, though.  I hope my algo is fast enough to give
no footprint in that sense :)

>  Scott Kaplan, a researcher  interested in compression of memory, has
>also helped a bit. This article is something definitely worth reading,
>and was one of Rodrigo's "starting point":
>
>http://www.cs.amherst.edu/~sfkaplan/papers/compressed-caching.ps.gz
>
>  (There are other relevant sources available on the web page).
>
>  Rodrigo has also written a  paper about his compressed caching which
>has much  more up-to-date information  than the web page.   His newest
>benchmarks  of  the  newest  compressed  cache  version  shows  better
>improvements then the numbers on the web page too. I'll ask him to put
>it somewhere public, if he's willing.
>
>Jörn Engel writes:
>> On Sun, 27 April 2003 14:31:25 -0400, rmoser wrote:
>
>[...]
>
>> Another thing: Did you look at the links John Bradford gave yet? It
>> doesn't hurt to try something alone first, but once you have a good
>> idea about what the problem is and how you would solve it, look for
>> existing code.
>
>  I think the compressed cache project is the one John mentioned.
>
>> Most times, someone else already had the same idea and the same
>> general solution. Good, less work. Sometimes you were stupid and the
>> existing solution is much better. Good to know. And on very rare
>> occasions, your solution is better, at least in some details.
>> 
>> Well, in this case, the sourceforge project appears to be silent since
>> half a year or so, whatever that means.
>
>  It means Rodrigo has been  busy writting his dissertation, and, most
>recently, looking  for a job :-)  I've talked to him  recently, and he
>intends to continue on with the project, as he might have some time to
>devote to it.
>
>  On a side  note, though, one thing that has  still not been explored
>is compressed  _swap_. Since the project's focus  has been performance
>gains, and it  was not clear from the  beginning that compressing swap
>actually  results  in  performance   gains,  it  still  has  not  been
>implemented. That said, this *is* on the project's to-study list. 
>

I'm going for size gains.  Performance is something I hope to not hurt,
but an increase there is alright.

>
>  Hope this helps,
>
>--  
>  Livio B. Soares
>-
>To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
>the body of a message to majordomo@vger.kernel.org
>More majordomo info at  http://vger.kernel.org/majordomo-info.html
>Please read the FAQ at  http://www.tux.org/lkml/

Re: Re: Swap Compression

[rmoser]

Well here's some new code.  I'll get to work on a userspace app
to compress files.  This code ONLY works on fcomp-standard
and does only one BruteForce (bmbinary is disabled) search for
redundancy.  This means three things:

1 - There's no support for messing with the pointer size and mdist/
analysis buffer size (max pointer distance)
2 - The compression ratios will not be the best.  The first match,
no matter how short, will be taken.  If it's less than 4 bytes, it will
return "no match" to the fcomp_push function.
3 - It will be slow.  BruteForce() works.  Period.  The code is too
simple for even a first-day introductory C student to screw up, and
there are NO bugs unless I truly AM a moron.  bmbinary() should
work, and the function it was coded from works in test, but neither
have been written out and proven to work by logic diagram.  It's
fast (infinitely faster than BruteForce()), but I'll try it when I feel that
the rest of the code is working right.

This should be complete for fcomp-standard.  A little alteration will
allow the fcomp-extended to work.  *Wags tail* this past two days
has been fun ^_^;

--Bluefox Icy

Re: Re: Swap Compression -- Try 2

[rmoser]

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

ERRRRRHHHHM!!!!!!!!!!....
...*blush*  I should attatch files when I try to upload them.  Let's
try this again!

Well here's some new code.  I'll get to work on a userspace app
to compress files.  This code ONLY works on fcomp-standard
and does only one BruteForce (bmbinary is disabled) search for
redundancy.  This means three things:

1 - There's no support for messing with the pointer size and mdist/
analysis buffer size (max pointer distance)
2 - The compression ratios will not be the best.  The first match,
no matter how short, will be taken.  If it's less than 4 bytes, it will
return "no match" to the fcomp_push function.
3 - It will be slow.  BruteForce() works.  Period.  The code is too
simple for even a first-day introductory C student to screw up, and
there are NO bugs unless I truly AM a moron.  bmbinary() should
work, and the function it was coded from works in test, but neither
have been written out and proven to work by logic diagram.  It's
fast (infinitely faster than BruteForce()), but I'll try it when I feel that
the rest of the code is working right.

This should be complete for fcomp-standard.  A little alteration will
allow the fcomp-extended to work.  *Wags tail* this past two days
has been fun ^_^;

--Bluefox Icy

[-- Attachment #2: fcomp.tar.bz2 --]
[-- Type: application/octet-stream, Size: 11115 bytes --]

begin 755 fcomp.tar.bz2
M0EIH.3%!62936?80L;4`()5_K/ZX(@!________?^O____\"```0``0`"&`G
MK[P'N'C>X^U]W=-=SGR]7G=?30(!2E0]L%1\]W%WW'=@N#ZM[WWLZ][8KPOO
M;([U-W>^VVX5V][Z`;"MVN>WT%9M+KY<)5?6/9+[K9V;6S>H[';*V#ZEI][G
M>`^WU]#Y=:9N$D0(`!!">A-,2-,E/VH4]3VIZ:IZ)^34FGJ::9/2/U0]0V4&
M@#$$!`B:$TU3R8D]1Y1ZF$](-``T``````!*8DBFJ?JG^IHU)Z:3U'E--!ZG
MJ!Z@:`:&C0``&F@#0`"%)$IA-)XJ/!3TU'DGE-/4]338HR>IM-$T``T``!H`
MT$21"F3`(IZI_JH_U3U-J833U3QJGDF(]1IA/28C3U!IH>D-`/4`(DA!!---
M&IA%3\R4>10_0H\4?J9/5&@T`::-`-#)A&#\0^']W[.KK7=_\95`[E8A=S"#
MR,'=4WQ<0\JM14$L9^VVDYT!J[8@&4!A!8GFI"$""2$S1*9A(=PTAI(0W;('
M(0+`1-U0.>5Q:I(IJE:J8HJ&2J2J(@B8F&1H*2@(AJ(I@EB`#_,J9#39F514
MT5,E5K+#`A&AI@(DB60A":$BIB0HF@B*D7(<!@EB2"$EH*)E+P0`ZH12!5'O
M++ZC^N<[7N_QI?9-TS_"7C[=.WVUHMM]I:M)7W1L\Y^&$9U[^QS\IE>3U-V\
M=OX0_%^/E,32S#+>V1G^.4YRM-/9.L;/2E5N!)F@B?-=6T/4X]Y-Z8]3\WB?
M!B5!FIJXURZ(`X>9UFR)UL.U9^P<T8)98=/\'7+=V54.GB]J'>D-:MC^F):1
MVA)1>G/E2%DX?'1'BYWSHXS+W:,X74O%N&C;5=MH";+=RLI/#,$,J$(4)<V%
MI'8X&0A&-QW*UTA)I"#TU+]]*.R%%AA">%3QMN@-X;1"OG08E0P/\\+*&H@4
M0\E6+E!QK3$`Z6UI#PU4>_&MQG>Z.ZO6VK9CV[R4MGY[UWFH]/I<[GV9J0;1
M@0A"'S^F[T?DRLAQFO,^?SF"&WY^_)Z^XI;P35Q_YLB=HQXH=@3(F-^L.J[$
M@5X4\/#FY<N73]<('R,=_7@,Q!2.KCD2Z!AA>5EI4%32U'R<?BHK5?O7$4DN
M5Q^M5+N3JM?/3VTB%]87S`(D,]%EAA-THD(PD8PE6_QD]W+VQR#I[3T6SS1I
MU!=[8'LB^'/QD]`G,(@B;,LK""8""J;8@J<>+];7Z1Z1NV,86;-6A)35$@2Q
M9M'5'@YQ7"I:*:/8#,'JJ\J.R04#9I5@IB+T>C1L!6$CJM')M,](MOBC34M9
MF.H?'PI;/<[MAMQY16T0*@<"!5FEH(AF-R]E&1ZM*[\"[9$PO;+(S_V.G?U+
MV'/A8-1COT0^]&Q9Q$L:F/[+>ZQ0A@3/%!:\:@PA_42AR?L8O][%=KW\>8$\
M*:3("'?7L**B'B#I*&Z#8:.$_7+^3OD1)./,>;7>MH?=&L_66!!8$#\VE;2'
M,YAMXWT7L^8Z^PN1VD"H>S%"WA<@P8B#8A&<L-2&J)#4%&H+1EI05$M!*(,A
M1X'?S<74>)T=3QF9CVVG-D/DDAZ'M\['MC?5$(A"217$@OHS'\;+)>8B+O,O
M&%JD?&VS&=BFU01':;44ZCR6O7,@<K=[54F<&EH_FR[_H\?3AS=A9V.>0DR<
M46GNH034H>;'U:O@35M*OZ,"7]+L@1L1#]O+&[0&T>(`3A,XRH+H93=K&WK8
M#(183L_*\8!W&YH/HO(<X5,#;$<FI-BD'*R>I66EBPO-Z9F3,V_[!Y6]1,#N
MO<,93(]7U7#;I7\+I4S;C8+3N'^)C&UMQ%V\PAX7NXG"(=YV.5,#,=UW<_JB
M\_/#(JSK=,P**ZK5S;M$AIQ*(0"T.,.39^BQ^$<ZZASAE8D3?2\.G1!W(C#)
MJ[,F=:ZYMAL3#XST8:H)+P%_(;5!2S$$DT<W1AJM=C;;QD:#'C'TO(;1*T,#
MO\-M$JT(&6:4#?+-,]9ATI72,:WDF:[>W9Y84.VS#`K:_R7:JZ46F&"F)K36
M]Y/N!K]U8M/#NY8"H*P#4'&L$*@O2V_+`\P@%@QJ<*V.!P:Q+&6*W%3B$G3I
MX8^9NJL30GE>P6C.[U&FWS3@'P:L%.--=?F>I(+OD=][]`QDYZJ_0B)XJ_IL
M>K+JADGK3</T`V;])@X,H+X5;<>/[C/\[?]Z^Q>Z=)*L4)+R%%D*S:?VMUAP
M?KUYE7TP$'0DP=D:5[H9S!<^5Y=^>=\UUN%-7M$.P0`6TW'@GIQDG(&43%2S
MC)GAB:JQAJ2-,&([LO5=_J;AV&OM#*`LOK=+:-3Q<76JJS9M;L'+L@;88=?3
M&!"#`NP<`2](C3.FP4#JIN'%;M`1V;3>ID:!+47.+(='.5UH(<O>]WJN0PXA
M@G.K,.Q'<X]#BA4',E#$&X%V!KOW=?R&Z^@T-GL`D+.&]*'C4'9&?W7GMO3K
MBE@<1X4X<5!13X9V*V.^L7,JGKIOLP@]@:^,OL(15A_-9/[\[^9`/T(^L_CD
M=F<TIL$0@0]A&CD"#-BX;J;WQOCH6P63:-P);7<*VFZJC3Y>>3@M6*QRCZ0(
MH3:(;0D&+0-*/`UNN59;C<I7^E9<[=6^7?9=>WM6N'K\M:,^;#.BJUHM[OQQ
M&<'*EV'>A7``P'?5=/EP44W$5JDV#I\N#+#Q^<8TG;F^$(A80$T3N4H^O=)$
MY&&ANG'OE\=`OX.^YR"6CA5;-0A4N$(6V0NG#.-](N829%4.SK$4$XF/&=5%
MF9LKV+Z5'FR@.A!5LCB&$3Y*=$_MS%(<+9(<KGWN!C=NE+SRI]0.N&'*I19[
M.[ORLR'@YE@*+"X$7$I184JC;'$[12YE=PR.6:OE^?+(!H&4H<0DNJ^D&--R
MJ2NS5*8T9/51!8,%X(::Q?E[/=2O7@1Y;=>GL6V[)R.&\E;9&@KZ,Y\]-<)&
M"R3+9B]70D%R89EM4>*UVN3V3R4<Y3%G-SMCM`I=@4Z.B'<**^7KO8@2;![=
MA$&3"@#N!W9I!;>E'(H/((K2NT<Y9O/:_@IWJ%%2Y/MJD=)M8IC3H<B(O(/Y
M+(4U&KXYO9;)ZH<#"6D1A,Z;BMF@59R@L"F[FH5.'JK&)Q@K,X!L8O>H+0)>
M&/B0FD!KNX3<T^AN14X>!)'GYZ1[%P7!-QMM<>79L[^;>V<5ZEMP^34UYN;5
MOFG*1;QQ*.ADS3$J0'\$3(",^3WVN+Z.!T9CXL7>M&:`44-\,<N(EB&'2M;<
M&-3NRHDA:BH./<%%IKE3L0OM19%63+:>-H'BJHW&\RB<"5Y0F*1@V6]^QGLU
MAQPK<Z544"GEKX@:"U/"DA\2C=Y:3LPQ):%;;22D`PI0O(EZ4/;9[%5[YO;4
MW&*%)!B$;5XZ'/?CH4=;:I.L?#3%`=G#OM4;JQZ$8\[$-WVUPQF]^6<@>"%U
M^CNF4$U>K5\[YL>Q7I5@-K&N`NI3AE':<C-T>96;T-CH+1\'::]ATTUQE]G.
MM@IJ[/2RVFHOUUB`KW6;0E97/KKT"BOEYC>14%>V&+;2AL_#8.5>ZS&ZVS<5
MH.9HQ2&.IA>\J^@KSC3'0:,6EVS@#3IHZHM)Q=B&=U<3+*>.6N==V&3Z679R
M+7Z5HU5VKYU575V)[X.-S5.LF'B]]AMC8_#PV9,R0F8%%'38:AV%ED[FK]A]
M;!QY_\RN>YO9^`]UA9;TWP_'$P87YC>0('S'ML^-H3#Y;&)\JL/X'7F,%\5'
MG+!:+S=^>S"3BQ[8<>IIM$[0[<QZ"(?#''M=Q,LCO6#$'&/1)%U>..40A<)+
M@0A<$(11STFV#'5#`'\6(X";(O3"/"-$3=408/6T`U"E$C[M'-(P9QG&#F]9
M^:WZ;UZ3U3/:Q\IQZG@>O^6+0]YAZOW*N6.L/N8K^X4SW]CF+>W4.C4;7A=M
M>5DRPD5C*)YG*<[NW.];?JC2[HJGT5/>LY=)OL^BCC)@?C4$[]K7&Y/<;'8=
M$H#>NCX%`QH$7#A@X0#%%-3ZKWF_N'U"IA6!`Z/*AL6@-A1"$0(&T@42W#EK
MSV#&DZD@4A1XR$.O"4#*/+YN^=<3#*#OS,OB\HM=PHHG1JU8NI.@E8'$.&FU
MG)I[O]NFS+1-2WC[[5YVQSIX?8_Z%3@M-/"V^Z8D0_#-R%LDC.SXNZ@<6RJ!
M4`@R!_IMC]0GRW@[\]6L'&KQ<I629]>&?WNI[U.'>ZEJ@/21)<4%.;W#^($`
M?'.HWIJP#B/L.18ZM.2A("2J&0:JA6HA*I#L(9W$SNA#.Z%NPSOKCJDLU\WJ
M@([<M_Z*K[>+9<)R,8R@;V@[W<93WF;^^G1!N9^FZT;@[45[=6=(>FANRK8O
M5RHG)CVZ6Y8%I@/>6E:VQJ)JX+RG)I-J0(N?.I*1F%KPMU6"\G"K9/J^4++5
M,JM],HA;ZK)APD5LI]/1:L-;JP9LZMLMEBI4+\:E#'YY*)+=!9G./J8S+GQ.
MJ8QD@,SV7[E6X![*Q[=Z^.=@9,(A`B!\?EH>1@\H3%1$24E504ECA'\"P]`2
MX%,%1M'YH#"=23$0,03!DIDQ%%4&29!5`T41)31$$0)0TE"5D9F9%''Q$8^W
MV.XCH^&!<A'TN(]N1I2\_-=X@Z3X_OS(,8V9:]V*9D'?N;I/ZTD##!,+_L&I
MJRRA0B?WJ^C`H/:KWBA<.#QJQ`@X(&7#@8?1@AP:V/93TYXV(7#U8>G#3B9$
M05^H,7(CICDZ`%<3$R-UF:FI.U.'M(%`7EZC+`2P+(D,#"$6"B34%;!5-2HG
MG((C:A$&!H$\FV+P+?#RG:XO1VH@ERUJKEOT_$Y)%S(:7"_.Z%C\C!,8:>O&
M_NWC9UY`WE&L?N0TE'SS)?><M#.%^$=0U:):M)EOHPU/R=X?#M9.D5,"AC,,
MK/HVR=KS&!742(+8:&+1[K(?V"9<X9&I]I7IPI>KS>:<#"=1H?20(!'2\N>/
MIZ[]*7N,M-N05'VQX9CPA;!\G`NKA]8AUVYJ-^=.1C?>1G?A`Y7G6,AF7:7`
M<1N911=QL-JR12HS^FYC9T`)]'A*/H*2K5*0&3Z4_+?HNR(XD((HR$=(27&H
MBXXJ*,[;78#7O[/6[F-WWAG0IYQ/812+T@$='<E\.S$]"_:>;\C^\3'O^13O
M%][N![[$//$',/G]&Z_T^-=:L%+!"#V?.4P#Y](V`@R,/B'E'_.T<Q@NN#(S
MDBZ!W^GZEQ4R8]9#)B/F(0@>\^9*>"P3;[@</-%?:._(;0^`PKU11-X,)I=)
MT:(Z13%@#([4J)!-ER"T.8]4'T]/[*$UJXCG&(&#X;S_1/A3C(8^43\@/6#3
M]#C>6$D!/$>]YG%7JZSK?+S$'O4-%[C:IX\_(>U/PF,,`^6')AYHM#'M=T&G
MD/0MULN'[[D(43IP.!W$*@A<>J6KC1<>T=$HIC4$J+4IE0<<!*<K4A<8]"3U
MAM8?@NFQ\5>1:226=%@1!L84_/@KR5:MTW-O-[W>CJ'NF+P>UZ`S-ESUY&[+
MX*-6X8R><,E5+,AIUV7@<3[3ZX?97<>#K;J]U\_XQ\9A0''HYE+(OS(^<"41
M[H;<TP&1F!B8L';P,2D(D)J@I<S$=8^7;9TA\"1#?$8!^GZ_N/:5S1[-5%17
M,S#X(5LJY104>&4?)6>9LK*-GO:-#GS`1UC#L6-ITT>M-_S'^]#@EJ3)QC`8
M!26?VP+T&6.`93D'$07;QI-F<U3LCH#$M`:&+P0+1-T&XO**!E"P,K&*$2M.
M5>Y?X9A,C</8%8A;%C."-H(+%8Q"]RV:/*A['4W10V3J#";=AJ%H-1IXBB5L
ML9S4/&/J.9.,D76^>E]96,,S#%CQ4$JS";.&:$AQ$K6:IYP/JBJII/*E`BM<
M#"ER<QE#(.$)!\6\GJ6MN-YQ0.$D0D!\T:B4"P$'JXX+333<R=)(1)_CXL&4
M4]<?3M-;*.\TH"@@[$-KY!^<+C<^(H#`J[*1D/IW5=W.2"^5_-![.0ON+,S+
M@CA(025;5]<"?:`%K`!&&LC@!Z"S4I"3@-2@:7^!P&5RYLE*OM@Q6*N(]_^7
M*=/EVEKJ.0X`<9U+,57JG3@DD"2*!ID#-\W#-M`:*_C8@(!!(`6,ZH".B02M
M)>@,-:8@PD,$[8!Q*91(K`@<DFAD99ZW-A",W1H)U.H-!&8.:A#9Z@'.G`B(
MJJ@AH)@FHB)FJJJI!B(@B!H)FJI)J9A)P)G34\FL=F'UPD*II(AWVC,WY\4Z
MPQ$<)31H_7H=/U9F4G02@WNF^UX26H-FI5R`6T=:TS31J,#8L,M2AJ$U*]ZX
M]@8D%(ITAY+""[U"S%*U%#>&T6@&W*6ZO#UL`/*`GP@=?9:VFPX=$-U-B._"
M(XI;0!-=*:B_UIU-2:8'W1SO*')HZ'&P10\'G$I>SBCF"Y##J<PLH)0EY8H@
M'@^5G=DP1WL!XL&3*^9Z4I,CX.A$4-L28'F?^9]?H^2KLBO*/50S/P[@5U$,
M$]L-9B2P\7R9#4!PH]%)"(K8"RP`KIM'77!SBP-1CD;FX,ZD7A$B4`+H;K`G
M&()<BVKN:!@1KJQ---7)A#S2,>:*P6&J,MN=8.H`;@Z7<<&^*S"L60;=J,_'
M$B?C5?9`&^K'2^@?(<M/)B!5$<T`TRY.R@5+`9AZ:TH;HABI0(&*1O9A&,\&
MZ,@,M$7U-*FDM0Z30\YB&&-9JQE,9U%=S]C.A5-=802"2"28EPD@Q%D4]TXR
M79.FQ;FMZTK-^5P(&$;I`3%N]:S#DN8W&^@+.N20(:XN,^*"@&MYK`/DPI-'
M'DG3!\S]UZH(2N^VBK]@F&7BX:5-K-X)\@)+A'Q*<+XA.#N\J]T-T:4J81`3
MWDUFE8)DE&-_M9$N1^FQ!40Z4&80/J(B*?SX\UO.]J`F:];>Y'E/0QO6[-E_
M'`-.)R>4XP#FG%)A.SLS(>(4D@ECF-JAPCX)F5[+F2G4L6,P[ISJ%Y:S;U/H
MB=7:GOSJ0:=CJNKR=]1Y-[N&#C)D$&9`T=A!*>7@0R(22GL8"M9<NA6&FK4A
MIF]OLM%#RJ@SB_R-*26>>I'`=_(*'*#B08(H/"]0#LXT@*C*;`H,&VHPQ%A<
M3'@G+`62`Y]52/+6T.M[=X89V0)*.XMM$,K[MO*(.L8O1VM,L!O`80+A`2\7
MVE?)<VG`W'/[<H*HJBJ#2@--*3X.FKW:21;BH&HUA!`,""5`8"0E3=B4'*$V
MY7:1J(`:CE7DA[[G_<;;_6EFHR)*A"8#C+,/N<,,OA^K^K_W)\?`>*"AB4Y5
M*H*V;0LM-0B%"7A(A]/=CL\8J<CBB=;SL%[.H/6D^J#[Q#X!<QY\+Q#I@/PG
MS0+@LG3I2,0B64@.X+&I"=5SM.J@N[A4D!Q*@!*MD2KD]94+)QR>01HL9EH)
M1*"E\['0`T8F<&D6Q]KQ3XZW-6.K)AXL7&J9VS%AABIMM89&]H"^+2G=+534
MP9_@[$\"R%$"$#D6+PYWYS$9/4P8$6#3*86BH'$JIMT.0)0)IVDBU3DO.ZQ>
M<9>3(/"5PJK*R18=7ETKF+;[N*I@>79-WVXR=@Q1U*A!4*,BH2<_&X:&C6$S
M()K*"1AS@.LM,7`N/TV[YSM=31P>H2'%$A$M$,R3%+LD&^8X%8IB<9F-TW1C
M@O.Z$L%+#&T9`"@D0.&$U\#0LM_E;GAX/JR]'I30'1G<7#6(<8IP@!EIBA'0
M^[I=+;6>%OI>MUXNBG09'#F/T3$ENZC9IL=AQCOB),Z"MX)/=P9.0/=0+'4A
MB'UCESONY9$+AJ+B,4Y1,5<S/O4(#"\!U:]>VH<6%!ZXHJJ%U`:CXIH>@(=/
M+MWD290X81OVF`JF@(0&@"$*+#W0(76BRPQ#,UJ(3@"!<Y]2/4*8F(GH`]HS
M7%EV1^MT\=<##$"@"C`@PB$)(D)HJ22B&`H(^1F4]/.`TI0#YV9J28T&T'JD
MX?<*Y1+D4N16H,@.-#<ZG>!T0_;PUWI70ZF>G;JSIR<$`(_M-(AF/F3M84GK
M(+&)OO="&#T$DT^!3N-Q-E<;SZ"G67=M(%H;:H;$TH)ZRVAE`ESYC('K=F:^
MYRPA:Y+&$,U<IG1P&7.S8M:DPLFJ"1:AF>ST'800A`K;LQ\S(2'NG>6.J`;2
MQ<,MR<[>BX@R@4]V>)QTDN[:<.+9#CFJ;][!>QXHAX$&$.OO.@VH&<+OV,AO
MP6D+ISZS./PT9:S;681@9IUI3H@S95TSIV9,5N!VCH,Q*,S',*,,SIS`/(SA
M#L4.."X/RC(OUZQB;F1<Z&KWY0V3A8[^M+YK*\D=)=#9K3Y+%SR&TW=MOU`;
M+MLSR!/7\5K<J?7+-%)8AZ6@S4Q`3F'$IV1^.=\+0B$0RC4'VA$/4$1RS*#)
MRH2Q%3!*;Q/=^,T6#A$A/W0-URA,ZTTIX9F.</5&S`G2%5D\#B:[MN0J]2>#
M&[)R_"TF$"!"ZB9D3O8J+KJU("UUP,]YH%@P;(84E3JCHJ0\`00,):FH@CP6
MFQ<[E`DZ*K':S(R<M]49KJZ,-5NYN-4Q2`3RNG=XD(KHLO;@&%TA<0/7,TL4
MZA`AL,%CN)#*PP,;SP+B&D7`3.#(G,.&G`F3'0=^V@*V9,ULM(8:!;)W(TF]
M;$X#@AX];.G;$W))/99+0+9QUU2OE(P-=2'6L61(-P3&`R2(L&)F53JBX\SV
M7#8G`&4!O/P0FO1$XF[*1#:]`P'=*8>#`?-,B!PAF.KO!W@8LRK=,^PJB3OK
M,,91`B!`CJ!P*(MI31E\=7Q'?FQ[O#GIJ5-GY*.<2`=Y#6V*=G;AIX<'-L-M
M!0[239)DAI$MF_6VSC'(F[/.;#VJ@Q#F4*U9/M%@D8AB=;[T3D<E%YF!MFGD
MS>5,O&>Y%9%(1C`60="&O5S/K6;`WY5L>.&S;%"7,54,(H#M)SP53#OG@ZWN
M6G?SFC(NK?"<0<V$.+BJE:02:Z_G*(?@YX-ZS]3.$MF=Z[R*\D4+V35!4`]6
M/19(480F0[#M1H`W&Q6#0R@0G2[%;P*5(?F3JJR!SPF)4R3@89KD*\B,QU,4
MYT"N@P:M@AXC&\"N58>8]0XY>XB..I%RC*2&7-G0<FXGR?],99&58(:6H.D#
MM90)RW'R;P.Z2`P]%-0#V6UI\,ILEFK`,E377Q`:-$HG,>F#UAO(Q!^"R+D7
M9[A9\NVXV,^#EY0VB3S0'B8S(QI]B,O?G#::9/9T&FKE8Z>EPS(,'KFF+S7<
MQN2\^\%&B,6"P#O](1E@**A1)R0#XN6ZY",+D"0B220>"9C"D-B#F03.8)E5
M%$4)5ZF%.$-21I@,"(FG`20R4<SVT8^3XOCTT&`,G!#Z24VA-VKK>U-[_40#
M6%HVQUOL33N9=C#3KK)WSO+C]`[=5)6Y478%1G,]Y[@!83.\M+OU5RQZ"R#2
M;B0;QD&H2#"#%"P$VZ'"_M<%L='5%MVD9`-+,:&-P0D)O&D&@U-\,N@&G:.N
MVW`V/TCL1U3:=F^#DUBBH`2-\*:\O8F3F3%9AH&Z=\87J\8%E/1S&[N9<@Y,
M$@RXPI@3MCTOK&NH,;MM.;AHL0$NP[BUZV&:UI`:W8=B^2HP"UGR<C7(%*'Y
M[&8+H.K1#?04[*Q5(6,5?0OI<UEB&A#0*!#H!RS6458NGU@^?5JY](K>0;[&
MAQI>19$:^S07QN:7(EN;T-K272"N4:K(%AC5L!"UXJ929!AW\P]$(&]//Y7]
MTL0,C^#8<1YPIA4(R[FJ5POD;82&\"Q0&_HIMTM)-NC+!'``H*BGGS'8YY,\
M#O@V+$Z^B2!8QB8`**AUO%[L;YG'4GJE0WL/;--?-];5PU'!``VC?%T'"%4:
M5PL5RI8ZD5VKHE;;)5TC&)EJ"IE((&D!"5U%NIQ:!?7<F0,@I`_#)'RVRME&
MH(:QXT'>@\PP2C<0H-L*4O2^`+(5")[\:"`&#C7-F*A#38[INX.`\&)8XEN6
M5N3ICY(&>,O`4SAA'85488TX:$0$4$JU#'&%&/.M//GWY!KY+V-PM`4XW;49
MUHA`0%P-"C1ZL8N%%`AKC0M4@L40+T%/2V#B)TJ'1$+7378XJ$+Z[,K@X0"3
MI(7T!8`F$VEZ0'$L+A5O2Q?0:5D%\7N&I1,FI:"+HYD&B6C':]$`,:8.2R$5
M6'">HLT6@279JY<"B#X>3I,/!5E%H&82=RU@F(G+Z!P,A)%DD61`02,%N%2F
ML7D@THR&+#UQ0"!PJ8LQLA8TDP8,KNRV>%J8``8@QNFS.]@*Q`H6!G%)!7!:
M#!`,$QF!@-Q%7U+0!H4KF"Y=2MV)648#*);AIC#?:KE@M%'U2HI(KJ9[LY<'
M?NS8BZ\QJ\*'(]9IL(QQ#`@YI-A0[$J=F0(P0)!$]WP*`=`Z=;(6ZH7C8'2"
M&'?34`B;EW\!87.BL7V0HY3.I'E?.SU;ZOL`"#%4DD`PNPHA?2Z'(N/OD(L@
M`N<`,ZQ;=NTQNIQ&\RX46RVAN579H&XY$'4F^[[&I34G*1#_1WE4?!`3+.U<
MN:#N.DA1&XZS),_#OL@GM0[%+.SGUO_3=M'6&S0-R?(W`*GRD#5L<.@+$<N:
MJX/5%CGNJJRHI7\-5L54?\",;,#`>U2-LJI(HW`.(]KUVRVK2&<OX;K8C:BB
M$IEH^$)(0PL7LW`X7X=XP,&$$C(,B1"!?0'F2@=\<H'+*B$4+.A2-B*0@GY=
M:;!20#?[Z"E]71E_TH7,\@2Y[@(ONET!Y'>@Z._1J33G`".Z5G)2`<Z<HB1F
MZSX[.C;(L]60Y@B@0'*;5<BDK6HJ1LX>QO5MI5C2M\LHT9]F<=B@Z^8`#(.Y
C>GA)`"1)"1B[@0!^&3Q4;`NT$`3!H=(?_%W)%.%"0]A"QM0
`
end

Re: Swap Compression

[Eric W. Biederman]

JXrn Engel <joern@wohnheim.fh-wedel.de> writes:

> Yes, zlib eats up several 100k of memory. You really notice this when
> you add it to a bootloader that was (once) supposed to be small. :)

I only measured about 32k for decompression.  But that was using
the variant from gzip via the kernel.

The really small algorithm I know about (at least for decompression)
is upx.  The compression is comparable with gzip with a decompressor
that can fit in a page or two of assembly code.

Probably irrelevant at this juncture but...

Eric

Re: Swap Compression

[Jörn Engel]

On Mon, 28 April 2003 02:52:15 -0600, Eric W. Biederman wrote:
> JXrn Engel <joern@wohnheim.fh-wedel.de> writes:
> 
> > Yes, zlib eats up several 100k of memory. You really notice this when
> > you add it to a bootloader that was (once) supposed to be small. :)
> 
> I only measured about 32k for decompression.  But that was using
> the variant from gzip via the kernel.

What were you measuring? Code size or runtime memory consumption? It
looks a bit large for code size, but _very_ small for runtime.

> The really small algorithm I know about (at least for decompression)
> is upx.  The compression is comparable with gzip with a decompressor
> that can fit in a page or two of assembly code.

Sounds interesting as well. Maybe we should add a central compression
library to the kernel. zlib is already central, but at least jffs2 and
ppp also have some other algorithms that could be moved and possibly
reused for other subsystems/drivers.

Jörn

-- 
Optimizations always bust things, because all optimizations are, in
the long haul, a form of cheating, and cheaters eventually get caught.
-- Larry Wall 

Re: Swap Compression

[rmoser]

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



*********** REPLY SEPARATOR  ***********

On 4/28/2003 at 6:25 PM Timothy Miller wrote:

>rmoser wrote:
>
>>So what's the best way to do this?  I was originally thinking like this:
>>
>>Grab some swap data
>>Stuff it into fcomp_push()
>>When you have 100k of data, seal it up
>>Write that 100k block
>>
>>But does swap compress in 64k blocks?  80x86 has 64k segments.
>>The calculation for compression performance loss, 256/size_of_input,
>>gives a loss of 0.003906 (0.3906%) for a dataset 65536 bytes long.
>>So would it be better to just compress segments, whatever size they
>>may be, and index those?  This would, of course, be much more efficient
>>in terms of finding the data to uncompress.  (And system dependant)
>>
>>
>We're not using DOS here.  x86 has arbitrarily-sized segments.  It is
>the PAGES you want to swap, and they are typically 4k.
>
>
>BTW, I see swap compression as being more valuable for over-loaded
>servers than for PDA's.  Yes, I see the advantage for a PDA, but you
>only get any significant benefit out of this if you have the horsepower
>and RAM required for doing heavy-weight compression.  If you can't
>compress a page very much, you don't benefit much from swapping it to RAM.

Feh.  Selectable compression is the eventual goal.  If you want serious
heavy-weight compression, go with fcomp2.  Ahh heck I'll attatch the
.plan file for fcomp2; this is rediculously RAM and CPU intensive in good
implimentation, so don't even think for a second that you'll want to use
this on your cpu-overloaded boxen.

And no implimenting this right away, it's too much to code!

--Bluefox Icy

[-- Attachment #2: __fcomp2.plan --]
[-- Type: application/octet-stream, Size: 7901 bytes --]

fcomp
Fox Compression 2:  Size is everything

by Bluefox Icy

This algoritm is copyright Bluefox Icy under the LGPL as it exists on April
28, 2003.  LGPL v2.0

Definitions:
  Base 0:  A number that starts at 0.  So 1 byte base 0 counters are ranged
  from 0 to 255.

  Base 1:  A number that starts at 1.  So 1 byte base 1 counters are ranged
  from 1 to 256, with 0x00 being 1 and 0x01 being 2 and 0xFF being 256.

  Order of Redundancy:  A numeric count of how much a specific string is used
  to reference other data in a file's compressed output.

fcomp uses a compression algorithm that is focussed on speed only.  It uses
little RAM, and was intended for kernel-level RAM compression and for packing
executable files on 1 Mhz 6502 processors (its creation purpose).  fcomp2 is
quite different.

fcomp2 uses compression and decompression routines by Bluefox Icy.  It was
created literally with size in mind only.  fcomp2 compression should be sane,
but there's always the warning that I wrote the boyer-moore search myself, and
someone really needs to FSA-prove that it works.  Replace it with KMP,  brute
force, or your own equivalent BM if you want a 100% guarentee.

fcomp2 compressed data is a mixed backpointer/table data format.  Officially,
fcomp2 is a floating size backpointer format; backpointer size and max distance
is capable of switching along the way.  Most implimentations will want to use
a fixed size backpointer though, usually 24 bit (16 MB).

fcomp2 uses a pointer table and various pointer types.  The pointer types are
quite diverse.  A general pointer container looks like so:

TYPE    SIZE    DESC
Byte       1    Type of pointer
X          X    The pointer itself
3Byte      3    24 bit forward reference indicating the location of the next
                pointer.  It is base 0, and a 0 indicates EOS (just like in
		fcomp)

Literal pointers (1) point back into the stream and may be 8, 16, 24, or 32
bit. These pointers are standard go-back-and-copy-N pointers, like fcomp uses.
They provide a pointer within the window that the scan is using.

TYPE    SIZE    DESC
Byte       1    Size N in bytes of pointer data
NByte      N    Distance back to look, base 1 (0 == 1, range is 1..2^N)
NByte      N    Distance to copy, base 1 (0 == 1, range is 0..2^N)

Table pointers (2) are extra power.  Table pointers are pointers that reference
a table which holds the absolute locations in the stream (not including the
table) of data that each pointer points to.  In reality, all back pointers can
be replaced with table pointers.

Please note that by stream, we mean the actual pointer-and-data stream that is
processed in the compression and NOT the supplimentary header or table.

TYPE    SIZE    DESC
Byte       1    Size N in bytes of pointer data.  Increasing the size increases
                your range in the table, i.e. 1 byte can access entries 0..255,
		2 can access 0..65535, 3 0..16777383, and so on.
NByte      N    Index of the entry to copy
NByte      N    Number of bytes base 0 to skip from the beginning
NByte      N    Number of bytes base 1 to copy

The final type of pointer is a NULL (0) pointer.  If the pointer is null, it
simply is blank, i.e. X = 0 in the general pointer container definition.  A
null pointer is always 4 bytes long including the general pointer container
defined above, and 0 bytes long not including it.  It looks like this:

TYPE    SIZE    DESC

Yes, this is complete.

The stream format is:

fcomp2 stream:
TYPE   SIZE    DESC
3Byte     3    Length of X base 0 (for consistency)
stream    X    a bunch of bytes to take as pure stream
Pointer   Y    A pointer inside a general pointer container

The last 2 repeat until EOS, which is where the general pointer container has
its next pointer as a 0.  The stream should always end with a pointer with a
forward reference of 0, either Literal, Table, or NULL.

The fcomp2 table is pretty simple.  It points to offsets in the stream of data,
which is read by a decompressor and used to give further
compression/decompression performance.  This works when things are out of reach
of backpointers.  Also, a very good implimentation may take the time to
optimize the table and stream; that is, it may move all the most commonly used
table entries to the beginning and use the smallest pointer data size possible.

The fcomp2 table is in itself not built for size.  Data of multiple redundancy
is initially entered into the table as a 32 bit (4 byte) offset.  The length is
not stored; the compressor will find an offset from this within the reach of
the next table entry at compression time, while the decompressor reads entry,
skip, and copy.  To do this more easily, the compressor should keep the data
table in the order the data appears in the file until compression is finished,
and then sort the table based on order of redundancy (aka how many times each
entry is used) from greatest to least.  As the table is sorted, the stream and
table both may be adjusted so as to squeeze out more space (i.e. the most used
table entries are referenced as 8 bit pointers, changing the pointers to point
at these and use 8 bit storage changes the compressed stream).  Note that
altering the size of the compressed stream should not alter the table, as it is
in reference to the uncompressed stream.

fcomp2-table:
TYPE    SIZE    DESC
Dword      4    A 32 bit offset of the data in the uncompressed stream

An fcomp2 data file contains a few things.  First are 2 longs:  Table and
Stream offsets in the file.  Second is some data, the table, and the stream.
The "some data" can be anything (encryption flags, CRC's, etc).

fcomp2 data file:
TYPE   SIZE    DESC
DWord     4    32 bit offset base 0 (this is AT 0) of where the table is in the
               fire
DWord     4    32 bit base 0 offset of the fcomp2 stream
stream    X    Whatever you want until the table occurs
fcomp2-table Y  The table
fcomp2-stream Z The stream.  The beginning of this is exactly where a pointer to
               offset 0 in the table would point to

I would encourage the open source community to experiment with implimenting
this compression schema.  It is VERY RAM intensive, but a good implimentation
should be able to squeeze great compression ratios from this.  Here are the
requirements for the best implimentation:

1.  Intelligent Table Generation
  Table entries are each 4 bytes in size.  A table should not be generated at a
  point less than 4 bytes from the previous table.
2.  Optimized Table Sorting
  The entries most used in the table should be placed at the beginning; the
  table should be sorted in descending reference order.  Then the pointers must
  be adjusted (must as in this will break the stream if you don't do this) in
  the compressed stream to point to the new locations of the table entries.  In
  adjusting the pointers, the compressor should shrink them to the smallest
  possible size given the index number they must reference and the
  distance/vector they must skip and copy.  For the best optimization, this
  step should also take into account the distance/vector sizes in the pointers,
  to assess how many pointers would gain and lose size in each range of index
  size (1/2/3/4 bytes) and compute the total size gain (positive or negative)
  for each pointer given the positions, and adjust according to these final
  scores.
3.  Intelligent Table Discarding
  When table entries in the table are close enough together, the pointers which
  reference them may be capable of using only a small set from a larger set of
  table entries.  If this is the case, the compressor should remove those table
  entries and readjust all related pointers.

If a compressor is written, it does not have to follow any of the above to have
compatible output with fcomp2 binary files; however, the above guidelines give
the best compression ratios for fcomp2 compressed files.

Re: Swap Compression

[rmoser]

Why keep a fixed page size?  A 4k page can be represented by an
N bit offset in the swap partition (32 for 4 gig or less) and a 13 bit
length description.  Let's not go with the overhead of 13 bit; 16 bit
lengths.  Something divisible by two.  Sure, we gain what
4 + 2 == 6 bytes per page, but we compress out more than that in
most cases (in theory).

and as for RAM, I really prefer the user to control swap-on-ram, and
to have it implimented as such.  4 meg'ers might try SoR but it may
hurt.  The kernel should default to using the RAM swap as its primary
swap partition though.  Why make extra overhead chopping up and
reassembling pages?  We did that with compression.

--Bluefox Icy
(Well that's my opinion)

*********** REPLY SEPARATOR  ***********

On 4/29/2003 at 10:13 AM Timothy Miller wrote:

>Here's a way to keep the two-level swap complexity down, perhaps.
>
>The VM is aware of two kinds of memory space and therefore two kinds of 
>swap.  The first kind of memory is "normal" memory that is used by 
>applications.  When the VM has to swap that, it compresses to RAM.  The 
>second kind of memory is "compressed" memory.  When the VM has to swap 
>that, it swaps it to disk.
>

Swap-on-RAM with compression enabled.

>All swapping operations are done in page units.  Compressed pages will 
>use arbitrary amounts of memory, so when compressed pages are swapped, 
>the boundaries between one compressed page and another are not 
>considered.  Compressed pages will be broken up.  But that's okay, 
>because if there is a page fault in the compressed memory, the VM just 
>swaps in from disk.  Perhaps some intelligent memory management could be 
>employed which reorganizes compressed RAM so that a recently used 
>compressed page does not share a physical page with a compressed page 
>that has not been touched in a while.
>

Ouch.  That introduces extra managment between the compressed RAM
and the swapping procedure.  On the plus, it would save us the hassle
of fragmented swap but heck, idle-time and on-urgent page defragmentation
should take care of that (do I need to explain these concepts?).

>There has been talk of a "simpler" system which compresses to swap 
>without the intermediate level.  The thing is, that intermediate level 
>always exists to some extent.  And trying to manage compressed pages on 
>disk like that can get quite complex.  If we were to compress to a whole 
>number of sectors, just so we could keep things separate, then we would 
>limit the benefit from compressing.  The two level system could be 
>employed to compress to swap simply by keeping the compressed memory 
>fixed and very small.

Re: Re: Swap Compression

[rmoser]

Yeah you did but I'm going into a bit more detail, and with a very tight algorithm.  Heck the algo was originally designed based on another compression algorithm, but for a 6502 packer.  I aimed at speed, simplicity, and minimal RAM usage (hint:  it used 4k for the code AND the compressed data on a 6502, 336 bytes for code, and if I turn it into just a straight packer I can go under 200 bytes on the 6502).

Honestly, I just never looked.  I look in my kernel.  But still, the stuff I defined about swapon options, swap-on-ram, and how the compression works (yes, compressed without headers) is all the detail you need about it to go do it AFAIK.  Preplanning should be done there--done meaning workable, not "the absolute best."

--Bluefox Icy

---- ORIGINAL MESSAGE ----
List:     linux-kernel
Subject:  Re: Swap Compression
From:     John Bradford <john () grabjohn ! com>
Date:     2003-04-25 21:17:11
[Download message RAW]

> Sorry if this is HTML mailed.  I don't know how to control those settings

HTML mail is automatically filtered from LKML.

> COMPRESSED SWAP

We discussed this on the list quite recently, have a look at:

http://marc.theaimsgroup.com/?l=linux-kernel&m=105018674018129&w=2

and:

http://linuxcompressed.sourceforge.net/

John.
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/