Received-SPF: pass (google.com: best guess record for domain of linux-crypto-owner@vger.kernel.org designates 209.132.180.67 as permitted sender) client-ip=209.132.180.67;
From:   Nick Terrell <terrelln@fb.com>
To:     Maninder Singh <maninder1.s@samsung.com>
CC:     Herbert Xu <herbert@gondor.apana.org.au>,
        "davem@davemloft.net" <davem@davemloft.net>,
        "keescook@chromium.org" <keescook@chromium.org>,
        "gustavo@embeddedor.com" <gustavo@embeddedor.com>,
        "linux-crypto@vger.kernel.org" <linux-crypto@vger.kernel.org>,
        "linux-kernel@vger.kernel.org" <linux-kernel@vger.kernel.org>,
        "a.sahrawat@samsung.com" <a.sahrawat@samsung.com>,
        "pankaj.m@samsung.com" <pankaj.m@samsung.com>,
        Vaneet Narang <v.narang@samsung.com>
Subject: Re: [PATCH 2/2] zstd: use U16 data type for rankPos
Thread-Topic: [PATCH 2/2] zstd: use U16 data type for rankPos
Thread-Index: AQHVBwEYf0+ujrSaGEy2U/daRipAjqaPOXKA
Date:   Thu, 6 Jun 2019 20:09:22 +0000
Message-ID: <31A71209-48C0-464D-9578-DBEEF5D16567@fb.com>
References: <CGME20190510061418epcas5p3679447cedd01f3ec70139f79ac7bcca1@epcas5p3.samsung.com>
 <1557468839-3388-1-git-send-email-maninder1.s@samsung.com>
In-Reply-To: <1557468839-3388-1-git-send-email-maninder1.s@samsung.com>
Accept-Language: en-US
Content-Language: en-US
received-spf: None (protection.outlook.com: fb.com does not designate
 permitted sender hosts)
Content-Type: text/plain; charset="us-ascii"
Content-ID: <D9DD0AFACE9A89419EC2781911FC2B00@namprd15.prod.outlook.com>
Content-Transfer-Encoding: quoted-printable
MIME-Version: 1.0
X-MS-Exchange-CrossTenant-Network-Message-Id: f75e8b7c-6279-41a7-5ad9-08d6eabaddaa
X-MS-Exchange-CrossTenant-originalarrivaltime: 06 Jun 2019 20:09:22.1450
 (UTC)
X-MS-Exchange-CrossTenant-fromentityheader: Hosted
X-MS-Exchange-CrossTenant-id: 8ae927fe-1255-47a7-a2af-5f3a069daaa2
X-MS-Exchange-CrossTenant-mailboxtype: HOSTED
X-MS-Exchange-CrossTenant-userprincipalname: terrelln@fb.com
X-MS-Exchange-Transport-CrossTenantHeadersStamped: MW2PR1501MB2169
X-OriginatorOrg: fb.com
X-Proofpoint-Virus-Version: vendor=fsecure engine=2.50.10434:,, definitions=2019-06-06_14:,,
 signatures=0
X-Proofpoint-Spam-Details: rule=fb_default_notspam policy=fb_default score=0 priorityscore=1501
 malwarescore=0 suspectscore=0 phishscore=0 bulkscore=0 spamscore=0
 clxscore=1011 lowpriorityscore=0 mlxscore=0 impostorscore=0
 mlxlogscore=999 adultscore=0 classifier=spam adjust=0 reason=mlx
 scancount=1 engine=8.0.1-1810050000 definitions=main-1906060135
X-FB-Internal: deliver
Sender: linux-crypto-owner@vger.kernel.org
Precedence: bulk
List-ID: <linux-crypto.vger.kernel.org>
X-Mailing-List: linux-crypto@vger.kernel.org

> On May 9, 2019, at 11:13 PM, Maninder Singh <maninder1.s@samsung.com> wro=
te:
>=20
> rankPos structure variables value can not be more than 512.
> So it can easily be declared as U16 rather than U32.
>=20
> It will reduce stack usage of HUF_sort from 256 bytes to 128 bytes
>=20
> original:
> e92ddbf0        push    {r4, r5, r6, r7, r8, r9, fp, ip, lr, pc}
> e24cb004        sub     fp, ip, #4
> e24ddc01        sub     sp, sp, #256    ; 0x100
>=20
> changed:
> e92ddbf0        push    {r4, r5, r6, r7, r8, r9, fp, ip, lr, pc}
> e24cb004        sub     fp, ip, #4
> e24dd080        sub     sp, sp, #128    ; 0x80
>=20
>=20
> Signed-off-by: Maninder Singh <maninder1.s@samsung.com>
> Signed-off-by: Vaneet Narang <v.narang@samsung.com>
> ---
> lib/zstd/huf_compress.c | 4 ++--
> 1 file changed, 2 insertions(+), 2 deletions(-)
>=20
> 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 la=
stNonNull, U32 maxNbBits)
> }
>=20
> 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 patc=
h there,
but in the kernel it makes sense to me.

This function is called by HUF_buildCTable_wksp() which takes a workspace p=
arameter.
We could put this table into the workspace instead to reduce the stack usag=
e 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 vers=
ion. I've opened
up https://github.com/facebook/zstd/issues/1636 to make sure we get this op=
timization in
before porting.

> static void HUF_sort(nodeElt *huffNode, const U32 *count, U32 maxSymbolVa=
lue)
> --=20
> 2.7.4
>=20