[RFC] seqlz: a compressor for zram, between lz4 and zstd

[Martin Leitner-Ankerl]

Hi Sergey, Minchan,

I wrote a compressor only for zram's pages, as a personal project of
mine. Before I send patches I'd like to know if you would consider a new
algorithm for zram at all. Much of the code was written with an AI
coding assistant, with me deciding the design and checking the results.

seqlz stores pages almost as small as zstd and swaps them in close to
lz4. On a Xiaomi Mi 9T with its own Linux 4.14, seqlz as a module,
20 000 pages from the phone's zram, the whole page fault per page:

          bytes/page   swap-in warm, A76 / A55   swap-out, A76 / A55
  lz4        1300          5.3 / 16.2 us        10.3 /  31.2 us
  lzo        1216          6.4 / 17.4           11.2 /  33.9
  zstd 3      898         16.9 / 47.5           34.7 / 133
  seqlz       935          6.0 / 17.9           12.4 /  38.8

So 28% fewer bytes than lz4 and 4% more than zstd. Swap-in is 11% to
13% slower than lz4 warm and 17% to 25% cold, swap-out 20% to 24%
slower. With 25 apps launched in turn, 1.5 GiB locked away and the same
disksize for all, seqlz had 3 cold launches in 3 runs, lz4 24 and zstd
6. With the disksize scaled so that each algorithm gets the same RAM,
lz4 had 54 cold launches in 3 runs and seqlz none.

It is LZ with Huffman coding, but with static tables that are part of
the format, so a page carries no tables. It needs less work memory per
CPU than lz4. The format is written down, and a second decoder written
from that description alone was fuzzed against the real one for over a
billion inputs without a difference.

The backend works on your series of 5th October, "zram: redesign zcomp
and rework backends", applied to mm-unstable at fb0fbeb37, and on
mainline without it (986c24e0fe44). Under KASAN and lockdep it swapped
12.7 million pages on the tree with your series, and 34.9 million on
mainline with UBSan too, preempt=full and lazy, no report and no page
that came back different. The zram selftests pass, and there are KUnit
tests.

What I don't know yet: the phone numbers are from 4.14 only, I have no
rooted phone with a current kernel. With 16 KiB pages seqlz needs more
work memory per CPU than lz4.

My questions:

1. Would you consider a new algorithm for zram, next to lz4, lzo-rle
   and zstd?
2. You wrote in March that zcomp will move to the acomp API [1], and
   your series of October reworks zcomp instead. Should seqlz come as a
   zram backend on top of that series, or as an acomp algorithm?
3. What would you want to see measured to decide?

The code, the format and all measurements are at
https://github.com/martinus/quetschn

Thanks,
Martin

[1] https://lore.kernel.org/r/aa9tz-EIh7kOF3RM@xxxxxxxxxx