linux-kernel - RE: [PATCH 0/3] staging: zcache: xcfmalloc support

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Message-ID: <36dad993-ea60-43f4-89f0-77831befd483@default>
Date:	Thu, 1 Sep 2011 08:17:48 -0700 (PDT)
From:	Dan Magenheimer <dan.magenheimer@...cle.com>
To:	Seth Jennings <sjenning@...ux.vnet.ibm.com>
Cc:	gregkh@...e.de, devel@...verdev.osuosl.org, ngupta@...are.org,
	cascardo@...oscopio.com, rdunlap@...otime.net,
	linux-kernel@...r.kernel.org
Subject: RE: [PATCH 0/3] staging: zcache: xcfmalloc support

> > Do you have any data comparing xcfmalloc vs xvmalloc for
> > compression ratio and/or performance (cycles to compress
> > or decompress different pages) on a wide(r) range of data?
> > Assuming xcfmalloc isn't "always better", maybe it would
> > be best to allow the algorithm to be selectable?  (And
> > then we would also need to decide the default.)
> >
> 
> I can get you some results comparing the two tomorrow.
> 
> You have to make the distinction between the
> "compression ratio" and the "effective compression".
> The compression ratio is the same since the compression
> algorithm, LZO, was changed.  The effective compression,

changed -> NOT changed, correct? LZO is used in both?
I had forgotten that, so the only issue might be the
overhead.

> the ratio of stored compressed pages to allocator pool
> pages, is different between the two, especially for
> allocation sets > PAGE_SIZE/2.

> What the numbers will tell you is that for allocations sets
> < PAGE_SIZE/2 xcfmalloc is a little worse (~2% greater
> overhead).  But for allocation sets > PAGE_SIZE/2,
> xcfmalloc has up to a 50% advantage over xvmalloc.
> 
> As far as performance numbers, all I can see is that
> the throughput is the same between the two.  I'm not
> sure how to get, for example, and cycles delta
> between the two.

IIRC, xvmalloc has O(1) overhead regardless of the number
of chunks of data stored.  Some algorithms are O(N) or
even O(N**2), i.e. might walk a potentially increasingly
very long list of allocations/descriptors
to find a slot, which would not be acceptable for
zcache as, for a large data set, the overhead might
be much worse than the cycles-to-compress.  Which is
xcfmalloc, O(1) or O(N) or O(N**2)?

(Also, since I think interrupts are still disabled,
reading the tsc before/after should be safe to
get the cycles delta.)

> I would be difficult to make it selectable because the
> function signatures (and some concepts) aren't the same.
> You can see the changes that were required in the patch
> 2/3.

Then I definitely would like to see some review
and discussion from Nitin.  Clearly xcfmalloc is better
for poorly-compressible data; I would like to be confident
that it is not "worse" for another large common set of
data.

An even better implementation could be if both are
active and the selection is made at runtime depending
on the compressibility of the data, i.e. poorly-compressible
data gets stored in xcfmalloc and other data in xvmalloc?
Probably not worth the effort, but food for thought.

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