Re: [PATCH v8 0/6] Btrfs: populate heuristic with code

[David Sterba]

On Sun, Oct 22, 2017 at 04:44:04PM +0300, Timofey Titovets wrote:
> 2017-10-20 16:45 GMT+03:00 David Sterba :
> > On Fri, Oct 20, 2017 at 01:48:01AM +0300, Timofey Titovets wrote:
> >> 2017-10-19 18:39 GMT+03:00 David Sterba :
> >> > On Fri, Sep 29, 2017 at 06:22:00PM +0200, David Sterba wrote:
> >> >> On Thu, Sep 28, 2017 at 05:33:35PM +0300, Timofey Titovets wrote:
> >> >> > Compile tested, hand tested on live system
> >> >> >
> >> >> > Change v7 -> v8
> >> >> >   - All code moved to compression.c (again)
> >> >> >   - Heuristic workspaces inmplemented another way
> >> >> > i.e. only share logic with compression workspaces
> >> >> >   - Some style fixes suggested by Devid
> >> >> >   - Move sampling function from heuristic code
> >> >> > (I'm afraid of big functions)
> >> >> >   - Much more comments and explanations
> >> >>
> >> >> Thanks for the update, I went through the patches and they looked good
> >> >> enough to be put into for-next. I may have more comments about a few
> >> >> things, but nothing serious that would hinder testing.
> >> >
> >> > I did a final pass through the patches and edited comments wehre I was
> >> > not able to undrerstand them. Please check the updated patches in [1] if
> >> > I did not accidentally change the meaning.
> >>
> >> I don't see a link [1] in mail, may be you missed it?
> >
> > Yeah, sorry:
> > https://github.com/kdave/btrfs-devel/commits/ext/timofey/heuristic
> 
> I did re-read updated comments, looks ok to me
> (i only found one typo, leave a comment).

Thanks, fixed and branch added to the rest for 4.15.
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v8 0/6] Btrfs: populate heuristic with code

[Timofey Titovets]

