Re: [PATCH v4 1/2] of: cache phandle nodes to reduce cost of of_find_node_by_phandle()

[Frank Rowand]

On 02/28/18 12:19, Andy Shevchenko wrote:
> On Wed, Feb 28, 2018 at 9:44 PM, Frank Rowand <frowand.list@xxxxxxxxx> wrote:
>> On 02/28/18 11:31, Andy Shevchenko wrote:
>>> On Wed, Feb 28, 2018 at 9:04 PM,  <frowand.list@xxxxxxxxx> wrote:
> 
>>> The question is why O(1) is so important? O(log(n)) wouldn't work?
>>
>> O(1) is not critical.  It was just a nice side result.
>>
>>
>>> Using radix_tree() I suppose allows to dynamically extend or shrink
>>> the cache which would work with DT overlays.
>>
>> The memory usage of the phandle cache in this patch is fairly small.
>> The memory overhead of a radix_tree() would not be justified.
> 
> OTOH the advantage I mentioned isn't a good argument?

No.  Deleting and re-creating the cache to resize it (when applying an
overlay) would be a rare event that would happen as desired by the
overlay application code.  There is no real gain by having extension
or shrinkage occur automatically and if the overlay application code
desires the resizing it is trivial to implement (a single function
call).