Received: by 2002:a05:6a11:4021:0:0:0:0 with SMTP id ky33csp1786848pxb; Fri, 24 Sep 2021 11:49:57 -0700 (PDT) X-Google-Smtp-Source: ABdhPJx6OunnGhLQivCNc7Z0TN820tWvMnIhKhiBqi6mrCz8Rkh0yu05fyRs/w6w8V4BpK6g6xOR X-Received: by 2002:a05:6e02:1a0b:: with SMTP id s11mr8213748ild.19.1632509397496; Fri, 24 Sep 2021 11:49:57 -0700 (PDT) ARC-Seal: i=1; a=rsa-sha256; t=1632509397; cv=none; d=google.com; s=arc-20160816; b=ybILyfkuUNUAJLMV2+4NXV9B1dCXoY1BayTrenYP5mCtzJ4l1BUUDzU6vooVIYKRhV kKsxbrGCQp77B9blYz3wxppDhtUZMAM9CG1hhV0A/P2knIYEUprl59VaAB0F1kWL7t96 H8awpEIUhDGs2dHAiYM8Iub1Nx/+2/tdzpK/Mct06Fecig6AWScIRoPQbDWPU/qup9zw 7k+V285KdYItvo4C/r6c0wpBHCwQnS2ZGiX5tt3fN7YakdiVMkKuEitfwchg+gjX62+x cGRhuU/Bt69ulmDAUrRHbS27zxmp41cgaVdDvXlTVyBYBLJXI2tNF0Hlf3ISzypYiBMG 2iLQ== ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=google.com; s=arc-20160816; h=list-id:precedence:content-transfer-encoding:mime-version :references:in-reply-to:message-id:subject:cc:to:from:date; bh=eyoyvlodttGfA9UoR6KegYIbZwuGM8iUgtigWXSCFp8=; b=y0hnVzqgwvbAPJWPYYrVrhDyjt8OL8o685EP9lTjhrKKWdZySwXu7k3rstEX3bKiaC aFGHocOvH7gat0nmA/GcznsuGfzmClVrRvC8ZRzl+536f6nJXejM4XW1RJk36KKyPe2a zEl8eHEjD9alO7+JqAxBngR6X3VD5SxeUj52DG8QFeB+GwZf5Ze3YpbVB6cSQqGjr4Xo Wodx0BsREbEwoj2Z1rT/jzlMcnYjEAk4sCaeZiJYR5aqkY1UIk2JvXbuEYgNH8HIXOTP gPW6iLFPSutoFkICFptw83oNSxREpK6wgy8l6QQR0iLGqkjd6xaxE4n+5mV4Tp+r6K+b PCYQ== ARC-Authentication-Results: i=1; mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Return-Path: Received: from vger.kernel.org (vger.kernel.org. [23.128.96.18]) by mx.google.com with ESMTP id e18si589300jaa.103.2021.09.24.11.49.46; Fri, 24 Sep 2021 11:49:57 -0700 (PDT) Received-SPF: pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) client-ip=23.128.96.18; Authentication-Results: mx.google.com; spf=pass (google.com: domain of linux-kernel-owner@vger.kernel.org designates 23.128.96.18 as permitted sender) smtp.mailfrom=linux-kernel-owner@vger.kernel.org Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1346348AbhIXNTM (ORCPT + 99 others); Fri, 24 Sep 2021 09:19:12 -0400 Received: from mail.kernel.org ([198.145.29.99]:45246 "EHLO mail.kernel.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1347215AbhIXNSD (ORCPT ); Fri, 24 Sep 2021 09:18:03 -0400 Received: from gandalf.local.home (cpe-66-24-58-225.stny.res.rr.com [66.24.58.225]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by mail.kernel.org (Postfix) with ESMTPSA id 005B760F4C; Fri, 24 Sep 2021 13:16:28 +0000 (UTC) Date: Fri, 24 Sep 2021 09:16:27 -0400 From: Steven Rostedt To: Eugene Syromyatnikov Cc: lkml , Ingo Molnar , Andrew Morton , Masami Hiramatsu , Mathieu Desnoyers , linux-trace-devel@vger.kernel.org Subject: Re: [PATCH 0/2] tracing: Have trace_pid_list be a sparse array Message-ID: <20210924091627.645a8fd3@gandalf.local.home> In-Reply-To: References: <20210924033547.939554938@goodmis.org> <20210924000717.310b492a@rorschach.local.home> X-Mailer: Claws Mail 3.17.8 (GTK+ 2.24.33; x86_64-pc-linux-gnu) MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Precedence: bulk List-ID: X-Mailing-List: linux-kernel@vger.kernel.org On Fri, 24 Sep 2021 12:51:07 +0200 Eugene Syromyatnikov wrote: Hi Eugene, > Note that there is only one top-level chunk (so its size doesn't > matter much), (usually) about one middle-tier chunk (except for some > heavy cases, since pids are allocated linearly), and quite some > lower-tier bitset leaves. So I'd optimise towards smaller leaves at > the expense of middle-tier (and especially top-tier) chunk size > (especially considering the fact that in the kernel, buddy allocator > is used), like 12-8-12 or something like that, but I have no factual What I really like about my 8 8 14 split I have, it makes everything 2K in size on 64 bit machines (1K 1K 2K for 32 bit, but who cares ;-) 1 << 8 * 8 bytes = 2K // top tiers are pointers to lower tiers 1 << 14 bits = 2K // lower tier only cares about bits This means they will likely all be allocated in the same slab. I'm optimizing the top tiers for size, because they are likely to be empty. Why add memory for something that will never be used, and can't be removed. Note, the middle and lower tiers can be reused when they go empty, which is a likely use case (at least when I test this using hackbench). > basis for arguing about specific split. Also, I cannot resist from > noticing that this reminds me an awful lot of XArray and [1]. Maybe, > some wrapper around XArray would do? > > [1] https://gitlab.com/strace/strace/-/raw/master/src/trie.h > I looked into xarray and it appears to be optimized for storing something, where as I'm just interested in a sparse bitmask. Thanks for the review. Note, I'll be posting a v3 soon because I found if I echo 1<<30 into set_event_pid, it adds 0 (because it only looks at the bottom 30 bits). It should really return -EINVAL. -- Steve