2017-10-22 16:44 GMT+03:00 Timofey Titovets :
> 2017-10-20 16:45 GMT+03:00 David Sterba :
>> On Fri, Oct 20, 2017 at 01:48:01AM +0300, Timofey Titovets wrote:
>>> 2017-10-19 18:39 GMT+03:00 David Sterba :
>>> > On Fri, Sep 29, 2017 at 06:22:00PM +0200, David Sterba wrote:
>>> >> On Thu, Sep 28, 2017 at 05:33:35PM +0300, Timofey Titovets wrote:
>>> >> > Compile tested, hand tested on live system
>>> >> >
>>> >> > Change v7 -> v8
>>> >> >   - All code moved to compression.c (again)
>>> >> >   - Heuristic workspaces inmplemented another way
>>> >> > i.e. only share logic with compression workspaces
>>> >> >   - Some style fixes suggested by Devid
>>> >> >   - Move sampling function from heuristic code
>>> >> > (I'm afraid of big functions)
>>> >> >   - Much more comments and explanations
>>> >>
>>> >> Thanks for the update, I went through the patches and they looked good
>>> >> enough to be put into for-next. I may have more comments about a few
>>> >> things, but nothing serious that would hinder testing.
>>> >
>>> > I did a final pass through the patches and edited comments wehre I was
>>> > not able to undrerstand them. Please check the updated patches in [1] if
>>> > I did not accidentally change the meaning.
>>>
>>> I don't see a link [1] in mail, may be you missed it?
>>
>> Yeah, sorry:
>> https://github.com/kdave/btrfs-devel/commits/ext/timofey/heuristic
>
> I did re-read updated comments, looks ok to me
> (i only found one typo, leave a comment).
>
>
> Thanks
> --
> Have a nice day,
> Timofey.

Can you please try that patch? (in attach)

I think some time about performance hit of heuristic and
how to avoid using sorting,

That patch will try prefind min/max values (before sorting) in array,
and (max - min), used to filter edge data cases where
byte core size < 64 or bigger > 200
It's a bit hacky workaround =\,
That show a ~same speedup on my data set as show using of radix sort.
(i.e. x2 speed up)

Thanks.

-- 
Have a nice day,
Timofey.
From fb2a329828e64ad0e224a8cb97dbc17147149629 Mon Sep 17 00:00:00 2001
From: Timofey Titovets 
Date: Mon, 23 Oct 2017 21:24:29 +0300
Subject: [PATCH] Btrfs: heuristic try avoid bucket sorting on edge data cases

Heap sort used in kernel are too slow and costly,
So let's make some statistic assume about egde input data cases
Based on observation of difference between min/max values in bucket.

Signed-off-by: Timofey Titovets 
---
 fs/btrfs/compression.c | 38 ++
 1 file changed, 38 insertions(+)

diff --git a/fs/btrfs/compression.c b/fs/btrfs/compression.c
index 0ca16909894e..56b67ec4fb5b 100644
--- a/fs/btrfs/compression.c
+++ b/fs/btrfs/compression.c
@@ -1310,8 +1310,46 @@ static int byte_core_set_size(struct heuristic_ws *ws)
 	u32 i;
 	u32 coreset_sum = 0;
 	const u32 core_set_threshold = ws->sample_size * 90 / 100;
+	struct bucket_item *max, *min;
+	struct bucket_item tmp;
 	struct bucket_item *bucket = ws->bucket;
 
+
+	/* Presort for find min/max value */
+	max = [0];
+	min = [BUCKET_SIZE - 1];
+	for (i = 1; i < BUCKET_SIZE - 1; i++) {
+		if (bucket[i].count > max->count) {
+			tmp = *max;
+			*max = bucket[i];
+			bucket[i] = tmp;
+		}
+		if (bucket[i].count < min->count) {
+			tmp = *min;
+			*min = bucket[i];
+			bucket[i] = tmp;
+		}
+	}
+
+	/*
+	 * Hacks for avoid sorting on Edge data cases (sorting too constly)
+	 * i.e. that will fast filter easy compressible
+	 * and bad compressible data
+	 * Based on observation of number distribution on different data sets
+	 *
+	 * Assume 1: For bad compressible data distribution between min/max
+	 * will be less then 0.6% of sample size
+	 *
+	 * Assume 2: For good compressible data distribution between min/max
+	 * will be far bigger then 4% of sample size
+	 */
+
+	if (max->count - min->count < ws->sample_size * 6 / 1000)
+		return BYTE_CORE_SET_HIGH + 1;
+
+	if (max->count - min->count > ws->sample_size * 4 / 100)
+		return BYTE_CORE_SET_LOW - 1;
+
 	/* Sort in reverse order */
 	sort(bucket, BUCKET_SIZE, sizeof(*bucket), _comp_rev, NULL);
 
-- 
2.14.2

Re: [PATCH v8 0/6] Btrfs: populate heuristic with code

[Timofey Titovets]

2017-10-20 16:45 GMT+03:00 David Sterba :
> On Fri, Oct 20, 2017 at 01:48:01AM +0300, Timofey Titovets wrote:
>> 2017-10-19 18:39 GMT+03:00 David Sterba :
>> > On Fri, Sep 29, 2017 at 06:22:00PM +0200, David Sterba wrote:
>> >> On Thu, Sep 28, 2017 at 05:33:35PM +0300, Timofey Titovets wrote:
>> >> > Compile tested, hand tested on live system
>> >> >
>> >> > Change v7 -> v8
>> >> >   - All code moved to compression.c (again)
>> >> >   - Heuristic workspaces inmplemented another way
>> >> > i.e. only share logic with compression workspaces
>> >> >   - Some style fixes suggested by Devid
>> >> >   - Move sampling function from heuristic code
>> >> > (I'm afraid of big functions)
>> >> >   - Much more comments and explanations
>> >>
>> >> Thanks for the update, I went through the patches and they looked good
>> >> enough to be put into for-next. I may have more comments about a few
>> >> things, but nothing serious that would hinder testing.
>> >
>> > I did a final pass through the patches and edited comments wehre I was
>> > not able to undrerstand them. Please check the updated patches in [1] if
>> > I did not accidentally change the meaning.
>>
>> I don't see a link [1] in mail, may be you missed it?
>
> Yeah, sorry:
> https://github.com/kdave/btrfs-devel/commits/ext/timofey/heuristic

I did re-read updated comments, looks ok to me
(i only found one typo, leave a comment).


Thanks
-- 
Have a nice day,
Timofey.
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v8 0/6] Btrfs: populate heuristic with code

[David Sterba]

On Fri, Oct 20, 2017 at 01:48:01AM +0300, Timofey Titovets wrote:
> 2017-10-19 18:39 GMT+03:00 David Sterba :
> > On Fri, Sep 29, 2017 at 06:22:00PM +0200, David Sterba wrote:
> >> On Thu, Sep 28, 2017 at 05:33:35PM +0300, Timofey Titovets wrote:
> >> > Compile tested, hand tested on live system
> >> >
> >> > Change v7 -> v8
> >> >   - All code moved to compression.c (again)
> >> >   - Heuristic workspaces inmplemented another way
> >> > i.e. only share logic with compression workspaces
> >> >   - Some style fixes suggested by Devid
> >> >   - Move sampling function from heuristic code
> >> > (I'm afraid of big functions)
> >> >   - Much more comments and explanations
> >>
> >> Thanks for the update, I went through the patches and they looked good
> >> enough to be put into for-next. I may have more comments about a few
> >> things, but nothing serious that would hinder testing.
> >
> > I did a final pass through the patches and edited comments wehre I was
> > not able to undrerstand them. Please check the updated patches in [1] if
> > I did not accidentally change the meaning.
> 
> I don't see a link [1] in mail, may be you missed it?

Yeah, sorry:
https://github.com/kdave/btrfs-devel/commits/ext/timofey/heuristic
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v8 0/6] Btrfs: populate heuristic with code

[Timofey Titovets]

2017-10-19 18:39 GMT+03:00 David Sterba :
> On Fri, Sep 29, 2017 at 06:22:00PM +0200, David Sterba wrote:
>> On Thu, Sep 28, 2017 at 05:33:35PM +0300, Timofey Titovets wrote:
>> > Compile tested, hand tested on live system
>> >
>> > Change v7 -> v8
>> >   - All code moved to compression.c (again)
>> >   - Heuristic workspaces inmplemented another way
>> > i.e. only share logic with compression workspaces
>> >   - Some style fixes suggested by Devid
>> >   - Move sampling function from heuristic code
>> > (I'm afraid of big functions)
>> >   - Much more comments and explanations
>>
>> Thanks for the update, I went through the patches and they looked good
>> enough to be put into for-next. I may have more comments about a few
>> things, but nothing serious that would hinder testing.
>
> I did a final pass through the patches and edited comments wehre I was
> not able to undrerstand them. Please check the updated patches in [1] if
> I did not accidentally change the meaning.

I don't see a link [1] in mail, may be you missed it?
I look at my patches in for-next branch, and that's not looks like
changed, so i assume your link not point at kernel.org %).

> I'm about to add the patchset to the main patch pile for 4.15 soon.
> Further tuning is possible and such patches will be probably accepted
> during the 4.15 development cycle once the as parts have landed. It's
> desirable to gather some testing results of heuristic effects on various
> data types. So far I've been watching for performance drops only.

Just for my information, you compare compress + heuristic with
compression force?

P.S.
Just to sync that we expect from heuristic:
it's expected to get some performance drops on easy compressible data, because
heuristic not free,
but how much this drops?
Main reason for heuristic, it's to win cpu/latency cost for bad
compressible data.
In compare to direct compression.
That allow to provide some worst case stable latency/throughput for userspace.

P.S.S.
I send some emails before, where i show slow paths in heuristic
(sort(), ilog2()).
So i expect that kernel can see same slow downs on that paths.
But i'm don't have enough skills for now, to perform kernel profiling.

> In case the heuristic would turn out to cause problems we can't fix
> during 4.15 cycle, we can still disable it. This is only a last resort
> measure but we need to be prepared.
kk

Thanks.


-- 
Have a nice day,
Timofey.
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v8 0/6] Btrfs: populate heuristic with code

