mm/zsmalloc: avoid unnecessary iteration in get_pages_per_zspage()

PATCH In review Ganesh Mahendran 3 participants 9 messages May 5, 2016 – May 11, 2016

Subsystems (2)

Memory management Zsmalloc compressed slab memory allocator

lore

Share & tools

lore

Ganesh Mahendran

author

2016-05-05 05:17 UTC #0 lore raw

PATCH 1/1 mm/zsmalloc: avoid unnecessary iteration in get_pages_per_zspage()

if we find a zspage with usage == 100%, there is no need to try other zspages.

Signed-off-by Ganesh Mahendran <[email protected]>

Cc Minchan Kim <[email protected]>

Cc Nitin Gupta <[email protected]>

Cc Sergey Senozhatsky <[email protected]>

---
 mm/zsmalloc.c |    3 +++
 1 file changed, 3 insertions(+)

mm/zsmalloc.c +3 -0

index fda7177..310c7b0 100644
@@ -765,6 +765,9 @@ static int get_pages_per_zspage(int class_size)
 		if (usedpc > max_usedpc) {
 			max_usedpc = usedpc;
 			max_usedpc_order = i;
+
+			if (max_usedpc == 100)
+				break;
 		}
 	}

Signature · 1 line

1.7.9.5

Sergey Senozhatsky

2016-05-05 10:01 UTC #1 lore raw

Quoted 2 lines · Ganesh Mahendran

if we find a zspage with usage == 100%, there is no need to try other zspages.

Hello,

well... we iterate there from 0 to 1<<2, which is not awfully a lot to break it in the middle, and we do this only when we initialize a new pool (for every size class).

the check is
- true 15 times
- false 492 times

so it _sort of_ feels like this new if-condition doesn't buy us a lot, and most of the time it just sits there with no particular gain. let's hear from Minchan.

-ss

Quoted 25 lines

Signed-off-by Ganesh Mahendran <[email protected]>
Cc Minchan Kim <[email protected]>
Cc Nitin Gupta <[email protected]>
Cc Sergey Senozhatsky <[email protected]>
---
 mm/zsmalloc.c |    3 +++
 1 file changed, 3 insertions(+)
mm/zsmalloc.c +3 -0
index fda7177..310c7b0 100644
@@ -765,6 +765,9 @@ static int get_pages_per_zspage(int class_size)
 		if (usedpc > max_usedpc) {
 			max_usedpc = usedpc;
 			max_usedpc_order = i;
+
+			if (max_usedpc == 100)
+				break;
 		}
 	}
 
Signature · 1 line
1.7.9.5

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in the body to [email protected]. For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Minchan Kim

maintainer

2016-05-06 03:09 UTC #2 lore raw

Quoted 6 lines · Sergey Senozhatsky

Quoted 2 lines · Ganesh Mahendran
if we find a zspage with usage == 100%, there is no need to try other zspages.
Hello,

Quoted 7 lines

well... we iterate there from 0 to 1<<2, which is not awfully a lot to break it in the middle, and we do this only when we initialize a new pool (for every size class).
the check is
- true 15 times
- false 492 times

Thanks for the data, Sergey!

Quoted 5 lines

so it _sort of_ feels like this new if-condition doesn't buy us a lot, and most of the time it just sits there with no particular gain. let's hear from Minchan.

I agree with Sergey.
First of al, I appreciates your patch, Ganesh! But as Sergey pointed out, I don't see why it improves current zsmalloc.
If you want to merge strongly, please convince me with more detail reason.

Thanks.

Quoted 24 lines

	-ss
Quoted 22 lines
Signed-off-by Ganesh Mahendran <[email protected]>
Cc Minchan Kim <[email protected]>
Cc Nitin Gupta <[email protected]>
Cc Sergey Senozhatsky <[email protected]>
---
 mm/zsmalloc.c |    3 +++
 1 file changed, 3 insertions(+)
mm/zsmalloc.c +3 -0
index fda7177..310c7b0 100644
@@ -765,6 +765,9 @@ static int get_pages_per_zspage(int class_size)
 		if (usedpc > max_usedpc) {
 			max_usedpc = usedpc;
 			max_usedpc_order = i;
+
+			if (max_usedpc == 100)
+				break;
 		}
 	}
 

