HeapSnapshot: replace O(N*ln(N)) algorithm of sorting with O(N) one.

HeapSnapshot: replace O(N*ln(N)) algorithm of sorting with O(N) one.

We have HashMap for the strings. They got id sequentially. So we could use index sort.

BUG=none
R=alph@chromium.org, yangguo@chromium.org

Committed: https://code.google.com/p/v8/source/detail?r=16734

[alph, 2013-09-16 11:18:09]

https://codereview.chromium.org/24174002/diff/1/src/heap-snapshot-generator.cc
File src/heap-snapshot-generator.cc (right):

https://codereview.chromium.org/24174002/diff/1/src/heap-snapshot-generator.c...
src/heap-snapshot-generator.cc:2696: Vector<HashMap::Entry*> sorted_strings =
A vector of strings instead of Entries should be a bit faster.

https://codereview.chromium.org/24174002/diff/1/src/heap-snapshot-generator.c...
src/heap-snapshot-generator.cc:2701:
sorted_strings[reinterpret_cast<uintptr_t>(entry->value)] = entry;
nit: parentheses

[loislo, 2013-09-16 12:05:20]

On 2013/09/16 11:18:09, alph wrote:
> https://codereview.chromium.org/24174002/diff/1/src/heap-snapshot-generator.cc
> File src/heap-snapshot-generator.cc (right):
> 
>
https://codereview.chromium.org/24174002/diff/1/src/heap-snapshot-generator.c...
> src/heap-snapshot-generator.cc:2696: Vector<HashMap::Entry*> sorted_strings =
> A vector of strings instead of Entries should be a bit faster.

done

> 
>
https://codereview.chromium.org/24174002/diff/1/src/heap-snapshot-generator.c...
> src/heap-snapshot-generator.cc:2701:
> sorted_strings[reinterpret_cast<uintptr_t>(entry->value)] = entry;
> nit: parentheses

done

[alph, 2013-09-16 12:17:50]

lgtm

[Yang, 2013-09-16 12:45:10]

I suppose that the value is set by GetStringId, which assigns it by a growing
index, making it unrelated to the string content. In that case, the sort order
is arbitrary, even if reproducible. Why do we need it to be sorted to begin
with?

https://codereview.chromium.org/24174002/diff/7001/src/heap-snapshot-generato...
File src/heap-snapshot-generator.cc (right):

https://codereview.chromium.org/24174002/diff/7001/src/heap-snapshot-generato...
src/heap-snapshot-generator.cc:2697: Vector<const unsigned
char*>::New(strings_.occupancy() + 1);
We don't seem to call Dispose on the Vector anywhere. Leak?

https://codereview.chromium.org/24174002/diff/7001/src/heap-snapshot-generato...
src/heap-snapshot-generator.cc:2700: entry = strings_.Next(entry)) {
indentation is a bit off.

[loislo, 2013-09-16 13:08:25]

On 2013/09/16 12:45:10, Yang wrote:
> I suppose that the value is set by GetStringId, which assigns it by a growing
> index, making it unrelated to the string content. In that case, the sort order
> is arbitrary, even if reproducible. Why do we need it to be sorted to begin
> with?

heap snapshot has number of strings inside as node names and edge names.
We are keeping these strings in strings part of the snapshot and use their
indexes in the nodes and edges.
We could put the names into strings part in the same order as they appears in
the nodes and in the edges parts.
But in that case many strings will have duplicates.
So we maps the strings into indexes. But we don't serialize indexes itself for
reducing the transfer size.



> 
>
https://codereview.chromium.org/24174002/diff/7001/src/heap-snapshot-generato...
> File src/heap-snapshot-generator.cc (right):
> 
>
https://codereview.chromium.org/24174002/diff/7001/src/heap-snapshot-generato...
> src/heap-snapshot-generator.cc:2697: Vector<const unsigned
> char*>::New(strings_.occupancy() + 1);
> We don't seem to call Dispose on the Vector anywhere. Leak?

done

> 
>
https://codereview.chromium.org/24174002/diff/7001/src/heap-snapshot-generato...
> src/heap-snapshot-generator.cc:2700: entry = strings_.Next(entry)) {
> indentation is a bit off.

done

[Yang, 2013-09-16 13:11:20]

On 2013/09/16 13:08:25, loislo wrote:
> On 2013/09/16 12:45:10, Yang wrote:
> > I suppose that the value is set by GetStringId, which assigns it by a
growing
> > index, making it unrelated to the string content. In that case, the sort
order
> > is arbitrary, even if reproducible. Why do we need it to be sorted to begin
> > with?
> 
> heap snapshot has number of strings inside as node names and edge names.
> We are keeping these strings in strings part of the snapshot and use their
> indexes in the nodes and edges.
> We could put the names into strings part in the same order as they appears in
> the nodes and in the edges parts.
> But in that case many strings will have duplicates.
> So we maps the strings into indexes. But we don't serialize indexes itself for
> reducing the transfer size.
> 
> 
> 
> > 
> >
>
https://codereview.chromium.org/24174002/diff/7001/src/heap-snapshot-generato...
> > File src/heap-snapshot-generator.cc (right):
> > 
> >
>
https://codereview.chromium.org/24174002/diff/7001/src/heap-snapshot-generato...
> > src/heap-snapshot-generator.cc:2697: Vector<const unsigned
> > char*>::New(strings_.occupancy() + 1);
> > We don't seem to call Dispose on the Vector anywhere. Leak?
> 
> done
> 
> > 
> >
>
https://codereview.chromium.org/24174002/diff/7001/src/heap-snapshot-generato...
> > src/heap-snapshot-generator.cc:2700: entry = strings_.Next(entry)) {
> > indentation is a bit off.
> 
> done

LGTM.

I actually meant that the indentation for the for loop should look like
for (var i = 0;
     i < 10;
     i++) {}

so that the items in the bracket line up with each other, not with the bracket.

[loislo, 2013-09-16 13:13:58]

Committed patchset #4 manually as r16734 (presubmit successful).