[David Sterba]

On Fri, Sep 29, 2017 at 06:22:00PM +0200, David Sterba wrote:
> On Thu, Sep 28, 2017 at 05:33:35PM +0300, Timofey Titovets wrote:
> > Compile tested, hand tested on live system
> > 
> > Change v7 -> v8
> >   - All code moved to compression.c (again)
> >   - Heuristic workspaces inmplemented another way
> > i.e. only share logic with compression workspaces
> >   - Some style fixes suggested by Devid
> >   - Move sampling function from heuristic code
> > (I'm afraid of big functions)
> >   - Much more comments and explanations
> 
> Thanks for the update, I went through the patches and they looked good
> enough to be put into for-next. I may have more comments about a few
> things, but nothing serious that would hinder testing.

I did a final pass through the patches and edited comments wehre I was
not able to undrerstand them. Please check the updated patches in [1] if
I did not accidentally change the meaning.

I'm about to add the patchset to the main patch pile for 4.15 soon.
Further tuning is possible and such patches will be probably accepted
during the 4.15 development cycle once the as parts have landed. It's
desirable to gather some testing results of heuristic effects on various
data types. So far I've been watching for performance drops only.

In case the heuristic would turn out to cause problems we can't fix
during 4.15 cycle, we can still disable it. This is only a last resort
measure but we need to be prepared.
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

Re: [PATCH v8 0/6] Btrfs: populate heuristic with code

[David Sterba]

On Thu, Sep 28, 2017 at 05:33:35PM +0300, Timofey Titovets wrote:
> Compile tested, hand tested on live system
> 
> Change v7 -> v8
>   - All code moved to compression.c (again)
>   - Heuristic workspaces inmplemented another way
> i.e. only share logic with compression workspaces
>   - Some style fixes suggested by Devid
>   - Move sampling function from heuristic code
> (I'm afraid of big functions)
>   - Much more comments and explanations

Thanks for the update, I went through the patches and they looked good
enough to be put into for-next. I may have more comments about a few
things, but nothing serious that would hinder testing.
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html

[PATCH v8 0/6] Btrfs: populate heuristic with code

[Timofey Titovets]

Based on linux master 4.14-rc2
Duplicated to github:
https://github.com/Nefelim4ag/linux/tree/heuristic_v8

Compile tested, hand tested on live system

Patches short:
1. Implement workspaces for heuristic
   Separate heuristic/compression workspaces
   Main target for that patch:
   Maximum code sharing, minimum changes

2. Add heuristic counters and buffer to workspaces
   Add some base macros for heuristic

3. Implement simple input data sampling
   It's get 16 byte samples with 256 bytes shifts
   over input data. Collect info about how many
   different bytes (symbols) has been found in sample data
   (i.e. systematic sampling used for now)

4. Implement check sample to repeated data
   Just iterate over sample and do memcmp()
   ex. will detect zeroed data

5. Add code for calculate how many unique bytes has been found
   in sample data.
   That heuristic can detect text like data (configs, xml, json, html & etc)
   Because in most text like data byte set are restricted to limit number
   of possible characters, and that restriction in most cases
   make data easy compressible.

6. Add code for calculate byte core set size
   i.e. how many unique bytes use 90% of sample data

   Several type of structured binary data have in general
   nearly all types of bytes, but distribution can be Uniform
   where in bucket all byte types will have the nearly same count
   (ex. Encrypted data)
   and as ex. Normal (Gaussian), where count of bytes will be not so linear

   That code require that numbers in bucket must be sorted
   That can detect easy compressible data with many repeated bytes
   That can detect not compressible data with evenly distributed bytes

Changes v1 -> v2:
  - Change input data iterator shift 512 -> 256
  - Replace magic macro numbers with direct values
  - Drop useless symbol population in bucket
as no one care about where and what symbol stored
in bucket at now

Changes v2 -> v3 (only update #3 patch):
  - Fix u64 division problem by use u32 for input_size
  - Fix input size calculation start - end -> end - start
  - Add missing sort.h header

Changes v3 -> v4 (only update #1 patch):
  - Change counter type in bucket item u16 -> u32
  - Drop other fields from bucket item for now,
no one use it

Change v4 -> v5
  - Move heuristic code to external file
  - Make heuristic use compression workspaces
  - Add check sample to zeroes

Change v5 -> v6
  - Add some code to hande page unaligned range start/end
  - replace sample zeroed check with check for repeated data

Change v6 -> v7
  - Add missing part of first patch
  - Make use of IS_ALIGNED() for check tail aligment

Change v7 -> v8
  - All code moved to compression.c (again)
  - Heuristic workspaces inmplemented another way
i.e. only share logic with compression workspaces
  - Some style fixes suggested by Devid
  - Move sampling function from heuristic code
(I'm afraid of big functions)
  - Much more comments and explanations

Timofey Titovets (6):
  Btrfs: compression.c separated heuristic/compression workspaces
  Btrfs: heuristic workspace add bucket and sample items, macros
  Btrfs: implement heuristic sampling logic
  Btrfs: heuristic add detection of repeated data patterns
  Btrfs: heuristic add byte set calculation
  Btrfs: heuristic add byte core set calculation

 fs/btrfs/compression.c | 393 +
 1 file changed, 366 insertions(+), 27 deletions(-)

--
2.14.2
--
To unsubscribe from this list: send the line "unsubscribe linux-btrfs" in
the body of a message to majord...@vger.kernel.org
More majordomo info at  http://vger.kernel.org/majordomo-info.html