llvm dev - Mar 2015 - [LLVMdev] On LLD performance

Newly-added undefined symbols may be solved by other file in the same
archive, so you've got to restart scanning from beginning. You would visit
the same symbol many times. Is that faster?

On Fri, Mar 20, 2015 at 3:03 PM, Rafael Espíndola <
rafael.espindola at gmail.com> wrote:
>  > I think that wouldn't work. When we find a member file in an
archive
> that
> > resolves an undefined symbol, the file would add both undefined and
> defined
> > symbols. We would need to scan the list of symbols again.
>
> Yes, keep scanning until no member is added.
>
> Cheers,
> Rafael
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150320/14309cad/attachment.html>

On 20 March 2015 at 18:08, Rui Ueyama <ruiu at google.com>
wrote:
> Newly-added undefined symbols may be solved by other file in the same
> archive, so you've got to restart scanning from beginning. You would
visit
> the same symbol many times. Is that faster?
>
I don't expect many passes in practice.

You can also avoid looking at the symbols of members you already
added. To do that you would need to keep just a table of indexes or
"double buffer" the list: at each pass either a member is added or the
symbol pointers are added to the other buffer. At the end of the pass,
swap the buffer.

You can also save the hash computation.

Cheers,
Rafael

On Fri, Mar 20, 2015 at 3:23 PM, Rafael Espíndola <
rafael.espindola at gmail.com> wrote:
> On 20 March 2015 at 18:08, Rui Ueyama <ruiu at google.com> wrote:
> > Newly-added undefined symbols may be solved by other file in the same
> > archive, so you've got to restart scanning from beginning. You
would
> visit
> > the same symbol many times. Is that faster?
> >
>
> I don't expect many passes in practice.
>
I still think we need at least two passes if a symbol is resolved using a
member file (first iteration resolves the symbol, and the second iteration
is to make sure that no more symbols can be resolved using the archive
file.) Two passes is many compared to hash table lookup, no?

It may worth to mention that the hash table construction is paralellized.
We create a hash table for each archive file in parallel because there's no
dependency between them.

> You can also avoid looking at the symbols of members you already
> added. To do that you would need to keep just a table of indexes or
> "double buffer" the list: at each pass either a member is added
or the
> symbol pointers are added to the other buffer. At the end of the pass,
> swap the buffer.
>
> You can also save the hash computation.
>
> Cheers,
> Rafael
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20150320/5721ad37/attachment.html>