Quoted 3 lines

Quoted 3 lines
Signature · 1 line
1.7.9.5

Ganesh Mahendran

author

2016-05-06 04:25 UTC #3 lore raw

Hi, Minchan:

2016-05-06 11:09 GMT+08:00 Minchan Kim <[email protected]>:

Quoted 18 lines · Sergey Senozhatsky

Quoted 6 lines · Ganesh Mahendran
Quoted 2 lines
if we find a zspage with usage == 100%, there is no need to try other zspages.
Hello,
Quoted 7 lines
well... we iterate there from 0 to 1<<2, which is not awfully a lot to break it in the middle, and we do this only when we initialize a new pool (for every size class).
the check is
- true 15 times
- false 492 times
Thanks for the data, Sergey!
Quoted 1 line

Quoted 8 lines

Quoted 4 lines
so it _sort of_ feels like this new if-condition doesn't buy us a lot, and most of the time it just sits there with no particular gain. let's hear from Minchan.
I agree with Sergey.
First of al, I appreciates your patch, Ganesh! But as Sergey pointed out, I don't see why it improves current zsmalloc.

This patch does not obviously improve zsmalloc.
It just reduces unnecessary code path.

Quoted 1 line

From data provided by Sergey, 15 * (4 - 1) = 45 times loop will be avoided.

So 45 times of below caculation will be reduced:
---
zspage_size = i * PAGE_SIZE;
waste = zspage_size % class_size;
usedpc = (zspage_size - waste) * 100 / zspage_size;

if (usedpc > max_usedpc) {
---

Thanks.

Quoted 30 lines

If you want to merge strongly, please convince me with more detail reason.

Thanks.

Quoted 24 lines

-ss

Quoted 22 lines

Signed-off-by Ganesh Mahendran <[email protected]>

Cc Minchan Kim <[email protected]>

Cc Nitin Gupta <[email protected]>

Cc Sergey Senozhatsky <[email protected]>

---
 mm/zsmalloc.c |    3 +++
 1 file changed, 3 insertions(+)

mm/zsmalloc.c +3 -0

index fda7177..310c7b0 100644
@@ -765,6 +765,9 @@ static int get_pages_per_zspage(int class_size)
            if (usedpc > max_usedpc) {
                    max_usedpc = usedpc;
                    max_usedpc_order = i;
+
+                   if (max_usedpc == 100)
+                           break;
            }
    }

Quoted 3 lines

Quoted 3 lines
Quoted 3 lines
--
1.7.9.5

Minchan Kim

maintainer

2016-05-06 04:36 UTC #4 lore raw

Hi Ganesh,

Quoted 33 lines · Ganesh Mahendran

Hi, Minchan:
2016-05-06 11:09 GMT+08:00 Minchan Kim <[email protected]>:
Quoted 18 lines · Sergey Senozhatsky
Quoted 6 lines · Ganesh Mahendran
Quoted 2 lines
if we find a zspage with usage == 100%, there is no need to try other zspages.
Hello,
Quoted 7 lines
well... we iterate there from 0 to 1<<2, which is not awfully a lot to break it in the middle, and we do this only when we initialize a new pool (for every size class).
the check is
- true 15 times
- false 492 times
Thanks for the data, Sergey!
Quoted 1 line
Quoted 8 lines
Quoted 4 lines
so it _sort of_ feels like this new if-condition doesn't buy us a lot, and most of the time it just sits there with no particular gain. let's hear from Minchan.
I agree with Sergey.
First of al, I appreciates your patch, Ganesh! But as Sergey pointed out, I don't see why it improves current zsmalloc.
This patch does not obviously improve zsmalloc.
It just reduces unnecessary code path.

Quoted 8 lines

