[Bug binutils/29993] objcopy --merge-notes slow for large .so with many annobin notes

[nickc at redhat dot com]

https://sourceware.org/bugzilla/show_bug.cgi?id=29993

Nick Clifton <nickc at redhat dot com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Assignee|unassigned at sourceware dot org   |nickc at redhat dot com
                 CC|                            |nickc at redhat dot com
             Status|NEW                         |ASSIGNED

--- Comment #3 from Nick Clifton <nickc at redhat dot com> ---
(In reply to Frank Ch. Eigler from comment #0)
Hi Frank,

> objcopy.c's merge copy seems to be responsible.  There is a
> doubly nested loop over the notes, resulting in O(n**2) complexity.

Not quite...

>    2406   for (pnote = pnotes; pnote < pnotes_end; pnote ++)
>    2407     {
> [...]
>    2426       /* Rule 2: Check to see if there is an identical previous
> note.  */
>    2427       for (iter = 0, back = pnote - 1; back >= pnotes; back --)
>    2428         {
>    2429           if (is_deleted_note (back))
>    2430             continue;

But a few lines further on there is:

          /* Don't scan too far back however.  */
          if (iter ++ > 16)
            {
              /* FIXME: Not sure if this can ever be triggered.  */
              merge_debug ("ITERATION LIMIT REACHED\n");
              break;
            }

So the inner loop only executes a maximum of 16 times per outer iteration. 
Well it inspects 16 non-deleted notes.  If there are lots of deletions then the
loop will continue for longer.  But there is also another optimization:

          /* Our sorting function should have placed all identically
             attributed notes together, so if we see a note of a different
             attribute type stop searching.  */
          if (back->note.namesz != pnote->note.namesz
              || memcmp (back->note.namedata,
                         pnote->note.namedata, pnote->note.namesz) != 0)
            break;

So once the scan reaches a different kind of note it will stop searching.


> Please consider improving the algorithm's performance on this sort of large
> dataset.

Do you have any suggestions ?  I will investigate myself, but if you have any
ideas I would love to hear them.

Cheers
  Nick

-- 
You are receiving this mail because:
You are on the CC list for the bug.