Implement tick events compression in a log file.

Implement tick events compression in a log file.

Two techniques are involved:
 - compress repeated line ends (common stack beginnings) by using back references;
 - do RLE compression of repeated tick events.

This gives only 5% size reduction on benchmarks run, but this is because tick events are only comprise 10% of file size. Under Chromium winnings are bigger because long repeated samples of idleness are now compressed into a single line.

Tickprocessor will be updated in the next patch.

Committed: http://code.google.com/p/v8/source/detail?r=2147

[Søren Thygesen Gjesse, 2009-06-11 11:13:56]

LGTM

Maybe log the value of kRecordCompressorWindow when compressing (like aliases
are logged) to let the client know the maximum backreference number to expect.

Is the handling of fields when compression actually required? Maybe the index to
a previous record could be a char position instead of a field position, and then
you can avoid the search for separators.

Btw. have you looked into using a higher base that 16 (hex) for logging
addresses? I think that will improve compression as well.

http://codereview.chromium.org/123012/diff/1/2
File src/log-utils.cc (right):

http://codereview.chromium.org/123012/diff/1/2#newcode355
Line 355: prev_ = curr_++;
Maybe add a comment here saying that we keep a circular bufer of the
kRecordCompressorWindow last records.

http://codereview.chromium.org/123012/diff/1/2#newcode392
Line 392: // Compare strings backwards, stop on the last matching character.
I am not sure how expensive this is, but perhaps comparing 4 chars at a time
using a uint32_t pointer instead of a char pointer can make a difference, even
though there is the edge case of moving to the first 4 byte aligned char.

http://codereview.chromium.org/123012/diff/1/2#newcode405
Line 405: && (prev_ptr != prev.start() && *(prev_ptr - 1) != kFieldSeparator
Will prev_ptr ever become prev.start() as the do loop starts by incrementing
prev_ptr? Maybe assert that instead.

http://codereview.chromium.org/123012/diff/1/4
File src/log.cc (right):

http://codereview.chromium.org/123012/diff/1/4#newcode858
Line 858: ++tick_repeat_count_;
Maybe we want to report something once in a while even if events are the same
e.g after 1s (X repeated events depending on the sample interval)?

http://codereview.chromium.org/123012/diff/1/7
File test/cctest/test-log-utils.cc (right):

http://codereview.chromium.org/123012/diff/1/7#newcode157
Line 157: void CheckCompression(LogRecordCompressor* comp,
Not that it's a big deal, but you could use a reference parameter here.

http://codereview.chromium.org/123012/diff/1/7#newcode165
Line 165: void CheckCompression(LogRecordCompressor* comp,
Ditto.

http://codereview.chromium.org/123012/diff/1/7#newcode265
Line 265: // string_1 is out of buffer by now, so it shouldn't be compressed.
Add an assert for kRecordCompressorWindow to easily spot why this test have
failed. E.g. make this function a friend of LogRecordCompressor and assert to
length of the buffer.

[Mikhail Naganov, 2009-06-11 14:07:12]

Thanks for comments!

> Maybe log the value of kRecordCompressorWindow when compressing (like aliases
> are logged) to let the client know the maximum backreference number to expect.

Done.

> Is the handling of fields when compression actually required? Maybe the index
to
> a previous record could be a char position instead of a field position, and
then
> you can avoid the search for separators.

Yes, you're right. Initially I thought that having references to fields makes
parsing easier, but then decided that I can cope with it. And since it really
simplifies the code, I've removed it.

> Btw. have you looked into using a higher base that 16 (hex) for logging
> addresses? I think that will improve compression as well.

Instead I've implemented using offsets instead of absolute addresses wherever
possible and dropping "0x" prefix (coming in next CL). For offsets using higher
base will not win much, though.

http://codereview.chromium.org/123012/diff/1/2
File src/log-utils.cc (right):

http://codereview.chromium.org/123012/diff/1/2#newcode355
Line 355: prev_ = curr_++;
On 2009/06/11 11:13:56, Søren Gjesse wrote:
> Maybe add a comment here saying that we keep a circular bufer of the
> kRecordCompressorWindow last records.

Done.

http://codereview.chromium.org/123012/diff/1/2#newcode392
Line 392: // Compare strings backwards, stop on the last matching character.
On 2009/06/11 11:13:56, Søren Gjesse wrote:
> I am not sure how expensive this is, but perhaps comparing 4 chars at a time
> using a uint32_t pointer instead of a char pointer can make a difference, even
> though there is the edge case of moving to the first 4 byte aligned char.

I'm aware of this optimization, but don't want to introduce it. This code runs
in a separate thread, so it doesn't affect V8's performance.

http://codereview.chromium.org/123012/diff/1/2#newcode405
Line 405: && (prev_ptr != prev.start() && *(prev_ptr - 1) != kFieldSeparator
On 2009/06/11 11:13:56, Søren Gjesse wrote:
> Will prev_ptr ever become prev.start() as the do loop starts by incrementing
> prev_ptr? Maybe assert that instead.

I've removed field alignment, so this code has gone.

http://codereview.chromium.org/123012/diff/1/4
File src/log.cc (right):

http://codereview.chromium.org/123012/diff/1/4#newcode858
Line 858: ++tick_repeat_count_;
On 2009/06/11 11:13:56, Søren Gjesse wrote:
> Maybe we want to report something once in a while even if events are the same
> e.g after 1s (X repeated events depending on the sample interval)?

I think this is not needed. Overflow of a counter will only happen after about
24 days. Also, as I've noticed, in Chromium even idle application doesn't stuck
in the same place for a while. Every incoming event causes it to resume
execution, so PC or SP periodically changes.

http://codereview.chromium.org/123012/diff/1/7
File test/cctest/test-log-utils.cc (right):

http://codereview.chromium.org/123012/diff/1/7#newcode157
Line 157: void CheckCompression(LogRecordCompressor* comp,
On 2009/06/11 11:13:56, Søren Gjesse wrote:
> Not that it's a big deal, but you could use a reference parameter here.

I'm modifying Compressor's state, to I'm treating it as an input/output
parameter.

http://codereview.chromium.org/123012/diff/1/7#newcode265
Line 265: // string_1 is out of buffer by now, so it shouldn't be compressed.
On 2009/06/11 11:13:56, Søren Gjesse wrote:
> Add an assert for kRecordCompressorWindow to easily spot why this test have
> failed. E.g. make this function a friend of LogRecordCompressor and assert to
> length of the buffer.

Actually, it doesn't depend on kRecordCompressorWindow, but instead on the
parameter passed to LogRecordCompressor's constructor in this test. But I added
an assertion anyway.