From data provided by Sergey, 15 * (4 - 1) = 45 times loop will be avoided. So 45 times of below caculation will be reduced:
---
zspage_size = i * PAGE_SIZE;
waste = zspage_size % class_size;
usedpc = (zspage_size - waste) * 100 / zspage_size;
if (usedpc > max_usedpc) {

As well, it bloats code side without much gain. I don't think it's worth to do until someone really has trouble with slow zs_create_pool performance.

add/remove: 0/0 grow/shrink: 1/0 up/down: 15/0 (15)

function                                     old     new   delta
zs_create_pool                               960     975     +15

Quoted 34 lines

---
Thanks.
Quoted 30 lines
If you want to merge strongly, please convince me with more detail reason.
Thanks.
Quoted 24 lines
      -ss
Quoted 22 lines
Signed-off-by Ganesh Mahendran <[email protected]>
Cc Minchan Kim <[email protected]>
Cc Nitin Gupta <[email protected]>
Cc Sergey Senozhatsky <[email protected]>
---
 mm/zsmalloc.c |    3 +++
 1 file changed, 3 insertions(+)
mm/zsmalloc.c +3 -0
index fda7177..310c7b0 100644
@@ -765,6 +765,9 @@ static int get_pages_per_zspage(int class_size)
            if (usedpc > max_usedpc) {
                    max_usedpc = usedpc;
                    max_usedpc_order = i;
+
+                   if (max_usedpc == 100)
+                           break;
            }
    }
 

Quoted 3 lines

Quoted 3 lines
Quoted 3 lines
Quoted 3 lines
--
1.7.9.5

Sergey Senozhatsky

2016-05-06 09:06 UTC #5 lore raw

In reply to Ganesh Mahendran

On (05/06/16 12:25), Ganesh Mahendran wrote:
[..]

Quoted 14 lines

Quoted 3 lines
I agree with Sergey.
First of al, I appreciates your patch, Ganesh! But as Sergey pointed out, I don't see why it improves current zsmalloc.
This patch does not obviously improve zsmalloc.
It just reduces unnecessary code path.
From data provided by Sergey, 15 * (4 - 1) = 45 times loop will be avoided. So 45 times of below caculation will be reduced:
---
zspage_size = i * PAGE_SIZE;
waste = zspage_size % class_size;
usedpc = (zspage_size - waste) * 100 / zspage_size;

Quoted 2 lines

