Re: [Elftoolchain-developers] Remaining FreeBSD ELF Tool Chain changes in the queue

[Mark J. <ma...@fr...>]

On Sat, Jun 29, 2019 at 10:51:57PM +0100, Joseph Koshy via Elftoolchain-developers wrote:
> > libelf: Use a red-black tree to manage the section list
> > https://reviews.freebsd.org/D20443
> 
> Two questions here:

Hi Joseph,

> 1. Per the FreeBSD Phabricator entry the motivation
>    for this change was to speed up elf_getscn(3).
>    If that is the case, how many sections does the
>    ELF object need to have before the use of a RB tree
>    vs a simpler data structure become relevant? I'm
>    curious if performance measurements were done?

The context for that change is FreeBSD PR 234949
(https://bugs.freebsd.org/bugzilla/show_bug.cgi?id=234949).
It comes from a series of changes which reduces elftoolchain's strip
runtime on an archive of Haskell libraries compiled with
-ffunction-sections.

One of the test files is libHSCabal-2.4.0.1_p.a, which contains 220
objects.  Among them, the minimum number of sections is 26, the
maximum is 46125, and the median and average are 964 and 2085,
respectively.

Reverting just this change (use a red-black tree) increases the runtime
of strip from 4s to 80s for this file.

> 2. The other thing to check would be whether our
>    target platforms have <sys/tree.h> implementations
>    suitable for use from userland.

I know that *BSD provides tree.h and libbsd has a tree.h as well; that
seemed sufficient to me, but maybe I'm missing something?  It seemed
reasonable to use tree.h given that elftoolchain already makes extensive
use of queue.h.