llvm dev - Apr 2014 - [LLVMdev] RFC: Binary format for instrumentation based profiling data

On Sat, Mar 22, 2014 at 1:18 AM, Justin Bogner <mail at
justinbogner.com>wrote:
> Chandler Carruth <chandlerc at google.com> writes:
> > I think it would be worthwhile to consider the alternative of having
> > the profile library write out data files in a format which is
> > essentially "always" transformed by a post-processing tool
before
> > being used during compilation.
>
> We seem to have some agreement that two formats for instrumentation
> based profiling is worthwhile. These are that emitted by compiler-rt in
> the instrumented program at runtime (format 1), and that which is
> consumed by clang when compiling the program with PGO (format 2).
>
> Format 1
> --------
>
> This format should be efficient to write, since the instrumented program
> should run with as little overhead as possible. This also doesn't need
> to be stable, and we can assume the same version of LLVM that was used
> to instrument the program will read the counter data. As such, the file
> format is versioned (so we can easily reject versions we don't
> understand) and consists basically of a memory dump of the relevant
> profiling counters.
>
This makes perfect sense to me.

>
> Format 2
> --------
>
> This format should be efficient to read and preferably reasonably
> compact. We'll convert from format 1 to format 2 using llvm-profdata,
> and clang will use format 2 for PGO.
>
> Since the only particularly important operation in this use case is fast
> lookup, I propose using the on disk hash table that's currently used in
> clang for AST serialization/PTH/etc with a small amount of metadata in a
> header.
>
> The hash table implementation currently lives in include/clang/Basic and
> consists of a single header. Moving it to llvm and updating the clients
> in clang should be easy. I'll send a brief RFC separately to see if
> anyone's opposed to moving it.
>
I can mention this and we can discuss this on the other thread if you would
rather, but I'm not a huge fan of this code. My vague memory was that this
was a quick hack by Doug that he never really expected to live long-term.

I have a general preference for from-disk lookups to use tries (for
strings, prefix tries) or other fast, sorted lookup structures. They have
the nice property of being inherently stable and unambiguous, and not
baking any hashing algorithm into it.

I've not thought enough about how to make a general purpose one of these to
have a stronger opinion though; perhaps I should do so...
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140324/874bbcfc/attachment.html>

On Mar 24, 2014, at 12:29 PM, Chandler Carruth <chandlerc at google.com>
wrote:
> Format 2
> --------
> 
> This format should be efficient to read and preferably reasonably
> compact. We'll convert from format 1 to format 2 using llvm-profdata,
> and clang will use format 2 for PGO.
> 
> Since the only particularly important operation in this use case is fast
> lookup, I propose using the on disk hash table that's currently used in
> clang for AST serialization/PTH/etc with a small amount of metadata in a
> header.
> 
> The hash table implementation currently lives in include/clang/Basic and
> consists of a single header. Moving it to llvm and updating the clients
> in clang should be easy. I'll send a brief RFC separately to see if
> anyone's opposed to moving it.
> 
> I can mention this and we can discuss this on the other thread if you would
rather, but I'm not a huge fan of this code. My vague memory was that this
was a quick hack by Doug that he never really expected to live long-term.
> 
> I have a general preference for from-disk lookups to use tries (for
strings, prefix tries) or other fast, sorted lookup structures.
These profiles will contain every function in a program.  Relatively few of
these will be needed per translation unit (per invocation of clang).  I suspect
that an on disk hash will perform better than a trie for this use case, since it
requires fewer loads from disk.

But the main benefit of the clang on-disk hash is that it’s in use and it
already works.  Unless tries are significantly better, I prefer cleaning up the
(working) hash table implementation to implementing (and debugging) something
new.
> They have the nice property of being inherently stable and unambiguous, and
not baking any hashing algorithm into it.
It *is* harder to keep the hash table stable.  I think it’s worth the cost here.