if (usedpc > max_usedpc) {
---

Hello,

I kinda believe we end up doing more work (instruction-count-wise), actually. it adds 495 cmp' for false case + 15 cmp je' for true case to eliminate 15 `mov cltd idiv mov sub imul cltd idiv cmp' *.

and it's not 45 iterations that we are getting rid of, but around 31:
not every class reaches it's ideal 100% ratio on the first iteration. so, no, sorry, I don't think the patch really does what we want.

* by the way, we don't even need `cltd' in those calculations. the reason why gcc puts cltd is because ZS_MAX_PAGES_PER_ZSPAGE has the 'wrong' data type. the patch to correct it is below (not a formal patch).

** well, we force gcc to generate worse' code in several more places. for example, there is no need for obj_idx' and obj_offset' to be unsigned long', it can easly (and probably must) be unsigned int', or simply int'. that can save some instructions in very-very hot paths:

add/remove: 0/0 grow/shrink: 1/6 up/down: 1/-27 (-26)

function                                     old     new   delta
obj_free                                     234     235      +1
obj_to_location                               45      44      -1
obj_malloc                                   234     233      -1
zs_malloc                                    817     815      -2
obj_idx_to_offset                             32      28      -4
zs_unmap_object                              556     551      -5

zs_compact 1611 1597 -14

I can cook a trivial patch later.

/*
* on x86_64, gcc 6.1. no idea what does the picture look like on ARM32.
* but smells like these two patches combined can make CPU a little less
* busy.
*/

=====================================================================

ZS_MAX_PAGES_PER_ZSPAGE defined as 'unsigned long' which forces the compiler to generate unneeded signed extension instructions `cltd' in several places. for instance:

     711:       44 89 d0                mov    %r10d,%eax
     714:       99                      cltd
     715:       41 f7 fe                idiv   %r14d
     718:       44 89 d0                mov    %r10d,%eax
     71b:       29 d0                   sub    %edx,%eax
     71d:       6b c0 64                imul   $0x64,%eax,%eax
     720:       99                      cltd
     721:       41 f7 fa                idiv   %r10d

there is no reason to do this and ZS_MAX_PAGES_PER_ZSPAGE can simply be 'int'.

the patch reduces the code size, a bit:

add/remove: 0/0 grow/shrink: 0/1 up/down: 0/-25 (-25)

function                                     old     new   delta
zs_malloc                                    842     817     -25

Signed-off-by Sergey Senozhatsky <[email protected]>

---
 mm/zsmalloc.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)

mm/zsmalloc.c +1 -1

index f9b58d1..1c28e0f6 100644
@@ -78,7 +78,7 @@
  * pages. ZS_MAX_ZSPAGE_ORDER defines upper limit on N.
  */
 #define ZS_MAX_ZSPAGE_ORDER 2
-#define ZS_MAX_PAGES_PER_ZSPAGE (_AC(1, UL) << ZS_MAX_ZSPAGE_ORDER)
+#define ZS_MAX_PAGES_PER_ZSPAGE (1 << ZS_MAX_ZSPAGE_ORDER)
 
 #define ZS_HANDLE_SIZE (sizeof(unsigned long))

Signature · 7 lines

2.8.2

--
To unsubscribe, send a message with 'unsubscribe linux-mm' in
the body to [email protected].  For more info on Linux MM,
see: http://www.linux-mm.org/ .
Don't email: <a href=mailto:"[email protected]"> [email protected] </a>

Sergey Senozhatsky

2016-05-06 09:32 UTC #6 lore raw

On (05/06/16 18:08), Sergey Senozhatsky wrote:
[..]

Quoted 3 lines

and it's not 45 iterations that we are getting rid of, but around 31:
not every class reaches it's ideal 100% ratio on the first iteration. so, no, sorry, I don't think the patch really does what we want.

to be clear, what I meant was:

495 cmp' + 15 cmp je' IN
31 `mov cltd idiv mov sub imul cltd idiv cmp' OUT

IN > OUT.

CORRECTION here:

Quoted 4 lines

* by the way, we don't even need `cltd' in those calculations. the reason why gcc puts cltd is because ZS_MAX_PAGES_PER_ZSPAGE has the 'wrong' data type. the patch to correct it is below (not a formal patch).

no, we need cltd there. but ZS_MAX_PAGES_PER_ZSPAGE also affects ZS_MIN_ALLOC_SIZE, which is used in several places, like get_size_class_index(). that's why ZS_MAX_PAGES_PER_ZSPAGE data type change `improves' zs_malloc().

-ss

Minchan Kim

maintainer

2016-05-09 05:01 UTC #7 lore raw

Quoted 22 lines · Sergey Senozhatsky

On (05/06/16 18:08), Sergey Senozhatsky wrote:
[..]
Quoted 3 lines
and it's not 45 iterations that we are getting rid of, but around 31:
not every class reaches it's ideal 100% ratio on the first iteration. so, no, sorry, I don't think the patch really does what we want.
to be clear, what I meant was:
495 cmp' + 15 cmp je' IN
31 `mov cltd idiv mov sub imul cltd idiv cmp' OUT
IN > OUT.
CORRECTION here:
Quoted 4 lines
* by the way, we don't even need `cltd' in those calculations. the reason why gcc puts cltd is because ZS_MAX_PAGES_PER_ZSPAGE has the 'wrong' data type. the patch to correct it is below (not a formal patch).

Quoted 4 lines

no, we need cltd there. but ZS_MAX_PAGES_PER_ZSPAGE also affects ZS_MIN_ALLOC_SIZE, which is used in several places, like get_size_class_index(). that's why ZS_MAX_PAGES_PER_ZSPAGE data type change `improves' zs_malloc().

Why not if such simple improves zsmalloc? :)
Please send a patch.

Thanks a lot, Sergey!

Sergey Senozhatsky

2016-05-11 09:33 UTC #8 lore raw

On (05/09/16 14:01), Minchan Kim wrote:
[..]

Quoted 9 lines

Quoted 4 lines
no, we need cltd there. but ZS_MAX_PAGES_PER_ZSPAGE also affects ZS_MIN_ALLOC_SIZE, which is used in several places, like get_size_class_index(). that's why ZS_MAX_PAGES_PER_ZSPAGE data type change `improves' zs_malloc().
Why not if such simple improves zsmalloc? :)
Please send a patch.
Thanks a lot, Sergey!

Hello Minchan,

sorry for long reply, I decided to investigate it a bit further. with this patch, gcc 6.1 -O2 generates "+13" instructions more, -Os "-25" instructions less. this +13 ins case is a no-no-no.

-ss