Re: [PATCH 2/2] zstd: use U16 data type for rankPos

From: Nick Terrell
Date: Thu Jun 06 2019 - 16:14:02 EST


> On May 9, 2019, at 11:13 PM, Maninder Singh <maninder1.s@xxxxxxxxxxx> wrote:
>
> rankPos structure variables value can not be more than 512.
> So it can easily be declared as U16 rather than U32.
>
> It will reduce stack usage of HUF_sort from 256 bytes to 128 bytes
>
> original:
> e92ddbf0 push {r4, r5, r6, r7, r8, r9, fp, ip, lr, pc}
> e24cb004 sub fp, ip, #4
> e24ddc01 sub sp, sp, #256 ; 0x100
>
> changed:
> e92ddbf0 push {r4, r5, r6, r7, r8, r9, fp, ip, lr, pc}
> e24cb004 sub fp, ip, #4
> e24dd080 sub sp, sp, #128 ; 0x80
>
>
> Signed-off-by: Maninder Singh <maninder1.s@xxxxxxxxxxx>
> Signed-off-by: Vaneet Narang <v.narang@xxxxxxxxxxx>
> ---
> lib/zstd/huf_compress.c | 4 ++--
> 1 file changed, 2 insertions(+), 2 deletions(-)
>
> diff --git a/lib/zstd/huf_compress.c b/lib/zstd/huf_compress.c
> index e727812..2203124 100644
> --- a/lib/zstd/huf_compress.c
> +++ b/lib/zstd/huf_compress.c
> @@ -382,8 +382,8 @@ static U32 HUF_setMaxHeight(nodeElt *huffNode, U32 lastNonNull, U32 maxNbBits)
> }
>
> typedef struct {
> - U32 base;
> - U32 curr;
> + U16 base;
> + U16 curr;
> } rankPos;

This seems fine to me. I measured zstd's performance in userspace with this change,
and there is a ~1% speed regression for level 1. We wouldn't take this patch there,
but in the kernel it makes sense to me.

This function is called by HUF_buildCTable_wksp() which takes a workspace parameter.
We could put this table into the workspace instead to reduce the stack usage by the whole
256 bytes. We'd just have to make sure that the workspace is large enough.

Eventually I will update the zstd in the kernel to the latest upstream version. I've opened
up https://github.com/facebook/zstd/issues/1636 to make sure we get this optimization in
before porting.

> static void HUF_sort(nodeElt *huffNode, const U32 *count, U32 maxSymbolValue)
> --
> 2.7.4
>