From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eu-smtp-delivery-151.mimecast.com (eu-smtp-delivery-151.mimecast.com [185.58.86.151]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by smtp.subspace.kernel.org (Postfix) with ESMTPS id 886D24D135 for ; Sat, 24 Feb 2024 22:10:38 +0000 (UTC) Authentication-Results: smtp.subspace.kernel.org; arc=none smtp.client-ip=185.58.86.151 ARC-Seal:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1708812641; cv=none; b=ZuPaVy3TgIKuVbSUo8kyQ1vCNT95K07UJz3qg9rDI3YmD/KdQVTIWdosEN4zkvZdPbuxeqHI3MQV0UnifgsdjXH0XwyJf+wu2S0tUfkzDCOOJJJtMYd9IZ0KgveS1K18rwmXRBLLs65MCJbX0PK87/mjCL/R4e+Hu0/9ghJ3bp0= ARC-Message-Signature:i=1; a=rsa-sha256; d=subspace.kernel.org; s=arc-20240116; t=1708812641; c=relaxed/simple; bh=3ptU5r2TNQLqAXFUNm3uyWN2DrpdKyRJ6+9DsuJYWIM=; h=From:To:CC:Subject:Date:Message-ID:References:In-Reply-To: MIME-Version:Content-Type; b=SDou7khAYvwGVswA4le0mUPA7RPe4nkDGD2g2W0qWd3Mr8ocsdbqiTYKJfkUXHV+tVW3fYj7n+3+T2RW0vPulmumO4Zasb4Z0nQi7PjPCcyW8EG+gLGACq8AHJudQpliNoJBNk1NcU8Hi/MWUvSDqPG1To5us7wvDHnL+xU7GwQ= ARC-Authentication-Results:i=1; smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=ACULAB.COM; spf=pass smtp.mailfrom=aculab.com; arc=none smtp.client-ip=185.58.86.151 Authentication-Results: smtp.subspace.kernel.org; dmarc=pass (p=none dis=none) header.from=ACULAB.COM Authentication-Results: smtp.subspace.kernel.org; spf=pass smtp.mailfrom=aculab.com Received: from AcuMS.aculab.com (156.67.243.121 [156.67.243.121]) by relay.mimecast.com with ESMTP with both STARTTLS and AUTH (version=TLSv1.2, cipher=TLS_ECDHE_RSA_WITH_AES_256_CBC_SHA384) id uk-mta-209-K7PK0T93M2GOk-Vn9vdHcA-1; Sat, 24 Feb 2024 22:10:28 +0000 X-MC-Unique: K7PK0T93M2GOk-Vn9vdHcA-1 Received: from AcuMS.Aculab.com (10.202.163.6) by AcuMS.aculab.com (10.202.163.6) with Microsoft SMTP Server (TLS) id 15.0.1497.48; Sat, 24 Feb 2024 22:10:27 +0000 Received: from AcuMS.Aculab.com ([::1]) by AcuMS.aculab.com ([::1]) with mapi id 15.00.1497.048; Sat, 24 Feb 2024 22:10:27 +0000 From: David Laight To: 'Herbert Xu' , "Matthew Wilcox (Oracle)" CC: "linux-kernel@vger.kernel.org" , Thomas Graf , "netdev@vger.kernel.org" , "linux-fsdevel@vger.kernel.org" , "maple-tree@lists.infradead.org" , "rcu@vger.kernel.org" Subject: RE: [PATCH 0/1] Rosebush, a new hash table Thread-Topic: [PATCH 0/1] Rosebush, a new hash table Thread-Index: AQHaZrdg3OPv1gzlbEiBbQpUz0xlprEaCpvw Date: Sat, 24 Feb 2024 22:10:27 +0000 Message-ID: <4a1416fcb3c547eb9612ce07da6a77ed@AcuMS.aculab.com> References: <20240222203726.1101861-1-willy@infradead.org> In-Reply-To: Accept-Language: en-GB, en-US X-MS-Has-Attach: X-MS-TNEF-Correlator: x-ms-exchange-transport-fromentityheader: Hosted Precedence: bulk X-Mailing-List: netdev@vger.kernel.org List-Id: List-Subscribe: List-Unsubscribe: MIME-Version: 1.0 X-Mimecast-Spam-Score: 0 X-Mimecast-Originator: aculab.com Content-Language: en-US Content-Type: text/plain; charset=UTF-8 Content-Transfer-Encoding: quoted-printable From: Herbert Xu > Sent: 24 February 2024 00:21 >=20 > On Thu, Feb 22, 2024 at 08:37:23PM +0000, Matthew Wilcox (Oracle) wrote: > > > > Where I expect rosebush to shine is on dependent cache misses. > > I've assumed an average chain length of 10 for rhashtable in the above > > memory calculations. That means on average a lookup would take five ca= che > > misses that can't be speculated. Rosebush does a linear walk of 4-byte >=20 > Normally an rhashtable gets resized when it reaches 75% capacity > so the average chain length should always be one. The average length of non-empty hash chains is more interesting. You don't usually search for items in empty chains. The only way you'll get all the chains of length one is if you've carefully picked the data so that it hashed that way. I remember playing around with the elf symbol table for a browser and all its shared libraries. While the hash function is pretty trivial, it really didn't matter whether you divided 2^n, 2^n-1 or 'the prime below 2^n' some hash chains were always long. =09David - Registered Address Lakeside, Bramley Road, Mount Farm, Milton Keynes, MK1 1= PT, UK Registration No: 1397386 (Wales)