Chandler Carruth <chandlerc at google.com> writes:
>     Format 2
>     --------
>    
>     This format should be efficient to read and preferably reasonably
>     compact. We'll convert from format 1 to format 2 using
llvm-profdata,
>     and clang will use format 2 for PGO.
>    
>     Since the only particularly important operation in this use case is
fast
>     lookup, I propose using the on disk hash table that's currently
used in
>     clang for AST serialization/PTH/etc with a small amount of metadata in
a
>     header.
>    
>     The hash table implementation currently lives in include/clang/Basic
and
>     consists of a single header. Moving it to llvm and updating the clients
>     in clang should be easy. I'll send a brief RFC separately to see if
>     anyone's opposed to moving it.
>
> I can mention this and we can discuss this on the other thread if you would
> rather, but I'm not a huge fan of this code. My vague memory was that
this was
> a quick hack by Doug that he never really expected to live long-term.
It may not be the prettiest piece of code, but given that it's used in
several places in clang and hasn't needed any significant changes since
2010, I'd say it's fairly solid. It also has the very obvious advantage
of already existing, which makes it a pretty good candidate for a
version 1 format, IMHO.
> I have a general preference for from-disk lookups to use tries (for
strings,
> prefix tries) or other fast, sorted lookup structures. They have the nice
> property of being inherently stable and unambiguous, and not baking any
> hashing algorithm into it.
I would like to experiment with a few trie-based approaches for this as
we try to optimize the PGO process further (both for space and for
lookup time). Even so, it's not a sure thing that this will work better,
and I don't think it's worth delaying getting something that people can
use out the door.

If you're opposed to moving the existing OnDiskHashTable into Support,
perhaps because you don't think it should proliferate to other uses,
the obvious alternative is to include a private copy of a stripped down
version of it for the profile reader and writer to use themselves. I'm
not sure if this is worth the copy pasted code, but it is an
option. What do you think?

Chandler, are you okay with this way forward?

Justin Bogner <mail at justinbogner.com> writes:
> Chandler Carruth <chandlerc at google.com> writes:
>>     Format 2
>>     --------
>>    
>>     This format should be efficient to read and preferably reasonably
>>     compact. We'll convert from format 1 to format 2 using
llvm-profdata,
>>     and clang will use format 2 for PGO.
>>    
>>     Since the only particularly important operation in this use case is
fast
>>     lookup, I propose using the on disk hash table that's currently
used in
>>     clang for AST serialization/PTH/etc with a small amount of metadata
in a
>>     header.
>>    
>>     The hash table implementation currently lives in
include/clang/Basic and
>>     consists of a single header. Moving it to llvm and updating the
clients
>>     in clang should be easy. I'll send a brief RFC separately to
see if
>>     anyone's opposed to moving it.
>>
>> I can mention this and we can discuss this on the other thread if you
would
>> rather, but I'm not a huge fan of this code. My vague memory was
that this was
>> a quick hack by Doug that he never really expected to live long-term.
>
> It may not be the prettiest piece of code, but given that it's used in
> several places in clang and hasn't needed any significant changes since
> 2010, I'd say it's fairly solid. It also has the very obvious
advantage
> of already existing, which makes it a pretty good candidate for a
> version 1 format, IMHO.
>
>> I have a general preference for from-disk lookups to use tries (for
strings,
>> prefix tries) or other fast, sorted lookup structures. They have the
nice
>> property of being inherently stable and unambiguous, and not baking any
>> hashing algorithm into it.
>
> I would like to experiment with a few trie-based approaches for this as
> we try to optimize the PGO process further (both for space and for
> lookup time). Even so, it's not a sure thing that this will work
better,
> and I don't think it's worth delaying getting something that people
can
> use out the door.
>
> If you're opposed to moving the existing OnDiskHashTable into Support,
> perhaps because you don't think it should proliferate to other uses,
> the obvious alternative is to include a private copy of a stripped down
> version of it for the profile reader and writer to use themselves. I'm
> not sure if this is worth the copy pasted code, but it is an
> option. What do you think?

