From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: (majordomo@vger.kernel.org) by vger.kernel.org via listexpand id S1753680AbeAZPOi (ORCPT ); Fri, 26 Jan 2018 10:14:38 -0500 Received: from smtp.codeaurora.org ([198.145.29.96]:50736 "EHLO smtp.codeaurora.org" rhost-flags-OK-OK-OK-OK) by vger.kernel.org with ESMTP id S1753393AbeAZPOf (ORCPT ); Fri, 26 Jan 2018 10:14:35 -0500 DMARC-Filter: OpenDMARC Filter v1.3.2 smtp.codeaurora.org 0FDBC600C9 Authentication-Results: pdx-caf-mail.web.codeaurora.org; dmarc=none (p=none dis=none) header.from=codeaurora.org Authentication-Results: pdx-caf-mail.web.codeaurora.org; spf=none smtp.mailfrom=cpandya@codeaurora.org Subject: Re: [PATCH v2] of: use hash based search in of_find_node_by_phandle To: Rasmus Villemoes , robh+dt@kernel.org, frowand.list@gmail.com, devicetree@vger.kernel.org Cc: linux-kernel@vger.kernel.org, linux-arm-msm@vger.kernel.org References: <1516955496-17236-1-git-send-email-cpandya@codeaurora.org> From: Chintan Pandya Message-ID: Date: Fri, 26 Jan 2018 20:44:22 +0530 User-Agent: Mozilla/5.0 (Windows NT 10.0; WOW64; rv:52.0) Gecko/20100101 Thunderbird/52.5.2 MIME-Version: 1.0 In-Reply-To: Content-Type: text/plain; charset=utf-8; format=flowed Content-Transfer-Encoding: 8bit Content-Language: en-US Sender: linux-kernel-owner@vger.kernel.org List-ID: X-Mailing-List: linux-kernel@vger.kernel.org > I'm probably missing something obvious, but: Aren't phandles in practice > small consecutive integers assigned by dtc? If so, why not just have a > smallish static array mapping the small phandle values directly to > device node, instead of adding a pointer to every struct device_node? Or > one could determine the size of the array dynamically (largest seen > phandle value, capping at something sensible, e.g. 1024). Haven't noticed this earlier !! If following is known or true, we can avoid using hash-table and save per device_node hlish_node.     1. How to know max phandle value without traversing tree once? In my case,        max is 1263.     2. Although, I haven't observed collision but is it like every device_node        is associated with unique phandle value ? > In either case, one would still need to keep the code doing the > whole-tree traversal for handling large phandle values, but I think the > above should make lookup O(1) in most cases. I would refrain doing this because that will make this API inconsistent in terms of time taken by different nodes. I see that people do change their device placing in DT and that changes time taken in of_* APIs for them but affecting others. > Alternatively, one could just count the number of nodes with a phandle, > allocate an array of that many pointers (so the memory use is certainly > no more than if adding a pointer to each device_node), and sort it by > phandle, so one can do lookup using a binary search. > > Rasmus This is certainly doable if current approach is not welcomed due to addition on hlish_node in device_node. Chintan Pandya -- The Qualcomm Innovation Center, Inc. is a member of the Code Aurora Forum, a Linux Foundation Collaborative Project