From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1754401AbcHXUkD (ORCPT ); Wed, 24 Aug 2016 16:40:03 -0400 Received: from mail.efficios.com ([78.47.125.74]:58845 "EHLO mail.efficios.com" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1751950AbcHXUkB (ORCPT ); Wed, 24 Aug 2016 16:40:01 -0400 Date: Wed, 24 Aug 2016 20:39:45 +0000 (UTC) From: Mathieu Desnoyers To: Matthew Wilcox Cc: "Paul E. McKenney" , linux-kernel , rp@svcs.cs.pdx.edu Message-ID: <1696204792.18122.1472071185916.JavaMail.zimbra@efficios.com> Subject: RCU Judy Array (optimisation over Radix Tree) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: 7bit X-Originating-IP: [78.47.125.74] X-Mailer: Zimbra 8.7.0_GA_1659 (ZimbraWebClient - FF45 (Linux)/8.7.0_GA_1659) Thread-Index: z1E8/O30lc7Kk4+GIuL5WatmEJQiQQ== Thread-Topic: RCU Judy Array (optimisation over Radix Tree) Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org Hi Matthew, Following our discussion at LinuxCon about Radix Trees and Judy Array, here is a pointer to my user-space implementation prototype of RCU Judy Array. I've simplified it a bit (removing features you don't need, just keeping fixed-sized integer keys), and it can still be simplified quite a bit by removing partitioned locking support, but it may contain nice ideas for radix tree improvements regarding the number of cache-lines touched by radix tree lookups. It's available in this branch: https://github.com/urcu/userspace-rcu/tree/urcu/rcuja-simple-int Here are Linux Plumbers 2012 slides and video from a few years ago: http://www.efficios.com/lpc2012-scaling-rcu-judy-arrays-cache-efficient-compact-fast-and-scalable-trie Feedback is welcome! Thanks, Mathieu -- Mathieu Desnoyers EfficiOS Inc. http://www.efficios.com