On Fri, Mar 28, 2014 at 1:33 PM, Justin Bogner <mail at
justinbogner.com>wrote:
> Chandler Carruth <chandlerc at google.com> writes:
> >     Format 2
> >     --------
> >
> >     This format should be efficient to read and preferably reasonably
> >     compact. We'll convert from format 1 to format 2 using
llvm-profdata,
> >     and clang will use format 2 for PGO.
> >
> >     Since the only particularly important operation in this use case
is
> fast
> >     lookup, I propose using the on disk hash table that's
currently used
> in
> >     clang for AST serialization/PTH/etc with a small amount of
metadata
> in a
> >     header.
> >
> >     The hash table implementation currently lives in
include/clang/Basic
> and
> >     consists of a single header. Moving it to llvm and updating the
> clients
> >     in clang should be easy. I'll send a brief RFC separately to
see if
> >     anyone's opposed to moving it.
> >
> > I can mention this and we can discuss this on the other thread if you
> would
> > rather, but I'm not a huge fan of this code. My vague memory was
that
> this was
> > a quick hack by Doug that he never really expected to live long-term.
>
> It may not be the prettiest piece of code, but given that it's used in
> several places in clang and hasn't needed any significant changes since
> 2010, I'd say it's fairly solid. It also has the very obvious
advantage
> of already existing, which makes it a pretty good candidate for a
> version 1 format, IMHO.
>
So, I've gone and read all of it to try and get a good handle on the
current state rather than dredging up memories from so many years ago. =] I
can speak more confidently now.

The OnDiskHashTable stuff seems perfectly fine for emitting just that - an
on-disk-hash-table. However, it was never designed to support long-lived
file formats in that form. The use in serialized ASTs is specifically not
supporting a long-term file format. The biggest issue there is endianness,
and I see you've already very nicely added good support for that. The only
remaining concern I might have are the 32-bit offset limitations.
While
>2gb of counter data may seem unlikely, I don't think it is
inconceivable,
and even >4gb of counter data might happen. Using 64-bit offsets seems an
easy fix though. Essentially, I think this part of the code could quickly
and easily be made viable for this purpose, although it would require a bit
more cleanup and documenting the intended stability.

Anyways, the part I was truly concerned about is actually nicely factored
out -- the hashing bit. The AST's hashing is *completely* unsuitable for a
long-term file format, but my assumption is that you'd just use the
existing stable PGO hashing stuff for this table? If so, it should work
fine. If you want to hash other things (function names?), I would just urge
using something like their MD5 or some other fixed, and uncontroversial
algorithm so we don't end up wondering how a bug snuck in there N years
later. So this seems workable too.

Essentially, to answer a later question:

If you're opposed to moving the existing OnDiskHashTable into
Support,
> perhaps because you don't think it should proliferate to other uses,
> the obvious alternative is to include a private copy of a stripped down
> version of it for the profile reader and writer to use themselves. I'm
> not sure if this is worth the copy pasted code, but it is an
> option. What do you think?

I think with the cleanups you've started plus a bit more documentation,
this could be a fine candidate for a generic on-disk (or, raw memory
buffer) hash table writer and reader.

OK, on to the general questions rather than ones concerning specific code...

> > I have a general preference for from-disk lookups to use tries (for
> strings,
> > prefix tries) or other fast, sorted lookup structures. They have the
nice
> > property of being inherently stable and unambiguous, and not baking
any
> > hashing algorithm into it.
>
> I would like to experiment with a few trie-based approaches for this as
> we try to optimize the PGO process further (both for space and for
> lookup time). Even so, it's not a sure thing that this will work
better,
>
So the first question is whether it is really worth looking into other
solutions. I have a suspicion that there are better formats for this
because of one key idea: while the important operation is lookup, I don't
think it is truly *random* lookup. In fact, I suspect it will be extremely
structured lookup, with a few hot clusters of data due to similar function
"names" (where the names of things like file-local static functions
get
file name prefixes and such to disambiguate them). So I think that there is
a real locality win possible in this space. Maybe not all the time, and
most of the time it may be below the noise floor, but I think it will still
be there.

> and I don't think it's worth delaying getting something that people
can
> use out the door.
>
If the file format is wide open to change over the coming months, then I'm
totally down with this. Makes perfect sense. However, I get the feeling
that it isn't wide open to change, and we're going to quickly end up
locked
into a particular format here to support the backwards compatibility
concerns. Personally, I'm happy to change the format *very* fluidly, at
least until there is an LLVM release, and potentially even after that, but
it would be good to hear from others that want to consume this data.
-------------- next part --------------
An HTML attachment was scrubbed...
URL:
<http://lists.llvm.org/pipermail/llvm-dev/attachments/20140416/4cfa2195/attachment.html>